Fonctions booléennes et formes normales

Les variables $a, b, c$ prennent les valeurs $0$ (faux) et $1$ (vrai). On note $a + b$ pour « $a$ ou $b$ » (ou inclusif, donc $1 + 1 = 1$), $ab$, $a \cdot b$ ou $a \times b$ pour « $a$ et $b$ », et $\overline{a}$ pour « non $a$ », que le thème Algèbre de Boole écrit aussi $\neg a$. Priorités : la barre d'abord, puis le produit, puis la somme, si bien que $a + \overline{b}c$ se lit $a + (\overline{b}\,c)$. Une barre longue nie tout ce qu'elle couvre : $\overline{ab}$ n'est pas $\overline{a}\,\overline{b}$. Le ou exclusif se note $a \oplus b$.

Une fonction booléenne à $n$ variables est une application $f : \{0,1\}^n \to \{0,1\}$. Elle est entièrement donnée par sa table, qui liste ses valeurs sur les $2^n$ éléments de $\{0,1\}^n$ rangés dans l'ordre du comptage en binaire. Une ligne vraie est un $n$-uplet où $f$ vaut $1$, une ligne fausse un $n$-uplet où elle vaut $0$. Une formule représente $f$ si elle prend la valeur $f(e)$ en chaque $e \in \{0,1\}^n$ : ainsi $a$, $a + ab$ et $a(a + b)$ représentent la même fonction, et on écrit entre elles le signe $=$. Choisir une fonction, c'est choisir $0$ ou $1$ sur chaque ligne : il y a $2^{2^n}$ fonctions booléennes à $n$ variables.

Un littéral est une variable $x_i$ ou sa négation $\overline{x_i}$. Un monôme est un produit de littéraux, comme $a\overline{b}$ ; une clause est une somme de littéraux, comme $\overline{a} + c$. Un minterme en $x_1, \dots, x_n$ est un monôme où chaque variable figure exactement une fois, barrée ou non ; un maxterme est une clause où chaque variable figure exactement une fois. Avec les trois variables $a, b, c$, le monôme $\overline{a}bc$ est un minterme, mais $ab$ n'en est pas un.

Soit $e = (e_1, \dots, e_n)$ une ligne de la table. Le minterme $m_e$ prend $x_i$ si $e_i = 1$ et $\overline{x_i}$ si $e_i = 0$ : un produit vaut $1$ si et seulement si chaque littéral vaut $1$, donc $m_e$ vaut $1$ en $e$ et $0$ sur toutes les autres lignes. Le maxterme $M_e$ prend à l'inverse $x_i$ si $e_i = 0$ et $\overline{x_i}$ si $e_i = 1$ : il vaut $0$ en $e$ et seulement en $e$. Pour $e = (1,0,1)$, on obtient $m_e = a\overline{b}c$ et $M_e = \overline{a} + b + \overline{c}$. Par De Morgan, $M_e = \overline{m_e}$.

Une formule est en forme normale disjonctive si c'est une somme de monômes, comme $ab + \overline{a}c$, et en forme normale conjonctive si c'est un produit de clauses, comme $(a + b)(\overline{a} + c)$. La forme normale disjonctive canonique de $f$ est la somme des mintermes de ses lignes vraies ; la forme normale conjonctive canonique est le produit des maxtermes de ses lignes fausses. Par convention, une somme vide vaut $0$ et un produit vide vaut $1$. Sans autre précision, « la forme normale » d'une table désigne la forme canonique.

Théorème : toute fonction booléenne est représentée par sa forme normale disjonctive canonique et par sa forme normale conjonctive canonique. Pour la première : en une ligne $x$, la somme vaut $1$ si et seulement si l'un de ses mintermes vaut $1$ en $x$, c'est-à-dire si $x$ est une ligne vraie ; pour la seconde, les lignes fausses de $f$ sont les lignes vraies de $\overline{f}$, et nier la forme disjonctive de $\overline{f}$ par De Morgan change chaque minterme en maxterme. Unicité : si $f$ est représentée par une somme de mintermes deux à deux distincts, ces mintermes sont exactement ceux des lignes vraies de $f$, car une telle somme vaut $1$ en $e$ si et seulement si elle contient $m_e$ ; de même, un produit de maxtermes deux à deux distincts qui représente $f$ contient exactement les maxtermes de ses lignes fausses. Conséquence : $\{\text{non}, \text{et}, \text{ou}\}$ est un système complet de connecteurs.

