Výroková logika - cvičení
1    Aplikace věty o kompaktnosti 1.1 Příklad:
Nechť A, B jsou nejvýše spočetné soubory a R C A x B je relace taková, že pro každé a E A je soubor Ba = {b \ (a, b) E R} neprázdný a konečný.
Dokažte, že pokud pro každou konečnou část Aq C A existuje injektivní funkce : Aq —> B taková, že C R (zde funkci /_^0 chápeme jako relaci), pak existuje také injektivní funkce / : A —> i? taková, že f Cl R.
Poznámka: Trojici (A,B,R) lze chápat jako bipartitní graf a injektivní funkce /_^0 a / jako párování v grafu (A, B, R).
Řešení:
Nechť Pat, je výroková proměnná pro každou dvojici (a, d) £ 4 x B, Definujme soubor T tvořený následujícími formulemi:
• V&g,Ba Pab Pro každé a E A
• "'Pabi V ^Pab2 Pro každé a G A a všechna &i, &2 £ -B taková, že b± ^ 62
• -iPaife V ^Pa2b Pro všechna ai, 122 S ^4 taková, že ai 7^ «2 a každé b E B
Nyní postupně ukážeme následující dvě tvrzení, která nám dohromady dají požadovaný výsledek:
Tvrzení:
1. Pokud pro každou konečnou část Aq C A existuje injektivní funkce Ja0 '■ Aq —> B taková, že /_^0 C i?, pak je soubor T splnitelný.
2. Pokud je soubor T splnitelný, pak existuje injektivní funkce / : A —> B taková, že / C R.
ad 1. Ukážeme, že libovolný konečný soubor formulí To C T je splnitelný. Požadované tvrzení pak obdržíme aplikací věty o kompaktnosti. Nechť Paibu • • • iPakbk Jsou právě ty výrokové proměnné, které se vyskytují ve formulích z Tq. Označme Aq = {a±,... ,aj,}. Z předpokladu dokazovaného tvrzení víme, že existuje injektivní funkce /_^0 : Aq —> B taková, že /_^0 C R.
Definujme valuaci v takto: Pro každé (a,b) E A x B definujeme ^{Pab) = 1 právě tehdy, když a E Aq a b = fA0(a) a dále definujeme v(Q) = 0 pro ostatní výrokové proměnné Q.
Dokážeme, že každá formule ip E Tq je pravdivá ve valuaci v.
1
• Předpokládejme, že ip je tvaru \JheBa Pab Pro nějaké a E A. Pak zřejmě a E Aq a tedy existuje b E B takové, že 6 = /A0(a) a b E Ba (protože /_^0 C i?). Z definice valuace 1/ obdržíme, že i^(Pq6) = 1 a tedy u(ip) = 1.
• Pokud </? je tvaru ^Pab1 V _1-Pa62 Pro nějaké a G A a 61,62 £ P, pak platí buď 61 7^ fAo(a) nebo 62 7^ ÍA0{a)i protože 61 7^ 62- Z definice valuace 1/ potom plyne, že buď v(Pabi) = 0 nebo v{Pab2) = 0 a tedy v{ip) = 1.
• Pokud </? je tvaru -i.Paií, V _1-Pa26 Pro nějaká ai, a2 E A & b E B, pak platí buď 6 ^ ÍA0(ai) nebo 6 7^ ÍA0{a2), protože fAo je injektivní a a± 7^ 02. Z definice valuace 1/ potom plyne, že buď v{Paib) = 0 nebo v{Pa2b) = 0 a tedy        = 1.
Proto je libovolný konečný soubor To C T splnitelný, a tedy i soubor T je splnitelný dle věty o kompaktnosti.
ad 2. Nechť v je valuace, při které jsou všechny formule z T pravdivé. Nechť / C A x B je relace, definovaná takto: (a, b) E f právě tehdy, když (a, b) E R a v(Pab) = 1- Ukážeme, že / je injektivní funkce.
Nechť a E A. Protože v(\Jb€Ba Pab) = 1 a 8„ ^ í, dostaneme, že (a, b) E f pro nějaké 6 E Ba. Protože navíc v(-^Pabi V ^Pab2) = 1 Pro libovolná 61,62 £ -B taková, že 61 7^ 62, dostaneme, že (a, 6) G / pro právě jedno b E B & tedy / je funkce.
Nyní předpokládejme, že f(ai) = /'(fli) = 6 pro nějaká a±,a2 E A taková, že a± 7^ 0,2 a nějaké b E B. Protože v(^Paib V _1-Pa26) = 1? dostaneme, že buď (ai, 6) 0 / nebo (122> 6) 0 /, což je spor.
Relace / je tedy injektivní funkce, což bylo dokázat. Kombinací výše uvedených tvrzení 1. a 2. obdržíme řešení příkladu.
2    Shefferovské funkce 2.1 Příklad:
Dokažte následující tvrzení: Výroková funkce F arity n > 1 je Shefferovská právě tehdy, když platí následující podmínky:
1. J-(P, ■ ■ ■ , P) ~ -iP (P je výroková proměnná)
2. pro nějaká x±,.. . ,xn E {P, Q} (P, Q jsou různé výrokové proměnné) platí, že J-(xi,..., xn) není ekvivalentní ani —<P ani —<Q
2
3 Řešení:
Důkaz:   <=:   Předpokládejme   platnost   podmínek   1.   cl  2.   cl necht e {P, Q} jsou taková, že F(xi,... ,xn) není ekvivalentní ani -.P
ani —<Q.
Idea: Následující pravdivostní tabulka ukazuje, jakých pravdivostních hodnot může nabývat formule J-(xi,... ,xn).
P   Q   F(xi,...,xn) F(x1,...,xn)
110 0
10            0 1
0    10 1
0    0            1 1
Z tabulky je zřejmé, že máme pouze dvě možnosti. Ostatní možnosti jsou vyloučeny podmínkami 1. a 2. V prvním případě se symbol T chová jako spojka X (NOR) a ve druhém případě jako | (NAND). Obě tyto spojky jsou Shefferovské, což nám dá požadovaný výsledek.
Formální důkaz: Pro x,y E {0,1} označme uxy = (u*y,... ,u^) E {0,1}™ vektor délky n definovaný takto:
xv     I x   pokud Xi = P pokud xl = Q
Pozorování:
(a) F(u00) = 1 a F^u11) = 0 (plyne přímo z podmínky 1.)
(b) Jestliže F(u10) = 0 a F(u01) = 1, pak by ...,xn)&^P
(c) Jestliže F(u10) = 1 a F(u01) = 0, pak by J^i,... ,xn) «
Tudíž možnosti (b) a (c) by byly v rozporu s naším předpokladem. Z toho plyne, že nám zbývají pouze dvě možnosti, jak se může funkce F chovat na vektorech uxy. Tyto možnosti jsou
i. F(u10) = F(u01) = 0
ii. F(u10) = F(u01) = 1
ad i. Předpokládejme, že F(u10) = F(u01) = 0. Definujme transformaci T : C(x) —> C(F), která bude nahrazovat spojku X spojkou T takto: T(R) = R pro libovolnou výrokovou proměnnou R a T(ip X ip) = F{Tfa),...,T{^n)) kde
Í(p pokud Xi = P if}   pokud xí = Q
3
Ukážeme, že pro libovolnou formuli r E £(x) platí r pa T (t). Důkaz povedeme indukcí vzhledem k délce vytvořující posloupnosti pro r.
Pokud r je výroková proměna, pak T(t) = r a tvrzení platí triviálně. Předpokládejme, že r je tvaru ip X ip a nechť (kde x,y £ {0,1}) je nějaká valuace taková, že vxy((p) = x a vxy{ip) = V- Pak
FMTfa)),vxy{T{4,n))) = F{u*y) = {)   P°k"d " = 27 = °
II) jmak
kde třetí rovnost plyne z indukčního předpokladu. Z definice spojky X plyne, že
I 1   pokud x = y = 0 II) jinak
a tedy skutečně T(ip X ip) ~ </? A ip.
Nyní nechť G je libovolná výroková funkce. Z přednášky víme, že existuje formule r G £(á) taková, že FT = G (kde fr je funkce definovaná formulí r, viz. definice 19. z přednášky). Víme však, že FT = FT(r), protože t ps T(t), a tedy že FT(r) = G kde T(t) e C(F).
ad ii. Pokud F(íí10) = F(u01) = 1 pak se podobně jako v předchozím případě zadefinuje transformace T : —> C(F) taková, že platí r ps T(t). Víme, že pro libovolnou výrokovou funkci G existuje formule r G £(|) taková, že FT = G a tedy -řr(r) = FT = G.
= >: Důkaz provedeme obměnou. Předpokládejme nejprve, že neplatí podmínka 1. ze zadání příkladu. Máme celkem tři možnosti.
(a) F(l,..		= 1 a F(0,..	.,o)	= 0
(b) F(l,..		= 1 a F(0,..	.,o)	= 1
(c) F(l,..		= 0 a F(0,..	.,0)	= 0
Následující tvrzení ukazuje, že ani v jednom z výše uvedených případů, nemůže být funkce F Shefferovská.
Tvrzení: Nechť (p je formule C{F) obsahující právě jednu výrokovou proměnnou P.
(a) Jestliže F(l,... , 1) = 1 a F(0,... , 0) = 0 pak F^l) = 1
(b) Jestliže F(l,... , 1) = 1 a F(0,... , 0) = 1 pak F^l) = 1
(c) Jestliže F(l,... , 1) = 0 a F(0,... , 0) = 0 pak FV{Q) = 0
4
Důkaz:   ad (a): Indukcí vzhledem k délce vytvořující posloupnosti pro ip.
• Jestliže ip je výroková proměnná P a v je valuace taková, že v(P) = 1 a v(Y) = 0 pro ostatní výrokové proměnné Y, pak zřejmě P^l) =
• Jestliže </? je tvaru J-(ipi,... , V'n) Pro nějaké formule ipi,..., ipn a i/ je valuace taková, že ľ(P) = 1 a v(Y) = 0 pro ostatní výrokové proměnné Y, pak z indukčního předpokladu plyne, že v{ipi) = 1 pro l<i<na tedy
F^l) = v(T(^ • • • , VrO) = ^Wl), • • • , v&n)) = F(l, . . • , 1) = 1
Body (b) a (c) se dokáží úplně stejně.
Z výše uvedeného tvrzení tedy plyne, že pokud není splněna podmínka 1. ze zadání, pak funkce F není Shefferovská.
Nyní předpokládejme, že podmínka 1. je splněna, ale není splněna podmínka 2. Dokážeme, že pro každou formuli ip E £(F) s právě jednou výrokovou proměnnou P platí buď ip ps P nebo ip ps -P. Důkaz povedeme indukcí vzhledem k délce vytvořující posloupnosti pro ip.
• Jestliže ip je výroková proměnná P, pak zřejmě ip ps P.
• Jestliže ip je tvaru J-(ipi,..., ipn)i Pak z indukčního předpokladu plyne, že buď ipi kí P nebo ^ ps ->P pro 1 < i < n. Pak (viz. cvičení 1.) <pnJ:(Pu...Pn) kde
P     pokud lpi ps P -•P   pokud     ps -iP
Nyní uvažme -iP za Q v podmínce 2. ze zadání příkladu. Protože předpokládáme, že podmínka 2. není splněna, dostaneme, že buď ip ps ^(Pl,. .. Pn) ps ^P nebo <p ps ^(A, • • • Pn) « -(--P) «
Z výše uvedeného plyne, že neexistuje formule ip E £(F) taková, že Fv(l) = 1 a Fv(0) = 1 a tudíž F není Shefferovská.
Cvičení:
1. Nechť J-(ipi,...,ipn) a J-(<pi,...,ipn) jsou formule formálního logického systému C(F) takové, že ipi ps ipi pro 1 < i < n. Dokažte, že F (lpi, ... ,ipn) ps F(ipi, . . . ,<pn).
2. Nechť ip, ip, £i, ^2 jsou formule formálního logického systému C(Fi,... , Fn) takové, že vytvořující posloupnost formule ip obdržíme z vytvořující posloupnosti formule ip nahrazením všech výskytů formule £i formulí £2 a zároveň £1 ps £2- Dokažte, že ip ps ip.
5
3. Rozhodněte a dokažte (bez použití Příkladu 2.1!) zda jsou následující formální logické systémy plnohodnotné.
(a)
(b) JZ(~)
(c) £(V,A)
4. Pokuste se na základě klasifikace z Příkladu 2.1 odvodit vzorec vyjadřující počet n-árních Shefferovských funkcí (viz. přednáška).
1 Symbol —> zde zastupuje binární funkci, která udává sémantiku (tj. pravdivostní tabulku) implikace
6