====== Cvičení 20.9.2010 ====== ===== Organizační ===== * 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 [[http://www.vsb.cz/okruhy/nastroje-sluzby/infoservis/detaily/?detail=15688|rektorskeho volna]]. ===== Teorie ===== * 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. ===== Cvičení ===== * 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.