How to Prove It - Solutions

This post contains solutions of Chapter - 1, Section - 1.5, The Conditional and Biconditional Connectives from Velleman’s book How To Prove It.

Summary

• $P \to Q$ is equivalent to :
  • $\lnot P \lor Q$.
  • $\lnot ( P \land \lnot Q)$.
• $P \to Q$ and $Q \to P$ are not equivalent. They are called converse of each other.
• $P \to Q$ and $\lnot Q \to \lnot P$ are equivalent. They are called contrapositive of each other.
• $P \to Q$ is equivalent to following:
  • $P$ implies $Q$.
  • $Q$, if $P$.
  • $P$, only if $Q$.
  • $P$ is a sufficient condition for $Q$.
  • $Q$ is necessary condition for $P$.
• $P \leftrightarrow Q$ is equivalent to $(P \to Q) \land (Q \to P)$. Thus it means:
  • $P$ is a necessary and sufficient condition for $Q$.
  • $P\,iff\,Q$.

Solutions

Soln1

(a)

$P$ Gas has pleasant smell.
$E$ Gas is explosive. $H$ Gas is hydrogen.

$(\lnot P \lor \lnot E) \to \lnot G$. This is equivalent to $\lnot (P \land E) \to \lnot H$ which is equivalent to $H \to (P \land Q)$.

(b)

$F =$ Fever, $H =$ Headache, $D =$ Doctor.
$(F \land H) \to D$.

(c) $(F \to D) \land (H \to D)$.

(d) $(x != 2) \to (P(x) \to O(x))$, where $P(x)$ is “x is prime” and $O(x)$ is “x is odd”.

Soln2

(a)

$G =$ Good Price, $N =$ Nice Apartment, $S =$ Sell house.

$S \to (G \land N)$.

(b)

$G =$ Good Credit History, $A =$ Adequate down payment, $M$ Getting mortgage.

$M \to (G \land A)$.

(c)

If someone not stops John then he will kill himself. $\lnot S \to K$.

(d) $D(x,4) \lor D(x,6) \to \lnot P(x)$, where $D(x,y)$ means “ x is divisible by y”, $P(x)$ means x is prime.

Soln3

$R =$ Raining, $W =$ Windy, $S =$ Shining.

(a) $R \to (W \land \lnot S)$.

(b) $(W \land \lnot S) \to R$. It is converse of (a).

(c) $R \to (W \land \lnot S)$. It is equivalent to (a).

(d) $(W \land \lnot S) \to R$. It is converse of (a).

(e) $(S \lor \lnot W) \to \lnot R$. It is same as $\lnot (\lnot S \land W) \to \lnot R$. It is equivalent to (a).

(f) $(R \to W) \land (R \to \lnot S)$. It is equivalent to $R \to (W \land \lnot S)$. It is equivalent to (a).

(g) $(W \to R) \lor (\lnot S \to R)$. IT is equivalent to $(W \land \lnot S) \to R$. It is converse of (a).

Soln4

(a)

From the table when all premises : $( S \lor E),\,(S \to B),\,(E \to \lnot B)$ are true then conclusion, $\lnot (S \land E)$ is also true.

(b)

It can be seen that when all premises are true then conclusion is also true. Thus argument is valid.

(c)

$W =$ Warning Light is on, $P =$ Pressure is too high, $R =$ Relief valve is clogged.

It can be seen that in one row above, when all premises are true, then corr. conclusion is not true. Thus argument is not valid.

Soln5

(a)

$P \leftrightarrow Q$ is equivalent to
$\; = (P \to Q) \land (Q \to P)$
$\; = (\lnot P \lor Q) \land (\lnot Q \lor P)$
$\; = ((\lnot P \lor Q) \land \lnot Q) \lor ((\lnot P \lor Q) \land P)$
$\; = ((\lnot P \land \lnot Q) \lor (Q \land \lnot Q)) \lor ((\lnot P \land P) \lor (Q \land P))$
$\; = ((\lnot P \land \lnot Q) \lor false) \lor (false \lor (Q \land P))$
$\; = (\lnot P \land \lnot Q) \lor (Q \land P)$
$\; = (P \land Q) \lor (\lnot P \land \lnot Q)$

(b)

$(P \to Q) \lor (P \to R)$
$\quad = (\lnot P \lor Q) \lor (\lnot P \lor R)$
$\quad = \lnot P \lor (Q \lor R)$
$\quad = P \leftrightarrow (Q \lor R)$.

Soln6

(a)

$(P \to R) \land (Q \to R)$
$\quad = (\lnot P \lor R) \land (\lnot Q \lor R)$
$\quad = (\lnot P \land \lnot Q) \lor R$
$\quad = \lnot ( P \lor Q) \lor R$
$\quad = ( P \lor Q) \to R$.

(b)

$(P \to R) \lor (Q \to R)$
$\quad = (\lnot P \lor R) \lor (\lnot Q \lor R)$
$\quad = (\lnot P \lor \lnot Q) \lor R$
$\quad = \lnot ( P \land Q) \lor R$
$\quad = ( P \land Q) \to R$.

