Aller au contenu

Chapitre 6.1 : Les opérateurs booléens⚓︎

I- Introduction⚓︎

En 1854, le Britannique George Boole invente une algèbre pour formaliser la logique à l'aide d'outils mathématiques. Dans l'algèbre de Boole, les variables booléennes ne peuvent prendre que les valeurs 0 (pour faux) et 1 (pour vrai). Elle définit également trois opérateurs de base (ET, OU, NON), qui permettent d'effectuer des opérations sur ces variables et de traiter tous les problèmes de logique.

L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Les ordinateurs, qui manipulent uniquement des bits (0 ou 1), s'appuient sur la théorie de Boole pour effectuer des opérations logiques grâce à des circuits électroniques, appelés portes logiques, qui modélisent des opérateurs booléens.

II - Les Opérateurs Logiques⚓︎

A savoir

L'algèbre de Boole définit trois opérateurs logiques de base : ET, OU et NON. En informatique, un quatrième opérateur est très utilisé : l'opérateur XOR (OU exclusif).

Opérateur NON (négation)⚓︎

L'opérateur NON, noté \(\bar{a}\), transforme vrai en faux et inversement.

Entrée Sortie
a \(S = \text{non } a\)
0 1
1 0

Opérateur OU (disjonction)⚓︎

L'opérateur OU, noté \(a + b\), est vrai si et seulement si \(a\) est vrai ou \(b\) est vrai (ou si les deux sont vrais).

Entrée Entrée Sortie
a b \(S = a \text{ ou } b\)
0 0 0
0 1 1
1 0 1
1 1 1

Opérateur ET (conjonction)⚓︎

L'opérateur ET, noté \(a \times b\), est vrai si et seulement si \(a\) est vrai et \(b\) est vrai.

Entrée Entrée Sortie
a b \(S = a \text{ et } b\)
0 0 0
0 1 0
1 0 0
1 1 1

Opérateur XOR (OU exclusif)⚓︎

L'opérateur XOR, noté \(a \oplus b\), est vrai si et seulement si \(a\) est vrai ou \(b\) est vrai, mais pas si les deux sont vrais.

Entrée Entrée Sortie
a b \(S = a \text{ xor } b\)
0 0 0
0 1 1
1 0 1
1 1 0

II - Expressions Booléennes⚓︎

A savoir

Une expression booléenne est une expression faisant intervenir des opérateurs booléens et des booléens.

Par exemple, si \(a\) et \(b\) sont des booléens, alors \(\text{non}(\text{non } a \text{ ou } \text{non } b)\) est une expression booléenne.

On peut construire la table de vérité de cette expression booléenne en procédant étape par étape :

Entrée Entrée non a non b non a ou non b non (non a ou non b)
a b
0 0 1 1 1 0
0 1 1 0 1 0
1 0 0 1 1 0
1 1 0 0 0 1

Explications :⚓︎

  • La colonne non a est complétée en prenant la négation des valeurs de a.
  • Même principe pour la colonne non b.
  • La colonne non a ou non b s'obtient en appliquant l'opérateur « ou » entre non a et non b.
  • Enfin, la sortie en dernière colonne s'obtient en prenant la négation de la colonne précédente.

Les opérateurs booléens vérifient la propriété de distributivité suivante, qui est vraie pour tous booléens \(a\), \(b\) et \(c\) :

\[ a \text{ et } (b \text{ ou } c) = (a \text{ et } b) \text{ ou } (a \text{ et } c) \]

Table de vérité pour démontrer cette égalité :⚓︎

a b c b ou c a et (b ou c)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
a b c a et b a et c (a et b) ou (a et c)
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 0 0 0
1 0 1 0 1 1
1 1 0 1 0 1
1 1 1 1 1 1

Vérification de l'Égalité⚓︎

En comparant les colonnes « a et (b ou c) » et « (a et b) ou (a et c) », nous constatons que les valeurs sont identiques pour toutes les combinaisons possibles de \(a\) et \(b\) : l'égalité entre les deux expressions est donc vraie.

