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

## Logic Problem Set Exercises[edit]

1.

- Thus the statements are the same

2.

3.

- a.
*x*^{2}= 9 means that*x*can be 3- 3
^{2}- 6*3 - 3 = 0 is false - Thus the sentence is false
- b.
- For this equation to be false we need an
*x*so that*x*^{2}=9 and*x*^{2}- 6x - 3 = 0 are both false. - The values of
*x*for which*x*^{2}=9 is true are x=3 and x=-3 - The values of
*x*for which*x*^{2}- 6x - 3 = 0 is true are - 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.

Therefore and , both need further NAND operators. Let a = c NAND d , and let b = e NAND f.

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

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

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)