WisFaq!

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 Oosting
17-8-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:




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
18-8-2003