Un peu d'histoire

Algèbre booléenne

George Boole (1847)

En 1847, le britannique George Boole inventa un formalisme permettant d'écrire des raisonnements logiques : l'algèbre de Boole.
Cette algèbre ne contient que deux valeurs et 3 opérations de base.

Claude Shannon (1938)

En 1938, l'américain Claude Shannon prouva dans sa thèse que des circuits électriques peuvent résoudre tous les problèmes que l'algèbre de Boole peut elle-même résoudre.
La route était ouverte à l'apparition des premiers ordinateurs électroniques.

Vrai ou Faux ?

"1 + 1 = 2"

Vrai ou Faux ?

"1 + 1 = 2" ET "2 + 2 = 4"

Vrai ou Faux ?

"1 + 1 = 2" ET "1 + 3 = 5"

Vrai ou Faux ?

"1 + 1 = 3" OU "Sydney est en Australie"

Les booléens

Les booléens ne possèdent que deux valeurs, codés sur un seul bit :

FAUX : noté 0, False, false …
VRAI : noté 1, True, true …

Introduction à l'algèbre de Boole

L'algèbre de Boole repose sur 3 opérateurs fondamentaux.

l'opérateur NON
l'opérateur ET
l'opérateur OU

Puisqu'il n'y a que 2 valeurs possibles, on peut dresser la liste de tous les cas dans un tableau appelé table de vérité.

NON (NOT)

Notations :

NON a
$\lnot a$
not a (Python)
$!a$ (C, Java…)
$\overline{a}$ (électronique)

NON (NOT)

Table de vérité

a	$\lnot a$
0
1

ET (AND)

Notations :

a ET b
$a \wedge b$
a and b (Python)
$a ~.~ b$ (mathématiques)
a & b (bit à bit)

Exercice 1 — Table de vérité de ET

Compléter la table de vérité de

a \wedge b

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

Correction — Table de ET

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

Le ET n'est vrai que si les deux opérandes sont vrais.

Exercice 2 — Python et AND

Évaluer chaque expression Python :

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

Puis expliquer le résultat ci-dessous :

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

Correction — Python et AND

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

>>> (7 / 0 == 1) and (4 / 2 == 2)  # ZeroDivisionError !
>>> (1 + 1 == 3) and (7 / 0 == 2)  # False → False (court-circuit)

Court-circuit de AND : si la première expression vaut False, Python n'évalue pas la seconde.

OU (OR)

Notations :

a OU b
$a \lor b$
a or b (Python)
$a + b$ (mathématiques)
$a~ | ~b$ (bit à bit)

Exercice 3 — Table de vérité de OU

Compléter la table de vérité de

a \lor b

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

Exercice 4 — Python et OR

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

Expliquer le résultat :

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

Correction — Python et OR

>>> (n % 10 == 0) or (n % 7 == 0)  # True  or False → True
>>> (n % 4 == 0) or (n % 5 == 0)  # True  or True  → True
>>> (n % 7 == 0) or (n % 3 == 0)  # False or False → False

>>> (n % 5 == 0) or (n % 0 == 0)  # True → True (court-circuit)

Court-circuit de OR : si la première expression vaut True, Python n'évalue pas la seconde (la division par zéro est évitée).

Exercice 5 — Python et NOT

Compléter la table de vérité de

\lnot a

, puis évaluer l'expression :

a	$\lnot a$
0
1

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

Correction — NOT

a	$\lnot a$
0	1
1	0

>>> not(n % 10 == 0)
# not(20 % 10 == 0) = not(True) = False

XOR — OU exclusif

Vrai uniquement si les deux opérandes sont différents.

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

Notations :

a XOR b
$a \oplus b$
a ^ b (Python, bit à bit)

Exercice 6 — Table de XOR

Compléter toutes les colonnes :

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

Correction — XOR

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

NAND — NON ET

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

Notations :

a NAND b
$\lnot(a \wedge b)$
not(a and b) (Python)

Exercice 7 — Table de NAND

Retrouver la table en complétant les colonnes intermédiaires :

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

NOR — NON OU

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

Notations :

a NOR b
$\lnot(a \lor b)$
not(a or b) (Python)

Exercice 8 — Table de NOR

Retrouver la table en complétant les colonnes intermédiaires :

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

Exercice 9 — Opérations bit à bit

Effectuer les opérations suivantes en binaire :

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

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

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

Vérifier en Python :

>>> 91 & 106
>>> 91 | 85
>>> 91 ^ 85

Correction — Opérations bit à bit

  1011011  (91)
