COMP 2711 HW 1

1

a

$$\begin{array}{rlrl}& TA(x)& & \text{x is a TA in COMP2711}\\ & R(x)& & \text{x reports to the course intstructors}\\ & CH(x)& & \text{x has curly hair}\\ & M(x)& & \text{x is a musician}\\ & E(x)& & \text{x is Eden}\\ & V(x)& & \text{x is a vegetarian}\\ & S(x)& & \text{x is a student in COMP2711}\\ & CO(x)& & \text{x takes other COMP courses}\\ & H(x)& & \text{x is Kenneth’s hiking mate}\end{array}$$

b

$$\begin{array}{rlrl}& 1.& & \forall x(TA(x)\to R(x))\\ & 2.& & \neg \exists x(CH(x)\wedge \neg M(x))\\ & 3.& & \forall x(E(x)\to \neg V(x))\\ & 4.& & \forall x(S(x)\to CO(x))\\ & 5.& & \forall x(TA(x)\leftrightarrow M(x))\\ & 6.& & \forall x(H(x)\leftrightarrow R(x))\\ & 7.& & \forall x(\neg CH(x)\to V(x))\end{array}$$

c

$$\begin{array}{rlrlrl}& 1.& & \neg \exists x(CH(x)\wedge \neg M(x))& & \text{Premise}\\ & 2.& & \forall x\neg (CH(x)\wedge \neg M(x))& & \text{De Morgan’s Laws (1)}\\ & 3.& & \forall x(\neg CH(x)\vee M(x))& & \text{De Morgan’s Laws (2)}\\ & 4.& & \forall x(CH(x)\to M(x))& & \text{Equivalence (3)}\end{array}$$

d

$$\begin{array}{rlrlrl}& 1.& & \forall x(E(x)\to \neg V(x))& & \text{Premise}\\ & 2.& & E(a)\to \neg V(a)& & \text{Universal Instantiation (1)}\\ & 3.& & \forall x(\neg CH(x)\to V(x))& & \text{Premise}\\ & 4.& & \neg CH(a)\to V(a)& & \text{Universal Instantiation (3)}\\ & 5.& & \forall x(CH(x)\to M(x))& & \text{Premise}\\ & 6.& & CH(a)\to M(a)& & \text{Universal Instantiation (5)}\\ & 7.& & \forall x(TA(x)\leftrightarrow M(x))& & \text{Premise}\\ & 8.& & TA(a)\leftrightarrow M(a)& & \text{Universal Instantiation (7)}\\ & 9.& & TA(a)\to M(a)\wedge M(a)\to TA(a)& & \text{Equivalence (8)}\\ & 10.& & M(a)\to TA(a)& & \text{Simplification (9)}\\ & 11.& & \forall x(TA(x)\to R(x))& & \text{Premise}\\ & 12.& & TA(a)\to R(a)& & \text{Universal Instantiation (11)}\\ & 13.& & \forall x(H(x)\leftrightarrow R(x))& & \text{Premise}\\ & 14.& & H(a)\leftrightarrow R(a)& & \text{Universal Instantiation (13)}\\ & 15.& & H(a)\to R(a)\wedge R(a)\to H(a)& & \text{Equivalence (14)}\\ & 16.& & R(a)\to H(a)& & \text{Simplification (15)}\end{array}$$

Considering $E(a)$ is true, i.e. $a$ is Eden

$$\begin{array}{rlrlrl}& 17.& & E(a)& & \text{Premise}\\ & 18.& & \neg V(a)& & \text{Modus Ponens (2, 17)}\\ & 19.& & CH(a)& & \text{Modus Tollens (4, 18)}\\ & 20.& & M(a)& & \text{Modus Ponens (6, 19)}\\ & 21.& & TA(a)& & \text{Modus Ponens (10, 20)}\\ & 22.& & R(a)& & \text{Modus Ponens (12, 21)}\\ & 23.& & H(a)& & \text{Modus Ponens (16, 22)}\end{array}$$

