Vyrokova_predikatova_logika

[v]) = D(A) = true/false.
2. Indukce Jsou-li B, C formule jazyka L, pak
I(B[v]) = true, právě když I(B[v]) = false
I((B ( C)[v]) = true, právě když I(B[v]) = true nebo I(C[v]) = true
I((B ( C)[v]) = true, právě když současně platí I(B[v]) = true a I(C[v]) = true
I((B ( C)[v]) = true, právě když I(B[v]) = false nebo I(C[v]) = true
I((B ( C)[v]) = true, právě když současně I((B ( C)[v]) = true a I((C ( B)[v]) = true.
3. Generalizace
Pravdivostní hodnota interpretace libovolné formule jazyka L výrokové logiky se pro danou valuaci v jejích výrokových proměnných stanoví vždy konečným počtem aplikací kroků 1. a 2.
Tabulky interpretačních pravidel
Definice 2.2 představuje definici funkčního zobrazení I(A(v(), kdy dané valuaci v výrokových proměnných formule A odpovídá vždy jediná výsledná hodnota interpretace formule A.
Funkční pojetí způsobu určení interpretačních pravidel umožňuje jejich přehledné vyjádření pravdivostními tabulkami (tab.2.1). Pravidlu pro interpretaci negace formule A odpovídá funkce jedné proměnné typu f(A), pravidlům pro ostatní logické spojky spojující formule A a B funkce dvou proměnných typu f(A,B).
A
B
f(A)
( (
f(A,B)
( (
(
A
A & B
A ( B
A ( B
A B
F
F
T
F
F
T
T
F
T
T
F
T
T
F
T
F
F
F
T
F
F
T
T
F
T
T
T
T
tab. .1
Interpretace formulí Booleovými funkcemi
Uvažujme nyní obecněji aplikaci zavedeného postupu interpretace na formuli s n výrokovými proměnnými p1,...,pn . Zde jde v prvním kroku o ohodnocení výrokových proměnných p1,...,pn a na základě nich pak o postupné odvozování výsledné pravdivostní hodnoty pomocí interpretačních pravidel. Tento postup lze též reprezentovat charakteristickou funkcí n proměnných definovaných na n-rozměrných vektorech z nul a jedniček a nabývající též hodnot z množiny {0,1}. Přitom je pravdivostní hodnota true zastoupena hodnotou 1, pravdivostní hodnota false hodnotou 0 charakteristické funkce pravdivosti formule.
Interpretaci výrokové formule o n výrokových proměnných lze pokládat za stanovení hodnoty funkce, jejímž definičním oborem je kartézský součin {0,1}n a oborem hodnot množina {0,1}.
Funkce tohoto typu se obecně nazývají Booleovy funkce n argumentů.
Definiční obor Booleovy funkce n argumentů obsahuje právě 2n prvků. Navzájem různých Booleových funkcí nad tímto definičním oborem je právě tolik, kolik je navzájem různých slov délky 2n nad dvouprvkovou abecedou {0,1}, tj. 2n -tá mocnina čísla 2. Např. Booleových funkcí dvou argumentů je 16. Všechny tyto možné funkce dvou výrokových proměnných a, b jsou uvedeny v tab.2.2.
V tabulce 2.2 lze vedle již známých funkcí základních výrokových spojek vidět i funkce odpovídající dalším užitečným výrokovým spojkám, jakými jsou např. spojka (+) pro vylučovací nebo, spojka nor ( (negace disjunkce), která je pravdivá pouze pro dvojici (0,0) a spojka nand ( pro (negace konjunkce) nebo též Schefferův operátor, která je nepravdivá pouze pro dvojici (1,1).
a
b
F
a(b
a&b
a
b
Ab
a(+)b
b
a
a( b
ab
a(b
T
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
0
1001010111011110000100101111101 tab.  STYLEREF 1 \s 2. SEQ tab. \* ARABIC \s 1 2

V následujícím odstavci, stejně jako v řadě dalších, bude ve známé tabulkové metodě sémantické analýzy formule, tj. analýzy interpretací formule při různých valuacích výrokových proměnných, používána notace Booleových funkcí (pravdivostní hodnoty nahrazeny hodnotami charakteristické funkce 0/1).
Tabulková metoda sémantické analýzy formule
V tabulce 2.1 jsou uvedena interpretační pravidla pro interpretaci formulí s výrokovými spojkami , & , (, (, ( přehledným způsobem pomocí interpretačních tabulek, vztahujících se k jednotlivým spojkám. Obdobně přehlednou tabulkovou metodou vyhodnocování Booleových funkcí je možno postupovat i při sémantické analýze formule. Ta spočívá v interpretacích formule pomocí interpretačních pravidel, přičemž jsou postupně uvažovány a řazeny do interpretační tabulky všechny možné valuace jejích výrokových proměnných.
Příklad .
Analýzujte tabulkovou metodou sémantiku formule ((p & q)  false) ( q.
V případě formule ((p & q)  false) ( q bude potřeba pro dvojici symbolů reprezentujících výrokové proměnné uvažovat 22 = 4 různých variací ohodnocení.
Jednotlivé řádky tabulky sémantické analýzy formule představují interpretace dané formule při valuacích dvou výrokových proměnných, uspořádaných v prvních dvou sloupcích tabulky.
Jak je vidět z tab. 2.3, některé postupně již interpretované podformule je vhodné v tabulce pro přehlednost označit metasymboly.
X
Y
p
q
p & q
X  false
q
Y ( q
0
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
0
0
tab. .
Úkol .
Vytvořte si podle pravidel syntaxe nějakou výrokovou formuli F s alespoň třemi výrokovými proměnnými a proveďte její sémantickou analýzu tabulkovou metodou. Její výsledky budete dále porovnávat s výsledky analýz jinými metodami.
Splnitelné formule, tautologie a kontradikce
Při sémantické analýze formule tabulkovou metodou se v posledním výsledném sloupci objeví jedničky spolu s nulami, pouze jedničky nebo pouze nuly. Je proto vhodné již nyní zavést pojmy, které uvedené tři případy pojmenovávají a víceméně charakterizují.
Definice 1 \s 2. (splnitelnosti, platnosti a nesplnitelnosti formule)
Formule A je splnitelná, existuje-li valuace v jejích výrokových proměnných, při němž I(A(v() = true.
Formule A je logicky platná neboli tautologie (označujeme (( A ), je-li buď logickou konstantou true nebo je-li I(A(v() = true při každé valuaci v výrokových proměnných.
Formule A je nesplnitelná neboli kontradikce, je-li buď logickou konstantou false nebo je-li pro všechny valuace v jejích výrokových proměnných I(A(v() = false.
Je negace splnitelné formule splnitelná ?
Je negace logicky platné formule splnitelná ?
Je negace splnitelné formule logicky platná ?
Vzájemné souvislosti výše definovaných pojmů spolu s metodami rozhodování, o který z případů jde, budou uvedeny v následujících odstavcích.
Modely formulí
Dříve, než bude definován pojem modelu formule, je třeba připomenout, že každá valuace výrokových proměnných je přiřazením určité pravdivostní struktury elementárním výrokům, které zastoupeny výrokovými proměnnými tvoří součást báze jazyka zkonstruovaného speciálně k reprezentaci určitého problému. Interpretace formule A pravdivostní hodnotou true vychází tedy z určité pravdivostní struktury elementárních výroků o modelovaném světě reprezentovaných výrokovými proměnnými. Ve výrokové logice se v takovém případě hovoří o modelu formule A.
V případě, že uvažujeme množinu formulí U namísto formule jediné, se hovoří o modelu množiny formulí U. Model formule je pak modelem jednoprvkové množiny formulí.
Definice . (modelu množiny formulí, modelu formule)
Pravdivostní struktura všech výrokových proměnných vyskytujících se v množině formulí U = (A1, A1,...,An(, určená jejich valuací v, je modelem množiny formulí (A1, A1,...,An(, jestliže platí I(Ai(v() = true pro všechna i, 1 ( i ( n.
Jde-li o jednoprvkovou množinou U = (A(, hovoříme o modelu formule A.
Příklad .
Z následující tabulky sémantické analýzy formule p  r) ( (q & (r p)) stanovte modely této formule
X
Y
Z
p
q
r
p  r
rp
q & Y
X  Z
1*
0
0
0
0
0
0
1
2
0
0
1
1
1
0
0
3*
0
1
0
0
0
0
1
4*
0
1
1
1
1
1
1
5
1
0
0
1
1
0
0
6
1
0
1
1
1
0
0
7*
1
1
0
1
1
1
1
8*
1
1
1
1
1
1
1
tab. .
Modely určují ty řádky tabulky, v nichž je formule interpretována jako true (zde označené hvězdičkou).
Např. model m4 odpovídající čtvrtému řádku tabulky má strukturu danou těmito valuacemi výrokových proměnných : v(p) = false, v(q) = true, v(r) = true, což je možno též vyjádřit trojicí p, q, r.
Úkol .
1. Zjistěte, zdali existuje model formule
A = ( a  c )  (( b  d )  (( a ( b )  c ))
B = ( a  b )  (( b  c )  a )
C = (a ( ((b  a) & c))  b
2. Zjistěte, zdali existuje model množiny formulí (A, B, C ( z příkladu 1.
3. Stanovte všechny modely vaší formule F.
Dualita formulí
Vytvoříme-li interpretační tabulku libovolné formule A a provedeme-li na ní transformaci spočívající ve vzájemné záměně všech pravdivostních hodnot tabulky, dostaneme interpretační tabulku formule AD duální k dané formuli A.
Definice . (duality formulí)
Formule AD, jejíž interpretační tabulka byla vytvořena z interpretační tabulky formule A vzájemnou záměnou všech jejích pravdivostních hodnot, je formulí duální k formuli A.
Tabulky 2.5 a 2.6 zobrazují formuli a & b a k ní duální formuli (a & b)D .
Interpretační tabulka Interpretační tabulka duální
formule a & b formule (a & b)D
a
b
a & b
a
b
(a & b)D
F
F
F
T
T
T
F
T
F
T
F
T
T
F
F
F
T
T
TTTFFF tab.  STYLEREF 1 \s 2. SEQ tab. \* ARABIC \s 1 5tab.  STYLEREF 1 \s 2. SEQ tab. \* ARABIC \s 1 6

aba ( bFFFFTTTFTTTT tab.  STYLEREF 1 \s 2. SEQ tab. \* ARABIC \s 1 7

Porovnáme-li nyní interpretační tabulku formule (a & b)D s interpretační tabulkou formule a ( b (tab. 2.7), vidíme, že se vzájemně liší pouze pořadím řádků. Formule a & b a formule a ( b jsou tedy formulemi duálními. Spojky & a ( proto bývají nazývány spojkami duálními.
Substituce
V tabulce 2.3 byly některé podformule dané interpretované formule v záhlaví sloupců označeny metasymboly.
Konkrétně bylo zavedeno : za podformuli (p & q) symbol X,
za podformuli ((p & q)  false) symbol Y.
To umožnilo vyjádřit danou formuli stručnějším způsobem.
Naopak, za metajazykový symbol pro podformuli dané formule lze substituovat její jazykovou podformuli. Totéž platí pro jazykový symbol označující výrokovou proměnnou.
Následující velmi užitečná věta se týká substitucí do formulí, které jsou tautologiemi.
Věta . (o tautologiích)
Nechť A je výroková formule s výrokovými proměnnými p1 ,..,pn . Nechť A’ vznikne z A tak, že za každý výskyt proměnné pi , 1(i(n, je substituována formule B. Je-li A tautologií, pak je tautologií i A’ .
Důkaz
Je-li A tautologií, pak je interpretována jako true nezávisle na ohodnocení výrokových proměnných pi, 1(i(n, resp. po substituci podformulí B nezávisle na výsledku jejich interpretace. Proto A’ je rovněž tautologií.
EKVIVALENCE VÝROKOVÝCH FORMULÍ
Ekvivalence jazyková a metajazyková
Dvě formule A, B, které nejsou z hlediska pravdivosti od sebe odlišitelné při žádné valuaci v výrokových proměnných obsažených v obou formulích, pokládáme za sémanticky ekvivalentní.
Definice . (ekvivalence formulí)
Formule A, B jsou ekvivalentní, označujeme A ( B, platí-li pro jejich interpretace
I(A(v() = I(B(v()
při libovolné valuaci v jejich výrokových proměnných.
Je zřejmé, že výraz A ( B označující ekvivalenci formulí A a B představuje ekvivalenci metajazykovou, rozdílnou od ekvivalence podformulí, pro niž používáme spojku ( jazyka L výrokové logiky.
Zavedený způsob vyjádření ekvivalence dvou formulí výrazem A ( B je evidentně výrazem metajazykovým už proto, že A a B nejsou symboly jazyka výrokové logiky, nýbrž symboly označující dobře utvořené formule jazyka výrokové logiky. Je zde proto na místě použít jiného symbolu ekvivalence, než je jazykový symbol  zavedený definicí 1.1.
Z definice 2.6. ekvivalence výrokových formulí vyplývá, že po substituci dobře utvořených formulí jazyka výrokové logiky za metasymboly A a B je možno symbol (nahradit jazykovým symbolem ( a získat tak rovněž dobře utvořenou výrokovou formuli.
Např. při substituci p ( q za A a substituci q ( p za B je namístě použít pro vyjádření ekvivalence podformulí vzniklé dobře utvořené formule spojky (, přičemž ekvivalence
p ( q  q ( p
je dobře utvořenou formulí výrokové logiky (s využitím úmluvy o prioritách logických spojek).
Přestože symboly  a  neznamenají totéž, je zřejmé, že metajazyková ekvivalence A  B platí, právě když ekvivalence jazykových výrazů odpovídajících symbolům A a B je tautologií.
Nejčastěji používané ekvivalence výrokových formulí
spolu s úvahami předcházejícího odstavce o ekvivalentních formulích poskytuje možnost vyjádření a praktického využití řady užitečných ekvivalencí.
Následující ekvivalence vyjádřené formou metajazykových schémat patří k nejznámějším a nejvíce používaným. Symboly X,Y,... v nich představují libovolné dobře utvořené formule, metajazykový symbol (( zde vyjadřuje platnost uvedených ekvivalencí. Substitucí dobře utvořených formulí za metasymboly X, Y,... a náhradou metajazykové spojky  spojkou  vzniknou z uvedených schémat tautologie výrokové logiky.
(1) (( ( X & X )  X idempotence
(2) ( X ( X )  X “
(3) ( X & Y )  ( Y & X ) komutativnost
(4) ( X ( Y )  ( Y ( X ) “
(5) (( X & Y ) & Z)  ( X & ( Y & Z )) asociativnost
(6) (( X ( Y ) ( Z)  ( X ( ( Y ( Z )) “
(7) (( X & Y ) ( Z)  (( X ( Z) & (Y ( Z )) distributivnost
(8) (( X ( Y ) & Z)  (( X & Z ) ( ( Y & Z )) “
(9) ( X ( X )  true komplementárnost
(10) ( X & X )  false “
(11) X  X identita
(12) (X)  X involuce
(13) ( X & Y )  (X ( Y ) de Morganovo pravidlo
(14) ( X ( Y )  (X & Y ) “
(15) ( X ( ( X & Y ))  X absorpce
(16) ( X & ( X ( Y ))  X “
(17) (X ( true)  true
(18) (X ( false)  X
(19) ( X & true )  X
(20) ( X & false )  false
(21) X  ( X  false )
(22)false true
Příklad .
Úprava formule p & (p ( q) na jednodušší ekvivalentní formuli pomocí uvedených ekvivalencí:
p & (p ( q)  (p & p) ( (p & q)  false ( (p & q)  (p & q)

Při úpravě zde byla použita komutativnost (3), distributivnost (8), komplementárnost (10) a (18).
Úkol .
1. Zjednodušte následující formule :
(p ( q) ( p
(p ( q) ( (p
(p ( q) ( q
2. Dokažte ekvivalenci následujících dvojic formulí :
p, p ( (p ( q)
p, p ( (p ( q)
p ( q, p
Funkčně úplné množiny výrokových spojek
De Morganova pravidla ( ekvivalence (13) a (14) ) z předcházejícího odstavce jsou příkladem toho, jak lze pomocí ekvivalentní formule nahradit určitou výrokovou spojku jinou výrokovou spojkou. Následující ekvivalence obdobně definují pomocí negace a implikace ostatní binární logické spojky :
(23) ( X ( Y )  (X  Y ) náhrada spojek & a (
(2) ( X & Y )  ( X  Y ) spojkami  a 
(25) ( X  Y )  ( X  Y ) & ( Y  X )
Naopak lze v případě potřeby nahradit spojku  spojkami  a ( :
(26) ( X  Y )  ( X ( Y )
„Vylučující nebo“ (+) lze definovat pomocí konjunkce a disjunkce
(27) ( X (+) Y )  ( X & Y ) ( (X & Y )
Pro účely důkazů bývá vhodné použít ekvivalence
(28) ( A  B )  (B  A)
V souvislosti s možností náhrady výrokové spojky jinými spojkami se nabízí otázka, zdali existují takové podmnožiny výrokových spojek, kterými lze nahradit všechny zbývající výrokové spojky.
Definice . (funkčně úplné množiny výrokových spojek)
Množina výrokových spojek je funkčně úplná, jestliže lze pomocí této množiny nahradit (přepisem formulí na formule ekvivalentní) všechny zbývající výrokové spojky.
Z výše uvedeného příkladu vyplývá, že množina {, } je funkčně úplná.
Množina spojek {&,(,} tvoří rovněž funkčně úplnou množinu. Protože spojku & lze vyjádřit pomocí spojek ( ,  a naopak spojku ( pomocí spojek & ,  De Morganovými pravidly, je funkčně úplná i množina {(,}, resp. množina {&,} (množina {&,( } nikoliv).
Jednoprvkovou funkčně úplnou množinu výrokových spojek tvoří spojka ( - negace disjunkce neboli nor, pravdivá pouze pro (0,0), neboť platí
a  a ( a ,
a & b  (a ( a) ( (b ( b).
Další jednoprvkovou funkčně úplnou množinu výrokových spojek tvoří spojka ( - negace konjunkce neboli nand, nepravdivá pouze pro (1,1), neboť platí
a  a ( a ,
a ( b  (a ( a) ( (b ( b).
Snadno lze dokázat, že každá z uvedených spojek tvořících jednoprvkové funkčně úplné množiny je ekvivalentní X, tj.
(29) ( X ( X )  X ,
(30) ( X ( X )  X ,
což je vlastnost využívaná v digitální elektronice.
Formuli (p ( q) & (r & (q  p)) přepište pouze pomocí spojek  a  .
Interpretace výrokové formule A spočívá v přiřazení jedné z pravdivostních hodnou true/false formuli A tímto postupem :
valuace všech výrokových proměnných formule A
interpretace formule A postupně z jednotlivých podformulí pomocí interpretačních pravidel v pořadí, jak byly podle pravidel syntaxe vytvářeny.
Sémantická analýza výrokové formule spočívá ve stanovení pravdivostních hodnot interpretace formule pro všechny možné valuace jejích proměnných. Pro tabulkovou metodu analýzy je typické systematické uspořádání variant valuací do tabulky.
Ty valuace proměnných dané formule A, při nichž je formule interpretována pravdivostní hodnotou true, jsou modely formule A.
Model množiny formulí je společným modelem všech formulí této množiny.
Dvě výrokové formule jsou ekvivalentní, když jsou při libovolné valuaci všech jejich výrokových proměnných interpretovány touž pravdivostní hodnotou.
S využitím ekvivalentních formulí lze v dané formuli přepsat logická spojení určitými spojkami na logická spojení jinými spojkami. Množiny spojek, kterými lze přepsat všechny ostatní spojky, jsou funkčně úplnými množinami spojek.
Vyřešte jeden z následujících příkladů :
Nakreslete syntaktický formační strom formule a stanovte míry její složitosti
( p ( ( q  r ))  (( p & s )  r )
(p & q  q)  ((r ( q) & (p  s))
((q & r )  ( p ( (s & t))) ( p (  q)
Jak je definována valuace proměnných ve formuli ? Jak jsou definována interpretační pravidla výrokové formule ?

SPLNITELNOST A PLATNOST VÝROKOVÝCH FORMULÍ
V této lekci, jejíž prostudování by vám mělo trvat zhruba 1,5 h, se budete věnovat postupům (algoritmům) rozhodování, zdali je dobře utvořená formule výrokové logiky formulí splnitelnou, resp. formulí logicky platnou (tautologickou). Uvidíte, že všechny zde uvedené metody představují jisté zlepšení efektivnosti rozhodování ve srovnání s rozhodováním interpretačními tabulkami.
Dále se budete blíže zabývat těmi ekvivalencemi výrokových formulí, které dávají možnost převedení formulí do konjunktivních a disjunktivních normálních forem. Přesvědčíte se, že na formule v normálních formách lze snadno aplikovat řadu algoritmů rozhodování platnosti, event. splnitelnosti formulí.
Seznámíme se s poměrně jednoduchým Quineovým algoritmem, který je založen na myšlence postupných valuací proměnných a částečných interpretací podformulí dané formule jen do takového kroku, od kterého se již valuacemi dalších proměnných výsledek interpretace formule nezmění.
ROZHODOVÁNÍ A ROZHODNUTELNOST
Dualita nesplnitelnosti a logické platnosti formulí
V lekci 2. byly zavedeny pojmy splnitelné formule, tautologie a kontradikce. Zde bude soubor základních pojmů doplněn o další pojmy a di