Algèbre de Boole

Deux assertions composées $A$ et $B$ sont logiquement équivalentes si elles ont la même valeur de vérité pour chaque choix des valeurs de vérité des lettres $P$, $Q$, $R$… qui y figurent ; on note $A \equiv B$. On note $\mathrm{V}$ une assertion toujours vraie et $\mathrm{F}$ une assertion toujours fausse. Écrire $A \equiv B$ n'affirme ni $A$ ni $B$ : cela affirme seulement qu'elles sont vraies ou fausses en même temps. Une table de vérité établit une telle équivalence en examinant tous les cas ; l'algèbre de Boole l'établit par le calcul, à partir d'équivalences de référence appelées lois.

Substitution : une loi reste vraie quand on remplace chacune de ses lettres par une assertion quelconque, la même à chaque occurrence ; ainsi la loi $\lnot(P \land Q) \equiv \lnot P \lor \lnot Q$, avec $\lnot R$ à la place de $P$, donne $\lnot(\lnot R \land Q) \equiv \lnot\lnot R \lor \lnot Q$. Remplacement : si $A \equiv B$, remplacer dans une assertion une partie écrite $A$ par $B$ donne une assertion équivalente. Symétrie : si $A \equiv B$, alors $B \equiv A$ ; c'est elle qui permet de lire une loi de droite à gauche, par exemple pour factoriser. Transitivité : si $A \equiv B$ et $B \equiv C$, alors $A \equiv C$. Ces règles garantissent qu'une chaîne de lignes reliées par $\equiv$, chacune obtenue par une loi, prouve l'équivalence de la première et de la dernière, et qu'on peut conclure $A \equiv B$ après avoir ramené $A$ et $B$ à une même forme $C$.

Pour toutes assertions $P$, $Q$, $R$ : $P \land Q \equiv Q \land P$ et $P \lor Q \equiv Q \lor P$ (commutativité) ; $(P \land Q) \land R \equiv P \land (Q \land R)$ et $(P \lor Q) \lor R \equiv P \lor (Q \lor R)$ (associativité). On écrit donc $P \land Q \land R$ sans parenthèses, et on range les termes dans l'ordre voulu, tant qu'un seul connecteur intervient. Grâce à la commutativité, les lois qui suivent valent aussi avec les termes dans l'autre ordre, sans qu'on le signale à chaque ligne. Dès que les deux connecteurs se mélangent, les parenthèses comptent : si $P$ est fausse et $R$ vraie, $(P \land Q) \lor R$ est vraie alors que $P \land (Q \lor R)$ est fausse.

Pour toutes assertions $P$, $Q$, $R$, le connecteur « et » est distributif sur « ou », et « ou » est distributif sur « et » :
$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$
$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
Lue de gauche à droite, une distributivité développe ; lue de droite à gauche, elle factorise. Contrairement aux réels, où $1 + 2 \times 3 = 7$ diffère de $(1 + 2) \times (1 + 3) = 12$, la seconde distributivité est vraie ici. Idée de preuve de la seconde, par cas : si $P$ est vraie, les deux membres sont vrais ; si $P$ est fausse, les deux ont la valeur de $Q \land R$.

Pour toutes assertions $P$ et $Q$ :
$\lnot(P \land Q) \equiv \lnot P \lor \lnot Q$
$\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$
La négation traverse la parenthèse, s'applique à chaque terme et échange « et » et « ou ». Justification sans table : « $P$ et $Q$ » est fausse exactement quand l'une au moins des deux est fausse, et « $P$ ou $Q$ » est fausse exactement quand les deux le sont. Par associativité et récurrence sur le nombre de termes, les lois s'étendent à un nombre quelconque de termes, et la double négation $\lnot\lnot P \equiv P$ règle le sort des termes déjà niés.