Quand l'utiliser : une table est donnée, ou une fonction est décrite en français (« vaut 1 exactement quand… »), et l'énoncé demande une formule ou une forme normale.
1) Dresser la table : $2^n$ lignes dans l'ordre du comptage en binaire (voir Assertions, connecteurs et tables de vérité).
2) Compter et écrire les lignes : « $f$ vaut 1 exactement sur les $p$ lignes … et 0 sur les $q$ autres. » Contrôle : $p + q = 2^n$.
3) Forme disjonctive : pour chaque ligne vraie, écrire son minterme, la variable telle quelle si elle vaut 1, barrée si elle vaut 0 ; puis faire la somme des $p$ mintermes.
4) Forme conjonctive : pour chaque ligne fausse, écrire son maxterme, la variable telle quelle si elle vaut 0, barrée si elle vaut 1 ; puis faire le produit des $q$ maxtermes.
5) Contrôler chaque terme sur sa ligne (un minterme doit y valoir 1, un maxterme 0) et vérifier qu'il y a autant de termes que de lignes comptées.
6) Si l'énoncé laisse le choix, prendre la forme la plus courte : la disjonctive quand $f$ a peu de lignes vraies.
Sur la copie : « La ligne vraie $(0,1,1)$ donne le minterme $\overline{a}bc$, qui vaut 1 sur cette seule ligne. […] Donc la forme normale disjonctive de $f$ est $\overline{a}bc + \dots$ »

Écrire les formes normales disjonctive et conjonctive du ou exclusif $a \oplus b$.
La table du ou exclusif est la suivante.

Le ou exclusif vaut 1 exactement sur les deux lignes $(0,1)$ et $(1,0)$, et 0 sur les deux lignes $(0,0)$ et $(1,1)$ ; on a bien $2 + 2 = 2^2$ lignes.
Forme disjonctive. La ligne vraie $(0,1)$ donne le minterme $\overline{a}b$, qui vaut 1 sur cette seule ligne ; la ligne vraie $(1,0)$ donne le minterme $a\overline{b}$.
Donc la forme normale disjonctive de $a \oplus b$ est $\overline{a}b + a\overline{b}$.
Forme conjonctive. La ligne fausse $(0,0)$ donne le maxterme $a + b$, qui vaut 0 sur cette seule ligne ; la ligne fausse $(1,1)$ donne le maxterme $\overline{a} + \overline{b}$.
Donc la forme normale conjonctive de $a \oplus b$ est $(a + b)(\overline{a} + \overline{b})$.
Vérifions par le calcul que les deux formes sont égales.
$(a + b)(\overline{a} + \overline{b}) = a\overline{a} + a\overline{b} + b\overline{a} + b\overline{b}$ (distributivité de $\times$ sur $+$)
$= 0 + a\overline{b} + \overline{a}b + 0$ (complémentarité $x\overline{x} = 0$, commutativité de $\times$)
$= \overline{a}b + a\overline{b}$ ($0$ neutre pour $+$, commutativité de $+$).
Conclusion : $a \oplus b = \overline{a}b + a\overline{b} = (a + b)(\overline{a} + \overline{b})$.
À retenir : on compte les lignes avant d'écrire, on lit les mintermes sur les lignes vraies et les maxtermes sur les lignes fausses.

Erreur fréquente : traduire « au moins deux variables valent 1 » par « exactement deux », ou lire la table trop vite.
Ligne fautive : « La forme normale disjonctive de $f$ est $\overline{a}bc + a\overline{b}c + ab\overline{c}$. »
Cette formule vaut $0$ en $(1,1,1)$ alors que $f(1,1,1) = 1$ : elle représente une autre fonction, et tout calcul qui la suit est faux.
Version correcte : « $f$ vaut 1 exactement sur les quatre lignes $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ et $(1,1,1)$, donc $f = \overline{a}bc + a\overline{b}c + ab\overline{c} + abc$. »
Réflexe : écrire la liste des lignes vraies et leur nombre AVANT la formule, puis vérifier qu'il y a autant de mintermes.

Erreur fréquente : reprendre les lignes vraies pour la forme conjonctive, par habitude de la forme disjonctive.
Ligne fautive : « Les lignes vraies du ou exclusif sont $(0,1)$ et $(1,0)$, donc sa forme normale conjonctive est $(\overline{a} + b)(a + \overline{b})$. »
En $(0,0)$, cette formule vaut $(1 + 0)(0 + 1) = 1$ alors que $0 \oplus 0 = 0$ : on a écrit l'équivalence de $a$ et $b$, qui est la négation du ou exclusif. Un produit s'annule dès qu'un facteur est nul, donc chaque facteur doit annuler une ligne fausse.
Version correcte : « Les lignes fausses sont $(0,0)$ et $(1,1)$ ; elles donnent les maxtermes $a + b$ et $\overline{a} + \overline{b}$, donc $a \oplus b = (a + b)(\overline{a} + \overline{b})$. »
Faute voisine : barrer dans un maxterme les variables qui valent 0 ; le maxterme $\overline{a} + \overline{b}$ s'annule en $(1,1)$, pas en $(0,0)$.

Chaque loi est écrite avec sa duale, obtenue en échangeant $+$ et $\times$, $0$ et $1$. Dans un calcul, on cite la loi par son nom, entre parenthèses, à droite de la ligne où elle sert.

L'involution $\overline{\overline{a}} = a$ est sa propre duale.

Quand l'utiliser : l'énoncé dit « simplifier » ou « montrer que $f$ s'écrit … », ou une forme canonique compte beaucoup de termes.
1) Repérer les paires de monômes de la forme $xm + \overline{x}m$ : identiques sauf pour un seul littéral, barré dans l'un et non barré dans l'autre.
2) Si un monôme doit servir dans plusieurs paires, le recopier autant de fois qu'il le faut (idempotence $m = m + m$).
3) Regrouper les paires (commutativité et associativité de $+$), factoriser (distributivité de $\times$ sur $+$), puis remplacer $x + \overline{x}$ par $1$ (complémentarité) et $1 \cdot m$ par $m$ (neutre).
4) Supprimer tout monôme qui en contient un autre : $m + mm' = m$ (absorption).
5) Éliminer un littéral par $x + \overline{x}y = x + y$ (élimination), où $\overline{x}$ est la négation du terme $x$ tout entier : pour $x = ab$, c'est $\overline{ab} = \overline{a} + \overline{b}$, et non $\overline{a}$.
6) Supprimer un terme de consensus : $xy + \overline{x}z + yz = xy + \overline{x}z$ (identité du consensus, qui se démontre à partir des lois).
7) Écrire une seule égalité par ligne, commencée par $=$, avec à droite la loi entre parenthèses.
8) Contrôler le résultat sur deux lignes de la table, une vraie et une fausse, puis conclure en recopiant l'égalité obtenue.
Qu'aucune loi ne s'applique plus ne prouve pas que la forme obtenue est la plus courte : on écrit « on s'arrête sur cette forme », sans prétendre qu'elle est minimale.
Sur la copie : « $= (\overline{a} + a)bc + \dots$ (distributivité de $\times$ sur $+$) ».

