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.
===========================================================================================
Ex-1(a)
Ex-1(b)
Ex-2(a)
Ex-2(b)
Ex-3(a) '+' denotes exclusive or
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:
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.
Ex-5(a)
$\downarrow$ means nor(not or)
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)
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)
clearly the argument is valid.
Ex-7(b)
clearly argument is not valid at row # 6
Ex-7(c)
clearly argument is valid.
Ex-7(d)
clearly argument is not valid at row # 6 and 8.
Ex-8
clearly a $\equiv$ c and b $\equiv e$ and d is equivalent to none
Ex-9
clearly a is none, b is contradiction and c is tautology
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.
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.
- Draw truth tables for both and see if they are exactly the same.
- Use equivalence relations described above to see if one can be transformed into other
===========================================================================================
Ex-1(a)
| P | Q | $\lnot P$ | $\lnot P \lor Q$ |
| F | F | T | T |
| T | F | F | F |
| F | T | T | T |
| T | T | F | T |
Ex-1(b)
| S | G | $\lnot S$ | $\lnot G$ | $S \lor G$ | $\lnot S \lor \lnot G$ | $(S \lor G) ∧ (\lnot S \lor \lnot G)$ |
| F | F | T | T | F | T | F |
| T | F | F | T | T | T | T |
| F | T | T | F | T | T | T |
| T | T | F | F | T | F | F |
Ex-2(a)
| P | Q | $\lnot P$ | $(Q \lor \lnot P)$ | $P \land (Q \lor \lnot P)$ | $\lnot (P \land (Q \lor \lnot P))$ |
| F | F | T | T | F | T |
| T | F | F | F | F | T |
| F | T | T | T | F | T |
| T | T | F | T | T | F |
Ex-2(b)
| P | Q | R | $\lnot P$ | $P \lor Q$ | $\lnot P \lor R$ | $(P \lor Q) \land (\lnot P \lor R)$ |
| F | F | F | T | F | T | F |
| T | F | F | F | T | F | F |
| F | T | F | T | T | T | T |
| T | T | F | F | T | F | F |
| F | F | T | T | F | T | F |
| T | F | T | F | T | T | T |
| F | T | T | T | T | T | T |
| T | T | T | F | T | T | T |
Ex-3(a) '+' denotes exclusive or
| P | Q | P+Q |
| F | F | F |
| T | F | T |
| F | T | T |
| T | T | F |
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:
| P | Q | $\lnot P$ | $\lnot Q$ | $P \land \lnot Q$ | $\lnot P \land Q$ | $(P \land \lnot Q) \lor (\lnot P \land Q)$ |
| F | F | T | T | F | F | F |
| T | F | F | T | T | F | T |
| F | T | T | F | F | T | T |
| T | T | F | F | F | F | F |
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.
| P | Q | $\lnot P$ | $\lnot Q$ | $\lnot P \land \lnot Q$ | $\lnot(\lnot P \land \lnot Q)$ | $P \lor Q$ |
| F | F | T | T | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| T | T | F | F | F | T | T |
Ex-5(a)
$\downarrow$ means nor(not or)
| P | Q | $P ↓ Q$ |
| F | F | T |
| T | F | F |
| F | T | F |
| T | T | F |
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)
| P | Q | P|Q |
| F | F | T |
| T | F | T |
| F | T | T |
| T | T | F |
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)
| Jm | Pm | Pc | $Jm \land Pm$ | $\lnot(Jm \land Pm)$ | $Pm \lor Pc$ |
| F | F | F | F | T | F |
| T | F | F | F | T | F |
| F | T | F | F | T | T |
| T | T | F | T | F | T |
| F | F | T | F | T | T |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| T | T | T | T | F | T |
clearly the argument is valid.
Ex-7(b)
| B | F | P | C | $B \lor F$ | $P \lor C$ | $F \land C$ | $\lnot(F \land C)$ | $B \land P$ | $\lnot(B \land P)$ |
| F | F | F | F | F | F | F | T | F | T |
| T | F | F | F | T | F | F | T | F | T |
| F | T | F | F | T | F | F | T | F | T |
| T | T | F | F | T | F | F | T | F | T |
| F | F | T | F | F | T | F | T | F | T |
| T | F | T | F | T | T | F | T | T | F |
| F | T | T | F | T | T | F | T | F | T |
| T | T | T | F | T | T | F | T | T | F |
| F | F | F | T | F | T | F | T | F | T |
| T | F | F | T | T | T | F | T | F | T |
| F | T | F | T | T | T | T | F | F | T |
| T | T | F | T | T | T | T | F | F | T |
| F | F | T | T | F | T | F | T | F | T |
| T | F | T | T | T | T | F | T | T | F |
| F | T | T | T | T | T | T | F | F | T |
| T | T | T | T | T | T | T | F | T | F |
clearly argument is not valid at row # 6
Ex-7(c)
| J | B | S | $\lnot B$ | $\lnot S$ | $J \lor B$ | $\lnot S \lor \lnot B$ | $J \lor \lnot S$ |
| F | F | F | T | T | F | T | T |
| T | F | F | T | T | T | T | T |
| F | T | F | F | T | T | T | T |
| T | T | F | F | T | T | T | T |
| F | F | T | T | F | F | T | F |
| T | F | T | T | F | T | T | T |
| F | T | T | F | F | T | F | F |
| T | T | T | F | F | T | F | T |
clearly argument is valid.
Ex-7(d)
| S | B | E | $\lnot B$ | $S \land B$ | $E \land \lnot B$ | $(S \land B) \lor (E \land \lnot B)$ | $S \land E$ | $\lnot(S \land E)$ |
| F | F | F | T | F | F | F | F | T |
| T | F | F | T | F | F | F | F | T |
| F | T | F | F | F | F | F | F | T |
| T | T | F | F | T | F | T | F | T |
| F | F | T | T | F | T | T | F | T |
| T | F | T | T | F | T | T | T | F |
| F | T | T | F | F | F | F | F | T |
| T | T | T | F | T | F | T | T | F |
clearly argument is not valid at row # 6 and 8.
Ex-8
| P | Q | $\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$ |
| F | F | T | T | F | T | T | T | T | T | T | T | F | T |
| T | F | F | T | F | F | F | F | T | F | F | F | F | F |
| F | T | T | F | F | F | F | T | F | T | F | F | F | T |
| T | T | F | F | T | F | T | T | T | T | T | F | T | T |
clearly a $\equiv$ c and b $\equiv e$ and d is equivalent to none
Ex-9
| P | Q | $\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)$ |
| F | F | T | T | F | T | F | T | F | T |
| T | F | F | T | T | T | T | F | F | T |
| F | T | T | F | T | T | T | F | F | T |
| T | T | F | F | T | F | F | F | F | T |
clearly a is none, b is contradiction and c is tautology
| P | Q | R | $\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)$ |
| F | F | F | T | T | T | F | T | T |
| T | F | F | F | T | T | T | F | T |
| F | T | F | T | T | T | F | T | T |
| T | T | F | F | T | T | T | F | T |
| F | F | T | T | F | F | F | T | T |
| T | F | T | F | F | F | F | T | T |
| F | T | T | T | F | T | F | T | T |
| T | T | T | F | F | T | T | T | T |
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.
Ex-12(c) solution is wrong.
ReplyDeleteThe correct one is: P V (Q Λ ¬R)
you're right, updated !
DeleteQuick note - I think your answer to Ex 18 is off a bit.
ReplyDeletea.) 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.)
An argument is invalid when the all the premises are true, while the conclusion is false.
Deletea.) 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.
answer of 12(a) should be P Λ (¬Q V ¬R). Double checked with truth tables.
ReplyDelete