Le hasard au secours de la satisfaction


Christian Laforest

L'univers booléen est un petit monde mathématiques où deux valeurs seulement existent : Vrai et Faux. Pourtant, il est déjà compliqué d'obtenir satisfaction ! Heureusement, le hasard vient à notre secours : parfois, en choisissant à pile ou face, on tombe étonnamment près d'un maximum recherché.


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 ... Lire la suite


références

 Les algorithmes en ligne. Christian Laforest, Tangente 176, 2017.
 Hasard et probabilités. Bibliothèque Tangente 17, 2004.