Matlogika

ojka.
Příklad:
„Praha je hlavní město ČR a v Praze je sídlo prezidenta ČR“ p q
„Praha je hlavní město ČR a 2 + 3 = 5“ p r

Pozor! Ne každé „a“ v přirozeném jazyce analyzujeme spojkou konjunkce, např.:
„Jablka a hrušky se pomíchaly“
„Přišel jsem domů a zatopil“.
3. Spojka disjunkce odpovídá „nebo“ (binární, komutativní spojka)

Pozor! Spojka „nebo“ se často používá v přirozeném jazyce ve vylučujícím smyslu „buď, anebo“, pak při analýze použijeme jinou spojku – alternativu (neboli nonekvivalenci ), viz tabulka všech binárních funkcí níže.
„Osobní auta mají přední nebo zadní náhon“ (nebo obojí) p q
„Napoleon diktoval nebo se procházel“ (nebo obojí) p q
Ale: „Tento muž je ženatý nebo svobodný“ (p q)
„Otec se zeptal, zda zůstanu doma nebo zda půjdu s ním“ (p q)
4. Spojka implikace odpovídá „ jestliže, pak“, „když, tak“, „je-li, pak “, apod.
Je to jediná binární spojka, která není komutativní, proto nazýváme první člen implikace antecedent , druhý konsekvent. Implikace nepředpokládá žádnou obsahovou souvislost mezi antecendentem a konsekventem, proto bývá někdy nazývána materiálová implikace (středověk „ suppositio materialis“ ).
Imp likace tedy (na rozdíl od častých případů v přirozeném jazyce) nezachycuje ani příčinnou ani časovou vazbu.
„Jestliže 1+1=2, pak železo je kov“ (pravdivý výrok) p q
„Jestliže existují ufoni, tak jsem papež“ p q
Pozn .: Co tím dotyčný vlastně tvrdí? Jelikož předpokládáme, že říká pravdu, a evidentně není papež (koncekvent je nepravdivý), musí být nepravdivý rovněž antecedent, tedy dotyčný chce říct, že ufoni neexistují.
5. Spojka ekvivalence odpovídá „ právě teh dy, když“, „tehdy a jen tehdy, když“ , apod. , ale ne „tehdy, když“ – to je implikace!
„Řecká vojska vyhrávala boje tehdy (a jen tehdy), když o jejich výsledku rozhodovala fyzická zdatnost“ p q
a) „Dám ti facku, když mě oklameš“ okl facka
b) „Dám ti facku tehdy a jen tehdy, když mě oklameš okl facka
Situace: Neoklamal jsem. Ad a) – můžu dostat facku, ad b) – nemůžu dostat facku.
Pozn .: V přirozeném jazyce se spojka ekvivalence používá zřídka, mnohem větší význam a častější použití má v exaktních vědách, zejména v matematice.
Pozn .: Převod z přirozeného do symbolické jazyka nemusí být vždy jednoznačný. (Proto také provádíme analýzu, abychom přirozené vyjádření zpřesnili, vybrali jeden z možných významů.)
Příklad: „Jestliže má člověk vysoký tlak a špatně se mu dýchá nebo má zvýšenou teplotu, pak je nemocen“.
p – „X má vysoký tlak“
q – „X se špatně dýchá“
r – „X má zvýšenou teplotu“
s – „X je nemocen“
1. analýza: [(p q) r] s 2. anal ý za: [p (q r)] s
Obě formule jsou různé, ale ze zadání nepoznáme, jak bylo tvrzení myšleno.
Poznámky 2.1.2:
1. Pravdivostní funkce složených formulí, definované tabulkou 2.1, lze ekvivalentně definovat následujícími vzorci:
w A) = 1-w A
w A B = min w A , w B
w A B = max w A , w B
w A B = max 1-w A , w B
w A B = max min w A , w B , min 1-w A , 1-w B
2. Obor pravdivostních hodnot nemusí být nutně dvouprvkovou množinou 1, 0 , ale může být také např. tříprvkovou množinou 0, 1/2, 1 , nebo nekonečnou spojitou množinou danou reálným uzavřeným intervalem . Pravdivostní funkce mohou být i nyní definovány výše uvedenými vzorci, ale také nějakým jiným způsobem. Výrokové logiky s takto definovanými pravdivos tními funkcemi nazýváme vícehodnotovými , resp. spojitěhodnotovými . V dalším se však budeme zabývat pouze dvouhodnotovou logikou s výše definovanými pravdivostními funkcemi.

