5
$\begingroup$

I need to prove the following expression is a tautology using propositional logic laws.

My current working out is as follows [not sure if it is correct]:

$$(p \land q)\land ( \lnot p \lor r) \rightarrow (q \lor r)$$

Taking the LHS: $(p \land q) \land (\lnot p \lor r)$

$( (p \land q) \land \lnot p) \lor ( (p \land q) \land r)$ [Using distributive law]

$( (p \land \lnot p) \land q) \lor ( (p \land q) \land r)$ [Using associative law]

$( F \land q) \lor ( (p \land q) \land r)$ [Using complement law]

$F \lor ( (p \land q) \land r)$ [Using identity law]

This is where I get stuck. Is this the correct working so far? What other laws am I missing to prove the expression is a tautology?

$\endgroup$
0

3 Answers 3

4
$\begingroup$

$p \land q \land (\lnot p \lor r)$ implies $q$ $\tiny\text{… by simplification}$

$q$ implies $q \lor r$ $\tiny\text{… by addition}$

The rest is obvious.

$\endgroup$
3
  • $\begingroup$ Sorry, I'm not quite sure I follow you. $\endgroup$ Commented Jul 29, 2019 at 7:15
  • $\begingroup$ It's a natural deduction style argument, rather than propositional calculus. $\endgroup$ Commented Jul 29, 2019 at 8:16
  • $\begingroup$ That propositional calculus fad is a clumsy way to prove many propositions. Why is it the only thing taught? Have they discarded teaching P., Q|- R. @GrahamKemp $\endgroup$ Commented Jul 29, 2019 at 9:19
3
$\begingroup$

First note that $$F \lor ( (p \land q) \land r)=p \land q \land r$$ Then recall that How to prove that $P \rightarrow Q$ is equivalent with $\neg P \lor Q $?

Hence, from your work, $$(p \land q)\land ( \lnot p \lor r) \rightarrow (q \lor r)$$ is equivalent to $$\lnot(p \land q \land r)\lor (q \lor r)$$ that is, by using De Morgan's laws, $$(\lnot p \lor \lnot q \lor \lnot r) \lor (q \lor r)=\lnot p \lor (\lnot q \lor q) \lor (\lnot r\lor r)=T.$$

$\endgroup$
1
  • $\begingroup$ Thanks! I got it now. $\endgroup$ Commented Jul 29, 2019 at 7:22
0
$\begingroup$

In fact, from $(p\land q)\land (\neg p\lor r)$ we can even prove $q\land r$. Note in particular $p\land(\neg p\lor r)\to r$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .