Is the following propositional logic valid?

Question

$$P ∧ (¬P∨Q) ∧ (¬Q∨R) → R$$

Truth table method seems to be hectic. Is there any other simple approach to check ?

You're saying that you want this to evaluate to true for any values of $P,$ $Q$, and $R$? — RideTheWavelet, Jul 04 '17 at 07:49
@RideTheWavelet Valid means it should be always true irrespective of the value . — Jon Garrick, Jul 04 '17 at 07:51
Check with "simplified" truth table approach; assume not, i.e. $R$ false. Then it is needed $Q$ false too to satisfy $(\lnot Q \lor R)$. This implies $P$ false too in order to satisfy $(\lnot P \lor Q)$ and this is inconsisent with $P$. — Mauro ALLEGRANZA, Jul 04 '17 at 07:55

score 2 · Accepted Answer · answered Jul 04 '17 at 07:59

If suffices to check the following: if $R$ is false, then $P ∧ (¬P∨Q) ∧ (¬Q∨R)$ is false. This is because $x \rightarrow \text{True}$ is always valid.

Note that by the distributive property, $P ∧ (¬P∨Q) = (P∧¬P) ∨ (P∧Q) = P∧Q$. Also since $R$ is false, $¬Q∨R = ¬Q$.

$$ P ∧ (¬P∨Q) ∧ (¬Q∨R) = (P∧Q) ∧ ¬Q = P∧(Q ∧ ¬Q)$$

Clearly, $Q ∧ ¬Q$ is false. This completes the proof.

skyking · Answer 2 · 2017-07-04T08:13:41.973

You have for the left hand side to be true that $P$ so $\neg P\lor Q$ is the same as $Q$ which is also required to be true so $\neg Q \lor R$ is $R$ so $R$ is also required to be true. This boils down to prove that:

$$P\land Q\land R\rightarrow R$$

Another way to see it is that $\phi\rightarrow\psi$ is the same as $\neg\phi\lor\psi$. Which makes the statement to be shown is the same as:

$$P\land (P\rightarrow Q)\land (Q\rightarrow R) \rightarrow R$$

which should be obvious.

score 0 · Answer 3 · answered Jul 04 '17 at 07:57

Recall that $A\rightarrow B$ is equivalent to $\neg (A\wedge \neg B)$. Therefore, it suffices to check that whenever the left hand side of this implication is true, the right hand side must also be true. Since the left hand side is made up of the conjunction of three propositions, it is true only when all three conjuncts are true. For the first conjunct to be true, $P$ is true. For the second conjunct to be true, since $\neg P$ is necessarily false, $Q$ must be true. Finally, since $\neg Q$ must be false, $R$ must be true, which completes the proof.

score 0 · Answer 4 · answered Jul 04 '17 at 08:10

Yes, this implication does hold.

One way to see this is because the left-hand side is only true when all of $P, Q, $ and $R$ are true. In all other cases, the left-hand side is false, and the implication follows vacuously.

Concretely, if $P$ is false, then $P \land x$ is false for any statement $x$.

Otherwise, suppose $P$ is true. Then if $Q$ is false, $\neg P \lor Q$ is false, rendering the entire left-hand side false (regardless of what $R$ is).

Finally, suppose $P$ and $Q$ are true. Then if $R$ is false, $\neg Q \lor R$ is false.

The only remaining case is that $P,Q$, and $R$ are all true, and you can check that in this case both sides of the implication are true. This rules out a statement of the form $F \implies T$ occurring in the truth table, and so the implication holds!

score 0 · Answer 5 · answered Jul 04 '17 at 13:03

$$(P \land (\neg P \lor Q) \land (\neg Q \land R)) \rightarrow R \Leftrightarrow \text{ (Reduction)}$$

$$(P \land Q \land (\neg Q \land R)) \rightarrow R \Leftrightarrow \text{ (Reduction)}$$

$$(P \land Q \land R) \rightarrow R \Leftrightarrow \text{ (Implication)}$$

$$\neg (P \land Q \land R) \lor R \Leftrightarrow \text{ (DeMorgan)}$$

$$\neg P \lor \neg Q \lor \neg R \lor R \Leftrightarrow \text{ (Complement)}$$

$$\neg P \lor \neg Q \lor \top \Leftrightarrow \text{ (Annihilation)}$$

$$\top$$

So yeah, this is a valid statement (this was obvious after 2 steps already, but I am not familiar with a rule $(X \land Y) \rightarrow X \Leftrightarrow \top$ ... there really should be!)

Is the following propositional logic valid?

5 Answers5