Solutions 2 - The Logic of Compound Statements

Entry | Notes

Exercise Set 2.1

Question 1

• $(a+2b)(a^2-b)$ can be written in prefix notation
• All algebraic expressions can be written in prefix notation

---

Question 2

• All numbers are odd; $2$ is odd

---

Question 3

• My mind is shot
• The logic is confusing

---

Question 4

• has $4$ vertices and $6$ edges
• is complete
• it’s complete

---

Question 5

(a) Is an statement.

(b) Is not an statement. (depends on the context)

(c) Is an statement.

(d) Is an statement. (we don’t know $x$)

---

Question 6

(a) $s\wedge i$

(b) $\neg s\wedge \neg i$

---

Question 7

$$m\wedge \neg c$$

---

Question 8

(a) $h\wedge w\wedge \neg s$

(b) $\neg w\wedge h\wedge s$

(c) $\neg w\wedge \neg h\wedge \neg s$

(d) $h\wedge \neg w\wedge \neg s$

(e) $w\wedge \neg (h\wedge s)$

---

Question 9

(a) $p\wedge q$

(b) $r\wedge p$

(c) $r\wedge (p\vee q)$

---

Question 10

(a) $p\wedge q\wedge r$

(b) $p\wedge \neg q$

(c) $p\wedge (\neg q\vee \neg r)$

(d) $\neg p\wedge q\wedge \neg r$

(e) $\neg p\vee (q\wedge r)$

---

Question 11

Both conditions can be true simultaneously. For example, if a team wins games 1, 3, and 4, they have:

• Two games in a row (games 3-4)
• Three total games Therefore it’s inclusive.

---

Question 12

$p$	$q$	$\neg p$	$\neg p\wedge q$
$T$	$T$	$F$	$F$
$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$F$

---

Question 13

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

---

Question 14

$p$	$q$	$r$	$q\wedge r$	$p\wedge (q\wedge r)$
$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$
$T$	$F$	$T$	$F$	$F$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$F$
$F$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$F$
$F$	$F$	$F$	$F$	$F$

---

Question 15

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

---

Question 16

They are logically equivalent; if $p$ is true, therefore $p\vee (p\wedge q)$ is always true, and if it’s false, $p\vee (p\wedge q)$ is always false.

$p$	$q$	$p\wedge q$	$p\vee (p\wedge q)$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$
$F$	$T$	$F$	$F$
$F$	$F$	$F$	$F$

---

Question 17

They are not logically equivalent.

$p$	$q$	$p\wedge q$	$\neg (p\wedge q)$	$\neg p$	$\neg q$	$\neg p\wedge \neg q$
$T$	$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$T$	$F$
$F$	$T$	$F$	$T$	$T$	$F$	$F$
$F$	$F$	$F$	$T$	$T$	$T$	$T$

---

Question 18

They are logically equivalent. The disjucntion of an statement with a tautology is always true, therefore a tautology.

$p$	$p\vee t$
$T$	$T$
$F$	$T$

---

Question 19

They are logically equivalent. The conjuction of an statement with a tautology is logically equivalent with the statement.

$p$	$p\wedge t$
$T$	$T$
$F$	$F$

---

Question 20

They are not logically equivalent. $p\wedge c$ is a contradication, but $p\vee c$ is logically equivalent to $p$.

$p$	$p\wedge c$	$p\vee c$
$T$	$F$	$T$
$F$	$F$	$F$

---

Question 21

They are logically equivalent, due to associative laws.

$p$	$q$	$r$	$p\wedge q$	$(p\wedge q)\wedge r$	$q\wedge r$	$p\wedge (q\wedge r)$
$T$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$T$	$F$
$F$	$T$	$F$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$F$	$F$	$F$	$F$	$F$

---

Question 22

They are logically equivalent, due to distributive laws.

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

---

Question 23

They are not equally equivalent.

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

---

Question 24

They are not equally equivalent.

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

---

Question 25

Hal is not a math major or Hal’s sister is not a computer science major.

---

Question 26

Sam is not an orange belt or Kate is not a red belt.

---

Question 27

