Cours

Variables booléennes

Une variable booléenne ne peut prendre que deux valeurs, notées 0 et 1 pouvant modéliser des informations binaires du type : oui/non, vrai/faux, marche/arrêt, allumé/éteint, …

Au sein d'une machine, la valeur booléenne est donnée par l'état d'une grandeur électrique. Plusieurs technologies existent pour représenter ces deux états : l'intensité du courant (4/20mA), la différence de potentiel (ou tension) TTL : 0/5V.

État Logique;Valeur Booléenne;Tension TTL;Intensité VRAI;1;5 V;20 mA FAUX;0;0 V;4 mA

Opérateurs booléens

Les calculs sur les variables booléennes sont réalisés grâce à l'algèbre de Boole qui comporte deux opérateurs élémentaires : NON et ET.

Opérateur NON (négation)

L'opérateur NON s'applique sur un seul opérande et se note avec une barre au-dessus de l'opérande (comme ceci).

Sa table de vérité est :

𝑎|𝑎 0|1 1|0

Opérateur ET (conjonction)

L'opérateur ET s'applique sur deux opérandes et se note avec un point. Il renvoie VRAI seulement quand les deux opérandes sont vrais.

Sa table de vérité est :

𝑎 |𝑏 |𝑎 · 𝑏 0 |0 |0 0 |1 |0 1 |0 |0 1 |1 |1

Opérateur OU (disjonction)

𝑎|𝑏|𝑎 + 𝑏 0|0|0 0|1|1 1|0|1 1|1|1

Propriété : OU n'est pas un opérateur élémentaire puisqu'il est possible de le créer à partir des opérateurs NON et ET.
En particulier :

Opérateurs composés

Il est possible de créer d'autres opérateurs en combinant ces trois opérateurs :

• La combinaison de NON avec ET forme l'opérateur NON-ET ou NAND.
  𝑎|𝑏|𝑎 · 𝑏 0|0|1 0|1|1 1|0|1 1|1|0
• La combinaison de NON avec OU forme l'opérateur NON-OU ou NOR.
  𝑎|𝑏|𝑎 + 𝑏 0|0|1 0|1|0 1|0|0 1|1|0
• L'opérateur OU-Exclusif ou XOR exclut la solution où les deux propositions sont VRAIES. Il se note ⊕.
  𝑎|𝑏|𝑎 ⊕ 𝑏 0|0|0 0|1|1 1|0|1 1|1|0
• L'opérateur Identité (coïncidence) renvoie VRAI lorsque les deux opérandes sont égaux. Il se note ⊙.
  𝑎|𝑏|𝑎 ⊙ 𝑏 0|0|1 0|1|0 1|0|0 1|1|1

Règles de priorité : Comme les opérateurs arithmétiques, les opérateurs booléens peuvent s'enchaîner et il y a un ordre de priorité :

• les expressions entre parenthèses sont à traiter en premier ;
• s'il n'y a pas de parenthèses, les opérations s'effectuent, du plus prioritaire au moins : NON > ET > OU.

1. Vérifier l'égalité logique 𝑎 ⊕ 𝑏 = 𝑎 · 𝑏 + 𝑎 · 𝑏 qui montre que l'opérateur OU-Exclusif est bien composé à partir des opérateurs élémentaires.
   𝑎|𝑏|𝑎 ⊕ 𝑏|𝑎 · 𝑏|𝑎 · 𝑏|𝑎 · 𝑏 + 𝑎 · 𝑏 0|0|…|…|…|… 0|1|…|…|…|… 1|0|…|…|…|… 1|1|…|…|…|…
   𝑎|𝑏|𝑎 ⊕ 𝑏|𝑎 · 𝑏|𝑎 · 𝑏|𝑎 · 𝑏 + 𝑎 · 𝑏 0|0|0|0|0|0 0|1|1|0|1|1 1|0|1|1|0|1 1|1|0|0|0|0
2. Vérifier l'égalité logique 𝑎 ⊙ 𝑏 = 𝑎 ⊕ 𝑏 qui montre que l'opérateur Identité est bien composé à partir des opérateurs élémentaires.
   𝑎|𝑏|𝑎 ⊙ 𝑏|𝑎 ⊕ 𝑏| 𝑎 ⊕ 𝑏 0|0|…|…|… 0|1|…|…|… 1|0|…|…|… 1|1|…|…|…
   𝑎|𝑏|𝑎 ⊙ 𝑏|𝑎 ⊕ 𝑏| 𝑎 ⊕ 𝑏 0|0|1|0|1 0|1|0|1|0 1|0|0|1|0 1|1|1|0|1

Portes logiques

Les opérateurs élémentaires existent sous la forme hardware (composant électronique) et leur combinaison permet de construire tous les autres opérateurs composés. On parle de portes logiques qui sont intégrées dans un circuit électronique.

Propriétés des opérateurs

**Élément neutre : Opérande qui ne modifie pas l'autre opérande.** - **FAUX** est l'élément neutre de l'opérateur **OU** : 𝑎 + 0 = 𝑎 - **VRAI** est l'élément neutre de l'opérateur **ET** : 𝑎 · 1 = 𝑎

**Élément absorbant : Opérande qui renvoie sa valeur quelque soit celle de l'autre opérande.** - **VRAI** est l'élément absorbant de l'opérateur **OU** : 𝑎 + 1 = 1 - **FAUX** est l'élément absorbant de l'opérateur **ET** : 𝑎 · 0 = 0

Élément complémentaire, incompatibilité :
NON(𝑎) aussi noté 𝑎, est :

