Výroková logika. Základy algoritmizace, FEI 1

Výroková logika Obsah Výroková logika......................................................................................................................... 2 Výrok...................................................................................................................................... 2 CVIČENÍ (Výroky):........................................................................................................... 3 Konjunkce .............................................................................................................................. 4 CVIČENÍ (Konjunkce): ..................................................................................................... 5 NEGACE................................................................................................................................ 6 CVIČENÍ (Negace):........................................................................................................... 7 DISJUNKCE .......................................................................................................................... 8 CVIČENÍ (Disjunkce):..................................................................................................... 10 IMPLIKACE ........................................................................................................................ 11 CVIČENÍ (Implikace):..................................................................................................... 13 EKVIVALENCE.................................................................................................................. 14 CVIČENÍ (Ekvivalence): ................................................................................................. 15 ZAVEDENÍ SYMBOLŮ ..................................................................................................... 16 CVIČENÍ (Zavedení symbolů): ....................................................................................... 18 ZKRACOVÁNÍ VÝRAZŮ.................................................................................................. 19 CVIČENÍ (Zkracování výrazů):....................................................................................... 20 VÝZNAMY V SYMBOLICKÉM JAZYCE ....................................................................... 21 CVIČENÍ (Významy v symbolickém jazyce):................................................................. 22 VÝPOČET HODNOTY FORMULE................................................................................... 23 CVIČENÍ (Výpočet hodnoty formule):............................................................................ 26 PRAVDIVOSTNÍ TABULKY FORMULÍ ......................................................................... 27 CVIČENÍ (Pravdivostní tabulky formulí):....................................................................... 29 TAUTOLOGIE A KONTRAINDIKACE VÝROKOVÉ LOGIKY.................................... 30 CVIČENÍ(Tautologie a kontradikce výrokové logiky):................................................... 32

Základy algoritmizace, FEI

1

Výroková logika

Výroková logika Pod pojmem výroková logika zahrneme všechna zkoumání týkající se logického spojování výroků, zejména pak ta, která vycházejí z významu (logického obsahu) výrokových spojení.

Výrok Pojem výrok patří ke klíčovým pojmům logiky. Výrokem je vše v jazykovém tvaru, co vyjadřuje nějaké tvrzení(nebo cokoli v tomto tvaru, čemuž lze přiznávat pravdu nebo nepravdu).Ve výrokové logice budeme za výroky pokládat i věty obsahující neurčité výrazy(proměnné), tj. výroky zde budou i výrazy, jímž za určitých okolností může být přiznána pravda za jiných nepravda. Příklady výroků. Výrokem je oznamovací věta „Jan je doma“, protože tvrdí o někom jménem „Jan“, že je doma. Naproti tomu výraz „nejstarší Janův bratr“ není výrokem; poukazuje sice na osobu, která je nejstarším Janovým bratrem, ale nic o ní netvrdí. Ani věta „nechť Jan je doma“ není výrokem; nevyjadřuje tvrzení o Janovi, ale pouze přání, jež se ho týká. Výrokem je každý z výrazů „2 + 3 = 5“, „2 + 3 ≠ 5“, „2 + 3 = 6“. Všechny tyto výrazy představují určitá tvrzení; na věci nic nemění to, že výraz druhý a třetí tvrdí něco zcela nepodloženého. Příklady ukazují, že výroky mohou být stejně pravdivé jako nepravdivé. Pravdivost a nepravdivost budeme nazývat pravdivostními hodnotami výroků. Pravdivý výrok má pravdivostní hodnotu pravda, nepravdivý výrok má pravdivostní hodnotu nepravda, Pravdivostní hodnoty jsou tedy dvě; první (pravdu) budeme označovat symbolem „1“, druhou (nepravdu) symbolem „0“. Úkolem logiky je zkoumat, zda jisté úvahy jsou logicky správné, zda z pravdivých výchozích tvrzen umožňují dojít opět jen k pravdivým tvrzením. Aby takové rozbory byly možné, je třeba se zaměřit na to, na čem logická správnost závisí. Podstatnou roli tu hraje forma výroků.Jí rozumíme to, co výrok charakterizuje po stránce skladebné (to, jak je konstruován, co jej vnějškové, typograficky charakterizuje, a ne co vypovídá). Díváme-li se na výroky z hlediska jejich formy, zjistíme brzy, že řada jich je výsledkem spojení výroků jednodušších. Spojování výroků je významná logická operace. Podíváme se nejdříve, jak jsou výroky spojovány. Srovnejme výroky „je doma“, „dívá se na televizi“ s výrokem „jestliže je dona, pak se dívá na televizi“. První dva výroky jsou součástmi výroku třetího. Výrok třetí je výsledkem spojení výroku prvního s druhým. Výroky „je doma“ a „dívá se na televizi“ nejsou již rozložitelné na jednodušší. Výroky toho druhu nazýváme elementárními.Výrok třetí je výsledkem spojení dvou (samostatných) výroků. Výroky vytvořené z jednodušších nazýváme složenými. K utvoření našeho složeného výroku bylo použito spojovacích slov „jestliže, pak“. Spojovací částice (jako celek ) tvoří to, co nazýváme výrokovou spojkou. Logický obsah výrokových spojek bude prvním tématem, jímž se budeme zabývat. na následujících stránkách budeme analyzovat hlavně tyto výrokové spojky: „a“, „ne-“, „nebo“, „jestliže, pak“, když a jen když“. Uvedené výrové spojky dovolují utvářet složené výroky této formy: „A a B“, „ne- A“, „A nebo B“, „jestliže A, pak B“, „A když a jen když B“. Tyto výroky nazýváme po řadě konjunkcí, negací, disjunkcí, implikací a ekvivalencí.


2

Výroková logika

CVIČENÍ (Výroky): 1.Určete, které ze zadaných vět nejsou výroky: a) Prší. b) Odešlete tento dopis. c) Jan není doma. d) Kolik je hodin? e) Je doma nebo ve škole?. 2.Určete, který ze zadaných výrazů není výrok: a) 10. září 1970 b) 5 < 8 c) x + 0 = x d) 2 3 − 1 3. Výrok „Čína je nejlidnatější země světa“ má pravdivostní hodnotu .......................................... Výrok „Sokrates byl toreadorem“ má pravdivostní hodnotu ...................................................... V případě, že Jana je blondýna, výrok „Jana je blondýna“ má pravdivostní hodnotu ................ V případě, že Jana není blondýna, výrok „Jana je blondýna“ má pravdivostní hodnotu ............ 4.Jak nazýváme výroky uvedeného tvaru? „A a B“ nazýváme............................................. „ne A“ nazýváme .............................................. „jestliže A, pak B“ nazýváme ........................... „A když a jen když B“....................................... „A nebo B“ nazýváme.......................................


3

Výroková logika

