Prove that the following is a tautology without using a truth table and only using logical equivalences.

$(p\vee q) \wedge (\neg p \vee r) \rightarrow (q \vee r)$

We know that $(p \rightarrow q)$ is logically equivalent to $(\neg p \vee q )$ so we apply that.

$\neg [(p\vee q) \wedge (\neg p \vee r)] \vee (q \vee r)$

De Morgan's Law follows that: $\neg (p \wedge q)$ is logically equivalent to $(\neg p \vee \neg q)$

[$\neg(p\vee q) \vee \neg(\neg p \vee r)] \vee (q \vee r)$

De Morgan's Law again...

$(\neg p\wedge \neg q) \vee ((\neg(\neg p) \wedge \neg r) \vee (q \vee r)$

Double negation of $\neg(\neg p)$ is equal to just $p$

$(\neg p\wedge \neg q) \vee (p \wedge \neg r) \vee (q \vee r)$

Now what comes next? Did I do everything right so far? Eventually, I'm suppose to start getting T or F for some of these compounds. I have these following laws.

Domination Law:

$p \vee T \equiv T$

$p \wedge F \equiv F $

Negation Law:

$p \vee \neg p \equiv T$

$p \wedge \neg p \equiv F$

  • $\begingroup$ let $p=T, q=F, r=F$ in your last step it gives $T$ but surely the initial statement is false. Which means some your your steps are incorrect. $\endgroup$ Sep 18 '15 at 6:16
  • $\begingroup$ Did you check my steps though to see where I went wrong? If I keep going, I should start getting F and T in the equation. That's why my question is what is my next step. $\endgroup$
    – J.A.R.
    Sep 18 '15 at 6:29
  • $\begingroup$ @baharampuri With your assignment of truth values, $p=T$, $q=F$, and $r=F$, the initial statement is true, because its antecedent is false. Specifically, in the antecedent, the conjunct $(\neg p)\lor r$ is false. (The initial statement is a tautology, as the problem claims.) $\endgroup$ Sep 18 '15 at 6:37

For simplicity of writing, I will use $+$, multiplication, and $\bar{p}$ for OR, AND, and $\neg p$.

We have \begin{align}\overline{(p+q)(\bar p+r)}+(q+r)=&\overline{(p+q)(\bar p+r)\bar q\bar r}\\ =&\overline{(pr+\bar pq+qr)\bar q\bar r}\\ =&\overline{pr\bar q\bar r+\bar pq\bar q\bar r+qr\bar q\bar r}\\ =&\overline{F+F+F}\\ =&T.\end{align}

Update: To see the first step, let $t=(p+q)(\bar p+r)$. Then $$\bar t+(q+r)=\overline{\overline{\bar t+(q+r)}}=\overline{t\ \overline{(q+r)}}=\overline{t(\bar q \bar r)}=\overline{t\bar q \bar r}.$$

  • $\begingroup$ How did you negate? the (q + r)? $\endgroup$
    – J.A.R.
    Sep 18 '15 at 7:31
  • $\begingroup$ I added an update with more steps. $\endgroup$
    – DirkGently
    Sep 18 '15 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.