Soit $f$ la fonction booléenne de $a, b, c$ qui vaut 1 exactement quand au moins deux des trois variables valent 1. Donner sa forme normale disjonctive, puis montrer que $f(a,b,c) = ab + bc + ca$.
Parmi les $2^3 = 8$ lignes, celles où au moins deux variables valent 1 sont $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ et $(1,1,1)$ : $f$ a quatre lignes vraies et vaut 0 sur les quatre autres.
Ces lignes donnent respectivement les mintermes $\overline{a}bc$, $a\overline{b}c$, $ab\overline{c}$ et $abc$.
Donc la forme normale disjonctive de $f$ est $f(a,b,c) = \overline{a}bc + a\overline{b}c + ab\overline{c} + abc$.
Simplifions. Le minterme $abc$ forme une paire $xm + \overline{x}m$ avec chacun des trois autres : on l'écrit trois fois en tout, en ajoutant deux copies.
$f(a,b,c) = \overline{a}bc + a\overline{b}c + ab\overline{c} + abc + abc + abc$ (idempotence de $+$, deux fois)
$= (\overline{a}bc + abc) + (a\overline{b}c + abc) + (ab\overline{c} + abc)$ (commutativité et associativité de $+$)
$= (\overline{a} + a)bc + (\overline{b} + b)ac + (\overline{c} + c)ab$ (commutativité de $\times$, puis distributivité de $\times$ sur $+$)
$= 1 \cdot bc + 1 \cdot ac + 1 \cdot ab$ (complémentarité $\overline{x} + x = 1$)
$= ab + bc + ca$ ($1$ neutre pour $\times$, commutativité de $+$ et de $\times$).
Contrôle : en $(1,1,0)$, $ab + bc + ca = 1 + 0 + 0 = 1$ ; en $(1,0,0)$, elle vaut $0 + 0 + 0 = 0$ ; ce sont bien les valeurs de $f$.
Conclusion : pour tous $a, b, c \in \{0,1\}$, $f(a,b,c) = ab + bc + ca$.
À retenir : pour fusionner un monôme avec plusieurs voisins, on le duplique d'abord par idempotence, et chaque ligne du calcul porte le nom de sa loi.

Erreur fréquente : appliquer $xm + \overline{x}m = m$ dès qu'une variable apparaît barrée dans un monôme et non barrée dans l'autre, sans regarder le reste.
Ligne fautive : « $a\overline{b}c + \overline{a}bc = c$ (complémentarité). »
En $(0,0,1)$, le membre de gauche vaut $0$ et le membre de droite vaut $1$ : l'égalité est fausse. Les deux monômes diffèrent par deux littéraux ; or la fusion exige deux monômes de la forme $xm$ et $\overline{x}m$, identiques sauf pour un seul littéral, barré dans l'un et non barré dans l'autre.
Version correcte : « $a\overline{b}c + \overline{a}bc = (a\overline{b} + \overline{a}b)c$ (distributivité de $\times$ sur $+$) », et la complémentarité ne permet pas d'aller plus loin.

La duale $E^*$ d'une formule $E$ écrite avec $+$, $\times$, la barre, $0$ et $1$ s'obtient en échangeant $+$ et $\times$ d'une part, $0$ et $1$ d'autre part, sans toucher aux variables ni aux barres. On conserve la structure en ajoutant les parenthèses que la priorité exige : la duale de $a + bc$ est $a(b + c)$, et non $ab + c$. La duale de l'identité $E = F$ est l'identité $E^* = F^*$. On a $(E^*)^* = E$, et la duale de $\overline{ab}$ est $\overline{a + b}$.

Théorème : si une identité $E = F$ est vraie pour toutes les valeurs des variables, son identité duale $E^* = F^*$ l'est aussi. Pour une identité démontrée par le calcul : chaque loi de l'algèbre de Boole a sa duale parmi les lois, donc dualiser chaque ligne du calcul prouve $E^* = F^*$. Pour toute identité vraie sur $\{0,1\}$ : par De Morgan, $E^*(x_1, \dots, x_n) = \overline{E(\overline{x_1}, \dots, \overline{x_n})}$ ; si $E = F$ pour toutes les valeurs, alors $E(\overline{x_1}, \dots, \overline{x_n}) = F(\overline{x_1}, \dots, \overline{x_n})$, donc, en niant, $E^* = F^*$. Le principe vaut dans toute algèbre de Boole pour les lois déduites des axiomes, car son système d'axiomes est stable par dualité.

Quand l'utiliser : l'énoncé demande de prouver une identité « par le calcul » ou « sans table », ou d'en donner l'identité duale.
1) Introduire les variables : « Soient $a$ et $b$ des variables booléennes. »
2) Partir du membre le plus long et le transformer jusqu'à l'autre, une égalité par ligne, la loi citée entre parenthèses. Ne jamais écrire les deux membres à la fois en travaillant « des deux côtés ».
3) Conclure en recopiant l'identité démontrée.
4) Écrire l'identité duale : échanger $+$ et $\times$, échanger $0$ et $1$, garder variables et barres, puis rétablir les parenthèses.
5) La justifier, au choix : « D'après le principe de dualité, l'identité duale … est vraie », ou refaire le calcul en dualisant chaque ligne et en remplaçant chaque loi citée par sa duale.
6) Contrôler la duale sur une ligne de la table : une duale fausse trahit un échange oublié.

