Vyrokova_predikatova_logika

uzel stromu, který není kořenem, platí, že množina jeho předchůdců je dobře uspořádána relací ( .
Strom, jehož každý uzel má nejvýše n následníků, se nazývá n-árním stromem.
Cestou stromem S je každá maximální lineárně uspořádaná podmnožina S.
Uzel stromu S, který nemá následníka, je listem stromu.
Symboly abecedy jazyka L výrokové logiky
Jazyk L výrokové logiky, který zde bude definován, vychází ze základní množiny elementárních symbolů, které tvoří jeho abecedu definovanou pro výrokovou logiku takto :
Definice . (abecedy jazyka L výrokové logiky)
Symboly abecedy jazyka L výrokové logiky patří výhradně do některé z následujících skupin elementárních symbolů :
(1) Symboly a,b,c,...,a1,b1,c1,... pro výrokové proměnné
(2) Symboly pro logické konstanty true (T) a false (F)
(3) Symboly pro logické spojky :
( negace
& konjunkce
( disjunkce
( implikace
( ekvivalence
(4) Pomocné symboly - závorky.

Podle počtu operandů se rozlišují mezi základními výrokovými spojkami spojka unární, tou je spojka (, a spojky binární, k nimž patří všechny zbývající čtyři základní spojky &, (, (, (.
Logické konstanty true a false bývají někdy též považovány za nulární výrokové spojky.
K tomu, aby bylo možno definovat syntax formulí jazyka výrokové logiky pomocí indukce a ukázat možnost její stromové reprezentace, je třeba si v následujícím odstavci připomenout některé pojmy teorie množin.
Definice gramatiky jazyka L výrokové logiky
Jak již bylo uvedeno v lekci 1., syntax jazyka je určena jeho gramatikou. V definici 2.1 byly zavedeny bázové symboly abecedy jazyka L, z nichž se vytvářejí formule jazyka výrokové logiky. Zde zavedeme pomocí induktivní definice způsob jejich vytváření určený gramatikou jazyka L výrokové logiky.
Následující induktivní způsob definování formulí výrokové logiky je zároveň návodem k jejich konstrukci, neboť obsahuje jednak určení základních stavebních prvků (bázi), z nichž je formule konstruována, jednak induktivní postup, jak z jednodušších formulí zkonstruovat formule složitější.
Gramatika jazyka L výrokové logiky vychází z konečné nebo spočetné množiny symbolů dané abecedy (viz definici 1.10) - atomů představujících základní dobře utvořené formule výrokové logiky. Z nich lze tvořit další dobře utvořené formule podle gramatických pravidel formulovaných induktivně v následující definici.
Definice . (gramatických pravidel jazyka L výrokové logiky)
Symboly abecedy skupiny (1) označující výrokové proměnné a skupiny (2) označující logické konstanty true a false představují atomické formule neboli atomy jazyka L výrokové logiky.
Báze : Každá atomická formule je formulí.
Indukce : Jsou-li X a Y formule, pak (X, X & Y , X ( Y , X ( Y a X ( Y jsou formule.
Generalizace : Všechny dobře utvořené formule jazyka výrokové logiky jsou výsledkem konečného počtu aplikací základního pravidla a pravidla indukce.
Symboly X, Y uvedené v předcházející induktivní definici gramatiky jazyka výrokové logiky nepatří k symbolům jazyka, nýbrž zde zastupují jeho libovolné formule. Obecně syntax jazyka nelze definovat jazykem samotným, nýbrž je potřeba použít metajazyka, v tomto případě jistým způsobem schématizovaného jazyka přirozeného, v němž zmíněné symboly sehrávají vůči jazyku výrokové logiky roli metasymbolů.
Backus - Naurova forma definice gramatiky jazyka L
Gramatiku jazyka L definovanou induktivně standardním způsobem v definici 1.11 lze též zapsat formou která je známa v informatice jako Backus - Naurova forma :
( formule ( ::= ( výroková proměnná (
::= ( logická konstanta (
::= ( (( formule ()
::= (( formule (( binární logická spojka (( formule ()
( výroková proměnná ( ::= a / b / c /......
( logická konstanta ( ::= true / false
( binární logická spojka ( ::= ( / ( / ( / (
Konstrukce výrokové formule
Induktivní proces vytváření formule aplikací gramatických pravidel se, jak vyplývá z předcházejícího odstavce, děje v postupných krocích, z nichž v každém rovněž vzniká rovněž dobře utvořená formule. Ty pak tvoří jistou posloupnost zvanou konstrukce formule. Konstrukce formule je tím složitější, čím je posloupnost nutných konstrukčních kroků vedoucích k jejímu vytvoření delší.
Definice . (konstrukce formule a její složitosti)
Konstrukce formule A z množiny atomů je posloupnost formulí B1 , B2 ,...,Bn , Bn = A, taková, v níž Bi , 1(i(n, je buď bázový atom nebo vznikla z B1 , B2 ,...,Bi-1 aplikací pravidla indukce.
Je-li posloupnost B1 , B2 ,...,Bn nejkratší konstrukcí formule A, pak B1 , B2 ,..., Bn jsou všechny podformule formule A a číslo n udává složitost konstrukce formule A.
Úmluva :
Pro eventuální možnost úspornějšího zápisu složitějších výrokových formulí s více binárními spojkami bez použití závorek budou zde zavedeny jisté úmluvy :
1. Priorita spojek bude dodržována v tomto pořadí :
, &, (, (, (
Např. formule
p ( q ( r ( p
bude konstruována jako formule
((p ( q) ( r) ( p .
2. Formule obsahující pouze vícenásobný výskyt téže binární spojky bude konstruována postupem zleva doprava.
Např. formule
p ( q ( p ( r
bude konstruována jako formule
((p ( q) ( p) ( r .
Příklad .
Zapište posloupnost podformulí představující konstrukci následující formule A
((p & q)  false) ( q
a stanovte složitost této konstrukce.
Konstrukci dané formule A tvoří např. (pořadí počátečních prvků posloupnosti označujících výrokové proměnné může být jiné) tato posloupnost jejích podformulí :
p, q, q, p & q, false, (p & q)  false, ((p & q)  false) ( q.
Konstrukce formule má složitost 7, neboť konstrukce formule je v každém případě posloupností o 7 členech.
Stromová reprezentace a míry složitosti formule
Formuli A z příkladu 1.2, při jejíž konstrukci bylo postupně použito pravidlo indukce pro spojky , &, ( a ( , lze, jak bude ukázáno, přiřadit (obr. 1.2) ohodnocený strom, jehož uzlům jsou postupně přiřazovány jako jejich návěští všechny podformule posloupnosti tvořící konstrukci formule. Pro takto vytvořený syntaktický formační strom je výsledná formule návěštím jeho kořene.
Jak bude dále dokázáno, přísluší každé dobře utvořené formuli výrokové logiky jediný syntaktický formační strom. Protože všechny zavedené výrokové spojky jsou spojkami nejvýše binárními, lze pro reprezentaci syntaxe výrokových formulí využít vlastností pouze binárních stromů.
Konstrukci formule A z předcházejícího příkladu 1.2. lze reprezentovat konečným binárním stromem, jehož kořen je označen návěštím tvaru výsledné formule A a jehož listy nesou jako návěští atomické podformule formule A. Konstrukci formule A z předcházejícího příkladu 1.2. odpovídá, jak ukazuje obr. 1.2, grafickou formou reprezentovaný syntaktický formační strom.
((p & q)  false) ( q

(p & q)  false q
p & q false q

p q
obr.1 \s 1.
Vlastností syntaktického formačního stromu formule se týká následující definice.
Definice . (syntaktického formačního stromu formule)
Syntaktický formační strom formule A jazyka L výrokové logiky je konečný binární strom, jehož všechny uzly jsou označeny návěštími - podformulemi formule A tak, že platí :
Kořen je označen formulí A.
Jestliže je uzel označen některým z návěští X & Y , X ( Y , X ( Y , X ( Y, kde X, Y jsou formule, pak uzly bezprostředně následující nesou po řadě (z leva do prava) návěští X a Y.
Je-li uzel označen podformulí (X, pak uzel bezprostředně následující nese jako návěští podformuli X.
Listy jsou označeny atomickými formulemi vyskytujícími se v A.
Věta .
Ke každé výrokové formuli existuje jediný odpovídající syntaktický formační strom.
Důkaz
Dokážeme nejdříve existenci syntaktického formačního stromu libovolné výrokové formule A. Ve druhém kroku pak dokážeme jeho jedinečnost. Důkaz bude proveden způsobem odpovídajícím induktivní definici syntaxe formule, tj. indukcí.
a) Důkaz existence syntaktického formačního stromu formule :
Pro atomickou formuli sestává syntaktický formační strom pouze z kořene, jehož návěštím je právě tato atomická formule (symbol pro elementární výrok nebo konstantu true/false).
Předpokládejme existenci syntaktického formačního stromu pro formule X a Y a uvažujme např. formuli X ( Y. Hledaný syntaktický formační strom formule X ( Y bude mít kořen označený touto formulí jako návěštím. Levá větev vycházející z kořene povede k uzlu s návěštím X, pravá větev k uzlu s návěštím Y. Spolu s návěštími X a Y převezme syntaktický formační strom formule X ( Y i stromy formulí X a Y jako své podstromy.
Podobně jako v případě implikace by postupovala konstrukce syntaktického formačního stromu pro ostatní binární výrokové spojky.
Za předpokladu existence stromu odpovídajícího formuli X bude mít strom pro formuli (X kořen s návěštím (X a jediná z něho vycházející větev povede k uzlu označenému X, s nímž výsledný formační strom formule (X převezme i jeho formační strom.
b) Důkaz, že syntaktický formační strom výrokové formule zkonstruovaný způsobem uvedeným v odstavci a) je jediný :
V případě atomické formule je zřejmě její syntaktický formační strom uvažovaný v odstavci a) stromem jediným. Kořen, který je zároveň listem tvoří celý strom.
Předpokládejme jedinečnost syntaktických formačních stromů formulí X a Y. Uvažujme např. syntaktický formační strom formule X ( Y. Podle definice nese kořen stromu návěští X ( Y a je následován jednoznačně levou a pravou větví směřující k uzlům označeným postupně z leva do prava návěštími X a Y. Tento vztah mezi stromem formule a stromy jejích podformulí přesně odpovídá situaci při konstrukci stromu v odstavci a). Jde tedy o týž jednoznačně určený syntaktický formační strom formule X ( Y. Podobnou úvahu by bylo možno provést pro ostatní výrokové spojky.
Vzájemně jednoznačné přiřazení dobře utvořené výrokové formule a jejího syntaktického formačního stromu umožňuje definovat vedle složitosti konstrukce formule též její hloubku a základnu.
Definice . (hloubky a základny formule)
Hloubka formule je hloubkou jejího syntaktického formačního stromu.
Základnu formule tvoří množina atomických formulí, které jsou návěštími listů jejího syntaktického formačního stromu.
Příklad .
Stanovte hloubku a velikost základny formule ((p & q)  false) ( q z příkladu 1.2., jejíž syntaktický formační strom je zobrazen na obr. 1.2.
Formule má hloubku h = 3, neboť obsahuje maximálně uzly 3. úrovně.
Základnu formule tvoří tři atomické formule p, q, a false.
Pro důkazy řady vlastností výrokových formulí bude v následujících odstavcích používána metoda indukce podle složitosti formule. Tento pojem definovaný v následující definici je třeba odlišit od pojmu složitosti konstrukce formule z definice 1.12.
Definice TYLEREF 1 \s 1. (složitosti formule)
Složitost formule je rovna počtu uzlů syntaktického formačního stromu formule, které nejsou listy.
Z definice 1.13, podle níž je syntaktický formační strom formule vytvářen, vyplývá platnost následující věty.
Věta .
Složitost formule je rovna počtu výrokových spojek vyskytujících se ve formuli.
Věta .
Složitost konstrukce formule je menší nebo rovna součtu složitosti formule a velikosti její základny.
Důkaz
Z definic je zřejmé, že pokud se ve formuli nevyskytuje vícenásobně žádná její neatomická podformule, je složitost konstrukce formule rovna součtu složitosti formule a velikosti její základny. V opačném případě jsou do složitosti formule započítávány i ty spojky, které se vyskytují opakovaně v týchž podformulích, a proto je součet složitosti formule a velikosti její základny větší než počet členů posloupnosti konstrukce formule, v níž se podformule opakovaně nevyskytují.
Formule z příkladu 1.2 má složitost 4, přitom složitost její konstrukce je, jak je v řešení příkladu uvedeno, rovna 7 a základna má (viz příklad 1.3) velikost 3.
Syntaktický formační strom formule je binární strom, reprezentující způsob, jakým byla formule z prvků abecedy podle syntaktických pravidel sestrojena. Kořen stromu nese tuto formuli jako své návěští, návěštími listů jsou atomické formule, tj. výrokové proměnné nebo logické konstanty.
Složitost formule, hloubka formule a základna formule odpovídají složitosti, hloubce a základně jejího syntaktického formačního stromu.
Složitost konstrukce formule je dána počtem podformulí, které musí být při konstrukci formule podle syntaktických pravidel vytvořeny.
Úkol .
Nakreslete syntaktický formační strom formule a stanovte její hloubku, základnu, složitost a složitost konstrukce.
( p ( ( q  r ))  (( p & s )  r )
2. K následujícím větám sestavte výrokové formule
Prší a mrzne, ale nesněží.
Buď prší nebo sněží a mrzne.
Mrzne-li, neprší nebo sněží.
Mrzne-li nebo sněží, neprší.
Spočetnost množiny výrokových formulí
Na závěr lekce o syntaxi jazyka výrokové logiky je třeba si položit otázku, kolik je jeho dobře utvořených formulí.
Snadno lze dokázat, že v případě spočetné abecedy platí pro množinu formulí výrokové logiky následující věta.
Věta .
Množina všech výrokových formulí utvořených ze spočetné množiny atomických formulí je spočetná.
Důkaz
Množina P všech atomických formulí je spočetná, existuje tedy bijekce mezi touto množinou a podmnožinou množiny N přirozených čísel. Všech výrokových formulí proto není méně než prvků množiny P ani více než slov utvořených ze sjednocení
P ( {, & , (, (, (, ( , ) }
spočetné abecedy P a konečné abecedy symbolů jazyka L výrokové logiky {, & , (, (, (, ( , ) }, kterých je spočetně mnoho. Pro představu, jakým způsobem mohou být postupně konstruované formule numerovány, tj. jakým způsobem jim mohou být přiřazována přirozená čísla, slouží uspořádání formulí naznačené v obr. 1.3.
V záhlaví tabulky, tj. horním řádku a levém sloupci jsou uvedeny formule, z nichž je na průsečíku příslušného řádku a sloupce vždy zkonstruována formule pomocí logické spojky. V obr. 1.3 je použita pouze spojka implikace, při použití dalších spojek by na příslušných průsečících byla uvedena další tři logická spojení, která by rovněž byla zahrnuta do numerace a zapsána do řádku i sloupce záhlaví tabulky. Zavedení negací do numerace lze pak provést tak, že negace každé z formulí v řádku záhlaví bude zařazena za tuto formuli, v případě sloupce záhlaví pod tuto formuli.
pp(p q(p(p)(p
pp(p(p(p)(pq(p((p(p)(p)(p
p(pp((p(p)(p(p)((p(p)(p(p)(p
qp(q(p(p)(q
(p(p)(pp(((p(p)(p)
obr..
Výrok je tvrzení deklarativního charakteru, o němž lze rozhodnout, zdali je pravdivý nebo nepravdivý, jiná možnost není.
Jazyk výrokové logiky je určen jeho gramatikou, tj. abecedou a syntaktickými pravidly tvorby dobře utvořených formulí.
Výrokovou formuli reprezentuje její jediný syntaktický formační strom. Charakteristiky složitosti, kterými jsou složitost formule, hloubka formule a základna formule a odpovídají příslušným charakteristikám syntaktického formačního stromu formule.
Složitost konstrukce formule je dána počtem podformulí, které je třeba vytvořit, aby podle pravidel syntaxe formule vznikla.
Množina všech formulí vytvořených ze spočetné abecedy je spočetná.
Najděte chybu v konstrukci syntaktického formačního stromu formule, opravte ji a z opraveného syntaktického formačního stromu stanovte složitost formule, její hloubku, velikost základny a složitost konstrukce
((p  q) & r)  (r ( q)

(p  q) & r  r ( q
p  q r r q
p q
SÉMANTIKA JAZYKA L VÝROKOVÉ LOGIKY
V této lekci se naučíte, jak se formule jazyka výrokové logiky interpretují, tj. jak se jim přiřazuje význam. Seznámíte se s induktivně definovanými interpretačními pravidly, která vám umožní na základě určité stanovené pravdivostní struktury výrokových proměnných vyskytujících se ve formuli stanovit výslednou pravdivostní hodnotu interpretace jednotlivých logických spojení. Seznámíte se s pojmy logicky platné (tautologické) formule, splnitelné a nesplnitelné (kontradiktické) formule.
Na závěr lekce se naučíte způsoby zjednodušujícího přepisu formulí na ekvivalentní formule, obsahující určité (funkčně úplné) množiny výrokových spojek.
Prostudování této lekce by vám mělo trvat zhruba 1.5 h.
VÝZNAM JAZYKA L VÝROKOVÉ LOGIKY
Interpretace jazyka L výrokové logiky
V předcházející lekci byl nezávisle na významu definován čistě formálně konstruovaný jazyk L výrokové logiky. Podobně jako je tomu u sémantiky jazyka přirozeného, kdy jednotlivým jazykovým výrazům náleží jako jejich denotáty pojmy, mají i formule modelově zjednodušeného jazyka výrokové logiky svoji denotační sémantiku, spočívající v přiřazování denotátu každé z jeho dobře utvořených formulí. To ve výrokové logice znamená, že při dané pravdivostní struktuře elementárních výroků je každá její dobře utvořená formule jednoznačně interpretována určitou pravdivostní hodnotou.
Jak již vyplývá z vymezení pojmu výroku na základě pojmu pravdivosti či nepravdivosti elementárních tvrzení, atomické formule výrokové logiky, kterými jsou elementární výroky reprezentovány, nabývají vždy pouze některé z logických hodnot true, false. Totéž platí, jak bude dále zpřesněno, i pro formule komponované. Jinými slovy, oborem sémantické interpretace výrokové logiky je dvouprvková množina W = {true, false}. - její universum diskursu.
Proces přiřazování významu, který se nazývá interpretací formule, začíná stanovením určité pravdivostní struktury atomů vyskytujících se ve formuli. V případě logických konstant true, false jsou denotáty konstantně dány příslušnými pravdivostními hodnotami universa diskursu. V případě výrokových proměnných se denotáty stanoví valuací, tj. jejich ohodnocením, a to rovněž vždy některou z  pravdivostních hodnot universa diskursu. Na základě přiřazení významu elementárním prvkům (atomům) jazyka se pak stanoví pomocí interpretačních pravidel její výsledná pravdivostní hodnota interpretace komponované formule.
V následujícím odstavci budou pojmy týkající se interpretace formulí výrokové logiky definovány přesněji.
Valuace výrokových proměnných a interpretace formulí
Zatímco symboly jazyka L výrokové logiky označující logické konstanty (symboly true, false) mají své denotáty v universu diskursu konstantně přiřazeny tak, že D(true) = true („pravdivý“), D(false) = false („nepravdivý“) (symbol D zde označuje denotační zobrazení přiřazující jazykovému výrazu objekt universa diskursu jako jeho denotát), symbolům pro výrokové proměnné je třeba, jak již bylo zmíněno, jejich význam přiřadit. Toto přiřazení se, jak bude zpřesněno v následující definici, nazývá jejich ohodnocením neboli valuací.
Definice . (valuace výrokových proměnných)
Valuace (ohodnocení) symbolu p označujícího výrokovou proměnnou je funkce v(p) přiřazující proměnné p jednu ze dvou možných pravdivostních hodnot z množiny
W = {true, false}.
v(p) = true/false.
Definice . (interpretace dobře utvořené formule jazyka L výrokové logiky)
Nechť v je valuace výrokových proměnných dobře utvořené formule A jazyka L, D je denotační zobrazení. Indukcí podle složitosti formule A definujeme interpretaci formule A při valuaci jejích proměnných v jako funkci
I(A[v]) = true/false
takto :
1. Báze Je-li formule A symbolem pro výrokovou proměnnou p v jazyce L, pak I(A[v]) = v(p).
Je-li formule A symbolem pro logickou konstantu true/false, pak I(A