2 - Logique en math et en info

Première façon de voir les choses : 0 pour FAUX, le reste pour VRAI

C'est la façon usuelle de traiter la vérité dans Python par exemple.

On travaille avec l'ensemble des valeurs possibles.

FAUX correspond à 0 et tous les contenus vides ( tuple (), tableau [], dictionnaire {} ou string "" ou None).

VRAI correspond à tout le reste.

Deuxième façon de voir les choses : 0 pour FAUX, 1 pour VRAI

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.

L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphonique par Claude Shannon. C'est pour cela qu'on retrouve toutes ces notions à la fois en informatique, en électronique et dans les télécommunications.

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.

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 expresion é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 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

Le problème de l'inattention

Voyons comment nous pourrions éviter ceci pour le néophyte :

Le problème vient du fait qu'on utilise le symbole + pour représenter plusieurs opérateurs différents :

• Dans 4 + 16, le + symbolise l'addition 'décimale) sur les entiers.

Si nous notions 4 +_ENT 16, cela serait plus clair. Ca donne 20.

• Dans 4.2 + 16.4, le + symbolise l'addition (décimale) sur les flottants.

Si nous notions 4.2 +_FLO 16.4, cela serait plus clair. Ca donne 20.6

• Dans 1001₂ + 1₂ en binaire, le + symbolise l'addition (binaire) bit à bit.

Si nous notions 1001₂ +_BIN 1₂, cela serait plus clair. Ca donne 1001₂ +_BIN 0001₂, soit 1010₂.

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

Si nous notions 1001₂ +_BIN 1₂, cela serait plus clair. Ca donne 1001₂ +_BIN 0001₂, soit 1010₂.

• Dans '1' + '1', le + 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 normaux, mais exprimés en binaire et nécessitant de faire les additions colonne par colonne (bit à bit).

• 1 + 1 = 10 (ce qui exprime bien 2 si on le lit en tant que binaire)
• 1 + 1 + 1 = 11 (ce qui exprime bien 3 si on le lit en tant que binaire)

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} = \overline{a} + \overline{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} = \overline{a} . \overline{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.\overline{b}+\overline{a}.b\)

Lois de De Morgan

\(\overline{a.b} = \overline{a} + \overline{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} = \overline{a} . \overline{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)