Écrire l'identité duale de $a + ab = a$, puis démontrer les deux identités par le calcul.
Soient $a$ et $b$ des variables booléennes.
Identité duale. On échange $+$ et $\times$ (les constantes $0$ et $1$ n'apparaissent pas) en gardant les variables : la duale de $a + ab$ est $a(a + b)$ et celle de $a$ est $a$.
L'identité duale de $a + ab = a$ est donc $a(a + b) = a$.
Démonstration de $a + ab = a$.
$a + ab = a \cdot 1 + ab$ ($1$ neutre pour $\times$)
$= a(1 + b)$ (distributivité de $\times$ sur $+$)
$= a \cdot 1$ ($1$ absorbant pour $+$)
$= a$ ($1$ neutre pour $\times$).
Démonstration de $a(a + b) = a$, en dualisant chaque ligne et chaque loi du calcul précédent.
$a(a + b) = (a + 0)(a + b)$ ($0$ neutre pour $+$)
$= a + 0 \cdot b$ (distributivité de $+$ sur $\times$)
$= a + 0$ ($0$ absorbant pour $\times$)
$= a$ ($0$ neutre pour $+$).
Conclusion : pour toutes valeurs de $a$ et $b$, $a + ab = a$ et $a(a + b) = a$.
À retenir : la preuve de l'identité duale est le calcul dual ligne à ligne, où le $1$ introduit au départ devient un $0$.

Erreur fréquente : échanger $+$ et $\times$ en oubliant que les constantes s'échangent aussi.
Ligne fautive : « L'identité $a + 1 = 1$ a pour duale $a \cdot 1 = 1$. »
Pour $a = 0$, cette « duale » donne $0 = 1$ : elle est fausse, alors que le principe de dualité garantit une identité vraie. La même faute change $a + \overline{a} = 1$ en $a\overline{a} = 1$, faux pour toute valeur de $a$.
Version correcte : « La duale de $a + 1 = 1$ est $a \cdot 0 = 0$ ($0$ absorbant pour $\times$), celle de $a + \overline{a} = 1$ est $a\overline{a} = 0$. »
Confusion voisine : barrer les variables en dualisant. C'est la négation, pas la dualité : la duale de $a + b$ est $ab$, et non $\overline{a}\,\overline{b}$.

Un ensemble $C$ de connecteurs est un système complet si toute fonction booléenne à $n \geq 1$ variables est représentée par une formule écrite avec les seules variables et les connecteurs de $C$, sans constante. La forme normale disjonctive montre que $\{\text{non}, \text{et}, \text{ou}\}$ est complet, la fonction nulle s'écrivant $x_1\overline{x_1}$. Pour montrer qu'un ensemble $C'$ est complet, il suffit d'exprimer avec $C'$ chaque connecteur d'un système déjà connu comme complet. Ainsi $\{\text{non}, \text{et}\}$ est complet car $a + b = \overline{\overline{a}\,\overline{b}}$, et $\{\text{non}, \text{ou}\}$ l'est car $ab = \overline{\overline{a} + \overline{b}}$.

Le non-et (barre de Sheffer) est le connecteur $a \uparrow b = \overline{ab}$ : il vaut $0$ seulement quand $a$ et $b$ valent $1$. Le non-ou (flèche de Peirce) est $a \downarrow b = \overline{a + b}$ : il vaut $1$ seulement quand $a$ et $b$ valent $0$. Les deux sont commutatifs, duaux l'un de l'autre, et non associatifs. Par De Morgan, $a \uparrow b = \overline{a} + \overline{b}$ et $a \downarrow b = \overline{a}\,\overline{b}$ : le et des négations n'est pas le non-et, c'est le non-ou.

Traductions à connaître ; la colonne du non-ou se déduit de celle du non-et par dualité, qui échange aussi et et ou.

Théorème : $\{\uparrow\}$ est un système complet, et par dualité $\{\downarrow\}$ aussi. Preuve : $\overline{a} = a \uparrow a$, puis $ab = \overline{a \uparrow b} = (a \uparrow b) \uparrow (a \uparrow b)$, puis $a + b = \overline{a} \uparrow \overline{b} = (a \uparrow a) \uparrow (b \uparrow b)$ ; en remplaçant ces connecteurs dans la forme normale disjonctive d'une fonction, on obtient une formule en $\uparrow$ seul. Parmi les seize connecteurs binaires, ce sont les deux seuls qui forment à eux seuls un système complet (résultat admis). C'est pourquoi tout circuit logique peut se construire avec un seul type de porte.

Quand l'utiliser : l'énoncé demande d'exprimer non, et, ou avec un connecteur donné, ou de prouver qu'un ensemble de connecteurs est complet.
1) Annoncer la stratégie : « Le système $\{\text{non}, \text{et}, \text{ou}\}$ est complet (forme normale disjonctive) ; il suffit d'exprimer ces trois connecteurs avec le seul connecteur étudié. »
2) La négation d'abord : chercher la valeur obtenue en répétant l'entrée, comme $a \uparrow a$ ou $a \downarrow a$.
3) Nier le connecteur à l'aide de l'étape 2 : pour $\uparrow$ on obtient le et, $ab = \overline{a \uparrow b}$ ; pour $\downarrow$ on obtient le ou, $a + b = \overline{a \downarrow b}$.
4) Obtenir le connecteur restant par De Morgan et involution : $a + b = \overline{a} \uparrow \overline{b}$ pour le non-et, $ab = \overline{a} \downarrow \overline{b}$ pour le non-ou.
5) Vérifier chaque égalité, par une table à quatre lignes où l'on compare deux colonnes, ou par un calcul dont chaque ligne cite sa loi.
6) Conclure : « Soit $f$ une fonction booléenne. Dans une formule de $f$ en non, et, ou, on découpe les produits et les sommes en connecteurs à deux entrées, puis on remplace chaque connecteur par son expression ; la valeur ne change sur aucune ligne, donc $f$ s'écrit avec le seul connecteur, qui forme un système complet. »
Pour montrer au contraire qu'un ensemble n'est pas complet, suivre la méthode « Montrer qu'un ensemble de connecteurs n'est pas complet ».

