2 - Logique en math et en info

FAUX pour 0 VIDE, VRAI pour tout le reste

C'est la méthode qu’utilise Python et que nous avions déjà vu sur le transtypage avec bool().

FAUX correspond à 0, None et tous les contenus vides : () [] {} ""

VRAI correspond à tout le reste.

FAUX pour 0, VRAI pour 1

On travaille uniquement avec 0 et 1.

FAUX correspond à 0 uniquement.

VRAI correspond à 1 uniquement.

Algèbre de Boole

L'algèbre de Boole est la branche des mathématiques qui traite de la logique avec une approche algébrique : on ramène la logique à un simple calcul à base d'additions, de multiplications...

L'algèbre de Boole doit son nom à son créateur : le mathématicien britannique George Boole, en 1854.

Principe

Dans la plupart des langages de programmation (dont Python), on dit que l'évaluation des expressions logiques est paresseuse.

Qu'est-ce que cela veut-dire pour un ET ?

Simplement qu'on évalue les expressions de gauche à droite, et dès qu'on rencontre une expression évaluée à FAUX, on arrête d'évaluer : la réponse est nécessairement FAUX !

Sur l'exemple du ET à 3 expressions d'entrée, on aurait ceci :

Conclusion

CONCLUSION : l'ordre dans lequel on fournit les expressions à évaluer peut rendre l'évaluation d'un ET long ou rapide ! Provoquer une erreur ou pas.

Exemple

On commence par vérifier que la note est bien un entier AVANT de tenter de la comparer à 0 puis à 20.

CAS 1 : 0 pour FAUX, le reste pour VRAI

On peut toujours associer les éléments d'un ensemble dénombrable à des indices entiers.

Si on interpréte FAUX pour l'indice 0 et VRAI pour tous les autres indices, le OU peut être vu comme l'évaluation booléenne de a + b

Voici les valeurs calculées et l'interprétation obtenue :

Pour avoir moins besoin de se demander tout cela, on peut simplement comprendre que L'interprétation usuelle est donc de considérer que l'opérateur + est ici l'opérateur booléen et qu'avec cet opérateur 1+1 donne 1 comme pour dire VRAI+VRAI donne VRAI.

CAS 2 : 0 pour FAUX, 1 pour VRAI

D'un point de vue rigoureux, si 0 et 1 sont les seules valeurs disponibles, le OU devrait se calculer ainsi : a + b - a.b

Voici les valeurs calculées qui reste bien dans {0, 1} et ne nécessite donc pas d'interprétation supplémentaire :

Encore une fois, plutôt que de réaliser ce calcul, pourquoi ne pas simplement considérer que 1 + 1 donne 1 tout simplement.

Conclusion

Principe

Dans certains langages de programmation, dont Python, on dit que l'évaluation des expressions logiques est paresseuse.

Qu'est-ce que cela veut-dire pour un OU ?

Simplement qu'on évalue les expressions de gauche à droite.

Dès qu'on rencontre une expression évaluée à VRAI, on arrête d'évaluer : la réponse est nécessairement VRAI !

Sur l'exemple du OU à 3 entrées, on aurait ceci :

Conclusion

CONCLUSION : l'ordre dans lequel on évalue les choses peut rendre l'évaluation d'un OU long ou rapide ! Provoquer une erreur ou pas.

Exemple

On commence par vérifier si la note est en réalité A puis sinon, si c'est un entier AVANT de tenter de la comparer à 0 puis à 20.

Le problème de l'inattention

Voyons comment nous pourrions éviter ceci avec de la syntaxe :

Le symbole + représente plusieurs opérateurs différents, c'est ça l'ambiguïté :

• Dans 4 + 16, + symbolise l'addition sur les entiers.

Nous pourrions noter 4 +_int 16 = 20

• Dans 4.2 + 16.4, + symbolise l'addition sur les flottants.

Nous pourrions noter 4.2 +_flo 16.4 = 20.6

• Dans 1001₂ + 1₂, + symbolise l'addition binaire bit à bit.

Nous pourrions noter 1001₂ +_bin 1₂ = 1010₂.

• Dans 1 + 1 dans l'algèbre de Boole, + symbolise l'addition logique dans l'ensemble de Boole {0, 1}.

Nous pourrions noter 1_B +_bool 1_B = 1_B.

• Dans '1' + '1', + symbolise la concaténation de strings.