Konjunkce Konjunkcí je, výrok tvaru „A a B“; výroky A, B v tomto výraze mohou být libovolné. konjunkcí je například výrok: vešel do domu a rozsvítil (1) Výroky „vešel do domu“ a „rozsvítil“ jsou složkami dané konjunkce. Spojka „a“ je spojkou konjunkce. V souladu s výměrem konjunkce je konjunkcí též například: dnes je pondělí a π je iracionální číslo (2) Skutečnost, že výrok (2) hodnotí logika jako smysluplný, může vzbudit jisté rozpaky. Výrok (2( je přijatelný jako konjunkce, vyplývá ze zaměření formální logiky: v této logice je pozornost soustředěna nikoli na obsah výroků, ale na to, jak jsou konstruovány, jakou mají logickou skladbu. Z toho důvodu také požadavek, aby logicky spojované výroky byly obsahově nějak spjaty, není do této logiky pojat. Logika nás však nenutí výroky typu (2) používat; říká jen, že by byly logicky přijatelné, kdybychom je někdy potřebovali. Konjunkce po stránce tvarové je vymezena; definujme ještě její logický obsah. Ten vymezíme tím, že určíme podmínky, za nichž je pravdivá. Konjunkce je pravdivá, jsou-li oba výroky, jež obsahuje, pravdivé. Nepravdivá je v případech zbývajících. Jak definice ukazuje , pravdivostní hodnota konjunkce je jednoznačně dána pravdivostními hodnotami jejích složek. To nám umožňuje tabulkové vyjádření této definice: A 1 1 0 0

B AaB 1 1 0 0 1 0 0 0 Pravdivostní tabulka konjunkce

Pravdivostní tabulka ukazuje, jak závisí pravdivostní hodnota konjunkce „A a B“ na hodnotách jejíchž složek, výroků A, B. Tak, například výrok „vešel do domu a rozsvítil“ bude pravdivý, právě když pravdivé budou výroky „vešel do domu“ a „rozsvítil“. (To indikuje první řádek tabulky konjunkce.) Za zbývajících okolností je nepravdivý. Tabulka naznačuje, že ve výrokové logice budou dobře použitelné funkční pojmy; pravdivostní hodnota výroku „A a B“ je, jak patrno, jednoznačně určena hodnotami výroků A, B, jinými slovy řečeno, hodnota „A a B“ je funkcí hodnot A, B. Pravdivostní tabulka konjunkce je tak vlastně tabulkou funkční(zadávající funkci), slovo „a“ v „A a B“ výrazem, který funkci reprezentuje, čili funktorem.


4

Výroková logika

CVIČENÍ (Konjunkce): 1. Znáte konjunkci po stránce skladebné?.................................................................................... Konjunkcí výroků „prší“ a „je chladno“ je výrok ........................................................................ Výrok „3 + 3 = 7 a dnes je pondělí“ je konjunkcí výroků ........................................................... Matematický výraz „x < y < z“ je zřejmě konjunkcí, a to výroků ............................................... 2.Rozhodněte! Je výrok „včera odcestoval a včera odcestoval“ konjunkcí? a) daný výrok je konjunkcí b) daný výrok není konjunkcí c) nedovedu odpovědět 3.Znáte konjunkci po stránce jejího obsahu? Konjunkce „Kypr je ostrov a 3/6 = 1/2“ má hodnotu .................................................................. Konjunkce „x je sudé číslo a x je prvočíslo“ má hodnotu pravda, právě když x = ..................... 4.Konjunkce je nepravdivá právě v těch případech, když a) aspoň jeden výrok v ní se vyskytující je nepravdivý b) oba výroky v konjunkci jsou nepravdivé 5.Rozhodněte. Pravdivostní hodnota konjunkce „dnes je pondělí a zítra čtvrtek“ na pravdivostní hodnotě „dnes je pondělí“. a) závisí b) nezávisí c) nelze to určit d) nedovedu odpovědět 6.Rozhodněte, co je správné! Pravdivostní hodnota konjunkce „dnes je pondělí a 2*2 = 4“ na pravdivostní hodnotě „dnes je pondělí“. a) b) c) d)

závisí nezávisí nelze to určit nevím


5

Výroková logika

NEGACE Negací je, jak jsme řekli, výrok tvaru ne-A, viz.: není přítomen voda není hořlavina dopis nebyl odeslán Negace „není přítomen“ je popřením výroku „je přítomen“, analogicky „voda není hořlavina“ je popřením výroku „voda je hořlavina“. Částice „ne-“ je spojka negace. Toto slovo bývá často zastupováno obratem „není pravda, že“, a to především v těch případech, kde užití „ne-“ naráží na jisté obtíže. Tak negacemi výroků „7 > 9“, „je doma a pracuje“, „nespí“ jsou po řadě výroky: není pravda, že 7 > 9 není pravda, že je doma a pracuje není pravda, že nespí Obraty „ne-“ a „není pravda, že“, budeme pokládat za synonymní; z toho vyplývá, že například výroky „není přítomen“ a „není pravda, že není přítomen“ vyjadřují touž negaci. Původní vymezení negace můžeme nyní trochu upřesnit: negací je každý výraz „ne-A“, popřípadě „není pravda, že A“, kde „A“ je výrok. Tak „není pravda, že nespí“ je negace, protože „nespí“ je výrok. Výrok „nespí“ je negace výroku „spí“. Výrok „není pravda, že nespí“ je tzv. dvojí negace. Obsah negace je vymezen takto: Negace je pravdivá, je-li negovaný výrok nepravdivý, a nepravdivá, je-li naopak pravdivý. A ne-A 1 0 0 1 Pravdivostní tabulka negace Tak například výrok „není pravda, že π je racionální číslo“ je pravdivý, neboť výrok „π je racionální číslo“ je nepravdivý. Výrok „není pravda, že je doma a pracuje“ bude pravdivý, právě když výrok „je doma a pracuje“ bude nepravdivý; tak tomu bude v tom případě, když aspoň jeden z výroků „je doma“ a „pracuje“ bude nepravdivý. Upozornění. Výraz tvaru „není pravda, že A“ není tvrzením o výroku A, ale složeným výrokem utvořeným z „není pravda, že“ a „A“. Naopak tvrzení „A je nepravdivý výrok“ není negací výroku A, ale přiřazením hodnoty nepravda výroku A. Negace kvantifikovaných výroků Výrok Negace výroku Každý …… je…… Aspoň jeden ….. není …… Aspoň jeden ….. je …… Žádný (každý) ….. není …. Aspoň n ….. je …… Nejvýše (n – 1) ….. je ….. Nejvýše n ….. je…. Aspoň (n + 1] ….. je …..


6

Výroková logika

CVIČENÍ (Negace): 1.Znáte dobře pojem negace? a) Výrok „dopis nedošel“ je negací výroku b) Výrok „a ≠ b“ je negací výroku c) Výrok „není pravda, že dopis nebyl odeslán“ je negací výroku d) Negujeme-li výrok „0,3 není celé číslo“ dostáváme výrok e) Negujeme-li výrok „a ≠ b“, dostáváme výrok 2.Co je správné? Které z níže uvedených tvrzení platí? a) „dnes je neděle“ je negací výroku „dnes není neděle“ b) „tři není sudé číslo“ je negací výroku „tři je sudé číslo“ c) „tři je sudé číslo“ je negací výroku „tři není sudé číslo“ 3.Znáte logický obsah negace? a) Má-li „ne-A“ hodnotu 0, pak A má hodnotu ................................................ b) Výrok „není pravda, že přišel“ bude pravdivý jen tehdy, když výrok „přišel“ bude ............................................................................................................. c) Má-li výrok A hodnotu 1 a výrok B hodnotu 0, pak výrok AaB má hodnotu ................................a výrok ne-(AaB) hodnotu 4.Pravdivostní hodnota výroku „ne-A“ na pravdivostní hodnotě výroku „A“ a) závisí b) občas závisí(podle obsahu A) 5.Výrok tvaru „není pravda, že A“ a) je vždy nepravdivý b) není vždy nepravdivý


