eXoMophisme

Algèbre de Boole — Exercices

1. Repères historiques

En 1847, le britannique George Boole inventa un formalisme permettant d'écrire des raisonnements logiques : l'algèbre de Boole. La notion même d'informatique n'existait pas à l'époque, même si les calculs étaient déjà automatisés (penser à la Pascaline de 1642).

Bien plus tard, en 1938, l'américain Claude Shannon prouva que des circuits électriques peuvent résoudre tous les problèmes que l'algèbre de Boole peut elle-même résoudre.

L'algèbre de Boole définit des opérations dans un ensemble à deux éléments : 0 et 1, ou FAUX et VRAI, ou encore False et True en Python.
Les trois opérations fondamentales sont : la conjonction (ET), la disjonction (OU) et la négation (NON).

2.1 Conjonction (AND)

Notations : & · ET · and (Python) ·

a \wedge b

a \cdot b

Exercice 1 — Table de vérité de l'opérateur ET

Cliquez sur les cellules ? pour les faire basculer entre 0 et 1, puis validez.

a	b	$a \wedge b$
0	0	?
0	1	?
1	0	?
1	1	?

Exercice 2 — Évaluation d'expressions Python (AND)

Évaluer les expressions suivantes :

>>> (1 + 2 == 3) and (7 + 1 == 8)
>>> (1 + 2 == 3) and (1 + 1 == 3)

(1 + 2 == 3) and (7 + 1 == 8) → True (True AND True = True)
(1 + 2 == 3) and (1 + 1 == 3) → False (True AND False = False)

Exercice 3 — Court-circuit de AND

Évaluer les expressions suivantes :

>>> (7 / 0 == 1) and (4 / 2 == 2)
>>> (1 + 1 == 3) and (7 / 0 == 2)

(7 / 0 == 1) and (4 / 2 == 2) → ZeroDivisionError : la division par zéro est évaluée avant que AND puisse court-circuiter.
(1 + 1 == 3) and (7 / 0 == 2) → False : Python évalue d'abord 1+1==3 qui vaut False. Grâce au court-circuit de AND, la seconde expression (division par zéro) n'est jamais évaluée.

2.2 Disjonction (OR)

Notations : | · OU · or (Python) ·

a \lor b

a + b

Exercice 4 — Table de vérité de l'opérateur OU

a	b	$a \lor b$
0	0	?
0	1	?
1	0	?
1	1	?

Exercice 5 — Évaluation d'expressions Python (OR)

>>> n = 20
>>> (n % 10 == 0) or (n % 7 == 0)
>>> (n % 4 == 0) or (n % 5 == 0)
>>> (n % 7 == 0) or (n % 3 == 0)

(n % 10 == 0) or (n % 7 == 0) → True (20%10=0 ✓)
(n % 4 == 0) or (n % 5 == 0) → True (20%4=0 ✓ ET 20%5=0 ✓)
(n % 7 == 0) or (n % 3 == 0) → False (20%7=6 ✗ ET 20%3=2 ✗)

Exercice 6 — Court-circuit de OR

>>> n = 20
>>> (n % 5 == 0) or (n % 0 == 0)

(n % 5 == 0) or (n % 0 == 0) → True
La première expression n % 5 == 0 vaut True. Grâce au court-circuit de OR, Python n'évalue pas la seconde expression (qui provoquerait une ZeroDivisionError).

2.3 Négation (NOT)

Notations : ~ · NON · not (Python) ·

\lnot a

\overline{a}

Exercice 7 — Table de vérité de l'opérateur NON

a	$\lnot a$
0	?
1	?

Exercice 8 — Évaluation d'une expression Python (NOT)

>>> n = 20
>>> not(n % 10 == 0)

n % 10 == 0 vaut True (20 est divisible par 10).
not(True) → False

2.4 Quiz

Q1 — Parmi les quatre expressions suivantes, laquelle s'évalue en True ?

