Exercice 3

1. On commence par la négation, qui servira à tout le reste : $$\boxed{\mathrm{non}\, P \Leftrightarrow P \uparrow P}$$ car $\mathrm{non}\,(P \ \mathrm{et}\ P)$ a la même valeur que $\mathrm{non}\, P$. La conjonction s'obtient en niant $P \uparrow Q$, la disjonction grâce à une loi de De Morgan, et l'implication grâce au point (iv) de la proposition 1 du cours : $$\boxed{P \ \mathrm{et}\ Q \Leftrightarrow (P \uparrow Q) \uparrow (P \uparrow Q)} \qquad \boxed{P \ \mathrm{ou}\ Q \Leftrightarrow (P \uparrow P) \uparrow (Q \uparrow Q)} \qquad \boxed{P \Rightarrow Q \Leftrightarrow P \uparrow (Q \uparrow Q)}$$ Pour la disjonction : $(P \uparrow P) \uparrow (Q \uparrow Q) = \mathrm{non}\,(\mathrm{non}\, P \ \mathrm{et}\ \mathrm{non}\, Q)$, qui équivaut à $P \ \mathrm{ou}\ Q$. Pour l'implication : $P \uparrow (\mathrm{non}\, Q) = \mathrm{non}\,(P \ \mathrm{et}\ \mathrm{non}\, Q)$, qui équivaut à $P \Rightarrow Q$.

2. Une table de vérité à deux variables comporte quatre lignes, et chacune peut recevoir l'une des deux valeurs V ou F, indépendamment des autres : $$\boxed{2^{4} = 16 \text{ connecteurs binaires.}}$$ Parmi eux figurent « et », « ou », $\Rightarrow$, $\Leftrightarrow$, $\uparrow$, le « ou exclusif », mais aussi des connecteurs dégénérés comme « toujours vrai » ou « valeur de $P$ ».

3. Soit $c$ un connecteur binaire. S'il est toujours faux, il équivaut à $P \ \mathrm{et}\ \mathrm{non}\, P$. Sinon, à chaque ligne de sa table où il vaut V, on associe la conjonction qui n'est vraie que sur cette ligne : par exemple $P \ \mathrm{et}\ \mathrm{non}\, Q$ pour la ligne où $P$ est vraie et $Q$ fausse. La disjonction de ces conjonctions est vraie exactement sur les lignes où $c$ vaut V : $$\boxed{\text{tout connecteur s'écrit comme une disjonction de conjonctions de } P,\ Q,\ \mathrm{non}\, P,\ \mathrm{non}\, Q.}$$ Par exemple, le « ou exclusif » s'écrit $(P \ \mathrm{et}\ \mathrm{non}\, Q) \ \mathrm{ou}\ (\mathrm{non}\, P \ \mathrm{et}\ Q)$. Comme la question 1 exprime « non », « et » et « ou » à l'aide de $\uparrow$, il suffit de remplacer chacun d'eux par son expression : $$\boxed{\text{tout connecteur binaire s'exprime à l'aide du seul connecteur } \uparrow.}$$

4. Montrons que toute assertion construite à partir de $P$ avec les seuls connecteurs « et », « ou » et $\Rightarrow$ est vraie lorsque $P$ est vraie. On raisonne par récurrence forte sur le nombre $k$ de connecteurs utilisés. Si $k = 0$, l'assertion est $P$ elle-même. Si $k \geqslant 1$, l'assertion s'écrit $F_{1} \ast F_{2}$, où $\ast$ est l'un des trois connecteurs et où $F_{1}$, $F_{2}$ utilisent chacune strictement moins de $k$ connecteurs ; par hypothèse de récurrence, $F_{1}$ et $F_{2}$ sont vraies lorsque $P$ l'est, et l'on conclut car « V et V », « V ou V » et « V $\Rightarrow$ V » valent tous V. Or $\mathrm{non}\, P$ est fausse lorsque $P$ est vraie. $$\boxed{\text{Non : } \mathrm{non}\, P \text{ ne s'exprime pas à l'aide de } P \text{ et des seuls connecteurs «~et~», «~ou~», } \Rightarrow.}$$

À retenir : pour démontrer une impossibilité, on cherche une propriété conservée par toutes les constructions autorisées et que l'objet visé ne possède pas : c'est la méthode de l'invariant. On en reverra des exemples tout au long de l'année. Par ailleurs, le connecteur $\uparrow$ est le « NAND » des électroniciens : un circuit logique arbitraire peut être réalisé avec ce seul type de porte.