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.
La NEGATION : Le NON logique
1.2 Table de vérité du NON
On considère une expression booléenne notée a et une valeur booléenne de sortie notée s.
Voici la table de vérité du NON :
En version FAUX / VRAI
Expression a
Sortie s
FAUX
VRAI
VRAI
FAUX
En version 0 / 1
Expression a
Sortie s
0
1
1
0
1.3 Le NON logique en Python
Il suffit d'utiliser le mot-clé not.
>>> not True
False
1.4 Equation mathématique du NON
Mathématiquement, cela revient à écrire : \(s = \bar a\).
A quoi correspond la barre supérieure ? Elle indique qu'il faut inverser ( ou complémenter ) a.
On dit d'ailleurs que \(\bar a\) est le complément de \(a\) car la propriété suivante est toujours vérifiée, quelque soit \(a\) :
\(\bar a + a = 1\).
Expression a
Sortie s
\(\bar a\)
0
1
0 donne 1
1
0
1 donne 0
Suivant la façon dont une documentation est réalisée, il est parfois difficile de placer le trait supérieur. On trouve donc d'autres manières d'indiquer la complémentarité.
La complémentarité de a peut donc se noter
\(\bar a\)
\(a/\)
\(\neg a\)
On notera aussi que NON(NON(a)) redonne simplement a :
\(\bar {\bar a} = a\)
\(\neg {\neg a} = a\)
Le caractère ¬ possède une valeur UNICODE 172 (en base 10). On peut donc l'afficher en HTML en utilisant ¬ mais il possède également un code raccourci : ¬. Vous voyez le rapprochement ?
01° Utiliser la console Python pour compléter la table de vérité du ET (vous pouvez cliquer sur les cases pour modifier la réponse affichée) :
>>> True and True
True
Expression a
Expression b
a ET b
FAUX
FAUX
?
FAUX
VRAI
?
VRAI
FAUX
?
VRAI
VRAI
?
En Javascript, C, C++, la codification est différente :
a && b
Question
Quel est le seul cas où le ET est VRAI ?
...CORRECTION...
Expression a
Expression b
a ET b
FAUX
FAUX
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
Le ET n'est VRAI que si toutes les entrées sont VRAIES.
02° Utiliser la console Python pour trouver la table de vérité du ET à 3 entrées (vous pouvez cliquer sur les cases pour modifier la réponse affichée) :
Expression a
Expression b
Expression c
a ET b ET c
FAUX
FAUX
FAUX
?
FAUX
FAUX
VRAI
?
FAUX
VRAI
FAUX
?
FAUX
VRAI
VRAI
?
VRAI
FAUX
FAUX
?
VRAI
FAUX
VRAI
?
VRAI
VRAI
FAUX
?
VRAI
VRAI
VRAI
?
Question
Quel est le seul cas où le ET est VRAI ?
...CORRECTION...
Expression a
Expression b
Expression c
a ET b ET c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
FAUX
FAUX
VRAI
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
VRAI
Le ET n'est VRAI que si toutes les entrées sont VRAIES.
03° Imaginons qu'on veuille vérifier qu'une note soit correctement rentrée dans un système informatique. On a besoin de vérifier trois propriétés devant être VRAIES EN MEME TEMPS :
La note doit bien être un entier
La note doit être supérieure ou égale à 0
La note doit être inférieure ou égale à 20
Pour réaliser cela avec Python, on a besoin d'utiliser le mot-clé and.
Placer ce programme en mémoire, tester les appels proposés et expliquer quelle proposition A , B ou C provoque une réponse False lorsqu'un False apparaît :
Le ET n'est VRAI que si toutes les expressions d'entrée sont VRAIES.
Avec 2 expressions :
Expression a
Expression b
a ET b
FAUX
FAUX
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
Avec 3 expressions :
Expression a
Expression b
Expression c
a ET b ET c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
FAUX
FAUX
VRAI
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
VRAI
2.2 Le ET logique en Python
Il suffit d'utiliser le mot-clé and.
>>> True and False
False>>> 5 and []
[]
Pour comprendre la dernière évaluation (un peu étrange), il faut se souvenir qu'en Python tout ce qui vaut 0 ou vide est associé à False. Python répond donc bien "Faux" en fournissant la valeur qui a servi à définir cette valeur "Faux". Si vous voulez une réponse clairement booléenne en Python, vous pouvez lui demander poliment :
>>> bool(5 and [])
False
2.3 Evaluation paresseuse du ET
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 :
Expression a
Expression b
Expression c
a ET b ET c
FAUX
Peu importe
Peu importe
FAUX
VRAI
FAUX
Peu importe
FAUX
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
VRAI
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.
On commence par vérifier que la note est bien un entier AVANT de tenter de la comparer à 0 puis à 20.
04° On veut afficher les valeurs contenues dans un tableau tant que la valeur actuelle est positive et donc s'arrêter dès qu'on tombe sur une valeur négative.
Expliquer pourquoi le premier programme fonctionne mais pas le second.
Dans le programme A, on teste si l'indice existe AVANT de tenter de lire la case correspondante.
Dans le programme B, on lit la case et ENSUITE on verifie si elle existait...
2.4 Equation mathématique du ET
En algèbre booléenne, a ET b revient à évaluer l'expression a . b en tant qu'expression booléenne : on lui attribue la valeur 0/FAUX ou 1/VRAI uniquement.
Expression a
Expression b
a . b
0
0
0.0 = 0 donc FAUX
0
1
0.1 = 0 donc FAUX
1
0
1.0 = 0 donc FAUX
1
1
1.1 = 1 donc VRAI
Opérateur . de l'algèbre booléenne
L'opérateur . n'est pas la multiplication traditionnelle : elle ne s'applique qu'à deux termes booléens. Il faut donc d'abord évaluer a et b en tant que booléen AVANT de réaliser cette multiplication.
Quelles que soient les valeurs qui peuvent prendre effectivement a et b :
La plus petite valeur est donc 0.0 qui donne 0.
La plus grande valeur est donc 1.1 qui donne 1.
En Python ?
Si on peut effectivement multiplier les deux termes dans un langage de programmation, on peut retrouver la bonne interprétation booléenne en considérant l'interprétation habituelle : FAUX c'est 0 ou vide, et VRAI c'est le reste des valeurs possibles.
>>> bool("" * 9)
False>>> bool("a" * 9)
True
05° Comment peut-on représenter a ET b ET c avec une équation ?
07° Utiliser la console Python pour trouver la table de vérité du OU (vous pouvez cliquer sur les cases pour modifier la réponse affichée).
En Python :
>>> True or False
True
Expression a
Expression b
a OU b
FAUX
FAUX
?
FAUX
VRAI
?
VRAI
FAUX
?
VRAI
VRAI
?
Remarque : en Javascript, C, C++, le ou s'écrit ainsi :
a || b
Question
Quel est le seul cas où le OU est FAUX ?
...CORRECTION...
Expression a
Expression b
a OU b
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
Le OU n'est FAUX que lorsque toutes les entrées sont fausses.
Dès que l'une des entrées est VRAIE, le OU répond VRAI.
08° Utiliser la console Python pour trouver la table de vérité du OU avec 3 expressions (vous pouvez cliquer sur les cases pour modifier la réponse affichée) :
Expression a
Expression b
Expression c
a OU b OU c
FAUX
FAUX
FAUX
?
FAUX
FAUX
VRAI
?
FAUX
VRAI
FAUX
?
FAUX
VRAI
VRAI
?
VRAI
FAUX
FAUX
?
VRAI
FAUX
VRAI
?
VRAI
VRAI
FAUX
?
VRAI
VRAI
VRAI
?
...CORRECTION...
Expression a
Expression b
Expression c
a OU b OU c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
VRAI
3.1 Table de vérité du OU
Le OU n'est FAUX que si toutes les expressions d'entrée sont FAUSSES.
Avec 2 expressions :
Expression a
Expression b
a OU b
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
Avec 3 expressions :
Expression a
Expression b
Expression c
a OU b OU c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
VRAI
VRAI
Remarquez bien que ce OU ne correspond pas au OU usuel du Français : la plupart du temps, on veut dire que l'UNE des choses est possible à la fois. Ici, toutes peuvent être vraies en même temps également.
3.2 Le OU logique en Python
Il suffit d'utiliser le mot-clé or.
>>> True or False
True>>> 5 or []
5
Pour comprendre la dernière évaluation (un peu étrange), il faut se souvenir qu'en Python tout ce qui n'est ni 0, ni vide est associé à True. Python répond donc bien "Vrai" en fournissant la valeur qui a servi à définir cette valeur "Vrai". Si vous voulez une réponse clairement booléenne en Python, vous pouvez lui demander poliment :
>>> bool(5 or [])
True
3.3 Evaluation paresseuse du OU
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 :
Expression a
Expression b
Expression c
a OU b OU c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
Peu importe
VRAI
VRAI
Peu importe
Peu importe
VRAI
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.
On commence par vérifier que la note est bien un entier AVANT de tenter de la comparer à 0 puis à 20.
3.4 Equation mathématique du OU
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 :
Expression a
Expression b
a + b
0
0
0+0=0 donc FAUX
0
1
0+1=1 donc VRAI
1
0
1+0=1 donc VRAI
1
1
1+1=2 donc VRAI
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 :
Valeur de a
Valeur de b
a + b - a.b
0
0
0+0 - 0.0=0 donc FAUX
0
1
0+1 - 0.1=1 donc VRAI
1
0
1+0 - 1.0=1 donc VRAI
1
1
1+1 - 1.1=1 donc VRAI
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
Expression a
Expression b
a + b
0
0
0+0=0 donc FAUX
0
1
0+1=1 donc VRAI
1
0
1+0=1 donc VRAI
1
1
1+1=1 donc VRAI
3.5 Interprétation du symbole +
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 10012 + 12 en binaire, le + symbolise l'addition (binaire) bit à bit.
Si nous notions 10012 +BIN 12, cela serait plus clair. Ca donne 10012 +BIN 00012, soit 10102.
Dans 1 + 1 dans l'algèbre de Boole, le + symbolise l'addition dans l'ensemble de Boole {0, 1}.
Si nous notions 10012 +BIN 12, cela serait plus clair. Ca donne 10012 +BIN 00012, soit 10102.
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)
09° On veut évaluer a or b.
L'expression a à 80% d'être True et b à 10% d'être True. Vaut-il mieux utiliser a or b ou b or a ?
10° Comment peut-on représenter a OU b OU c avec une équation logique ?
...CORRECTION...
Si on prend VRAI pour tout ce qui n'est pas 0 :
s = a + b + c
Si on veut s'éviter l'interprétation et tomber directement sur 0 ou 1, c'est plus long :
Le XOR n'est VRAI que si UNE UNIQUE EXPRESSION d'entrée est VRAIE.
Le X du XOR vient du X de eXclusif.
Ce OU correspond au OU usuel du Français : fromage ou dessert ?
Avec 2 expressions :
Expression a
Expression b
a XOR b
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
FAUX
Avec 3 expressions :
Expression a
Expression b
Expression c
a XOR b XOR c
FAUX
FAUX
FAUX
FAUX
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
FAUX
VRAI
VRAI
FAUX
VRAI
FAUX
VRAI
VRAI
FAUX
FAUX
VRAI
VRAI
VRAI
FAUX
11° Créer la fonction xor() qui possède deux paramètres d'entrée :
a : un booléen.
b : un booléen.
La fonction devra renvoyer un booléen correspondant au OU EXCLUSIF entre a et b.
...CORRECTION...
Voir la partie XOR en Python ci-dessous.
4.2 Le XOR logique en Python
Le XOR n'existe pas naturellement en Python. Mais si vous avez besoin d'une expression booléenne qui l'utilise, vous pouvez toujours le créer via une fonction comme celle-ci :
1
2
defxor(a,b):return(aorb)andnot(aandb)
Ou encore :
1
2
defxor(a,b):return(aandnotb)or(bandnota)
Notez que les parenthèses sont indispensables à cause des priorités :
D'abord not
Ensuite and ("multiplication")
Puis or ("addition")
4.3 Equation mathématique du XOR
Le XOR est assez facile à décrire en réalité : il suffit de fournir les deux cas possibles :
\(a.\overline{b}+\overline{a}.b\)
On utilise un nouveau symbole signifiant XOR comme alias de cette formule :
12° Utiliser la console Python pour trouver la table de vérité du NON-ET (vous pouvez cliquer sur les cases pour modifier la réponse affichée):
Expression a
Expression b
a ET b
NON(a ET b)qu'on peut écrirea NAND b
FAUX
FAUX
?
?
FAUX
VRAI
?
?
VRAI
FAUX
?
?
VRAI
VRAI
VRAI
FAUX
...CORRECTION...
>>> not(False and False)
True>>> not(False and True)
True>>> not(True and False)
True>>> not(True and True)
False
5.1 Table de vérité du NAND
Le AND n'est VRAI que si toutes les expressions d'entrée sont VRAIES.
Le NAND n'est FAUX que si toutes les expressions d'entrée sont VRAIES.
Avec 2 expressions :
Expression a
Expression b
a NAND b
FAUX
FAUX
VRAI
FAUX
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
FAUX
5.2 Le NAND logique en Python
Le NAND n'existe pas naturellement en Python. Mais si vous avez besoin d'une expression booléenne qui l'utilise, vous pouvez toujours le créer via une fonction comme celle-ci :
1
2
defnand(a,b):returnnot(aandb)
Notez que les parenthèses sont indispensables à cause des priorités :
D'abord not
Ensuite and ("multiplication")
Puis or ("addition")
5.3 Equation mathématique du NON-ET
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}\)
Valeur de a
Valeur de b
\(\overline{a.b}\)
FAUX
FAUX
VRAI
FAUX
VRAI
VRAI
VRAI
FAUX
VRAI
VRAI
VRAI
FAUX
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(aandb)=notaornotb
Puisque que not est prioritaire sur or, les parenthèses ne sont pas obligatoires. On peut bien entendu les rajouter si on veut :
not(aandb)= (nota) or (notb)
13° Pour qu'une note soit correcte, elle doit être supérieure à 0 ET inférieure à 20.
1
2
defest_valide(note):returnnote>=0andnote<=20
On peut en déduire qu'elle est incorrecte si cette expression booléenne renvoie l'inverse.
Le OR n'est FAUX que si toutes les expressions d'entrée sont FAUSSES.
Le NOR n'est VRAI que si toutes les entrées sont FAUSSES.
Avec 2 expressions :
Expression a
Expression b
a NOR b
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
FAUX
FAUX
VRAI
VRAI
FAUX
6.2 Le NOR logique en Python
Le NOR n'existe pas naturellement en Python. Mais si vous avez besoin d'une expression booléenne qui l'utilise, vous pouvez toujours le créer via une fonction comme celle-ci :
1
2
defnor(a,b):returnnot(aorb)
Notez que les parenthèses sont indispensables à cause des priorités :
D'abord not
Ensuite and ("multiplication")
Puis or ("addition")
6.3 Equation mathématique du NON-OU
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}\)
Valeur de a
Valeur de b
\(\overline{a+b}\)
FAUX
FAUX
VRAI
FAUX
VRAI
FAUX
VRAI
FAUX
FAUX
VRAI
VRAI
FAUX
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(aorb)=notaandnotb
Puisque que not est prioritaire sur and, les parenthèses ne sont pas obligatoires. On peut bien entendu les rajouter si on veut :
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 :
1 + 1 = 1
1 + 1 + 1 = 1
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(aandb)= (nota) or (notb)
not(aandb)=notaornotb
Version symétrique avec le OR :
\(\overline{a+b} = \overline{a} . \overline{b}\)
not(aorb)= (nota) and (notb)
not(aorb)=notaandnotb
7.3 Système complet d'opérateurs
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)
7.4 Evaluation paresseuse et priorité
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)
14° Un élève écrit ceci en python :
not a or not b and c
A quoi correspond en réalité cette opération ?
(not a) or (not (b and c))
not (a or not (b and c))
not (a or not b) and c
(not a) or ((not b) and c)
...CORRECTION...
not a or not b and c
On commence par mettre des parenthèses autour des not, qui sont prioritaires.
(not a) or (not b) and c
Ensuite, on sait que le AND est prioritaire sur le OR.
<(not a) or (not b) and c
La réponse de la sortie finale correspond bien à celle d'un OR.
(not a) or ((not b) and c)
C'est donc la réponse D.
15° Compléter progressivement (en cliquant) les colonnes de la table de vérité suivante. Donner alors la fonction logique équivalente à la formule de la dernière colonne.
Pour la dernière colonne, souvenez-vous qu'un OR n'est FAUX que si ces deux entrées sont FAUSSES.
a
b
NOT a
NOT b
(NOT a) OR (NOT b)
0
0
?
?
?
0
1
?
?
?
1
0
?
?
?
1
1
?
?
?
...CORRECTION...
a
b
NOT a
NOT b
(NOT a) OR (NOT b)
0
0
1
1
1
0
1
1
0
1
1
0
0
1
1
1
1
0
0
0
La réponse de la sortie finale correspond à celle de a NAND b.
16° Compléter progressivement (en cliquant) les colonnes de la table de vérité suivante. Donner alors la fonction logique équivalente à la formule de la dernière colonne.
Pour la dernière colonne, souvenez-vous qu'un NAND n'est FAUX que si ces deux entrées sont VRAIES.
a
b
NOT a
NOT b
(NOT a) NAND (NOT b)
0
0
?
?
?
0
1
?
?
?
1
0
?
?
?
1
1
?
?
?
...CORRECTION...
a
b
NOT a
NOT b
(NOT a) NAND (NOT b)
0
0
1
1
0
0
1
1
0
1
1
0
0
1
1
1
1
0
0
1
La réponse de la sortie finale correspond à celle de a OR b.
17° Compléter progressivement (en cliquant) les colonnes de la table de vérité suivante. Donner alors la fonction logique équivalente à la formule de la dernière colonne.
Il faut être rigoureux et trouver simplement le seul cas à un NAND est FAUX : lorsque ses deux entrées sont VRAIES.
a
b
a NAND b
a NAND (a NAND b) [1]
b NAND (a NAND b) [2]
[1] NAND [2]
0
0
?
?
?
?
0
1
?
?
?
?
1
0
?
?
?
?
1
1
?
?
?
?
...CORRECTION...
Recherche de la première colonne inconnue :
a
b
a NAND b
a NAND (a NAND b) [1]
b NAND (a NAND b) [2]
[1] NAND [2]
0
0
1
0
1
1
1
0
1
1
1
0
On cherche alors les valeurs de la colonne nommée [1].
a
b
a NAND b
a NAND (a NAND b) [1]
b NAND (a NAND b) [2]
[1] NAND [2]
0
0
1
1
0
1
1
1
1
0
1
0
1
1
0
1
Idem pour la colonne [2].
a
b
a NAND b
a NAND (a NAND b) [1]
b NAND (a NAND b) [2]
[1] NAND [2]
0
0
1
1
1
0
1
1
1
0
1
0
1
0
1
1
1
0
1
1
Reste la colonne finale :
a
b
a NAND b
a NAND (a NAND b) [1]
b NAND (a NAND b) [2]
[1] NAND [2]
0
0
1
1
1
0
0
1
1
1
0
1
1
0
1
0
1
1
1
1
0
1
1
0
La réponse de la sortie finale correspond à celle de a XOR b.
18° Utiliser les lois de De Morgan pour montrer que
a NAND b = (NOT a) OR (NOT b).
...CORRECTION...
On transforme d'abord le NAND en AND :
a NAND b = NOT ( a AND b )
Il suffit d'utiliser les lois de De Morgan : on remplace le AND par un OR et les entrées du AND par leurs compléments.
a NAND b = NOT ( a AND b ) = NOT a OR NOT b
On retrouve alors la formule voulue (not a) OR (not b).
19° Utiliser les lois de De Morgan pour montrer que
(NOT a) NAND (NOT b) = a OR b
...CORRECTION...
On transforme d'abord le NAND en AND :
(NOT a) NAND (NOT b) = NOT ( (NOT a) AND (NOT b) )
On transorme alors la formule de droite avec les lois de De Morgan : on transforme le AND en OR et on complémente les entrées du AND.
(NOT a) NAND (NOT b) = NOT ( (NOT a) AND (NOT b) ) = (NOT(NOT a)) OR (NOT(NOT b))
En supprimant les deux compléments successifs, on retrouve bien a OR b.
20° (Hors programme) Utiliser l'algèbre de Boole et les lois de De Morgan pour montrer que
[a NAND (a NAND b)] NAND [b NAND (a NAND b)] = a XOR b
On rappelle que a XOR b = (a AND NOT b) OR (NOT a AND b)
...CORRECTION...
On commence par transformer la formule [a NAND (a NAND b)] NAND [b NAND (a NAND b)] dans l'algèbre de Boole.