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















SEH$S \lor E$$S → H$$E → \lnot H$$(S \lor E) \land (S → H) \land (E → \lnot H)$$\lnot(S \land E)
FFFFTTFT
TFFTFTFT
FTFTTTTT
TTFTFTFF
FFTFTTFT
TFTTTTTT
FTTTTFFT
TTTTTFFF


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$























XURG$X \land U → R$$G → \lnot R$$G \land X$$(X \land U → R) \land (G → \lnot R) \land (G \land X)$$\lnot U$
FFFFTTFFT
TFFFTTFFT
FTFFTTFFF
TTFFFTFFF
FFTFTTFFT
TFTFTTFFT
FTTFTTFFF
TTTFTTFFF
FFFTTTFFT
TFFTTTTTT
FTFTTTFFF
TTFTFTTFF
FFTTTFFFT
TFTTTFTFT
FTTTTFFFF
TTTTTFTFF


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$















WPR$P \land R$$W ↔ P \land R$$W ↔ P$
FFFFTT
TFFFFF
FTFFTF
TTFFFT
FFTFTT
TFTFFF
FTTTFF
TTTTTT


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)














PQR$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))$
FFFTTTTTTTTTT
TFFFTTTFFTTFF
FTFTFFTFFFFTF
TTFTTFTFTFTFF
FFTTTTFTTFTTT
TFTFTTFFFFFTF
FTTTFTTTFTTTT
TTTTTTTTTTTTT


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)

4 comments:

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

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

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



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

    ReplyDelete