# How to Prove It - Solutions

## Chapter - 1, Sentential Logic

### Section - 1.5 - The Conditional and Biconditional Connectives

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)

$S$ $E$ $B$ $S \lor E$ $S \to B$ $E \to \lnot B$ $\lnot (S \land E)$
true true true true true false false
true true false true false true false
true false true true true true true
true false false true false true true
false true true true true false true
false true false true true true true
false false true false true true true
false false false false true true true

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)

$T$ $U$ $G$ $R$ $T \land U$ $(T \land U) \to R$ $G \to \lnot R$ $G \land T$ $\lnot U$
true true true true true true false true false
true true true false true false true true false
true true false true true true true false false
true true false false true false true false false
true false true true false true false true true
true false true false false true true true true
true false false true false true true false true
true false false false false true true false true
false true true true false true false false false
false true true false false true true false false
false true false true false true true false false
false true false false false true true false false
false false true true false true false false true
false false true false false true true false true
false false false true false true true false true
false false false false false true true false true

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.

$W$ $P$ $R$ $W \leftrightarrow (P \land R)$ $\lnot R$ $W \leftrightarrow P$
true true true true false true
true true false false true true
true false true false false false
true false false false true false
false true true false false false
false true false true true false
false false true true false true
false false false true true true

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