Pour toute assertion $P$ : $P \land \mathrm{V} \equiv P$ et $P \lor \mathrm{F} \equiv P$, donc $\mathrm{V}$ est neutre pour « et » et $\mathrm{F}$ pour « ou » ; $P \land \mathrm{F} \equiv \mathrm{F}$ et $P \lor \mathrm{V} \equiv \mathrm{V}$, donc $\mathrm{F}$ est absorbant pour « et » et $\mathrm{V}$ pour « ou ». Les lois de complémentarité traduisent la non-contradiction et le tiers exclu : $P \land \lnot P \equiv \mathrm{F}$ et $P \lor \lnot P \equiv \mathrm{V}$. Dans un calcul, ce sont elles qui font disparaître une lettre : on cherche à faire apparaître $Q \land \lnot Q$ ou $Q \lor \lnot Q$.

Pour toutes assertions $P$ et $Q$ : $P \land P \equiv P$ et $P \lor P \equiv P$ (idempotence) ; $P \land (P \lor Q) \equiv P$ et $P \lor (P \land Q) \equiv P$ (absorption). L'absorption découle des lois précédentes : $P \lor (P \land Q) \equiv (P \land \mathrm{V}) \lor (P \land Q) \equiv P \land (\mathrm{V} \lor Q) \equiv P \land \mathrm{V} \equiv P$, par neutre, factorisation, absorbant puis neutre. On ne confond pas l'élément absorbant, une constante qui l'emporte sur tout, avec la loi d'absorption, où un terme fait disparaître un autre terme qui le contient. Une conséquence sert souvent, et se démontre par la seconde distributivité : $P \lor (\lnot P \land Q) \equiv P \lor Q$.

Sur $\{0, 1\}$, on définit la somme $a + b = \max(a, b)$, le produit $ab = \min(a, b)$ et le complément $\overline{a} = 1 - a$, différence calculée dans les entiers. Ainsi $0 + 0 = 0$ et $0 + 1 = 1 + 0 = 1 + 1 = 1$ ; $ab = 1$ seulement si $a = b = 1$ ; $\overline{0} = 1$ et $\overline{1} = 0$. Priorités : le complément avant le produit, le produit avant la somme, donc $a + \overline{b}c$ se lit $a + (\overline{b}\,c)$, et une barre posée sur un groupe, comme dans $\overline{ab}$, joue le rôle de parenthèses. Le produit coïncide avec celui des entiers, mais pas la somme : ici $1 + 1$ vaut $1$, ni $2$ ni $0$.

On associe à une assertion $P$ sa valeur $p \in \{0, 1\}$, égale à $1$ si $P$ est vraie et à $0$ sinon. Alors $\lnot P$, $P \land Q$ et $P \lor Q$ ont pour valeurs $\overline{p}$, $pq$ et $p + q$, tandis que $\mathrm{V}$ et $\mathrm{F}$ ont pour valeurs $1$ et $0$. Deux assertions sont logiquement équivalentes si et seulement si leurs expressions sont égales pour toutes les valeurs des lettres dans $\{0, 1\}$ : chaque loi a donc sa version numérique, comme $\overline{p + q} = \overline{p}\,\overline{q}$ ou $p + qr = (p + q)(p + r)$. Un calcul se mène indifféremment dans l'une ou l'autre écriture.

Le ou exclusif de $P$ et $Q$, noté $P \oplus Q$, est vrai quand exactement une des deux assertions est vraie : $P \oplus Q \equiv (P \land \lnot Q) \lor (\lnot P \land Q)$. Il ne diffère du « ou » inclusif des mathématiques que dans un cas : $P$ et $Q$ toutes deux vraies. Sur $\{0, 1\}$, $a \oplus b = a\overline{b} + \overline{a}b$ vaut $1$ si $a \neq b$ et $0$ si $a = b$ ; en particulier $1 \oplus 1 = 0$. C'est l'addition modulo 2 : $a \oplus b$ est le reste de la division par $2$ de la somme ordinaire des entiers $a$ et $b$, somme qui vaut $0$, $1$ ou $2$.

Pour tous $a, b, c \in \{0, 1\}$ : $\oplus$ est commutatif et associatif, puisque les deux parenthésages de $a \oplus b \oplus c$ donnent le reste de la division par $2$ de la somme ordinaire des trois entiers ; $0$ est neutre et $a \oplus a = 0$. De plus $1 \oplus a = \overline{a}$, et le produit est distributif sur $\oplus$ : $a(b \oplus c) = ab \oplus ac$. Enfin $a + b = a \oplus b \oplus ab$, ce qui ramène tout calcul booléen à l'arithmétique modulo 2, où $aa = a$. En revanche, la somme n'est pas distributive sur $\oplus$ : pour $a = b = c = 1$, $a + (b \oplus c) = 1$ alors que $(a + b) \oplus (a + c) = 1 \oplus 1 = 0$.

