Tables de vérité

Une **table de vérité** énumère **toutes les combinaisons possibles** de valeurs de vérité des variables d'une expression et donne, pour chaque ligne, la valeur de l'expression entière. **Combien de lignes ?** Chaque variable peut être V (vrai) ou F (faux), donc chaque nouvelle variable double le nombre de lignes : $$\text{lignes} = 2^n \quad (n = \text{nombre de variables})$$ Ainsi, 2 variables demandent $2^2 = 4$ lignes et 3 variables demandent $2^3 = 8$ lignes. **Construire une table en 4 étapes :** 1. Compte les variables et écris $2^n$ lignes vides. 2. Remplis les colonnes des variables dans un ordre fixe : la première colonne est à moitié V, puis à moitié F ; chaque colonne suivante change deux fois plus souvent ; la dernière colonne alterne V, F, V, F. 3. Ajoute une **colonne auxiliaire** pour chaque partie de l'expression, en commençant par la plus intérieure (un NON sur une seule variable, puis les parenthèses). 4. Combine les colonnes auxiliaires pour obtenir la colonne finale. **Exemple :** $P \land \neg Q$ | $P$ | $Q$ | $\neg Q$ | $P \land \neg Q$ | |:---:|:---:|:---:|:---:| | V | V | F | F | | V | F | V | **V** | | F | V | F | F | | F | F | V | F | La colonne finale dit tout : cette expression est vraie dans une seule ligne, quand $P$ est vrai et $Q$ est faux. **Lire la colonne finale :** - Que des V : l'expression est une **tautologie** (toujours vraie). - Que des F : c'est une **contradiction** (toujours fausse). - Deux expressions qui ont **la même colonne finale à chaque ligne** sont **logiquement équivalentes**.

Une table à deux variables

Construis la table de vérité de $P \lor \neg Q$.

Compter les lignes: Il y a 2 variables, $P$ et $Q$, donc il faut $2^2 = 4$ lignes = 4 lignes

Remplir les colonnes des variables: $P$ : V, V, F, F (moitié V, moitié F). $Q$ : V, F, V, F (en alternance) = Les 4 combinaisons apparaissent une fois

Ajouter la colonne auxiliaire $\neg Q$: Inverse chaque valeur de $Q$ : V, F, V, F devient F, V, F, V = $\neg Q$ : F, V, F, V

Combiner avec OU: Ligne par ligne : V OU F = V, V OU V = V, F OU F = F, F OU V = V = $P \lor \neg Q$ : V, V, F, V

Answer: La colonne finale est V, V, F, V. L'expression n'est fausse qu'à la ligne 3, où $P$ est faux et $Q$ est vrai.

Préparer trois variables

Remplis les colonnes des variables d'une table de vérité pour $P$, $Q$ et $R$.

Compter les lignes: 3 variables, donc $2^3 = 2 \times 2 \times 2 = 8$ lignes = 8 lignes

Remplir la colonne $P$: La moitié de 8 est 4 : quatre V, puis quatre F = $P$ : V, V, V, V, F, F, F, F

Remplir la colonne $Q$: Changer deux fois plus souvent, par blocs de 2 = $Q$ : V, V, F, F, V, V, F, F

Remplir la colonne $R$: La dernière colonne alterne par blocs de 1 = $R$ : V, F, V, F, V, F, V, F

Answer: Les 8 lignes sont VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF. Chaque combinaison apparaît exactement une fois et aucune ne manque.

Une expression à trois variables

Construis la table de vérité de $(P \land Q) \lor \neg R$. Dans combien de lignes est-elle vraie ?

Préparer 8 lignes: Utilise l'ordre de l'exemple précédent : $P$ par blocs de 4, $Q$ par blocs de 2, $R$ en alternance = 8 lignes

Colonne auxiliaire $P \land Q$: ET n'est vrai que si $P$ et $Q$ sont vrais tous les deux : lignes 1 et 2 = $P \land Q$ : V, V, F, F, F, F, F, F

Colonne auxiliaire $\neg R$: Inverse $R$ : V, F, V, F, V, F, V, F devient F, V, F, V, F, V, F, V = $\neg R$ : F, V, F, V, F, V, F, V