The connector is not loose and the machine is plugged.

---

Question 28

The train is not late and my watch is not fast.

---

Question 29

This computer program doesn’t have a logical error in the first ten lines and it is not being run with an incomplete data set.

---

Question 30

The dollar is not at an all-time high or the stock market is not at a record low.

---

Question 31

(a) The first character of $s$ is either $0$ or $1$ and the second character of $s$ is either $1$ or $2$.

(b) The first character if $s$ is neither $0$ nor $1$ and the second character of $s$ is either $1$ or $2$.

(c) The first character is either $1$ or $2$ and the second character is either $0$ or $1$.

---

Question 32

$$x\le -2\text{ or }7\le x$$

---

Question 33

$$x\le -10\text{ or }2\le x$$

---

Question 34

$$2\le x\le 5$$

---

Question 35

$$-1<x\le 1$$

---

Question 36

$$x<-3\text{ or }1\le x$$

---

Question 37

$$x<-7\text{ or }0\le x$$

---

Question 38

$$(\text{num-orders}\le 100\text{ or }\text{num-instock}>500)\text{ and }\text{num-instock}\ge 200$$

---

Question 39

$$\begin{array}{rl}& (\text{num-orders}\ge 50\text{ or }\text{num-instock}\le 300)\text{ and}\\ & ((\text{num-orders}<50\text{ or }\text{num-orders}\ge 75)\text{ or }\text{num-instock}\le 500)\end{array}$$

---

Question 40

It’s a tautology.

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

---

Question 41

It’s a contradiction.

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

---

Question 42

It’s a contradiction.

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

---

Question 43

It’s a tautology.

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

---

Question 44

(a) There is no real number that can satisfy $x>2\text{ and }(x=0\text{ or }x<0)$

(b) There is no real number that can satisfy $(x=1\text{ or }x>1)\text{ and }x<-1$

---

Question 45

Let

• The statement “Bob is a math major” be $p$.
• The statement “Bob is a computer science major” be $q$.
• The statement “Ann is a math major” be $r$.
• The statement “Ann is a computer major” be $s$.

(a) The statement is equivalent to $(p\wedge q)\wedge (r\wedge \neg s)$

(b) The statement is equivalent to $\neg (p\wedge r\wedge q\wedge s)\wedge (r\wedge (p\wedge q))$

In the second statement let $A\equiv (p\wedge q\wedge r)$, therefore the second statement is equivalent to,

$$\neg (s\wedge A)\wedge A\equiv (\neg s\vee \neg A)\wedge A$$

For this statement to be true, $A$ and $(\neg s\vee \neg A)$ must both be true, assuming $A$ as true would make $\neg A$ false, therefore $\neg s$ has to be true. In conclusion, for this statement is logically equivalent to $p\wedge q\wedge r\wedge \neg s$. which is the same as the first statement.

---

Question 46

(a)

• $p\oplus p\equiv (p\vee p)\wedge \neg (p\wedge p)\equiv (p\vee p)\wedge (\neg p\vee \neg p)\equiv p\wedge \neg p\equiv F$
• $(p\oplus p)\oplus p\equiv F\oplus p\equiv (F\vee p)\wedge \neg (F\wedge p)\equiv p\wedge \neg F\equiv p\wedge T\equiv p$

(b) They are logically equivalent.

$p$	$q$	$r$	$p\oplus q$	$(p\oplus q)\oplus r$	$q\oplus r$	$p\oplus (q\oplus r)$
$T$	$T$	$T$	$F$	$T$	$F$	$T$
$T$	$T$	$F$	$F$	$F$	$T$	$F$
$T$	$F$	$T$	$T$	$F$	$T$	$F$
$T$	$F$	$F$	$T$	$T$	$F$	$T$
$F$	$T$	$T$	$T$	$F$	$F$	$F$
$F$	$T$	$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$F$	$F$

(c) They are not logically equivalent.

$p$	$q$	$r$	$p\oplus q$	$(p\oplus q)\oplus r$	$p\wedge r$	$q\wedge r$	$(p\wedge r)\oplus (q\wedge r)$
$T$	$T$	$T$	$F$	$T$	$T$	$T$	$F$
$T$	$T$	$F$	$F$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$F$	$F$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$F$	$F$	$F$
$F$	$F$	$F$	$F$	$F$	$F$	$F$	$F$

