Show that these two conditional statements are tautologies without using truth tables.

Question

These are the two expressions : $$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$$ $$[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$$

---

For the first statement this is what I have tried : $$ \begin{align} & [(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r) \\ & \equiv \neg[(p \rightarrow q) \land (q \rightarrow r)] \lor (p \rightarrow r) \space\space\space [\text{because} \space\space p \rightarrow q \equiv \neg p \lor q] \\ & \equiv \neg (p \rightarrow q) \lor \neg (q \rightarrow r) \lor (p \rightarrow r) \space\space\space [\text{De Morgan's Law}] \\ & \equiv (p \land \neg q) \lor (q \land \neg r) \lor (\neg p \lor r) \space\space\space\space\space\space [\text{because} \space \neg (p \rightarrow q) \equiv p \land \neg q \space \text{and} \space p \rightarrow q \equiv \neg p \lor q] \\ \end{align} $$

Am I proceeding correctly? What should I do next? I can't seem to figure out.

---

And for the second one, $$ \begin{align} & [(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r \\ & \equiv [(p \lor q) \land \{(p \lor q) \rightarrow r\}] \rightarrow r \space\space\space [\text{because} \space (p \rightarrow r) \land (q \rightarrow r) \equiv (p \lor q) \rightarrow r]\\ & \equiv [(p \lor q) \land \{\neg (p \lor q) \lor r\}] \rightarrow r \space\space [\text{because} \space\space p \rightarrow q \equiv \neg p \lor q] \\ & \equiv [(p \lor q) \land \{\neg p \land \neg q \lor r\}] \rightarrow r \space\space \space [\text{De Morgan's Law}] \\ \end{align} $$

I'm stuck here too.

Any help would be appreciated. Thanks.

Answer 1

Here's a guide, rather than a complete solution:

For the first sentence, your process is correct. You can continue by using the distributivity law: $$A\lor (B\wedge C)\equiv (A\lor B)\wedge (A\lor C)$$ Then, eliminate all formulas of the form $(a\lor \neg a)$.

For the second sentence, your process is again correct, but I wouldn't use de morgan's law in the last step. In the 2nd and 3rd line, you have formulas of the form $(A\land(A\to B))\to B\equiv(A\land(\neg A \lor B))\to B$, where $A = (p\lor q)$ and $B = r$. I would either try to eliminate the last remaining implication, or I would use distributivity again in the condition of the implication.

In both cases you need to arrive to some known tautology, like $T$ (for truth), or $A\lor\neg A$, or $A\to A$.

Answer 2

An example of what you are supposed to do :

$(P \land \neg P) \rightarrow Q$ ( " from a contradiction, anything follows" or " ex falso..." )

$\equiv \neg ( (P\land\neg P) \land Q)$

$\equiv \neg ( \mathbb F \land Q)$

$\equiv \neg \mathbb F$

$\equiv \mathbb T$

Here I use $X \rightarrow Y \equiv_{df} \neg (X\land\neg Y)$

the propositional constant $\mathbb F$ or " falsity" that is, the proposition that is equivalent to any antilogy ( or logical falsehood).

the propositional constant $\mathbb T$ or " truth " that is, the proposition that is equivalent to any tautology

the Domination Law.