Table de vérité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Table (homonymie).

Une table de vérité est une table mathématique utilisée en logique — en particulier le calcul propositionnel classique et l'algèbre de Boole — pour représenter de manière sémantique des expressions logiques et calculer la valeur de leur fonction relativement à chacun de leurs arguments fonctionnels (chaque combinaison de valeur assumée par leurs variables logiques). Les tables de vérité peuvent être utilisées en particulier pour dire si une proposition est vraie pour toutes les valeurs légitimement imputées, c'est-à-dire : si une proposition est « logiquement valide ».

En pratique, une table de vérité est composée d'une colonne pour chaque variable imputée (A et B par exemple, ou p et q), et d'une colonne où sont inscrits tous les résultats possibles de l'opération logique représentée par le tableau (A XOR B par exemple). Chaque ligne de la table de vérité contient ainsi une des configurations possibles des variables imputées (par exemple : A=vrai, B=faux), ainsi que le résultat de l'opération pour ces valeurs.

Ces outils sont couramment utilisés en électronique (porte logique) et en informatique (tests) selon un code d'entrée binaire (0 / 1, faux / vrai, éteint / allumé, etc.). Une sortie, également représentée sous forme de colonne, est la résultante des états d'entrée, elle-même exprimée sous forme d'état binaire. En d'autres termes, lorsque les entrées remplissent les conditions du circuit, la (les) sortie est activée.

Entrées Sortie
États État

Lire une table de vérité[modifier | modifier le code]

Pour lire une table de vérité, on recherche dans la liste des entrées l'état souhaité pour en déterminer la sortie (qui se trouve donc sur la même ligne).

Exemple de base[modifier | modifier le code]

Dans les exemples suivants, nous découvrons la table de vérité pour certaine porte logique. Par exemple, pour que la sortie de la porte logique ET soit activée, nous devons avoir les deux entrées à 1. Alors que la porte logique OU n'a besoin que d'une des entrées pour afficher un 1 à la sortie.

Table de vérité de ET
a b a ET b
0 0 0
0 1 0
1 0 0
1 1 1
Table de vérité de OU
a b a OU b
0 0 0
0 1 1
1 0 1
1 1 1
Table de vérité de XOR (OU exclusif)
a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0
Table de vérité de l'implication
a b a ⇒ b
0 0 1
0 1 1
1 0 0
1 1 1

Exemple composé[modifier | modifier le code]

Table de vérité de a.(b + c)
a b c a.(b + c)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Le '.' se dit et, le '+' se lit ou.

On lit dans ce tableau: a et (b ou c)

Pour valider cette table, il faut donc que le a soit à l'état 1, ainsi que b ou c.

et et ou sont les opérateurs d'un état logique. On note les entrées "E" et les sorties "S".

Opérations unaires[modifier | modifier le code]

Il existe 4 opérations unaires (ne requérant qu'un seul argument ou opérande, ici « p ») : fausseté (F), vérité (V), identité (p) et négation (¬p).

Faux logique[modifier | modifier le code]

Faux logique
p F
V F
F F

Vrai logique[modifier | modifier le code]

Vrai logique
p V
V V
F V

Identité logique[modifier | modifier le code]

L'identité logique est une opération appliquée à un énoncé logique — typiquement une proposition (p) — afin d'en établir la valeur de vérité : vraie dans le cas où l'opérande est vrai, de fausse lorsqu'il est faux.

Identité logique
p p
V V
F F

Négation logique[modifier | modifier le code]

La négation logique est une opération qui inverse la valeur de l'opérande auquel elle est appliquée : il prend valeur de faux lorsqu'il est vrai, et de vrai lorsqu'il est faux. L'opérateur de la négation est symbolisé par les signes « ¬ » ou « ~ ».

Négation logique
p ¬p
V F
F V

Opérations binaires[modifier | modifier le code]

Une opération binaire est une opération à deux arguments (p et q par exemple), chacun pouvant être vrai ou faux (p {V, F} ; q {V, F}) : leur combinaison (p x q) donne ainsi 2² = 4 manières de combiner leur valeur de vérité.

p q   p   q
 
    V   V
  V   F
  F   V
    F   F


Chacune de ces 2² combinaisons d'entrée ayant elles-mêmes deux résultats possibles (« [{V, F} x {V, F}] → {V,F} »), on obtient ainsi 4² = 16 fonctions de vérité, qui forment les 16 colonnes de la table de vérité suivante :

P Q       ¬(←)  ¬p  ¬(→)  ¬q   w           q p v T
V V F F F F F F F F V V V V V V V V
V F F F F F V V V V F F F F V V V V
F V F F V V F F V V F F V V F F V V
F F F V F V F V F V F V F V F V F V

Où V = vrai et F = Faux.

Conjonction logique (ET)[modifier | modifier le code]

Article détaillé : Conjonction logique.

Une conjonction logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si ses deux opérandes sont vrais. La table de vérité pour p et q (aussi noté p ∧ q, Kpq, ou p & q) est la suivante:

Conjonction logique
p q pq
1 1 1
1 0 0
0 1 0
0 0 0

Nous pouvons aussi dire que, si p, p ∧ q est q, sinon p ∧ q est égal à p.

Disjonction logique (OU)[modifier | modifier le code]

Article détaillé : disjonction logique.

Une disjonction logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si au moins un des opérandes est vrai.

La table de vérité pour p OU q (aussi noté p ∨ q, Apq, p || q ou p + q) est la suivante :

Disjonction logique
p q pq
1 1 1
1 0 1
0 1 1
0 0 0

Implication logique[modifier | modifier le code]

Article détaillé : Implication (logique).

Une implication logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur fausse seulement dans le cas où le premier opérande est vrai, et le second est faux. La table de vérité associée à l'implication si p alors q (aussi noté p → q) et l'implication logique p implique q (aussi noté p ⇒ q, ou encore Cpq) est la suivante :

Implication logique
p q pq
1 1 1
1 0 0
0 1 1
0 0 1

Il peut également être noté p → q qui équivaut à ¬p ∨ q.

Équivalence logique[modifier | modifier le code]

Article détaillé : Équivalence logique.

Une équivalence logique (également connu sous le nom de biconditionelle) est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si les deux opérandes sont faux ou vrais. La table de vérité pour p XNOR q (écrit aussi p ↔ q, Epq, p = q, ou p ≡ q) est la suivante:

Équivalence logique
p q pq
1 1 1
1 0 0
0 1 0
0 0 1

Disjonction exclusive[modifier | modifier le code]

Article détaillé : Fonction OU exclusif.

Une disjonction exclusive est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si une des deux des opérandes est une valeur vraie. La table de vérité pour p XOR q (aussi noté p ⊕ q, Jpq, ou p ≠ q) est la suivante:

Disjonction exclusive
p q pq
1 1 0
1 0 1
0 1 1
0 0 0

Pour deux propositions, XOR peut également être noté (p ∧ ¬q) ∨ (¬p ∧ q).

NON-ET logique[modifier | modifier le code]

Article détaillé : Fonction NON-ET.

Le NON-ET est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur fausse si les deux opérandes sont vrais. En d'autres termes, il produit une valeur vraie si au moins un de ses opérandes est faux. La table de vérité de p NAND q (aussi noté p ↑ q, Dpq, ou p | q) est la suivante :

NON-ET logique
p q pq
1 1 0
1 0 1
0 1 1
0 0 1

Il est souvent utile d'exprimer une opération logique comme une opération composée, qui est, construite ou composé d'autres opérations logiques. Beaucoup de ces compositions sont possibles, et dépendent des opérations qui sont prises comme base, et les opérations qui sont prises en composite.

La négation d'une conjonction: ¬(p ∧ q), et de la disjonction de négations: (¬p) ∨ (¬q) peuvent être 'totalisées' comme suit:

p q p ∧ q ¬(p ∧ q) ¬p ¬q p) ∨ (¬q)
1 1 1 0 0 0 0
1 0 0 1 0 1 1
0 1 0 1 1 0 1
0 0 0 1 1 1 1