7

Výroková logika

DISJUNKCE Protože disjunkcí je každý výrok tvaru „A nebo B“, kde A, B jsou výroky, disjunkcí je například výrok x = 2 nebo x = 4 (1) Výroky „x = 2“ a „x = 4“ jsou složkami disjunkce (1), slovo „nebo“ spojkou disjunkce. Disjunkcí je ovšem například i: 2 < 3 nebo zítra je pátek (2) Skutečně, „2 < 3“ a „zítra je pátek“ jsou výroky, jejichž spojení pomocí „nebo“ musí být disjunkcí. Logický obsah disjunkce vymezuje následující definice. Disjunkce je pravdivá, je-li aspoň jeden výrok, který se v ní vyskytuje, pravdivý. Nepravdivá je, jen když oba její výroky jsou nepravdivé. To ukazuje pravdivostní tabulka disjunkce: A 1 1 0 0

B 1 0 1 0

A nebo B 1 1 1 0

Snadno ověřujeme, že výrok (2) je v logice nejen smysluplný, ale i pravdivý. Vzniká zde otázka, v jakém poměru je logické „nebo“(spojka disjunkce) k „nebo!, které užíváme běžně v češtině. Čeština má několik zvláštních „nebo“, lišících se významově. probereme zde tři nejtypičtější „nebo“ češtiny; označíme si je „nebo1“, „nebo2“, „nebo3“. První z uvedených spojek „nebo1“, užije člověk tehdy, chce-li vypovědět, že ze dvou neslučitelných alternativ jedna platí, není ovšem známo, která; tak je tomu například v souvětí: zůstal doma, nebo1 odjel na ryby Že řečené platí, k tomu stačí, aby jedna z možností byla potvrzena. Druhá je automaticky vyloučena, protože platí-li A (resp. B), je vyloučeno, aby v „A nebo1 B“ platilo též B (resp.A). Spojku „nebo2“ použijeme tehdy, když hodláme vyjádřit, že ze dvou zároveň realizovatelných možností platí právě jedna, není ovšem známo, která. Takové „nebo“ se vyskytuje v souvětí dostal rekreační poukaz peněžitou nebo2 odměnu řečeném s úmyslem vyjádřit, že buďto dostal rekreační poukaz, a ne peněžitou odměnu , nebo peněžitou odměnou, ale nikoli rekreační poukaz. Uvedené „nebo“ se liší od „nebo1“ v tom, že neslučitelnost uvozovaných alternativ přímo konstatuje, kdežto v souvětí s „nebo1“ tato neslučitelnost dána fakty, které jsou obsahem alternativ. Platnost „A nebo2 B“ může být potvrzena jen prozkoumáním platnosti A i B, protože potvrzením/popřípadě vyvrácením) A (resp. B) není ještě o platnosti „A nebo2 B“ rozhodnuto. abychom v češtině vyznačili, že máme na mysli tento smysl „nebo“ (smysl vylučovací), píšeme před „nebo2“, čárku. Někdy se „nebo2“ nahrazuje „anebo“, popřípadě vazbou „buďto, anebo“; těmito obraty jen zesilujeme vylučovací smysl spojení. Poslední z našich „nebo “,„nebo3“, užijeme tehdy, záleží-li nám na tom, abychom vyjádřili, že z daných alternativ musí platit aspoň jedna. O takové „nebo“ jde například ve výroku: je nemocen nebo3 přepracován Základy algoritmizace, FEI

8

Výroková logika K potvrzení platnosti „A nebo3 B“ stačí zjistit, že jedna z uvedených možností platí. Platnost (či neplatnost) té druhé je už zcela irelevantní. Protože toto „nebo“ nevylučuje, aby obě z uvedených alternativ platily současně, nazývá se „nebo“ nevylučovací. Právě ono je vzorem spojky disjunkce. Všechna ukázaná „nebo“ češtiny se liší od spojky disjunkce navíc ještě tím, že věty jimi uvozované musí být skutečnými alternativami(tj. větami ve své platnosti si tak či onak konkurujícími, a v důsledku toho i nějak obsahové spjatými). Jako alternativy nemohou ovšem vystupovat věty, jejichž platnost nemá problematický charakter. Tak v běžném jazyce má smysl říkat x = 4 nebo x > 5 (3) ale nikoli nap59klad 4 = 4 nebo 4 > 5 (4) Tvrzení (4) se nám zdá být nepřípadné, protože výroky 4 = 4 , 4 > 5 nepociťujeme jako problematická tvrzení, neboť pravdivost prvního a nepravdivost druhého jsou mimo pochybnost.


9

Výroková logika

CVIČENÍ (Disjunkce): 1.Výrok „prší nebo sněží“ je pravdivý v těchto třech případech, když a) prší a sněží b) c) 2.Výrok „A nebo B“ má hodnotu 0, jen když ........................................ 3.Má-li výrok A hodnotu 0, pak hodnota „A nebo B“ na hodnotě B a) závisí b) nezávisí c) nevím 4. Má-li výrok B hodnotu 1, pak hodnota „A nebo B“ na hodnotě A a) závisí b) nezávisí c) nevím 5.Potvrdí-li se pravdivost jednoho (lhostejno kterého) výroku v disjunkci, to stačí/nestačí k tomu, aby byla potvrzena pravdivost celé disjunkce. Zakroužkujte správnou odpověď. 6.V souvětí „přijde domů na vánoce nebo na Nový rok“ se vyskytuje: nebo1 nebo2 nebo3 7.Doplňte následující tabulku: A 1 1 0 0


B A a B A nebo2 B A nebo3 B 1 0 1 0

10

Výroková logika

