How to Prove It - Solutions

Summary

• Truth Tables
• Argument Validation using Truth Tables. For all the rows in truth tables where “premises” are true, corresponding rows of “conclusion” must also be true.
• DeMorgan’s Laws:
  • \( \lnot (P \land Q) \text{ is equivalent to } \lnot P \lor \lnot Q \).
  • \( \lnot (P \lor Q) \text{ is equivalent to } \lnot P \land \lnot Q \).
• Commutative Laws:
  • \( P \land Q \text{ is equivalent to } Q \land P \).
  • \( P \lor Q \text{ is equivalent to } Q \lor P \).
• Associative Laws:
  • \( P \land (Q \land R) \text{ is equivalent to } (P \land Q) \land R \).
  • \( P \lor (Q \lor R) \text{ is equivalent to } (P \lor Q) \lor R \).
• Idemponent Laws:
  • \( P \land P \text{ is equivalent to } P \).
  • \( P \lor P \text{ is equivalent to } P \).
• Distributive Laws:
  • \( P \land (Q \lor R) \text{ is equivalent to } (P \land Q) \lor (P \land R) \).
  • \( P \lor (Q \land R) \text{ is equivalent to } (P \lor Q) \land (P \lor R) \).
• Absorption Laws:
  • \( P \lor (P \land Q) \text{ is equivalent to } P \).
  • \( P \land (P \lor Q) \text{ is equivalent to } P \).
• Double Negation Law:
  • \( \lnot \lnot P \text{ is equivalent to } P \).
• Tautologies: Formulas that are always true.
• Contradictions: Formulas that are always false.

Solutions

Soln.1

(a)

(b)

Soln.2

(a)

(b)

Soln.3

(a)

(b)

(Updated 20th June’18: I restructured this solution as per the suggestion from Maxwell)

Approach

Before we proceed for this solution, let’s first come up with an approach to get a desired output for given inputs.

First we note few properties about $\, \land \,$ and $\, \lor \,$ operators:

1. We know that \( \land \) gives true only when all of its inputs are true. Or returns false only if any of the input is false.
2. Also \( \lor \) returns true if any of the inputs are true. Or returns false only if all of the inputs are false.

We can use the above properties to our advantage.

If we want true we can use $\, \land \,$ and ensure in some way that all of the inputs to $\, \land \,$ are true.

Similarly, if we want false, we can use $\, \lor \,$ and ensure that all of the inputs to $\, \lor \,$ are false.

Consider a simple case:

Suppose we want desired output, say O, to be true for a given set of inputs, say M and N. Since we want output = true, we will use $\, \land \,$. To ensure that all the inputs to $\, \land \,$ are true:

1. M = true, N = true. We can get the desired output = true, by using $\, M \,$ and $\, N \,$ as inputs to $\, \land \,$. Thus we use $\, M \land N \,$ . And for any other values of M and N, generated output will be false.
2. M = true, N = false. We can get the desired output = true, by using $\, M \,$ and $\, \lnot N \,$ as inputs to $\, \land \,$. Thus we use $\, M \land \lnot N \,$. And for any other values of M and N, output generated will be false.
3. M = false, N = true. We can get the desired output = true, by using $\, \lnot M \,$ and $\, N \,$ as inputs to $\, \land \,$. Thus we use $\, \lnot M \land N \,$. And for every other value of M and N, output generated will be false.
4. M = false, N = false. We can get the desired output = true, by using $\, \lnot M \,$ and $\, \lnot N \,$ as inputs to $\, \land \,$. Thus we use $\, \lnot M \land \lnot N \,$. And for any other value of M and N, output generated will be false.

Similarly, if we want desired output = false for a given set of inputs, say M and N. We have to ensure that all the inputs to $\, \lor \,$ are false:

1. For M = true, N = true. We can get the desired output = false, by using $\, \lnot M \,$ and $\, \lnot N \,$ as inputs to $\, \lor \,$. Thus we use $\, \lnot M \lor \lnot N \,$. Thus for any other values of M and N, generated output will be true.
2. … We use $\, \lnot M \lor N \,$
3. … We use $\, M \lor \lnot N \,$
4. … We use $\, M \lor N \,$

Till, now we figured a way to get a desired output for only one possible set of input. What if we want desired output = true for two possible sets of inputs, For eg: (i) When M = true and N = true, and (ii) When M = true and N = false?

We can use $\, \lor \,$ to combine the isolated solutions for (i) and (ii) so that we get output = true if either (i) or (ii) is true. Thus we get $\, (M \land N) \lor (M \land \lnot N) \,$.

In a similar way if we want desired output = false for two possible sets of inputs, for eg: (i) and (ii) from above. Since here we want false, we combine isolated solutions of (i) and (ii) using $\, \land \,$. Thus we get $\, (\lnot M \lor \lnot N) \land (\lnot M \lor N) \,$.

Thus the above approach suggests that there two alternative(but similar) ways:

• Either we focus on generating true as output by using $\, \land \,$ and for multiple possible inputs, we combine the isolated solutions using $\, \lor \,$.
• Or we focus on generating false as output by using $\, \lor \,$ and for multiple possible inputs we combine isolated solutions using $\, \land \,$.

