Prove $((P \cup Q) \cap (P \to R) \cap (Q \to R)) \to R $ is a Tautology

Question

$[(P \cup Q) \cap (P \rightarrow R) \cap (\neg Q \cup R)] \rightarrow R $ Logical Equivalences.

$[(P \cup Q) \cap (\neg P \cup R) \cap (\neg Q \cup R)] \rightarrow R$ Logical Equivalences.

$\neg[(P \cup Q) \cap (\neg P \cup R) \cap (\neg Q \cup R)] \cup R$ Logical Equivalences.

$[\neg(P \cup Q) \cup \neg (\neg P \cup R) \cup \neg (\neg Q \cup R)] \cup R$ De Morgan’s Laws.

$(\neg P \cap \neg Q) \cup (P \cap \neg R) \cup (Q \cap \neg R) \cup R$ De Morgan’s Laws.

I'm thinking I can use the distributive property here, but I don't know how I would set that up.

$(\neg P \cup P) \cap (\neg P \cup ¬R) \cap (\neg Q \cup P) \cap (\neg Q \cup \neg R)$ $\leftarrow$ That is as far as I have gotten as I am unsure if I continue to distribute the letters throughout the entire thing or not like this instead:

$(\neg P \cup P \cup Q \cup R) \cap (\neg P \cup \neg R \cup \neg R \cup R) \cap (\neg Q \cup P \cup Q \cup R) \cap (\neg Q \cup \neg R \cup \neg R \cup R).$

Now that I look at it, I think the second way looks correct, but I'm still unsure.

Identity Laws, domination, idempotent, double negation, commutative, associative, distributive, De Morgan's, Absorption, and Negation laws.
For logical Equivalences, we're only allowed to use P->Q = ~P v Q and P <-> Q = (P -> Q) ^ (Q-> P) — SqualoredToad, Feb 10 '23 at 20:55
I thought for distributive, you had to distribute the letter throughout all of it. Why is it ((P ^ (P ->R))v(Q ^(Q-> R)))->R and not ((P ^ (P ->R) ^ (Q-> R)) v (Q ^ (P -> R) ^ (Q-> R))->R? — SqualoredToad, Feb 10 '23 at 21:18

score 1 · Answer 1 · answered Feb 10 '23 at 23:20

1

Hint: use modus ponendo ponens:

$P\land (P\implies Q)\implies Q$.

And the distributive rules.

answered Feb 10 '23 at 23:20

ryaron

1,091

score 1 · Answer 2 · answered Feb 11 '23 at 13:19

$[\neg (P \cup Q) \cup \neg(\neg P \cup R) \cup \neg(\neg Q \cup R)] \cup R.$ (line 4 of your derivation)

$[\neg (P \cup Q) \cup (P \cap \neg R) \cup (Q \cap \neg R)] \cup R.$

$\{\neg (P \cup Q) \cup [(P \cup Q) \cap \neg R]\} \cup R.$

$\neg (P \cup Q) \cup \{ [(P \cup Q) \cap \neg R] \cup R\}.$

$\neg (P \cup Q) \cup \{[(P \cup Q) \cup R] \cap (\neg R \cup R)\}.$

$\neg (P \cup Q) \cup \{[(P \cup Q) \cup R] \cap \textbf{T}\}.$

$\neg (P \cup Q) \cup [(P \cup Q) \cup R].$

Can you take it from here?

score 1 · Answer 3 · answered Feb 11 '23 at 19:15

1

If $R$ is true, then $\to$ is true. ($A\to T=T$), so $R$ must be false for the tautology to fail.

So we need to prove that if $R=F$ then the LHS is false.

As $A\to F=\lnot A$, from $(P\to R)\cap (Q\to R)$ we get $(P\to F)\cap (Q\to F)=\lnot P\cap\lnot Q=\lnot(P\lor Q)$

So the LHS becomes $(P\lor Q)\land\lnot(P\lor Q)=F$.

answered Feb 11 '23 at 19:15

JMP

21,771

Now I understand your comment. :-) Concise answer. (+1) – Markus Scheuer Feb 11 '23 at 19:24

score 0 · Answer 4 · answered Feb 11 '23 at 18:10

Truth tables are often a convenient alternative. We obtain \begin{align*} \begin{array}{ccccccccccccccccc} ((&P& \cup& Q&) \cap ((&P& \to &R&) &\cap& (&Q& \to& R&))) &\to& R\\ \hline &1&1&1&1&1&1&1&&1&&1&1&1&&\color{blue}{1}&1\\ &1&1&1&0&1&0&0&&0&&1&0&0&&\color{blue}{1}&0\\ &1&1&0&1&1&1&1&&1&&0&1&1&&\color{blue}{1}&1\\ &1&1&0&0&1&0&0&&0&&0&1&0&&\color{blue}{1}&0\\ &0&1&1&1&0&1&1&&1&&1&1&1&&\color{blue}{1}&1\\ &0&1&1&0&0&1&0&&0&&1&0&0&&\color{blue}{1}&0\\ &0&0&0&0&0&1&1&&1&&0&1&1&&\color{blue}{1}&1\\ &0&0&0&0&0&1&0&&1&&0&1&0&&\color{blue}{1}&0\\ \hline &1& 4& 2&6 &1& 4 &3& &5& &2& 4& 3& &7& 3\\ \end{array} \end{align*} and the claim follows.

The bottom row in the table indicates the order of evaluation.

Prove $((P \cup Q) \cap (P \to R) \cap (Q \to R)) \to R $ is a Tautology

4 Answers4