Diskrétní struktury 1 - Logikabelohlavek.inf.upol.cz/vyuka/diskretni-struktury-1-logika.pdf ·...

Diskrétní struktury 1Logika

Radim Bělohlávek

KATEDRA INFORMATIKYUNIVERZITA PALACKÉHO V OLOMOUCI

http://www.inf.upol.cz



Co se naučíme

– co je logika– výroky, pravdivost výroků, logické spojky, kvantifikátory– výroková logika, formule logiky, vyplývání– logické (booleovské) funkce, vyjadřování logických spojek jinými– normální formy– axiomatický systém logiky (jen nahlédneme)– logické paradoxy, zajímavosti z logiky a z historie logiky

Bělohlávek (Univerzita Palackého v Olomouci) Diskrétní struktury 1 2020 1 / 76


UpozorněníTyto slajdy jsou jen doprovodným materiálem k učebnímu textu

[DS1] R. Bělohlávek, Diskrétní struktury 1, Olomouc, 2020.

Slajdy nejsou plnohodnotným studijním materiálem.Některé části učebního textu na slajdech probrány nejsou.Na učební text se odkazujeme [DS1].



Co je logika

– věda o správném usuzování– jde o formu, ne o obsah

Prší.Jestliže prší, pak jsou silnice mokré.Silnice jsou mokré.Mám hlad.Jestliže mám hlad, kručí mi v břiše.Kručí mi v břiše.

úsudky s různým obsahem, ale stejnou formou:

ϕϕ→ ψ

ψ



– proto: formální logika, popř. symbolická logika– moderní logika používá matematické metody– budeme se zabývat klasickou logikou:

– dvě pravdivostní hodnoty (pravda, nepravda)– klasické spojky („a“, „nebo“, „jestliže . . . pak . . . “, . . . ne . . . )

– existují neklasické logiky– modální: spojky „je možné, že . . . “, „je nutné, že“– temporální: výroky závislé na čase– fuzzy logika: více pravdivostních hodnot, např. 0.5 (je částečně pravda)



Proč logika

– obecný význam:– vede k přesnosti a srozumitelnosti– pevný základ pro ostatní obory

– význam pro informatiku:– formální povaha logiky, syntax vs. sémantika ≈ způsob práce v informatice, počítač rozumí

jen přesně popsaným informacím– základ pro různé oblasti informatiky, např.

automatické dokazování (odvozování z předpokladů, jazyk Prolog),umělá inteligence (reprezentace znalostí, přibližné odvozování, expertní systémy),databáze (relační databáze, dotazovací jazyky),logická analýza dat

– kromě toho řada „menších důvodů“, např. vyhodnocování podmíněných výrazůprogramovacích jazyků se provádí podle pravidel logiky



VýrokyVýrokem je (intuitivně) tvrzení, u kterého má smysl uvažovat o jeho pravdivosti.

Výroky jsou:Prší.Byl jsem v obchodě a koupil jsem si knihu.Když prší, jsou mokré silnice.2 + 2 = 4 a 3 < 100.2 + 2 = 6.

Výroky nejsou:Kniha v obchodě.2 + 2Ať je pěkné počasí.



Logické spojkyLogická spojka je (intuitivně) jazykový výraz, který umožňuje z jednodušších výroků tvořitsložitější.

Příklady logických spojek:„. . . a . . . “, „. . . nebo . . . “, „jestliže . . . , pak . . . “,„. . . , právě když . . . “, „ne . . . “ (tj. „není pravda, že . . . “).

– Z výroků „2+2=4“ a „Prší.“ vytvoříme pomocí spojky „a“ výrok „2+2=4 a Prší.“– Z výroku „Prší.“ vytvoříme pomocí spojky „ne“ (tj. „není pravda, že . . . “) výrok„Neprší.“ (tj. „Není pravda, že prší.“).

– Z výroků „Prší.“ a „Silnice jsou mokré.“ vytvoříme pomocí spojky „jestliže . . . , pak. . . “ výrok „Jestliže prší, pak jsou silnice mokré.“



Všimněme si:

– pojem spojka používáme v logice v širším významu, než je běžné (např. „jestliže . . . ,pak . . . “)

– výše uvedené jsou takzvané klasické spojky– existují neklasické („je možné, že . . . “, „věří se, že . . . “), viz [DS1]

Označení základních spojek klasické logiky:

V1 ∧ V2 označuje „V1 a V2“V1 ∨ V2 označuje „V1 nebo V2“V1 → V2 označuje „jestliže V1, pak V2“V1 ↔ V2 označuje„V1, právě když V2“¬V označuje „není pravda, že V “



Pravdivostní hodnota výroku

– některé výroky jsou pravdivé („2 + 2 = 4“),některé jsou nepravdivé („Jaromír Jágr je prezidentem ČR.“)

– je-li výrok V pravdivý, resp. nepravdivý, říkáme, že má pravdivostní hodnotu „pravda“,resp. „nepravda“, a píšeme

||V || = 1, resp. ||V || = 0,

– pravdivostní hodnota výroku V se značí ||V ||



Jak určit pravdivostní hodnotu výroku?

– výrok je „Prší a venkovní teplota je menší než 15◦C.“– vznikl použitím spojky „a“ na výroky „Prší“ a „Venkovní teplota je menší než 15◦C.“– jeho pravdivostní hodnota závisí na

– významu spojky „a“– pravdivostních hodnotách výroků „Prší“ a „Venkovní teplota je menší než 15◦C.“

– uvedený výrok je pravdivý, právě když je pravdivý první výrok i druhý výrok– jaké je za tím obecné pravidlo?



Obecný pohled:

– výrok má tvarV1 ∧ V2

kde ∧ je symbol spojky „a“– pravdivostní hodnotu ||V1 ∧ V2|| „spočítáme“ z pravdivostních hodnot ||V1|| a ||V2||

