$\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.