Tuesday, April 13, 2010

how to prove it - ch1, sec1.2 ex

Validity:To prove validity of an argument of the form $premises \Rightarrow conclusion$ we need to create the truth table and see that all the cases where premises are true, conclusion must be true.

Tautology: A statement that is always true.

Contradiction: A statement that is always false.

This section also introduces various equivalences such as DeMorgan's laws, Commutative laws, Associative laws, Idempotent laws, Distributive laws, Double Negation law and Absorption laws($P \lor (P \land Q) \equiv P$ and $P \land (P \lor Q) \equiv P$)

There are two ways to prove the equivalence of two complex logical statements.
  1. Draw truth tables for both and see if they are exactly the same.
  2. Use equivalence relations described above to see if one can be transformed into other


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

Ex-1(a)










PQ$\lnot P$$\lnot P \lor Q$
FFTT
TFFF
FTTT
TTFT



Ex-1(b)










SG$\lnot S$$\lnot G$$S \lor G$$\lnot S \lor \lnot G$$(S \lor G) ∧ (\lnot S \lor \lnot G)$
FFTTFTF
TFFTTTT
FTTFTTT
TTFFTFF



Ex-2(a)










PQ$\lnot P$$(Q \lor \lnot P)$$P \land (Q \lor \lnot P)$$\lnot (P \land (Q \lor \lnot P))$
FFTTFT
TFFFFT
FTTTFT
TTFTTF


Ex-2(b)














PQR$\lnot P$$P \lor Q$$\lnot P \lor R$$(P \lor Q) \land (\lnot P \lor R)$
FFFTFTF
TFFFTFF
FTFTTTT
TTFFTFF
FFTTFTF
TFTFTTT
FTTTTTT
TTTFTTT


Ex-3(a) '+' denotes exclusive or










PQP+Q
FFF
TFT
FTT
TTF


Ex-3(b)
In general, to find the formula from truth table, take the rows where the output of unknown formula is T, for each such row take negation/conjunction of input propositions in such a way that they produce T and then take disjunction of them all.

For above truth table, P+Q is T for 2 cases
1. P = T, Q = F : this suggests $P \land \lnot Q$
2. P = F, Q = T : this suggests $\lnot P \land Q$

taking disjunction of above 2, we get
$(P \land \lnot Q) \lor (\lnot P \land Q)$

Let us see the truth table for this:










PQ$\lnot P$$\lnot Q$$P \land \lnot Q$$\lnot P \land Q$$(P \land \lnot Q) \lor (\lnot P \land Q)$
FFTTFFF
TFFTTFT
FTTFFTT
TTFFFFF


Ex-4
Using DeMorgan's law we can easily see that $P \lor Q \equiv \lnot(\lnot P \land \lnot Q)$ . Let us justify it with the truth table.











PQ$\lnot P$$\lnot Q$$\lnot P \land \lnot Q$$\lnot(\lnot P \land \lnot Q)$$P \lor Q$
FFTTTFF
TFFTFTT
FTTFFTT
TTFFFTT


Ex-5(a)
$\downarrow$ means nor(not or)










PQ$P ↓ Q$
FFT
TFF
FTF
TTF


Ex-5(b)
Its easily seen that it is NOT OR that is $\lnot (P \lor Q)$

Ex-5(c)
$\lnot P \equiv (P \downarrow P)$
$P \lor Q \equiv \lnot(P \downarrow Q) \equiv (P \downarrow Q) \downarrow (P \downarrow Q)$
$P \land Q \equiv \lnot(\lnot P \lor \lnot Q) \equiv \lnot P \downarrow \lnot Q \equiv (P \downarrow P) \downarrow (Q \downarrow Q)$

Ex-6(a)
| means nand (Not And)










PQP|Q
FFT
TFT
FTT
TTF


Ex-6(b) $\lnot(P \land Q)$

Ex-6(c)
$\lnot P \equiv P|P$
$P \lor Q \equiv \lnot(\lnot P \land \lnot Q) \equiv \lnot P | \lnot Q \equiv (P|P)|(Q|Q)$
$P \land Q \equiv \lnot(\lnot(P \land Q)) \equiv \lnot(P|Q) \equiv (P|Q)|(P|Q)$

Ex-7(a)














JmPmPc$Jm \land Pm$$\lnot(Jm \land Pm)$$Pm \lor Pc$
FFFFTF
TFFFTF
FTFFTT
TTFTFT
FFTFTT
TFTFTT
FTTFTT
TTTTFT

clearly the argument is valid.

Ex-7(b)






