---

Question 47

This is asking about English usage where two positive statements combine to create a negative meaning.

Common example: “Yeah, right!”

• When said sarcastically, this means “I don’t believe you” or “That’s not true”
• Both “yeah” and “right” are positive affirmations, but together (with sarcastic tone) they express disbelief

Other examples:

• “Sure, sure” (said dismissively)
• “Of course, of course” (said sarcastically)
• “Absolutely” (said with heavy sarcasm)

The key is that the repetition or tone converts the affirmative into ironic negation.

---

Question 48

• Step (a): Distributive laws
• Step (b): Commutative laws
• Step (c): Negation Laws
• Step (d): Identity Laws

---

Question 49

• Step (a): Commutative laws
• Step (b): Distributive laws
• Step (c): Negation Laws
• Step (d): Identity Laws

---

Question 50

By Absorption Laws:

$$(p\wedge \neg q)\vee p\equiv p$$

---

Question 51

By Absorption Laws:

$$p\wedge (\neg q\vee p)\equiv p$$

---

Question 52

By De Morgan’s Laws:

$$\neg (p\vee \neg q)\vee (\neg p\wedge \neg q)\equiv (\neg p\wedge q)\vee (\neg p\wedge \neg q)$$

By Distributive Laws:

$$\neg (p\vee \neg q)\vee (\neg p\wedge \neg q)\equiv \neg p\wedge (q\vee \neg q)$$

By Negation Laws:

$$\neg (p\vee \neg q)\vee (\neg p\wedge \neg q)\equiv \neg p\wedge T$$

By Identity Laws:

$$\neg (p\vee \neg q)\vee (\neg p\wedge \neg q)\equiv \neg p$$

---

Question 53

By De Morgan’s Laws:

$$\neg ((\neg p\wedge q)\vee (\neg p\wedge \neg q))\vee (p\wedge q)\equiv ((p\vee \neg q)\wedge (p\vee q))\vee (p\wedge q)$$

By Distributive Laws:

$$\neg ((\neg p\wedge q)\vee (\neg p\wedge \neg q))\vee (p\wedge q)\equiv (p\vee (q\wedge \neg q))\vee (p\wedge q)$$

By Negation Laws:

$$\neg ((\neg p\wedge q)\vee (\neg p\wedge \neg q))\vee (p\wedge q)\equiv (p\vee F)\vee (p\wedge q)$$

By Identity Laws:

$$\neg ((\neg p\wedge q)\vee (\neg p\wedge \neg q))\vee (p\wedge q)\equiv p\vee (p\wedge q)$$

By Absorption Laws:

$$\neg ((\neg p\wedge q)\vee (\neg p\wedge \neg q))\vee (p\wedge q)\equiv p$$

---

Question 54

By De Morgan’s Law:

$$(p\wedge (\neg (\neg p\vee q)))\vee (p\wedge q)\equiv (p\wedge (p\wedge \neg q))\vee (p\wedge q)$$

By Associative and Idempotent Laws:

$$(p\wedge (\neg (\neg p\vee q)))\vee (p\wedge q)\equiv (p\wedge \neg q)\vee (p\wedge q)$$

By Distributive Laws:

$$(p\wedge (\neg (\neg p\vee q)))\vee (p\wedge q)\equiv p\wedge (q\vee \neg q)$$

By Negation Laws:

$$(p\wedge (\neg (\neg p\vee q)))\vee (p\wedge q)\equiv p\wedge T$$

By Identity Laws:

$$(p\wedge (\neg (\neg p\vee q)))\vee (p\wedge q)\equiv p$$

Exercise Set 2.2

Question 1

If it doesn’t contain a stop or a to go, then this loop will repeat exactly $N$ times.

---

Question 2

If I catch the 8:05 bus, then I will be on time for work.

---

Question 3

If you don’t freeze I will shoot.

---

Question 4

If you don’t fix my ceiling I will not pay my rent.