Exprimer non $a$, $a$ et $b$, puis $a$ ou $b$ à l'aide du seul connecteur non-et $a \uparrow b = \overline{ab}$, en vérifiant chaque égalité par une table ; en déduire que $\{\uparrow\}$ est un système complet.
Soient $a$ et $b$ des variables booléennes.
Non. On a $a \uparrow a = \overline{aa} = \overline{a}$ (idempotence de $\times$). On propose $\overline{a} = a \uparrow a$.
Et. Le et est la négation du non-et, et d'après la ligne précédente la négation d'une expression $u$ s'écrit $u \uparrow u$. On propose $ab = (a \uparrow b) \uparrow (a \uparrow b)$.
Ou. Par De Morgan et involution, $a + b = \overline{\overline{a}\,\overline{b}} = \overline{a} \uparrow \overline{b}$. On propose $a + b = (a \uparrow a) \uparrow (b \uparrow b)$.
Vérifions les trois égalités sur les quatre lignes de la table.

Sur chaque ligne, la colonne de $a \uparrow a$ coïncide avec celle de $\overline{a}$, la colonne de $(a \uparrow b) \uparrow (a \uparrow b)$ avec celle de $ab$, et la colonne de $(a \uparrow a) \uparrow (b \uparrow b)$ avec celle de $a + b$ : les trois égalités sont vraies pour toutes valeurs de $a$ et $b$ dans $\{0,1\}$, donc encore lorsque $a$ et $b$ sont remplacés par des sous-formules, qui ne prennent que ces valeurs.
Soit maintenant $f$ une fonction booléenne à $n \geq 1$ variables. Elle est représentée par une formule en non, et, ou : sa forme normale disjonctive, ou $x_1\overline{x_1}$ si $f$ est nulle.
Dans cette formule, on écrit chaque produit de plusieurs facteurs comme une suite de et à deux termes et chaque somme de plusieurs termes comme une suite de ou à deux termes ; on remplace ensuite chaque non, chaque et, chaque ou par son expression en $\uparrow$, ce qui, d'après les trois égalités, ne change la valeur sur aucune ligne.
Donc $f$ est représentée par une formule qui n'utilise que $\uparrow$, et $\{\uparrow\}$ est un système complet.
À retenir : on ramène le nouveau connecteur à un système déjà complet, en traduisant chacun de ses connecteurs et en vérifiant chaque traduction.

