Aller au contenu

Les opérateurs booléens⚓︎

image

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, les travaux de 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. Pendant la deuxième guerre mondiale, les travaux d'Alan TURING puis de John VON NEUMANN poseront définitivement les bases de l'informatique moderne.

2. Algèbre de Boole⚓︎

L'algèbre de Boole définit des opérations dans un ensemble qui ne contient que deux éléments notés 0 et 1, ou bien FAUX et VRAI ,ou encore False et True (en Python)

Les opérations fondamentales sont :

  • la conjonction ("ET")
  • la disjonction ("OU")
  • la négation ("NON").

Dans toute la suite, x et y désigneront des Booléens (éléments d'une algèbre de Boole) quelconques, F désignera FAUX et V désignera VRAI.

2.1 Conjonction (AND)⚓︎

  • français : ET
  • anglais (et Python) : and
  • notation logique : \(\wedge\)
  • notation mathématique : .
  • autre symbole : & (appelé esperluette en français et ampersand en anglais)

C'est l'opération définie par:

  • x and F = F
  • x and V = x

Puisque l'algèbre de Boole ne contient que deux éléments, on peut étudier tous les cas possibles et les regrouper dans un tableau appelé table de vérité:

Table de vérité de AND ❤

x y x & y
F F F
F V F
V F F
V V V

Notations usuelles:

  • \(Q=A . B\)
  • \(Q=A \wedge B\)
  • \(Q=A\)&\(B\)
  • \(Q=A and B\)

On représente souvent les opérateurs booléens à l'aide de portes logiques:

Symbole européen (norme ISO): Symbole américain (norme ANSI):

Exemples en Python⚓︎

>>> n = 20
>>> (n % 10 == 0) and (n % 7 == 0)
False
>>> (n % 4 == 0) and (n % 5 == 0)
True

L'évaluation paresseuse⚓︎

Pouvez-vous prévoir le résultat du code ci-dessous ?

>>> (n % 4 == 0) and (n % 0 == 0)
    ---------------------------------------------------------------------------

    ZeroDivisionError                         Traceback (most recent call last)

    <ipython-input-3-d8a98dcba9be> in <module>
    ----> 1 (n % 4 == 0) and (n % 0 == 0)


    ZeroDivisionError: integer division or modulo by zero

Évidemment, la division par 0 provoque une erreur.
Mais observez maintenant ce code :

>>> (n % 7 == 0) and (n % 0 == 0)
False

On appelle évaluation paresseuse le fait que l'interpréteur Python s'arrête dès que sa décision est prise : comme le premier booléen vaut False et que la conjonction and est appelée, il n'est pas nécessaire d'évaluer le deuxième booléen.

2.2 Disjonction (OR)⚓︎

  • français : OU
  • anglais (et Python) : or
  • notation logique : \(\vee\)
  • notation mathématique : \(+\)
  • autre symbole : | appelé pipe en anglais

C'est l'opération définie par:

  • x or V = V
  • x or F = x

On en déduit la table suivante:

Table de vérité de OR ❤

x y x or y
F F F
F V V
V F V
V V V

Notations usuelles:

  • \(Q=A + B\)
  • \(Q=A \vee B\)
  • \(Q=A or B\)
  • \(Q=A | B\)

Symbole européen (norme ISO):
Symbole américain (norme ANSI):

Exemples en Python⚓︎

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

L'évaluation paresseuse (retour)⚓︎

Pouvez-vous prévoir le résultat du code ci-dessous ?

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

2.3 Négation (NOT)⚓︎

  • français : NON
  • anglais (et Python) : not
  • notation logique : \(\neg\)
  • notation mathématique : \(\overline{x}\)
  • autre symbole : ~

C'est l'opération définie par:

  • not V = F
  • not F = V

On en déduit la table suivante:

Table de vérité de NOT ❤

x not x
F V
V F

Notations usuelles:

  • \(Q=\overline{A}\)
  • \(Q=\neg A\)
  • \(Q=not A\)
  • \(Q=\) ~\(A\)

Symbole européen (norme ISO): Symbole américain (norme ANSI):

Exemples en Python⚓︎

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

2.4 Exercice 1⚓︎

Exemple de circuit :

  1. Ouvrir le simulateur de circuits et créer pour chaque opération AND, OR, NOT un circuit électrique illustrant ses propriétés.

  2. Utiliser successivement les circuits XOR, NAND et NOR et établir pour chacun leur table de vérité.

Un corrigé à regarder après avoir réalisé vos propres schémas.

3. Fonctions composées⚓︎

3.1 Disjonction exclusive XOR⚓︎

(en français OU EXCLUSIF)

x ^ y = (x and not y) | (not x and y)

Table de vérité de XOR ❤

x y x ^ y
F F F
F V V
V F V
V V F

Symbole européen (norme ISO): Symbole américain (norme ANSI):

Le XOR joue un rôle fondamental en cryptographie car il possède une propriété très intéressante : (x ^ y)^y=x

Si x est un message et y une clé de chiffrage, alors x^y est le message chiffré. Mais en refaisant un XOR du message chiffré avec la clé y, on retrouve donc le message x initial.

3.2 Fonction Non Et (NAND)⚓︎

not(x and y)

Table de vérité de NAND ❤

x y x and y not(x and y)
F F F V
F V F V
V F F V
V V V F

Symbole européen (norme ISO): Symbole américain (norme ANSI):

3.3 Fonction Non Ou (NOR)⚓︎

not(x or y)

Table de vérité de NOR ❤

x y x + y not(x + y)
F F F V
F V V F
V F V F
V V V F

Symbole européen (norme ISO): Symbole américain (norme ANSI):

Il est temps de se reposer un peu et d'admirer cette vidéo :

Remarque :⚓︎

Les fonctions NAND ET NOR sont dites universelles : chacune d'entre elles peut générer l'intégralité des autres portes logiques. Il est donc possible de coder toutes les opérations uniquement avec des NAND (ou uniquement avec des NOR). Voir Wikipedia

3.4 Exercice 4⚓︎

Calculer les opérations suivantes.

   1011011
&  1010101
----------


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


   1011011
^  1010101
----------
solution 
 1011011
&1010101
----------
 1010001

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

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

3.5 Calculs en Python⚓︎

les opérateurs &, | et ^ sont utilisables directement en Python

# calcul A
>>> 12 & 7
4

# calcul B
>>> 12 | 7
15

# calcul C
>>> 12 ^ 5
9

Pour comprendre ces résultats, il faut travailler en binaire. Voici les mêmes calculs :

# calcul A
>>> bin(0b1100 & 0b111)
    '0b100'

# calcul B
>>> bin(0b1100 | 0b111)
   '0b1111'

# calcul C
>>> bin(0b1100 ^ 0b111)
    '0b1011'

!!! Défi_1: "Personnage mystère" Personnage mystère

!!! Défi_2: "Clé endommagée" clé endommagée Objectif : chiffrer (= crypter) le mot "BONJOUR" avec la clé (de même taille) "LEMONDE".
Protocole de chiffrage : XOR entre le code ASCII des lettres de même position.

Complément : propriétés des opérateurs logiques⚓︎

Les propriétés suivantes sont facilement démontrables à l'aide de tables de vérités: (source : G.Connan)

Dernière mise à jour: 2025-01-13