& 1101010  (106)
---------
  1001010  (74)

  1011011  (91)
| 1010101  (85)
---------
  1011111  (95)

  1011011  (91)
^ 1010101  (85)
---------
  0001110  (14)

>>> 12 & 7   # → 4
>>> 12 | 7   # → 15
>>> 12 ^ 5   # → 9

Le cours en vidéo
Le cours de NovelClass

Chiffrement XOR

Le chiffre XOR est une méthode de chiffrement symétrique :
on chiffre et déchiffre avec la même clé, en appliquant XOR deux fois.

Principe : pour chiffrer un message lettre par lettre avec un masque, pour chaque position i :

Récupérer ord(message[i]) et ord(masque[i])
Soustraire 64 à chaque valeur (A→1, B→2 … Z→26)
Appliquer XOR entre les deux valeurs
Ajouter 64 et convertir avec chr()

Exercice 10 — Chiffrement de 'B' avec la clé 'L'

ord('B') = 66   →   66 - 64 = ?
ord('L') = 76   →   76 - 64 = ?
? ^ ?  =  ?
? + 64 =  ?   →   chr(?) = ?

TP : écrire une fonction chiffrement(message, masque).
Vérifier que chiffrement(chiffrement("BONJOUR","LPOSADA"),"LPOSADA") == "BONJOUR".

Correction — Chiffrement XOR

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

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

Propriété clé : chiffrement(chiffrement(m, k), k) == m

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)

Quiz — Q1 — Correction

Réponse : D

True or (True and False)
= True or False (court-circuit : True or … → True)
= True

Quiz — Q2

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

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

Quiz — Q2 — Correction

Réponse : C

a and b = False and True = False
not(False) = True

Quiz — 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

Quiz — Q6 — Correction

Réponse : D

not(a or b) = True
⟹ a or b = False
⟹ a = False ET b = False

(si l'un des deux était True, le OR serait True)

Quiz — Q9

Soient a et b 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)

Quiz — Q9 — Correction

Réponse : B

Par De Morgan : not(a and b) = not(a) or not(b)
Donc : [not(a) or not(b)] or a
= not(a) or a or not(b)
= True or not(b) (tiers-exclu)
= True

Théorèmes de De Morgan

Démontrer les théorèmes de De Morgan par table de vérité :

Premier théorème :

\lnot(a \lor b) = \lnot a \wedge \lnot b

Deuxième théorème :

\lnot(a \wedge b) = \lnot a \lor \lnot b

Exercice — Table de $\lnot(a \lor b)$

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

Exercice — Table de $\lnot a \wedge \lnot b$

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

Exercice — Distributivité

Soient a, b et c trois booléens.
Établir les tables de vérité de :

$a \wedge (b \lor c)$ : a ET (b OU c)
$(a \wedge b) \lor (a \wedge c)$ : (a ET b) OU (a ET c)

Ces deux expressions sont-elles équivalentes ?

Titre du popup

Message du popup !

Un peu d'histoire

Algèbre booléenne

George Boole (1847)

Claude Shannon (1938)

Vrai ou Faux ?

Vrai ou Faux ?

Vrai ou Faux ?

Vrai ou Faux ?

Les booléens

Introduction à l'algèbre de Boole

NON (NOT)

NON (NOT)

ET (AND)

Exercice 1 — Table de vérité de ET

Correction — Table de ET

Exercice 2 — Python et AND

Correction — Python et AND

OU (OR)

Exercice 3 — Table de vérité de OU

Exercice 4 — Python et OR

Correction — Python et OR

Exercice 5 — Python et NOT

Correction — NOT

XOR — OU exclusif

Exercice 6 — Table de XOR

Correction — XOR

NAND — NON ET

Exercice 7 — Table de NAND

NOR — NON OU

Exercice 8 — Table de NOR

Exercice 9 — Opérations bit à bit

Correction — Opérations bit à bit

Chiffrement XOR

Exercice 10 — Chiffrement de 'B' avec la clé 'L'

Correction — Chiffrement XOR

Quiz — Q1

Quiz — Q1 — Correction

Quiz — Q2

Quiz — Q2 — Correction

Quiz — Q6

Quiz — Q6 — Correction

Quiz — Q9

Quiz — Q9 — Correction

Théorèmes de De Morgan

Exercice — Table de \lnot(a \lor b)

Exercice — Table de \lnot a \wedge \lnot b

Exercice — Distributivité

Titre du popup

Exercice — Table de $\lnot(a \lor b)$

Exercice — Table de $\lnot a \wedge \lnot b$