---

Question 5

$p$	$q$	$\neg p$	$\neg q$	$\neg p\vee q$	$\neg p\vee q\to \neg q$
$T$	$T$	$F$	$F$	$T$	$F$
$T$	$F$	$F$	$T$	$F$	$T$
$F$	$T$	$T$	$F$	$T$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

---

Question 6

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

---

Question 7

$p$	$q$	$r$	$\neg q$	$p\wedge \neg q$	$p\wedge \neg q\to r$
$T$	$T$	$T$	$F$	$F$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$T$	$F$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$F$	$T$
$F$	$F$	$F$	$T$	$F$	$T$

---

Question 8

$p$	$q$	$r$	$\neg p$	$\neg p\vee q$	$\neg p\vee q\to r$
$T$	$T$	$T$	$F$	$T$	$T$
$T$	$T$	$F$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$F$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$T$	$F$
$F$	$F$	$T$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$F$

---

Question 9

$p$	$q$	$r$	$\neg r$	$p\wedge \neg r$	$q\vee r$	$p\wedge \neg r\leftrightarrow q\vee r$
$T$	$T$	$T$	$F$	$F$	$T$	$F$
$T$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$T$	$F$	$F$	$T$	$F$
$T$	$F$	$F$	$T$	$T$	$F$	$T$
$F$	$T$	$T$	$F$	$F$	$T$	$F$
$F$	$T$	$F$	$T$	$F$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$T$	$F$	$F$	$T$

---

Question 10

$p$	$q$	$r$	$p\to r$	$q\to r$	$(p\to r)\leftrightarrow (q\to r)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$F$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$T$

---

Question 11

