přednášky

lkulu
Výrokový kalkul je formalizovaná teorie výroků. Jelikož formalizovaný výrokový kalkul je teorií ve složení (J, ℒ, A=() , je potřebné postupně definovat formální pojetí výroků a potom komponent J a ℒ.
Hlavní je, že se budeme důsledně držet abstrakce od významuplných elementárních výroků typu "číslo 1 je sudé číslo", …, "číslo 5 je menší než číslo 7". Proto budeme muset zvolit strukturu S = ( D, (, ( ) a ukázat si, co jsou vlastně formální výroky a jak je ohodnotit. My již víme, že ( je množina n-árních operací nad prvky z D a ( zase množina n-árních relací mezi prvky nosiče D.
V dané struktuře S zavedeme individuální proměnné označované malými písmeny a,b,c,x,y... případně i s indexem, např. x1, x2, … Objekty množiny D, nosiče struktury S, budeme označovat symboly a1, a2, …, an, …
Množina D obsahuje objekty, přičemž každý z nich se může stát hodnotou individuální proměnné. Proces přiřazení je vlastně OHODNOCENÍM individuální proměnné.
Definice
Je-li ((( libovolná n-ární relace mezi objekty a1, a2, …, an , potom výraz
a1, a2, …, an ( ( označující, že objekty a1, a2, …, an jsou v relaci (, nazveme primitivním výrokem ve struktuře S.
Jsou-li x1, x2, …, xn výrokové proměnné, potom ( (x1, x2, …, xn ) je charakteristická funkce relace (, pro kterou budeme chtít aby platilo ( (x1, x2, …, xn ): Dn {0, 1}. Jinými slovy,
1, potom je výrok a1, a2, …, an ( ( pravdivý
jestliže ( (a1, a2, …, an ) =
0, a1, a2, …, an ( ( nepravdivý
Jazyk J0 formálního výrokového kalkulu
Abeceda jazyka je dána předpisem A0 = V0 ( {(, (, (, (, (} ( { ( , ) }, kde V0 je množinou výrokových proměnných. Jsou to znaky p, q, r, s, p1, … ( , ) jsou závorky.
Znaky (, (, (, (, ( jsou bezobsažné unární nebo binární junktory.
Jazyk J0 je definován notací J0 = (A0, ℱ0 ), kde ℱ0 je množina všech formulí. Jazyk je rovněž bezobsažný.
Formule
Produkce formulí množiny ℱ0 je založena na pravidlech, jejichž schéma již známe z teorie množin:
Všechny výrokové proměnné jsou elementární formule.
Jsou-li a, b formule, potom rovněž ((a) (a(b) (a(b) (a (b) (a(b) jsou formule.
Prioritní seřazení junktorů (, (, (, (, ( umožní vynechávat závorky a tedy za formule rovněž považovat (a a(b a(b a (b a(b
Pro formule se dále zavádí následující pojmy: bezprostřední podformule, běžná podformule, rozklad formule, substituce, schéma formule, model formule, priorita junktorů, … Všechny tyto pojmy podáme v následujícím textu.
Množina proměnných dané formule
Označme Z(a) množinu všech znaků formule a , pak V0 (a) = Z(a) ( V0 je množina všech proměnných formule a. Je zřejmé, že V0 ((a ) = V0 ( a ), V0 ( a * b ) = V0 ( a ) ( V0 ( b ) když za * dosadíme libovolný z bezobsažných junktorů.
Bezprostřední podformule dané formule
Formule q se nazývá bezprostřední podformulí formule a, má-li jeden z následujících tvarů: ( b ( c ), ( c ( b ), ( b ( c ), ( c ( b ), ( b ( c ), ( c ( b ), ( b ( c ), ( c ( b ), (b
Formule q se nazývá (běžnou) podformulí formule a, jestliže existuje taková posloupnost formulí c1, c2, …, cm , m(1, že c1 je q a cm je a. Dále je požadováno, aby pro i =2, 3,…, m byla ci-1 bezprostřední podformulí formule ci.
Tím jsme vlastně nadefinovali rozklad formule na podformule. V rozkladu se postupuje tak, že hledáme vždy bezprostřední podformule.
Příklad
Nalezněte rozklad formule (((p(q) ( (((r ( q) ( (q)) . Zde je řešení ve tvaru stromu:

(((p(q) ( (((r ( q) ( (q))
((p(q) ((r ( q) ( (q)
(p(q) ((r ( q) (q
p q (r ( q) q
r q
Jestliže ve formuli a o proměnných p1, p2, … provedeme substituce tak, že proměnné nahradíme jinými formulemi, dostaneme opět formuli. Tvrzení se dá dokázat indukcí.
Příklad
p ( q je formule. Proveďme substituce p ( (p ( q) , q ( (p ( q), potom (p ( q) ( (p ( q) je opět formule.
Poznámka:
Často se junktor ( neuvádí hned mezi ostatními junktory, ale zavádí se definitoricky jako speciální formule. Např.: Jestliže a, b jsou formule, potom (a ( b) ( (b ( a) je rovněž formule, kterou označíme notací a ( b .
Ačkoliv pro používání závorek bychom mohli definovat jistá pravidla (kdy jsou nutné a kdy ne), není to potřebné protože již máme dostatečné zkušenosti z jejich používání v aritmetických výrazech.
Logika ℒ0
Je totožná s logikou teorie, která má množinu axiomů A=(.
Algebra
Množina formulí ℱ0 , její nosič D, uvažované spolu s operacemi ( = {(, (, (, (, (}, je algebraická struktura, nazývaná algebrou formulí. V této algebře se často definuje relace rovnosti-ekvivalence formulí, kterou budeme označovat symbolem (.
Definice
Dvě formule a, b(ℱ0 jsou ekvivalentní, píšeme a ( b, jestliže [a ( b], [b ( a] .
takto definovaná ekvivalence formulí je reflexivní (a ( a), symetrická (a ( b , b ( a) a tranzitivní (jestliže a ( b, b ( c, pak a ( c). zavedení ekvivalence je podáno na základě spojky (. Protože ( je relace, tak ji nesmíme ztotožňovat se spojkou (.
Co bude požadováno:
Znalosti:
Jak je zaveden primitivní výrok formálního kalkulu?
Jak je zaveden jazyk formálního kalkulu a bezprostřední podformule?
Co je junktor, logika a algebra formálního kalkulu?
Jak je zavedena ekvivalence formulí?
Dovednosti:
Umět rozkládat formuli na bezprostřední podformule.

Klasický výrokový kalkul
Může být podán jako specifická interpretace formálního výrokového kalkulu
Tato interpretace nám umožní dopředu nahlédnout do podstaty klasického výrokového počtu, protože nám odhalí jak klasický kalkul vlastně vznikl.
Zde budeme uvažovat tzv. dvouhodnotovou interpretaci. Interpretovat budeme muset především jazyk J0 tím, že formulím jazyka přiřadíme interpretací konkrétní obsah. Nechť je hodnotou výrokové proměnné intuitivně chápaný dvouhodnotový výrok. Našli jsme tedy zobrazení V0 ℬ, kde ℬ je množina všech intuitivně chápaných dvouhodnotových výroků a V0 je množina výrokových proměnných. Je zřejmé, že platí ℬ {0,1} . Toto zobrazení rozšíříme na všechny formule množiny ℱ0 tím, že budeme za elementární formuli považovat rovněž intuitivně chápaný dvouhodnotový výrok.
Tím došlo k interpretaci formulí ℱ0 ℬ. Junktory teď již nejsou bezobsažné, ale byly převedeny na logické spojky, protože spojují intuitivně chápané dvouhodnotové výroky. Dvouhodnotová interpretace vede na zobrazení V0 {0,1} a ℱ0 {0,1}. zavedená zobrazení dávají možnost rychle vyhodnotit každou formuli ve stromu podformulí (rozklad formule).
Jestliže každé ohodnocení formule vede na hodnotovou třídu {1}, potom je formule tautologií. Existuje mnoho schémat tautologií, např. T1 – T26 , …. Každou tautologii je možno dokázat ohodnocením obálky (koncové proměnné/elementární výroky) ve stromu podformulí/nadformulí. Mnohé z tautologií mají velmi zajímavé názvy (např. zákon reductio ad absurdum, zákon vyloučení třetího – tertium non datur, …). Protože strom rozkladu se zobrazuje tabulkou, říká se této metodě tabulková.
Základy klasického výrokového kalkulu
Kalkul je založen na intuitivním dvouhodnotovém pojetí elementárních výroků a formulí.
Elementární výrok
Elementárním - atomickým výrokem nazveme jakýkoliv jazykový výraz, o kterém má smysl (v dvouhodnotovém pojetí pravda, nepravda) prohlásit, že je buď pravdivý nebo nepravdivý a který nelze dále rozložit.

Prohlásit, že daný výrok je pravdivý nebo nepravdivý je ale někdy problémem (*). Zde si musíme pomoct zákony vědomě odůvodněného myšlení, které je založeno na naší životní praxi.
Logické spojky
Pomocí následujících logických spojek vznikají složené výroky:
"a" "současně" konjunkce
"nebo" disjunkce
"jestliže…, pak" implikace
"platí-li…, potom platí…"
"platnost… implikuje platnost…"
"tehdy a jen tehdy když" ekvivalence
"když a jen když"
"právě když"
"je ekvivalentní"
Formální označování elementárních výroků
K tomu se používají malá písmena a,b, …, p,q, … případně s indexy. Jestliže zobecníme poslání formálních označení, dostáváme se k proměnným, které mohou mít za svou hodnotu elementární výrazy.
Formální prezentace logických spojek
Negace (
Disjunkce (
Konjunkce (
Implikace (
Ekvivalence (
Pravdivostní hodnoty logických spojek
a
(a
0
1
1
0
Negace a
a
b
a ( b
0
0
0
1
0
1
0
1
1
1
1
1
Disjunkce a nebo b je nepravdivá jen v případě nesprávnosti obou výroků

a
b
a ( b
0
0
0
1
0
0
0
1
0
1
1
1
Konjunkce a současně b a a b je pravdivá jen v případě správnosti obou výroků
a
b
a ( b
0
0
1
0
1
1
1
0
0
1
1
1
Implikace jestliže a potom b je nepravdivá právě když ze pravdivé premise a vyvodíme nepravdivý závěr b
Implikaci a ( b vždy chápeme ve smyslu:
není pravda, že když platí a, tak současně neplatí b
a
b
a ( b
0
0
1
1
0
0
0
1
0
1
1
1

Ekvivalence a tehdy a jen tehdy když b je pravdivá, když mají oba výroky stejnou pravdivostní hodnotu.
Ekvivalenci a ( b vždy chápeme ve smyslu:
implikace a ( b , b ( a platí současně
Pozor na správné čtení logických spojek v metajazyku
Negace: není pravda, že a ne a non a neplatí a
Konjunkce: a a b a současně b
Disjunkce: a nebo b
Implikace: a implikuje b jestliže a pak b b jestliže a b v důsledku a a je dostatečnou podmínkou pro b b je nutnou podmínkou pro a
Ekvivalence: a je ekvivalentní b a tehdy a jen tehdy když b a právě když b jestliže a, pak b a jestliže b, pak a a je nutná a postačující podmínka pro b a b je nutná a postačující podmínka pro a
Významná tvrzení o hodnotách spojek
Konjunkce dvou výroků má pravdivostní hodnotu 1 tehdy a jen tehdy, když oba výroky mají zároveň hodnotu 1.
Disjunkce dvou výroků je pravdivá právě když alespoň jeden z nich je pravdivý (pravdivost jednoho z výroků disjunkce implikuje, že disjunkce je pravdivá) .
Implikace dvou výroků má hodnotu 0 právě když její antecedent-premisa-předpoklad má hodnotu 1 a konsekvent-závěr-tvrzení má hodnotu 0 (premisa 1 a závěr 0 implikuje, že implikace má hodnotu 0).
K pravdivosti implikace stačí: - pravdivost závěru (bez ohledu na pravdivostní hodnotu premisy) - nepravdivost premisy (bez ohledu na pravdivostní hodnotu závěru).
Teď můžeme říci, že výrok, který neobsahuje žádnou logickou spojku se nazývá elementární a naopak, elementární výroky svázané logickými spojkami formují tzv. složené výroky.
Příklad
Které z následujících vět nejsou elementární výroky?
"prší"
"odešlete tento dopis"
"Jan není doma"
"kolik je hodin?"
Je doma nebo ve škole"
Věty b. , d. , e. nejsou elementární výroky (b., d. nejsou výroky, e. je složený výrok).
Příklad
Které z daných výrazů nejsou výroky?
"10. září 1970"
"5 < 8"
"8 < 5"
"x + 0 = x"
"23 – 1"
Provedeme-li abstrakci od skutečných elementárních výroků a nahradíme je symboly – tzv. výrokovými proměnnými, za jejichž hodnoty budeme elementární výroky považovat, značně tím zjednodušíme zápis neelementárních, tj. složených výroků.
Příklad
Zapište formálně následující výroky.
Jana a Karel jdou do kina. p(q
Petr leží nebo spí p(q
Je to pěkné, ale není to moc velké p ( (q
Když sněží, má vlak zpoždění s ( z
Sněžení je postačující podmínkou pro zpoždění vlaku s ( z
Sněžení je nutnou podmínkou pro zpoždění vlaku z ( s
Sněžení je nutnou a postačující podmínkou pro zpoždění vlaku s ( z
Vlak má zpoždění tehdy a jen tehdy, když sněží s ( z
Vlak má zpoždění jen tehdy, když sněží z ( s
Vlak má zpoždění právě tehdy, když sněží s ( z
Příklad
Na večeři bylo pozváno pět přátel, které označíme prvním písmenem křestního jména K,L,M,N,P. Jejich odpovědi na pozvání lze vyjádřit těmito výroky: 1 přijde K a přijde L p ( q (přijde K…p přijde L…q) 2 Přijde L nebo přijde M q ( r (přijde M…r) 3 jestliže přijde M, pak přijde také N r ( s (přijde N…s) 4 P přijde právě tehdy, když přijde M t ( r (přijde P…t) Pro nepříznivé počasí nepřišel nikdo. Rozhodněte, kteří z pozvaných přesto porušili slib, tj. které z výroků 1 – 4 jsou pravdivé.
Protože nepřišel nikdo platí: q ( r = 0 jelikož q = 0 ( r = 0
p ( q = 0 p = 0 ( q = 0
r ( s = 1 na hodnotě s nezávisí, protože r = 0
t ( r = 1 je r = 0 a t = 0
Tedy, platí výroky 3,4 r ( s , t ( r , tj. slib neporušily osoby N a P.
Příklad
Zapište formálně následující výroky.
Jestliže přijde otec, pak přijde i matka p ( q (přijde otec…p, přijde matka…q)
Přijde alespoň jeden z rodičů p ( q
Přijde nejvýše jeden z rodičů ((p ( q) .... (p ( (q
Přijde právě jeden z rodičů (p ( (q) ( ((p ( q)
Protože chápání pojmu dostatečné a nutné podmínky v implikaci může být obtížné na formálních notacích, ukážeme si dva praktické příklady.
Mějme výrok "Jestliže prší, pak je mokro". Je to implikace p ( q , kde výroková proměnná p nahrazuje elementární výrok "prší" a proměnná q zase elementární výrok "je mokro". Dostatečnou a nutnou podmínku vyskytnuvší se v této implikaci vysvětlíme takto:
Nemůže být pravda, že když "prší", tak současně neplatí "je mokro". Takto je totiž zaveden význam zadané implikace. Tedy, platnost "prší" dostačuje k tomu, že platí "je mokro" a je proto dostatečnou podmínkou.
"je mokro" ovšem může platit i tenkrát, když "prší" neplatí. Klidně jsme mohli vylít na trávu sud s vodou a hned bylo mokro. Tedy, platnost "prší" není nutná k tomu, aby bylo platné "je mokro".
Teď obráceně. Neplatí-li "je mokro", tak nemohlo ani platit "prší". Jelikož vylití sudu není v naší implikací uvedeno, tak musíme platnost "je mokro" považovat za nutné k platnosti "prší". Tedy, platnost "je mokro" je nutnou podmínkou pro platnost "prší".
Mějme výrok "Jestliže Jarda přijde večer domů, pak je zatopeno". Je to implikace p ( q , kde výroková proměnná p nahrazuje elementární výrok "Jarda přijde večer domů" a proměnná q zase elementární výrok "je zatopeno".
Nemůže být pravda, že když "Jarda přijde večer domů", tak současně neplatí "je zatopeno". Takto je totiž zaveden význam zadané implikace. Tedy, platnost "Jarda přijde večer domů" dostačuje k tomu, že platí "je zatopeno" a je proto dostatečnou podmínkou. Dostatečné mohou být i jiné důvody, ale ty nás nezajímají, nejsou součástí zadané implikace.
"je zatopeno" ovšem může platit i tenkrát, když "Jarda přijde večer domů" neplatí. Klidně se zbytek rodiny vrátil z vycházky, manželka zatopila a platí "je zatopeno". Tedy, platnost "Jarda přijde večer domů" není nutná k tomu, aby bylo platné "je zatopeno".
Teď obráceně. Neplatí-li "je zatopeno", tak nemůže ani platit "Jarda přijde večer domů". To by bylo v rozporu s významem zadané implikace. Jelikož jiný důvod zatopení není v naší implikací uveden, tak musíme platnost "je zatopeno" považovat za nutné k platnosti "Jarda přijde večer domů". Tedy, platnost "je zatopeno" je nutnou podmínkou pro platnost "Jarda přijde večer domů". Platnost "je zatopeno" ale nemůžeme považovat za dostatečnou k platnosti "Jarda přijde večer domů". Proč? Jarda pracuje v Brně a domů za rodinou jezdí v pátek. V baráku je zatopeno bez ohledu na jeho nepřítomnost.
Osvětlení pojetí nutné a dostatečné podmínky v ekvivalenci p ( q se provede prostřednictvím jejího rozkladu na dvě konjunkce (p ( q) ( (q ( p) . Poznámka:
Všimněte si, že v elementárních výrocích je zcela jasné koho se vyslovená vlastnost týká. Nikde není použito obecné kvantifikace (každý, všichni, nikdo, žádný, nic, alespoň jeden, ....) adresátů vlastností. Dále, o pravdivosti/nepravdivosti elementárních výroků jsme schopni okamžitě rozhodnout. Výroky, které budou obsahovat obecné kvantifikace adresátů vlastností budeme nazývat zobecněnými výroky. Tyto výroky jsou ovšem nad možnosti klasického výrokového kalkulu 1. stupně. Např. výroky "Každý člověk je smrtelný" "Žádné úlevy nebyly poskytnuty" "Alespoň někdo udělal zkoušku z TZI" nejsou elementární, ale zobecněné výroky. Takovými výroky se budeme zabývat až v predikátovém kalkulu.
Je pochopitelné, že za relevantní zdroj elementárních a zobecněných výroků můžeme považovat život na naší zeměkouli. Jde o celý rozsah životního prostředí a existenci člověka v něm. Tento zdroj je v příkladech nejčastěji používán. Vedle toho můžeme používat i abstraktní zdroje mezi které jistě patří i středoškolská a vysokoškolská matematika. Je to rovněž vděčný zdroj jak elementárních, tak i zobecněných výroků a výrokových a predikátových formulí. Projdeme teď některými oblastmi středoškolské a vysokoškolské matematiky a vybereme několik vhodných příkladů.
Příklad
Je dána implikace p ( q . Zapište výrokové formule vyjadřující:
obrácení dané implikace q ( p
obměnu implikace (p ( q) ( ((p ( q) ( (q ( (p) ( ((q ( ( p)
negaci implikace (p ( (q)
Výsledky prověříme jednoduchou pravdivostní tabulkou (výsledky na stejné kombinace pravdivostních hodnot parametrů jsou stejné).
p
q
p (q
((p ( q)
(q ( (p
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
Příklad
Následující příklady jsou orientovány na formalizaci složených výroků a jejich vyhodnocení.
Ředitel dává svým zaměstnancům zajímavý příslib: "Zvýšíte-li si kvalifikaci, pak získáte vyšší pracovní zařazení" Ředitel by nesplnil svůj slib jen v případě, kdy si zaměstnanec zvýší kvalifikaci a on mu nedá vyšší pracovní zařazení.
Pavel nepřišel do školy. Můžeme považovat za pravdivý výrok "Jestliže Pavel onemocněl, pak dnes nepřišel do školy" i když nevíme, zda Pavel opravdu onemocněl? Protože k pravdivosti implikace stačí pravdivost závěru, můžeme výrok považovat za pravdivý.
Trosečníci Adam, Barry, Code a Dan zapoměli po čase kalendář. Začali se dohadovat, který den v týdnu vlastně je. Každý z nich řekl svůj názor: A: Dnes je úterý nebo zítra je neděle B: Dnes není úterý nebo zítra je neděle C: Dnes je úterý nebo zítra není neděle D: Dnes není úterý nebo zítra není neděle a) Kdo z nich měl pravdu, jestliže toho dne byl ve skutečnosti pátek? dnes je úterý…..p zítra je neděle……q A: p ( q B: ((p) ( q C: p ( (( q) D: ((p) ( ((q) Pravdu měli B, C a D. b) Kdo z nich neměl pravdu jestliže toho dne bylo úterý? Pravdu neměl B. c) Která tvrzení jsou pravdivá nezávisle na tom, který den v týdnu byla vyslovena? Tvrzení trosečníka Dana.
při praktickém cvičení z elektřiny mají studenti provést sérii tří pokusů P1, P2, P3 . Úspěšnost pokusů na sobě závisí takto: - nepodaří-li se pokus P1, nepodaří se ani pokus P2 - nepodaří-li se pokus P2, nepodaří se ani pokus P3 Během provádění pokusu si všimne student Nevrlý, že jeho soused Mokrý provedl pokus P2 neúspěšně. A tedy mu radí: a) aby nezačínal pokus P3 b) aby opakoval pokus P1, protože v něm musela být chyba Která z obou rad je oprávněná, když Nevrlému nebylo nic bližšího známo o výsledku Mokrého pokusu P1 . Řešení: Zaveďme tyto výroky: "podaří se pokus P1 "…..p1 "podaří se pokus P2 "…..p2 "podaří se pokus P3 "…..p3 Pokus P2 je neúspěšný, tedy ( p2 =1 . závislost pokusů lze zapsat dvěma formulemi: ( p1 ( ( p2 ……f1 (x1, x2) ( p2 ( ( p3 ..….f2 (x2, x3) Rada a) je oprávněná, protože ( x2=1 a f2 (0, x3) =1 jen když x3=0 Rada b) je neoprávněná, protože ( x2=1 a f1 (0, x2) =1 nebo f1 (1, x2) =1 Jestliže Nevrlý nevěděl jak dopadl pokus P1, tak radil špatně, protože klidně mohl být pokus P1 úspěšný.
Nechť je p=0. Co se dá říct o pravdivostní hodnotě pravdivostní funkce formule (p(q) ( (p(r) ať jsou hodnoty pro q, r jakékoliv? Řešení: Formule je kontradikce b