Table de vérité pour toute expression logique

D’abord les parenthèses, puis la négation, puis la conjonction (ET), puis la disjonction (OU) avec le OU exclusif, puis l’implication, et l’équivalence en dernier. Ainsi ¬A ∧ B ∨ C ∧ D signifie ((¬A) ∧ B) ∨ (C ∧ D). Un cas n’a pas de règle unique : une chaîne d’implications sans parenthèses. La logique mathématique lit A ⇒ B ⇒ C comme A ⇒ (B ⇒ C), alors que certains cours l’évaluent de gauche à droite. L’implication n’est pas associative, donc les deux lectures donnent des tables différentes — l’outil indique celle qu’il a utilisée et permet d’en changer. Attention : dans une rédaction, « A ⇒ B ⇒ C » veut souvent dire « A ⇒ B et B ⇒ C » ; pour cette formule-là, écrivez (A ⇒ B) ∧ (B ⇒ C).

A ⇒ B est une promesse : « si A, alors B ». Elle n’est rompue que lorsque A est vraie et que B ne l’est pas — c’est l’unique ligne 1 ⇒ 0 = 0. Quand A est fausse, la promesse n’a pas été mise à l’épreuve : elle est tenue pour respectée, et l’implication vaut 1. Voilà pourquoi A ⇒ B a la même table que ¬A ∨ B, et pourquoi l’outil remplace l’implication par cette formule exacte quand il simplifie.

La forme canonique disjonctive prend une conjonction de toutes les variables — un minterme — pour chaque ligne où F = 1 : une fonction qui vaut 1 sur six lignes reçoit six longs termes. La minimisation fusionne les termes qui ne diffèrent que par une variable : A∧B∧C ∨ A∧B∧¬C = A∧B. Dans un tableau de Karnaugh, ces termes sont des cases voisines, et un regroupement de 2, 4 ou 8 cases devient un seul terme court. La méthode de Quine-McCluskey fait les mêmes fusions de façon systématique, puis choisit l’ensemble de termes le moins coûteux qui couvre encore tous les 1.

Listez les lignes de la table complète où F prend la valeur donnée dans l’extrait — il y en a généralement peu. Cherchez ce qu’elles ont en commun : si y = 1 chaque fois que F = 0, une colonne qui contient un 0 sur une ligne où F = 0 ne peut pas être y. Prenez ensuite la ligne la plus parlante de l’extrait et voyez à quelles lignes complètes elle peut correspondre ; les lignes de l’extrait sont toutes différentes, ce qui élimine d’autres cas. Le mode « Énigme » fait exactement cela et écrit chaque étape.

Le polynôme de Jegalkine (forme normale algébrique) écrit toute fonction booléenne avec seulement ET, OU exclusif et la constante 1, et il est unique pour chaque fonction — un moyen commode de comparer des fonctions et de tester la linéarité. Les cinq classes de Post répondent à une autre question : peut-on construire n’importe quelle fonction à partir d’un jeu de portes donné ? D’après le théorème de Post, un ensemble est complet exactement lorsque, pour chacune des cinq classes, il contient une fonction hors de cette classe. NAND (NON-ET) et NOR (NON-OU) ne sont dans aucune d’elles : c’est pourquoi chacune suffit, à elle seule, à construire n’importe quel circuit.