Une conjonction est une assertion de la forme « $P$ et $Q$ », une disjonction une assertion de la forme « $P$ ou $Q$ ». Développer, c'est appliquer une distributivité de gauche à droite ; factoriser, l'appliquer de droite à gauche ; simplifier ou réduire, c'est obtenir une assertion équivalente où les lettres apparaissent moins souvent. On cite une loi par son nom : commutativité, associativité, distributivité de « et » sur « ou » (ou de « ou » sur « et »), lois de De Morgan, double négation, élément neutre, élément absorbant, complémentarité, idempotence, absorption. Pour citer une loi dans une phrase, on écrit « par la loi de De Morgan » ou « d'après l'absorption » ; or introduit une loi ou un fait qu'on va utiliser, et de même annonce le même calcul sur un autre terme. Entre deux lignes d'un calcul on écrit $\equiv$, ou $=$ sur $\{0, 1\}$, et le mot donc n'arrive qu'à la conclusion, pour affirmer l'équivalence obtenue.

Pour toutes assertions $P$, $Q$, $R$ et tous $a, b, c \in \{0, 1\}$ :

Les quatre lignes couvrent toutes les valeurs du couple $(a, b)$ :

Les colonnes $a + b$ et $a \oplus b$ ne diffèrent que sur la dernière ligne : c'est tout l'écart entre le ou inclusif et le ou exclusif.

Signal : l'énoncé demande de simplifier, de réduire ou d'écrire une assertion « sous une forme plus simple », sans imposer de table.
1) Poser les objets : « Soient $P$ et $Q$ des assertions. » (ou « Soient $a, b \in \{0, 1\}$. »).
2) Repérer la structure : quel connecteur est le plus extérieur, quelles négations portent sur une parenthèse.
3) Réduire d'abord ce qui se réduit à l'intérieur des parenthèses ; faire ensuite entrer les négations par De Morgan jusqu'aux lettres, en effaçant les doubles négations.
4) Chercher ce qui fait disparaître des termes : une lettre et sa négation dans un même groupe (complémentarité), un terme répété (idempotence), un terme qui en contient un autre (absorption), un terme commun (factorisation par l'une ou l'autre distributivité). Puis regarder chaque terme où manque une lettre présente ailleurs, car il est peut-être superflu : on y fait entrer la lettre en écrivant $T \equiv T \land (R \lor \lnot R)$ (sur $\{0, 1\}$ : $t = t(a + \overline{a})$), on développe, puis on regarde si chaque morceau est absorbé par un terme plus court (règle du consensus).
5) Écrire une loi par ligne, sous la forme « $\equiv$ nouvelle expression (nom de la loi) ». Si on l'applique à plusieurs termes à la fois, le dire (« dans chaque terme ») ; une commutativité ou une associativité qui l'accompagne se cite sur la même ligne.
6) Conclure par une phrase : « Donc [expression de départ] $\equiv$ [expression finale]. »
7) Contrôler au brouillon sur deux valuations, l'une qui rend le résultat vrai, l'autre qui le rend faux (s'il n'est pas constant) : un seul contrôle où tout vaut vrai ne détecte pas un résultat trop large.
Une étape peut allonger provisoirement l'expression (seconde distributivité, lettre qu'on fait entrer) quand elle prépare une complémentarité ou une absorption. On s'arrête quand aucune loi ne réduit plus l'expression, même après avoir fait entrer les lettres manquantes ; la forme obtenue n'est pas toujours la plus courte possible.