výroků V1 a V2 pomocí významu spojky „a“– význam spojky „a“ je dán tabulkou:

∧ 0 10 0 01 0 1

– je-li např. ||V1|| = 1 (V1 je pravdivý) a ||V2|| = 0 (V2 je nepravdivý), je dle tabulky||V1 ∧ V2|| = 0

– je-li ||V1|| = 1 a ||V2|| = 1 (oba výroky pravdivé), je dle tabulky ||V1 ∧ V2|| = 1– analogicky postupujeme v případě ostatních spojek



Zbývá tedy zjistit pravdivostní hodnoty ||Vi||. Jak? Jsou dvě možnosti:

1. Vi neobsahuje logické spojky (je to atomický výrok)Například Vi je „Prší.“Hodnota ||Vi|| je pak dána „zvenčí“, tj. zjistíme, jestli prší, popř. se někoho zeptáme.Určíme ji tedy podle externího zdroje e (stojí mimo logiku).e určuje pravdivostní hodnoty atomických výroků, proto taky píšeme

||V ||e místo ||V ||

2. Vi obsahuje logické spojky (je to složený výrok)například Vi je „Prší a 2 + 2 = 4.“Hodnota ||Vi|| se pak určí podobně jako na předchozím slajdu.



Ještě k tabulce spojky ∧ (později vysvětlíme znovu):

– tabulka∧ 0 10 0 01 0 1

popisuje tzv. pravdivostní funkci spojky ∧ (také: logická nebo booleovská funkce)– tato funkce se značí ∧·, jejími argumenty jsou 0 a 1 a podle tabulky pro ni platí:

0 ∧· 0 = 0, 0 ∧· 1 = 0, 1 ∧· 0 = 0, 1 ∧· 1 = 1

– máme tedy– ∧ · · · symbol spojky (syntax)– ∧· · · · význam spojky (sémantika)

– někdy píšeme pro jednoduchost ∧ místo ∧·, ale přísně vzato je třeba rozlišovat– a další spojky?



název zápis v přirozeném symbol pravdivostní tabulkajazyce funkce pravd. funkce

negace “ne” ¬ ¬·a ¬·a0 11 0

konjunkce “a” ∧ ∧·∧· 0 10 0 01 0 1

disjunkce “nebo” ∨ ∨·∨· 0 10 0 11 1 1

implikace “jestliže . . . , pak . . . ” → →·→· 0 10 1 11 0 1

ekvivalence “. . . , právě když . . . ” ↔ ↔·↔· 0 10 1 01 0 1



PříkladUrčete pravdivostní hodnotu výroku „2 + 2 = 5 nebo číslo 10 je dělitelné číslem 6.“

Jde o výrok V tvaruV1 ∨ V2

Zřejmě je (to víme z „externího zdroje“ e)

||V1|| = ||„2 + 2 = 5“|| = 0 a ||V2|| = ||„číslo 10 je dělitelné číslem 6“|| = 0

a tedy

||V || = ||„2 + 2 = 5 nebo číslo 10 je dělitelné číslem 6.“|| == ||V1 ∨ V2|| = ||V1|| ∨· ||V2|| = 0 ∨· 0 = 0.

Daný výrok je tedy nepravdivý.

K čemu takhle? Odpověď je přeci zřejmá? Ano, ale výše je u postup, jak ji mechanickyodvodit.



UzávorkováníU složených výroků používáme kvůli jednoznačnosti závorky.

Uvažujme2 · 3 = 5 a 2 + 2 = 5 nebo 2 + 2 = 4

Není jasné, jestli myslíme

(2 · 3 = 5 a 2 + 2 = 5) nebo 2 + 2 = 4”

nebo2 · 3 = 5 a (2 + 2 = 5 nebo 2 + 2 = 4)”

Při prvním uzávorkování dostaneme pravdivý výrok, zatímco při druhém uzávorkovánídostaneme výrok nepravdivý.

Závorky používáme i při symbolickém zápisu. Píšeme např. V1 ∧ (V2 ∨ V3), (V1 ∧ V2) ∨ V3.



PříkladUrčete pravdivostní hodnotu výroku:“(2 + 2 = 4 a číslo 10 je dělitelné číslem 6), právě když není pravda, že Čína jenejlidnatější stát světa”, víme-li, že “Čína je nejlidnatější stát světa” je pravdivý výrok.

Tři atomické výroky, V1, V2 a V3:“2 + 2 = 4”, “číslo 10 je dělitelné číslem 6” a “Čína je nejlidnatější stát světa.”

Víme, že ||V1|| = 1, ||V2|| = 0, ||V3|| = 1.

Symbolická podoba zadaného výroku je

(V1 ∧ V2)↔ ¬V3.

Pravdivostní hodnota je

||(V1 ∧ V2)↔ ¬V3|| = ||V1 ∧ V2|| ↔· ||¬V3|| =(||V1|| ∧· ||V2||)↔· (¬·||V3||) = (1 ∧· 0)↔· (¬·1) = 0↔· 0 = 1,

tedy výrok je pravdivý.Bělohlávek (Univerzita Palackého v Olomouci) Diskrétní struktury 1 2020 17 / 76


Proměnné a výroky s kvantifikátory

Číslo x je větší nebo rovno 3.2 + y = 4.Jestliže je x dělitelné deseti, pak je x sudé.x+ y ≥ z.

Nejsou to výroky. Obsahují proměnné.

Dosazením číselných hodnot za proměnné vzniknou výroky. Pokud dosadíme 1 za x, 2 zay, 103 za z, dostaneme výroky

Číslo 1 je větší nebo rovno 3.2 + 2 = 4.Jestliže je 1 dělitelné deseti, pak je 1 sudé.1 + 2 ≥ 103.

První a čtvrtý výrok je nepravdivý, druhý a třetí je pravdivý.



Výroky s proměnnými se nazývají výrokové formy.

