Informatique
Table de vérité d'une expression booléenne
Écrivez l'expression dans la notation que vous préférez — AND/OR/NOT, les symboles · + ', ou && || ! — et obtenez la table de vérité complète.
Comment lire une table de vérité
Une table de vérité énumère toutes les combinaisons possibles des entrées et la valeur que prend l'expression pour chacune. Avec n variables il y a 2ⁿ lignes : deux variables donnent quatre lignes, trois en donnent huit, quatre seize. L'ordre conventionnel est celui du compteur binaire, la première variable changeant le plus lentement, et il garantit qu'aucune combinaison n'est oubliée.
Les trois opérateurs fondamentaux se ramènent à trois phrases. AND n'est vrai que si les deux entrées le sont, OR n'est faux que si les deux sont fausses, NOT inverse. Le XOR, moins utilisé dans les premiers exercices et central dans les circuits arithmétiques, est vrai quand les entrées diffèrent : c'est l'addition binaire sans retenue.
La table est aussi l'outil qui permet de démontrer une identité. Deux expressions sont équivalentes quand leurs colonnes de sortie coïncident ligne à ligne, et c'est ainsi que l'on vérifie les lois de De Morgan : la négation d'un AND est le OR des négations, et réciproquement. C'est la transformation qui permet de réaliser n'importe quel circuit avec un seul type de porte.
Erreurs fréquentes
- Se tromper sur la priorité des opérateurs : NOT lie plus fort que AND, qui lie plus fort que OR. Sans parenthèses, A OR B AND C signifie A OR (B AND C), pas (A OR B) AND C.
- Mal appliquer De Morgan en ne niant qu'un seul terme : la négation de (A AND B) est (NOT A) OR (NOT B), l'opérateur central changeant lui aussi.
- Sauter des combinaisons dans la table : avec trois variables il y a huit lignes et toutes doivent y figurer, même celles qui semblent évidentes. Suivre l'ordre binaire évite d'en perdre une.
Questions fréquentes
Combien de lignes compte une table de vérité ?
Deux puissance le nombre de variables : 2ⁿ. Deux variables donnent quatre lignes, trois huit, quatre seize. Chaque ligne est une combinaison différente de zéros et de uns.
Quelle est la priorité des opérateurs booléens ?
NOT d'abord, puis AND, puis XOR, enfin OR. C'est la hiérarchie de l'algèbre ordinaire si l'on voit AND comme un produit et OR comme une somme — d'où les notations · et +.
Que disent les lois de De Morgan ?
Que la négation d'une conjonction est la disjonction des négations, et inversement : NOT(A AND B) = NOT A OR NOT B, et NOT(A OR B) = NOT A AND NOT B. On les vérifie en comparant les colonnes de sortie.
Quelle différence entre OR et XOR ?
Le OR est vrai même quand les deux entrées sont vraies ; le XOR non : il n'est vrai que lorsque les entrées diffèrent. C'est pourquoi on l'appelle aussi « OU exclusif ».
Comment fonctionne ce calcul
Opérateurs : NOT A vaut 1 quand A vaut 0. A AND B vaut 1 seulement si A = B = 1. A OR B vaut 0 seulement si A = B = 0. A XOR B vaut 1 quand A ≠ B. Priorité, de la plus forte à la plus faible : NOT, AND, XOR, OR ; les parenthèses la remplacent. Nombre de lignes avec n variables : 2ⁿ. Lois de De Morgan : ¬(A·B) = ¬A + ¬B et ¬(A + B) = ¬A · ¬B. Identités utiles : A + A·B = A (absorption), A·(A + B) = A, A + ¬A = 1 (tiers exclu), A·¬A = 0 (non-contradiction). L'analyseur accepte la notation par mots, la notation symbolique (· + ') et celle des langages de programmation (&& || !).