BFPC$B \lor F$$P \lor C$$F \land C$$\lnot(F \land C)$$B \land P$$\lnot(B \land P)$
FFFFFFFTFT
TFFFTFFTFT
FTFFTFFTFT
TTFFTFFTFT
FFTFFTFTFT
TFTFTTFTTF
FTTFTTFTFT
TTTFTTFTTF
FFFTFTFTFT
TFFTTTFTFT
FTFTTTTFFT
TTFTTTTFFT
FFTTFTFTFT
TFTTTTFTTF
FTTTTTTFFT
TTTTTTTFTF

clearly argument is not valid at row # 6

Ex-7(c)














JBS$\lnot B$$\lnot S$$J \lor B$$\lnot S \lor \lnot B$$J \lor \lnot S$
FFFTTFTT
TFFTTTTT
FTFFTTTT
TTFFTTTT
FFTTFFTF
TFTTFTTT
FTTFFTFF
TTTFFTFT

clearly argument is valid.

Ex-7(d)














SBE$\lnot B$$S \land B$$E \land \lnot B$$(S \land B) \lor (E \land \lnot B)$$S \land E$$\lnot(S \land E)$
FFFTFFFFT
TFFTFFFFT
FTFFFFFFT
TTFFTFTFT
FFTTFTTFT
TFTTFTTTF
FTTFFFFFT
TTTFTFTTF

clearly argument is not valid at row # 6 and 8.

Ex-8










PQ$\lnot P$$\lnot Q$$P \land Q$$\lnot P \land \lnot Q$a = $(P \land Q) \lor (\lnot P \land \lnot Q)$b = $\lnot P \lor Q$$P \lor \lnot Q$$Q \lor \lnot P$c = $(P \lor \lnot Q) \land (Q \lor \lnot P)$d = $\lnot(P \lor Q)$$Q \land P$e = $(Q \land P) \lor \lnot P$
FFTTFTTTTTTTFT
TFFTFFFFTFFFFF
FTTFFFFTFTFFFT
TTFFTFTTTTTFTT

clearly a $\equiv$ c and b $\equiv e$ and d is equivalent to none

Ex-9










PQ$\lnot P$$\lnot Q$$P \lor Q$$\lnot P \lor \lnot Q$a = $(P \lor Q)\land (\lnot P \lor \lnot Q)$$\lnot P \land \lnot Q$b = $(P \lor Q)\land (\lnot P \land \lnot Q)$c = $(P \lor Q)\lor (\lnot P \lor \lnot Q)$
FFTTFTFTFT
TFFTTTTFFT
FTTFTTTFFT
TTFFTFFFFT


clearly a is none, b is contradiction and c is tautology















PQR$\lnot P$$\lnot R$$Q \lor \lnot R$$P \land (Q \lor \lnot R)$$\lnot P \lor R$d = $(P \land (Q \lor \lnot R)) \lor (\lnot P \lor R)$
FFFTTTFTT
TFFFTTTFT
FTFTTTFTT
TTFFTTTFT
FFTTFFFTT
TFTFFFFTT
FTTTFTFTT
TTTFFTTTT

clearly d is tautology.

Ex-10 Its trivial, pass.

Ex-11(a)
$\lnot(\lnot P \land \lnot Q)$
= $\lnot\lnot P \lor \lnot\lnot Q$ ...DeMorgan's Law
= $P \lor Q$ ...Double Negation Law

Ex-11(b)
$(P \land Q) \lor (P \land \lnot Q)$
= $((P \land Q) \lor P) \land ((P \land Q) \lor \lnot Q))$ ...Distribution Law
= $P \land ((P \land Q) \lor \lnot Q))$ ...Absorption Law
= $P \land ((P \lor \lnot Q) \land (Q \lor \lnot Q))$ ...Distribution Law
= $P \land (P \lor \lnot Q)$
= $P$ ...Absorption law

Ex-11(c)
$\lnot (P \land \lnot Q) \lor (\lnot P \land Q)$
= $(\lnot P \lor Q) \lor (\lnot P \land Q)$ ...DeMorgan's and then Double Negation law
= $((\lnot P \lor Q) \lor \lnot P) \land (\lnot P \lor Q) \lor Q))$ ...Distribution law
= $((\lnot P \lor \lnot P) \lor Q) \land (\lnot P \lor (Q \lor Q))$ ...Commutative and Associative laws
= $(\lnot P \lor Q) \land (\lnot P \lor Q)$ ...Idempotent law
= $\lnot P \lor Q$ ...Idempotent law

Ex-12(a)
$\lnot(\lnot P \lor Q) \lor (P \land \lnot R)$
= $(P \land \lnot Q) \lor (P \land \lnot R)$ ...DeMorgan's, Double Negation law
= $((P \land \lnot Q) \lor P) \land ((P \land \lnot Q) \lor \lnot R)$ ...Distribution law
= $P \land ((P \land \lnot Q) \lor \lnot R)$ ...Absorption law
= $(P \land (P \land \lnot Q)) \lor (P \land \lnot R)$ ...Distribution law
= $(P \land \lnot Q) \lor (P \land \lnot R)$ ...Associative, Idempotent law


