$\frac{P \rightarrow Q , P}{\therefore Q}$

Another important thing to learn is, what these connectives usually translate in English to, Conditional can translate to

If P then Q

Q, if P

Q, when P

Q unless $\lnot$P

P only if Q

P is a sufficient condition for Q

Q is a necessary condition for P

and Biconditional can translate to

P if and only if Q

P iff Q

P is the necessary and sufficient condition for Q

Some important equivalences...

$P \rightarrow Q$ = $\lnot P \lor Q$ = $\lnot Q \rightarrow \lnot P$ (this last one is known as contrapositive law)

$P \leftrightarrow Q$ = $P \rightarrow Q \land Q \rightarrow P$

=========================================================================================

Ex-1(a)

$S \lor \lnot E \rightarrow \lnot H$ where

S = Unpleasant smell

E = Explosive

H = Hydrogen

Ex-1(b) $F \land H \rightarrow D$

Ex-1(c) $F \lor H \rightarrow D$

= $\lnot(F \lor H) \lor D$

= $(\lnot F \land \lnot H) \lor D$

= $(\lnotF \lor D) \land (\lnot H \lor D)$

= $(F \rightarrow D) \land (H \rightarrow D)$

Ex-1(d) $A \rightarrow (O \rightarrow P)$ or $(A \land O) \rightarrow P$

A means $x \neq 2$

O means x is odd

P means x is prime

Ex-2(a) $S \rightarrow P \land A$

S means, Marry will sell her house

P means, she can get a good price

A means, she finds a nice apartment

Ex-2(b) $M \rightarrow C \land D$

C means, having a good credit history

D means, an adequate down payment

M means, getting the mortgate

Ex-2(c) Given sentence is equivalent to, If someone does not stop John then he'll kill himself. Its logical form is.. $\lnot S \rightarrow K$

where S means, someone stops john and

K means, john kills himself

Ex-2(d) $D(x,4) \lor D(x,6) \rightarrow \lnot P(x)$

where D(x,y) means, x is divisible by y and

P(x) means x is prime

Ex-3

(a) $R \rightarrow W \land \lnot S$

R means, its raining

W means, its windy

S means, sun is shining

(b) $W \land \lnot S \rightarrow R$ , clearly its the converse of (a)

(c) $R \rightarrow W \land \lnot S$, its same as (a)

(d) $W \land \lnot S \rightarrow R$ , clearly its the converse of (a)

(e) $S \lor \lnot W \rightarrow \lnot R$

= $\lnot(\lnot S \land W) \rightarrow \lnot R$

= $R \rightarrow \lnot S \land W$

= $R \rightarrow W \land \lnot S$ , same as (a)

(f) $(R \rightarrow W) \land (R \rightarrow \lnot S)$

= $(\lnot R \lor W) \land (\lnot R \lor \lnot S)$

= $((\lnot R \lor W) \land \lnot R) \lor ((\lnot R \lor W) \land \lnot S))$

= $\lnot R \lor ((\lnot R \lor W) \land \lnot S))$

= $\lnot R \lor ((\lnot R \land \lnot S) \lor (W \land \lnot S))$

= $(\lnot R \lor (\lnot R \land \lnot S)) \lor (W \land \lnot S)$

= $\lnot R \lor (W \land \lnot S)$

= $R \rightarrow W \land \lnot S$, same as (a)

(g) $(W \rightarrow R) \lor (\lnot S \rightarrow R)$

= $(\lnot W \lor R) \lor (S \lor R)$

= $(\lnot W \lor S) \lor (R \lor R)$

= $\lnot(W \land \lnot S) \lor R$

= $W \land \lnot S \rightarrow R$, converse of (a)

Ex-4(a)

S means, Sales will go up

E means, Expenses will go up

H means, Boss will be Happy

Logical form of given statement is $(S \lor E) \land (S \rightarrow H) \land (E \rightarrow \lnot H)$ and $\therefore$ $\lnot (S \land E)$

S | E | H | $S \lor E$ | $S → H$ | $E → \lnot H$ | $(S \lor E) \land (S → H) \land (E → \lnot H)$ | $\lnot(S \land E) |

