Cvičení 20.9.2010

Na přednášce jsme se dozvěděli, že část náplně se přenáší do jiného předmětu (kdo má zapsaný?).

Cvičení dne 27.9. odpadá z důvodu rektorskeho volna.

Je třeba zpaměti znát převody různých operátorů mezi sebou (implikace na disjunkci, …) a rozklady asociativity, de Morganova pravidla. Pro toto cvičení si je opět necháme poznačené na tabuli.

Ekvivalenci formulí značíme ⇔ a definujeme ji tak, že dvě formule jsou ekvivalentní právě tehdy, pokud mají stejnou množinu modelů.

Normální formy (NF) nám pomohou při řešení složitějších příkladů. Používáme dvě NF - konjunktivní normální formu (KNF) a disjunktivní normální formu (DNF). KNF je konjuknce elementárních disjunkcí a DNF je disjunkce elementárních konjunkcí.

Úplná elementární disjunkce/konjunkce obsahuje vždy všechny elementární výroky - přímo nebo negovaně. Úplná KNF/DNF se skládá pouze z úplných elementárních disjunkcí/konjunkcí.

Každá úplná elementární konjunkce představuje v tabulce právě jeden řádek s výsledkem pravda (tj. model), každá úplná elementární disjunkce představuje právě jeden řádek s výsledkem nepravda. Z toho lze odvodit, že tautologie a kontradikce vždy jednu z úplných normálních forem nemají.

Úsudek můžeme tabulkou dokázat tak, že si ho pomocí věty o dedukci převedeme na formu tautologie a následně tabulkou ověříme, že formule je skutečně tautologie.

Další metodou je sématické tablo (i přes tento název jde o syntaktickou metodu, protože pracuje pouze se symboly). Na tomto cvičení nebude příliš prostoru se mu věnovat, takže pouze předvedu myšlenku a jednoduchý příklad. V principu jde o podobnou věc jako u tabulové metody, tedy dokázat tautologii nebo kontradikci, přičemž tato metoda samotná obsahuje postup tvorby normální formy.

V tomto cvičení přecházíme k mechaničtějším řešením, založeným na symbolech.

První příklad je podobný poslednímu příkladu z minulého cvičení, ale tentokrát místo použití hrubé síly (metoda tabulkou) použijeme ekvivalentní úpravy, které jsme si minule vyzkoušeli.

Hodně podobný je i třetí příklad. Cílem je najít úplné normální formy formulí. Zde použijeme obě metody, tedy tabulku i ekvivalentní úpravy.

V druhém příkladu si vyzkoušíme několik postupů, jak můžeme dokázat platnost úsudku. Až na přirozenou dedukci (která je podle plánu posledním tématem v tomto semestru) budou všechny metody řešit, zda je nějaká formuluje taugologie či kontradikce. Proto velmi často budeme používat větu o dedukci, abychom příklad na takovéto zadání převedli.