We can conclude that Eden

• is not a vegetarian
• is a person with curly hair
• is a musician
• is a TA in COMP2711
• reports to the course instructors
• is Kenneth’s hiking mate

2

a

AND

$p$	$q$	$p\overline{\wedge }q$	$(p\overline{\wedge }q)\overline{\wedge }(p\overline{\wedge }q)$	$p\wedge q$	$((p\overline{\wedge }q)\overline{\wedge }(p\overline{\wedge }q))\leftrightarrow (p\wedge q)$
T	T	F	T	T	T
T	F	T	F	F	T
F	T	T	F	F	T
F	F	T	F	F	T

Since $((p\overline{\wedge }q)\overline{\wedge }(p\overline{\wedge }q))\leftrightarrow (p\wedge q)$ is a tautology, they are equivalent

OR

$p$	$q$	$p\overline{\wedge }p$	$q\overline{\wedge }q$	$(p\overline{\wedge }p)\overline{\wedge }(q\overline{\wedge }q)$	$p\vee q$	$((p\overline{\wedge }p)\overline{\wedge }(q\overline{\wedge }q))\leftrightarrow (p\vee q)$
T	T	F	F	T	T	T
T	F	F	T	T	T	T
F	T	T	F	T	T	T
F	F	T	T	F	F	T

Since $((p\overline{\wedge }p)\overline{\wedge }(q\overline{\wedge }q))\leftrightarrow (p\vee q)$ is a tautology, they are equivalent

NOT

$p$	$p\overline{\wedge }p$	$\neg p$	$(p\overline{\wedge }p)\leftrightarrow (\neg p)$
T	F	F	T
F	T	T	T

Since $(p\overline{\wedge }p)\leftrightarrow (\neg p)$ is a tautology, they are equivalent

b

$$\begin{array}{rl}& p\to (q\wedge r)\\ & \equiv \neg p\vee (q\wedge r)\\ & \equiv (p\overline{\wedge }p)\vee (q\wedge r)\\ & \equiv (p\overline{\wedge }p)\vee ((q\overline{\wedge }r)\overline{\wedge }(q\overline{\wedge }r))\\ & \equiv ((p\overline{\wedge }p)\overline{\wedge }(p\overline{\wedge }p))\overline{\wedge }(((q\overline{\wedge }r)\overline{\wedge }(q\overline{\wedge }r))\overline{\wedge }((q\overline{\wedge }r)\overline{\wedge }(q\overline{\wedge }r)))\end{array}$$

c

$$\begin{array}{rl}& (\neg p\vee q)\to ((p\wedge r)\wedge (\neg q\wedge r))\\ & \equiv \neg (\neg p\vee q)\vee ((p\wedge r)\wedge (\neg q\wedge r))\\ & \equiv (p\wedge \neg q)\vee (r\wedge p\wedge \neg q)\\ & \equiv p\wedge \neg q\\ & \equiv p\wedge (q\overline{\wedge }q)\\ & \equiv (p\overline{\wedge }(q\overline{\wedge }q))\overline{\wedge }(p\overline{\wedge }(q\overline{\wedge }q))\end{array}$$

d

$$\begin{array}{rl}& (p\overline{\wedge }(q\overline{\wedge }q))\overline{\wedge }(p\overline{\wedge }(q\overline{\wedge }q))\\ & \equiv p\wedge (q\overline{\wedge }q)\\ & \equiv p\wedge \neg q\end{array}$$

$p$	$q$	$r$	$\neg p$	$\neg q$	$\neg p\vee q$	$p\wedge r$	$\neg q\wedge r$	$(p\wedge r)\wedge (\neg q\wedge r)$	$(\neg p\vee q)\to ((p\wedge r)\wedge (\neg q\wedge r))$	$p\wedge \neg q$
T	T	T	F	F	T	T	F	F	F	F
T	T	F	F	F	T	F	F	F	F	F
T	F	T	F	T	F	T	T	T	T	T
T	F	F	F	T	F	F	F	F	T	T
F	T	T	T	F	T	F	F	F	F	F
F	T	F	T	F	T	F	F	F	F	F
F	F	T	T	T	T	F	T	F	F	F
F	F	F	T	T	T	F	F	F	F	F

