Calcul d'Expressions Booléennes

La simplification d'équations booléennes peut utiliser différentes méthodes : outre les classiques développement via associativité, commutativité, distributivité, etc. Les tables de vérité ou les diagrammes de Venn permettent un bonne vue d'ensemble des expressions.

Exemple : Expression originale (LaTeX) $$ \overline{a \land b \land (c \lor \bar{d})} \lor \bar{b} $$

dCode autorise plusieurs syntaxes :

Notation algébrique

Exemple : !(ab(c+!d))+!b avec multiplication implicite ab = a ET b et ! (exclamation) pour la barre : le NON logique.

Notation logique/informatique

Exemple : !(a&&b&&(c||!d))||!b, le double caractère & (esperluette) pour ET et le double caractère | (barre verticale, pipe) pour OU logique.

Notation littérale

Exemple : NOT( a AND b AND ( c OR NOT d) ) OR NOT b

Il peut y avoir plusieurs représentations minimales pour une même expression, dCode fourni une solution.

Certaines notations sont ambigues, éviter la notation fonctionnelle 'XOR(a,b)' pour écrire a XOR b, éviter aussi l'apostrophe suffixé a' et préférer !a.

L'algèbre booléenne a de nombreuses propriétés (lois booléennes) :

1 - Elément neutre : $ 0 $ est neutre pour OU logique alors que $ 1 $ est neutre pour ET logique

$$ a + 0 = a \\ a.1 = a $$

2 - Element absorbant : $ 1 $ est absorbant pour OU logique alors que $ 0 $ est absorbant pour ET logique

$$ a + 1 = 1 \\ a.0 = 0 $$

3 - Idempotence : l'application de plusieurs fois la même opération ne modifie pas la valeur

$$ a + a = a + a + \cdots + a = a \\ a . a = a . a . \cdots . a = a $$

4 - Involution ou double complémentarité : l'opposé de l'opposé de $ a $ est $ a $

$$ a = \overline{\overline{a}} = !(!a) $$

5 - Complémentarité par Contradiction : $ a $ ET $ \text{non}(a) $ est impossible, donc est faux et vaut $ 0 $

$$ a . \overline{a} = 0 $$

6 - Complémentarité par Tiers exclus : $ a $ OU $ \text{non}(a) $ est toujours vrai, donc vaut $ 1 $

$$ a + \overline{a} = 1 $$

7 - Loi d'Associativité : les parenthèses sont inutiles entre opérations identiques

$$ a.(b.c) = (a.b).c = a.b.c \\ a+(b+c) = (a+b)+c = a+b+c $$

8 - Loi de Commutativité : l'ordre n'a pas d'importance

$$ a.b = b.a \\ a+b = b+a $$

9 - Loi de Distributivité : ET se distribue sur OU mais aussi OU se distribue sur ET

$$ a.(b+c) = a.b + a.c \\ a+(b.c) = (a+b).(a+c) $$

10 - Lois de De Morgan (voir plus de détails ci-après)

$$ \overline{a+b} = \overline{a}.\overline{b} \\ \overline{a.b} = \overline{a}+\overline{b} $$

11 - Autres simplifications par combinaisons de celles ci-dessus

$$ a.(a+b) = a \\ a+(a.b) = a \\ (a.b) + (a.!b) = a \\ (a+b).(a+!b) = a \\ a + (!a.b) = a + b \\ a.(!a + b) = a.b \\ a.b + \overline{a}.c = a.b + \overline{a}.c + b.c $$

Méthode 1 : en les simplifiant jusqu'à obtenir la même écriture en algèbre booléenne.

Méthode 2 : en calculant leur table de vérité qui seront identiques.

Les lois de De Morgan sont souvent utilisée pour réécrire des expressions logiques. Elles sont généralement énoncées : non(a et b) = (non a) ou (non b) et non(a ou b) = (non a) et (non b). Voici les écritures logiques équivalentes :

$$ \overline{(a \land b)} \leftrightarrow (\overline{a})\lor (\overline{b}) \iff \bar{AB} = \bar{a} + \bar{b} $$

$$ \overline{(a \lor b)} \leftrightarrow (\overline{a}) \land (\overline{b}) \iff \bar{a+b} = \bar{a} * \bar{b} $$

La logique utilise différents formats pour assurer une meilleur lisibilité ou utilisabilité.

La forme normale disjonctive (FND) utilise une somme de produits (SOP) :

Exemple : (a.c)+b

La forme normale conjonctive (FNC) ou forme clausale utilise un produit de sommes (POS) :

Exemple : (a.c)+b

Les étapes de calcul telles qu'un humain les imagine n'existent pas pour le solveur. Les opérations effectuées sont binaires bit à bit et ne correspondent pas à celles réalisées lors d'une résolution à la main.