Applying the above approach

Let’s first see the truth table again from part(a):

We may proceed as follows:

• P + Q is true only for two cases:
  1. P = true and Q = false
  2. P = false and Q = true.
• Similarly, P + Q is false only for two cases:
  1. P = Q = true
  2. P = Q = false

From the method outlined, we can get two solutions corresponding to the two alternatives we saw above

• By focusing on generating true, we get \( (P \land \lnot Q) \lor (\lnot P \land Q) \). This is the resulting formula to get output = true in 2nd row and 3rd row in truth table and false in every other case(1st and 4th row).
• By focussing on generating false, we get \( (\lnot P \lor \lnot Q) \land (P \lor Q) \). This is the resulting formula to get false in 1st row and 4th row in truth table and true in every other case (2nd and 3rd row).

Let’s create truth table for both expressions:

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

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

As can be seen above both expressions returns the same result.

Soln.4

We know that:

\( P \lor Q = \lnot \lnot (P \lor Q) \)

Using Demorgans Law: \( P \lor Q = \lnot (\lnot P \land \lnot Q) \)

Truth table for \( \lnot (\lnot P \land \lnot Q) \) :

As can be seen \( \lnot (\lnot P \land \lnot Q) \) is same as \( P \lor Q \).

Soln.5

(a)

(b)

To find formula for \( P \downarrow Q \) we can use the method outlined in Soln3-b above.

We can get two formulas:

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

(c)

It can be easily verified that \( \lnot P = P \downarrow P \) ….(i)

From Soln5(b), we have \( P \downarrow Q = \lnot P \land \lnot Q \).

\( \Rightarrow P \land Q = \lnot P \downarrow \lnot Q \)

\( \Rightarrow P \land Q = (P \downarrow P) \downarrow (Q \downarrow Q) \) …(ii)

Also, using Demorgans law on Soln5(b), \( \lnot P \land \lnot Q \) can be written as \( \lnot ( P \lor Q ) \).

\( \Rightarrow P \downarrow Q = \lnot ( P \lor Q ) \)

Or we can say, \( P \lor Q = \lnot (P \downarrow Q) = (P \downarrow Q) \downarrow (P \downarrow Q) \) …..(ii)

Thus (i), (ii) and (iii) are the desired answers.

Soln6

(a)

(b)

To find formula for \( P \downarrow Q \) we can use the method outlined in Soln3-b above.

Also, we can directly see that ““P and Q are not both true.” is equivalent to \( \lnot (P \land Q) \).

(c)

It can be easily verified that \( \lnot P = P \vert P \) ….(i)

Now from part(b), \( P \vert Q = \lnot (P \land Q) \)

\( \Rightarrow P \land Q = \lnot (P \vert Q) = (P \vert Q) \vert (P \vert Q) \) …(ii)

Again from part(b), \( P \vert Q = \lnot (P \land Q) = \lnot P \lor \lnot Q \)

\( \Rightarrow P \lor Q = \lnot P \vert \lnot Q = (P \vert P) \vert (Q \vert Q) \) …(iii)

Thus (i), (ii) and (iii) are the desired answers.

Soln7

(a)

When values corresponding to all premises are true, then conclusion is also true.

(b)

It can be easily seen that when all premises are true, then also conclusion \( \lnot (B \land P) \) is not true.

(c)

Thanks Maxwell for pointing out. Earlier got the column $\, J \lor B \,$ wrong in the table.

Thus it can be easily verified when premises are true, then conclusions are also true.

(d)

Thus argument is not valid because when premise is true, conclusion is not true.

Soln8

(a)

(b)

(c)

(d)

(e)

Clearly (a) and (c) are equivalent. Also (b) and (e) are equivalent. (d) is not equivalent to any.

Sol9

(a)

Thus it is niether a tautology nor a contradiction.

(b)

Thus it is a contradiction.

(c)

Thus it is a tautology.

(d)

Thus it is also a tautology.

Soln10

(a)

Thus \( \lnot (P \lor Q) \) is equivalent to \( \lnot P \land \lnot Q \).

(b)

As can be seen in the table \( P \land (Q \lor R) \) is equivalent to \( (P \land Q) \lor ( P \land R) \)

As can be seen in the table \( P \lor (Q \land R) \) is equivalent to \( (P \lor Q) \land ( P \lor R) \).

Soln11

(a)

\( \lnot (\lnot P \land \lnot Q) = \lnot \lnot P \lor \lnot \lnot Q = P \lor Q\).

(b)

Using Distributive Law:

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

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

Using Tautology \( A \lor \lnot A \)

\( \Rightarrow (P \land Q \lor P) \land P \)

Using Absorption law:

\( \Rightarrow P \land P \)

\( \Rightarrow P \)

(c)

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

Using Demorgans Law: \( (\lnot P \lor \lnot \lnot Q) \lor (\lnot P \land Q) \)

Double Negation Law: \( (\lnot P \lor Q) \lor (\lnot P \land Q) \)

