septembre
2010
Un article de bredelet
Une valeur de vérité (booléen) peut prendre deux valeurs en logique, soit vrai soit faux. En fait la logique s’étend à des ensembles de valeurs plus grand mais on ne s’intéresse qu’à ces deux-là ici.
Dès lors, on peut considérer une valeur de vérité comme un ensemble de taille maximale un.
L’ensemble vide [] signifie faux et l’ensemble avec un élément [v] signifie vrai. Il est aisé de relier les opérations sur les ensembles aux opérations booléennes:
Union (conjonction OU)
quel que soit E: E union E = E
[] union [v] = [v]
[v] union [] = [v]
Table de vérité:
a b | a OU b _______|_____ 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1
Intersection (disjonction ET)
quel que soit E: E intersection E = E
[] intersection [v] = []
[v] intersection [] = []
Table de vérité:
a b | a ET b _______|_____ 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1
Complément (négation NON)
complément [] = [v]
complément [v] = []
Table de vérité:
a | NON a ___|_____ 0 | 1 1 | 0
Différence symétrique (disjonction exclusive XOR)
quel que soit E: E différence symétrique E = []
[] différence symétrique [v] = [v]
[v] différence symétrique [] = [v]
Table de vérité:
a b | a XOR b _______|_____ 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0
On voit que les relations sont les mêmes pour les valeurs ensemblistes [], [v] et les valeurs de vérité 0, 1.
Dans dodo, qualifier Logic apporte les opérations || (OU/union), && (ET/intersection), ! (NON/complément) et ^^ (XOR/différence symétrique). Il s’applique à la fois aux booléens, aux intervalles et aux ensembles.
Une représentation efficace d’un ensemble dont l’ensemble d’éléments possibles est limité est un entier. Chaque bit de l’entier correspond à un élément possible. Si le bit vaut 1 l’élément est présent mais s’il vaut 0 l’élément est absent.
Dans le cas du booléen considéré comme un ensemble décrit ci-dessus, l’ensemble des éléments possibles se limite à un seul: v. Il suffit donc d’un bit pour représenter le booléen.
En utilisant le bit le moins significatif, on obtient la représentation suivante:
[] = 0x0000 = 0
[v] = 0x0001 = 1
Si bien que faux vaut 0, et vrai vaut 1! Si vous êtes familier avec C ou un autre langage qui a repris la même convention cela ne devrait pas vous surprendre. De fait c’est une notation largement acceptée en logique.