## Friday, April 16, 2010

### how to prove it - ch1, sec1.5(the conditional and biconditional connectives) ex

This section introduces the Conditional($\rightarrow$) and the Biconditional($\leftrightarrow$) logical connectives and a form of valid reasoning, which is

$\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 → RG → \lnot RG \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$,$\thereforeW \leftrightarrow P$ W P R$P \land RW ↔ P \land RW ↔ 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 → QQ → PQ → RR → Q(P → Q) \land (Q → R)P ↔ QR ↔ 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)

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

2. 4(a)

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

3. Here's an alternative for 7 a)

(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)]

4. Hi Himanshu! Thanks for these incredibly helpful posts.

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