IMPLIKACE Že A implikuje B, vyjádříme obecně výrazem tvaru jestliže A, pak B Implikací bude tak každý výrok, který dostaneme, když do schématu jestliže _ _ _, pak . . . dosadíme na volná místa výroky. Výrok jestliže je neděle, pak obrazárna je otevřená (1) je zřejmě výsledkem dosazení „je neděle“ na první místo a „obrazárna je otevřená“ na druhé místo uvedeného schématu. První výrok v implikaci (dosazený na místo _ _ _) nazýváme antecedentem, druhý (dosazený na místo . . .) konsekventem implikace. Antecedentem i konsekventem mohou být libovolné výroky, implikacemi jsou proto například i takováto souvětí: jestliže voda je hořlavina, pak 2 + 3 = 5 (2) jestliže voda je hořlavina, pak 2 + 3 = 6 (3) jestliže voda není hořlavina, pak 2 + 3 = 5 (4) jestliže voda není hořlavina, pak 2 + 3 = 6 (5) Výroky (2( až (5) naznačují, že logika nezamýšlí implikace užívat v platnosti podmínkového souvětí. Jaký logický obsah byl sousloví „jestliže, pak“ jakožto spojce implikace určen, vyjadřuje tato definice: Implikace je pravdivá, jsou-li oba její výroky buďto pravdivé, nebo oba nepravdivé, nebo antecedent je nepravdivý a konsekvent pravdivý; nepravdivá je když antecedent je pravdivý a konsekvent nepravdivý. Tabulka implikace: A B Jestliže A, pak B 1 1 1 1 0 0 0 1 1 0 0 1 Tabulka implikace prozrazuje, že logické souvětí „jestliže A, pak B“ nemá za úkol vyjádřit nějaký obsahový vztah mezi složkami A, B, nýbrž jen vztah mezi jejich pravdivostními hodnotami: konkrétně to, že se nepočítá s možností s možností, že první výrok implikace je pravdivý a druhý nepravdivý. Tvrdíme-li implikaci jestliže číslo je dělitelné 6, pak je dělitelné 3 vyjadřujeme pouze to, že nevěříme v možnost, že by číslo bylo dělitelné 6 a přitom nebylo dělitelné 3 Podobně tak implikace jestliže se stav zhoršil, pak lékař nařídil hospitalizaci nemůže být vykládána jako vyjádření, že zhoršení stavu je příčinou (nebo podmínkou) toho, že lékař nařídil hospitalizaci, nýbrž jen toho, že se nevěří v možnost, že by stav nemocného se zhoršil a lékař nenařídil hospitalizaci Z tohoto vysvětlení jasně vyplývá, že implikaci nelze pokládat za „podmínkové souvětí“ logiky. To je možno velmi přesvědčivě doložit i na výroku jestliže 7 je prvočíslo, pak kyslík je prvek který jako implikace je zjevně pravdivý (pravdivý je jak antecedent, tak i konsekvent, pravdivá je proto i celá implikace), který ovšem není pravdivý jako podmínkové souvětí


11

Výroková logika (neboť skutečnost, že číslo 7 je prvočíslo, nelze klást v žádném ohledu jako podmínku pro to, že kyslík je prvek).


12

Výroková logika

CVIČENÍ (Implikace): 1.Doplňte: Výrok tvaru „jestliže A, pak B se nazývá .................. Druhý výrok v implikaci se nazývá............................ První výrok v implikaci se nazývá ............................. 2.Výrok „jestliže je doma, pak se dívá na televizi“ je pravdivý v těchto situacích: je doma a dívá se na televizi .............................................. .............................................. 3.Implikace je nepravdivá jen v případě, že antecedent je ........ a konsekvent ......................... . 4.A má hodnotu 0, B má hodnotu 1; potom „jestliže A, pak B“ má hodnotu ..................... 5. Víme, že je pravdivá implikace: „Jestliže je Jana nemocná, potom nepřijde do školy. Dnes Jana nepřišla do školy. Rozhodněte, zda je pravdivý výrok: „Jana je nemocná.“ 6. Zapište formálně následující výroky. 1. Jana a Karel jdou do kina. 2. Petr leží nebo spí. 3. Je to pěkné, ale není to moc velké. 4. Když sněží, má vlak zpoždění. 5. Sněžení je postačující podmínkou pro zpoždění vlaku. 6. Sněžení je nutnou podmínkou pro zpoždění vlaku. 7. Sněžení je nutnou a postačující podmínkou pro zpoždění vlaku. 8. Vlak má zpoždění tehdy a jen tehdy, když sněží. 9. Vlak má zpoždění jen tehdy, když sněží. 10. Vlak má zpoždění právě tehdy, když sněží.


13

Výroková logika

EKVIVALENCE Spojkou ekvivalence je sousloví „když a jen když“, ekvivalencí každý výraz vzniklý dosazením výroků do schématu ------------- když a jen když -----------Ve smyslu této definice je ekvivalencí výrok signál přichází, když a jen když vznikne porucha (1) stejně jako výrok Praha je město, když a jen když 8 < 9 (2) Co do logického obsahu je ekvivalence vymezena takto: Ekvivalence je pravdivá, jsou-li její výroky buďto oba pravdivé, nebo oba nepravdivé. V ostatních případech je nepravdivá. Tabulka ekvivalence A 1 1 0 0

B A když a jen když B 1 1 0 0 1 0 0 1

Tak ekvivalence (1) je pravdivá v těchto dvou případech: když signál přichází a vznikla porucha a signál nepřichází a porucha nevznikla. Výrok (2) je jistě pravdivý, protože splňuje podmínky prvního řádku tabulky ekvivalence. Sousloví „když a jen když“ lze nahrazovat například souslovími „ tehdy a jen tehdy, když“, právě tehdy, když“, „právě když“.


14

Výroková logika

CVIČENÍ (Ekvivalence): 1.Podtrhněte správnou odpověď.Ekvivalence „4 je prvočíslo, když a jen když Dunaj teče do Severního moře“je (pravdivá, nepravdivá). 2.Ekvivalence „a – b = 0, když a jen když a = b“ je pravdivá, protože není možné, aby ............ nebo ................................................ 3.Jestliže výrok A má hodnotu 0, pak pravdivostní hodnota „A když a jen když B“ na hodnotě B: a) závisí b) nezávisí c) nelze určit 4.Výrok „píše, jen když má inspiraci“ má význam výroku a) „píše, právě když má inspiraci“ b) „jestliže píše, pak má inspiraci“ c) „jestliže má inspiraci, pak píše“ d) žádné z těchto vět 5.Pokuste se sestavit tyto tabulky A B A, jen když B A, když B A, právě když B 1 1 1 0 0 1 0 0


15

Výroková logika

