Question

Use the laws of propositional logic to prove that the following compound propositions are tautologies.
A. $\left( \neg p\wedge \left( p\vee q \right) \right)\to q$
B. $\left( \left( p\to q \right)\wedge \left( q\to r \right) \right)\to \left( p\to r \right)$

Answer 1

Hint: For the A part of the question, the main step is that we use the distribution law of propositional logic and then the implication and De Morgan’s formula. While evaluating, use the identity, negation, and null laws to simplify easily. For the B part of the question, the main step is that we use the implication law of propositional logic and then De Morgan’s formula. While evaluating use the absorption, negation, and null laws to simplify further to prove the tautology.

Complete step by step solution:
First, let us solve the A part of the question.
Given that, $\left( \neg p\wedge \left( p\vee q \right) \right)\to q$ and we are asked to prove that the statement is a tautology.
$\Rightarrow \left( \neg p\wedge \left( p\vee q \right) \right)\to q$
Here we first use the distribution law, which is given by, $A\wedge \left( B\vee C \right)=\left( A\wedge B \right)\vee \left( A\wedge C \right)$
$\Rightarrow \left( \left( \neg p\wedge p \right)\vee \left( \neg p\vee q \right) \right)\to q$
Now let us use the negation law, which is given by, $A\wedge \neg A=F$
$\Rightarrow \left( F\vee \left( \neg p\vee q \right) \right)\to q$
Let us now use the identity law, which is given by, $F\vee \left( A \right)=A$
$\Rightarrow \left( \neg p\vee q \right)\to q$
Here we further simplify using the implication law, which is given by, $A\to B=\neg A\wedge B$
$\Rightarrow \neg \left( \neg p\vee q \right)\vee q$
The major law which we will be using here is the De Morgan’s law, which is given by, $\neg \left( A\wedge B \right)=\neg A\vee \neg B$
$\Rightarrow \left( \neg \left( \neg p \right)\vee \neg q \right)\vee q$
Now let us try using the double negation law to simply further.
The double negation law, which is given by, $\neg \left( \neg A \right)=A$
$\Rightarrow p\vee \neg q\vee q$
Now we implement the negation law, which is given by, $A\wedge \neg A=T$
$\Rightarrow p\vee T$
And finally, the null law, which is given by, $T\vee A=T$
$\Rightarrow T$
Hence, we have proved that $\left( \neg p\wedge \left( p\vee q \right) \right)\to q$ is a tautology.
Now let us solve the B part of the question.
Given that, $\left( \left( p\to q \right)\wedge \left( q\to r \right) \right)\to \left( p\to r \right)$ and we are asked to prove that the statement is a tautology.
$\Rightarrow \left( \left( p\to q \right)\wedge \left( q\to r \right) \right)\to \left( p\to r \right)$
Here we first use the implication law, which is given by, $A\to B=\neg A\wedge B$
$\Rightarrow \neg \left( \left( \neg p\wedge p \right)\vee \left( \neg p\vee q \right) \right)\wedge q$
Another major law which we will be using here is the De Morgan’s law, which is given by, $\neg \left( A\vee B \right)=\neg A\wedge \neg B$
$\Rightarrow \neg \left( \neg p\wedge p \right)\wedge \neg \left( \neg p\vee q \right)\wedge q$
Now let us use the negation law, which is given by, $A\wedge \neg A=F$
$\Rightarrow \neg F\wedge \neg \left( \neg p\vee q \right)\wedge q$
We will be using De Morgan’s law again, which is given by, $\neg \left( A\vee B \right)=\neg A\wedge \neg B$
$\Rightarrow \neg F\wedge \left( \neg \left( \neg p \right)\wedge \neg q \right)\wedge q$
Now let us try using the double negation law to simply further.
The double negation law, which is given by, $\neg \left( \neg A \right)=A$
$\Rightarrow T\wedge p\wedge \neg q\wedge q$
Now we implement the negation law, which is given by, $A\wedge \neg A=T$
$\Rightarrow T\wedge p\wedge T$
And finally, the null law, which is given by, $T\wedge A=T$
$\Rightarrow T$
Hence, we have proved that $\left( \left( p\to q \right)\wedge \left( q\to r \right) \right)\to \left( p\to r \right)$ is a tautology.

Note: First before solving any of the propositional questions, always write down the laws of propositional logic on the side. Looking at the formula and the question together will give you ideas of which law can be used.
Some of the major formula, which is used frequently,
The distribution law, which is given by, $A\wedge \left( B\vee C \right)=\left( A\wedge B \right)\vee \left( A\wedge C \right)$
The absorption law, which is given by, $\left( A\wedge \neg B \right)\vee B=\left( A\vee B \right)$
The implication law, which is given by, $A\to B=\neg A\wedge B$
The De Morgan’s law, which is given by, $\neg \left( A\wedge B \right)=\neg A\vee \neg B$
The negation law, which is given by, $A\wedge \neg A=T$
The double negation law, which is given by, $\neg \left( \neg A \right)=A$
The identity law, which is given by, $F\vee \left( A \right)=A$
The null law, which is given by, $T\vee A=T$