V (x) označuje výrokovou formu s proměnnou x, např. „Číslo x je větší nebo rovno 3.“.V (1) označuje V (x) po dosazení 1 za x, tedy např. „Číslo 1 je větší nebo rovno 3.“

Podobně „x+ y ≥ z“ označíme např. U(x, y, z).

K proměnné x musíme určit obor jejích hodnot Dx. Např.Dx = {0, 1,−1, 2,−2, 3,−3, . . . }.



Obecný kvantifikátor s proměnnou x je výraz„Pro každý x platí, že . . . “, symbolicky (∀x) . . .

Tedy„Pro každý x platí, že x je větší nebo rovno 1“ zapíšeme (∀x) (x ≥ 1).

Tento výraz je výrokem.

Existenční kvantifikátor s proměnnou x je výraz„Existuje x tak, že platí . . . “, symbolicky (∃x). . .

Tedy„Existuje x tak, že x je větší nebo rovno 1“ zapíšeme (∃x) (x ≥ 1).

Ten výraz je také výrokem.



Pravdivost výroků s kvantifikátoryJe dána výroková forma V (x), kde x je proměnná s oborem hodnot Dx.Jak definovat pravdivostní hodnoty (∀x)V (x) a (∃x)V (x)?

||(∀x)V (x)|| ={

1 pokud pro každé m ∈ Dx je ||V (m)|| = 10 jinak.

Tedy: (∀x)V (x) je pravdivý, pokud pro každou hodnotu m z oboru Dx je výrok V (m),který vznikne dosazením m do výrokové formy V (x), pravdivý.

||(∃x)V (x)|| ={

1 pokud aspoň pro jedno m ∈ Dx je ||V (m)|| = 10 jinak.

Tedy: (∃x)V (x) je pravdivý, pokud pro alespoň jednu hodnotu m z oboru Dx je výrokV (m), který vznikne dosazením m do výrokové formy V (x), pravdivý.



PříkladJe dán výrok „Pro každé x platí, že jestliže x je dělitelné 6, pak x je dělitelné 3.“ aDx = {1, 2, 3, 4, . . . }. Určete pravdivostní hodnotu daného výroku.

Výrok má tvar (∀x)(V (x)), kde V (x) je „Jestliže x je dělitelné 6, pak x je dělitelné 3.“

Podle pravidla výše je ||(∀x)(V (x))|| = 1, p.k. pro každé číslo m z Dx je ||V (m)|| = 1.

V (m) je V1(m)→ V2(m), kde V1(m) je „m je dělitelné 6“, V2(m) je „m je dělitelné 3“.

Je zřejmé, že ||V1(m)→ V2(m)|| = 1, tj. že ||V (m)|| = 1. Proč?:

(a) pro m dělitelná 6 je ||V1(m)→ V2(m)|| = ||V1(m)|| →· ||V2(m)|| = 1→· 1 = 1;

(b) pro m nedělitelná 6 je||V1(m)→ V2(m)|| = ||V1(m)|| →· ||V2(m)|| = 0→· ||V2(m)|| = 1).

Proto je ||(∀x)V (x)|| = ||(∀x)(V1(x)→ V2(x))|| = 1.



PříkladJe dán výrok „Existuje x tak, že pro každé y platí, že x ≤ y“. Dx = Dy = {1, 2, 3, 4, . . . }.

Výrok je pravdivý, viz [DS1].

Co když Dx = Dy = {. . . ,−2− 1− 0, 1, 2, . . . }?



ZkratkaKvantifikátory se někdy objevují v následující podobě.

„Pro každé liché x platí, že x2 − 1 je sudé.“ „Existuje liché x tak, že x2 − 2 jeprvočíslo.“,

obecně tedy:„Pro každé x splňující P (x) platí V (x).“ „Existuje x splňující P (x) tak, že V (x).“

Tato tvrzení jsou zkratkou za„Pro každé x platí, že jestliže P (x), pak V (x).“ „Existuje x tak, že P (x) a V (x).“

u výroku výše tedy„Pro každé x platí, že jestliže x je liché, pak x2 − 1 je sudé.“ „Existuje x tak, želiché x tak, že x2 − 2 je prvočíslo.“



Shrnutí

– ukázali jsme si základní pojmy a postupy logiky, zejm.– zejména výrok, logická spojka,– prvadivostní funkce spojek,– pravdivost výroku,– kvantifikátory

– většinu pojmů jsme definovali jen intuitivně, nepřesně– to někdy stačí, nepřesnost ale může vést k problémům– v dalším se proto seznámíme s úvodem do (formální) výrokové logiky



Odbočka: paradoxyExistuje velké množství tzv. logických paradoxů, některé plynou z nepřesného zacházenís jazykem a ukazují potřebu formálního systému logiky.

Paradox lháře: Člověk C říká: „Lžu“. Mluví pravdu?

Jiné ukazují např. na meze klasické logiky.

Paradox hromady: 1 je malé přirozené číslo. Je-li n malé, je i n+ 1 malé. Tedy každépřirozené číslo je malé.

Vrátíme se k němu později.



ZÁKLADY VÝROKOVÉ LOGIKY



Výroková logika

– definovat výroky, pravdivost apod. intuitivně nestačí

– přirozený jazyk je bohatý a intuitivní přístup vede k logickým sporům (p. lháře)

– možné řešení: pojmy výrok, pravdivost apod. definovat přesně, formálně

– výroková logika je nejjednodušším formálním systémem logiky



Jazyk a formule výrokové logiky

– výroková logika (VL) nepracuje se skutečnými výroky, ale s formami (tvary) výroků

– ty se nazývají formule

– jsou to přesně definované řetězce symbolů, např. (p ∧ ¬q), (p→ (q ∧ r)), (p ∧ r) ∨ q

– výrok vznikne z formule dosazením výroků za výrokové symboly p, q, r, . . .

– z formule (p→ (q ∧ r)) vznikne výrok„Jestliže prší, pak jsou silnice mokré a hrozí nebezpečí smyku.“,

– práce s formulemi = soustředíme se na formu, odhlížíme od obsahu

– symboly, ze kterých sestávají formule tvoří jazyk VL



Definice Jazyk výrokové logiky se skládá z– výrokových symbolů p, q, r, . . . , popř. s indexy, p1, p2; je jich neomezeně mnoho;– symbolů výrokových spojek:¬ (negace), →(implikace), popř. dále ∧ (konjunkce), ∨ (disjunkce), ↔ (ekvivalence);

– pomocných symbolů (, ), [, ], atd. (různé druhy závorek).



Definice Formule daného jazyka výrokové logiky je definována následovně:1. každý výrokový symbol p je formule (tzv. atomická formule);2. jsou-li ϕ a ψ formule, jsou i výrazy

¬ϕ,(ϕ ∧ ψ),(ϕ ∨ ψ),(ϕ→ ψ),(ϕ↔ ψ)

formule (tzv. složené formule).

Definice je tzv. induktivní.

Formulemi jsou: p, q1, ¬p, (p→ q), ((p ∧ r) ∨ p), (¬p→ (q ∧ ¬r)).

Formulemi nejsou řetězce: ∧p, p ∧ ∨p, pp→ (p∧)), atd.