Distribution Law: \( ((\lnot P \lor Q) \lor \lnot P) \land ((\lnot P \lor Q) \lor Q) \)

Associative Law: \( (\lnot P \lor Q \lor \lnot P) \land (\lnot P \lor Q \lor Q) \)

Using Idempotent Law: \( (\lnot P \lor Q \lor \lnot P) \land (\lnot P \lor Q) \)

Using associative, commutative and idempotent law: \( (\lnot P \lor Q) \land (\lnot P \lor Q) \)

Using Idempotent Law: \( \lnot P \lor Q \)

Soln12

(a)

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

Using Demorgans and double Negation Law: \( ( P \land \lnot Q) \lor (P \land \lnot R) \)

Using Distributed Law: \( ( P \land \lnot Q \lor P) \land ( (P \land \lnot Q) \lor \lnot R) \)

Using Absorption law: \( P \land ( (P \land \lnot Q) \lor \lnot R) \)

Using Distributive law: \( (P \land (P \land \lnot Q)) \lor (P \land \lnot R) \)

Using Idempotent Law: \( (P \land \lnot Q) \lor (P \land \lnot R) \)

(b)

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

Using Demorgans Law and Double Negation Law : \( ( P \lor \lnot Q) \lor (P \land \lnot R) \)

Using Distributed Law : \( ( P \lor \lnot Q \lor P) \land ((P \lor \lnot Q) \lor \lnot R) \)

Using Associative and Idempotent Law: \( ( P \lor \lnot Q ) \land ((P \lor \lnot Q) \lor \lnot R) \)

Using Absorption Law: \( P \lor \lnot Q \)

(c)

\( ( P \land R ) \lor [ \lnot R \land ( P \lor Q ) ] \)

Using Distributed Law: \( ( P \land R ) \lor [ (\lnot R \land P) \lor ( \lnot R \land Q ) ] \)

Using Associative Law: \( [( P \land R ) \lor (\lnot R \land P)] \lor ( \lnot R \land Q ) \)

Using Distributive Law: \( [(( P \land R ) \lor \lnot R) \land (( P \land R ) \lor P)] \lor ( \lnot R \land Q ) \)

Using Distributive Law: \( [(( P \lor \lnot R) \land ( R \lor \lnot R )) \land (( P \land R ) \lor P)] \lor ( \lnot R \land Q ) \)

Using Tautology: \( [( P \lor \lnot R) \land (( P \land R ) \lor P)] \lor ( \lnot R \land Q ) \)

Using Absorption Law: \( [( P \lor \lnot R) \land P] \lor ( \lnot R \land Q ) \)

Using Distributive Law: \( [( P \land P) \lor ( P \land \lnot R)] \lor ( \lnot R \land Q ) \)

Using Idempotent Law: \( [ P \lor ( P \land \lnot R)] \lor ( \lnot R \land Q ) \)

Using Absorption Law: \( [ P ] \lor ( \lnot R \land Q ) \)

\( \Rightarrow P \lor ( \lnot R \land Q ) \)

Soln13

\( \lnot (P \land Q) = \lnot P \lor \lnot Q \).

Taking negation on both sides, \( \lnot \lnot (P \land Q) = \lnot (\lnot P \lor \lnot Q) \).

Applying Double negation law:

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

Using \( P1 = \lnot P, Q1 = \lnot Q \), gives:

\( \lnot P1 \land \lnot Q1 = \lnot ( P1 \lor Q1) \)

\( \Rightarrow \lnot ( P1 \lor Q1) = \lnot P1 \land \lnot Q1 \). .. which is the required derivation.

Soln14

We have \( [P \land (Q \land R)] \land S \)

Using Associative law, \( [(P \land Q) \land R] \land S \)

Using Associative law, \( (P \land Q) \land [R \land S] \) which is same as was required.

Soln15

Each letter doubles the number of lines. So total lines should be \( 2^n \)

Soln16

We can use same steps as in soln 3b:

We can have two formulas: - \( P \lor \lnot Q \) - \( (\lnot P \land \lnot Q) \lor (P \land \lnot Q) \lor (P \land Q) \).

Soln17

We can use same steps as in soln 3b:

We can have two formulas: - \( (P \lor Q) \land (\lnot P \lor \lnot Q) \). - \( (\lnot P \land Q) \lor (P \land \lnot Q) \).

Son18

• If the conclusion of an argument is a tautology. The argument is always true. We have two cases:
  • If all premises are true. In this case it is obvious that argument is valid.
  • All or some premises are not true then also argument will be valid. An argument is considered valid when all premises are true, then conclusion should also be true. Thus argument validation check does not apply when premises are not true.
• If the conclusion is contradiction. We have two cases:
  • If premises are true, then argument is not valid.
  • If premises are false, then argument is valid.
• If one of the premise is a Tautology:
  • We are not sure of the other premises and also we dont know about the conclusion. Thus answer will depend on further datapoints.
• If one of the premise is Contradiction: -Than argument is always valid. An argument is valid when all premises are true and then conclusion is also true. In this case all premises will never be true thus .