Kenneth H. Rosen - Propositional Logic

Question

Explain, without using a truth table, why (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) is true when p, q, and r have the same truth value and it is false otherwise.

Answer 1

Statement S : (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p)

S can be written as :

$\Rightarrow (p + {q}').(q + {r}').(r + {p}')$

$\Rightarrow pqr + {p}'{q}'{r}'$

$\therefore S = pqr + {p}'{q}'{r}'$

---

Let, $x_{1} = pqr$ & $x_{2} = {p}'{q}'{r}'$

S = $x_{1} + x_{2}$

Now, we want S to be TRUE.

S is TRUE when :

Case 1 : $x_{1}$ = T & $x_{2}$ = F

Case 2 : $x_{1}$ = F & $x_{2}$ = T

Case 3 : $x_{1}$ = T & $x_{2}$ = T

---

Case 1 : $x_{1}$ = T & $x_{2}$ = F

$x_{1}$ = pqr

In $x_{1}$ if atleast one of p, q, r is FALSE then $x_{1}$ will become FALSE. So, in order to be $x_{1}$ be TRUE

then p = T & q = T & r = T. Then $x_{1}$ will be TRUE and $x_{2}$ will automatically become FALSE.

Then, S = T + F = T

Hence, S will be evaluated as TRUE.

Here, p, q, r have same truth value as TRUE (p = q = r = TRUE).

---

Case 2 : $x_{1}$ = F & $x_{2}$ = T

$x_{1}$ = pqr & $x_{2}$ = ${p}'{q}'{r}'$

If we want $x_{1}$ = F & $x_{2}$ = T simultaneously then it is only possible when

p = F & q = F & r = F. Then $x_{1}$ will be FALSE and $x_{2}$ will automatically become TRUE.

Then, S = F + T = T

Hence, S will be evaluated as TRUE.

Here, p, q, r have same truth value as FALSE (p = q = r = FALSE).

---

Case 3 : $x_{1}$ = T & $x_{2}$ = T

This case is not feasible because it is NOT POSSIBLE to make $x_{1}$=T & $x_{2}$=T at the same time.

---

From Case 1 & Case 2 we have proved that (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) is true when p, q, and r

have the same truth value.

Answer 2

Lets solve this with little intuition ;

Question: (P∨ ¬Q) ∧ (Q ∨ ¬R) ∧ (R ∨ ¬P)

Formula used Here:   (¬P v Q) is logically equivalent to (P → Q).

with this equivalance we can reformat this question as

• (Q→P) ∧ (R→Q) ∧ (P→R)

Now, I am going to ask you to look closely. 

 

lmplication is false only when the consequent(conclusion) is false and antecedent(hypothesis) is true otherwise it is true;

• Try not to make any of these two conjuction(AND) false; We can do this by avoiding the situation where hypothesis is TRUE and conclustion is FALSE(T→ F=F).

---

• Second option by makeing hypothesis False and conclusion True, doing so we end up Falsifying one of the conjuction(AND), which makes our propositional Formula false.

---

• and the third option is either we choose to make both hypothesis and conclusion False(F→F=T) or Both True(T→T=T). This Option is Suitable for making our  propositional Formula True.

 

This leads us to a conclusion that the propositional variables must be have the same truth value to be true.