Aller au contenu

1NSI : Opérateurs et Expressions Booléennes.⚓︎

Expressions Booléennes⚓︎

Expression Booléenne

La composition de plusieurs opérateurs booléens est appelée une Expression Booléenne

Exp

\(\overline{(x+y)}.z\) est une expression booléenne.

Pte

Toute fonction booléenne peut être définie par une Expression Booléenne, ou Formule Booléenne, de ses entrées.

Exp

L'expression booléenne \(f(x,y,z)=(x. \overline{y}) \oplus (\overline{x} + z)\) définit une fonction booléenne \(f\) des entrées \(x,y,z\).

Utilité En électronique,

  • les Tables de vérité permettent de représenter des Expressions Booléennes (et réciproquement), i.e. qu'une table de vérité peut être convertie en expression booléenne (et réciproquement)
  • les Expressions Booléennes permettent de réprésenter des circuits.

Mais il faut d'abord apprendre à simplifier les expressions booléennes, grâce aux:

Lois de Morgan et Autres Lois composition⚓︎

Lois de Morgan⚓︎

Exp

  • Si il est faux de dire que je suis Grand et Fort, c'est que :
    • Ou bien je ne suis pas Grand
    • Ou bien je ne suis pas Fort
  • Si il est faux de dire que je suis Grand ou Fort, c'est que je ne suis :
    • NI Grand
    • NI Fort

Autrement dit :

Lois de Morgan

Notations
ET: \(\land\)
OU: \(\lor\)		 Notations
ET: \(.\)
OU: \(+\)
\(\overline{A\land B} = \overline{A} \lor \overline{B}\) \(\overline{A.B} = \overline{A} + \overline{B}\)
\(\overline{A\lor B} = \overline{A} \land \overline{B}\) \(\overline{A+B} = \overline{A} . \overline{B}\)

Preuve des Lois de Morgan

  1. Renseigner les Tables de Vérité suivantes :

    Col

    \(A\) \(B\) \(S=\overline{A\land B}\)
    \(0\) \(0\)
    \(0\) \(1\)
    \(1\) \(0\)
    \(1\) \(1\)

    Col

    \(A\) \(B\) \(S=\overline{A}\lor \overline{B}\)
    \(0\) \(0\)
    \(0\) \(1\)
    \(1\) \(0\)
    \(1\) \(1\)

  2. Que peut-on en déduire ?

Autres Lois de Composition⚓︎

Lois de Composition

Les lois de composition sont des règles logiques qui permettent de simplifier des expressions algébriques:

and, . , \(\wedge\) or, +, \(\vee\)
Involutif \(\overline {\overline{A}} = A\)
\(not\) \(not A = A\)
Neutre \(1.A=A\)
\(1\) \(and\) \(A=A\)		 \(0+A=A\)
\(0\) \(or\) \(A\) \(=A\)
Absorbant \(0.A=0\)
\(0\) \(and\) \(A\) \(=0\)		 \(1+A=1\)
\(1\) \(or\) \(A\) \(=1\)
Idempotence \(A.A=A\)
\(A\) \(and\) \(A\) \(=A\)		 \(A+A=A\)
\(A\) \(or\) \(A\) \(=A\)
Complément \(A.\overline{A}=0\)
\(A\) \(and\) \(\overline{A}\) \(=0\)		 \(A+\overline{A}=1\)
\(A\) \(or\) \(\overline{A}\) \(=1\)
Commutativité \(A.B=B.A\)
\(A\) \(and\) \(B\) \(=B\) \(and\) \(A\)		 \(A+B=B+A\)
\(A\) \(or\) \(B\) \(=B\) \(or\) \(A\)
Associativité \(A.(B.C)=(A.B).C\)
\(A\) \(and\) \((B\) \(and\) \(C)\) \(=(A\) \(and\) \(B)\) \(and\) \(C\)		 \(A+(B+C)=(A+B)+C\)
\(A\) \(or\) \((B\) \(or\) \(C)\) \(=(A\) \(or\) \(B)\) \(or\) \(C\)
Distributivité \(A.(B+C)=A.B+A.C\)
\(A\) \(and\) \((B\) \(or\) \(C)\) \(=(A\) \(and\) \(B)\) \(or\) \((A\) \(and\) \(C)\)		 \(A+(B.C)=(A+B).(A+C)\)
\(A\) \(or\) \((B\) \(and\) \(C)\) \(=(A\) \(or\) \(B)\) \(and\) \((A\) \(or\) \(C)\)
Lois de Morgan \(\overline{A.B}=\overline{A}+\overline{B}\)
\(not (A\) \(and\) \(B)\) \(=not\) \(A\) \(or\) \(not\) \(B\)
\(=(not\) \(A)\) \(or\) \((not\) \(B)\)		 \(\overline{A+B}=\overline{A}.\overline{B}\)
\(not (A\) \(or\) \(B)\) \(=not\) \(A\) \(and\) \(not\) \(B\)
\(=(not\) \(A)\) \(and\) \((not\) \(B)\)

