# High School Mathematics Extensions/Logic/Problem Set/Solutions

## Logic Problem Set Exercises

1.

${\displaystyle x'\Rightarrow y'=x+y'}$
${\displaystyle y\Rightarrow x=y'+x=x+y'}$
Thus the statements are the same

2.

${\displaystyle (x\Leftrightarrow y)\Rightarrow z=}$
${\displaystyle (x\Leftrightarrow y)'+z=}$
${\displaystyle (x'+y)'+z=}$
${\displaystyle xy'+z}$

3.

a. ${\displaystyle (\forall x)(x^{2}=9\Rightarrow x^{2}-6x-3=0)}$
x2 = 9 means that x can be 3
32 - 6*3 - 3 = 0 is false
Thus the sentence is false
b.${\displaystyle (\exists x)((x^{2}=9)\times (x^{2}-6x-3=0))}$
For this equation to be false we need an x so that x2=9 and x2 - 6x - 3 = 0 are both false.
The values of x for which x2=9 is true are x=3 and x=-3
The values of x for which x2 - 6x - 3 = 0 is true are ${\displaystyle x=2{\sqrt {3}}+3{\mbox{ and }}x=-2{\sqrt {3}}+3}$
Since none of the values for x are the same there exist no numbers at all for which the statement is true.

4. (This solution is due to Tom Lam). Let (x+y)w+z = a NAND b , where a and b can either be one of x,y,w,z or another NAND operator.

${\displaystyle (x+y)w+z=(ab)'}$

${\displaystyle (x+y)w+z=a'+b'}$

Therefore ${\displaystyle a=[(x+y)w]'}$ and ${\displaystyle b=z'}$ , both need further NAND operators. Let a = c NAND d , and let b = e NAND f.

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

${\displaystyle (x+y)w+z=cd+ef}$

Therefore d=w, e=f=z,c=x+y.Let c = g NAND h.

${\displaystyle x+y=(gh)'}$

${\displaystyle x+y=g'+h'}$

Now g=x' and h=y', we still need more NAND operators. Let g = i NAND j and let h = k NAND l.

${\displaystyle (ij)'=x'}$ ${\displaystyle x=ij}$ ${\displaystyle (kl)'=y'}$ ${\displaystyle kl=y}$

Therefore i=j=x and k=l=y.

Now substitute all the variables back, you should get: (x+y)w+z={[(x NAND x) NAND (y NAND y)] NAND w} NAND (z NAND z)

Alternatively Each of AND, OR and NOT can be expressed in terms of NAND only. And therefore any boolean expression can be written down entirely in terms of NAND. This property is called the universality of NAND. Remember x NAND y = (xy)'

Firstly,

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

also,

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

and

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

Now

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

and so

(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)