přednášky

ez ohledu na hodnoty q, r.
nechť platí q=1. Zjistěte, zda za této podmínky nabývá pravdivostní funkce formule (q ( (p ( r) hodnoty pravda pro libovolné hodnoty p, r. ANO. Zdůvodnění: f (x1, x2, x3)= ( x2 ( (x1 ( x3) . Pro q=1 je (q=0. Potom f (x1, 1, x3)= 1 právě když (p ( r) = 0,1, což je pro libovolné p, r.
Formule výrokového počtu
Výraz sestavený z výrokových proměnných, logických spojek a závorek podle jistých pravidel je formulí výrokového počtu. Formule jsou tvořeny následujícími pravidly:
Výrokové proměnné p, q, r, ... jsou gramaticky správné formule.
Je-li ( formule, potom rovněž (( je gramaticky správná formule.
Jsou-li (, ( formule, potom i výrazy (((), ((((), ((((), ((((), (((() jsou gramaticky správné formule (Použití závorek [ ] je rovněž povoleno).
Jen formule vyhovující pravidlům 1, 2 a 3 jsou gramaticky správné.
Priorita logických spojek
Závorky ve formulích definují jejich jednoznačné vyhodnocení. Závorky lze eliminovat na základě zavedení priority spojek. Priority jsou stanoveny na základě "síly" každé spojky. Pořadí ( ( ( ( ( chápeme tak, že negace má nejvyšší a ekvivalence nejnižší prioritu. Priorita umožní ve formulích vynechávat závorky, tedy ((, (((, (((, (((, ((( budeme rovněž považovat za gramaticky správné formule. Vyhodnocení formule bez závorek potom probíhá od vyhodnocení spojky s nejvyšší prioritou a konče spojkou s nejnižší prioritou. Spojky se stejnou prioritou se vyhodnocují zleva doprava.

Polská – Lukasiewiczova notace formule
Je to speciální seřazení spojek a proměnných umožňující vyhodnotit formule zleva doprava. Taková notace formulí se vytváří automatem se zásobníkovou pamětí.
Příklad
Např. pro formuli (p ( ((q ( r) ( p)) ( (p ( q) je polskou notací forma pqr(p((pq((
Převod se provede pomocí automatu se zásobníkovou pamětí . Základní princip spočívá v definici stavů a aktivit takového zásobníku. Pro jednoduchost nebudeme stavy ani operace zapisovat formálně. Zapíšeme jen potřebné operace slovně:
Proměnná přechází zprava doleva a do zásobníku nepadá.
závorky nepřechází do polské notace.
Levá závorka ( nevyráží nic ze zásobníku, padá do něj s prioritou 0. Bude zničena a ze zásobníku odstraněna pomocí odpovídající pravé závorky ).
Pravá závorka ) má prioritu 1, nepadá do zásobníku, ničí odpovídající (.
operátor vyráží ze zásobníku jiný operátor stejné a větší priority.
je-li vstupní řetězec již vyčerpán a v zásobníku jsou ještě operátory, tak jsou postupně ze zásobníku vyraženy do polské notace.
Práci automatu ilustrují dva následující příklady. U druhého je zápis zásobníku redukován.

Pravdivostní hodnota
Pravdivostní hodnota formule ( je vlastně její zobrazení do množiny I = {0, 1}. Toto zobrazení je v podstatě založeno na zobrazení množiny výrokových proměnných do množiny I, tedy V0 {0, 1} a množiny výroků do {0, 1}. Tato zobrazení tvoří pravdivostní základ pro ohodnocení formule (. Jak vyhodnotíme pravdivostní hodnotu formule ( ?
Ke každé formuli lze sestrojit pravdivostní funkci f(x1, x2, …, xn), kde x1, x2, …, xn jsou výrokové proměnné formule. Pravdivostní funkce je definována jako n-ární operace
f: In I.
Množina In představuje právě 2n různých n-tic x1, x2, …, xn , přičemž každá z proměnných nabývá jen hodnoty 0,1. Pravdivostní funkce se z dané formule ( získá substitucemi typu p ( x1, q ( x2, … za proměnné p, q, ... Často se ovšem dělají substituce p ( p, q ( q, … , tj. proměnné formule se nemění.
Pravdivostní vyhodnocování formulí
Vyhodnocení každé formule je založeno na postupném vyčíslení pravdivostní funkce formule na počet 2n n-tic x1, x2, …, xn hodnot proměnných. Např. formule ((p ( q) ( r) ( (q ( r) má proměnné p,q,r a je tedy 23 = 8 trojic kombinací jejich hodnot: 000, 001, 010, 111, 110, 011, 100, 101 pro pravdivostní funkci. Na těchto kombinacích funkci f vyčíslíme. Vyčíslení můžeme vhodně uspořádat do tzv. pravdivostní tabulky, kde na levé straně jsou kombinace pravdivostních hodnot proměnných a na pravé straně podformule v pořadí priorit jejich vyčíslení.
p
q
r
p ( q
((p ( q) ( r)
q ( r
((p ( q) ( r) ( (q ( r)
0
0
0
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
0
0
0
1
1
1
0
1
0
1
0
0
Příklad
Pomocí pravdivostní tabulky ověřte platnost/neplatnost asociativního zákona
[(a ( b) ( c] ( [a ( (b ( c)]
a
b
c
a ( b
(a ( b) ( c
b ( c
a ( (b ( c )
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
1
0
1
1
1
Asociativní zákon pro ( neplatí.
Podobně udělejte vyhodnocení pro [a ( (b ( c)] ( [(a ( b) ( c] (asociativní zákon pro ( platí)
Příklad
Ivana ví, co jí sluší a proto se při oblékání řídí jistými vlastními zásadami: 1) K tmavé sukni neoblékne barevnou halenku 2) když si oblékne barevnou halenku, potom si natáhne tmavé punčochy 3) Žádný kabát nenosí bez tmavých punčoch. V sobotu, jak sama řekla, si vzala tmavou sukni. Vzala si Ivana v sobotu do kina kabát?
Řešení:
Stanovme nejdříve elementární výroky obsažené v zadání:
Má oblečenou tmavou sukni p
Má oblečenou barevnou halenku q
má oblečené tmavé punčochy r
Má oblečený kabát s
potom můžeme složené výroky v zadání formulovat následovně:
p ( (q
q ( r
s ( r
Jestliže má mít kabát, potom musí platit následující vztah:
(p ( (q) ( (q ( r) ( (s ( r) ( s
Platnost této formule můžeme prověřit pomocí pravdivostní tabulky nebo prostou úvahou.
Kdyby byla premisa neplatná, potom je možno vyvodit pravdivý nebo nepravdivý závěr. To ale nevede k prověření, že má na sobě kabát. Tedy premisa musí být pravdivá.
Pravdivost premisy je zaručena jen tenkrát, když je každý člen pravdivý. Je jasné, že p = 1 (vzala si tmavou sukni….prohlásila sama)
(p ( (q) = 1 má-li být implikace správná musí být typu 1 ( 1, tedy q = 0. Ivana nemá oblečenou barevnou halenku.
(q ( r) = 1, po dosazení je implikace typu 0 ( r, řešení je r = 0,1
(s ( r) = 1 dosadíme hodnoty za r (nejprve r = 1, tj. má oblečené tmavé punčochy). Potom je implikace typu s ( 1 nebo typu s ( 0 . Vzhledem k tomu, že oba typy musí být pravdivé, je řešením s = 0,1. Jelikož premisa musí být pravdivá, tak tomu vyhovuje řešení p =1, q = 0 a r = 1. Tedy musí mít i kabát, tj. s = 1 (protože černé punčochy nenosí bez kabátu). Případ p =1, q = 0 a r = 0 vede na s = 0. Nemá-li tedy tmavé punčochy, nemá ani kabát.
Tedy jen v případě p =1, q = 0 a r = 1 má zcela jistě kabát (má tmavou sukni, nemá barevnou halenku, má tmavé punčochy).
Tautologie – logické teorémy
Definice
Formule ( se nazývá tautologií jestliže pro ((x1, x2, …, xn) ( In , I={0,1} má její pravdivostní funkce vždy hodnotu 1, tj. f(x1, x2, …, xn) = 1 . Formule ( se nazývá kontradikcí, jestliže platí f(x1, x2, …, xn) = 0 pro ((x1, x2, …, xn) ( In. Pro tautologie se často používá označení ( , které čteme " formule ( je tautologie".
Jednou z metod jak se přesvědčit o tom, že nějaká formule je tautologií je tabulková metoda pro její pravdivostní funkci.
Operace nad tautologiemi
Zde uvedeme bez důkazů velmi užitečná tvrzení, která můžeme později použít při dokazování, zda je/není daná formule tautologií. Vedle toho je užitečné si pamatovat nevelký počet jednoduchých tautologií a naučit se je používat.
Např. ne ve všech případech bude použití pravdivostní tabulky k důkazu tautologie tak jednoduché jako pro tvrzení…. Formule ( a ( jsou ekvivalentní jestliže (( ( ().
Jestliže do tautologie provedeme speciální substituce, potom pravdivostní hodnota formule, která substitucemi vznikla, nezávisí na pravdivostních hodnotách substituovaných výroků, viz věty 4-1 a 4-2.
Věta
Nechť ( a ( jsou formule, xi výroková proměnná formule (. Nechť (' je formule , která vznikne z formule ( substitucí ( ( xi formule ( za proměnnou xi na všechna místa jejího výskytu ve formuli (. Platí-li ( , potom platí rovněž ('.

( ('
xi ( ( xi (
Substituce do tautologie, na všechna místa výskytu téže proměnné xi, tuto tautologii "neohrozí". Snadno se to dokáže indukcí vůči počtu proměnných.
Věta
Nechť (, (, ( jsou formule, ( je částí (. Nechť ( je formule, která vznikne z formule ( nahrazením formule ( substitucí ( ( (. a) Je-li (( ( (), pak je rovněž (( ( () b) Je-li (( ( () a (, pak je rovněž ( .
( (
( ( ( ( (
Jestliže do formule za její část, na všech místech výskytu této části, substituujeme ekvivalentní formuli, hodnota nové formule se nezmění.
Jestliže do tautologie za její část, na všech místech výskytu, substituujeme ekvivalentní formuli, tautologie se nezmění.
Dále uvedeme některá jednoduchá, ale užitečná tvrzení.
Věta
Je-li ( a (( ( () pak je (.
Jestliže implikace jisté formule z tautologie je tautologií, potom implikovaná formule je rovněž tautologií.
Příklad
Dokažte že platí [(u ( () ( ((u ( () ( (m ( n)) ( (m ( n)] .
řešení:
Cílem je najít si známou výchozí tautologii z níž po následných substitucích dosáhnou cílovou formuli. Takovou je např. tautologie p ( (p ( q) ( q (jak to víme???). Stačí dále, když provedeme následující substituce:
p ( u ( ( q ( m ( n a dostaneme cílovou formuli. Podle věty o substitucích do tautologie je také cílová formule tautologií.
Příklad
Zjednodušte zápis formule [r ( (((s ( t)].
Řešení:
Bude zajímavé z čeho vyjdeme. Je to zcela triviální tautologie (((s ( t) ( (s ( t) , která vznikla z tautologie (((p) ( p .. Zákon dvojí negace substitucí p ( (s ( t). Takže zjednodušení je r ( (s ( t).
Příklad
Dokažte, že :
Je-li (X ( Y), potom také platí X , Y. Z předpokladu plyne, že pravdivostní funkce formule (X ( Y) musí mít jen hodnotu 1. To není ale možné jinak než pravdivostní funkce pro X a Y mají hodnotu 1. Tedy musí to být tautologie.
Je-li X tautologie a Y formule, potom jsou rovněž X ( Y a Y ( X tautologie. Víme, že X ( Y = Y ( X , X ( (X ( Y) a Y ( (X ( Y) – disjunkce je implikovaná každým ze svých členů. Jestliže platí X , potom aby byla implikace pravdivá musí být (X ( Y).
Zákony výrokového počtu – logické teorémy - tautologie
Uveďme teď některé tautologie, které mají bohaté využití. V logice teorie jsme je nazvali logickými teorémy.
tautologie s jedinou výrokovou proměnnou
[ ( (p ((p) ] Zákon sporu: Dva výroky, z nichž jeden je negací druhého nemohou být najednou pravdivé.
[(p ( (p) ] Zákon vyloučení třetího: Ze dvou výroků, z nichž jeden je negací druhého, je právě jeden pravdivý a druhý nepravdivý a třetí možnost není.
(p ( p) Zákon totožnosti: Každý výrok implikuje sám sebe.
[((p ( p) ] Zákon dvojí negace: Dvojí negace každého výroku je s tímto výrokem ekvivalentní.
[((p ( p) ( p], [(p ((p) ( (p]…..Zákon Claviův (reductio ad absurdum) Je-li výrok implikován svou vlastní negací, pak je pravdivý.
Poznámka:
Buď p ( q základní tvar výroku implikace (podmíněný výrok). V dalších tautologiích budeme často potřebovat další obměny zmíněného výroku. Zavedeme rovněž jejich názvy:
q ( p Konversní výrok
(p ( (q Inversní výrok
(q ( (p Kontrapositivní výrok
tautologie o více výrokových proměnných
[(p ( q) ( ((q ( (p)] Zákon kontraposice: Kdykoliv je implikace pravdivá, je pravdivý i odpovídající kontrapositivní výrok.
[((q ( (p) ( (p ( q)] Varianty zákona kontrapozice [((p ( q) ( ((q ( p)]
[((p ( q) ( (q ( r)) ( (p ( r)] Zákon hypotetického sylogismu: Tranzitivita implikace. Je to schéma často používaného myšlenkového postupu.
[((p ( q) ( (q ( r)) ( (p ( r)] Tranzitivita ekvivalence: Jsou-li dva výroky ekvivalentní třetímu, pak jsou ekvivalentní.
[(p ( (p) ( q] Zákon Dunse Scota: Z nepravdy vyplývá cokoli (přijmeme-li nesprávný předpoklad, jsme nuceni přijmout i důsledky, které z něj vyplývají, ať už jsou jakékoliv).
[(p ( q) ( p] , [(p ( q) ( q] Konjunkce implikuje každý ze svých členů.
[p ( (p(q)] [ q ( (p ( q)] Disjunkce je implikována každým ze svých členů.
Další tautologie tvaru implikace
[(p ( q) ( (q ( p)] , [(p ( q) ( (q ( p)] Komutativita konjunkce a disjunkce. Platí též pro ekvivalenci.
[((p ( q) ( r) ( (p ( (q ( r))] Asociativita konjunkce a platí též pro disjunkci.
(p ( (q ( r)) ( ((p ( q) ( (p ( r))] Distributivita konjunkce vzhledem k disjunkci. Platí i pro distributivitu disjunkce vzhledem ke konjunkci.
[((p (( q) ( (p (( (q ] de Morganovy zákony. Dualita konjunkce a disjunkce.
(p ( (q ( r)) ( ((p ( q) ( r] V postupné implikaci lze premisy sloučit v konjunkci.
[(p ( q) ( ((p ( q) ( (q ( p))] Ekvivalenci lze rozložit na konjunkci dvou obrácených implikací.
[(p ( q) ( (p ( q)] Od ekvivalence lze přejít k implikaci.
Libovolný pravdivý výrok je zvláštním prvkem vůči ( a (
Některé další tautologie tvaru ekvivalence. [p ( (p ( q) ( q] ……
Tautologie zachycující vzájemné vztahy logických spojek. To umožní pochopit "Úplný systém logických spojek" sestavený jen z (, (, ( [(p ( q) ( (( p ( q)] Převod implikace do ( a ( . [(p ( q) ( ((p ( q) ( (q ( p))] Převod ekvivalence na implikaci a konjunkci.

Na základě vět 4-1, 4-2 a 4-3 lze tautologie zobecnit na logicky správná teorémová schémata zadaná ve formulích. V notacích takových schémat používáme pro formule označení a, b, c, .... nebo (, (, ... (pozor na to, že např. [ ( (p ((p) ] není teorémové schéma, protože p je pouhou výrokovou proměnnou).
VZTAHY MEZI LOGICKÝMI SPOJKAMI
V této části půjde o klasifikaci tzv. "Úplného systému" logických spojek, který je postaven jen na (, (, (. Důležitá je následující věta.
Věta
Ke každé formuli ( existuje formule ( obsahující pouze spojky (, (, ( taková, že [( ( (] , tj. formule jsou ekvivalentní.
Důkaz lze provést několika způsoby. Např. ukázáním, že v každé formuli lze ostatní spojky nahradit spojkami z Úplného systému logických spojek.
Dokonce lze definovat Úplné systémy spojek jen z dvojic ((, ((, (( .
Výzkum v matematické logice objevil dvě zvláštní spojky:
( …Peirceova spojka p ( q ( (( p ( (q) ( ((p ( q)
(…Shefferova spojka p ( q ( (( p ( (q) ( ((p ( q)

pomocí každé z nich lze definovat Úplný systém logických spojek.
Jak převedeme (,(,( na ( nebo ( ?
Zapamatujte si převody:
p ( q převedeme na ((( p ( q) ( (((p ( (q) … systém (, (
p ( q převedeme na ((( p ( q) ( (((p ((q) … systém (, (
Věta
Ke každé formuli X existuje formule Y taková, že obsahuje právě jednu ze spojek (, ( a přitom platí [X(Y] .
Příklad
a) Tento příklad ukáže jak provést obrácený proces – konstrukce formule podle zadané pravděpodobnostní tabulky. Později to bude zcela zřejmé, až zvládneme tzv. disjunktní formy.
Nechť je dána formule (x2 ( (x1 ( x3) a její pravděpodobnostní tabulka
x1
x2
x3
(x2
(x1 ( x3)
(x2 ( (x1 ( x3)
0
0
0
1
1
1
0
0
1
1
1
1
0
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
0
1
0
Disjunktní forma vznikne tak, že dáme do disjunkce dílčí konjunkce vzniklé z řádků pravdivostní tabulky:
( x1 ( (x2 ( (x3
(x1 ( (x2 ( x3
(x1 ( x2 ( (x3
(x1 ( x2 ( x3
x1 ( (x2 ( (x3
x1 ( (x2 ( x3
x1 ( (x2 ( x3
x1 ( x2 ( x3
b) Napište formuli, která má následující pravdivostní tabulku
p
q
f(p,q)
0
0
1
0
1
1
1
0
1
1
1
0
c) Pokuste se zapsat symbolický výrok " není to ani bílé ani červené"
"je to bílé"…..b
"je to černé"…..c
" není to ani bílé ani červené"……. (b ( (c …..b ( c… Peirceova spojka
d) Ve výrocích bývá často použita spojka "vylučovací nebo". Používá se slovního obratu
buď…nebo… Formální spojka, které vylučovacímu nebo odpovídá se označuje ( nebo symbolem nonekvivalence ( přičemž (p ( q) ( ((p ( q)
VYČÍSLENÍ NEGACE FORMULÍ
Negace složitých výroků se dá vyřešit pomocí tzv. principu duality. K tomu slouží následující věta.
Věta
Nechť X je formule obsahující pouze spojky (, (, ( a proměnné x1, x2, …, xn . Sestrojme formuli Y tak, že:
každou ze spojek (, ( nahradíme druhou ze dvojice,
každou proměnnou nahradíme její negací.
Potom platí, že ((X (Y) .
Důkaz se dá provést indukcí.
Příklad
podle principu duality negujte následující formule (žlutě jsou označeny výsledky):
p(q (p ( (q
p(q (p((q
p ( q (( p ( q)……p ((q ……………….t23
p ( q ((p ( q) ( (q ( p))………. (( p ( q) ( (q ( p)… (p ( (q) ( ((p(q)
Velmi často se používá termín "logicky ekvivalentní" formule. Jeho zavedení již sice bylo naznačeno, ale teď uvedeme explicitní definici na základě spojky ekvivalence.
Definice 4-2
Říkáme, že formule ( a ( jsou logicky ekvivalentní, jestliže platí ( ( ( . Pochopitelně, každá formule je logicky ekvivalentní sama sobě.
NÁSLEDUJE OPAKOVÁNÍ OBECNÝCH POZNATKŮ O LOGICE TEORIE A JEJÍ DEDUKTIVNÍ SOUSTAVĚ.
Pojetí logiky teorie ------ OPAKOVÁNÍ
Logika ℒ teorie T = ( J , ℒ , A ) je druhou její strukturální komponentou. Bude vybudovaná nad množinou formulí spolu se speciální relací důsledku . Pomocí této relace budeme moci logicky odvozovat další správná tvrzení. Obecná podstata logiky teorie je budována počínaje první definicí.
Nechť je již vybudován jazyk J teorie T . Označme symbolem ℱ množinu všech formulí jazyka J. Podmnožiny množiny všech formulí ℱ budeme označovat symboly (, (', ('', … Systém všech podmnožin množiny ℱ (potence množiny všech formulí) označíme symbolem ℙ (ℱ).
Definice
Logikou ℒ teorie T nazveme množinu ℱ formulí spolu s jistou relací mezi ℙ (ℱ ) a ℱ , kterou nazveme relací důsledku. Logiku ℒ můžeme považovat za strukturu ℒ = [ℙ (ℱ ) x ℱ , ] , kde je jistá unární relace na ℙ (ℱ ) x ℱ .
Notaci ( a budeme číst jako "formule a je důsledkem množiny formulí obsažených v (. Všimněte si, že kartézský součin ℙ (ℱ ) x ℱ je množinou dvojic ((,y), kde ( je množina formulí a y jediná formule. Nevylučuje se ani ( = ( .
Buď a(ℱ běžná formule množiny ℱ všech formulí a (, (' buďte podmnožiny množiny ℱ. Potom na relaci budeme klást tyto definiční požadavky (ODPo):
{a} a pro každou formuli a(ℱ ……reflexivita relace
Jestliže ( a , pak (((' a pro každou množinu (' ( ℱ .
Jestliže ( a pro každou formuli a((' a jestliže (' b , pak ( b ….tranzitivita relace
Jestliže ( a , pak existuje konečná podmnožina ('( ( taková, že (' a ….finitnost dedukce.
Existuje neprázdná množina ℱL ( ℱ taková, že a(ℱL právě tehdy, když ( a . Formule a je univerzálně platná, tj. nepotřebujeme žádnou množinu ( premis, jejichž důsledkem by byla formule a.
Jestliže ( a , potom platí rovněž a , kde je permutace množiny (.
Jestliže {a}, ( b , potom a, ( b ……redukce notace.
Poznámka:
Jestliže ( a , pak formule množiny ( nazýváme premisami (hypotézami), formuli a nazýváme konkluzí (závěrem, logickým důsledkem). Říkáme, že formule a je logickým důsledkem formulí množiny (.
Formule množiny ℱL nazýváme logickými teorémy. Jestliže ( = {a1, a2, …, an}, kde n(1, a1, a2, …, an jsou formule, pak místo {a1, a2, …, an} a budeme psát jen a1, a2, …, an a . Místo ( a , když ( = ( , budeme psát jen a , tj. formule a je logický teorém ( v klasickém výrokovém kalkulu to budou tautologie).
Vlastnostmi 1-5 není relace jednoznačně určena. takových relací je mnoho (vše upřesňuje interpretace relace, viz klasický výrokový/predikátový kalkul).
Příklad
Je zde uvedena ukázka interpretace relace důsledku. Představme si, že pracujeme s jistými jevy a množina ℱ je potom množinou výroků o jevech náležících právě prováděnému pokusu. ( je potom množinou výroků ohodnocujících jisté jevy