Ici, les variables que l’on est autorisé à manipuler ne prennent que deux valeurs : Vrai ou Faux. Ce sont des variables booléennes. Ainsi, si x est une telle variable, soit x a pour valeur Vrai (x = Vrai), soit x a pour valeur Faux (x = Faux). Pour élémentaires et restreintes qu’elles soient, ces valeurs permettent tout de même de faire des calculs. Pour cela, on définit des opérations, un peu comme l’addition ou l’inverse pour les nombres ordinaires (non nuls).
Qui fait non, non, non…
La première opération est la négation : si x est une variable ayant une certaine valeur booléenne, alors ¬ x vaut le « contraire » de x, au sens où ¬Vrai = Faux et ¬Faux = Vrai. L’opérateur ¬ se prononce « Non » (donc Non(Vrai) = Faux, ce qui paraît logique !).
Pour définir notre seconde opération, il convient de simplifier un peu le formalisme standard. Une 3-clause est un triplet composé de variables ou de négations de variables. Les variables composant une 3-clause doivent être distinctes, mais l’ordre dans le triplet n’a aucune importance. Voici quelques exemples de 3-clauses avec les variables booléennes x, y, z et t :
(x, y, t),
(z, ¬ x, ¬ t),
(¬ y, ¬ x, ¬ t),
( ¬ z, ¬ t, ...
Lire la suite