Tautology, Propositional Logic

Question

I am solving a past exam paper for my final exams in my university and I am studying computer science. I couldn't solve one question and it is about proving a propositional identity that it is tautology.

The question:

(p ∧ ¬q) ∨ ( q ∧ ¬r) ∨ ¬p ∨ r

Show algebraically that the identity is a tautology.

Many thanks for the all help in advance.

Answer 1

You can combine the 4 terms in two steps, two by two:

$(p \land \lnot q) \lor \lnot p = (p \lor \lnot p) \land (\lnot q \lor \lnot p)$ by distributivity, and the first term is $\top$ (true),which is a neutral element for $\land$ so we get

$$(p \land \lnot q) \lor \lnot p = \lnot q \lor \lnot p$$

Two remaining terms are $(q \land \lnot r) \lor r$ which simplifies to $$(q \lor r) \land (\lnot r \lor r) = (q \lor r) \land \top = q \lor r$$

Now combining all 4 we get $$\lnot q \lor \lnot p \lor q \lor r$$ which is $\top$ as it contains the tautology $\lnot q \lor q$ among the terms we combine by $\lor$. So we have a tautology in total.

If I'd have to reason about it in advance: what falsifies the total $\lor$ statement? $r$ would have to be false, $\lnot p$ (last terms) too, so $p$ is true, and $\lnot r$ is true, so $q$ would also have to be false, but then the first term $(p \land \lnot q$) would be true,a nd thus the statement. This contradiction shows we canot falsify it.. The algebraic approach looks for terms to combine instead.

Answer 2

$$P\overline{Q} + Q\overline{R} + \overline{P}+R \\ = \overline P + \overline Q + R+Q \\ = P + R + 1 \\ = 1$$ Which is a tautology

P.s: Second line uses the property $A + \overline A B = A + B$