NON-OU logique[modifier | modifier le code]

Article détaillé : Fonction NON-OU.

Le NON-OU logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si ses deux opérandes sont fausses. En d'autres termes, il produit une valeur fausse, si au moins l'un de ses opérandes est vrai. ↓ est également connu sous le nom de la flêche de Peirce, nom provenant de son inventeur, Charles Sanders Peirce.

La table de vérité de p NOR q (aussi noté p ↓ q, Xpq, ou ¬(p ∨ q)) est la suivante:

NON-OU logique
p q pq
1 1 0
1 0 0
0 1 0
0 0 1

La négation d'une disjonction ¬(p ∨ q), et la conjonction de négations (¬p) ∧ (¬q) peuvent être décomposés sous forme de tableau comme suit:

p q p ∨ q ¬(p ∨ q) ¬p ¬q p) ∧ (¬q)
1 1 1 0 0 0 0
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 0 1 1 1 1

Les première et les seconde expressions de chaque paire sont logiquement équivalents, et peuvent être substitués les uns les autres dans tout contextes qui se rapportent uniquement à leurs valeurs logiques.

Cette équivalence est l'une des lois de De Morgan.

Application[modifier | modifier le code]

Les tables de vérité peuvent être utilisés pour prouver beaucoup d'autres équivalences logique. Par exemple, considérons la table de vérité suivante:

Équivalence logique : (pq) = (¬pq)
p q ¬p ¬pq pq
1 1 0 1 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1

Ceci démontre que p → q est logiquement équivalent à ¬p ∨ q.

Table de vérité pour les opérateurs logiques les plus couramment utilisés[modifier | modifier le code]

Voici une table de vérité donnant la définition des 6 fonctions de vérité les plus couramment utilisée des 16 possibles de 2 variables binaires (P, Q sont ainsi des variables booléennes)[1] :

1 1 1 1 0 1 1 1 1
1 0 0 1 1 0 0 1 0
0 1 0 1 1 0 1 0 0
0 0 0 0 0 1 1 1 1

Légende :

1 = vrai, 0 = faux
= ET (conjonction logique)
= OU (disjonction logique)
= XOR (fonction OU exclusif)
= XNOR (fonction NON-OU exclusif)
= Implication "si - alors"
= Implication "(alors) - si"
biconditionel "si et seulement si" est équivalent logiquement à .

Les opérateurs logiques peuvent également être représentés à l'aide de diagrammes de Venn.

Tables de vérité condensés pour des opérateurs binaires[modifier | modifier le code]

Pour les opérateurs binaires, une forme condensée de table de vérité est également utilisé, où les en-têtes de colonnes et de lignes spécifient les opérandes, et les cellules du tableau précise le résultat. Par exemple, la logique booléenne utilise cette notation :

0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1

Cette notation est particulièrement utile si les opérations sont commutatives. Sa forme est rapidement reconnaissable de la distribution des valeurs dans le tableau, qui peut aider le lecteur à saisir les règles plus rapidement.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. « Tractatus logico-philosophicus », Wikipédia,‎ (lire en ligne)

Articles connexes[modifier | modifier le code]