Working with logically equivalent formulas

Propositional Logic: Logical consequence and consistency

Working with logically equivalent formulas

We did call the previous theory page Useful Tautologies, but what use do they actually have? An example makes it clear that they play a major role in simplifying compound logical formulas and in proving that two formulas are logically equivalent without constructing the truth table of the formulas.

Show that for propositional variables $p$ and $q$ the formulas $(p\lor q)\land\neg(\neg\,p\land q)$ and $p$ are logically equivalent.

Solution.
We give sequential equivalences that reduce $(p\lor q)\land\neg(\neg\,p\land q)$ to $p$ :

$\begin{array}{rll} (p\lor q)\land\neg(\neg\,p\land q)&\iff& (p\lor q)\land(\neg\neg\,p\lor \neg\, q) & \blue{\text{rule of de Morgan}}\\[0.2cm] &\iff & (p\lor q)\land(p\lor \neg\, q) & \blue{\text{double negation}}\\[0.2cm] &\iff & p\lor( q\land \neg\, q)& \blue{\text{distributivity}}\\[0.2cm] &\iff & p\lor \psi\text{ for any contradiction } \psi& \blue{\text{inversion}}\\[0.2cm] &\iff & p& \blue{\text{identity}}\end{array}$

Show that for propositional variables $p$ and $q$ the formulas $\neg(p\rightarrow q)$ and $p\land\neg\, q$ are logically equivalent.

Solution.
We give sequential equivalences that reduce $\neg(p\rightarrow q)$ to $p\land\neg\, q$ :

$\begin{array}{rll} \neg(p\rightarrow q)&\iff& \neg(\neg\,p\lor q) & \blue{\text{contraposition}}\\[0.2cm] &\iff & \neg\neg\,p\land \neg\,q & \blue{\text{rule of De Morgan}}\\[0.2cm] &\iff & p\land\neg\, q & \blue{\text{double negation}}\end{array}$

For the proof of logical equivalence of two logical formulas, it is sometimes useful to replace sub-formulas of a given formula with other formulas. Such a replacement is called substitution in a more dignified, more mathematical wording.

Substitution Theorem

Suppose the formula $\varphi$ is a tautology. Suppose that $p$ is a propositional variable in $\varphi$ and that we replace occurrences of $p$ in $\varphi$ with a formula $\psi$ , then the result after substitution is also a tautology.
Suppose $\varphi$ is a logical formula and $\phi$ and $\chi$ are logically equivalent formulas. Suppose $p$ is a proposition variable in $\varphi$ and we replace occurrences of $p$ in $\varphi$ with $\psi$ and do exactly the same thing but replace $p$ with $\chi$ . Then the formulas obtained by these two substitutions are logically equivalent.

Suppose $p$ and $q$ are proposition variables. Consider $\varphi=p\rightarrow q$ . Furthermore, the formulas $\psi=q\rightarrow p$ and $\chi=\neg\, q\lor p$ are logically equivalent. Now we replace $p$ in $\varphi$ with $\psi$ and once with $\chi$ . Then we get the formulas $(q\rightarrow p)\rightarrow q$ and $(\neg q\lor p)\rightarrow q$ . According to the substitution theorem, these two formulas are logically equivalent.