ZAVEDENÍ SYMBOLŮ V předchozích kapitolách jsme se obeznámili se způsoby spojování výroků. Výroková logika, v jejímž rámci jsou výzkumy spojování výroků prováděny, klade si za cíl prozkoumat logické zákonitosti, které se k těmto jevům vztahují. Nejoptimálnější možnosti pro tyto výzkumy skýtá jazyk zvlášť pro tyto účely konstruovaný, symbolický jazyk logiky. Jazyk ovládá člověk tehdy, disponuje-li určitou zásobou slov toto jazyka, dále zná-li způsoby, jak této zásoby slov využívat k vyjadřování myšlenek. Zásobu slov toho kterého jazyka nazýváme slovníkem, to, jak se slova kombinují ve vyšší smysluplné celky, nazývá se gramatika. Umělý jazyk, jakým bude jazyk výrokové logiky, vzniká vždy na podkladě dohody. Touto dohodou je stanoven jak jeho slovník, tak i jeho gramatika. Slovníkem budeme tu rozumět seznam symbolů; jedině z nich je možno sestavovat výrazy daného jazyka. Gramatikou je soubor pravidel určujících, které výrazy jsou v daném jazyce gramaticky správně utvořeny. Ve významu elementárních výroků budou v ustavovaném jazyce vystupovat písmena p, q, r, s, v případě s indexy, p1, p2, p3 atd. Tato písmena budeme nazývat výrokovými proměnnými (nebo také výrokovými symboly) Spojky konjunkce, negace, disjunkce, implikace a ekvivalence budou v daném symbolismu zastoupeny po řadě symboly ∧, ∼,∨, ⊃, ≡.(pro konjunkci můžeme použít také znak &, pro negaci ¬, pro implikaci →, pro ekvivalenci ↔ Podrobněji o nich informuje dále uvedená tabulka. složený výrok spojka symbol Výrok s p, q konjunkce „a“ p∧q ∧ negace „ne-“ p∼q ∼ disjunkce „nebo“ p∨q ∨ implikace „jestliže, pak“ p⊃q ⊃ ekvivalence „když a jen když“ p≡q ≡ Vedle výrokových symbolů a spojek obsahuje jazyk výrokové logiky ještě závorky. Jejích funkce spočívá v tom, že ukazují, jakým způsobem jsou spojeny části uvnitř složeného výrazu. Jazyk výrokové logiky má tento slovník a gramatiku: Slovník obsahuje a) výrokové symboly: p, q, r, s nebo, p1, p2, p3 atd. b) výrokové spojky: ∧, ∼,∨, ⊃ c) pomocné symboly: [,] Gramatika má tato pravidla: A) symboly p, q, r atd. samy o sobě jsou gramaticky správné; B) jestliže A je gramaticky správný výraz, pak ∼A je gramatický správný výraz; C) jestliže A, B jsou gramaticky správné, pak [A ∧ B], [A ∨ B], [A ⊃ B]; D) jen výrazy vyhovující podmínkám uvedeným pod (A) až (C) jsou gramaticky správné Pokud se jedná o výraz tvaru [A ≡ B], jde vždy o zkratku konjunkce [[A ⊃ B] ∧ [B ⊃A]]. Ukažme, že v souhlase s ustanoveními jazyka výrokové logiky je výraz [p ⊃ [q ∨ ∼ p]] gramaticky správný. Písmena p, q jsou gramaticky správná (pravidlo A). Výraz ∼ p je Základy algoritmizace, FEI

16

Výroková logika gramaticky správný, protože písmeno p je gramaticky správný, protože písmeno p je gramaticky správné (pravidlo B). Disjunkce [q ∨ ∼ p] je gramaticky správná v důsledku správnosti výrazů ∼ p a q (pravidlo C). Sám výraz [p ⊃ [q ∨ ∼ p]] je gramaticky správný, protože správné jsou výrazy p a [q ∨ ∼ p] (pravidlo C). Jiný příklad; Výraz ∼ ∼ ∼ ∼ ∼ p je gramaticky správný; ∼ p je správný výraz v důsledku správnosti p (pravidlo B), ∼ ∼ p je správný výraz v důsledku správnosti ∼ p (pravidlo B), . . ., ∼ ∼ ∼ ∼ ∼ p je výraz gramaticky správný v důsledku správnosti ∼ ∼ ∼ ∼ p. Nesprávný je například výraz [∼ p ∧], protože nemá žádný z tvarů, jež připouštějí gramatická pravidla.


17

Výroková logika

CVIČENÍ (Zavedení symbolů): 1.Jazyk logiky je ustanoven, je-li dán (co?) ............................ toho jazyka a (co?) ..................................... daného jazyka. 2.Slovník jazyka a výrokové logiky obsahuje výčet (čeho ?) .. ............................... , ..................................... a pravou a levou závorkou. 3.Výraz [A ≡ B] není gramaticky správným výrazem jazyka výrokové logiky, protože jde o (co ?) ........................... (čeho?) ............................................... .


18

Výroková logika

ZKRACOVÁNÍ VÝRAZŮ Výrazy logiky není nutné používat v tom tvaru, jakým jim předpisuje gramatika daného jazyka; gramaticky správné výrazy je možno podle potřeby zkracovat tzn. možno z nich jisté znaky vyloučit, popřípadě možno je i nějakým způsobem vedoucím ke zjednodušení jinak transformovat. To vše je možné jen za předpokladu, že každý zkrácený výraz se dá vždy jednoznačná převést na původní nezkrácený, gramaticky správný. Splnění tohoto požadavku zajišťují v logice pravidla o zkracování. Jde o jisté dohody (technické konvence), jež se zavazuje respektovat uživatel daného jazyka. Principy zkracování nejsou v logice jednotné (existuje řada metod zkracování). V zásadě všechny mají smysl v tom, usnadňovat zápisy, čtení a operace s logickými výrazy. Zkracování gramaticky správných výrazů budeme provádět ve shodě s těmito dohodami: (I) Má-li gramaticky správný výraz vnější závorky, možno je vynechat. Například [p ⊃q] je možno zkrátit na p ⊃q; výraz ∼ [p ⊃q] nemá vnější závorky, proto nemůže být podle bodu (Ι) zkracován. (II) .... Ve všech gramaticky správných výrazech je možno vynechávat znak konjunkce. Podle této a předchozí dohody zkratkou [p ∧ q] je pq, zkratkou [[p ∧ q] ∨ ∨, [q ∧ ∼ r]] je [pq] ∨ [q ∼ r] atd. (III)... Závorky uvnitř gramaticky správných výrazů lze vynechávat podle předností spojek. V tomto systému zkracování implikace a ekvivalence mají přednost před ostatními spojkami, disjunkce má přednost před konjunkcí a negací, konjunkce má přednost před negací. Podle tohoto systému p ∨ q ⊃ r je implikací (implikace má přednost před disjunkcí), p ∨ q ⊃ r je tedy zkratkou gramaticky správného výrazu [[p ∨ q] ⊃ r]. Podobně ∼ p ∨ p je disjunkcí (disjunkce má přednost před negací); ∼ p ∨ p je zkratkou [∼ p ∨ p], a nikoli například ∼ [p ∨ p]. Analogicky pq ∨ r ≡ ∼ p je ekvivalencí, neboť ekvivalence má přednost před všemi ostatními spojkami ve výrazu obsaženými. její levá strana je disjunkcí, neboť disjunkce má přednost před konjunkcí; pq ∨ r ≡ ∼ p je tedy zkratkou [[[p ∧ q] ∨ r] ≡ ∼ p]. (IV)... Několikanásobné konjunkce a disjunkce zkracujeme takto: ABC je zkratkou [[A ∧ B] ∧ C], A ∨ B ∨ C je zkratkou [[A ∨ B] ∨C]. Danému principu říkáme princip seskupování závorek doleva. Tak například p ∨ q ∨ r ∨ ∼ s je zkratkou [[[p ∨ q] ∨ r] ∨∼ s], p ∼ q ∨ r ∨ ps je zkratkou za [[[p ∧ ∼ q] ∨ r] ∨ [p ∧ s]].


19

Výroková logika

CVIČENÍ (Zkracování výrazů): Najděte vhodné zkratky pro tyto gramaticky správné výrazy: a)[p ∨ q] lze zkracovat na ........................................................ ................................ b)[p ∧ ∼ q] lze zkracovat na ..................................................... ................................ c)[[s ∨ p] ⊃ q] lze zkrátit na ..................................................... ................................ d)[p ∨ [q ⊃ r]] lze zkrátit na ..................................................... ................................


