Calcul d'Expressions Booléennes

Une expression booléenne/logique est une expression mathématique utilisant l'algèbre de Boole et qui utilise comme variables des valeurs booléennes (0 ou 1, vrai ou faux) et qui possède comme résultat/simplification des valeurs booléennes. L'expression peut contenir des opérateurs tels que la conjonction (ET), la disjonction (OU) et la négation (NOT).

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 une bonne vue d'ensemble des expressions.

dCode autorise plusieurs syntaxes :

Notation algébrique

Notation logique/informatique

Notation littérale

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

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

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

2 - Élément 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ées 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 \overline{AB} = \overline{a} + \overline{b} $$

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

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

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

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

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.