$p$	$q$	$r$	$q\to r$	$p\to (q\to r)$	$p\wedge q$	$(p\wedge q)\to r$	$(p\to (q\to r))\leftrightarrow ((p\wedge q)\to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$F$	$T$	$T$

---

Question 12

If $x>2$ then $x^2>4$ and if $x<-2$ then $x^2>4$.

---

Question 13

(a)

$p$	$q$	$\neg p$	$\neg p\vee q$	$p\to q$
$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$T$	$T$

Saying “if A then B” is the same as saying “Not A or B”.

(b)

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

The negation of “if A then B” is “A and not B”.

---

Question 14

(a) Consider $p\to q\vee r$, since $p\to q\equiv \neg p\vee q$, thus

$$p\to q\vee r\equiv \neg p\vee q\vee r$$

By the same logic,

$$\neg p\vee q\vee r\equiv \neg (\neg p\vee q)\to r$$ $$\neg p\vee q\vee r\equiv \neg (\neg p\vee r)\to q$$

Using De Morgan’s law,

$$\neg (\neg p\vee q)\to r\equiv (p\wedge \neg q)\to r$$ $$\neg (\neg p\vee r)\to q\equiv (p\wedge \neg r)\to q$$

(b)

• If $n$ is a prime and $n$ is not odd, then $n$ is $2$.
• If $n$ is a prime and $n$ is not $2$, then $n$ is odd.

---

Question 15

Assume $p\equiv F$, $q\equiv T$ and $r\equiv F$, therefore,

• $p\to (q\to r)\equiv F\to (T\to F)\equiv F\to F\equiv T$
• $(p\to q)\to r\equiv (F\to T)\to F\equiv T\to F\equiv F$

Therefore they are not logically equivalent.

---

Question 16

Let,

• $p$ be “You paid full price”
• $q$ be “You bought it at Crown Books”

Thus,

• First statement: $p\to \neg q$
• Second statement: $\neg q\vee p$

$p$	$q$	$\neg q$	$p\to \neg q$	$\neg q\vee p$
$T$	$T$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$
$F$	$F$	$T$	$T$	$T$

No, they are not logically equivalent.

---

Question 17

Let,

• $p$ be ”$2$ is a factor of $n$”
• $q$ be ”$3$ is a factor of $n$”
• $r$ be ”$6$ is a factor of $n$”

Thus,

• First statement: $p\wedge q\to r$
• Second statement: $\neg p\vee \neg q\vee r$

They are logically equivalent since,

$$p\wedge q\to r\equiv \neg (p\wedge q)\vee r\equiv \neg p\vee \neg q\vee r$$

---

Question 18

Let,

• $p$ be “It walks like a duck.”
• $q$ be “It talks like a duck.”
• $r$ be “It is a duck.”

Thus,

• First statement: $p\wedge q\to r$
• Second statement: $(\neg p\vee \neg q)\vee r$
• Third statement: $\neg p\wedge \neg q\to \neg r$

The first and second statements are logically equivalent since,

$$p\wedge q\to r\equiv \neg (p\wedge q)\vee r\equiv (\neg p\vee \neg q)\vee r$$

But they are not logically equivalent with the first one, assume $p\equiv F$, $q\equiv F$ and $r\equiv T$, thus:

• $p\wedge q\to r\equiv F\wedge F\to T\equiv F\to T\equiv T$
• $\neg p\wedge \neg q\to \neg r\equiv T\wedge T\to F\equiv T\to F\equiv F$

---

Question 19

Let,

• $p$ be “Sue is Luiz’s mother.”
• $q$ be “Ali is his cousin.”

Thus,

• First statement: $p\to q$
• Second statement: $p\to \neg q$

The negation of the first statement would be,

$$\neg (p\to q)\equiv \neg (\neg p\vee q)\equiv p\wedge \neg q$$

Which is not logically equivalent to the second statement,

$$p\to \neg q\equiv \neg p\vee \neg q$$

---

Question 20

(a) $P$ is a square and $P$ is not a rectangle.

(b) Today is New Year’s Eve and tomorrow is not January.

(c) The decimal expansion of $r$ is terminating and $r$ is not rational.

(d) $n$ is prime and $n$ is not odd and $n$ is not $2$.

(e) $x$ is non-negative and $x$ is not positive and $x$ is not $0$.

(f) Tom is Ann’s father and, Jim is not her uncle or Sue is not her aunt.

(g) $n$ is divisible by $6$ and, $n$ is not divisible by $2$ or $n$ is not divisible by $3$.

---

Question 21

Since $p\to q\equiv F$, therefore $p\equiv T$ and $q\equiv F$, thus, (a) $\neg p\to q\equiv \neg T\to F\equiv F\to F\equiv T$

(b) $p\vee q\equiv T\vee F\equiv T$

(c) $q\to p\equiv F\to T\equiv T$

---

Question 22

(a) If $P$ is not a rectangle then $P$ is not a square.

(b) If tomorrow is not January then today is not New Year’s Eve.

(c) If $r$ is not rational then the decimal expansion of $r$ is not terminating.

(d) If $n$ is not odd and $n$ is not $2$ then $n$ is not prime.

(e) If $x$ is not positive and $x$ is not $0$ then it is not non-negative.

(f) If Jim is not her uncle or Sue is not her aunt then Tom is not Ann’s father.

(g) If $n$ is not divisible by $2$ or $n$ is not divisible by $3$ then $n$ is not divisible by $6$.

---

Question 23

(a)

• Converse: If $P$ is a rectangle then $P$ is a square.
• Inverse: If $P$ is not a square then $P$ is not a rectangle.

(b)

• Converse: If tomorrow is January then today is New Year’s Eve.
• Inverse: If today is not New Year’s Eve then tomorrow is not January.

(c)

• Converse: If $r$ is rational then the decimal expansion of $r$ is terminating.
• Inverse: If the decimal expansion of $r$ is not terminating then $r$ is not rational.

(d)

• Converse: If $n$ is odd or $n$ is $2$ then $n$ is prime.
• Inverse: If $n$ is not prime then $n$ is not odd and $n$ is not $2$.

(e)

• Converse: If $x$ is positive or $x$ is $0$ then $x$ is non-negative.
• Inverse: If $x$ is not non-negative then $x$ is not positive and $x$ is not $0$.

(f)

• Converse: If Jim is her uncle and Sue is her aunt then Tom is Ann’s father.
• Inverse: If Tom is not Ann’s father then Jim is not her uncle or Sue is not her aunt.

(g)

• Converse: If $n$ is divisible by $2$ and $n$ is divisible by $3$ then $n$ is divisible by $6$.
• Inverse: If $n$ is not divisible by $6$ then $n$ is not divisible by $2$ or $n$ is not divisible by $3$.

---

Question 24

$p$	$q$	$p\to q$	$q\to p$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$F$
$F$	$F$	$T$	$T$

$$p\to q\cancel{\equiv }q\to p$$

---

Question 25

$p$	$q$	$\neg p$	$\neg q$	$p\to q$	$\neg p\to \neg q$
$T$	$T$	$F$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$T$
$F$	$T$	$T$	$F$	$T$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$$p\to q\cancel{\equiv }\neg p\to \neg q$$

---

Question 26

$p$	$q$	$\neg p$	$\neg q$	$p\to q$	$\neg q\to \neg p$
$T$	$T$	$F$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

$$p\to q\equiv \neg q\to \neg p$$

---

Question 27

$p$	$q$	$\neg p$	$\neg q$	$q\to p$	$\neg p\to \neg q$
$T$	$T$	$F$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$T$	$F$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$$q\to p\equiv \neg p\to \neg q$$

---

Question 28

• The statement “I say what I mean” can be rewritten as “If I mean it then I say it.”
• The statement “I mean what I say” can be rewritten as “If I say it then I mean it.”

Let,

• $p$ be “I say it.”
• $q$ be “I mean it.”

Thus,

• The first statement: $q\to p$
• The second statement: $p\to q$

These statements are converse of each other and are not logically equivalent.

---

Question 29

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

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

---

Question 30

$p$	$q$	$r$	$q\vee r$	$p\wedge (q\vee r)$	$p\wedge q$	$p\wedge r$	$(p\wedge q)\vee (p\wedge r)$	$(p\wedge (q\vee r))\leftrightarrow ((p\wedge q)\vee (p\wedge r))$
$T$	$T$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$T$	$F$	$T$	$T$	$T$	$F$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$F$	$T$	$F$	$F$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$F$	$F$	$F$	$F$	$T$
$F$	$F$	$F$	$F$	$F$	$F$	$F$	$F$	$T$

$$(p\wedge (q\vee r))\leftrightarrow ((p\wedge q)\vee (p\wedge r))\equiv T$$

---

Question 31

$p$	$q$	$r$	$q\to r$	$p\to (q\to r)$	$p\wedge q$	$(p\wedge q)\to r$	$(p\to (q\to r))\leftrightarrow ((p\wedge q)\to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$F$	$T$	$T$

$$(p\to (q\to r))\leftrightarrow ((p\wedge q)\to r)\equiv T$$

---

Question 32

If quadratic equation has two distinct real roots then its discriminant is greater than zero and if its discriminant is greater than zero then the quadratic equation has two distinct real roots.

---

Question 33

If the integer is even then it equals twice some integer and if it equals twice some integer then the integer is even.

---

Question 34

• If The Cubs win the pennant then they win tomorrow’s game.
• If The Cub don’t win tomorrow’s game then they don’t win the pennant.

---

Question 35

• If Sam is allowed on Signe’s racing boat then he is an expert sailor.
• If Sam is not an expert sailor then he is not allowed on Signe’s racing.

---

Question 36

Let

• $p$ be “you major in mathematics.”
• $q$ be “you get a B average or better.”
• $r$ be “you take accounting.”
• $s$ be “you get hired.”

Since $p,q,r\equiv T$ and $s\equiv F$, therefore,

$$s\to p\wedge q\wedge r\equiv F\to T\wedge T\wedge T\equiv F\to T\equiv T$$

Thus, no, the manager has not lied.

---

Question 37

If a new hearing is not granted then payment will be made on the fifth.

---

Question 38

If it does not rain then Ann will go.

---

Question 39

If a security code is not entered then this door will not open.

---

Question 40

If you catch the 8:05 bus then you will be on time for work.

---

Question 41

If a triangle has two $45^{\circ }$ angles then it is a right triangle.

---

Question 42

• If the number is not divisible by $3$ then is not divisible by $9$.
• If it is divisible by $9$ then it is divisible by $3$.

---

Question 43

• If Jim doesn’t do homework regularly then Jim won’t pass the course.
• If Jim passes the course then he has done homework regularly.

---

Question 44

If Jon’s team win the rest of its games then it will win the championship.

---

Question 45

If this computer program produces error messages during translation then it is not correct.

---

Question 46

Let,

• $p$ be “compound X is boiling.”
• $q$ be “its temperature must be at least $150^{\circ }C$.”

Therefore, $p\to q\equiv T$

(a) $q\to p$, it is not logically equivalent to $p\to q\equiv T$, therefore it’s not necessarily true.

(b) $\neg q\to \neg p$, it is logically equivalent to $p\to q\equiv T$, therefore it is true.

(c) $p\to q$, it is true.

(d) $\neg p\to \neg q$, it is not logically equivalent to $p\to q\equiv T$, therefore it’s not necessarily true.

(e) $\neg q\to \neg p$, it is logically equivalent to $p\to q\equiv T$, therefore it is true.

(f) $q\to p$, it is not logically equivalent to $p\to q\equiv T$, therefore it’s not necessarily true.

---

Question 47

(a) $p\wedge \neg q\to r\equiv \neg p\vee q\vee r$

(b) $\neg p\vee q\vee r\equiv \neg (p\wedge \neg q\wedge \neg r)$

---

Question 48

(a) $p\vee \neg q\to r\vee q\equiv (\neg p\wedge q)\vee (r\vee q)\equiv r\vee (q\vee (\neg p\wedge q))\equiv r\vee q$

(b) $r\vee q\equiv \neg (\neg r\wedge \neg q)$

---

Question 49

(a)

$$\begin{array}{rl}(p\to r)\leftrightarrow (q\to r)& \equiv ((p\to r)\to (q\to r))\wedge ((q\to r)\to (p\to r))\\ & \equiv ((p\wedge \neg r)\vee (\neg q\vee r))\wedge ((q\wedge \neg r)\vee (\neg p\vee r))\\ & \equiv ((p\wedge \neg r)\vee \neg q\vee r)\wedge ((q\wedge \neg r)\vee \neg p\vee r)\\ & \equiv (\neg q\vee p\vee r)\wedge (\neg p\vee q\vee r)\text{(since }(A\wedge \neg r)\vee r\equiv A\vee r\text{)}\\ & \equiv r\vee ((p\vee \neg q)\wedge (q\vee \neg p))\end{array}$$

(b)

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

---

Question 50

(a)

$$\begin{array}{rl}& (p\to (q\to r))\leftrightarrow ((p\vee q)\to r)\\ & \equiv [(\neg p\vee (\neg q\vee r))\to ((\neg p\wedge \neg q)\vee r)]\wedge [((\neg p\wedge \neg q)\vee r)\to (\neg p\vee (\neg q\vee r))]\\ & \equiv [((p\wedge q)\wedge \neg r)\vee ((\neg p\wedge \neg q)\vee r)]\wedge [((p\vee q)\wedge \neg r)\vee (\neg p\vee \neg q\vee r)]\\ & \equiv [(p\wedge q)\vee \neg (p\vee q)\vee r]\wedge [(p\vee q)\vee \neg (p\wedge q)\vee r]\text{(since }(A\wedge \neg r)\vee r\equiv A\vee r\text{)}\\ & \equiv r\vee [((p\wedge q)\vee \neg (p\vee q))\wedge (\neg (p\wedge q)\vee (p\vee q))]\\ & \equiv r\vee [((p\wedge q)\vee \neg (p\vee q))\wedge (\neg p\vee \neg q\vee p\vee q)]\\ & \equiv r\vee (p\wedge q)\vee \neg (p\vee q)\end{array}$$

(b)

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

---

Question 51

Since $\leftrightarrow$ and $\to$ can be written in $\neg ,\wedge ,\vee$ form and $\vee$ can be written is $\neg ,\wedge$ form, therefore it is safe to say that any statement can be written in $\neg ,\wedge$ form.

Exercise Set 2.3