Simplifier l'assertion $\lnot(P \lor (\lnot P \land Q))$ en justifiant chaque étape par la loi utilisée.
Soient $P$ et $Q$ des assertions. On réduit d'abord la disjonction placée sous la négation.
$P \lor (\lnot P \land Q) \equiv (P \lor \lnot P) \land (P \lor Q)$ (distributivité de « ou » sur « et »)
$\equiv \mathrm{V} \land (P \lor Q)$ (complémentarité : $P \lor \lnot P \equiv \mathrm{V}$)
$\equiv P \lor Q$ ($\mathrm{V}$ neutre pour « et »).
Par remplacement, $\lnot(P \lor (\lnot P \land Q)) \equiv \lnot(P \lor Q)$.
Or $\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$ (loi de De Morgan).
Donc $\lnot(P \lor (\lnot P \land Q)) \equiv \lnot P \land \lnot Q$ : l'assertion est vraie exactement quand $P$ et $Q$ sont toutes deux fausses.
Contrôle : pour $P$ fausse et $Q$ vraie, $\lnot P \land Q$ est vraie, donc $P \lor (\lnot P \land Q)$ est vraie et sa négation est fausse, comme $\lnot P \land \lnot Q$.
À retenir : une ligne, une loi nommée entre parenthèses ; on réduit l'intérieur avant de faire entrer la négation.

Signal : on doit écrire le contraire d'une assertion qui contient « et », « ou », « à la fois », « l'un au moins », ou un encadrement comme $a \leq x \leq b$, qui cache une conjonction.
1) Expliciter la structure en écrivant les parenthèses et les connecteurs cachés : « $0 \leq x \leq 1$ » s'écrit « $0 \leq x$ et $x \leq 1$ ».
2) Nier le connecteur le plus extérieur par De Morgan : « et » devient « ou », « ou » devient « et », et la négation passe sur chaque terme.
3) Recommencer sur chaque terme jusqu'à n'avoir que des négations d'assertions simples, puis les écrire positivement : non($x \leq 1$) s'écrit $x > 1$, et non(non $P$) s'écrit $P$.
4) Conserver les parenthèses : la négation de « $A$ ou ($B$ et $C$) » est « non $A$ et (non $B$ ou non $C$) ».
5) Contrôler sur une valeur : l'assertion et sa négation doivent toujours avoir des valeurs de vérité opposées.
Sur la copie : « Par les lois de De Morgan, la négation de [assertion] est [négation]. »

Soit $x$ un réel. Écrire, sous la forme la plus simple, la négation de l'assertion $A$ : « $0 \leq x \leq 1$ ou $x \geq 2$ ».
L'assertion $A$ s'écrit « ($0 \leq x$ et $x \leq 1$) ou $x \geq 2$ ».
Par la loi de De Morgan pour « ou », non $A$ équivaut à « non($0 \leq x$ et $x \leq 1$) et non($x \geq 2$) ».
Par la loi de De Morgan pour « et », non($0 \leq x$ et $x \leq 1$) équivaut à « non($0 \leq x$) ou non($x \leq 1$) », c'est-à-dire à « $x < 0$ ou $x > 1$ ».
Comme non($x \geq 2$) s'écrit $x < 2$, non $A$ équivaut à « ($x < 0$ ou $x > 1$) et $x < 2$ ».
Par distributivité de « et » sur « ou », non $A$ équivaut à « ($x < 0$ et $x < 2$) ou ($x > 1$ et $x < 2$) ».
Or $x < 0$ entraîne $x < 2$, donc « $x < 0$ et $x < 2$ » équivaut à « $x < 0$ » ; de plus, « $x > 1$ et $x < 2$ » s'écrit $1 < x < 2$.
Donc la négation de $A$ est : « $x < 0$ ou $1 < x < 2$ ».
Contrôle : pour $x = 1{,}5$, $A$ est fausse et sa négation vraie ; pour $x = 3$, $A$ est vraie et sa négation fausse.
À retenir : on explicite le « et » caché dans l'encadrement avant de nier, puis chaque loi de De Morgan échange le connecteur et nie tous les termes.