Si nous notions '1' +_str '1', cela serait plus clair. Ca donne "11".

Les cas à connaitre

En décimal

Ce sont les calculs normaux.

• 1 + 1 = 2
• 1 + 1 + 1 = 3

En binaire

Ce sont les calculs exprimés en binaire et nécessitant de faire les additions colonne par colonne (bit à bit).

• 1 + 1 = 10 (ce qui exprime 2 en décimal)
• 1 + 1 + 1 = 11 (ce qui exprime 3 en décimal)

En logique booléenne

Ce sont les calculs sur la vérité.

• 1 + 1 = 1 (ce qui exprime que VRAI OU VRAI donne VRAI)
• 1 + 1 + 1 = 1 (ce qui exprime que VRAI OU VRAI OU VRAI donne VRAI)

NAND décrit avec AND

Le NON-ET est l'inverse du ET. Son complément.

Si on sait écrire mathématiquement un ET logique, on sait donc écrire un NON-ET.

Le NAND est le complément du AND : $\overline{a.b}$

NAND décrit avec OR : les lois de De Morgan

Les lois de De Morgan sont des identités entre propositions logiques. Elles ont été formulées par le mathématicien britannique Augustus De Morgan (1806-1871).

L'une des ces lois est la suivante :

$\overline{a.b}=\bar{a}+\bar{b}$

Cela revient à dire ceci :

not(a and b) = not a or not b

Puisque que not est prioritaire sur or, les parenthèses ne sont pas obligatoires. On peut bien entendu les rajouter si on veut :

not(a and b) = (not a) or (not b)

NOR décrit avec OR

Le NON-OU est l'inverse du OU. Son complément.

Si on sait écrire mathématiquement un OU logique, on sait donc écrire un NON-OU.

Le NOR est le complément du OR : $\overline{a+b}$

NOR décrit avec AND : les lois de De Morgan

L'une des ces lois est la suivante :

$\overline{a+b}=\bar{a}.\bar{b}$

Cela revient à dire ceci :

not(a or b) = not a and not b

Puisque que not est prioritaire sur and, les parenthèses ne sont pas obligatoires. On peut bien entendu les rajouter si on veut :

not(a or b) = (not a) and (not b)

Algèbre booléenne

• 0 pour FAUX
• 1 pour VRAI

Attention, les symboles + et . ci-dessous ne correspondent pas à l'addition et la multiplication classique. Ils ne s'appliquent qu'à des termes booléens et l'addition réagit de cette façon :

AND

Le AND correspond à la multiplication booléenne : $a.b$

OR

Le OR correspond à l'addition booléenne : $a+b$

NAND

Le NAND est le complément du AND : $\overline{a.b}$

NOR

Le NOR est le complément du OR : $\overline{a+b}$

XOR

Le XOR  : $a\oplus b=a.\bar{b}+\bar{a}.b$

Lois de De Morgan

$\overline{a.b}=\bar{a}+\bar{b}$

not(a and b) = (not a) or (not b)

not(a and b) =  not a  or  not b

Version symétrique avec le OR :

$\overline{a+b}=\bar{a}.\bar{b}$

not(a or b) = (not a) and (not b)

not(a or b) =  not a  and  not b

Système complet

Un ensemble donné d'opérateurs logiques est dit complet s'il permet de recréer tous les autres opérateurs logiques.

Voici quelques ensembles complets :

• {NOT, AND}
• {NOT, OR}
• {NAND}
• {NOR}

Exemple du {NOT, AND}

Les lois de De Morgan permettent facilement de montrer que ce système est complet.

• a NAND b = NOT (a AND b)
• a NOR b = NOT (a OR b) = NOT a AND NOT b
• a OR b = NOT (a NOR b) = NOT (NOT a AND NOT b)

Evaluation paresseuse

Dès qu'on rencontre une expression évaluée à FAUX dans un ET, on arrête : la réponse est nécessairement FAUX.

Dès qu'on rencontre une expression évaluée à VRAI dans un OU, on arrête : la réponse est nécessairement VRAI.

Priorité des opérateurs logiques entre eux

• D'abord le NON
• Ensuite le AND (*)
• Enfin le OR (+)

Priorité des opérateurs logiques par rapport aux autres

• D'abord les opérateurs arithmétiques (* + ...)
• Ensuite les opérateurs d'appartenance et de comparaison (in > ==...)
• Enfin les opérateurs logiques (NON ET OU)