20

Výroková logika

VÝZNAMY V SYMBOLICKÉM JAZYCE Jazyk ustanovený v předminulé kapitole (Zavedení symbolů) je z běžného hlediska neúplný; jeho pravidla sice umožňují rozlišit gramaticky správné výrazy od zbývajících, avšak nedostává se takových pravidel, která by určila, co jednotlivé gramaticky správné výrazy znamenají. Jazyk určený pro vyjádření výrokové logiky je proto jazykem čistě formálním, jeho výrazy jsou rovněž výrazy formální. Tato okolnost ještě neznamená, že by nebylo vůbec možné dosáhnout toho, aby formální výrazy něco znamenaly. I když východiskem logických úvah je jazyk formální, máme stále po ruce možnost symbolům a výrazům jazyka nějaký význam přiznat, a v důsledku toho dosáhnout obsahuplnosti jazyka. Přiřazení významů jazykovým symbolům a výrazům formálního jazyka nazýváme interpretací toho jazyka. Pod pojmem interpretace si nesmíme představit něco na způsob doslovného překladu výrazů logiky do běžného jazyka. Interpretace může přiznávat některým symbolům třeba jen význam gramatických kategorií. I například to, že nějakému písmenu přisoudíme úlohu blíže nespecifikovaného pravdivého výroku, je interpretace. Ve výrokové logice interpretaci podléhají výrokové proměnné (výrokové symboly) a výrokové spojky. Pokud jde o první výrazy , jejich interpretace se omezuje na konstatování, že jako proměnné (tj. víceznačné symboly) mohou mít hodnotu pravda nebo nepravda. Interpretace výrokových spojek byla provedena v předchozích kapitolách, v nichž byl jednoznačně stanoven jejich význam pomocí pravdivostních tabulek. V tomto významu bude brán jazyk výrokové logiky ve všech sémantických úvahách. Pokud jde o výrokové symboly jazyka výrokové logiky , nic nemůže bránit tomu, spojovat je v daných konkrétních úvahách s detailnějšími významy. Tak je možno brát „p“ řekněme ve významu výroku „2 je prvočíslo“, písmeno „q“ ve významu výroku „9 je liché číslo“ apod. Je třeba poznamenat, že takovéto interpretace mají čistě didaktický nebo praktický význam; pro výrokovou logiku jako teorii je tento druh interpretace bezvýznamný. V některých, zejména starších matematických textech výrok tvaru :jestliže A, pak B“, bývá vyjadřován některým z těchto způsobů: A je podmínkou postačující pro B B je podmínka nutná pro A Popřípadě stručněji aby B, k tomu stačí, že A aby A, ktomu je nutné, aby B:


21

Výroková logika

CVIČENÍ (Významy v symbolickém jazyce): Nechť písmena d, s, p znamenají po řadě výroky „je doma“, „studuje“, „má před zkouškou“. Převeďte do běžného jazyka tyto formule: a)d ∼ s ⊃ ∼ p znamená.............................................. b)∼ s ∼ dp znamená.............................................. c)d [s ≡ p] znamená.............................................. d)ds ≡ p znamená.............................................. e)[s ⊃ p] [p ⊃ s] znamená..............................................


22

Výroková logika

VÝPOČET HODNOTY FORMULE Interpretace uvedená v předcházejících částech, přiznávající formulím výrokové logiky význam výroků, dává možnost formulovat tuto jednoduchou úlohu: určit pravdivostní hodnotu složeného výroku, když jsou dány pravdivostní hodnoty jeho elementárních složek. Aby¨tato úloha mohla být formulována na potřebné formální úrovni, je třeba vymezit některé důležité pojmy, především pojem udělení hodnoty proměnné. Udělení hodnoty je formální úkon, jímž proměnná (jako víceznačný symbol) je na čas, pro danou úvahu, významově „fixována“ a chápána v nějakém přísně specifikovaném významu. Pokud jde o výrokové proměnné (které mohou mít hodnoty pravda a nepravda), přichází tu v úvahu udělení hodnoty pravda, jímž získává proměnná význam výroku pravdivého, a udělení hodnoty nepravda, jímž dostává význam nepravdivého výroku. Daným udělením budeme rozumět vždy takové udělení hodnot proměnným výrazu, v němž všem proměnným výrazu jsou přiřazeny nějaké hodnoty. Tak například 101 je jedním z daných udělení hodnot proměnným výrazu p ∧ q ⊃ p ∨ r. Toto udělení přiznává abecedně prvnímu písmenu výrazu (tj. písmenu p) hodnotu 1, abecedně druhému (tj. písmenu q) hodnotu 0 a poslednímu (tj. r) hodnotu 1. Explicitně je možno toto udělení zapsat takto: p ∧ q ⊃ p ∨ r 1 0 1 1 Pro různé výpočty i úvahy je potřebné znát celkový počet možných udělení hodnot odpovídajících danému výrazu. Následující úvaha nám umožní tento počet stanovit. Obsahuje-li výraz jednu výrokovou proměnnou, existují celkem dvě udělení hodnot, a to 1 a 0. Pro p ⊃ ∼ p (obsahující jednu výrokovou proměnnou, ovšem ve dvou výskytech) máme tato udělení: p ⊃ ∼ p 1 1 0 0 Obsahuje-li výraz dvě (navzájem různé) výrokové proměnné, existují celkem 4 udělení hodnot, a to 11, 10, 01 a 00. Pro formuli p ⊃ [q ⊃ p] jsou to tato udělení: p ⊃ [q ⊃ p] 1 1 1 1 0 1 0 1 0 0 0 0 Obsahuje-li výraz tři proměnné, existuje celkem osm udělení hodnot jeho proměnným: 111, 110, 101, 100, 011, 010, 001, 000. Jak patrno zvětší-li se počet proměnných ve výraze o jednu, zdvojnásobuje se počet udělení. Pro n proměnných úhrnný počet udělení je tak 2 . 2 . . . 2 = 2n Najděme nyní hodnotu p ∨ q ⊃ r pro udělení 100. Výpočet hodnoty pro toto udělení vyjadřuje graf


23

Výroková logika

∨

[p 1

⊃

q] 0

r 0

(a) (b) (c)

1 0

Řádek (a) grafu je dané udělení hodnot. v řádku (b) figuruje hodnota p ∨ q vypočítaná z hodnot p a q na základě tabulky disjunkce. V řádku (c) je zanesena hodnota vypočtená z hodnot p ∨ q a r na základě pravdivostní tabulky implikace. Tato hodnota je hodnotou celé formule pro dané udělení. Závěr zní: p ∨ q ⊃ r nabývá pro udělení hodnot 100 hodnoty 0. Hodnotu formule pro dané udělení hodnot vypočítáváme tedy tak, že určujeme postupně (na základě pravdivostních tabulek) hodnoty jednotlivých částí výrazů, a to vždy tak, že vyjdeme od hodnot částí skladebně jednodušších a spějeme k hodnotám částí skladebně bezprostředně vyšších. Tak dojdeme až k určení hodnoty formule celé. Vypočítejme ještě hodnotu ∼ [p ∼ q] pro udělení 10 ∼

