Tables de vérité

Les connecteurs logiques de base sont :

• Négation $\neg P$ : vrai si $P$ est faux, faux si $P$ est vrai
• Conjonction $P \land Q$ : vrai si $P$ ET $Q$ sont tous les deux vrais
• Disjonction $P \lor Q$ : vrai si $P$ OU $Q$ est vrai (ou les deux)
• Implication $P \Rightarrow Q$ : faux uniquement si $P$ est vrai et $Q$ est faux
• Équivalence $P \Leftrightarrow Q$ : vrai si $P$ et $Q$ ont la même valeur

Pour $n$ variables propositionnelles, la table de vérité comporte $2^n$ lignes.

Équivalences fondamentales :

• Double négation : $\neg\neg P \equiv P$
• Contraposée : $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$
• Implication : $P \Rightarrow Q \equiv \neg P \lor Q$
• Lois de De Morgan : $\neg(P \land Q) \equiv \neg P \lor \neg Q$ et $\neg(P \lor Q) \equiv \neg P \land \neg Q$

• Tautologie : formule vraie pour toutes les combinaisons — dernière colonne que des V. Exemple : $P \lor \neg P$ (tiers exclu), $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$ (contraposée).

• Contradiction : formule fausse pour toutes les combinaisons — dernière colonne que des F. Exemple : $P \land \neg P$.

• Formule contingente (satisfaisable) : au moins une ligne V et au moins une ligne F.

Prouver une équivalence $A \equiv B$ : construire la table et vérifier que les colonnes de $A$ et $B$ sont identiques pour toutes les lignes (revient à prouver que $A \Leftrightarrow B$ est une tautologie).

Lois de De Morgan — preuve par table :

| $P$ | $Q$ | $\neg(P \land Q)$ | $\neg P \lor \neg Q$ | |:---:|:---:|:-----------------:|:--------------------:| | V | V | F | F | | V | F | V | V | | F | V | V | V | | F | F | V | V |

Colonnes identiques → $\neg(P \land Q) \equiv \neg P \lor \neg Q$ prouvée.

Toute formule propositionnelle peut être mise sous forme normale, facilitant l'automatisation du raisonnement logique.

Littéral : variable $P$ ou sa négation $\neg P$.

Forme Normale Disjonctive (DNF) :

• OU de ET : $\bigvee_i \bigwedge_j \ell_{ij}$ — exemple : $(P \land Q) \lor (\neg P \land R)$
• Construction depuis la table : prendre les lignes où $F$ vaut V ; pour chaque ligne, écrire la conjonction des littéraux (variable si V, négation si F) ; faire le OU de toutes ces conjonctions.

Forme Normale Conjonctive (CNF) :

• ET de OU : $\bigwedge_i \bigvee_j \ell_{ij}$ — exemple : $(P \lor Q) \land (\neg P \lor R)$
• Construction depuis la table : prendre les lignes où $F$ vaut F ; pour chaque ligne, écrire la disjonction des littéraux inversés (négation si V, variable si F) ; faire le ET de toutes ces clauses.
• Utilisée par les solveurs SAT (vérification formelle, IA).

Résultat : toute fonction logique admet une DNF et une CNF — formes canoniques pour l'implémentation en circuits.

Chaque connecteur logique correspond à une porte logique électronique :

| Connecteur | Porte | Comportement | |---|---|---| | $\neg P$ | NOT | Inverse le signal | | $P \land Q$ | AND | 1 seulement si les deux entrées à 1 | | $P \lor Q$ | OR | 1 si au moins une entrée à 1 | | $\neg(P \land Q)$ | NAND | Inverse de AND — porte universelle | | $\neg(P \lor Q)$ | NOR | Inverse de OR — porte universelle | | $P \oplus Q$ | XOR | 1 si exactement une entrée à 1 |

XOR (ou exclusif) : $P \oplus Q \equiv (P \lor Q) \land \neg(P \land Q)$

Additionneur 1 bit : somme $= A \oplus B$, retenue $= A \land B$.

Portes universelles : NAND seule (ou NOR seule) suffit pour construire tous les autres connecteurs — fondamental pour la fabrication de circuits intégrés (réduction du nombre de types de portes).

Minimisation : DNF/CNF permettent d'implémenter une fonction logique en circuit ; tables de Karnaugh et algorithme de Quine-McCluskey réduisent le nombre de portes nécessaires.