Signal : « montrer que $A \equiv B$ », « montrer que $A$ et $B$ sont équivalentes » ou une égalité à établir pour tous $a, b, c \in \{0, 1\}$, avec la consigne « sans table » ou trop de lettres pour qu'une table soit commode.
1) Introduire les objets : « Soient $P$, $Q$, $R$ des assertions. »
2) Partir du membre le plus compliqué et viser l'autre ; si aucun ne se ramène à l'autre, transformer les deux vers une même forme $C$, puis écrire : « D'une part $A \equiv C$, d'autre part $B \equiv C$ ; donc $A \equiv B$. » (symétrie et transitivité).
3) Écrire la chaîne « $A \equiv A_1$ (loi) », puis « $\equiv A_2$ (loi) », jusqu'à $B$, une loi par ligne.
4) Si l'on bloque : factoriser par la seconde distributivité ; faire apparaître $Q \lor \lnot Q$ ou $Q \land \lnot Q$ ; faire entrer une lettre $R$ qui manque en écrivant $A \equiv A \land (R \lor \lnot R)$, puis développer pour rendre une absorption possible.
5) Conclure : « Donc, pour toutes assertions $P$, $Q$, $R$, on a $A \equiv B$. »
Une table peut servir de contrôle au brouillon, mais la preuve demandée est la chaîne de lois. Les lignes se relient par $\equiv$, jamais par « donc » ni par une flèche : chaque ligne équivaut à la précédente, aucune n'est affirmée vraie.

Démontrer par le calcul, sans table, que pour toutes assertions $P$ et $Q$, $(P \lor Q) \land (P \lor \lnot Q) \equiv P$.
Soient $P$ et $Q$ des assertions. On part du membre de gauche.
$(P \lor Q) \land (P \lor \lnot Q) \equiv P \lor (Q \land \lnot Q)$ (distributivité de « ou » sur « et », lue de droite à gauche : on factorise $P$)
$\equiv P \lor \mathrm{F}$ (complémentarité : $Q \land \lnot Q \equiv \mathrm{F}$)
$\equiv P$ ($\mathrm{F}$ neutre pour « ou »).
Donc, pour toutes assertions $P$ et $Q$, $(P \lor Q) \land (P \lor \lnot Q) \equiv P$.
Autrement dit, la valeur de $Q$ n'intervient pas : « $P$ ou $Q$ » et « $P$ ou non $Q$ » sont vraies ensemble exactement quand $P$ l'est.
À retenir : devant deux disjonctions qui partagent un terme, on factorise par la seconde distributivité au lieu de tout développer.

Démontrer par le calcul que pour tous $a, b, c \in \{0, 1\}$, $ab + \overline{a}c + bc = ab + \overline{a}c$.
Soient $a$, $b$, $c$ des éléments de $\{0, 1\}$. Le terme $bc$ ne contient pas $a$ : on l'y fait apparaître.
$bc = bc \cdot 1$ ($1$ neutre pour le produit)
$= bc(a + \overline{a})$ (complémentarité : $a + \overline{a} = 1$)
$= abc + \overline{a}bc$ (distributivité du produit sur la somme, commutativité et associativité du produit).
Par remplacement, puis par commutativité et associativité de la somme :
$ab + \overline{a}c + bc = (ab + abc) + (\overline{a}c + \overline{a}bc)$.
Or $ab + abc = ab + (ab)c = ab$ (absorption $x + xy = x$, avec $x = ab$ et $y = c$).
De même, $\overline{a}c + \overline{a}bc = \overline{a}c + (\overline{a}c)b = \overline{a}c$ (commutativité du produit, puis absorption avec $x = \overline{a}c$ et $y = b$).
Donc, pour tous $a, b, c \in \{0, 1\}$, $ab + \overline{a}c + bc = ab + \overline{a}c$.
À retenir : pour absorber un terme où manque une lettre, on la fait entrer par $1 = a + \overline{a}$, on développe, puis chaque morceau est absorbé par un terme plus court.

Signal : l'énoncé mêle les deux écritures, ou le calcul serait plus lisible dans l'autre (produits et barres sont plus compacts que les connecteurs, et l'addition modulo 2 rend le ou exclusif mécanique).
1) Poser le dictionnaire : « À chaque assertion $P$, $Q$ on associe sa valeur $p$, $q$ dans $\{0, 1\}$, égale à $1$ si elle est vraie et à $0$ sinon. »
2) Traduire connecteur par connecteur, en gardant les parenthèses : $\lnot P$ devient $\overline{p}$, « et » devient le produit, « ou » la somme, $P \oplus Q$ devient $p \oplus q$, $\mathrm{V}$ et $\mathrm{F}$ deviennent $1$ et $0$.
3) Calculer avec les lois de l'algèbre de Boole, en nommant chacune, et seulement avec elles : pas de $a + a = 2a$, pas de soustraction, pas de passage de $a + b = a + c$ à $b = c$.
4) Retraduire et conclure : « Les deux expressions sont égales pour toutes valeurs de $p$ et $q$, donc [assertion] $\equiv$ [assertion]. »
5) Dans l'autre sens, lire $ab$ comme « $a$ et $b$ valent $1$ », $a + b$ comme « l'un au moins vaut $1$ », $a \oplus b$ comme « exactement un des deux vaut $1$ ».