Příklad 2.1.2:
V následující tabulce jsou počítány pravdivostní funkce formulí:
p, q, p q (sloupce označené 1),
( p q), (p q) /sloupce označené 2/,
( p q) (p q) /3.sloupec/ a
[( p q) (p q)] /4.sloupec/.
Sloupce v tabulce vyplňujeme v pořadí vyznačeném pořadovými čísly uvedenými ve druhém řádku tabulky (tj. při určování pravdivostní funkce formule postupujeme ve směru rostoucího hierarchického řádu podformulí). Sloupce označené 0 obsahují všechny možné kombinace ohodnocení výrokových symbolů, n-té sloupce se počítají na základě sloupců (n-1)-ých.

p q p q 4. 1. 0. 2. 1. 0. 3. 2. 0. 1. 0. 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1

Definice 2.1.3:
Je-li formule A vytvořena z k různých výrokových symbolů, pak existuje celkem 2 k různých ohodnocení (valuací) v formule A. Každé ohodnocení v výrokových symbolů obsažených ve formuli A, pro které je hodnota pravdivostní funkce rovna 1, tedy w (A) = 1, se nazývá model této formule .
Formule A výrokové logiky je splnitelná , je-li w(A) = 1 pro nějaké ohodnocení v, neboli existuje aspoň jeden model formule A.
Formule A výrokové logiky je tautologií /logickým zákonem/ , je-li w(A) = 1 pro všechna ohodnocení v, neboli každé ohodnocení je modelem formule A. Skutečnost, že formule A je tautologií, označujeme zápisem |= A.
Formule A výrokové logiky je kontradikcí , jestliže neexistuje takové ohodnocení výrokových symbolů, pro které by hodnota pravdivostní funkce formule A byla rovna 1, tj. w(A) = 0 pro všechna ohodnocení v, formule nemá model.
Množina formulí M je splnitelná , jestliže existuje valuace v taková, že w (A) = 1 pro každou formuli A M. Takové ohodnocení v se pak nazývá model množiny M.
Formule A výrokově logicky vyplývá z množiny formulí M, značíme M |= A, jestliže A je pravdivá v každém modelu množiny M.

Poznámka 2.1.3:
Připomeňme si obecnou definici logického vyplývání (Definice 1.1.) z úvodní kapitoly. (Za všech okolností, kdy jsou pravdivé premisy, musí být pravdivý i závěr.) Vidíme tedy, že ty okolnosti mapujeme ve výrokov é logice pouze jako ohodnocení výrokových proměnných (což odpovídá pravdivosti či nepravdivosti elementárních výroků).
Jestliže je množina formulí sporná, pak nemá model, a tedy (viz vlastnost 5) - kap. 1) z ní vyplývá jakákoli formule.
Jak jsme již naznačili v příkladě 2.1.2, pro zjištění pravdivostní hodnoty formule používáme tabulkové metody. Musíme prozkoumat všechny možné valuace v. Je-li n počet výrokově logických proměnných v A, pak počet valuací je 2 n a příslušná tabulka má 2 n řádků.
Příklad 2.1.3:
Formule p, q, p, q, p q, p q, p q , ( p q) p q jsou splnitelné.
Např. formule p q je pravdivá (má pravdivostní hodnotu 1) pro ohodnocení 0,1 výrokových symbolů p,q ). Rovněž ohodnocení (1,0), ( 0,0) jsou její modely, ale ne (1,1).
Formule ( p q) p q je tautologií. Pro všechna možná ohodnocení 0,0 , 0,1 , 1,0 , 1,1 výrokových symbolů p, q je tato formule pravdivá. Každé ohodnocení formuli splňuje , je jejím modelem.
Formule [ p q) p q ] je kontradikcí. Neexistuje ohodnocení výrokových symbolů p, q pro které by byla formule pravdivá. Žádné ohodnocení formuli nesplňuje, formule nemá model.
Platnost uved ených tvrzení okamžitě plyne z tabulky předchozího příkladu 2.1.2.

Zjistíme, zda množina formulí M = p r, q r, p q je splnitelná:

p q r p r q r p q 1 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 Daná množina M je splnitelná a jejími modely jsou ohodnocení odpovídající 1., 3. a 5. řádku. Dále z tabulky vidíme, že z množiny M logicky vyplývá formule r. Pro každý mod el této množiny je r pravdivá. Tedy (závorky pro množinu premis není nutno uvádět): p r, q r, p q |= r
Příklad 2.1.4 /některé důležité tautologie výrokové logiky/ :
Tautologie s jediným výrokovým symbolem:
|= p p
|= p p zákon vyloučeného třetího
|= (p p) zákon sporu
|= p p zákon dvojí negace
Algebraické zákony:
|= ( p q) (q p) komutativní zákon pro
|= ( p q) (q p) komutativní zákon pro
|= ( p q) (q p) komutativní zákon pro
|= ( p q) r p (q r) asociativní zákon pro
|= ( p q) r p (q r) asociativní zákon pro
|= (( p q) r) (p (q r)) asociativní zákon pro
|= ( p q) r (p r) (q r) distributivní zákon pro ,
|= ( p q) r (p r) (q r) distributivní zákon pro ,
Zákony pro implikaci:
|= p (q p) zákon simplifikace
|= ( p p) q zákon Dunse Scota
|= (p q) ( q p) zákon kontrapozice
|= ( p (q r)) ((p q) r) spojování předpokladů
|= ( p (q r)) (q (p r)) na pořadí předpokladů nezáleží
|= ( p q) ((q r) (p r)) hypotetický sylogismus
|= (( p q) (q r)) (p r) tranzitivita implikace
|= ( p (q r)) ((p q) (p r)) Fregův zákon
|= ( p p) p reductio ad absurdum
|= (( p q) (p q)) p reductio ad absurdum
|= ( p q) p , |= ( p q) q
|= p (p q) , |= q (p q)
Zákony pro vzájemné převody funktorů:
|= ( p q) (p q) (q p)
|= ( p q) (p q) ( q p)
|= ( p q) ( p q)
|= ( p q) (p q) Negace implikace !
|= ( p q) ( p q) De Morganovy zákony
|= ( p q) ( p q) De Morganovy zákony

Pozn. : Uv edené zákony snadno ověříme tabulkovou metodou.
Metoda protipříkladu - ověřování tautologií (vyplývání) sporem:
Tabulková metoda ověřování logického vyplývání či logických zákonů, splnitelnosti, atd. je vhodná pouze pro formule s malým počtem výrokových proměnných. Vždyť již při čtyřech proměnných má příslušná tabulka 16 řádků, při pěti 32 řádků! Proto jsou používány jiné, vhodnější metody. Jednou z nich je metoda protipříkladu, která je zejména vhodná pro ověřování tautologií ve tvaru implikace a pro ověřo vání logického vyplývání. (S ostatními se seznámíme v dalším textu.)
Příklad 2.1.5
Ověříme zákon simplifikace p (q p). Vycházíme z toho, že implikace je nepravdivá jen v jednom případě (Tab. 2.1), a to když je antecendent pravdivý a konsekvent nepravdivý. Prověříme tedy všechny valuace, pro něž je konsekvent nepravdivý a jestliže alespoň pro jednu z těchto valuací nastane případ, že by byl antecedent pravdivý, nemůže být daná formule tautologie a naopak, jestliže pro žádnou z těchto valuací není antecedent pravdivý, je uvažovaná formule tautologie. V našem případě bude konsekvent nepravdivý pouze při jedné valuaci, a to q = 1, p = 0. Ale v tom případě nemůže být antecedent p = 1, tedy celá formule je pravdivá i pro tuto valuaci. Nyní vše názorněji:
p (q p)
1 0
1 0
0 ! spor !
Nyní ověříme, zda formule p logicky vyplývá z množiny p q, r q, r . Názorně tedy prověříme úsudkové schéma (všimněte si, že je to formalizace úsudku z kapitoly 1 „o kurzu a přednášejícím“):
p q, r q, r / p
1 1 1 0
0 1
1 1 0 1
0 ! spor !

Věta 2.1.1 /o substituci/ :
Nechť A je tautologie výrokové logiky utvořená z výrokových symbolů p 1 , p 2 ,...,p n . Nechť formule B vznikne z tautologie A simultánním nahrazením výrokových symbolů p 1 , p 2 ,...,p n formulemi A 1 ,A 2 ,...,A n (tj. substitucemi A i za p i pro i = 1, 2,...,n). Potom formule B je rovněž tautologií.
Důkaz:
Uvažujme libovolné pravdivostní ohodnocení výrokových symbolů obsažených ve formuli B a nechť při tomto ohodnocení mají formule A 1 ,A 2 ,...,A n pravdivostní hodnoty h 1 ,h 2 ,...,h n . Udělíme-li tyto hodnoty výrokovým symbolům p 1 ,p 2 ,...,p n formule A, budou mít formule A i B stejnou pravdivostní hodnotu. Vzhledem k tomu, že A je tautologie, bude tato pravdivostní hodnota vždy 1.
Poznámka 2.1.4:
Věta o substituci umožňuje vytvořit k dané tautologii neomezeně mnoho dalších tautologií, které mají s danou výchozí ta