Tables de vérité des opérateurs élémentaires

Le ET, le OU et le NON.

Tables de vérité de formules complexes

Définissons un nouvel opérateur, nommé op1 et défini par :

Construisons la table de vérité de cette formule. La technique à suivre est la suivante :

1. Construire une colonne pour chacune des variables (ici il y en a deux, a et b).

   a	b

2. Ajouter dans le tableau une ligne pour chaque toutes les valeurs possibles des variables. Dans le cas général où la formule contient n variables, il y aura 2ⁿ lignes. Nous avons donc maintenant 4 lignes dans notre tableau :

   a	b
   Faux	Faux
   Faux	Vrai
   Vrai	Faux
   Vrai	Vrai

3. On ajoute ensuite une colonne pour les sous-expressions de la formule, la dernière colonne correspondant à la formule complète. Cette fois, le nombre de colonnes est libre, fonction de la facilité que l'on a à évaluer des expressions complexes. Pour op1, on pourra par exemple avoir :

   a	b	NON a	NON b	a ET (NON b)	(NON a) ET b	op1(a,b)
   Faux	Faux
   Faux	Vrai
   Vrai	Faux
   Vrai	Vrai

4. Il reste à remplir chaque case, c'est-à-dire à établir la valeur de chacune des sous-expressions en fonction des colonnes précédentes (et en particulier des valeurs des variables). Nous obtenons finalement :

   a	b	NON a	NON b	a ET (NON b)	(NON a) ET b	op1(a,b)
   Faux	Faux	Vrai	Vrai	Faux	Faux	Faux
   Faux	Vrai	Vrai	Faux	Faux	Vrai	Vrai
   Vrai	Faux	Faux	Vrai	Vrai	Faux	Vrai
   Vrai	Vrai	Faux	Faux	Faux	Faux	Faux

En conclusion, la table de vérité de notre nouvel opérateur est :

Application : équivalence de deux formules

Considérons maintenant l'opération op2 définie par

et calculons, de la même manière que précédemment sa table de vérité :

Plus succintement,

Il apparaît que, quel que ce soit a et b, les résultats de op1 et op2 sont identiques et calcule un même opérateur que l'on peut identifier comme le OU-exclusif.

Le résultat du OU-exclusif sur deux nombres identiques est nécessairement un zéro.