Combiner avec OU: Une ligne est vraie si au moins une colonne auxiliaire vaut V : lignes 1, 2, 4, 6, 8 = Final : V, V, F, V, F, V, F, V

Compter les lignes vraies: Compte les V dans la colonne finale = 5 lignes

Answer: L'expression est vraie dans 5 des 8 lignes et fausse aux lignes 3, 5 et 7.

Tautologie, contradiction ou ni l'une ni l'autre ?

Classe $P \lor \neg P$, $P \land \neg P$ et $(P \land Q) \lor \neg P$.

Trouver $\neg P$: Avec une seule variable, il y a $2^1 = 2$ lignes. $P$ : V, F, donc $\neg P$ : F, V = $\neg P$ : F, V

Vérifier $P \lor \neg P$: V OU F = V et F OU V = V = Que des V : tautologie

Vérifier $P \land \neg P$: V ET F = F et F ET V = F = Que des F : contradiction

Vérifier $(P \land Q) \lor \neg P$: 4 lignes. $P \land Q$ : V, F, F, F. $\neg P$ : F, F, V, V. OU : V, F, V, V = Mélangé : ni l'une ni l'autre

Answer: $P \lor \neg P$ est une tautologie, $P \land \neg P$ est une contradiction, et $(P \land Q) \lor \neg P$ n'est ni l'une ni l'autre, car elle est fausse à la ligne 2.

Vérifier une équivalence (De Morgan)

$\neg(P \land Q)$ et $\neg P \lor \neg Q$ sont-elles équivalentes ? Et $\neg(P \land Q)$ et $\neg P \land \neg Q$ ?

Colonne finale de $\neg(P \land Q)$: $P \land Q$ : V, F, F, F. On l'inverse = F, V, V, V

Colonne finale de $\neg P \lor \neg Q$: $\neg P$ : F, F, V, V. $\neg Q$ : F, V, F, V. OU ligne par ligne = F, V, V, V

Comparer chaque ligne: F = F, V = V, V = V, V = V = Identiques dans les 4 lignes : équivalentes

Colonne finale de $\neg P \land \neg Q$: $\neg P$ : F, F, V, V ET $\neg Q$ : F, V, F, V = F, F, F, V : différente aux lignes 2 et 3