A — False and (True and False) B — False or (True and False) C — True and (True and False) D — True or (True and False)

Q2 — Si a vaut False et b vaut True, que vaut not(a and b) ?

A — 0 B — False C — True D — None

Q3 — On exécute le code suivant. Quelle est la valeur de d ?

a = 2
b = 3
c = a ** b
d = c % b

A — 1 B — 2 C — 3 D — 4

Q4 — x = 3, y = 4. Quelle expression s'évalue en True ?

A — x == 3 or y == 5 B — x == 3 and y == 5 C — x != 3 or y == 5 D — y < 4

Q5 — À quelle affectation est équivalent ce code (a, b entiers, c booléen) ?

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

A — c = (a == b) or (a > b + 10) B — c = (a == b) and (a > b + 10) C — c = not(a == b) D — c = not(a > b + 10)

Q6 — Sachant que not(a or b) vaut True, quelles peuvent être les valeurs de a et b ?

A — True et True B — False et True C — True et False D — False et False

Q7 — Voici la table de vérité d'une formule form. Quelle est cette formule ?

a	b	form
True	True	False
False	True	False
True	False	True
False	False	False

A — a and b B — a or b C — a and not(b) D — not(a) or b

Q8 — Pour quelles valeurs de a, b et c, l'expression (a or b) and (not c) vaut-elle True ?

A — a=True, b=False, c=True B — a=True, b=False, c=False C — a=False, b=False, c=True D — a=False, b=True, c=True

Q9 — a et b sont deux booléens. L'expression not(a and b) or a est équivalente à :

A — False B — True C — not(b) D — not(a) or not(b)

Q10 — Si A et B sont des booléens, quelle expression est équivalente à (not A) or B ?

A — (A and B) or (not A and B) B — (A and B) or (not A and B) or (not A and not B) C — (not A and B) or (not A and not B) D — (A and B) or (not A and not B)

3. Fonctions composées

3.1 Disjonction exclusive (XOR)

XOR = OU EXCLUSIF : vrai seulement si les deux opérandes sont différents.

x \oplus y = (x \wedge \lnot y) \lor (\lnot x \wedge y)

Exercice 9 — Table de vérité de XOR

a	b	$a \wedge \lnot b$	$\lnot a \wedge b$	$a \oplus b$
0	0	?	?	?
0	1	?	?	?
1	0	?	?	?
1	1	?	?	?

3.2 NON-ET (NAND)

NAND = NON ET :

x \uparrow y = \lnot(x \wedge y)

Exercice 10 — Table de vérité de NAND

a	b	$a \wedge b$	$\lnot(a \wedge b)$
0	0	?	?
0	1	?	?
1	0	?	?
1	1	?	?

3.3 NON-OU (NOR)

NOR = NON OU :

x \downarrow y = \lnot(x \lor y)

Exercice 11 — Table de vérité de NOR

a	b	$a \lor b$	$\lnot(a \lor b)$
0	0	?	?
0	1	?	?
1	0	?	?
1	1	?	?

4. Opérations sur les nombres binaires

Exercice 12 — Opérations bit à bit

Effectuer les opérations suivantes en binaire :

  1011011
& 1101010
---------
  ?

  1011011
& 1101010
---------
  1001010

  1011011
| 1010101
---------
  ?

  1011011
| 1010101
---------
  1011111

  1011011
^ 1010101
---------
  ?

  1011011
^ 1010101
---------
  0001110

Exercice 13 — Calculs bit à bit en Python

Expliquer les résultats obtenus :

>>> 12 & 7   # résultat : 4
>>> 12 | 7   # résultat : 15
>>> 12 ^ 5   # résultat : 9

12 & 7 = 4
12 = 0001100, 7 = 0000111
AND bit à bit : 0000100 = 4

12 | 7 = 15
12 = 0001100, 7 = 0000111
OR bit à bit : 0001111 = 15

12 ^ 5 = 9
12 = 0001100, 5 = 0000101
XOR bit à bit : 0001001 = 9