F | F | F | F | T | T | F | T |

T | F | F | T | F | T | F | T |

F | T | F | T | T | T | T | T |

T | T | F | T | F | T | F | F |

F | F | T | F | T | T | F | T |

T | F | T | T | T | T | T | T |

F | T | T | T | T | F | F | T |

T | T | T | T | T | F | F | F |

Clearly all the places where $(S \lor E) \land (S \rightarrow H) \land (E \rightarrow \lnot H)$ is T, $\lnot (S \land E)$ is also T . So, $\lnot (S \land E)$ can be inferred from $(S \lor E) \land (S \rightarrow H) \land (E \rightarrow \lnot H)$ and the argument is valid.

Ex-4(b)

X means, Tax rate goes up

U means, Unemployment rate goes up

R means, there will be a recession

G means, GNP goes up

logical form of the given statement is $(X \land U \rightarrow R) \land (G \rightarrow \lnot R) \land (G \land X)$, $\therefore$ $\lnot U$

X | U | R | G | $X \land U → R$ | $G → \lnot R$ | $G \land X$ | $(X \land U → R) \land (G → \lnot R) \land (G \land X)$ | $\lnot U$ |

F | F | F | F | T | T | F | F | T |

T | F | F | F | T | T | F | F | T |

F | T | F | F | T | T | F | F | F |

T | T | F | F | F | T | F | F | F |

F | F | T | F | T | T | F | F | T |

T | F | T | F | T | T | F | F | T |

F | T | T | F | T | T | F | F | F |

T | T | T | F | T | T | F | F | F |

F | F | F | T | T | T | F | F | T |

T | F | F | T | T | T | T | T | T |

F | T | F | T | T | T | F | F | F |

T | T | F | T | F | T | T | F | F |

F | F | T | T | T | F | F | F | T |

T | F | T | T | T | F | T | F | T |

F | T | T | T | T | F | F | F | F |

T | T | T | T | T | F | T | F | F |

using the same argument as earlier, its a valid argument.

Ex-4(c)

W means, Warning light will come on

P means, Pressure is too high

R means, Relief valve is clogged

logical form is $(W \leftrightarrow P \land R) \land \lnot R$ , $\therefore$ $W \leftrightarrow P$

W | P | R | $P \land R$ | $W ↔ P \land R$ | $W ↔ P$ |

F | F | F | F | T | T |

T | F | F | F | F | F |

F | T | F | F | T | F |

T | T | F | F | F | T |

F | F | T | F | T | T |

T | F | T | F | F | F |

F | T | T | T | F | F |

T | T | T | T | T | T |

we can see an inconsistency at line 3, so its not a valid argument.

Ex-5(a) $P \leftrightarrow Q$