• l'élément complémentaire de 𝑎, car on a toujours :      𝑎 + 𝑎 = 1
• un élément incompatible avec 𝑎, car on a toujours:      𝑎 · 𝑎 = 0

Distributivité :

• 𝑎·(𝑏 + 𝑐) = 𝑎 · 𝑏 + 𝑎 · 𝑐

Deux Identités : les lois de De Morgan :

• 𝑎 · 𝑏 = 𝑎 + 𝑏
  𝑎|𝑏| 𝑎 · 𝑏| 𝑎|𝑏| 𝑎 + 𝑏 0|0|1|1|1|1 0|1|1|1|0|1 1|0|1|0|1|1 1|1|0|0|0|0
• 𝑎 + 𝑏 = 𝑎 · 𝑏
  𝑎|𝑏| 𝑎 + 𝑏| 𝑎|𝑏| 𝑎 · 𝑏 0|0|1|1|1|1 0|1|0|1|0|0 1|0|0|0|1|0 1|1|0|0|0|0

L'algèbre de Boole dans les langages de programmation

Les opérateurs booléens (ou logiques)

Opération\Logique\Python\C / C++ / Javascript / PHP FAUX\0\False\false VRAI\1\True\true NON\𝑎\not a\!a ET\𝑎 · 𝑏 \a and \a && b OU\𝑎 + 𝑏 \a or b\a || b

En python les expressions booléennes sont évaluées de manière séquentielle, c'est-à-dire opérande après opérande. Si dans certains cas, l'étude du premier opérande suffit, le deuxième n'est pas appelé.

Exemples : Dans l'expression a or b si a est VRAI, il est inutile de connaître b, le résultat de l'opération sera obligatoirement VRAI. La variable b peut ne pas être définie, il n'y aura pas d'erreur.
De même dans l'expression a and b si a est FAUX, il est inutile de connaître b, le résultat de l'opération sera obligatoirement FAUX. La variable b peut ne pas être définie, il n'y aura pas d'erreur.

Les opérateurs booléens binaires (ou logiques binaires)

Il existe également des opérateurs booléens binaires qui permettent de réaliser les opérations booléennes bit à bit.

Opération € Logique € Python / C / C++ / Javascript / PHP ET bit à bit € 𝑎 · 𝑏 € a & b OU bit à bit€ 𝑎 + 𝑏 €a | b OU exclusif bit à bit€𝑎 ⊕ 𝑏€ a ^ b NON bit à bit€𝑎€~ a

Applications

1. Établir la table de vérité de déverouillage de l'entrée d'un laboratoire 𝐿 en fonction des quatres variables suivantes : présence de l'employé n°1 𝐸₁, de l'employé n°2 𝐸₂, de l'employé n°3 𝐸₃ ou du directeur 𝐷 d'après les règles d'accès suivantes :
   • Le directeur de l'établissement est habilité à rentrer seul.
   • Les employés n'ont le droit de rentrer que s'ils se présentent au moins à deux.
   Le symbole ∀ signifie « quel que soit ». En effet, pour la première ligne du tableau, quelles que soient les valeurs de 𝐸₁, 𝐸₂ et 𝐸₃, si le directeur est là, la porte s'ouvre. 𝐸₁;𝐸₂;𝐸₃;𝐷;𝐿 0;0;0;0;0 ∀;∀;∀;1;1 0;0;1;0;0 0;1;0;0;0 0;1;1;0;1 1;0;0;0;0 1;0;1;0;1 1;1;0;0;1 1;1;1;0;1
2. En déduire l'équation logique 𝐿 = 𝑓(𝐸₁, 𝐸₂, 𝐸₃, 𝐷) à partir de la table de vérité. 𝐿 = 𝐷 + 𝐸₁·𝐸₂ + 𝐸₂·𝐸₃ + 𝐸₁·𝐸₃

Circuits logiques

Les portes logiques

Dans cette partie, nous allons utiliser le simulateur de CircuitVerse.org.

1. Donner l'expression logique que réalise le circuit logique ci-dessus ? A + A·B
2. Ce circuit logique peut-il être simplifié ? La sortie est la même qu'une des entrées. L'autre entrée est inutile.
   On peut simplifier l'expression équivalente : A + A·B = A·(1 + B) = A·1 = A

Implémentation électronique de l'addition

• Additionneur : Permet de réaliser l'addition de 2 bits.
• Additionneur avec retenue : Permet de réaliser l'addition de 2 bits avec une retenue précédente. Ce circuit est composé de deux circuits logiques "Additionneur".
• Additionneur 4 bits : Permet de réaliser l'addition de 2 × 4 bits. Il est composé d'un « Additionneur » et trois « Additionneurs avec retenue précédente ».

1. Vérifier que le premier circuit logique « Additionneur » réalise bien l'addition de deux bits en faisant varier les variables d'entrée A et B.
2. De même pour le deuxième circuit logique « Additionneur avec retenue » en ajoutant une éventuelle retenue précédente.
3. Enfin, vérifier le fonctionnement du troisième circuit logique « Additionneur 4 bits ».

Retenez que chaque opération effectuée dans un ordinateur, de la plus simple à la plus complexe, est réalisée à l'aide d'une combinaison de portes logiques.

Implémentation électronique de la soustraction

Réaliser le circuit logique d'un soustracteur sur un bit à l'aide du simulateur CircuitVerse.org. Les entrées seront A et B et il faut prévoir deux sorties : A - B et l'emprunt éventuel fait sur le bit de poids supérieur. Accéder au simulateur

Bibliographie :

• Site permettant de simplifier une expression booléenne : dcode.fr
• Atelier pour créer des circuits électroniques en logique combinatoire : CircuitVerse.org