Soient $a, b \in \{0, 1\}$. Simplifier $ab + a\overline{b} + \overline{a}b$ en citant les lois, vérifier par une table que le résultat est $a + b$, puis traduire l'égalité obtenue en termes de connecteurs.
Soient $a$ et $b$ des éléments de $\{0, 1\}$.
$ab + a\overline{b} + \overline{a}b = a(b + \overline{b}) + \overline{a}b$ (distributivité du produit sur la somme : on factorise $a$)
$= a \cdot 1 + \overline{a}b$ (complémentarité : $b + \overline{b} = 1$)
$= a + \overline{a}b$ ($1$ neutre pour le produit)
$= (a + \overline{a})(a + b)$ (distributivité de la somme sur le produit)
$= 1 \cdot (a + b)$ (complémentarité : $a + \overline{a} = 1$)
$= a + b$ ($1$ neutre pour le produit).
Donc, pour tous $a, b \in \{0, 1\}$, $ab + a\overline{b} + \overline{a}b = a + b$.
Vérification par une table, sur les quatre valeurs du couple $(a, b)$ :

Les deux dernières colonnes coïncident, ce qui confirme le calcul.
Traduction : pour des assertions $P$ et $Q$ de valeurs $a$ et $b$, le produit traduisant « et », la somme « ou » et la barre « non », les deux membres sont les valeurs de $(P \land Q) \lor (P \land \lnot Q) \lor (\lnot P \land Q)$ et de $P \lor Q$. Ils sont égaux pour toutes valeurs de $a$ et $b$, donc $(P \land Q) \lor (P \land \lnot Q) \lor (\lnot P \land Q) \equiv P \lor Q$.
À retenir : on calcule sur $\{0, 1\}$ avec les seules lois de Boole, la table ne sert que de contrôle, et l'égalité, vraie pour toutes les valeurs, se relit en équivalence d'assertions.

Démontrer que pour toutes assertions $P$ et $Q$, $\lnot(P \oplus Q) \equiv \lnot P \oplus Q$ et $(P \oplus Q) \oplus Q \equiv P$.
Soient $P$ et $Q$ des assertions, de valeurs respectives $p$ et $q$ dans $\{0, 1\}$.
La valeur de $\lnot(P \oplus Q)$ est $\overline{p \oplus q}$, et $\overline{p \oplus q} = 1 \oplus (p \oplus q)$ (car $\overline{x} = 1 \oplus x$ pour tout $x \in \{0, 1\}$)
$= (1 \oplus p) \oplus q$ (associativité de $\oplus$)
$= \overline{p} \oplus q$ (car $1 \oplus p = \overline{p}$).
Or $\overline{p} \oplus q$ est la valeur de $\lnot P \oplus Q$ : les deux assertions ont la même valeur quelles que soient $p$ et $q$, donc $\lnot(P \oplus Q) \equiv \lnot P \oplus Q$.
De même, la valeur de $(P \oplus Q) \oplus Q$ est $(p \oplus q) \oplus q$, et $(p \oplus q) \oplus q = p \oplus (q \oplus q)$ (associativité de $\oplus$)
$= p \oplus 0$ (car $x \oplus x = 0$ pour tout $x \in \{0, 1\}$)
$= p$ ($0$ neutre pour $\oplus$).
Donc $(P \oplus Q) \oplus Q \equiv P$ : appliquer deux fois le ou exclusif avec $Q$ redonne $P$.
À retenir : traduit en addition modulo 2, le ou exclusif se calcule comme une somme où chaque terme s'annule avec lui-même.

