I. La logique booléenne¶

Cours¶

Introduction¶

L'informatique est basée sur l'utilisation de 1 et de 0 : ils représentent le vrai et le faux, True et False en Python, et correspondent au type booléen.

Pour combiner des expressions booléennes, on utilise des opérateurs booléens. Ils servent :
- en programmation,
- dans la conception de circuits électroniques,
- dans la résolution de problèmes de logique.

A. Le NON¶

Définitions

L'opérateur \(NON\) (le \(NOT\) en anglais) inverse la valeur d'une variable booléenne. Si l'expression booléenne \(A\) est fausse, alors \(NON(A)\) est vraie et réciproquement. On résume cela avec une table, dite table de vérité de l'opérateur \(not\) :

Notation standard

\(A\)	\(NON(A)\)
Faux	Vrai
Vrai	Faux

Notation en Python

`A`	`not(A)`
`False`	`True`
`True`	`False`

La table de vérité d'une expression booléenne indique la valeur de l'expression pour chaque valeur possible de ses variables.

En électronique, on représente cette opération sous la forme d'une porte logique dont le symbole est le suivant :

On symbolise la présence d'un courant par un 1, et son absence par un 0. La table de vérité peut donc aussi s'écrire sous la forme suivante :

\(A\) \(NON(A)\)

0 1

1 0

B. Le ET¶

Définition

L'opérateur \(ET\) (le \(AND\) en anglais) permet d'associer deux expressions booléennes \(A\) et \(B\) de la manière suivante : \(A\) \(ET\) \(B\) est vraie si A est vraie et B est vraie. Cela donne la table de vérité suivante :

Notation standard

\(A\)	\(B\)	\(A\) \(ET\) \(B\)
Faux	Faux	Faux
Vrai	Faux	Faux
Faux	Vrai	Faux
Vrai	Vrai	Vrai

Notation en Python

`A`	`B`	`A and B`
`False`	`False`	`False`
`True`	`False`	`False`
`False`	`True`	`False`
`True`	`True`	`True`

Porte logique à 2 entrées A et B :

C. Le OU¶

Définition

L'opérateur \(OU\) ( le \(OR\) en anglais) permet d'associer deux expressions booléennes de la manière suivante : \(A\) \(OU\) \(B\) est vrai si \(A\) est vraie, \(B\) est vraie, ou bien si les deux le sont. Cela donne la table de vérité suivante :

`A`	`B`	`A` OU `B`
`False`	`False`	`False`
`True`	`False`	`True`
`False`	`True`	`True`
`True`	`True`	`True`

Porte logique à 2 entrées A et B :

Conclusion¶

Les portes logiques sont les éléments de base des circuits électroniques. Leur combinaison permet de réaliser des circuits beaucoup plus complexes.

TD : Les expressions booléennes¶

Exercice 1 : Vrai ou Faux¶

Si a vaut True et b vaut False, not(a or b) s'évalue à True.
L'expression not(a or b) a la même valeur que l'expression (not a) or (not b).
Si a vaut True et b vaut True, not(a and b) s'évalue à True.
L'expression not(a and b) a la même valeur que l'expression not(a) or not(b).

Exercice 2 :¶

Sélectionner la(les) bonne(s) réponse(s) parmi les différentes propositions.

L'expression booléenne a or not(b) s'évalue à True. Quelles peuvent être les valeurs de a et de b ?
- a vaut True et b vaut True
- a vaut True et b vaut False
- a vaut False et b vaut True
- a vaut False et b vaut False
Parmi les expressions suivantes, laquelle s'évalue en True ?
- True and (False and True)
- True or (False and True)
- False and (False and True)
- False or (False and True)

Exercice 3¶

On considère l'expression a and b où a et b sont deux expressions booléennes. Si a vaut False, quelle sera la valeur de l'expression, en fonction de la valeur de b ? Que pouvez-vous en déduire ?
On considère l'expression a or b où a et b sont deux expressions booléennes. Si a vaut True, quelle sera la valeur de l'expression, en fonction de la valeur de b ? Que pouvez-vous en déduire ?

Conclusion (à retenir) :

Exercice 4¶

On rappelle qu'un nombre est pair si son reste dans la division euclidienne par 2 vaut 0, et qu'il est impair sinon. Pour écrire une fonction indiquant si un entier n est pair ou non, on peut avoir envie de l'exprimer en Python avec des conditions :

Code

def pair(n):
    if n%2 == 0:
        return True
    else:
        return False

Cette écriture est abusive, car l'expression n%2 == 0 renvoie déjà soit la valeur True, soit la valeur False. On préfère l'écrire simplement avec une expression booléenne :

Code

def pair(n):
    return n%2 == 0

Se baser sur l'exemple donné pour écrire une fonction centaine(n) qui renvoie True si n est supérieur à 100, et False sinon. La fonction n'utilisera pas de conditions, mais une expression booléenne.
Comment peut-on obtenir les nombres impairs à partir de la fonction pair(n) ? Même question pour obtenir les nombres inférieurs à 100.