Since $((\neg p\vee q)\to ((p\wedge r)\wedge (\neg q\wedge r)))\leftrightarrow (p\wedge \neg q)$ is a tautology, they are logically equivalent

3

a

Let $p$ be the statement $\forall x\exists y(y>2711x)$

Assume $\neg p$, i.e. $\exists x\forall y(y\le 2711x)$

For any $x$, we can always choose $y=2711x+1$, such that $y>2711x$

Therefore $\neg p$ is false

By proof of contradiction, $p$ is true

b

Let $p$ be the statement $\exists x\forall y(x\le y^2)$

Assume $\neg p$, i.e. $\forall x\exists y(x>y^2)$

For $x=-1$, since $y^2\ge 0$, there does not exist a $y$ such that $y^2<x$

Therefore $\neg p$ is false

By proof of contradiction, $p$ is true

4

a

$$\begin{array}{rl}& \neg \forall xP(x)\vee \exists xQ(x)\\ & \equiv \exists x(\neg P(x))\vee \exists xQ(x)\\ & \equiv \exists x(\neg P(x)\vee Q(x))\end{array}$$

b

$$\begin{array}{rl}& \exists xP(x)\to \forall xQ(x)\\ & \equiv \neg \exists xP(x)\vee \forall xQ(x)\\ & \equiv \forall x(\neg P(x))\vee \forall xQ(x)\\ & \equiv \forall x_1(\neg P(x_1))\vee \forall x_{2}Q(x_2)\\ & \equiv \forall x_1\forall x_2(\neg P(x_1)\vee Q(x_2))\end{array}$$

c

$$\begin{array}{rl}& \exists xP(x)\wedge \exists xQ(x)\\ & \equiv \exists x_{1}P(x_1)\wedge \exists x_{2}Q(x_2)\\ & \equiv \exists x_1\exists x_2(P(x_1)\wedge Q(x_2))\end{array}$$

5

a

The answer is $C$

The statement is true if $P(n)$ is true for all integers $n\ge 1$

The statement is false if at least one $P(n)$ is false for any integers $n\ge 1$

b

The answer is $F$

If $P(1)$ is true, then for all integers $n\ge 1$, $P(4n+1)$ is also true, i.e. $P(5),P(9),P(13),P(17),\dots$ is true. Therefore $\exists n(\neg P(4n+1))$ is false and the whole statement is false.

If $P(1)$ is false, the statement is false

c

The answer is $T$

$$\begin{array}{cccc}n& n+1& n+2& n+3\\ n+4& n+5& n+6& n+7\\ n+8& n+9& n+10& n+11\\ ⋮& ⋮& ⋮& ⋮\end{array}$$

The diagram above illustrated how the implication “chained” downward.

If there exists $n$ such that $P(n)$, $P(n+1)$, $P(n+2)$, $P(n+3)$ are all true, then that implies for all $m\ge n$, $P(m+4)$ is true.

d

The answer is $T$

For all $n$, if $P(n)$ is true then there must exists at least one $m\ge n$ that makes $P(m)$ true, i.e. $m=n+4$

e

The answer is $C$

If $P(n)$ is false, the statement is true, since $F$ implies either $T$ or $F$ is true.

If $P(n)$ is true, the statement depends on whether $P(n+1)$, $P(n+2)$, $P(n+3)$ are all true.
If they are all true, then ${\forall }_{m>n}P(m)$ is true (same as part c), and the statement is true.
Otherwise, if any of them are false, ${\forall }_{m>n}P(m)$ is false, then $P(n)\to {\forall }_{m>n}P(m)$ is false, and the statement is false.