∧

[p 1

∼

q] 0

1 1 0

Formule ∼ [p ∼ q] pro udělení 10 hodnotu 0. Graf, který jsme použili při výpočtu hodnoty, je jen pomocným prostředkem, bez něhož je možno se obejít. jednotlivé nalezené hodnoty je možno vepsat přímo do jediného řádku, aniž se přitom použijí spojnice naznačující postup výpočtu, Tak například výpočet r 0

≡

∼

p 1

[∼

⊃

0 1 0 1

může být vyjádřen jednořádkově takto:


24

q] 1

Výroková logika r ≡ ∼ [∼ p ⊃ q] 0 1 0

0

1

1

1

Tento způsob zápisu nenaznačuje sice tak očividně postup výpočtu; to ovšem není na závadu, neboť tento postup je jednoznačně určen samou skladbou výrazu. Nakonec ukážeme , že popsaná procedura umožňuje to, co bylo v úvodu naznačováno: určovat hodnoty složeného výroku, když hodnoty jeho složek jsou dány. Mějme složený výrok: jestliže se nedostaví ani nedá o sobě vědět, pak o jeho žádosti se přestane uvažovat (1) Nechť situace je taková, že se nedostaví, dá o sobě vědět a o jeho žádosti se nepřestalo uvažovat. Tomu na formální úrovni odpovídá výraz [∼ p ∧ ∼ q] ⊃ r a udělení hodnot 010 jeho proměnným. Pro toto udělení má shora uvedená formule hodnotu 1; proto za popsané situace může být výrok (1) jen pravdivý.


25

Výroková logika

CVIČENÍ (Výpočet hodnoty formule): 1.Vypočítejte pravdivostní hodnoty a) p ∼ q ≡ ∼ r pro udělení 001 b) [p ⊃ r] ⊃ r pro udělení 00 2.Vyhodnoťte tyto formule pro dané udělení: a) [∼ ∼ ∼ p ⊃ ∼ q] pro udělení 01 b) [∼ p ≡ q] ∧ [∼ r ⊃ p] pro udělení 000


26

Výroková logika

PRAVDIVOSTNÍ TABULKY FORMULÍ Pravdivostní tabulkou rozumíme takovou tabulku, která udává pravdivostní hodnoty nějakého výrazu pravšechna udělení hodnot jeho proměnným. Takovými tabulkami jsou například tabulky konjunkce, negace, disjunkce a další. V této části popíšeme v obecnosti metodu konstrukce pravdivostní tabulky pro libovolné výrazy výrokové logiky. Pravdivostní tabulka je útvar mající řádky a sloupce. Řádky tabulky představují jednotlivá udělení hodnot proměnným výrazu a odpovídající výpočty, sloupce pak jednotlivě „průběh“hodnot pro daná udělení. Jeden ze sloupců tabulky je sloupcem hlavním (čili výsledným), ten obsahuje vypočtené výsledné hodnoty výrazu pro jednotlivá udělení hodnot. Tabulku můžeme začít konstruovat, jakmile známe počet jejích řádků. Těch je tolik, kolik je udělení hodnot pro daný výraz. Má-li výraz n navzájem různých proměnných, pak mu odpovídá celkem 2n udělení hodnot. Všech 2n kombinací hodnot pravda a nepravda je třeba v jistém pořadí vypsat a zanést do tabulky. Postupujeme přitom takto: Nejdříve napíšeme výraz, pro nějž konstruujeme pravdivostní tabulku (viz. obr. 1). Nato vyhledáme v tomto výraze abecedně první výrokový symbol a pod něj do sloupce (o 2n symbolech) píšeme hodnoty 1 a 0 tak, že v první polovině sloupce jsou vesměs jedničky a v druhé vesměs nuly. Je-li abecedně prvním symbolem výrazu například písmeno p, pak takový sloupec zaneseme pod každý výskyt toho písmene ve výraze (viz sloupce „p“, první a poslední, na obr. 1) Sloupce abecedně dalšího symbolu dělíme na čtvrtiny a při jejich vypisování opět střídáme jedničky a nuly tak, že v první a třetí čtvrtině jsou vesměs hodnoty 1, v druhé a čtvrté vesměs hodnoty 0 (viz sloupce „q“ na obr. 1). Sloupce dalšího výrokového symbolu dělíme na osminy a opět střídavě rozdělujeme jedničky tak, že první, třetí, pátá atd. část má hodnoty 1, druhá, čtvrtá atd. hodnoty 0. Tak pokračujeme, až jsou vypsány sloupce pro všechny výrokové symboly výrazu. Pro tabulku výrazu [p ⊃ q] ⊃ [[r ∨ ∼ q] ∧ p] tato výchozí struktura vypadá takto: Obr. 1

[p 1 1 1 1 0 0 0 0

⊃

q] 1 1 0 0 1 1 0 0

⊃

[[r 1 0 1 0 1 0 1 0

∨

∼

q] 1 1 0 0 1 1 0 0

∧

p] 1 1 1 1 0 0 0 0

Další postup konstrukce je nám už znám; výsledné hodnoty (viz. hodnoty v orámovaném sloupci na obr. 2) v jednotlivých řádcích dostáváme stejným početním postupem, který jsme si osvojili v minulé části (výpočet hodnoty formule), když jsme vypočítávali hodnotu formule pro dané udělení. konečná podoba pravdivostní tabulky pro [p ⊃ q] ⊃ [[r ∨ ∼ q] ∧ p] je na obr. 2. Pro ilustraci čtvrtý řádek indikuje, že daný výraz má pro udělení hodnot 100 hodnotu 1. Logický charakter formule je zachycen v hlavním (výsledném) sloupci. jeho hodnoty bývají nazývány průběhem hodnot formule.Ta je v mnoha ohledech významná, jak poznáme z výkladů, které budou následovat.


27

Výroková logika

Obr. 2

[p 1 1 1 1 0 0 0 0

⊃ 1 1 0 0 1 1 1 1

q] 1 1 0 0 1 1 0 0


⊃ 1 0 1 1 0 0 0 0

[[r 1 0 1 0 1 0 1 0

∨ 1 0 1 1 1 0 1 1

28

∼ 0 0 1 1 0 0 1 1

q] 1 1 0 0 1 1 0 0

∧ 1 0 1 1 0 0 0 0

p] 1 1 1 1 0 0 0 0

Výroková logika

CVIČENÍ (Pravdivostní tabulky formulí): Zkonstruujte pravdivostní tabulky pro formule a) ∼ [p ⊃ ∼ q] b) ∼ [p ∼ q] c) [p ⊃ q] ∧ [q ⊃ p]


29

Výroková logika

TAUTOLOGIE A KONTRAINDIKACE VÝROKOVÉ LOGIKY V minulém cvičení jsme narazili na výrazy. které měly ve výsledném sloupci své pravdivostní tabulky vesměs hodnoty pravda. Stejnou vlastnost mají například formule p ∨ ∼ p, [p ⊃ q] ⊃ [[q ⊃ r] ⊃ [p ⊃ r]], viz: p 1 0