Ligne fautive : la négation de « $n$ est pair et $n$ est multiple de $3$ » est « $n$ est impair et $n$ n'est pas multiple de $3$ ».
Pour $n = 3$, l'assertion de départ est fausse, car $3$ est impair, et la prétendue négation l'est aussi, car $3$ est multiple de $3$ : deux assertions fausses en même temps ne sont pas la négation l'une de l'autre.
Version correcte : par la loi de De Morgan, la négation est « $n$ est impair ou $n$ n'est pas multiple de $3$ ». Pour qu'une conjonction soit fausse, il suffit qu'un de ses termes le soit.
Sur $\{0, 1\}$, la même faute consiste à couper la barre : $\overline{ab} = \overline{a}\,\overline{b}$ est faux (pour $a = 1$ et $b = 0$, on trouve $1$ d'un côté et $0$ de l'autre), et la loi juste est $\overline{ab} = \overline{a} + \overline{b}$.

Ligne fautive : $a + a\overline{b} + a = a\overline{b}$, car $a + a = 0$.
C'est confondre la somme booléenne, qui traduit « ou », avec le ou exclusif, qui est l'addition modulo 2 : $1 + 1 = 1$ mais $1 \oplus 1 = 0$. Pour $a = b = 1$, le membre de gauche vaut $1$ et le membre de droite $0$.
Version correcte : $a + a\overline{b} + a = a + a + a\overline{b}$ (commutativité de la somme)
$= a + a\overline{b}$ (idempotence : $a + a = a$)
$= a$ (absorption).
L'erreur inverse existe aussi : écrire $a \oplus a = a$ par réflexe d'idempotence, alors que $a \oplus a = 0$. Avant de simplifier, on vérifie quel symbole on manipule.

Ligne fautive : $P \lor (Q \land R) \equiv (P \lor Q) \land R$, en déplaçant la parenthèse comme pour une associativité.
Pour $P$ vraie et $R$ fausse, le membre de gauche est vrai et le membre de droite faux. L'erreur vient des réels, où $a + bc$ ne se factorise pas : on croit qu'aucune loi ne s'applique, et l'on invente un déplacement de parenthèses.
Version correcte : $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ (distributivité de « ou » sur « et »), qui s'écrit $a + bc = (a + b)(a + c)$ sur $\{0, 1\}$.
Conséquence pratique : $(P \lor Q) \land (P \lor \lnot Q)$ se factorise en $P \lor (Q \land \lnot Q)$ en une ligne, alors que le développement complet produit quatre termes à réduire.

Ligne fautive : $\lnot(P \land \lnot Q) \lor Q \equiv (\lnot P \land Q) \lor Q \equiv Q$.
Aucune loi n'est citée, et le correcteur doit tout refaire pour trouver la faute : la première étape applique De Morgan en gardant « et », la seconde est une absorption juste qui masque l'erreur. Pour $P$ et $Q$ fausses, le membre de gauche est vrai et le résultat $Q$ est faux.
Version correcte :
$\lnot(P \land \lnot Q) \lor Q \equiv (\lnot P \lor \lnot\lnot Q) \lor Q$ (De Morgan)
$\equiv (\lnot P \lor Q) \lor Q$ (double négation)
$\equiv \lnot P \lor (Q \lor Q)$ (associativité de « ou »)
$\equiv \lnot P \lor Q$ (idempotence).
Écrire le nom de la loi oblige à vérifier qu'elle s'applique : « De Morgan » à côté d'un « et » conservé se voit immédiatement.

Ligne fautive : $\lnot(\lnot P \lor Q) \equiv \lnot P \land \lnot Q$.
La négation doit porter sur chaque terme, y compris celui qui est déjà nié : ici $\lnot P$ a été recopié au lieu d'être nié. Pour $P$ vraie et $Q$ fausse, le membre de gauche est vrai et le membre de droite faux.
Version correcte : $\lnot(\lnot P \lor Q) \equiv \lnot\lnot P \land \lnot Q$ (De Morgan)
$\equiv P \land \lnot Q$ (double négation).
Sur $\{0, 1\}$ : $\overline{\overline{a} + b} = \overline{\overline{a}}\,\overline{b} = a\overline{b}$.