Approfondissements de lycée/SP Logique

Logique

Ensemble d'exercices de problèmes de logique

1.

$x'\Rightarrow y'=x+y'$

$y\Rightarrow x=y'+x=x+y'$

Donc, les énoncés sont les mêmes

2.

$(x\Leftrightarrow y)\Rightarrow z=\,$

$(x\Leftrightarrow y)'+z=\,$

$(x'+y)'+z=\,$

$xy'+z\,$

3.

a. $(\forall x)(x^{2}=9\Rightarrow x^{2}-6x-3=0)$

x² = 9 veut dire que x peut être 3

3² - 6*3 - 3 = 0 est faux

Donc, la phrase est fausse

b.$(\exists x)((x^{2}=9)\times (x^{2}-6x-3=0))$

Pour que cette équation soit fausse, nous devons avoir un x tel que x²=9 et x² - 6x - 3 = 0 soient tous les deux faux.

Les valeurs de x pour lesquelles x²=9 est vraie sont x = 3 et x = - 3

Les valeurs de x pour lesquelles x² - 6x - 3 = 0 est vraie sont $x=2{\sqrt {3}}+3{\mbox{ et }}x=-2{\sqrt {3}}+3$

Puisque aucune des valeurs de x sont les mêmes, il n'existe pas de nombre pour lequel l'énoncé est vrai.

4. (Cette solution est due à Tom Lam). Soit (x+y)w+z = a NAND b , où a et b peuvent être soit un des x,y,w,z ou un autre opérateur NAND.

$(x+y)w+z=(ab)'$

$(x+y)w+z=a'+b'$

Par conséquent $a=[(x+y)w]'$ et $b=z'$ , les deux ont besoin de plus d'opérateurs NAND. Soit a = c NAND d , et soit b = e NAND f.

$(x+y)w+z={(cd)'}^{'}+{(ef)'}^{'}$

$(x+y)w+z=cd+ef$

Par conséquent d=w, e=f=z,c=x+y. Soit c = g NAND h.

$x+y=(gh)'$

$x+y=g'+h'$

Maintenant g=x' et h=y', nous avons besoins d'encore plus d'opérateurs NAND. Soit g = i NAND j et soit h = k NAND l.

$(ij)'=x'\,$ $x=ij\,$ $(kl)'=y'\,$ $kl=y\,$

Par conséquent i=j=x et k=l=y.

Maintenant, substituons toutes les variables, vous devriez obtenir : (x+y)w+z={[(x NAND x) NAND (y NAND y)] NAND w} NAND (z NAND z)

D'une manière différente Chacun des ET, OU et NON peut être exprimé en termes de NAND. Et par conséquent toute expression booléenne peut être écrite entièrement avec l'opérateur NAND. Cette propriété est appelée l'universalité de NAND. Rappelez-vous que x NAND y = (xy)'

D'abord,

NOT x = x' = x'x' = (xx)' = x NAND x

donc,

x OR y = x + y = (x'y')' = (x NAND x) NAND (y NAND y)

et

x AND y = xy = (xy)' ' = (x NAND y) NAND (x NAND y)

Maintenant

(x + y)w = ((x NAND x) NAND (y NAND y)) NAND w

et donc

(x + y)w + z = ((((x NAND x) NAND (y NAND y)) NAND w) NAND (((x NAND x) NAND (y NAND y)) NAND w)) NAND (z NAND z)