a b c b ou c a et (b ou c) a et b a et c (a et b) ou (a et c)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

III - Exercices⚓︎

Exercice 1⚓︎

Construire la table de vérité de « (a et non b) ou (non a et b) » et vérifier que l'égalité suivante est vraie :

\[ a \text{ xor } b = (a \text{ et non } b) \text{ ou } (\text{non } a \text{ et } b) \]
Solution

Pour construire la table de vérité de l'expression « (a et non b) ou (non a et b) », nous devons considérer toutes les combinaisons possibles des valeurs de \(a\) et \(b\).

Table de Vérité⚓︎

a b non a non b a et non b non a et b (a et non b) ou (non a et b) a xor b
0 0 1 1 0 0 0 0
0 1 1 0 0 1 1 1
1 0 0 1 1 0 1 1
1 1 0 0 0 0 0 0

Explication⚓︎

  • non a : Négation de \(a\)
  • non b : Négation de \(b\)
  • a et non b : Conjonction de \(a\) et de la négation de \(b\)
  • non a et b : Conjonction de la négation de \(a\) et de \(b\)
  • (a et non b) ou (non a et b) : Disjonction des deux expressions précédentes
  • a xor b : OU exclusif de \(a\) et \(b\)

Vérification de l'Égalité⚓︎

En comparant les colonnes « (a et non b) ou (non a et b) » et « a xor b », nous constatons que les valeurs sont identiques pour toutes les combinaisons possibles de \(a\) et \(b\).

Exercice 2⚓︎

  1. Montrer que \( x \text{ et } y = \text{non}(\text{non}(x) \text{ ou non}(y)) \).
  2. Montrer que \( x \text{ ou } y = \text{non}(\text{non}(x) \text{ et non}(y)) \).
Solution

Pour montrer ces égalités, nous allons construire les tables de vérité des expressions de chaque côté des égalités et vérifier qu'elles sont identiques.

1. Montrer que \( x \text{ et } y = \text{non}(\text{non}(x) \text{ ou non}(y)) \)⚓︎

Table de Vérité⚓︎
x y non x non y non x ou non y non(non x ou non y) x et y
0 0 1 1 1 0 0
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 0 1 1
Explication⚓︎
  • non x : Négation de \(x\)
  • non y : Négation de \(y\)
  • non x ou non y : Disjonction des négations de \(x\) et \(y\)
  • non(non x ou non y) : Négation de la disjonction des négations de \(x\) et \(y\)
  • x et y : Conjonction de \(x\) et \(y\)

En comparant les colonnes « non(non x ou non y) » et « x et y », nous constatons que les valeurs sont identiques pour toutes les combinaisons possibles de \(x\) et \(y\).

Nous avons donc montré que :

\[ x \text{ et } y = \text{non}(\text{non}(x) \text{ ou non}(y)) \]

2. Montrer que \( x \text{ ou } y = \text{non}(\text{non}(x) \text{ et non}(y)) \)⚓︎

Table de Vérité⚓︎
x y non x non y non x et non y non(non x et non y) x ou y
0 0 1 1 1 0 0
0 1 1 0 0 1 1
1 0 0 1 0 1 1
1 1 0 0 0 1 1
Explication⚓︎
  • non x : Négation de \(x\)
  • non y : Négation de \(y\)
  • non x et non y : Conjonction des négations de \(x\) et \(y\)
  • non(non x et non y) : Négation de la conjonction des négations de \(x\) et \(y\)
  • x ou y : Disjonction de \(x\) et \(y\)

En comparant les colonnes « non(non x et non y) » et « x ou y », nous constatons que les valeurs sont identiques pour toutes les combinaisons possibles de \(x\) et \(y\).

Nous avons donc montré que :

\[ x \text{ ou } y = \text{non}(\text{non}(x) \text{ et non}(y)) \]

Conclusion⚓︎

Nous avons démontré les égalités suivantes en utilisant des tables de vérité :

  1. \( x \text{ et } y = \text{non}(\text{non}(x) \text{ ou non}(y)) \)
  2. \( x \text{ ou } y = \text{non}(\text{non}(x) \text{ et non}(y)) \)