5. Chiffrement XOR

Le chiffre XOR est une méthode de chiffrement symétrique très efficace à implémenter. Associé au principe du masque jetable, c'est une solution cryptographiquement robuste.

Principe du chiffrement

Pour chiffrer "BONJOUR" avec le masque "LPOSADA" :

Le masque doit être au moins aussi long que le message.
Pour chaque position, on récupère les codes ASCII de la lettre du message et du masque.
On soustrait 64 à chaque code (pour rester dans les lettres majuscules : A=1, B=2, …)
On effectue le XOR des deux valeurs.
On additionne 64 et on convertit en caractère ASCII.

Exemple : chiffrement de 'B' (pos. 0) avec la clé 'L'

ord('B') = 66  →  66 - 64 = 2
ord('L') = 76  →  76 - 64 = 12
2 ^ 12 = 14
14 + 64 = 78  →  chr(78) = 'N'

Message	Masque	msg−64	clé−64	XOR	+64	Résultat
B (66)	L (76)	2	12	14	78	N
O (79)	P (80)	15	16	31	95	_ (souligné)
N (78)	O (79)	14	15	1	65	A
J (74)	S (83)	10	19	25	89	Y
O (79)	A (65)	15	1	14	78	N
U (85)	D (68)	21	4	17	81	Q
R (82)	A (65)	18	1	19	83	S

BONJOUR chiffré avec LPOSADA → N_AYNAQS

Propriété clé : appliquer deux fois le XOR avec le même masque redonne le message original (le déchiffrement utilise la même opération).

TP — Fonction de chiffrement XOR

Écrire une fonction chiffrement(message, masque) qui chiffre le message à l'aide du masque (en appliquant la transformation décrite ci-dessus).

Vérifier que chiffrement(chiffrement("BONJOUR", "LPOSADA"), "LPOSADA") redonne "BONJOUR".

def chiffrement(message, masque):
    resultat = ""
    for i in range(len(message)):
        code_msg = ord(message[i]) - 64
        code_cle = ord(masque[i % len(masque)]) - 64
        resultat += chr((code_msg ^ code_cle) + 64)
    return resultat

# Test
code = chiffrement("BONJOUR", "LPOSADA")
print(code)                          # N_AYNAQS
print(chiffrement(code, "LPOSADA")) # BONJOUR

6. Exercices avancés — Tables de vérité composées

Exercice A — $a \wedge (\lnot a \lor b)$

Établir la table de vérité de l'expression a ET (NON a OU b).

a	b	$\lnot a$	$\lnot a \lor b$	$a \wedge (\lnot a \lor b)$
0	0	?	?	?
0	1	?	?	?
1	0	?	?	?
1	1	?	?	?

Exercice B — $\lnot a \lor \lnot(a \wedge b)$

Établir la table de vérité de l'expression NON a OU NON(a ET b).

a	b	$\lnot a$	$\lnot(a \wedge b)$	$\lnot a \lor \lnot(a \wedge b)$
0	0	?	?	?
0	1	?	?	?
1	0	?	?	?
1	1	?	?	?

Exercice C — $\lnot(a \lor \lnot c) \lor \lnot(b \wedge c)$

Établir la table de vérité de l'expression NON(a OU NON c) OU NON(b ET c).

a	b	c	$\lnot(a \lor \lnot c) \lor \lnot(b \wedge c)$
0	0	0	?
0	0	1	?
0	1	0	?
0	1	1	?
1	0	0	?
1	0	1	?
1	1	0	?
1	1	1	?

Exercice D — $\lnot(a \wedge b) \lor c$

Établir la table de vérité de l'expression NON(a ET b) OU c.

a	b	c	$\lnot(a \wedge b) \lor c$
0	0	0	?
0	0	1	?
0	1	0	?
0	1	1	?
1	0	0	?
1	0	1	?
1	1	0	?
1	1	1	?