Soln7

(a)

RHS:

$(P \to R) \land [(P \leftrightarrow Q) \lor (R \leftrightarrow Q)]$
$\quad = ( P \to R )(((P \land Q) \lor (\lnot P \land \lnot Q)) \lor ((R \land Q) \lor (\lnot R \land \lnot Q)))$
$\quad = ( P \to R )(((P \land Q) \lor (R \land Q)) \lor ((\lnot P \land \lnot Q) \lor (\lnot R \land \lnot Q)))$
$\quad = ( P \to R )(((P \land Q) \lor (R \land Q)) \lor ((\lnot P \land \lnot Q) \lor (\lnot R \land \lnot Q)))$
$\quad = ( \lnot P \lor R )(((P \lor R) \land Q) \lor ((\lnot P \lor \lnot R) \land \lnot Q))$
$\quad = (( \lnot P \lor R ) \land (P \lor R) \land Q) \lor (( \lnot P \lor R ) \land (\lnot P \lor \lnot R) \land \lnot Q)$
$\quad = ((( \lnot P \land P ) \lor R) \land Q) \lor ((( R \lor \land R) \lor \lnot P) \land \lnot Q)$
$\quad = ((R) \land Q) \lor ((\lnot P) \land \lnot Q)$
$\quad = (R \land Q) \lor (\lnot P \land \lnot Q)$
$\quad = ((R \land Q) \lor \lnot P) \land ((R \land Q) \lor \lnot Q)$
$\quad = ((R \lor \lnot P) \land (Q \lor \lnot P)) \land ((R \lor \lnot Q) \land (Q \lor \lnot Q))$
$\quad = ((R \lor \lnot P) \land (Q \lor \lnot P)) \land ((R \lor \lnot Q))$
$\quad = (R \lor \lnot P) \land (Q \lor \lnot P) \land (R \lor \lnot Q)$
$\quad = (R \lor \lnot P) \land (\lnot P \lor Q) \land (R \lor \lnot Q)$

Consider:

• In above equation, Q is present two times, $(\lnot P \lor Q)$ and $(R \lor \lnot Q)$.
• The equation will be true when all of the terms $(R \lor \lnot P)$ and $(\lnot P \lor Q)$ and $(R \lor \lnot Q)$ are true.
• That means $(\lnot P \lor Q)$ and $(R \lor \lnot Q)$ should be true. Here $Q$ is present in both terms, $Q$ and $\lnot Q$. So for both terms to become true, $\lnot P$ and $R$ must be true.
• Thus we have from the two terms containing $Q$, that $(R \lor \lnot P)$ must be true, for these two terms to become true.
• That means we can safely remove the term $(R \lor \lnot P)$ from the equation as it will be true if next two terms are also true.

Thus we have:

$\quad = (\lnot P \lor Q) \land (R \lor \lnot Q)$
$\quad = (\lnot P \lor Q) \land (\lnot Q \lor R)$
$\quad = ( P \to Q) \land ( Q \to R)$ = LHS.

(b)

$(P \to Q) \lor (Q \to R)$
$\quad = (\lnot P \lor Q) \lor (\lnot Q \lor R)$
$\quad = \lnot P \lor Q \lor \lnot Q \lor R$
$\quad = \lnot P \lor true \lor R$
$\quad = true$.

Soln8

$P \to Q = \lnot (P \land \lnot Q)$
$\quad \Rightarrow P \to Q = \lnot (P \land \lnot Q)$
$\quad \Rightarrow \lnot (P \land \lnot Q) = P \to Q$
$\quad \Rightarrow (P \land \lnot Q) = \lnot (P \to Q)$
$\quad \Rightarrow (P \land Q) = \lnot (P \to \lnot Q)$.

Soln9

$P \leftrightarrow Q = (P \to Q) \land (Q \to P)$
Using Soln8,
$\quad \Rightarrow P \leftrightarrow Q = \lnot((P \to Q) \to \lnot (Q \to P))$.

Soln10

(a)

$P \to (Q \to R)$
$\quad = \lnot P \lor (\lnot Q \lor R)$
$\quad = \lnot P \lor \lnot Q \lor R$.

(b)

$Q \to (P \to R) = \lnot Q \lor \lnot P \lor R$. This is equivalent to (a).

(c)

$(P \to Q) \land (P \to R)$
$\quad = (\lnot P \lor Q) \land (\lnot P \lor R)$
$\quad = \lnot P \lor (Q \land R)$

(d)

$(P \land Q) \to R$
$\quad = \lnot (P \land Q) \lor R$
$\quad = (\lnot P \lor \lnot Q) \lor R$
$\quad = \lnot P \lor \lnot Q \lor R$. This is equivalent to (a).

(e)

$P \to (Q \land R)$
$\quad = \lnot P \lor (Q \land R)$. This is equivalent to (c).