Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Logica - semantische tableaus

Kan iemand mij helpen met het volgende probleem:
Toon aan dat de volgende propositie een tautologie is, zonder gebruik te maken van een waarheidstabel. Geef bij elke stap een verantwoording:

(¬(Q $\Rightarrow$ R)$\vee$¬(¬Q $\Rightarrow$(R V S)))$\Rightarrow$ (¬ R$\Rightarrow$S)

Harrie
Docent - zondag 17 augustus 2003

Antwoord

Naast het testen op tautologieën via een waarheidstabel, kan je ook semantische tableaus gebruiken. Om te controleren of een formule g onder elke waardering waar is, bekijk je het sequent met aan de linkerkant het lege rijtje:

o g

Als dit sequent geen tegenvoorbeeld heeft, dan is g waar in elk model van de lege verzameling. Aangezien elke waardering model is van de lege verzameling, is elke waardering model van g. Dus g is een tautologie als een tableau van o g sluit.

Ik weet niet in hoeverre je bekend bent met semantische tableaus. De werkwijze is in ieder geval vrij eenvoudig. Je moet gewoon de klassieke herschrijfregels gebruiken en zien of het tableau daarmee sluitend kan gemaakt worden.

Ik zet ze even op een rijtje:

q13492img1.gif
q13492img2.gif

Een tableau sluit als alle taken ontstaan door het toepassen van de herschrijfregels sluiten. Een tak sluit als een formule zowel links als rechts van het sequent voorkomt.

Daarmee zou het op zich moeten lukken.

Iris
maandag 18 augustus 2003

©2001-2024 WisFaq