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 en de formules en logisch equivalent zijn.
Oplossing.
We geven achtereenvolgende equivalenties die herleiden tot :
Bewijs van equivalentie Toon aan dat voor propositievariabelen en de formules en logisch equivalent zijn.
Oplossing.
We geven achtereenvolgende equivalenties die herleiden tot :
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 een tautologie is. Stel dat een propositievariabele in is en dat we alle voorkomens van in vervangen door een formule , dan is het resultaat na substitutie ook een tautologie.
- Stel dat een logische formule is en dat en logisch equivalente formules zijn. Stel dat een propositievariabele in is en dat we één of meer voorkomens van in vervangen door en precies hetzelfde doen maar dan met een vervanging van met . Dan zijn de formules verkregen door deze twee substituties logisch equivalent.
Stel en zijn propositievariabelen. Bekijk . Verder zijn de formules en logisch equivalent. We vervangen nu in door en een keer door . We krijgen dan de formules en . Volgens de substitutiestelling zijn deze twee formules dan logisch equivalent.