Quand l'utiliser : l'énoncé demande si un ensemble de connecteurs est complet et les traductions de non, et, ou échouent, ou il faut prouver qu'une fonction ne s'écrit pas avec certains connecteurs.
1) Choisir une propriété des valeurs, par exemple « vaut 1 lorsque toutes les variables valent 1 ».
2) Vérifier que chaque variable la possède et que chaque connecteur du système la conserve : « $1 + 1 = 1$ et $1 \cdot 1 = 1$ ».
3) L'étendre à toutes les formules par récurrence sur le nombre de connecteurs, avec la propriété « $P(k)$ : toute formule comportant au plus $k$ connecteurs vaut 1 lorsque toutes ses variables valent 1 ». Le « au plus » permet d'appliquer $P(k)$ aux deux sous-formules d'une formule à $k + 1$ connecteurs.
4) Exhiber une fonction qui ne vérifie pas la propriété, en général non $a$ pour $a = 1$.
5) Conclure : « Aucune formule écrite avec ces connecteurs ne représente non $a$, donc le système n'est pas complet. »
Des essais infructueux, ou l'échec d'une méthode d'écriture, ne prouvent aucune impossibilité : seule une propriété conservée par toutes les formules la prouve.

Démontrer que $\{\text{et}, \text{ou}\}$ n'est pas un système complet de connecteurs.
Montrons qu'aucune formule écrite avec la variable $a$ et les seuls connecteurs $+$ et $\times$ ne représente non $a$.
Pour $k \in \mathbb{N}$, notons $P(k)$ la propriété : « toute formule écrite avec des variables et les seuls connecteurs $+$ et $\times$, comportant au plus $k$ connecteurs, vaut $1$ lorsque toutes ses variables valent $1$ ».
Initialisation. Une formule sans connecteur est une variable ; elle vaut $1$ lorsque toutes les variables valent $1$. Donc $P(0)$ est vraie.
Hérédité. Soit $k \in \mathbb{N}$ tel que $P(k)$ soit vraie. Montrons $P(k + 1)$.
Soit $E$ une formule en $+$ et $\times$ comportant au plus $k + 1$ connecteurs, et supposons que toutes ses variables valent $1$.
Si $E$ comporte au plus $k$ connecteurs, $E$ vaut $1$ d'après $P(k)$.
Sinon, $E$ comporte $k + 1$ connecteurs ; elle s'écrit $E = F + G$ ou $E = F \times G$, où $F$ et $G$ comportent au total $k$ connecteurs, donc chacune au plus $k$.
D'après $P(k)$, $F$ et $G$ valent $1$, donc $E$ vaut $1 + 1 = 1$ ou $1 \times 1 = 1$.
Dans tous les cas $E$ vaut $1$, donc $P(k + 1)$ est vraie.
Par récurrence, $P(k)$ est vraie pour tout $k \in \mathbb{N}$.
Soit maintenant $E$ une formule écrite avec la seule variable $a$ et les connecteurs $+$ et $\times$. Pour $a = 1$, $E$ vaut $1$ d'après ce qui précède, alors que $\overline{1} = 0$.
Donc $E$ ne représente pas non $a$.
Conclusion : la fonction non $a$ ne s'écrit pas avec et, ou seuls, donc $\{\text{et}, \text{ou}\}$ n'est pas un système complet.
À retenir : pour prouver une impossibilité d'écriture, on exhibe une propriété que la récurrence transmet à toutes les formules du système et que la fonction visée n'a pas.