Ex

Démontrer chacune de ces équivalences/égalités grâce à des Tables de Vérité.

Priorités des Opérateurs Booléens

  • le \(not\) est prioritaire sur le \(and\) et sur le \(or\) (cf dernière ligne du tableau précédent)
  • le \(and\) est prioritaire sur le \(or\)
  • Résumé: \(not\) \(>>\) \(and\) \(>>\) \(or\)
  • Précaution : En cas de doute -> surparenthéser !

Conversions: Tables de Vérité \(\Leftrightarrow\) Expressions Booléennes \(\Leftrightarrow\) Circuits⚓︎

  • Expression Booléenne \(\Rightarrow\) Table de Vérité: Soit \(f(x,y,z)=(x.\overline{y})+z\) une fonction booléenne. Construire la Table de vérité de cette Expression Booléenne :
\(x\) \(y\) \(z\) \(\overline{y}\) \(x. \overline{y}\) \(f(x,y,z)=(x.\overline{y})+z\)
\(0\) \(0\) \(0\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(0\) \(1\)
\(0\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(1\) \(1\) \(1\) \(0\) \(0\) \(1\)
  • Table de Vérité: \(\Rightarrow\) Expression Booléenne:
    • A chaque combinaison de valeurs qui rend la fonction égale à 1, on associe le produit des variables en ajoutant la barre de la négation sur les variables dont la valeur est 0.
    • Ensuite, on fait la somme des produits déterminés précédemment.
    • Enfin, on simplifie la formule
\(x\) \(y\) \(z\) \(f(x,y,z)\)
\(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(0\)
\(0\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(1\) \(\overline x.y.z\)
\(1\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(x.\overline y.z\)
\(1\) \(1\) \(0\) \(1\) \(x.y.\overline z\)
\(1\) \(1\) \(1\) \(1\) \(x.y.z\)

On trouve \(f(x,y,z)=\overline x.y.z + x.\overline y.z + x.y.\overline z + x.y.z\)

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 prouvèrent 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.

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.

Conjonction \(\&\) (AND)⚓︎

Symbole
et Synomymes
Usuels		 Nom (en..)
\(\&\) Esperluette 🇫🇷
ET Commercial 🇫🇷
Ampersand 🇬🇧
ET ET 🇫🇷
and AND 🇬🇧
\(\wedge\) ET
(Notation)
Logique
. ET
Notation
Mathématique

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

  • x & F = F
  • x & 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

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

Notation usuelle en électronique : \(Q=A \wedge B\)

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)⚓︎

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

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

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

  • x | V = V
  • x | 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

Notation usuelle en électronique : \(Q=A \vee B\)

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)

Négation (NOT)⚓︎

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

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

  • ~V = F
  • ~F = V

On en déduit la table suivante:

Table de vérité de NOT ❤

x ~x
F V
V F

Notation usuelle en électronique : \(Q=\neg A\)

Exemples en Python⚓︎

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

Exercice 1⚓︎

Comprendre ce mème :

image

Exercice 2⚓︎

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

Exemple (inintéressant) de circuit :

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

Fonctions composées⚓︎

Disjonction exclusive XOR⚓︎

(en français OU EXCLUSIF)

x ^ y = (x & ~y) | (~x & y)

Table de vérité de XOR ❤

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

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

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

Fonction Non Et (NAND)⚓︎

x ↑ y = ~(x & y)

Table de vérité de NAND ❤

x y x ↑ y
F F V
F V V
V F V
V V F

Fonction Non Ou (NOR)⚓︎

x ↓ y = ~(x & y)

Table de vérité de NOR ❤

x y x ↓ y
F F V
F V F
V F F
V V F

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

Exercice 4⚓︎

Calculer les opérations suivantes.

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


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


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

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

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

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'

Exercice 5 : préparation du pydéfi⚓︎

Objectif : chiffrer (= crypter) le mot "BONJOUR" avec la clé (de même taille) "MAURIAC".

Protocole de chiffrage : XOR entre le code ASCII des lettres de même position.

<!-* 

msg = "BONJOUR"
cle = "MAURIAC"

def crypte_lettre(lm, lc):
  a = ord(lm)
  b = ord(lc)
  c = a^b
  lettre = chr(c)

  return lettre

def crypte_mot(mot1, mot2):
  mot3 = ""
  for i in range(len(mot1)):
    car = crypte_lettre(mot1[i],mot2[i])
    mot3 = mot3 + car
  return mot3

crypte_mot(msg, cle)

'\x0f\x0e\x1b\x18\x06\x14\x11'

-->

Exercice⚓︎

À faire sur Capytale : Lien

Résolvez le pydéfi la clé endommagée

<!-*

solution :

lien

-->

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)

Toutes ces lois sont aisément compréhensibles si on les transpose en mathématiques :

  • & équivaut à \(\times\)
  • \(|\) équivaut à \(+\)
  • \(\neg\) équivaut à \(-\)