= $(P \rightarrow Q) \land (Q \rightarrow 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 (Q \land P)$

= $(P \land Q) \lor (\lnot P \land \lnot Q)$

Ex-5(b) $(P \rightarrow Q) \lor (P \rightarrow R)$

= $(\lnot P \lor Q) \lor (\lnot P \lor R)$

= $(\lnot P \lor \lnot P) \lor (Q \lor R)$

= $\lnot P \lor (Q \lor R)$

= $P \rightarrow (Q \lor R)$

Ex-6(a) $(P \rightarrow R) \land (Q \rightarrow R)$

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

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

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

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

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

= $(\lnot(P \lor Q)) \lor R$

= $P \lor Q \rightarrow R$

Ex-6(b) $(P \rightarrow R) \lor (Q \rightarrow R)$ = $P \land Q \rightarrow R$

Here is the proof...

$(P \rightarrow R) \lor (Q \rightarrow R)$

= $(\lnot P \lor R) \lor (\lnot Q \lor R)$

= $(\lnot P \lor \lnot Q) \lor (R \lor R)$

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

= $P \land Q \rightarrow R$

Ex-7(a)

P | Q | R | $P → Q$ | $Q → P$ | $Q → R$ | $R → Q$ | $(P → Q) \land (Q → R)$ | $P ↔ Q$ | $R ↔ Q$ | $(P ↔ Q) \lor (R ↔ Q)$ | $P → R$ | $(P → R) \land ((P ↔ Q) \lor (R ↔ Q))$ |

F | F | F | T | T | T | T | T | T | T | T | T | T |

T | F | F | F | T | T | T | F | F | T | T | F | F |

F | T | F | T | F | F | T | F | F | F | F | T | F |

T | T | F | T | T | F | T | F | T | F | T | F | F |

F | F | T | T | T | T | F | T | T | F | T | T | T |

T | F | T | F | T | T | F | F | F | F | F | T | F |

F | T | T | T | F | T | T | T | F | T | T | T | T |

T | T | T | T | T | T | T | T | T | T | T | T | T |

Match column 8 and 13, clearly both are same.

Ex-7(b)

$(P \rightarrow Q) \lor (Q \rightarrow R)$

= $(\lnot P \lor Q) \lor (\lnot Q \lor R)$

= $\lnot P \lor (Q \lor \lnot Q) \lor R$

= $\lnot P \lor (TRUE) \lor R$

= TRUE

Ex-8 $P \land Q$

= $\lnot(\lnot P \lor \lnot Q)$

= $\lnot(P \rightarrow \lnot Q)$

Ex-9 $P \leftrightarrow Q$

= $(P \rightarrow Q) \land (Q \rightarrow P)$ , now using Ex-8

= $\lnot((P \rightarrow Q) \rightarrow \lnot(Q \rightarrow P))$

Ex-10

(a) $P \rightarrow (Q \rightarrow R)$

= $\lnot P \lor (\lnot Q \lor R)$

= $\lnot P \lor \lnot Q \lor R$

(b) $Q \rightarrow (P \rightarrow R)$

= $\lnot Q \lor (\lnot P \lor R)$

= $\lnot Q \lor \lnot P \lor R$

= $\lnot P \lor \lnot Q \lor R$ , clearly its same as (a)

(c) $(P \rightarrow Q) \land (P \rightarrow R)$

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

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

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

= $\lnotP \lor (\lnot P \land R) \lor (Q \land R)$

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

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

we've reduced original form to disjunctive normal form(disjunction of conjunctions) here

(d) $(P \land Q) \rightarrow R$

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

= $\lnot P \lor \lnot Q \lor R$

clearly its same as (a) and (b)

(e) $P \rightarrow (Q \land R)$

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

clearly its same as (c)

for question 4A how did you come up with that logical statement?

ReplyDelete4(a)

ReplyDeleteS means, Sales will go up

E means, Expenses will go up

H means, Boss will be Happy

From the question, take each sentence one by one..

Either sales or expenses will go up: $(S \lor E)$

If sales go up then boss will be happy: $(S \rightarrow H)$

If expenses go up then boss will be unhappy: $(E \rightarrow \lnot H)$

Since question means to say all of the above, so we take the conjunction of all of the above logical statements to get $(S \lor E) \land (S \rightarrow H) \land (E \rightarrow \lnot H)$

therefore sales and expenses will not both go up, meaning(yes, there is scope of ambiguity here I guess) Both of them together will not go up..so.. not of (both sales and expense going up together): $\lnot (S \land E)$

Now, to be honest, I can't really remember how I came up with it but maybe I did reverse engineer a little bit.

Here's an alternative for 7 a)

ReplyDelete(P→Q)∧(Q→R)=

(P→Q)∧(Q→R)∧[(R∨¬R)∨(¬P∨P)]

(P→Q)∧(Q→R)∧[(¬P∨R)∨(P∨¬R)]

(P→Q)∧(Q→R)∧[(¬P∨R)∨(P∨(¬Q∧Q)∨¬R)]

(P→Q)∧(Q→R)∧[(¬P∨R)∨(¬Q∨P)∧(¬R∨Q)]

(P→Q)∧(Q→R)∧(P→R)∨(Q→P)∧(R→Q)

(P→R)∧(P→Q)∧(Q→P)∨(Q→R)∧(R→Q)

(P→R)∧[P↔Q)∨(R↔Q)]

Hi Himanshu! Thanks for these incredibly helpful posts.

ReplyDeleteOn Exercise 1.d. shouldn't the correct logical form be A ∧ P → O. Disregarding A for instance, O is by no means sufficient condition for P.