∨ 1 1

∼ 0 1

p 1 0

[p 1 1 1 1 0 0 0 0

⊃ 1 1 0 0 1 1 1 1

q] 1 1 0 0 1 1 0 0

⊃ 1 1 1 1 1 1 1 1

[[q 1 1 0 0 1 1 0 0

⊃ 1 0 1 1 1 0 1 1

⊃ 1 1 1 0 1 1 1 1

r] 1 0 1 0 1 0 1 0

[p 1 1 1 1 0 0 0 0

⊃ 1 0 1 0 1 1 1 1

r]] 1 0 1 0 1 0 1 0

Výrokové výrazy, které každé udělení hodnot činí pravdivými, budeme nazývat tautologiemi (výrokové logiky). Tautologie patří mezi výrazy logicky platné. (Každá tautologie je výrazem logicky platným, ne však každý logicky platný výraz je tautologií). Že A je tautologie, budeme psát |≡ A a číst „A je tautologie“, popřípadě „A (logicky) platí“. Zkoumejme podrobněji základní rysy tautologií, zejména to, čím je určena jejich pravdivost. To, že nějaké tvrzení je pravdivé, závisí obvykle na dvou důležitých okolnostech: 1. na tom, jaké má toto tvrzení věcný obsah (čili o čem vypovídá), a 2. na tom, jakou má formu (strukturu, skladbu – tj. jakých logických obratů a vazeb bylo při jeho formulaci použito jak). Charakteristickým znakem tautologií je, že jejich pravdivostní hodnota není závislá na jejich věcném obsahu, nýbrž jen a jen na tom, jaká je jejich logická forma, tj. jaké logické výrazy se v nich vyskytují a v jakých formálních vztazích v nich vystupují. ukažme si to na velmi prostém příkladě. Výrok „dnes je neděle nebo dnes není neděle“ je nade vší pochybnost pravdivý (je to případ tautologie p ∨ ∼ p). Pro pravdivost tohoto výroku je zcela irelevantní okolnost, že se v něm vyskytuje elementární výrok „dnes je neděle“; na tomto výroku totiž pravdivost celého složeného výroku vůbec nezávisí. Je to dobře patrné z toho, že výrok „dnes je neděle nebo dnes není neděle“ zůstává tautologií při každém zastoupení elementárního výroku „dnes je neděle“ jiným, viz „je doma nebo není doma“, „prší nebo neprší, „x = y nebo x ≠ y“ atd. Vylučme z hořejších výroků to, co je pro jejich pravdivost nepodstatné; dostaneme takovýto skelet: . . . . . ., nebo ne- . . . . . ., Vzhledem k tomu, že daný skelet je složen jen z logických elementů a že podobný skelet odpovídá každé tautologií, a koneckonců že pravdivost tautologie je tak jen logicky podmíněna, nazýváme tautologie logicky pravdivými výroky. Analogické výrazy, ale s protikladnými hodnotami ve výsledném sloupci, jsou výroky, jež mají v hlavním sloupci svých pravdivostních tabulek vesměs hodnoty nepravda. Takovými


30

Výroková logika výrazy jsou například formule p ∧ ∼ p, [p ⊃ q] ∧ [p ∧ ∼ p], viz: p p ∧ ∼ 1 0 0 1 0 0 1 0 [p

⊃

q]

∧

[p

∧

∼

q]

Tyto výrazy nazýváme kontradikcemi. Kontradikce jsou tedy výrazy (výrokové logiky), které každé udělení hodnot činí nepravdivými. Co bylo řečeno o tautologiích, platí v obráceném smyslu i o kontradikcích. Nepravdivost kontradikce je podmíněna jen a jen logicky, tzn. je důsledkem její logické skladby, nikoli jejich faktuálních složek (tj. elementárních výroků). To, co kontradikce věcně vypovídá, je proto irelevantní pro její nepravdivost. Elementární výroky se v ní vyskytují nepodstatně, tzn. jejich nahrazení jinými nemůže změnit její nepravdivost. To nás vede opět k tomu, abychom kontradikce nazývali výroky logicky nepravdivými. Pojem pravdivosti (nepravdivosti) logické dobře vynikne na pozadí pojmu pravdivosti (nepravdivosti) faktuální. Výraz, který je pravdivý, ale není pravdivý logicky, je pravdivý faktuálně. Obdobně výraz, který je nepravdivý, ale není nepravdivý logicky, je nepravdivý faktuálně. Pravdivost faktuálně pravdivého výroku je podmíněna nejen logickou skladbou výroku, nýbrž i věcným obsahem elementárních složek výroku. Totéž platí i o faktuální nepravdivosti. Ilustrujeme faktuální pravdivost. výrok „jestliže dnes je neděle, pak zítra je pondělí“ je faktuálně pravdivý. Jeho pravdivost závisí podstatně na jeho elementárních složkách, totiž na výrocích „dnes je neděle“ a „zítra je pondělí“. Nahraďme výrok „dnes je neděle“ v daném složeném výroku výrokem „dnes je v sobotu“; výsledný výrok „jestliže dnes je sobota, pak zítra je pondělí“ je nepravdivý. to dokumentuje, že elementární složky se v rozebíraném složeném výroku vyskytují podstatně, tzn. že jeho pravdivost významně podmiňují. Tyto úvahy mají přímý vztah k informačnímu obsahu výroků. Vyskytují-li se elementární složky v tautologii nepodstatně, nemohou určovat její obsah;její obsah musí být tedy (věcně) nulový. Vskutku, pomocí tautologie nelze zprostředkovat nijakou faktuální informaci, tautologie jsou faktuálně prázdné výrazy. Tak vezměme jako případ tautologie [p ⊃ ∼ q] ⊃ [q ⊃ ∼ p] souvětí „[jestliže (jestliže dostal upomínku, pak knihu (ještě) nevrátil), pak(jestliže knihu vrátil, pak nedostal upomínku)]“; toto souvětí nemá žádný věcný obsah, nevypovídá nic o obdržení upomínky ani vrácení knihy, ani dokonce o vztahu mezi vracením knih a posíláním upomínek. tautologie (jako tato) mají však jistý logický obsah; vyjadřují totiž jistou logickou zákonitost. Této logické zákonitosti lze využít při vyvozování pravdivých výroků z výroků, jejichž pravdivost už byla potvrzena. Toto téma však už nespadá do rámce této kapitoly. Jako tautologie vyjadřují logické zákonitosti, kontradikce vyjadřuje logické absurdity. Jejich význam spočívá v tom, že představují pomocné prostředky při odhalování logických sporů.


31

Výroková logika

CVIČENÍ(Tautologie a kontradikce výrokové logiky): Vyhledejte mezi danými výrazy tautologie a kontradikce. použijte metody konstrukce pravdivostní tabulky. a)∼[p ∼ p] b) [p ⊃ ∼ p] ⊃ p c) [∼p ⊃ p] ⊃ p d) [p ⊃ ∼ q] ⊃ [∼ q ⊃ ∼ p] e) [p ≡ ∼ p]


32

Výroková logika


33

Výroková logika. Základy algoritmizace, FEI 1

Recommend Documents