Base De Données

Calcul Propositionnel 181

9 Table de v´erit´e

R´esum´e № 12 Pour pr´esenter l’´evaluation d’une formule φ dans ses

diff´erents mod`eles possibles, on utilise un tableau d´enomm´e table de

v´erit´e. Puisque l’´evaluation d’une formule passe par l’´evaluation de ses

sous-formules, chaque rang´ee de ce tableau correspond `a un mod`ele possible,

chaque colonne repr´esentant une sous-formule.

�

Pour discerner si deux formules sont ´equivalentes ou non, il faut en principe regarder tous

les mod`eles possibles de ces deux formules. Cela devient vite assez compliqu´e. La table de v´erit´e

est une r´eponse pratique `a ce probl`eme. Elle constitue une sorte de signature s´emantique de

la formule, parce qu’elle repr´esente tout simplement l’ensemble des informations sur tous les

mod`eles possibles de cette formule, informations dispos´ees de mani`ere astucieuse sous forme de

tableau.

Si l’on s’arrˆete quelques secondes sur l’´evaluation d’une formule dans un mod`ele, on s’aper¸coit

que pour ´evaluer correctement la formule il nous faut ´evaluer toutes ses sous-formules. En effet,

si l’on regarde la formule comme un arbre, on voit bien que pour trouver la valeur de v´erit´e

de la racine de cet arbre (et donc de la formule elle-mˆeme) il nous faut petit-`a-petit calculer

la valeur de v´erit´e pour chacun des noeuds de l’arbre, en commen¸cant par les feuilles (qui ne

comportent que des variables propositionnelles) et en remontant `a la racine. Si l’on se rappelle

qu’un noeud de l’arbre d´efinit une sous-formule (celle dont l’arbre est pr´ecis´ement le sous-arbre

dont ce noeud forme la racine) et r´eciproquement, on s’aper¸coit qu’´evaluer une formule revient

`a ´evaluer chacune de ses sous-formules.

Cela n´ecessite encore plus d’effort lorsqu’il s’agit de proc´eder `a l’´evaluation d’une formule

dans chacun des mod`eles possibles. En supposant que cette formule contienne n variable propositionnelle,

2n mod`eles doivent ˆetre consid´er´es et dans chacun d’eux toutes les sous-formules

doivent ˆetre ´evalu´ees.

La table de v´erit´e est simplement une mise `a disposition plus ou moins ´el´egante de ce processus

quelque peu r´ebarbatif. Au sens strict, lorsqu’on parle de la table de v´erit´e d’une formule,

il s’agit uniquement d’une pr´esentation des

...