📝 Mini-cours GRATUIT

Je m’inscris pour accéder gratuitement à ce contenu

Algèbre de Boole 1

Définition

La valeur de vérité d'une formule dépend des variables. Si elle est toujours vraie c'est une tautologie. Une formule propositionnelle

$P$ qui n'est pas une simple variable peut toujours se décomposer en l'un des cas suivants : - En une formule

$P'$ telle que

$P=\neg P'$ , dans ce cas la formule P est vraie si et seulement si P' est fausse. - En deux sous-formules

$Q$ et

$Q'$ telle que

$P$ s'écrive

$Q \wedge Q'$ ou

$Q \vee Q'$ . Dans le premier cas

$P$ est vraie si les deux autres sont vraies, dans le deuxième cas

$P$ est vraie si au moins une des deux autres est vraie. L'implication peut aussi être transformée en disjonction (ou). Pour les quantificateurs, une formule

$\forall a, P(a)$ est vraie si et seulement P(a) est vraie pour toute valeur de a. Propriétés Pour

$P$ et

$Q$ deux formules propositionnelles :

$(P\rightarrow Q)$ est équivalent à

$(Q\vee \neg P)$ .

$\neg \forall a, P(a)$ est équivalent à

$\exists a, P(a)$ .

$\neg \exists a, \forall b, P(a,b)$ est équivalent à

$\forall a, \exists b, P(a,b)$ .

$\neg (A \vee B)$ est équivalent à

$\neg A \wedge \neg B$ et

$\neg (A \wedge B)$ est équivalent à

$\neg A \vee \neg B$ (lois de De Morgan)

Algèbre de Boole 2

On peut représenter vrai et faux par 0 et 1. Dans ce cas ET est noté * et OU est noté +.

La négation est notée par une barre au dessus. A ou (B et NON C) est donc noté $a+b\overline {c}$ Le XOR ou OUX (ou exclusif) vaut 1 quand une seule des deux variables vaut 1 (ou VRAI).

Le NAN vaut 0 uniquement quand les deux variables valent 1 (donc quand elles sont toutes les deux vraies).

Une table de Karnaugh est une variante de la table de vérité et fonctionne de manière similaire à ceci près que les valeurs suivent généralement un code de Gray.