Ex-12(b)
$\lnot(\lnot P \land Q) \lor (P \land \lnot R)$
= $(P \lor \lnot Q) \lor (P \land \lnot R)$ ...DeMorgan's, Double Negation law
= $((P \lor \lnot Q) \lor P) \land ((P \lor \lnot Q) \lor \lnot R)$ ...Distribution law
= $(P \lor \lnot Q) \land ((P \lor \lnot Q) \lor \lnot R)$ ...Commutative,Associative law
= $P \lor \lnot Q$ ...Absorption law

Ex-12(c)
$(P \land R) \lor (\lnot R \land (P \lor Q))$
$(P \land R) \lor ((\lnot R \land P) \lor (\lnot R \land Q))$ ...Distribution law
$(P \land R) \lor (\lnot R \land P) \lor (\lnot R \land Q)$
$((P \land R) \lor (\lnot R \land P)) \lor (\lnot R \land Q)$
$(P \land (R \lor \lnot R)) \lor (\lnot R \land Q)$ ...Distribution law
$(P \land TRUE) \lor (\lnot R \land Q)$ ...Tautology
$ P \lor (\lnot R \land Q)$


Ex-13
LHS
= $\lnot(P \lor Q)$
= $\lnot(\lnot\lnot P \lor \lnot\lnot Q)$ ...Double Negation law
= $\lnot(\lnot(\lnot P \land \lnot Q))$ ...First DeMorgan's law
= $\lnot P \land \lnot Q$ ...Double Negation law
= RHS

Ex-14
$(P \land (Q \land R)) \land S$
= $((P \land Q) \land R) \land S$
= $((P \land Q) \land (R \land S))$
= $(P \land Q) \land (R \land S)$

Ex-15 $2^n$

Ex-16
Using the same strategy as described in Ex-3(b)..

output holds true for
P = F, Q = F ; suggests $\lnot P \land \lnot Q$
P = T, Q = F ; suggests $P \land \lnot Q$
P = T, Q = T ; suggests $P \land Q$

taking disjunction of all
$(\lnot P \land \lnot Q) \lor (P \land \lnot Q) \lor (P \land Q)$
= $(\lnot P \land \lnot Q) \lor ((P \land \lnot Q) \lor (P \land Q))$ ...Commutative law
= $(\lnot P \land \lnot Q) \lor (((P \land \lnot Q) \lor P) \land ((P \land \lnot Q) \lor Q))$ ...Distribution law
= $(\lnot P \land \lnot Q) \lor (P \land ((P \land \lnot Q) \lor Q))$ ...Absorption law
= $(\lnot P \land \lnot Q) \lor (P \land ((P \lor Q) \land (\lnot Q \lor Q)))$ ...Distribution law
= $(\lnot P \land \lnot Q) \lor (P \land (P \lor Q))$ ...Tautology
= $(\lnot P \land \lnot Q) \lor P$ ...Absorption law
= $(\lnot P \lor P) \land (\lnot Q \lor P)$ ...Distribution law
= $\lnot Q \lor P$ ...Tautology

Ex-17
Again using the same strategy as described in Ex-3(b)..we get

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

Ex-18
Suppose the conclusion of an argument is a tautology. What can you say about the validity of the argument?
We can say, its always valid because for all the cases where premises are true conclusion will also be true(as its a tautology).

What if conclusion is contradiction?
We can't say anything.

What if one of the premises is a tautology?
We can't say anything.

What if one of the premises is a contradiction?
We can say, the argument is always valid as all premises will never be true.

4 comments:

  1. Ex-12(c) solution is wrong.

    The correct one is: P V (Q Λ ¬R)

    ReplyDelete
  2. Quick note - I think your answer to Ex 18 is off a bit.

    a.) if the conclusion is a contradiction, then the argument is invalid because the premises can be true while the conclusion is false)
    b.) if the conclusion is a tautology, then the argument is valid for similar reasoning.
    c.) if the argument has a contradictory premise, then it is valid, as the premises cannot all be true without the conclusion being true. (even if it is only in the vacuous sense.)

    ReplyDelete
    Replies
    1. An argument is invalid when the all the premises are true, while the conclusion is false.

      a.) I agree with Himanshu. There is not enough information. Yes, it would be invalid if the premises were all true, but we don't have that information to conclude that the argument is invalid. For all we know, the premises could be all false for all situations in this argument, and that would make it a valid argument.

      b.) The argument is valid in all circumstances. There is no way to make this invalid based on the definition of an invalid argument.

      Delete