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.
Simplifying a logical formula 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}\]
Proof of equivalence 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 all 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 one or more 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.
