Petr Hliněný, FI MU Brno 1 FI: IB000: Úvod do Logiky 7 Jemný úvod do Logiky7 Jemný úvod do Logiky Základem přesného matematického vyjadřování je správné používání (matematické) logiky a logických úsudků. Logika jako filozofická disciplína se intenzivně vyvíjí už od dob antiky, avšak ke skutečnému rozmachu logiky coby součásti matematiky došlo až začátkem 20. století. 2 Dnes se samozřejmě základní logický kalkulus používá nejen v matematice, ale ,,stojí na něm veškeré logické obvody a počítače. Stručný přehled lekce * Výroky v přirozené mluvě a formální výroková logika. * Mechanický postup negace výrokových formulí. * Neformální zmínka o predikátové logice (a kvantifikátorech). Petr Hliněný, FI MU Brno 2 FI: IB000: Úvod do Logiky 7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl prohlásit, že je buď pravdivé nebo nepravdivé.2 Několik příkladů, které z nich jsou výroky? * Dnes už v Brně pršelo.2 * Předmět FI: IB000 se vyučuje v prvním ročníku.2 * Platí 2 + 3 = 6.2 * To je bez problémů. (Co?)2 * Platí x > 3.2 * Pro každé celé číslo x platí, že x > 3.2 Všimněte si, že pravdivost výroku by mělo být možné rozhodnout bez skrytých souvislostí (kontextu), a proto čtvrtý a pátý příklad za výroky nepovažujeme. Fakt: Z jednoduchých výroků můžeme vytvářet výroky složitější pomocí tzv. logických spojek. Petr Hliněný, FI MU Brno 3 FI: IB000: Úvod do Logiky Několik dalších příkladů. * Kateřina přijela ve 12:00 a šli jsme spolu do kina.2 * Množina {a, b} má více než jeden prvek a není nekonečná.2 * Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem.2 * Jestliže má kráva 10 nohou, mají všechny domy modrou střechu. Schopnost porozumět takovýmto větám je součást lidského způsobu uvažování a z tohoto hlediska nemá přímou souvislost s matematikou (je to ,,přirozená logika ).2 Formální (matematická) logika pak definuje jazyk matematiky a odstraňuje nejednoznačnosti přirozeného jazyka. Petr Hliněný, FI MU Brno 4 FI: IB000: Úvod do Logiky 7.2 (Formální) výroková logika7.2 (Formální) výroková logika Definice 7.1. Syntaxe výrokové logiky. Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných (tzv. atomů). Množina výrokových formulí je definována induktivně následujícími pravidly: (1) AT . 2 (2) Jestliže , , pak také () a () () . 2 (3) Každý prvek vznikne konečně mnoha aplikacemi pravidel (1) a (2).2 Značení: Symbol je zván negací a je nazýván implikací. Příklady několika správně utvořených formulí: A, (A) (B), ((A) ((B))) (((B)) (C))2 A také příklady několika ne zcela správně utvořených formulí: A B, A B C, A B Petr Hliněný, FI MU Brno 5 FI: IB000: Úvod do Logiky Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to nepovede k nejednoznačnostem za předpokladu, že negace má ,,vyšší prioritu než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace jejích prvků.) 2 Dále si zavedeme, že (disjunkce) je jiný zápis formule ,2 (konjunkce) je jiný zápis formule ( ),2 (ekvivalence) je jiný zápis formule ( ) ( ).2 Například formule (((A) (B))) (((B)) (C)) se dá s naší konvencí zapsat jako (A B) B C . Petr Hliněný, FI MU Brno 6 FI: IB000: Úvod do Logiky Definice 7.3. Sémantika výrokové logiky. Valuace (ohodnocení) je funkce : AT {true, false}. 2Pro každou valuaci definujeme funkci S : {true, false} (vyhodnocení) induktivně takto: * S(A) = (A) pro každé A AT . 2 * S() = true jestliže S() = false; false jinak. 2 * S( ) = false jestliže S() = true a S() = false; true jinak. 2 Tvrzení 7.4. Důsledkem této definice je následovné: * S( ) = true právě když S() = true nebo S() = true. 2 * S() = true právě když S() = true a současně S() = true.2 * S( ) = true právě když platí jedna z následujících podmínek S() = true a současně S() = true, S() = false a současně S() = false.2 Poznámka: Tento předpis podává nejen definici funkce S, ale také návod na to, jak ji pro daný argument vypočítat. 2 Petr Hliněný, FI MU Brno 7 FI: IB000: Úvod do Logiky Pravdivostní hodnoty V praxi často vyhodnocení S logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky má sloupce pro jednotlivé proměnné, případné ,,meziformule (pomůcka pro snažší vyplnění) a výslednou formuli. Řádků je 2p (počet valuací), kde p je počet použitých proměnných. Místo true, false píšeme 1, 0. Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem. 2 Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A B) B C? A B C A B (A B) B C 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 2 Petr Hliněný, FI MU Brno 8 FI: IB000: Úvod do Logiky Definice: Formule je splnitelná, pokud pro některou valuaci platí, že S() = true.2 Formule je vždy pravdivá, neboli výroková tautologie, psáno |= , pokud pro každou valuaci platí, že S() = true.2 Řekneme, že dvě formule , jsou ekvivalentní, právě když |= . 2 Tvrzení 7.6. Několik užitečných tautologií: * |= A A2 * |= A A2 * |= (A (A B)) B2 * |= (B A) (A B)2 * |= (A (B B)) A Kde jsme se s užitím takových tautologií už setkali? Petr Hliněný, FI MU Brno 9 FI: IB000: Úvod do Logiky 7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ? Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (podobně jako v běžné řeči).2 ,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad. 2 Výrokové formule se proto obvykle prezentují v tzv. normálním tvaru, kde se negace vyskytují pouze u výrokových proměnných, formálně:2 Definice: Formule je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné. Například, pokud přijmeme pravidlo ,,dvojí negace ( A A), tak výše napsanou větu si převedeme na lépe srozumitelný tvar: ,,Nemusím říct, že tě mám nerad. 2 Tvrzení 7.7. Každou výrokou formuli lze převést do normálního tvaru, pokud k povolíme i užívání odvozených spojek a . 2 * Pro ilustraci k (A B) je ekvivalentní A B, * k C (A B) je ekvivalentní C (A B). Petr Hliněný, FI MU Brno 10 FI: IB000: Úvod do Logiky Normální tvar (formální postup) ,,Znegováním formule se obvykle myslí převod do normálního tvaru. 2 Metoda 7.8. Převod formule do normálního tvaru F(). Definujeme funkce F a G pro náš převod induktivními předpisy F(A) = A G(A) = A F() = G() G() = F() F( ) = F() F() G( ) = F() G() F( ) = F() F() G( ) = G() G() F( ) = F() F() G( ) = G() G() F( ) = F() F() G( ) = (F() G()) (G() F())2 Uvažme formuli (A (B (C A))). Užitím postupu 7.8 získáme: F((A (B (C A)))) = G(A (B (C A))) = 2 F(A) G((B (C A))) = A F(B (C A)) = 2 A (F(B) F((C A))) = A (B G(C A)) = A (B (F(C) G(A))) = A (B (C F(A))) = A (B (C A))2 Petr Hliněný, FI MU Brno 11 FI: IB000: Úvod do Logiky Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v matematicky přesném tvaru. Důkaz tohoto tvrzení je zároveň velmi hezkou ukázkou použití strukturální matematické indukce. Věta 7.9. Pro libovolnou výrokovou formuli platí, že a) F() je jí ekvivalentní formule v normálním tvaru b) a G() je formule v normálním tvaru ekvivalentní negaci . 2 Důkaz povedeme tzv. ,,indukcí ke struktuře formule , tedy indukci povedeme podle ,,délky ­ počtu aplikací induktivních pravidel (Definice 7.1) při sestavování formule . 2 * Báze indukce ( = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že F(A) = A je ekvivalentní A a G(A) = A je ekvivalentní A. 2 * V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule délky nejvýše . Vezmeme si formuli délky +1, která je utvořená jedním z následujících způsobů: Petr Hliněný, FI MU Brno 12 FI: IB000: Úvod do Logiky ( je ,,definiční rovnítko pro formule). Podle výše uvedeného induktivního předpisu je F() = F() = G(). Podle indukčního předpokladu pak je G() formule v normálním tvaru ekvivalentní = . 2 Obdobně pro funktor G vyjádříme G() = G() = F(). Podle indukčního předpokladu pak je F() formule v normálním tvaru ekvivalentní a to je dále ekvivalentní = podle Tvrzení 7.6. 2 (1 2). Podle výše uvedeného induktivního předpisu je F() = F(1 2) = F(1) F(2). Podle indukčního předpokladu jsou F(1) i F(2) formule v normálním tvaru ekvivalentní 1 a 2. Potom i F(1) F(2) je v normálním tvaru dle definice a podle sémantiky je ta ekvivalentní formuli (1 2) = . 2 Obdobně rozepíšeme G() = G(1 2) = F(1) G(2). Jelikož je pro nás jen zkratka, výraz dále rozepíšeme G() = (F(1) G(2)). Podle indukčního předpokladu (a dvojí negace) jsou F(1) a G(2) po řadě ekvivalentní formulím 1 a 2. Tudíž nakonec odvodíme, že G() je ekvivalentní negaci formule 1 2, což jsme zde měli dokázat. Petr Hliněný, FI MU Brno 13 FI: IB000: Úvod do Logiky (1 2). Zde si musíme opět uvědomit, že spojka je pro nás jen zkratka, a přepsat (1 2). Potom podle předchozích dokázaných případů víme, že F() = F(1 2) = F(1) F(2) je ekvivalentní formuli (1 2) = , což bylo třeba dokázat. Stejně tak G() = G(1 2) = F(1) G(2) je podle předchozích případů důkazu ekvivalentní (1 2) = . 2 (1 2) a (1 2) už dokončíme analogicky. 2 Petr Hliněný, FI MU Brno 14 FI: IB000: Úvod do Logiky 7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace * Predikátová logika je obecnější než logika výroková; každá formule výrokové logiky je i formulí predikátové logiky, ale ne obráceně.2 * Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované výroky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. 2Výrokové proměnné lze chápat jako predikáty bez parametrů.2 Pro neformální přiblížení si uvedeme několik ukázek predikátů: x > 3 (parameterem je zde x),2 R je ekvivalence na M (parametr R),2 čísla x a y jsou nesoudělná (parametry x, y), obecně psáno P(x, y).2 Definice 7.10. Syntaxe i sémantika predikátové logiky. Z predikátů lze vytvářet predikátové formule pomocí už známých (viz Definice 7.1) výrokových spojek a následujících tzv. kvantifikátorů: * x . ,,pro každou volbu parametru x platí formule , * x . ,,existuje alespoň jedna volba parametru x, pro kterou platí . Petr Hliněný, FI MU Brno 15 FI: IB000: Úvod do Logiky Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je celá formule buď pravdivá nebo nepravdivá.2 Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se domluvíme na následujícím. ,,Neuzavřené proměnné vyskytující se v predikátech ve formuli někdy pro referenci vypisujeme jako ,,parametry samotné formule (x, y, . . .).2 Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá se notace x M . a x M . . (Platí, jen pokud je kvantifikovaný parametr prvkem nějaké fixní množiny!). 2 Tečka za symbolem kvantifikátoru se někdy vynechává (při vhodném uzávorkování formule), nebo se používá symbol ,, : .2 Místo x1 . x2 . xn . se někdy krátce píše x1, x2, , xn . . Podobně u existenčního kvantifikátoru x1, x2, , xn . . Petr Hliněný, FI MU Brno 16 FI: IB000: Úvod do Logiky Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice: * Každé prvočíslo větší než 2 je liché, n . (Pr(n) n>2) Li(n). 2 * Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde n = y a y > 1, n . (n > 1 Pr(n) y . (y| n n=y y>1)). 2 * Jsou-li R a S ekvivalence na M, je také R S ekvivalence na M. Zde například můžeme mít dva pohledy na toto tvrzení ­ v jednom bereme množinu M za pevnou R, S : (EqM (R) EqM (S)) EqM (RS), kdežto ve druhém je i množina M parametrem M R, S : (Eq(M, R) Eq(M, S)) Eq(M, RS). 2 Petr Hliněný, FI MU Brno 17 FI: IB000: Úvod do Logiky Jak ,,negovat formule predikátové logiky? Metoda 7.13. Převod predikátové formule do normálního tvaru F(). Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla: F(P(x1, . . . , xn)) = P(x1, . . . , xn) G(P(x1, . . . , xn)) = P(x1, . . . , xn) F(x . ) = x . F() G(x . ) = x . G() F(x . ) = x . F() G(x . ) = x . G()2 Uvažme například formuli (M R, S : (Eq(M, R) Eq(M, S)) Eq(M, RS)) . Pak F((M R, S : (Eq(M, R) Eq(M, S)) Eq(M, RS))) = 2G(M R, S : (Eq(M, R) Eq(M, S)) Eq(M, RS)) = 2M R, S : G((Eq(M, R) Eq(M, S)) Eq(M, RS)) = M R, S : (Eq(M, R) Eq(M, S) Eq(M, RS)) .