Exercice 3⚓︎

Soit la fonction booléenne multiplexeur telle que :

\(mux(x, y, z) = y~~si~~x = 0\)
\(mux(x, y, z) = z~~si~~x = 1\)

  1. Dresser la table de vérité de cette fonction.

  2. Montrer que \(\text{mux}(x, y, z) = (\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z)\).

Solution

1. Table de Vérité de la Fonction Multiplexeur⚓︎

Pour dresser la table de vérité de cette fonction, nous devons considérer toutes les combinaisons possibles des valeurs de \(x\), \(y\) et \(z\).

x y z mux(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

2. Montrer que \(\text{mux}(x, y, z) = (\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z)\)⚓︎

Pour montrer cette égalité, nous allons comparer la table de vérité de \(\text{mux}(x, y, z)\) avec celle de l'expression \((\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z)\).

Table de Vérité de \((\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z)\)⚓︎

x y z non(x) non(x) et y x et z (non(x) et y) ou (x et z)
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 1 1 0 1
0 1 1 1 1 0 1
1 0 0 0 0 0 0
1 0 1 0 0 1 1
1 1 0 0 0 0 0
1 1 1 0 0 1 1

Comparaison des Tables de Vérité⚓︎

En comparant les deux tables de vérité, nous constatons que les colonnes \(\text{mux}(x, y, z)\) et \((\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z)\) sont identiques.

x y z mux(x, y, z) (non(x) et y) ou (x et z)
0 0 0 0 0
0 0 1 0 0
0 1 0 1 1
0 1 1 1 1
1 0 0 0 0
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1

Nous avons donc montré que :

\[ \text{mux}(x, y, z) = (\text{non}(x) \text{ et } y) \text{ ou } (x \text{ et } z) \]

Exercice 4⚓︎

Écrire en Python une fonction xor(a, b) :

  • Qui prend en paramètres 2 booléens a et b représentés par 0 et 1
  • Qui renvoie la valeur de l'opération logique « a xor b »

Jeu de tests avec exemples :

# Programme principal
assert xor(1, 0) == 1, "Erreur fonction xor test 1"
assert xor(1, 1) == 0, "Erreur fonction xor test 2"
assert xor(0, 1) == 1, "Erreur fonction xor test 3"
assert xor(0, 0) == 0, "Erreur fonction xor test 4"
print("Tests fonction xor OK")
Solution

L'opération logique XOR (ou exclusif) renvoie 1 si les deux entrées sont différentes et 0 si elles sont identiques. En d'autres termes :

  • \(a \text{ xor } b = 1\) si \(a \neq b\)
  • \(a \text{ xor } b = 0\) si \(a = b\)

Nous pouvons implémenter cette logique en Python en utilisant une structure conditionnelle if et une seule instruction return. Voici comment nous pouvons écrire cette fonction :

# Définition des fonctions
def xor(a, b):
    """Fonction XOR qui prend deux booléens a et b représentés par 0 et 1,
    et renvoie la valeur de l'opération logique « a xor b ».
    Paramètres :
     - a (int) : Premier booléen représenté par 0 ou 1.
     - b (int) : Deuxième booléen représenté par 0 ou 1.
    Renvoie :
     - (int) : Résultat de l'opération logique XOR entre a et b.
    """
    if a != b:
        resultat = 1
    else:
        resultat = 0
    return resultat

# Programme principal
# Tests pour la fonction xor
assert xor(1, 0) == 1, "Erreur fonction xor test 1"
assert xor(1, 1) == 0, "Erreur fonction xor test 2"
assert xor(0, 1) == 1, "Erreur fonction xor test 3"
assert xor(0, 0) == 0, "Erreur fonction xor test 4"
print("Tests fonction xor OK")

Explication⚓︎

  • La fonction xor prend deux paramètres a et b.
  • Elle utilise une expression conditionnelle if pour vérifier si a et b sont différents.
  • Si a et b sont différents, l'expression renvoie 1.
  • Si a et b sont identiques, l'expression renvoie 0.