Trouver l'expression booléenne pouvant remplacer le code suivant :

Code

if a==b:
    c = True
elif a > b+10:
    c = True
else:
    c = False

TD : Problème de logique¶

Au milieu du désert, vous cherchez une oasis. Vous arrivez à un carrefour où votre chemin se divise en 2 : un chemin va vers la gauche, un autre vers la droite. Deux sphinx sont posés à ce carrefour et savent quel est le chemin à prendre. Ils vont vous donner des indications, mais attention ! Soit ils disent tous les deux la vérité, soit ils mentent tous les deux.

Voici ce que vous disent les sphinx S1 et S2 :

S1 : "L'oasis se trouve sur la gauche."
S2 : "Non elle est à droite."
S1 : "Ou alors sur la droite."

Représenter ce qu'affirme S1 en fonction d'une variable booléenne notée G, valant True si le chemin menant à l'oasis est celui de gauche, False s'il est à droite.
Représenter ce qu'affirme S2 en fonction de la même variable G.
Remplir la table de vérité suivante :

G S1 S2

True

False
En déduire quel chemin est-ce qu'il faut prendre pour aller jusqu'à l'oasis.

TD : L'additionneur binaire¶

On utilise des portes logiques (représentation électronique des opérateurs booléens) pour construire des circuits en assemblant ces portes. On rappelle leur représentation classique :

Opérateur booléen	Porte logique
NON(`A`)
`A` ET `B`
`A` OU `B`

A. L'opérateur XOR¶

Le XOR est un opérateur renvoyant True si, et seulement si, une de ses deux entrées A et B valent True. Il est appelé OU EXCLUSIF, par opposition au OU du cours, qui est le OU INCLUSIF (il inclue le cas dans lequel les deux entrées sont à True). On raisonne ici au niveau des circuits, on remplace donc les True et False par, respectivement, 1 et 0.

Compléter la table de vérité du XOR donnée ci-dessous :

A B A XOR B

0 0

1 0

0 1

1 1

On peut le représenter électroniquement par la porte suivante :
Vérifier que le circuit ci-dessous fait bien le calcul du XOR à partir des opérateurs booléens de base, en attribuant toutes les valeurs possibles (entre 0 et 1) aux entrées A et B et en calculant la valeur de la sortie S. La valeur de S doit correspondre aux valeurs A XOR B obtenues dans la table de vérité de la question 1.
A partir de ce circuit, trouver l'expression booléenne constituée des opérateurs NON, ET et OU qui permet de calculer le XOR. Pour cela, il faut suivre les fils du circuit et faire l'opération correspondant à chaque porte sur les entrées exprimées en fonction de A et B.
Utiliser l'expression booléenne obtenue à la question 3 pour programmer une fonction xor prenant en paramètres deux booléens a et b et renvoyant un booléen, en utilisant les opérateurs booléens not, and et or.

B. L'additionneur 1 bit¶

Un additionneur 1 bit est un circuit permettant d'additionner deux bits entre eux. Il dispose de :
Trois entrées :
- a : le premier bit,
- b : le deuxième bit,
- re : la retenue entrante (peut exister dans le cas où l'on combine les additionneurs)

Deux sorties :
- s : la somme des deux bits,
- rs : la retenue sortante.

Aller voir le circuit électronique correspondant à l'URL suivante : https://www.cahier-nsi.fr/additionneur1bit/

Compléter les colonnes de s et de rs dans la table de vérité de l'additionneur en changeant les valeurs d'entrée du circuit :

a b re s rs (a XOR b) XOR re

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1
On donne l'expression booléenne de (a XOR b) XOR re
Compléter la table de vérité de cette expression. A quelle autre colonne correspond-elle ? Retrouver l'expression à partir du circuit électronique.
Se baser sur le circuit pour obtenir l'expression booléenne permettant de calculer rs.
Programmer une fonction add1bit, prenant en paramètres trois entiers a, b et la retenue re, et renvoyant en sortie s et la retenue rs, dont les expressions booléenne ont été trouvées aux questions 2 et 3. Utiliser la fonction xor définie Partie A, question 4.

N.B.: Pour qu'une fonction renvoie 2 valeurs en sortie, il faut les séparer par une ,, après le return.

`a`	`b`	`re`
`0`	`0`	`0`
`0`	`0`	`1`
`0`	`1`	`0`
`0`	`1`	`1`
`1`	`0`	`0`
`1`	`0`	`1`
`1`	`1`	`0`
`1`	`1`	`1`

`G`	`S1`	`S2`
`True`
`False`

`a`	`b`	`re`
`0`	`0`	`0`
`0`	`0`	`1`
`0`	`1`	`0`
`0`	`1`	`1`
`1`	`0`	`0`
`1`	`0`	`1`
`1`	`1`	`0`
`1`	`1`	`1`

`a`	`b`	`re`
`0`	`0`	`0`
`0`	`0`	`1`
`0`	`1`	`0`
`0`	`1`	`1`
`1`	`0`	`0`
`1`	`0`	`1`
`1`	`1`	`0`
`1`	`1`	`1`