High School Mathematics Extensions/Logic/Problem Set/Solutions

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Logic Problem Set Exercises

1.

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

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

Thus the statements are the same

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 means that x can be 3

3² - 6*3 - 3 = 0 is false

Thus the sentence is false

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

For this equation to be false we need an x so that x²=9 and x² - 6x - 3 = 0 are both false.

The values of x for which x²=9 is true are x=3 and x=-3

The values of x for which x² - 6x - 3 = 0 is true are $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.

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

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

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

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

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

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

$x+y=(gh)'$

$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.

$(ij)'=x'$ $x=ij$ $(kl)'=y'$ $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)