Propositielogica: Geldig gevolg en consistentie
Werken met logisch equivalente formules
We hebben de vorige theoriepagina wel Nuttige tautologieën genoemd, maar wat is hun nut dan? Een voorbeeld maakt duidelijk dat ze een grote rol spelen bij het vereenvoudigen van samengestelde logische formules en in bewijzen dat twee formules logisch equivalent zijn zonder de waarheidstabel van de formules op te stellen.
Vereenvoudiging van een logische formule Laat zien dat dat voor propositievariabelen \(p\) en \(q\) de formules \((p\lor q)\land\neg(\neg\,p\land q)\) en \(p\) logisch equivalent zijn.
Oplossing.
We geven achtereenvolgende equivalenties die \((p\lor q)\land\neg(\neg\,p\land q)\) herleiden tot \(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{regel van De Morgan}}\\[0.2cm] &\iff & (p\lor q)\land(p\lor \neg\, q) & \blue{\text{dubbele ontkenning}}\\[0.2cm] &\iff & p\lor( q\land \neg\, q)& \blue{\text{distributiviteit}}\\[0.2cm] &\iff & p\lor \psi\text{ voor elke contradictie } \psi& \blue{\text{inversie}}\\[0.2cm]
&\iff & p& \blue{\text{identiteit}}\end{array}\]
Bewijs van equivalentie Toon aan dat voor propositievariabelen \(p\) en \(q\) de formules \(\neg(p\rightarrow q)\) en \(p\land\neg\, q\) logisch equivalent zijn.
Oplossing.
We geven achtereenvolgende equivalenties die \(\neg(p\rightarrow q)\) herleiden tot \(p\land\neg\, q\): \[\begin{array}{rll} \neg(p\rightarrow q)&\iff& \neg(\neg\,p\lor q) & \blue{\text{contrapositie}}\\[0.2cm] &\iff & \neg\neg\,p\land \neg\,q & \blue{\text{regel van De Morgan}}\\[0.2cm] &\iff & p\land\neg\, q & \blue{\text{dubbele negatie}}\end{array}\]
Voor het bewijs van logische equivalentie van twee logische formules is het soms handig om deelformules van een gegeven formule te vervangen door andere formules. Zo'n vervanging heet met een deftiger, meer wiskundig woord substitutie.
Substitutiestelling
- Stel dat de formule \(\varphi\) een tautologie is. Stel dat \(p\) een propositievariabele in \(\varphi\) is en dat we alle voorkomens van \(p\) in \(\varphi\) vervangen door een formule \(\psi\), dan is het resultaat na substitutie ook een tautologie.
- Stel dat \(\varphi\) een logische formule is en dat \(\phi\) en \(\chi\) logisch equivalente formules zijn. Stel dat \(p\) een propositievariabele in \(\varphi\) is en dat we één of meer voorkomens van \(p\) in \( \varphi\) vervangen door \(\psi\) en precies hetzelfde doen maar dan met een vervanging van \(p\) met \(\chi\). Dan zijn de formules verkregen door deze twee substituties logisch equivalent.
Stel \(p\) en \(q\) zijn propositievariabelen. Bekijk \(\varphi=p\rightarrow q\). Verder zijn de formules \(\psi=q\rightarrow p\) en \(\chi=\neg\, q\lor p\) logisch equivalent. We vervangen nu \(p\) in \(\varphi\) door \(\psi\) en een keer door \(\chi\). We krijgen dan de formules \((q\rightarrow p)\rightarrow q\) en \((\neg q\lor p)\rightarrow q\). Volgens de substitutiestelling zijn deze twee formules dan logisch equivalent.