Konvence o vynechávání závorek

– vnější závorky místo (p→ q) jen p→ q

– priority spojek od největší po nejmenší: ¬, ∧, ∨, →, ↔

místo (p ∧ (q ∧ r)) jen p ∧ (q ∧ r),místo (p→ ((p ∧ q) ∨ r)) jen p→ p ∧ q ∨ r



Pravdivostní ohodnoceníFormule jsou syntaktické objekty, samy o sobě nemají pravdivostní hodnotu, význam.Proto musíme definovat sémantiku VL. Základní sémantický pojem je následující:

Definice (Pravdivostní) ohodnocení je libovolné zobrazení e výrokových symbolů danéhojazyka do množiny {0, 1}.

– e tedy přiřazuje každému symbolu p hodnotu 0 (nepravda) nebo 1 (pravda).– význam ohodnocení e:

výrokové symboly označují atomické výrokye(p) = 1 znamená, že atomický výrok označený symbolem p je pravdivýe(p) = 0 znamená, že atomický výrok označený symbolem p je nepravdivý.



Pravdivostní hodnota formuleDefinice Pravdivostní hodnota formule ϕ při daném ohodnocení e, označujeme ji ‖ϕ‖e, jedefinována následovně:– Je-li ϕ výrokovým symbolem p, pak

‖p‖e = e(p).– Je-li ϕ složná formule, tj. jednoho z tvarů ¬ψ, ψ ∧ θ, ψ ∨ θ, ψ → θ, ψ ↔ θ, pak

‖¬ψ‖e = ¬·‖ψ‖e,‖ψ ∧ θ‖e = ‖ψ‖e ∧· ‖θ‖e,‖ψ ∨ θ‖e = ‖ψ‖e ∨· ‖θ‖e,‖ψ → θ‖e = ‖ψ‖e →· ‖θ‖e,‖ψ ↔ θ‖e = ‖ψ‖e ↔· ‖θ‖e,

kde ¬·, ∧·, ∨·, →·, ↔· jsou pravdivostní funkce logických spojek z výše uvedenétabulky.

Definice je induktivní, „kopíruje“ definici formule.



– ‖ϕ‖e = 1 (‖ϕ‖e = 0) . . . formule ϕ je při ohodnocení e pravdivá (nepravdivá)

– důležité:– otázka „je formule ϕ pravdivá?“ nemá smysl– teprve otázka „je formule ϕ pravdivá při daném e?“ má smysl

– alternativní definice ‖ϕ‖e (slovně):