Answer: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ (l'une des lois de De Morgan). Mais $\neg(P \land Q)$ et $\neg P \land \neg Q$ ne sont pas équivalentes : une seule ligne différente suffit.

Une table de vérité est le moyen le plus sûr de vérifier un énoncé logique, car elle n'oublie aucun cas : - **Programmation** : avant de mettre en ligne une condition comme (membre OU coupon) ET NON bloqué, les testeurs vérifient chaque combinaison d'entrées - **Électronique** : les ingénieurs conçoivent des circuits avec des tables de vérité et remplacent un circuit compliqué par un circuit plus simple et moins cher qui fait la même chose - **Sécurité et alarmes** : une alarme à 4 capteurs a $2^4 = 16$ états possibles, et elle doit réagir correctement dans chacun d'eux - **Arguments et débats** : une table de vérité montre si deux phrases disent vraiment la même chose ou si elles se ressemblent seulement - **Énigmes et jeux** : on résout les énigmes logiques en éliminant les lignes qui ne peuvent pas être vraies Tu sais déjà comment fonctionnent ET, OU et NON séparément. Les tables de vérité te permettent de les combiner en n'importe quelle expression tout en restant sûr du résultat.

Mistake: Écrire trop peu de lignes, par exemple 6 lignes pour 3 variables

Why: Le nombre de lignes n'est pas $2 \times n$. Chaque variable double le nombre de combinaisons, donc 3 variables donnent $2 \times 2 \times 2 = 8$ lignes.

Correct: Utilise toujours $2^n$ lignes : 4 pour 2 variables, 8 pour 3 variables, 16 pour 4 variables.

Mistake: Remplir les colonnes des variables au hasard

Why: Sans méthode, on écrit facilement deux fois la même combinaison et on en oublie une autre. La table donne alors un verdict faux.

Correct: Suis le modèle fixe : première colonne par blocs de la moitié des lignes, chaque colonne suivante par blocs deux fois plus courts, dernière colonne en alternance V, F.

Mistake: Traiter $\neg P \land Q$ comme si c'était $\neg(P \land Q)$

Why: Sans parenthèses, NON ne porte que sur la variable qui le suit. La version avec parenthèses inverse le résultat de tout le ET.

Correct: Crée une colonne auxiliaire pour exactement ce sur quoi porte NON : $\neg P$ seul, ou d'abord $P \land Q$ puis sa négation.

Mistake: Dire que deux expressions sont équivalentes après avoir vérifié seulement quelques lignes

Why: Deux expressions peuvent coïncider sur plusieurs lignes et différer sur une seule. $\neg(P \land Q)$ et $\neg P \land \neg Q$ coïncident aux lignes 1 et 4 mais pas aux lignes 2 et 3.

Correct: Compare les colonnes finales à chaque ligne. Équivalentes veut dire identiques sur les $2^n$ lignes.

Systèmes d'alarme

Les ingénieurs en sécurité listent chaque état des capteurs pour s'assurer que l'alarme réagit correctement dans chaque cas.

Une alarme avec 3 capteurs de porte a $2^3 = 8$ états, de toutes les portes fermées à toutes les portes ouvertes.

Tester un logiciel

Les programmeurs testent une condition avec chaque combinaison d'entrées, ce qui est exactement une table de vérité.

Une règle de connexion (bon mot de passe ET NON bloqué) demande $2^2 = 4$ cas de test pour être entièrement vérifiée.

Simplifier des circuits

Si deux circuits ont la même table de vérité, les ingénieurs peuvent choisir celui qui a moins de composants ou des composants moins chers.

Les lois de De Morgan permettent de remplacer un NON-ET par un OU de deux NON sans changer ce que fait le circuit.

Une table de vérité énumère toutes les combinaisons de valeurs de vérité et la valeur de l'expression à chaque ligne

Avec $n$ variables, la table a $2^n$ lignes : 4 pour 2 variables, 8 pour 3 variables

Remplis les colonnes des variables dans un ordre fixe : d'abord des blocs de la moitié des lignes, la dernière colonne en alternance V, F

Utilise des colonnes auxiliaires pour chaque partie de l'expression, la plus intérieure d'abord

Que des V dans la colonne finale signifie une tautologie, que des F une contradiction

Deux expressions sont équivalentes quand leurs colonnes finales coïncident à chaque ligne

Q: Pourquoi chaque nouvelle variable double-t-elle le nombre de lignes ?

A: Chaque ligne existante peut être prolongée avec la nouvelle variable à V ou à F. Chaque ligne se divise donc en deux : 2 lignes deviennent 4, 4 deviennent 8, et ainsi de suite, ce qui donne $2^n$.

Q: L'ordre des lignes est-il important ?

A: N'importe quel ordre est correct tant que chaque combinaison apparaît exactement une fois. L'ordre standard (qui commence par tout V) rend la vérification et la comparaison des tables faciles. Certains livres commencent plutôt par F ; les lignes sont les mêmes, simplement dans l'ordre inverse. Les tables interactives de cette leçon suivent l'ordre standard.

Q: Comment s'appelle une expression qui n'est ni une tautologie ni une contradiction ?

A: On l'appelle une **contingence** : sa valeur dépend des entrées. La plupart des expressions courantes, comme $P \land Q$, sont des contingences.

Q: Ai-je toujours besoin de colonnes auxiliaires ?

A: Elles ne sont pas obligatoires, mais elles évitent la plupart des erreurs. Avec de l'entraînement, tu peux regrouper de petites étapes de tête, mais avec 3 variables ou des parenthèses dans des parenthèses, les colonnes auxiliaires restent la méthode la plus sûre.

Quitter la présentation

Tables de vérité

1 / 14

Logique & Ensembles / Logique booléenne

Tables de vérité

Apprends à construire étape par étape la table de vérité d'une expression composée et à l'utiliser pour trouver tautologies, contradictions et expressions équivalentes.

Intermédiaire25 min

Utilisez les touches fléchées ou la barre d'espace pour naviguer