‖¬ψ‖e ={

1 pokud ‖ψ‖e = 0,0 jinak,

‖ψ ∧ θ‖e ={

1 pokud ‖ψ‖e = 1 a ‖θ‖e = 1,0 jinak,

‖ψ ∨ θ‖e ={

1 pokud ‖ψ‖e = 1 nebo ‖θ‖e = 1,0 jinak,

‖ψ → θ‖e ={

1 pokud ‖ψ‖e = 0 nebo ‖θ‖e = 1,0 jinak,

‖ψ ↔ θ‖e ={

1 pokud ‖ψ‖e = ‖θ‖e,0 jinak.



PříkladJakou pravdivostní hodnotu má formule p ∨ ¬q při ohodnocení e?

1. e je dáno takto: e(p) = 0, e(q) = 0. Pak‖p ∨ ¬q‖e = ‖p‖e ∨· ‖¬q‖e = ‖p‖e ∨· ¬·‖q‖e = 0 ∨· ¬·0 = 0 ∨· 1 = 1

2. e je dáno takto: e(p) = 0, e(q) = 1. Pak‖p ∨ ¬q‖e = ‖p‖e ∨· ‖¬q‖e = ‖p‖e ∨· ¬·‖q‖e = 0 ∨· ¬·1 = 0 ∨· 0 = 0.



Tautologie, sémantické vyplýváníDefinice Formule se nazývá– tautologie, je-li při každém ohodnocení pravdivá,– kontradikce, je-li při každém ohodnocení nepravdivá,– splnitelná, je-li při aspoň jednom ohodnocení pravdivá.

Formule ϕ sémanticky vyplývá z množiny T formulí, označujeme

T |= ϕ,

je-li ϕ pravdivá při každém ohodnocení, při kterém jsou pravdivé všechny formule z T .



Příklad

1. Formule p ∨ ¬p i p→ (p ∨ q) jsou tautologie.

2. Formule p ∧ ¬p i p↔ ¬p jsou kontradikce.

3. Formule p→ ¬p je splnitelná, ale není to ani tautologie, ani kontradikce.

4. Formule p→ q sémanticky vyplývá z množiny formulí T = {p→ r,¬q → ¬r}.



Tabulková metoda

– jak zjistit a zapsat pravdivostní hodnoty formule při všech možných ohodnoceních

– sloupce ≈ výrokové symboly p1, p2, . . . , pn a jeden sloupec pro formuli ϕ(p1, . . . , pn)řádky ≈ jednotlivá pravdivostní ohodnocení

Tabulka (nebo pravdivostní tabulka) pro formuli (p→ q) ∧ (p→ r) je

p q r (p → q) ∧ (p → r)0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 01 0 1 01 1 0 01 1 1 1

Tabulka popisuje tzv. pravdivostní funkci formule (p→ q) ∧ (p→ r).



– počet řádků = počet možných přiřazení 0 a 1 symbolům p1, . . . , pn ve formuli ϕ

– tento počet je 2n

– v řádku odpovídajícím ohodnocení e jsou hodnoty: e(p1), . . . , e(pn), ‖ϕ‖e– předchozí tabulka: 3 výrokové symboly p, q, r, tabulka má tedy 23 = 8 řádků

– drobná nepřesnost: u tabulkové metody nepracujeme s „celými“ ohodnoceními e, alejen s „částmi ohodnocení“, tj. s hodnotami ohodnocení e pro p1, . . . , pn;to můžeme, protože hodnota ‖ϕ(p1, . . . , pn)‖e závisí jen na e(p1), . . . , e(pn); viz [DS1]

– zřejmě platí: ϕ je– tautologie, právě když ve sloupci odpovídajícím formuli ϕ jsou samé 1;– kontradikce, právě když ve sloupci odpovídajícím formuli ϕ jsou samé 0;– splnitelná, právě když ve sloupci odpovídajícím formuli ϕ je aspoň jedna 1.



Vybrané tautologie (ověřte tabulkovou metodou)

ϕ ∨ ¬ϕ (zákon vyloučeného třetího)ϕ→ ϕ

DOPLNIT



– Lze pro více formulí. Tabulka pro formule ¬¬p, (¬q → ¬p) a q:

p q ¬¬p (¬q → ¬p) q

0 0 0 1 00 1 0 1 11 0 1 0 01 1 1 1 1

– Zjistit, zda {ϕ1, . . . , ϕm} |= ϕ, tj. formule ϕ sémanticky plyne z formulí ϕ1, . . . , ϕm:právě když v každém řádku, kde mají ϕ1, . . . , ϕm hodnotu 1, má i ϕ hodnotu 1.

– Např. výše vidíme, že{¬¬p, (¬q → ¬p)} |= q,

ale{¬q → ¬p), q} 6|= ¬¬p,

neboť ve druhém řádku mají (¬q → ¬p) a q hodnotu 1, ale ¬¬p tam má 0.



(Sémanticky) ekvivalentní formuleDefinice Formule ϕ a ψ se nazývají (sémanticky) ekvivalentní, značíme ϕ ≡ ψ, právě kdyžpro každé ohodnocení e je ‖ϕ‖e = ‖ψ‖e.

Věta Formule ϕ a ψ jsou ekvivalentní, právě když ϕ |= ψ a ψ |= ϕ.Důkaz Plyne přímo z definice ≡ a |=.

Příklad Ukažte, že (a) ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ) a že (b) ϕ→ ψ ≡ ¬ϕ ∨ ψ.Ověříme tabulkou:

ϕ ψ ϕ ∨ ψ ¬(¬ϕ ∧ ¬ψ) ϕ→ ψ ¬ϕ ∨ ψ0 0 0 0 1 10 1 1 1 1 11 0 1 1 0 01 1 1 1 1 1

(a): 3. a 4. sloupec mají stejné hodnoty;(b): 5. a 6. sloupec mají stejné hodnoty.



Důležité dvojice ekvivalentních formulíϕ ∧ ψ ≡ ψ ∧ ϕ ψ ∨ ϕ ≡ ϕ ∨ ψ (komutativita)

ϕ ∧ (ψ ∧ θ) ≡ (ϕ ∧ ψ) ∧ θ ϕ ∨ (ψ ∨ θ) ≡ (ϕ ∨ ψ) ∨ θ (asociativita)ϕ ∧ (ψ ∨ θ) ≡ (ϕ ∧ ψ) ∨ (ϕ ∧ θ) ϕ ∨ (ψ ∧ θ) ≡ (ϕ ∨ ψ) ∧ (ϕ ∨ θ) (distributivita)

ϕ ≡ ¬¬ϕ (zákon dvojí negace)¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ (De Morganovy zákony)ϕ→ ψ ≡ ¬ϕ ∨ ψ ϕ→ ψ ≡ ¬(ϕ ∧ ¬ψ)ϕ→ ψ ≡ ¬ψ → ¬ϕ (obměněná implikace)



Obměněná a obrácená implikace

Pro formuli ϕ→ ψ se často uvažují následující formule:¬ψ → ¬ϕ (obměněná implikace)ψ → ϕ (obrácená implikace)

Jak ukazuje následující tabulka, ¬ψ → ¬ϕ je ekvivalentní s ϕ→ ψ, ale ψ → ϕ ne.

ϕ ψ ϕ→ ψ ¬ψ → ¬ϕ ψ → ϕ

0 0 1 1 10 1 1 1 01 0 0 0 11 1 1 1 1



Obměněná implikace: použití

Máme-li dokázat tvrzení ve tvaru ϕ→ ψ, můžeme místo toho dokázat ¬ψ → ¬ϕ, cožmůže být snazší.

PříkladDOPLNIT



Booleovské funkceDefinice Booleovská funkce s n argumenty je libovolná funkce f , která každé uspořádanén-tici hodnot 0 nebo 1 přiřadí hodnotu 0 nebo 1, tedy libovolná

f : {0, 1}n → {0, 1}.

– B. funkci f s n argumenty lze zapsat tabulkou podobně jako u tabulkové metody.Zde jsou tabulky binárních b. funkcí f a g:

x1 x2 f

0 0 00 1 11 0 11 1 1

x1 x2 g

0 0 00 1 11 0 11 1 0

– f je shodná s ∨· (pravdivostní funkce spojky ∨).g je nová pravdivostní funkce (odpovídá spojce „buď . . . , nebo . . . “).



– Každou booleovskou funkci 2 proměnných můžeme považovat za pravdivostní funkcilogické spojky se dvěma argumenty.

– Tedy spojky ∧, ∨, → a ↔ jen některé z logických spojek se dvěma argumety (vizfunkce g výše).

– Kolik je ale booleovských funkcí s n argumenty, tj. kolik je různých logických spojek sn argumenty?

Věta Existuje právě 2(2n) booleovských funkcí s n argumenty.

Důkaz Funkcí je tolik, kolika způsoby lze vyplnit příslušnou tabulku.Protože funkce mají n argumentů, má tabulka 2n řádků.V každém řádku je jedno volné místo pro hodnotu funkce, a tu můžeme vyplnit libovolnýmzpůsobem (napsat tam 0 nebo 1).Protože volných míst je 2n, lze je hodnotami 0 nebo 1 vyplnit 2(2n) způsoby.



Všechny unární (n = 1) booleovské funkce:

Dle Věty jich je 2(2n) = 2(21) = 22 = 4. Zde jsou:

x1 f1

0 01 0

x1 f2

0 01 1

x1 f3

0 11 0

x1 f4

0 11 1

f1 . . . nepravda, f2 . . . identita, f3 . . . negace, f4 . . . pravda



Všechny binární (n = 2) booleovské funkce:

Dle Věty jich je 2(2n) = 2(22) = 24 = 16. Zde jsou:

x1 x2 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

všimněme si:

– f2, f8, f10 a f14 jsou po řadě pravdivostní funkce spojek ∧, ∨, ↔ a →.– Funkce f7 je pravdivostní funkce výše zmíněné spojky „buď . . . , anebo . . . “



Booleovské funkce vytvořené formulemi

– Každá formule ϕ(p1, . . . , pn) vytvoří (indukuje) booleovskou funkci fϕ s n argumenty.Je to právě funkce, jejíž tabulku získáme vytvořením tabulky pro formuli ϕ.

– Pro formuli (p→ q) ∧ (q → r) je f(p→q)∧(q→r) znázorněna v tabulce

p q r f(p→q)∧(p→r)0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 01 0 1 01 1 0 01 1 1 1

– Platí i naopak: Ke každé booleovské funkci f s n argumenty existuje formule ϕ taková,že tato formule indukuje právě funkci f , tj. f = fϕ. Dokonce k tomu stačí spojky ¬, ∧a ∨. Ukážeme nyní.



Úplné disjunktivní a konjunktivní normální formyDefinice Nechť V je množina výrokových symbolů. Pak– literál je libovolný výrokový symbol z V nebo jeho negace;– úplná elementární konjunkce (ÚEK) je konjunkce literálů, kde se každý symbol z V

vyskytuje právě v jednom literálu;– úplná elementární disjunkce (ÚED) je disjunkce literálů, kde se každý symbol z Vvyskytuje právě v jednom literálu;

– úplná konjunktivní normální forma (ÚKNF) je konjunkce úplných el. disjunkcí nad V ;– úplná disjunktivní normální forma (ÚDNF) je disjunkce úplných el. konjunkcí nad V .

Význam:ÚDNF a ÚKNF = standardizované tvary formulí



Příklad Pro V = {p, q, r}– literály: p, q, r,¬p,¬q,¬r (ne ¬¬p)– ÚEK: p ∧ q ∧ r, ¬p ∧ q ∧ ¬r (ne p ∧ r)– ÚED: p ∨ ¬q ∨ r– ÚDNF: (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r)– ÚKNF: (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r)



Konstrukce úplné disjunktivní normální formy k dané f

– Je dána (tabulkou) booleovská funkce f(x1, . . . , xn) : {0, 1}n → {0, 1}.– Uvažujme následující postup pro vytvoření ÚDNF ϕ nad V = {p1, . . . , pn}:

1. Pro každý řádek tabulky odpovídající ohodnocení e, při kterém má funkce f hodnotu 1(tedy f(e(p1), . . . , e(pn)) = 1) sestrojíme ÚEK

l1 ∧ l2 ∧ · · · ∧ ln

kdeli =

{pi pokud e(pi) = 1¬pi pokud e(pi) = 0

2. ϕ je disjunkcí ÚEK postupně sestrojených v bodu 1.



Příklad konstrukce ÚDNF k dané fBooleovská funkce f je dána následující tabulkou:

p q r f

0 0 0 10 0 1 10 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 1

Krok 1.: projdeme řádky s 1 ve sloupci „f “ a vytvoříme příslušné ÚEK:ř. 1. : ÚEK je ¬p ∧ ¬q ∧ ¬rř. 2. : ÚEK je ¬p ∧ ¬q ∧ rř. 8. : ÚEK je p ∧ q ∧ rKrok 2.: výsledná ÚDNF je disjunkcí ÚEK z kroku 1., tedy je to formule

(¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r)



Správnost konstrukceVěta Pokud f má aspoň v jednom řádku hodnotu 1 (tedy nepředstavuje kontradikci), paksestrojená ÚDNF ϕ splňuje f = fϕ (tedy ϕ vytváří (reprezentuje) funkci f ; tabulky f a ϕjsou stejné).

(Pokud má f ve všech řádcích 0, postup vrátí „prázdnou formuli“.)

Důkaz Máme ukázat, že pro libovolné ohodnocení e platí:‖ϕ‖e = 1, p. k. v tabulce f je v řádku odpovídajícímu e hodnota 1.

ϕ má tvar k1 ∨ · · · ∨ km.

„⇒“: Nechť ‖ϕ‖e = 1. Z vlastností ∨: pro nějakou kj = l1 ∧ · · · ∧ ln musí být ‖kj‖e = 1.Tedy musí být: pro li = pi je e(pi) = 1 a pro li = ¬pi je e(pi) = 0.To e je ale právě ohodnocení odpovídající řádku, díky kterému se kj dostala do ϕ, tedyv tomto řádku je hodnota 1.

„⇐“: Je-li v nějakém řádku 1, uvažujme odpovídající ohodnocení e a odpovídající kj .Z konstrukce plyne, že ‖kj‖e = 1, a tedy ‖ϕ‖e = ‖k1 ∨ · · · ∨ km‖e = 1.



Jako snadný důsledek tedy dostaneme:

Věta Ke každé booleovské funkci f , která nepředstavuje kontradikci, existuje ÚDNF ϕtak, že f = fϕ.

Důkaz Požadovanou ϕ je například ÚDNF sestrojená k tabulce funkce f .



Konstrukce ÚDNF k dané formuli ψÚlohu lze obměnit:Je dána formule ψ (místo funkce f). Najděte ÚDNF ϕ tak, že ϕ a ψ jsou sémantickyekvivalentní (tj. mají stejné tabulky).

Příklad Sestrojte ÚDNF formule (p→ q) ∧ (p→ r).

Vytvoříme tabulku. Rovnou přidáme sloupec, kam zapíšeme ÚEK:

p q r (p → q) ∧ (p → r) ÚEK0 0 0 1 ¬p ∧ ¬q ∧ ¬r0 0 1 1 ¬p ∧ ¬q ∧ r0 1 0 1 ¬p ∧ q ∧ ¬r0 1 1 1 ¬p ∧ q ∧ r1 0 0 01 0 1 01 1 0 01 1 1 1 p ∧ q ∧ r

ÚDNF tedy je (¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ r)Bělohlávek (Univerzita Palackého v Olomouci) Diskrétní struktury 1 2020 58 / 76


Konstrukce ÚKNF k dané funkci f (formuli ψ)

– Místo hledání ÚDNF můžeme hledat ÚKNF ϕ k dané funkci f : {0, 1}n → {0, 1}(nebo k dané formuli ψ).

– Postup je „duální“:

1. Pro každý řádek tabulky odpovídající ohodnocení e, při kterém má funkce f hodnotu 0(tedy f(e(p1), . . . , e(pn)) = 0) sestrojíme ÚED

l1 ∨ l2 ∨ · · · ∨ ln

kdeli =

{pi pokud e(pi) = 0¬pi pokud e(pi) = 1

2. ϕ je konjunkcí ÚED postupně sestrojených v bodu 1.



Sestrojte ÚKNF k formuli (p→ q) ∧ (p→ r).

Vytvoříme tabulku pravdivostní funkce formule (p→ q) ∧ (p→ r); do dalšího sloupcezapíšeme příslušné ÚED.

p q r (p→ q) ∧ (p→ r) ÚED0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 0 ¬p ∨ q ∨ r1 0 1 0 ¬p ∨ q ∨ ¬r1 1 0 0 ¬p ∨ ¬q ∨ r1 1 1 1

Tedy ÚKNF je: (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r)



Analogická (duální) tvrzení pro ÚKNFVěta Pokud f má aspoň v jednom řádku hodnotu 0 (tedy f nepředstavuje tautologii), paksestrojená ÚKNF ϕ splňuje f = fϕ.

Jako snadný důsledek tedy dostaneme:

Věta Ke každé booleovské funkci f , která nepředstavuje tautologii, existuje ÚKNF ϕ tak,že f = fϕ.



Vyjadřování spojek jinými spojkamiVíme:ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ), tedyϕ ∨ ψ a ¬(¬ϕ ∧ ¬ψ) nabývají stejných hodnot.

Jinak řečeno, pro libovolné pravdivostní hodnoty a a b jea ∨· b = ¬·(¬·a ∧· ¬·b)

To znamená, že spojku ∨ lze vyjádřit pomocí ¬ a ∧.



Další příklady:

a ∨· b = ¬·(¬·a ∧· ¬·b)a ∨· b = ¬·a→· b

a ∧· b = ¬·(¬·a ∨· ¬·b)a ∧· b = ¬·(a→· ¬·b)

a→· b = ¬·(a ∧· ¬·b)a→· b = ¬·a ∨· b



Dvě důležité spojky:

Shefferova (↑, popř. |, NAND):↑· 0 10 1 11 1 0

Peirceova (také Nicodova, ↓, NOR):↓· 0 10 1 01 0 0

Všimněme si:

a ↑· b = ¬·(a ∧· b)a ↑· b = ¬·a ∨· ¬·b

a ↓· b = ¬·a ∧· ¬·ba ↓· b = ¬·(a ∨· b)



Každou ze spojek ¬, ∧ a ∨ lze vyjádřit pomocí ↑ i pomocí ↓.

¬·a = a ↑· aa ∧· b = (a ↑· b) ↑· (a ↑· b)a ∨· b = (a ↑· a) ↑· (b ↑· b)

¬·a = a ↓· aa ∧· b = (a ↓· a) ↓· (b ↓· b)a ∨· b = (a ↓· b) ↓· (a ↓· b)

Úkol: Ověřte výše uvedené tabulkovou metodou. Vyjádřete podobně → a ↔.



Funkčně úplné systémy spojekDefinice Množina {f1, . . . , fk} booleovských funkcí je funkčně úplná, pokud každouf : {0, 1}n → {0, 1} lze vyjádřit jako složení některých funkcí z {f1, . . . , fk}.Množina výrokových spojek je úplná, jestliže je úplná množina jejich pravdivostních funkcí.

Věta {¬·,∧·,∨·} je funkčně úplná.(Jinak řečeno: {¬,∧,∨} je funkčně úplná.)

Důkaz Máme dokázat, že každou booleovskou funkci f lze získat složením ¬·, ∧· a ∨·.To plyne z věty o ÚDNF (i z věty o ÚKNF):

K libovolné funkci f existuje odpovídající ÚDNF ϕ. Její pravdivostní funkce ϕ· je složená z¬·, ∧· a ∨·.



Následující tvrzení je zřejmé:

Lemma Je-li možné každou z {f1, . . . , fk} vyjádřit jako složení některých z {g1, . . . , gl},pak je-li {f1, . . . , fk} funkčně úplná, je i {g1, . . . , gl} funkčně úplná.

Např.: Každou ze spojek z {¬·,∧·,∨·} lze vyjádřit složením logických funkcí z {¬·,→·}(např. a ∨· b = ¬·a→· b). Protože je {¬·,∧·,∨·} úplná, je dle lemma i {¬·,→·} úplná.

Z uvedených vztahů o vzájemném vyjadřování spojek a z uvedeného lemma tedy plyne:

Věta Následující množiny logických funkcí jsou funkčně úplné:{¬·,∧·}, {¬·,∨·}, {¬·,→·}, {↑·}, {↓·}.

Ale: žádná z následujících množin není funkčně úplná:{¬·}, {∧·}, {∨·}, {∧·,∨·}, {→·}, {↔·}, {¬·,↔·}.

Pokuste se zdůvodnit proč (poslední tři jsou obtížnější).Bělohlávek (Univerzita Palackého v Olomouci) Diskrétní struktury 1 2020 67 / 76


Z dějin logiky

Aristotelés (384–322 př. n. l.)zakladatel logiky

– směr, kterým se logika ubírala až do 19. století (aristotelovská logika)– sylogismy:

Každý člověk je smrtelný.Sókratés je člověk.Sókratés je smrtelný.

– oddělil formu a obsah



mezi Aristotelem a 19. stoletím

– středověk: logika a scholastici

– raný novověk: moderní úvahy od praktickém využití logikynapř. Gottfried Wilhelm Leibniz (1646–1716):– lidské myšlení je možné redukovat na matematické výpočty– univerzální jazyk, characteristica universalis, ve kterém mělo být možné pracovat s

matematickými a vědeckými pojmy– koncept zařízení, tzv. calculus ratiocinator, které mělo provádět příslušné výpočty



George Boole (1815–1864)

– revoluční kniha The Laws of Thought (Zákony myšlení)– matematický přístup k logice– vliv: hlavní směr moderní logiky se nazývá Booleova logika



2. pol. 19. století– matematizace logiky

– formalizace a používání matematických metod– logika jako metodický základ pro matematiku a exaktní vědy

– významní logici:– Gottlob Frege (1848–1925),– Giuseppe Peano (1858–1932),– Charles Sanders Peirce (1839–1914),– David Hilbert (1862–1943)

– začal vznikat logický kalkul, který později podrobně popsali Bertrand Russell(1872–1970) a Alfred Whitehead (1887–1974): Principia Mathematica (1910–1913)

– vyvinula se z něj moderní predikátová logika– předmětem intenzívního zkoumání v 1. pol. 20. stol.



1. pol. 20. stol.– významné objevy v logice:

– možnosti (objevena axiomatizace)– meze formálních systémů (nerozhodnutelnost, neúplnost)– výpočetní aspekty logiky

–– významní logici:

Kurtl Gödel Alonzo Church Alan Turing(1906–1978) (1903–1955) (1912–1954)



Nahlédnutí do dalších oblastí moderní logikyAxiomatický systém logiky

– čistě syntaktický systém, ve kterém lze mechanickou manipulací se symboly z formulílogicky správně odvozovat další formule

– axiomatický systém výrokové logiku– axiomy:

ϕ→ (ψ → ϕ)(ϕ→ (ψ → χ))→ ((ϕ→ ψ)→ (ϕ→ χ))(¬ψ → ¬ϕ)→ (ϕ→ ψ)

– odvozovací pravidlo (tzv. modus ponens)

ϕ,ϕ→ ψψ

(z ϕ a ϕ→ ψ odvoď ψ)

– platí např. věta o úplnosti:Formule ϕ je odvoditelná z axiomů, právě když ϕ je tautologie.



Predikátová logika

– rozšíření výrokové logiky– značně bohatší jazyk: relace, funkce, kvantifikátory, . . .– základ pro mnoho oblastí informatiky, např. relační databáze, umělá inteligence, logicképrogramování



Logické programování a Prolog

– programování založené na predikátové logice– program = množina logických formulí (předpoklady)– spuštění programu:

– uživatel položí dotaz (logická formule)– prologovský interpret zjistí, zda dotaz logicky vyplývá z předpokladů– založeno na algoritmech automatického dokazování

– pro programování expertních systémů



Fuzzy logika– neklasická logika– vznik 1965, Lotfi Zadeh (1921–2017)

– více pravdivostních hodnot, místo {0, 1} máme např. {0, 12 , 1} nebo [0, 1]

– proč: || Zaběhnout 100 m za 13 sekund je vynikající výkon || = 0.8– mnoho aplikací:

– fuzzy regulátory, expertní systémy– spotřební elektronika (pračky, kamery, myčky nádobí, . . . )– automatické převodovky, řízení metra, . . .

– výzkum na naší katedřeBělohlávek (Univerzita Palackého v Olomouci) Diskrétní struktury 1 2020 76 / 76


Date post:	18-Oct-2020
Category:	Documents
Upload:	others
View:	6 times
Download:	0 times

Diskrétní struktury 1 - Logikabelohlavek.inf.upol.cz/vyuka/diskretni-struktury-1-logika.pdf ·...

Documents