Výroková logika. · 2020. 1. 15. · Výroková logika. Pokud bychom m¥li de noatv pojem logika...

Výroková logika.

Pokud bychom m¥li de�novat pojem logika, asi bychom nejvýstiºn¥ji mohli °íci, ºe je tostudium argumentace. Logika se snaºí kodi�kovat správné postupy, pomocí nichº vyvozu-jeme platné záv¥ry z daných informací. I kdyº v¥t²ina lidí p°i svých úvahách intuitivn¥dodrºuje základní logické zákony, je p°esto vhodné se snaºit o jejich formalizaci. Ta námpomáhá p°i sloºit¥j²ích situacích, kdy je t°eba se vyznat ve velkém mnoºství logickýchvztah·, ale moºná je²t¥ d·leºit¥j²í je její uplatn¥ní p°i implementaci procesu dedukce dopo£íta£ových program·.

Jsou dv¥ základní úrovn¥ klasické logiky: Niº²í je výroková logika, kterou se v této £ástibudeme zabývat, a vy²²í, tzv. predikátová logika, o které se zmíníme pozd¥ji.

Pod pojmem výrok budeme rozum¥t tvrzení, o nemº lze v principu rozhodnout, zdaje pravdivé nebo nepravdivé. Tím se automaticky vylu£ují zvolání, rozkazy, otázky a v¥ty,které jsou samy se sebou v rozporu. Výrok totiº musí spl¬ovat dv¥ základní vlastnosti:

• Výrok je bu¤ pravdivý nebo nepravdivý, t°etí moºnost neexistuje.

• Výrok nem·ºe být sou£asn¥ pravdivý i nepravdivý.

Uve¤me si n¥kolik p°íklad· výroku.

Delfín je savec.Kruh je bu¤ £tverec nebo trojúhelník.Shakespeare byl básník a námo°ní kapitán.Toto je krychle.

Situace s poslední v¥tou není na první pohled p°íli² jasná, nebo´ nem·ºeme rozhodnout,zda je tato v¥ta pravdivá £i nikoli, dokud nebude ur£eno, na co se vztahuje zájemno �Toto� .Nicmén¥ i poslední v¥tu povaºujeme za výrok, nebo´ p°i interpretaci zájmena bude moºnépravdivost £i nepravdivost posoudit.

Co ur£it¥ nejsou výroky, jsou následující.

Kolikátého je dnes?Kdybych tohle tu²il!Okamºit¥ vypadn¥te!Tato v¥ta není pravdivá.

Poslední tvrzení není výrok, nebo´ poru²uje dichotomii, kterou u výrok· poºadujeme.Toto tvrzení není ani pravdivé ani nepravdivé: P°edpokládáme-li, ºe tvrzení je pravdivé,okamºit¥ dospíváme k záv¥ru, ºe pravdivé není. Pokud naopak p°edpokládáme, ºe tvrzení

1

J. TI�ER: VÝROKOVÁ LOGIKA

není pravdivé, pak po jeho op¥tovném p°e£tení vidíme, ºe obsah odpovídá skute£nosti. Tose u nepravdivého tvrzení stát nem·ºe.

P°íklad. M¥jme seznam S = {V1, V2, . . . , V50} výrok·, kde k-tý výrok zní

Vk: �Práv¥ k výrok· na seznamu S je nepravdivých.�

Co m·ºeme vyvodit o pravdivosti £i nepravdivosti výrok· na seznamu S?První pozorování je, ºe výrok V50 nem·ºe být pravdivý, nebo´ pak by byly v²echny vý-

roky (v£etn¥ V50) nepravdivé. Takºe alespo¬ jeden z výrok· pravdivý je. Dále si v²imneme,ºe není moºné, aby dva r·zné výroky byly sou£asn¥ pravdivé. Z t¥chto dvou pozorováníplyne, ºe na seznamu S je práv¥ jeden pravdivý výrok. A tedy 49 je jich nepravdivých.Proto jediný pravdivý výrok je V49.

Formule výrokové logiky

P°ikro£me nyní k formalizaci. V b¥ºném jazyce m·ºeme jednu my²lenku vyjád°it mnohazp·soby. Ve výrokové logice dáváme p°ednost jednozna£nosti. Proto je pro studium výrok·vhodné uºívat zápisu, který pracuje s velmi omezenou mnoºinou symbol·, zvanou abecedavýrokové logiky. P°esto, ºe se abeceda skládá z malého po£tu symbol·, umoº¬uje vyjad°ovatzákladní logickou stavbu v²ech výrok·.

De�nice 1. Abeceda výrokové logiky je tvo°ena symboly uvedenými v následující tabulce.

Symbol Název Význam(, ) závorky¬ negace ne∧ konjunkce a∨ disjunkce nebo (nevylu£ovací)⇒ implikace jestliºe ..., pak⇔ ekvivalence práv¥, kdyº

P,Q,R, . . . výrokové prom¥nné výrokyPn, Qn, Rn, . . . , n = 0, 1, 2, . . . výrokové prom¥nné výroky

Symboly ¬,∧,∨,⇒, and ⇔ se nazývají logické spojky. Výrokové prom¥nné ozna£ujíjednotlivé výroky a jejich význam je na rozdíl od logických spojek v r·zných situacíchr·zný. Mnoºinu v²ech výrokových prom¥nných budeme zna£it V.

Výroky ve tvaru implikace P ⇒ Q jsou v matematice velmi £asté a uºívá se pro n¥ celá°ada r·zných ekvivalentních vyjád°ení:

Jestliºe platí P , pak platí Q.P implikuje Q.P je posta£ující podmínka pro Q.Q vyplývá z P .Q je nutná podmínka pro P .Q platí, kdykoli platí P .

2


Má-li výrok tvar implikace P ⇒ Q, pak výrok tvaru ¬Q ⇒ ¬P se nazývá kontrapo-zice.

Zápisy studovaných výrok· budeme chtít nazývat formulemi. V principu je takový zápiskone£ná posloupnost symbol· abecedy. Nap°. P ∧ Q nebo Q1P ((⇒ ∨ jsou p°íklady dvoukone£ných posloupností. Z nich pouze ta první m·ºe reprezentovat zápis výroku, a protojen takové posloupnosti jsou pro nás zajímavé z hlediska studia. Musíme proto de�novatpravidla, tzv. syntaxi, podle kterých lze vytvá°et posloupnosti schopné ozna£ovat výroky.

De�nice 2. Formule výrokové logiky je kone£ná posloupnost symbol· abecedy vyhovujícínásledující induktivní konstrukci.

(i) Výroková prom¥nná je formule.

(ii) Jsou-li ϕ a ψ formule, pak (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ⇒ ψ), (ϕ⇔ ψ) a (¬ϕ) jsou formule.

Mnoºinu v²ech formulí ozna£íme V∗.

Slovo �induktivní� v p°ede²lé de�nici ozna£uje speciální typ konstrukce, která se £astovyskytuje jak v logice, tak i v ostatních odv¥tvích matematiky. Její princip je následující.

Vytvá°íme danou mnoºinu tak, ºe za£neme jejími základními prvky (v na²em p°ípad¥to jsou výrokové prom¥nné). To je poºadavek (i) v De�nici 2. Na tyto základní prvkyopakovan¥ aplikujeme operace z bodu (ii). Takºe po první aplikaci dostaneme nap°. formuletypu

(P ∧Q), (R1 ⇔ P2), (¬Q3), . . .

M·ºeme je nazývat formulemi prvního °ádu. Formule druhého °ádu jsou vygenerovány zjiº vytvo°ných formulí (coº jsou výrokové prom¥nné a formule prvního °ádu). P°íkladytakových nových formulí jsou

(¬(P ∧Q)), ((R1 ⇔ P2) ∨ (¬Q3)), . . .

Tímto zp·sobem pokra£ujeme v kostrukci dal²ích úrovní. Je z°ejmé, ºe kaºdá formulevznikla z výrokových prom¥nných kone£n¥ mnoha aplikacemi operací z bodu (ii).

Pokud bychom se drºeli p°ísn¥ na²í de�nice, brzy bychom zjistili, ºe se v zápisechvyskytuje p°íli² mnoho závorek. Nap°. P ∧Q není formule, nebo´ podle na²ich pravidel jeformulí pouze (P ∧Q). Podobn¥

(((P ∨Q) ∨R) ∨Q1)

je formule, aleP ∨Q ∨R ∨Q1

není. Abychom si zápis usnadnili a u£inili ho £iteln¥j²ím, p°ijmeme následující úmluvu.

(i) Vn¥j²í závorky nebudeme psát. Tak zápisem P ∧Q budeme rozum¥t (P ∧Q).

(ii) Zavedeme preference mezi logickými spojkami. Negace váºe siln¥ji neº konjunkce adisjunkce. Konjunkce a disjunkce váºí siln¥ji neº implikace a ekvivalence. Nap°.

R1 ∧Q2 ⇒ ¬P3 ∨ P je ((R1 ∧Q2)⇒ ((¬P3) ∨ P )).

3


Do jaké míry budeme tuto konveci pouºívat záleºí na na²í volb¥. V p°ípad¥ nebezpe£í,ºe by mohla vzniknout dvojzna£nost, rad¥ji uºijeme více závorek neº mén¥.

P°íklad. Zapi²te formulemi následující výroky s vyuºitím daných výrokových prom¥nných

P : �Zpráva je skenována proti vir·m.�

Q : �Zpráva p°i²la z neznámé adresy.�

(i) Zpráva je skenována proti vir·m, kdykoli p°ijde z neznámé adresy.

(ii) Zpráva p°i²la z neznámé adresy, ale nebyla skenována proti vir·m.

(iii) P°ijde-li zpráva z neznámé adresy, není skenována proti vir·m.

(iv) Není pravda, ºe je nutné skenovat zprávu proti vir·m, p°ijde-li z neznámé adresy.

�e²ení. (i) Q⇒ P ; (ii) Q ∧ ¬P ; (iii) Q⇒ ¬P ; (iv) ¬(Q⇒ P ).

Cvi£ení.

(1) Které z následujících posloupností znak· jsou formule výrokového po£tu?

PQ∨, (R1 ∧Q)⇒ (T2 ⇔ P ), (R¬Q), (P ∨ ¬(S = Q)), ¬¬Q.

(2) Ozna£íme

P : �Ptolemáios je �ek.�

R : �Ramses je Egypán.�

Q1 : �Monet prodal sv·j obraz.�

Q2 : �Cézanne prodal sv·j obraz.�

Q3 : �Gauguin prodal sv·j obraz.�

Zapi²te formulemi následující výroky.

(a) Ptolemáios není �ek.

(b) Prolemáios je �ek, zatímco Ramses je Egypán.

(c) Je-li Ptolemáios �ek, není Ramses Egypán.

(d) Ptolemáios je �ek nebo, pokud není, Ramses není Egypán.

(e) Ptolemáios je �ek a Ramses je Egypán nebo ani jedno z toho.

(f) Monet jako jediný z trojice Monet, Cézanne a Gauguin prodal obraz.

(g) Gauguin jako jediný z trojice Monet, Cézanne a Gauguin neprodal obraz.

(h) Pouze jediný z trojice Monet, Cézanne a Gauguin prodal obraz.

(i) Alespo¬ jeden z trojice Monet, Cézanne a Gauguin prodal obraz.

(j) Alespo¬ dva z trojice Monet, Cézanne a Gauguin prodali obraz.

4


(k) Nejvý²e dva z trojice Monet, Cézanne a Gauguin prodali obraz.

(l) P°esn¥ dva z trojice Monet, Cézanne a Gauguin prodali obraz.

(3) M¥jme tvrzení T1, T2, . . . , k ∈ N, která zn¥jí:

Tk : �V²echna tvrzení Tn jsou pro n > k nepravdivá.�

Ukaºte, ºe ºádné z tvrzení T1, T2, . . . není výrok.

(4) U následujících výrok· tvaru implikace ur£ete, co je p°edpoklad a co je záv¥r. Kekaºdému výroku vyslovte opak a kontrapozici.

(a) Jsou-li jablka ºlutá, pak pomeran£e jsou zelené.

(b) Diferencovatelnost funkce f je posta£ující ke spojitosti f .

(c) Funkce je omezená, je-li interovatelná.

(d) Posloupnost je omezená, kdykoli je konvergentní.

(e) Je nutné, aby n bylo prvo£íslo, má-li být také 2n − 1 prvo£íslo.

(f) Ná² tým vyhraje, pouze pokud v n¥m bude Karel.

(5) Která z následujících podmínek je nutná nebo posta£ující nebo nemá ºádný vztah kvýroku: ��íslo n je d¥litelné 6.�

(a) n je d¥litelné 3.

(b) n je d¥litelné 9.

(c) n je d¥litelné 12.

(d) n+ 1 je d¥litelné 6.

(e) n2 je d¥litelné 3.

(f) n3 je sudé a d¥litelné 3.

(g) n je sou£in sudého a lichého £ísla.

(h) Sou£et cifer je d¥litelný 3.

Výsledky.

(1) Formule výrokové logiky jsou dv¥: druhá a pátá, u které bereme v úvahu úmluvu ozávorkách. U £tvrté vadí znaménko =, které nepat°í do abecedy výrokové logiky.

(2) (a) ¬P .(b) P ∧R.(c) P ⇒ ¬R.(d) P ∨ (¬P ⇒ ¬R).

(e) (P ∧R) ∨ (¬P ∧ ¬R).

(f) Q1 ∧ ¬Q2 ∧ ¬Q3.

(g) ¬Q2 ∧Q1 ∧Q3.

5


(h) (Q1 ∧ ¬Q2 ∧ ¬Q3) ∨ (¬Q1 ∧Q2 ∧ ¬Q3) ∨ (¬Q1 ∧ ¬Q2 ∧Q3).(i) Q1 ∨Q2 ∨Q3.(j) (Q1 ∧Q2 ∧Q3) ∨ (¬Q1 ∧Q2 ∧Q3) ∨ (Q1 ∧ ¬Q2 ∧Q3) ∨ (Q1 ∧Q2 ∧ ¬Q3) nebo

také (Q1 ∧Q2) ∨ (Q1 ∧Q3) ∨ (Q2 ∧Q3).(k) ¬Q1 ∨ ¬Q2 ∨ ¬Q3.(l) (¬Q1 ∧Q2 ∧Q3) ∨ (Q1 ∧ ¬Q2 ∧Q3) ∨ (Q1 ∧Q2 ∧ ¬Q3).

(3) Nejprve si uv¥domíme, ºe ºádné tvrzení Tk nem·ºe být pravdivý výrok. P°ipustíme-li, ºe n¥jaké Tk je pravdivý výrok, pak v²echna tvrzení s vy²²ím indexem neº k jsounepravdivá. Specieln¥ Tk+1 je nepravdivé. Av²ak obsah tohoto údajn¥ nepravdivéhotvrzení je pravdivý, nebo´ °íká, ºe v²echna Tk+2, Tk+3, . . . jsou nepravdivá - spor.

Zbývá moºnost, ºe v²echna Tk jsou nepravdivé výroky. Pak ale tvrzení kaºdého Tk od-povídá skute£nosti, coº u nepravdivého výroku nem·ºe nastat. Záv¥r celého rozboruje, ºe ºádné Tk není výrok.

(4) (a) Opak: Jablka jsou ºlutá a pomeran£e nejsou zelené.Kontrapozice: Nejsou-li pomeran£e zelené, pak nejsou jablka ºlutá.

(b) Opak: f je diferencovatelná a není spojitá.Kontrapozice: Není-li f spojitá, pak není diferencovatelná.

(c) Opak: Funkce je integrovatelná a neomezená.Kontrapozice: Není-li funkce omezená, není ani integrovatelná.

(d) Opak: Posloupnost je konvergentní a neomezená.Kontrapozice: Není-li posloupnost omezená, pak není konvergentní.

(e) Opak: n není prvo£íslo a 2n − 1 prvo£íslo je.Kontrapozice: Není-li n prvo£íslo, není ani 2n − 1 prvo£íslo.

(f) Opak: Ná² tým vyhrál i bez Karla.Kontrapozice: Nebude-li v týmu Karel, tým nevzhraje.

(5) P = posta£ující, N = nutná, 0 = nezávislá podmínka.P : (c), (f); N : (a), (e), (g), (h); 0: (b), (d).

Pravdivostní ohodnocení

V této £ásti se budeme o n¥co podrobn¥ji v¥novat pravdivosti a nepravdivosti výrok·.Cht¥li bychom de�novat, co to znamená, ºe jedna formule je logickým d·sledkem jinéformule nebo mnoºiny formulí. Nap°. by zcela jist¥ m¥lo platit, ºe formule P je d·sledekformule P ∧ Q. Protoºe a´ uº formule P a Q ozna£ují jakýkoli výrok, z toho ºe P ∧ Q jepravdivé, musí plynou, ºe je pravdivé i P . Tato na²e p°edstava se dá vyjád°it zcela p°esnýmzp·sobem. K tomu budeme pot°ebovat pojem pravdivostní ohodnocení.

Za�xujme si mnoºinu {0,1} pravdivostních hodnot:

0 ozna£ující nepravdu,

1 ozna£ující pravdu.

Nyní m·ºeme p°i°adit v²em výrokovým prom¥nným z na²í abecedy pravdivostní hodnotu0 nebo 1.

6


De�nice 3. Ohodnocení výrokových prom¥nných je kaºdé zobrazení ν z mnoºiny V domnoºiny {0,1}, ν : V −→ {0,1}.

Zápis ν(P ) = 1 £teme, ºe P je pravdivý výrok a ν(P ) = 0 £teme, ºe P je nepravdivývýrok.

Rádi bychom ohodnocení výrokových prom¥nných roz²í°ili z mnoºiny V na mnoºinuV∗ v²ech formulí. Toto roz²í°ení v²ak musí respektovat následující pravidla. Jsou-li ϕ a ψformule, pak

(i) ν(¬ϕ) =

{0, kdyº ν(ϕ) = 1,1 jinak.

(ii) ν(ϕ ∧ ψ) =

{1, kdyº ν(ϕ) = 1 a ν(ψ) = 1,0 jinak.

(iii) ν(ϕ ∨ ψ) =

{1, kdyº ν(ϕ) = 1 nebo ν(ψ) = 1,0 jinak.

(iv) ν(ϕ⇒ ψ) =

{0, kdyº ν(ϕ) = 1 a ν(ψ) = 0,1 jinak.

(v) ν(ϕ⇔ ψ) =

{1, kdyº ν(ϕ) = ν(ψ),0 jinak.

Ve zkrácené podob¥ m·ºeme uvedená pravidla sumarizovat v následující tabulce.

ϕ ψ ¬ϕ ϕ ∧ ψ ϕ ∨ ψ ϕ⇒ ψ ϕ⇔ ψ

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

Tabulka 1

De�nice 4. Roz²í°ení ohodnocení ν výrokových prom¥nných z mnoºiny V na mnoºinuV∗, které p°itom respektuje pravidla v Tabulce 1, budeme nazývat pravdivostní ohodnoceníformulí (nebo jen krátce pravdivostní ohodnocení) a ozna£ovat jej op¥t písmenem ν.

V praxi obvykle nerozli²ujeme mezi ohodnocením výrokových prom¥nných a jeho roz-²í°ením na v²echny formule. Mluvíme jednodu²e o pravdivostní hodnot¥ formule ϕ p°iohodnocení ν.

Pozastavme se na chvíli u Tabulky 1. Do jaké míry odpovídají pravidla v ní uvedenána²í intuici? Ur£it¥ nikdo nebude p°ekvapen, ºe pravdivostní hodnota ϕ je 1 práv¥, kdyºpravdivostní hodnota ¬ϕ je 0. Jiná v¥c je ale v p°ípad¥ implikace. Rozhodnutí dát hod-notu 1 formuli ϕ ⇒ ψ, kdyº nap°. ob¥ formule ϕ a ψ mají hodnotu 0, m·ºe n¥kohoznepokojit. Abychom rozptýlili tuto pochybnost, poloºme si otázku: V jaké situaci bychomozna£ili implikaci ϕ⇒ ψ za nepravdivou? Asi budeme souhlasit s tím, ºe pouze v p°ípad¥,kdy p°edpoklad ϕ je pravdivý, ale záv¥r ψ nepravdivý. To v²ak znamená, ºe v²em ostatnímp°ípad·m musíme p°iznat hodnotu 1.

7


Pravdivostní ohodnocení implikace, které máme v Tabulce 1, vede rovn¥º k tomu, ºenásledující dva výroky jsou pravdivé, i kdyº se nám to na první pohled bude zdát podivné.

Je-li £íslo 3 d¥litelné 7, pak je £íslo 3 sudé.Je-li £íslo 4 d¥litelné 7, pak je £íslo 4 sudé.

První typ je (0⇒ 0) a druhý (0⇒ 1).V De�nici 4 jsme zavedli pravdivostní ohodnocení, jako roz²í°ení jakéhokoli zobrazení ν

z mnoºiny výrokových prom¥nných na v²echny formule. Zatím v²ak nevíme, zda-li takovéroz²í°ení v·bec existuje a kdyº ano, je-li jediné nebo je jich více? Následující v¥ta odpovídána tuto otázku.

V¥ta 5. M¥jme ν : V −→ {0,1} ohodnocení výrokových prom¥nných. Pak existuje jedinéroz²í°ení ν : V∗ −→ {0,1} na mnoºinu v²ech formulí takové, ºe je pravdivostním ohodno-cením, tj. zachovává pravidla Tabulky 1.

D·kaz. D·kaz provedeme indukcí podle °ádu formule. Pro ú£ely tohoto d·kazu nazvemevýrokové prom¥nné formulemi °ádu 0. Formule °ádu n jsou ty, které vznikly z formulí°ádu 0 nejvý²e n-násobnou aplikací bodu (ii) z De�nice 2.

Krok 1: Na formulích °ádu 0 je ν jednozna£n¥ zadané.Krok 2: P°edpokládejme, ºe jsme ν jednozna£n¥ roz²í°ili na formule aº do °ádu n.

Kaºdá formule °ádu (n + 1), která není °ádu n, je vytvo°ena z formulí °ádu n jednou zp¥ti operací uvedených v De�nici 2 (ii). Tabulka 1 de�nuje roz²í°ení ν pro tyto formule, ato jednozna£ným zp·sobem. Tím jsme dokázali, ºe ν má jednozna£né roz²í°ení na v²echnyformule aº do °ádu (n+ 1). �

Roz²i°ování pravdivostního ohodnocení popsané v p°edchozí V¥t¥ 5 není pro nás veskute£nosti nic nového. Provádíme jej pokaºdé, kdyº vypl¬ujeme pravdivostní tabulkun¥jaké formule. Pravdivostní tabulka uvádí pravdivostní hodnotu dané formule p°i v²echmoºných ohodnoceních výrokových prom¥nných.

P°íklad. Vytvo°íme pravdivostní tabulku pro formuli ϕ = (P ∧Q) ∨ (¬P ⇒ R).

P Q R P ∧Q ¬P ⇒ R (P ∧Q) ∨ (¬P ⇒ R)

0 0 0 0 0 0

0 0 1 0 1 1

0 1 0 0 0 0

0 1 1 0 1 1

1 0 0 0 1 1

1 0 1 0 1 1

1 1 0 1 1 1

1 1 1 1 1 1

První t°i sloupce tabulky odpovídají t°em výrokovým prom¥nným formule ϕ a obsahujív²echny trojice vytvo°ené ze symbol· 0 a 1. Takových je 23 = 8. Pokud by formule obsa-hovala n prom¥nných, p°íslu²ná tabulka by m¥la 2n °ádk·. Je rozumné si zvolit system provypl¬ování 0 a 1 do prvních sloupc· tabulky, abychom na n¥jakou kombinaci nezapom¥li.Zde jsme zvolili lexikogra�cké uspo°ádání.

8


Pravdivostní tabulku m·ºeme pouºívat i v opa£ném sm¥ru: Známe-li hodnotu formule,chceme vyvodit moºné hodnoty výrokových prom¥nných. Tento typ se obvykle hodí v tzv.logických hádankách.

P°íklad. T°i osoby A, B a C jsou podez°elé ze spáchání zlo£inu. Vypov¥d¥ly následující:

A : �B je vinen a C je neviný.�

B : �Je-li vinen A, je vinen i C.�

C : �Jsem nevinen, ale alespo¬ jeden z A a B je vinen.�

Jaké jsou odpov¥di na otázky:

(i) Mohou být v²echny t°i výpov¥di pravdivé?

(ii) Jsou-li v²ichni nevinní, kdo vypovídal k°iv¥?

(iii) Jsou-li výpov¥di pravdivé, kdo je pachatel?

(iv) Mluví-li nevinní pravdu a viníci lºou, kdo je pachatel?

Ozna£íme si postupn¥A,B a C výroky �A je nevinen� , �B je nevinen� a �C je nevinen� .Pak jednotlivé výpov¥di jsou formule

¬B ∧ C, ¬A⇒ ¬C, C ∧ (¬A ∨ ¬B).

K odpov¥dím na poloºené otázky pot°ebujeme pravdivostní tabulku pro t°i vý²e uvedenéformule.

A B C ¬B ∧ C ¬A⇒ ¬C C ∧ (¬A ∨ ¬B)

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

Odpov¥di na otázky jsou následující:

(i) Ano, vidíme to v 6. °ádku.

(ii) K°iv¥ vypovídaly osoby A a C, viz poslední °ádek.

(iii) Ze 6. °ádku plyne, ºe pachatel je B.

(iv) Podmínka v otázce znamená, ºe pravdivostní hodnoty musí vyhovovat t°em rovnos-tem

ν(A) = ν(¬B ∧ C), ν(B) = ν(¬A⇒ ¬C) a ν(C) = ν(C ∧ (¬A ∨ ¬B)).

První rovnost je spln¥na v °ádcích 1, 3, 4, 6. V rámci nich je druhá rovnost spln¥napouze v °ádku 3. V tomto °ádku platí i t°etí rovnost, takºe odpov¥¤ je, ºe pachatelijsou osoby A a C.

9


Cvi£ení.

(1) Utvo°te pravdivostní tabulku formule (P ∨Q) ∧ ¬(P ∧Q) (vylu£ovací disjunkce).

(2) Utvo°te pravdivostní tabulku formule (P ⇒ (¬Q ∧Q))⇔ ¬P .

(3) Na ostrov¥ ºijí dva druhy obyvatel: pravdomluvní a lhá°i. Ti první mluví za v²echokolností pravdu, ti druzí stále lºou.

(a) Potkáme dva obyvatele P a Q a zeptáme se: �Je n¥kdo z vás lhá°?� P odpoví:�Alespo¬ jeden z nás je lhá°� . Lze ur£it, kdo jsou P a Q?

(b) Potkáme dva obyvatele P a Q a zeptáme se P : �Je n¥kdo z vás lhá°?� P odpoví:�Je-li Q lhá°, pak i já jsem lhá°� . Kdo jsou P a Q?

(c) Potkáme dva obyvatele a zeptáme se: �Je n¥kdo z vás pravdomluvný?� Z odpo-v¥di bylo moºné ur£it, kdo je kdo. Jaká byla odpov¥¤ a jaký je ná² záv¥r?

(d) Potkáme t°i obyvatele P , Q a R a zeptáme se P : �Jste lhá°?� P n¥co odpov¥d¥l,ale my jsme to p°eslechli. Zeptáme se tedy Q: �Co °íkal P?� Q odpov¥d¥l: ��ekl,ºe je lhá°.� Pak se ozval R: �Nev¥°te Q, je to lhá°.� Kdo je kdo?

(4) M¥jme karty takové, ºe kaºdá má na jedné stran¥ písmeno a na druhé stran¥ £íslo.Vidíme p°ed sebou poloºené tyto £ty°i karty:

S U 3 8

Pravidlo zní: Pokud je písmeno samohláska, na druhé stran¥ je sudé £íslo. Kolik karetmusíme oto£it, abychom zjistili, zda tyto £ty°i karty vyhovují pravidlu?

(5) Pro která pravdivostní ohodnocení prom¥nných P1, . . . , Pn je pravdivá níºe uvedenáformule?

(a) (P1 ⇒ P2) ∧ · · · ∧ (Pn−1 ⇒ Pn),(b) (P1 ⇒ P2) ∧ · · · ∧ (Pn−1 ⇒ Pn) ∧ (Pn ⇒ P1),(c) Konjunkce formulí (Pi ⇒ ¬Pj) p°es v²echny dvojice index· i 6= j. Formáln¥

zapsáno:∧i 6=j(Pi ⇒ ¬Pj).

Výsledky.

(1) ν((P ∨Q) ∧ ¬(P ∧Q)

)= 1 práv¥, kdyº ν(P ) 6= ν(Q).

(2) Pravdivostní hodnota je 1 ve v²ech ohodnoceních.

(3) (a) P je pravdomluvný, Q je lhá°.(b) Oba jsou pravdomluvní.(c) Odpov¥¤ byla NE, odpovídající byl lhá° a druhý byl pravdomluvný.(d) R je pravdomluvný, Q je lhá° a P nelze ur£it.

(4) Dv¥ karty U a 3.

(5) (a) Existuje £íslo k ∈ {0, 1, . . . , n}, ºe ν(Pi) = 0 pro i ≤ k a ν(Pi) = 1 pro i > k.(b) Bu¤ ν(Pi) = 0 pro v²echna i nebo ν(Pi) = 1 pro v²echna i.(c) ν(Pi) = 1 pro nejvý²e jeden index i.

10


Logický d·sledek

Nyní zavedeme pojem, který odráºí na²i p°edstavu o logickém vyplývání.

De�nice 6. M¥jme formuli ϕ a mnoºinu formulí Σ. �ekneme, ºe ϕ je logický d·sledekformulí z mnoºiny Σ (nebo Σ logicky implikuje ϕ), je-li formule ϕ pravdivá v kaºdémohodnocení, ve kterém jsou pravdivé v²echny formule v mnoºin¥ Σ. Zna£íme Σ |= φ.

V tomto kontextu nazýváme formule v mnoºine Σ p°edpoklady a formuli ϕ záv¥rem.Pokud ϕ není logický d·sledek mnoºiny Σ, zna£íme Σ 6|= φ.

Je-li Σ jednoprvková mnoºina, Σ = {ψ}, pí²eme ψ |= ϕ místo {ψ} |= ϕ. Nastane-li situace, ºe ψ |= ϕ a sou£asn¥ ϕ |= ψ, pak °íkáme, ºe ψ a ϕ jsou logicky (nebo takétautologicky £i sémanticky) ekvivalentní a pí²eme ψ |=| ϕ.

P°íklad. Uvaºujme mnoºinu Σ = {P, P ⇒ Q}. Ukáºeme, ºe Σ |= Q.Pravdivostní tabulka je následující:

P Q P ⇒ Q

0 0 10 1 11 0 01 1 1

Jediný p°ípad, kdy jsou ob¥ formule v Σ interpretovány jako pravdivé, je poslední °ádek.Ale tam je pravdivá i formule Q. Proto platí, ºe Σ |= Q.

Z De�nice 6 plyne, ºe nutná a posta£ující podmínka k Σ 6|= ϕ je existence pravdivostníhoohodnocení ν, které v²echny formule v Σ interpretuje jako pravdivé, ale ν(ϕ) = 0. Jakoukázku vezm¥me mnoºinu Σ = {P, Q⇒ P} a otestujme, zda Σ |= Q. Pravdivostní tabulkaje podobná tabulce z p°ede²lého p°íkladu.

P Q Q⇒ P

0 0 10 1 01 0 11 1 1

Zde t°etí °ádek sv¥d£í o tom, ºe Σ 6|= Q, nebo´ ob¥ formule v mnoºin¥ Σ jsou interpre-továny jako pravdivé, ale hodnota Q je 0. Na tom nic nezm¥ní ani fakt, ºe £tvrtý °ádekdává hodnotu 1 jak formulím v Σ, tak prom¥nné Q. Stojí za pov²imnutí, ºe z mnoºiny Σneplyne ani ¬Q, Σ 6|= ¬Q.

P°íklad. Ov¥°íme, ºe formule (P ⇒ Q)∧ (Q⇒ P ) a P ⇔ Q jsou logicky ekvivalentní. Zatím ú£elem sestavíme pravdivostní tabulku obou formulí.

P Q P ⇒ Q Q⇒ P (P ⇒ Q) ∧ (Q⇒ P ) P ⇔ Q

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

11


Z tabulky vidíme, ºe v kaºdém ohodnocení, kdy je první formule pravdivá, je pravdivá idruhá, coº znamená, ºe

(P ⇒ Q) ∧ (Q⇒ P ) |= (P ⇔ Q).

Ale i naopak, je-li pravdivá druhá z formulí, je pravdivá i první, tedy

(P ⇔ Q) |= (P ⇒ Q) ∧ (Q⇒ P ).

Dohromady máme (P ⇒ Q) ∧ (Q⇒ P ) |=| (P ⇔ Q).

Pou£ení z vý²e uvedeného p°íkladu je, ºe prohlásit dv¥ formule ϕ a ψ za logicky ekvi-valentní, je to samé jako °íci, ºe formule ϕ a ψ mají tutéº pravdivostní tabulku. To se námbude je²t¥ hodit.

Podívejme se nyní na zvlá²tní p°ípad logického d·sledku, kdy mnoºina p°edpoklad· jeprázdná, Σ = ∅. Jaká formule ϕ je logickým d·sledkem prázdné mnoºiny formulí, ∅ |= ϕ?Intuitivn¥ to znamemá, ºe záv¥r ϕ má být pravdivý, kdykoli jsou pravdivé p°edpoklady.Zde ºádné p°edpoklady nejsou, takºe ϕ musí být pravdivé �samo o sob¥� . Jinými slovy,ν(ϕ) = 1 pro kaºdé pravdivostní ohodnocení ν. Takové formule se nazývají tautologie.

De�nice 7. Formule ϕ se nazývá tautologie, pokud ν(ϕ) = 1 pro kaºdé pravdivostní ohod-nocení ν. Zápis je |= ϕ.

Asi nejjednodu²í tautologie je (P ∨¬P ). Opak tautologie je formule zvaná kontradikce.

De�nice 8. Formule ϕ se nazývá kontradikce, pokud ν(ϕ) = 0 pro kaºdé pravdivostníohodnocení ν. Zápis je |= ¬ϕ.

P°íklad kontradikce je (P ∧¬P ). Je rovn¥º z°ejmé, ºe negace tautologie je kontradikcea negace kontradikce je tautologie. Kdyº si p°ipomeneme, ºe dv¥ formule jsou logickyekvivalentní práv¥, kdyº mají identické pravdivostní tabulky, ihned vidíme, ºe v²echnytautologie jsou mezi sebou logicky ekvivalentní a rovn¥º v²echny kontradikce jsou mezisebou logicky ekvivalentní.

P°íklad. Ov¥°te, ºe formule Q1 ⇒ (Q2 ⇒ (Q3 ⇒ Q1)) je tautologie.Zp·sob, který vºdy funguje, je pomocí pravdivostní tabulky. Pro t°i prom¥nné je to

je²t¥ zvládnutelné, ale pro více prom¥nných to p°estává být sch·dné. Jiná moºnost, vhodnázejména p°i implikacích, je metoda sporem. P°edpokládáme, ºe formule je nepravdivá.Implikace je nepravdivá pouze v jediném p°ípad¥: p°edpoklad má hodnotu 1 a záv¥r 0. Toznamená, ºe

ν(Q1) = 1 a ν(Q2 ⇒ (Q3 ⇒ Q1)) = 0.

Je-li ν(Q1) = 1, je i ν(Q3 ⇒ Q1) = 1 bez ohledu na hodnotu Q3. Odtud plyne, ºe iQ2 ⇒ (Q3 ⇒ Q1) je pravdivé, a tím celá p·vodní formule. Coº je spor, který ukazuje, ºep°i ºádném pravdivostním ohodnocení nem·ºe být Q1 ⇒ (Q2 ⇒ (Q3 ⇒ Q1)) nepravdiváformule.

Logický d·sledek i tautologie jsou de�novány pomocí pravdivostního ohodnocení. Na-víc v obou p°ípadech hrají hlavní roli ta ohodnocení, která p°íslu²ným formulím dávajíhodnotu 1. Nep°ekvapí nás proto, ºe mezi logickým d·sledkem a tautologií je t¥sný vztah.

12


V¥ta 9. M¥jme formule ϕ1, ϕ2, . . . , ϕn a ψ. Následující je ekvivalentní:

(i) {ϕ1, ϕ2, . . . , ϕn} |= ψ, tj. ψ je logickým d·sledkem mnoºiny {ϕ1, ϕ2, . . . , ϕn}.

(ii) |= (ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn)⇒ ψ, tj. (ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn)⇒ ψ je tautologie.

D·kaz. P°edpokládejme, ºe je spln¥n bod (i) a ov¥°íme, ºe implikace

(1) (ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn)⇒ ψ

je tautologie. M¥jme libovolné ohodnocení ν. Pokud je ν(ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) = 0, jeimplikace pravdivá. Pokud je ν(ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) = 1, pak musí být pravdivé v²echnyformule ϕ1, ϕ2, . . . , ϕn. V tom p°ípad¥ je podle (i) pravdivé i ψ, a tím i celá implikace.

Nyní naopak p°edpokládejme, ºe platí bod (ii) a ov¥°íme, ºe ψ je logický d·sledekmnoºiny {ϕ1, ϕ2, . . . , ϕn}. Za tím ú£elem m¥jme pravdivostní ohodnocení ν takové, ºeν(ϕ1) = · · · = ν(ϕn) = 1. Protoºe víme, ºe implikace (1) je tautologie, a tedy pravdivá,musí být nutn¥ ν(ψ) = 1. �

Z V¥ty 9 vyplývá, ºe logickou ekvivalenci m·ºeme redukovat na tautologii a naopak.Navíc platí tvrzení, ºe ϕ |=| ψ práv¥, kdyº |= (ϕ ⇔ ψ). Je-li totiº ϕ |=| ψ, pak je spln¥noϕ |= ψ i ψ |= ϕ. Podle V¥ty 9 to zna£í, ºe ob¥ formule ϕ⇒ ψ a ψ ⇒ ϕ jsou tautologiemi.Jejich konjunkce je samoz°ejm¥ op¥t tautologie, která není nic jiného neº ϕ⇔ ψ.

Uvedeme si n¥kolik £asto uºívaných a uºite£ných logických ekvivalencí.

dvojitá negace: ¬¬P |=| P

nahrazení implikace: (ϕ⇒ ψ) |=| ¬ϕ ∨ ψ

kontrapozice: (ϕ⇒ ψ) |=| (¬ψ ⇒ ¬ϕ)

de Morganova pravidla:¬(ϕ ∧ ψ) |=| ¬ϕ ∨ ¬ψ¬(ϕ ∨ ψ) |=| ¬ϕ ∧ ¬ψ

distributivní zákony:ϕ ∧ (ψ ∨ θ) |=| (ϕ ∧ ψ) ∨ (ϕ ∧ θ)ϕ ∨ (ψ ∧ θ) |=| (ϕ ∨ ψ) ∧ (ϕ ∨ θ)

Poslední d·leºitý pojem spojený s pravdivostním ohodnocením je splnitelnost mnoºinyformulí.

De�nice 10. M¥jme mnoºinu Σ formulí. �ekneme, ºe je splnitelná (nebo ºe má model),jestliºe existuje pravdivostní ohodnocení, ve kterém jsou v²echny formule v Σ pravdivé.

Uºíváme-li alternativní terminologii, tj. ºe Σ má model, pak modelem rozumíme práv¥to ohodnocení, ve kterém jsou v²echny formule z Σ interpretovány jako pravdivé. Pokudse mnoºina Σ skládá z jediné formule ϕ, Σ = {ϕ}, mluvíme o splnitelnosti formule ϕ. Vtakovém p°ípad¥ je splnitelnost ϕ to samé, jako °íci, ºe ϕ není kontradikce.

P°íklad. Zjist¥te, zda je splnitelná mnoºina

Σ = {(P ⇒ Q)⇒ R, ¬P ∨R, ¬P ∧Q ∧R, Q⇔ (P ∨R)}.

Formule obsahují jen t°i prom¥nné, proto je moºné úlohu °e²it pravdivostní tabulkou.

13


P Q R (P ⇒ Q)⇒ R ¬P ∨R ¬P ∧Q ∧R Q⇔ (P ∨R)

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

Ze £tvrtého °ádku vyvozujeme, ºe mnoºina Σ je splnitelná.

Je z°ejmé, ºe kaºdá podmnoºina splnitelné mnoºiny je rovn¥º splnitelná. Specieln¥,prázdná mnoºina je splnitelná.

Uvaºujme mnoºinu formulí. P°i°adíme-li formulím n¥jaký význam, stanou se z nichvýroky. Pak splnitelnost mnoºiny formulí znamená, ºe p°íslu²né výroky jsou konzistentní,tj. nejsou navzájem ve sporu. V rovin¥ formulí je tedy splnitelnost to samé jako konzistencev rovin¥ výrok·.

V¥ta 11. M¥jme formuli ϕ a mnoºinu formulí Σ. Následující je ekvivalentní:

(i) Σ |= ϕ,

(ii) Σ ∪ {¬ϕ} není splnitelná.

D·kaz. P°edpokládejme, ºe Σ |= ϕ a ºe ν je pravdivostní ohodnocení, ve kterém jsouv²echny formule v Σ pravdivé. Protoºe ϕ je logickým d·sledkem Σ, je ν(ϕ) = 1. Pak je alemnoºina Σ ∪ {¬ϕ} nesplnitelná.

Nyní naopak p°edpokládejme, ºe Σ ∪ {¬ϕ} je nesplnitelná. M¥jme ohodnocení ν, vekterém jsou v²echny formule v Σ pravdivé. Pak nutn¥ musí platit, ºe ν(¬ϕ) = 0, nebo´ vopa£ném p°ípad¥ by byla mnoºina Σ ∪ {¬ϕ} splnitelná. Odtud plyne, ºe ν(ϕ) = 1. �

Poznamenejme, ºe z V¥ty 11 vyplývá, ºe logickým d·sledkem nesplnitelné mnoºiny jekaºdá formule.

V jedné z dal²ích sekcí budeme diskutovat testování splnitelnosti pomocí efektivn¥j²ímetody neº je pravdivostní tabulka. S pomocí V¥ty 11 tím získáme i efektivn¥j²í zp·sobov¥°ování logického d·sledku.

Cvi£ení.

(1) Které z následujících formulí jsou tautologie, které kontradikce a které jsou spnitelné.

(a) ¬(P ⇒ ¬P );

(b) P ∨ (P ⇒ ¬P );

(c) P ∨ (Q ∨ ¬Q);

(d) ¬((P ∨ ¬P )⇒ Q);

14


(e) ¬P ∨ ¬(P ⇒ Q);

(f) ((P ⇒ Q)⇒ P )⇒ P ;

(g) (P ∨ ¬Q)⇒ ¬(Q ∨ ¬P );

(h) ((P ⇒ Q)⇒ P ) ∧ ¬P ;(i) (P ⇒ Q) ∨ (Q⇒ R) ∨ ¬(¬P ∨R);

(j) ¬(¬P ⇔ Q)⇒ (R ∨ ¬Q);

(k) ((P ∧R)⇒ Q)⇔ (R ∧ ¬(P ⇒ Q)).

(2) Ur£ete, které z nazna£ených logických d·sledk· jsou správné.

(a) {¬P ⇒ Q, ¬P ⇒ ¬Q} |= P .

(b) {P ∧Q, P ⇒ R, Q⇒ S} |= R ∧ S.(c) {¬R,¬(P ∧ ¬R), ¬P ⇒ ¬Q} |= ¬Q.

(3) Ukaºte, ºe formule (P ⇒ (Q ⇒ (R ⇔ (Q ⇒ P )))) a P ⇒ (Q ⇒ R) jsou logickyekvivalentní.

(4) Ukaºte, ºe formule P ⇔ (Q⇔ R) a (P ⇔ Q)⇔ R jsou logicky ekvivalentní. Platnostasociativního zákona by nás mohla vést k tomu, ºe bychom psali krátce P ⇔ Q⇔ R.Tuto formuli v²ak obvykle interpretujeme, ºe P,Q,R jsou bu¤ v²echny pravdivé nebov²echny nepravdivé, coº není ekvivalentní ani jedné z formulí P ⇔ (Q ⇔ R) a(P ⇔ Q)⇔ R.

(5) Mnoºina formulí F se nazývá nezávislá, kdyº pro kaºdou ϕ ∈ F platí, ºe nenílogickým d·sledkem ostatních formulí z F , tj. F \ {ϕ} 6|= ϕ. Která z následujícíchmnoºin je nezávislá?

(a) {P ⇒ Q, Q⇒ R, R⇒ P};(b) {P ⇒ Q, Q⇒ R, P ⇒ R};(c) {P, Q, P ⇒ R, R⇒ Q};(d) {P1, P1 ∧ P2, P1 ∧ P2 ∧ P3, . . . , P1 ∧ · · · ∧ Pn, . . . }. Má tato mnoºina n¥jakou

nezávislou podmnoºinu?

(6) Uvaºujme v²echny formule t°í prom¥nných P,Q,R.

(a) Kolik je jich, aº na logickou ekvivalenci, pravdivých p°esn¥ v p¥ti pravdivostníchohodnoceních?

(b) Kolik je jich, aº na logickou ekvivalenci, logickým d·sledkem P ∨Q?

(Víme, ºe formule je jednozna£n¥ ur£ena, aº na logickou ekvivalenci, svojí pravdi-vostní tabulkou.)

Výsledky.

(1) Tautologie: (b), (c), (f), (i). Kontradikce: (h), (k). Splnitelné: (a), (d), (e), (g), (j).

15


(2) V²echny logické d·sledky platí.

(5) (a) Mnoºina je nezávislá.

(b) Mnoºina není nezávislá, nap°. {P ⇒ Q, Q⇒ R} |= P ⇒ R.

(c) Mnoºina není nezávislá, nap°. {P, P ⇒ R, R⇒ Q} |= Q.

(d) Pouze prázdná mnoºina a jednoprvkové podmnoºiny jsou nezávislé. Obsahuje-lipodmnoºina alespo¬ dv¥ formule, pak nejkrat²í formule v dané podmnoºin¥ jelogickým d·sledkem zbylých formulí.

(6) (a) Formule ϕ o t°ech prom¥nných má osmi°ádkovou pravdivostní tabulku. Z nichsi zvolíme 5 °ádk·, kde bude stát ohodnocení 1. To lze u£init

(85

)= 56 zp·soby.

(b) Osmi°ádková tabulka pro formuli ϕ obsahuje 6 °ádk·, kde má P nebo Q ohod-nocení 1. Na t¥chto °ádcích musí mít hodnotu 1 i formule ϕ. Na zbylých dvou°ádcích mohou být hodnoty 0 nebo 1. To lze doplnit £ty°mi zp·soby. Po£ethledaných formulí je tak 4.

Booleovské funkce

Zatím jsme pouºívali p¥t logických spojek: ¬, ∧, ∨, ⇒ a ⇔. Je z°ejmé, ºe t¥chto p¥t zná-mých spojek nep°edstavuje jedinou moºnost. Získali bychom n¥co p°idáním nových spojekk abeced¥? Nebo naopak ztratili bychom n¥co vynecháním n¥jaké ze spojek, které máme?Abychom odpov¥d¥li na tyto otázky, p°ipome¬me si p°íklady logických ekvivalencí z p°ed-chozí sekce. Ukazují nám, ºe nap°. ϕ⇒ ψ je ekvivalentní formuli ¬ϕ∨ψ. Pokud vypustímez abecedy implikaci, nic neztrácíme, protoºe ji m·ºeme modelovat pomocí zbylých spo-jek. Podobná situace by byla, kdybychom roz²í°ili na²i abecedu o n¥jakou novou logickouspojku. Takové roz²í°ení by nám nic nového nep°ineslo, protoºe kaºdou formuli v roz²í°enéabeced¥ bychom mohli ekvivalentn¥ nahradit formulí v p·vodní abeced¥.

Abychom od·vodnili p°edchozí argumentaci, bude vhodné si zavést pojem booleovskéfunkce.

De�nice 12. Kaºdá funkce B : {0,1}n −→ {0,1} se nazývá (n-ární) booleovská funkce,n ∈ N.

V p°ípad¥ n = 1 a n = 2 uºíváme názvy �unární� a �binární� . P°íklad unární booleovskéfunkce je

B(0) = 1, B(1) = 0.

Binární booleovská funkce je nap°.

B(0,0) = 1, B(0,1) = 1, B(1,0) = 0, B(1,1) = 0.

Obecn¥, n-ární booleovská funkce je funkce n prom¥nných, které nabývají hodnot pouze 0a 1.

D·leºitý p°ípad nastává, kdyº je booleovská funkce odvozena z n¥jaké formule ϕ. Je-linap°. ϕ = P ∧ Q, m·ºeme utvo°it pravdivostní tabulku a pomocí ní booleovskou funkcide�novat.

16


P Q P ∧Q B(X1, X2)

0 0 0 B(0,0) = 00 1 0 B(0,1) = 01 0 0 B(1,0) = 01 1 1 B(1,1) = 1

Booleovskou funkci odvozenou z formule ϕ budeme zna£it Bϕ a °íkat, ºe Bϕ je realizovánaformulí ϕ. Obecná de�nice je následující:

De�nice 13. M¥jme formuli ϕ = ϕ(P1, . . . , Pn) obsahující výrokové prom¥nné P1, . . . , Pn.Booleovská funkce Bϕ(X1, . . . , Xn) realizovaná formulí ϕ je funkce, pro kterou platí

Bϕ(ν(P1), . . . , ν(Pn)

)= ν(ϕ)

pro v²echna pravdivostní ohodnocení ν.

Vyvstává p°irozená otázka, zda lze kaºdou booleovskou funkci realizovat n¥jakou for-mulí. Neº odpovíme na tuto otázku v plné obecnosti bude uºite£né se podívat na konkrétníp°íklad.

M¥jme booleovskou funkci B zadanou:

B(0,0,0) = 0,B(0,0,1) = 1,B(0,1,0) = 0,B(0,1,1) = 1,B(1,0,0) = 1,B(1,0,1) = 0,B(1,1,0) = 0,B(1,1,1) = 1.

Jedna moºnost, jak sestrojit formuli ϕ, ºe Bϕ = B, je následující.Metoda A:Sestavíme seznam v²ech trojic (X1, X2, X3), ve kterých je B(X1, X2, X3) = 1. Ke kaºdé

trojici napí²eme vhodnou konjunkci, která má hodnotu 1 práv¥ pro ohodnocení dané toutotrojicí pravdivostních hodnot.

001 ¬P1 ∧ ¬P2 ∧ P3,011 ¬P1 ∧ P2 ∧ P3,100 P1 ∧ ¬P2 ∧ ¬P3,111 P1 ∧ P2 ∧ P3.

Kdyº nyní poloºíme

ϕ = (¬P1 ∧ ¬P2 ∧ P3) ∨ (¬P1 ∧ P2 ∧ P3)

∨ (P1 ∧ ¬P2 ∧ ¬P3) ∨ (P1 ∧ P2 ∧ P3),

pak ϕ je pravdivá jen pro vý²e vypsané trojice hodnot a nepravdivá ve v²ech ostatních.Jinými slovy, Bϕ = B.

17


Nemáme ºádný apriorní d·vod preferovat trojice (X1, X2, X3), kde hodnota funkceB(X1, X2, X3) = 1. M·ºeme provést podobnou konstrukci i pro trojice, ve kterých jeB(X1, X2, X3) = 0.

Metoda B:Zde vytvo°íme seznam trojic, pro které je B(X1, X2, X3) = 0. Napravo od kaºdé trojice

napí²eme disjunkci, která má hodnotu 0 práv¥ pro ohodnocení dané touto trojicí.

000 P1 ∨ P2 ∨ P3,010 P1 ∨ ¬P2 ∨ P3,101 ¬P1 ∨ P2 ∨ ¬P3,110 ¬P1 ∨ ¬P2 ∨ P3.

Poloºíme-li

ϕ = (P1 ∨ P2 ∨ P3) ∧ (P1 ∨ ¬P2 ∨ P3)

∧ (¬P1 ∨ P2 ∨ ¬P3) ∧ (¬P1 ∨ ¬P2 ∨ P3),

pak bude ϕ nepravdivá jen pro trojice vypsané vý²e a pravdivá ve v²ech ostatních p°ípa-dech. Tj. Bϕ = B.

V¥ta 14. M¥jme n-ární booleovskou funkci B. Pak existuje formule ϕ závislá na n pro-m¥nných, která realizuje funkci B, B = Bϕ.

D·kaz. Ke konstrukci m·ºeme uºít kterýkoli ze dvou p°ístup· uvedených p°ed v¥tou.Provedeme nap°. detailn¥ Metodu A a Metodu B jen stru£n¥ okomentujeme.

Je-li B = 0, pak ϕ = P ∧ ¬P .M·ºeme tedy p°edpokládat, ºe existují body z de�ni£ního oboru {0,1}n, kde B nabývá

hodnoty 1. �ekn¥me, ºe takových bod· je k a my jsme si je v²echny vypsali:

(X11, X12, . . . , X1n)(X21, X22, . . . , X2n)

...(Xk1, Xk2, . . . , Xkn)

Pro kaºdou vypsanou n-tici vytvo°íme konjunkci prom¥nných, která bude mít hodnotu 1práv¥ jen pro ohodnocení uvedené v n-tici. Pro i = 1, . . . , k a j = 1, . . . , n poloºíme

θij =

{Pj je-li Xij = 1¬Pj je-li Xij = 0.

P°íslu²ná konjunkce pro i-tý °ádek je ψi = θi1 ∧ θi2 ∧ · · · ∧ θin. V²imn¥me si, ºe ψi jepravdivá jen pro jediný výb¥r pravdivostního ohodnocení, a to pro (Xi1, Xi2, . . . , Xin).Nakonec formule ϕ,

ϕ = ψ1 ∨ ψ2 ∨ · · · ∨ ψk.

Nyní je jasné, ºe booleovská funkce Bϕ realizovaná formulí ϕ nabývá hodnoty 1 v bodechuvedených na seznamu vý²e a 0 v²ude jinde. Takºe Bϕ = B.

18


Kdybychom se rozhodli pro Metodu B, podíváme se nejd°íve, zda existuje bod de�ni£-ního oboru {0,1}n, kde hodnota funkce je 0. Pokud ne, je formule ϕ = P ∨ ¬P . Jinakp°íslu²ná formule vypadá

ϕ = ψ1 ∧ ψ2 ∧ · · · ∧ ψk,kde

ψi = θi1 ∨ θi2 ∨ · · · ∨ θini a θij =

{Pj je-li Xij = 0¬Pj je-li Xij = 1

.

�

Podle práv¥ dokázané v¥ty je kaºdá booleovská funkce realizovaná formulí. Formule,která danou funkci realizuje není jediná. Jakákoli s ní logicky ekvivalentní realizuje stejnoubooleovskou funkci.

D·sledek p°edchozí v¥ty je rovn¥º fakt, ºe logických spojek je dosta£ující (dokoncevíce neº dosta£ující) mnoºství pro realizaci v²ech booleovských funkcí. P°edstavme si, ºebychom roz²í°ili jazyk výrokového po£tu o n¥jakou novou exotickou logickou spojku. Kaºdáformule ϕ̃ v tomto roz²í°eném jazyce realizuje booleovskou funkci Bϕ̃. Podle p°edchozí v¥tyale existuje formule ϕ v p·vodním jazyce, která rovn¥º realizuje Bϕ̃. Formule ϕ̃ má takekvivalentní prot¥j²ek ve formuli ϕ, vyjád°ené v p·vodním neroz²í°eném jazyce.

Poslední poznámka se týká názvu �booleovský� . Mnoºina {0,1} je obda°ena algebraic-kou strukturou: booleovským sou£inem a booleovským sou£tem. První operace je totoºnás oby£ejným sou£inem £ísel. Druhá se od normálního s£ítání li²í v jediném bod¥, a to, ºe

1 + 1 = 0,

coº je s£ítání modulo 2. Mnoºina {0,1} s vý²e uvedenými operacemi je d·leºitý p°ípadobecn¥j²í matematické struktury nazývané booleovská algebra. Do dal²ích detail· zde ne-budeme zacházet, nicmén¥ ve cvi£ení (1) níºe je vid¥t, jak má p¥t logických spojek svéprot¥j²ky v booleovských operacích.

Cvi£ení.

(1) M¥jme dv¥ formule ϕ a ψ, které realizují booleovské funkce Bϕ a Bψ. Pomocí prav-divostní tabulky ov¥°te následující rovnosti. Znaménko + má význam booleovskéhosou£tu.

(a) B¬ϕ = 1 +Bϕ,

(b) Bϕ∧ψ = BϕBψ,

(c) Bϕ∨ψ = Bϕ +Bψ +BϕBψ,

(d) Bϕ⇒ψ = 1 +Bϕ +BϕBψ,

(e) Bϕ⇔ψ = 1 +Bϕ +Bψ.

(2) M¥jme formule ϕ a ψ. Ukaºte, ºe

(a) ϕ |= ψ práv¥, kdyº Bϕ ≤ Bψ.(b) ϕ |=| ψ práv¥, kdyº Bϕ = Bψ.

(c) |= ϕ práv¥, kdyº Bϕ = 1.

19


Tvary DNF a CNF

Z d·kazu V¥ty 14 plyne je²t¥ jedno pou£ení. Formule, která realizuje danou booleovskoufunkci je velmi speci�ckého tvaru. Jediné logické spojky, které obsahuje, jsou ¬, ∧ a ∨. Dv¥metody uºité p°i konstrukci nám dávají dva kanonické tvary formulí.

De�nice 15. Formule, která je rovna pouze výrokové prom¥nné nebo negaci výrokové pro-m¥nné, se krátce nazývá literál.

Formule ϕ je v disjunktivním normálovém tvaru (DNF), kdyº

ϕ = ψ1 ∨ ψ2 ∨ · · · ∨ ψk,

kde v²echny ψi jsou konjunkcemi literál·, tj. ψi = θi1 ∧ θi2 ∧ · · · ∧ θini a θij jsou literály.Podobn¥ formule ϕ je v konjunktivním normálovém tvaru (CNF), kdyº

ϕ = ψ1 ∧ ψ2 ∧ · · · ∧ ψk,

kde v²echny ψi jsou disjunkcemi literál·, tj. ψi = θi1 ∨ θi2 ∨ · · · ∨ θini a θij jsou literály.

Dv¥ metody uºité v d·kaze V¥ty 14 dávají

D·sledek. Kaºdá formule je logicky ekvivalentní formuli ve tvaru DNF i CNF.

P°evedeme formuli (¬P ⇒ Q) ⇒ (R ⇒ P ) do CNF i do DNF. P°i tomto p°evodunemusíme jít cestou p°es booleovské funkce a Metodu A a B. Mnohem krat²í je aplikovatpravidla, která zachovávají logickou ekvivalenci.

(¬P ⇒ Q)⇒ (R⇒ P ) |=| eliminace krajních implikací(¬¬P ∨Q)⇒ (¬R ∨ P ) |=| odstran¥ní dvojité negace

(P ∨Q)⇒ (¬R ∨ P ) |=| eliminace implikace¬(P ∨Q) ∨ (¬R ∨ P ) |=| de Morganovo pravidlo(¬P ∧ ¬Q) ∨ ¬R ∨ P |=| distributivní zákon

(¬P ∨ ¬R ∨ P ) ∧ (¬Q ∨ ¬R ∨ P )

Poslední °ádek je tvar CNF dané formule. Tvar DNF máme dokonce uº v p°edposledním°ádku.

Kaºdá tautologie má CNF i DNF tvar jednoduchý: P ∨¬P . Obdobn¥ kaºdá kontradikcemá CNF i DNF tvar P ∧ ¬P .

Protoºe kaºdá booleovská funkce m·ºe být realizována formulí uºívající pouze spojky{¬,∧,∨}, °íkáme, ºe mnoºina spojek {¬,∧,∨} je úplná. Úplnost této mnoºiny m·ºe býtje²t¥ zlep²ena:

V¥ta 16. Mnoºiny {¬,∧} a {¬,∨} jsou úplné.

D·kaz. Protoºe {¬,∧,∨} je úplná mnoºina spojek, sta£í, pro první p°ípad, modelovatdisjunkci pomocí n¥jaké kombinace negace a konjunkce. Toho dosáhneme de Morganovýmpravidlem P ∨Q |=| ¬(¬P ∧ ¬Q). Stejn¥ postupujeme i ve druhém p°ípad¥. �

M·ºeme jít je²t¥ dále a ptát se, zda existuje n¥jaká zvlá²tní logická spojka, která samao sob¥ tvo°í úplnou mnoºinu? Taková opravdu existuje, zna£í se | a nazývá se She�er·voperátor. Je de�nován P |Q := ¬(P ∧Q) nebo následující tabulkou.

20


P Q P|Q0 0 10 1 11 0 11 1 0

Pomocí She�erova operátoru m·ºeme modelovat nap°. negaci a konjunkci:

¬P |=| P |PP ∧Q |=| (P |Q)|(P |Q)

Z V¥ty 16 te¤ plyne, ºe mnoºina {|} je úplná.

Cvi£ení.

(1) P°eve¤te následující formule do tvaru CNF a DNF.

(a) ¬(P ⇔ Q),

(b) ((P ⇒ Q) ∧ ¬Q)⇒ P ,

(c) (P ⇔ ¬Q)⇔ R,

(d) P ⇒ (¬Q⇔ R),

(e) (¬P ∧ (¬Q⇔ P ))⇒ ((Q ∧ ¬P ) ∨ P ).

(2) De�nujme binární spojku (P ↓ Q) |=| ¬(P ∨ Q). Ukaºte, ºe mnoºina {↓} je úplnámnoºina spojek.

(3) Ukaºte, ºe {¬,→} je úplná mnoºina spojek. Mnoºiny {∨,∧,⇒,⇔} a {¬,⇔} nejsouúplné.

(4) Ozna£íme symbolem \ novou logickou spojku de�novanou

ν(\(PQR)) =

{1 pokud alespo¬ dv¥ prom¥nné z P,Q,R mají ohodnocení 1,0 jinak.

Nalezn¥te tvar DNF formule ϕ = \(PQR).

Výsledky.

(1) (a) CNF: (P ∨Q) ∧ (¬P ∨ ¬Q); DNF: (P ∧ ¬Q) ∨ (¬P ∧Q).

(b) CNF i DNF je stejný, P ∨Q.(c) CNF: (¬P ∨Q ∨R) ∧ (P ∨ ¬Q ∨R) ∧ (P ∨Q ∨ ¬R) ∧ (¬P ∨ ¬Q ∨ ¬R);

DNF: (¬P ∧Q ∧R) ∨ (P ∧ ¬Q ∧R) ∨ (P ∧Q ∧ ¬R) ∨ (¬P ∧ ¬Q ∧ ¬R).

(d) CNF: (¬P ∨ ¬Q ∨ ¬R) ∧ (¬P ∨Q ∨R); DNF: ¬P ∨ (Q ∧ ¬R) ∨ (¬Q ∧R).

(e) Formule je tautologie, P ∨ ¬P .

(2) Podle V¥ty 16 sta£í modelovat pomocí ↓ negaci a disjunkci: ¬P |=| P ↓ P , P ∨Q |=|(P ↓ Q) ↓ (P ↓ Q).

21


(3) Podle V¥ty 16 sta£í modelovat ∨ pomocí ¬,⇒: P ∨Q |=| ¬P ⇒ Q.Pomocí spojek ∨,∧,⇒,⇔ nelze modelovat negaci. Uvaºujme formule ϕ(P ) prom¥nnéP tvo°ené pouze spojkami z {∨,∧,⇒,⇔} Vlastnost kaºdé takové formule ϕ je, ºe jepravdivá, kdykoli ν(P ) = 1. (Rozmyslete!) Proto nem·ºe platit ϕ(P ) |=| ¬P .Podobn¥ pomocí spojek ¬,⇔ nelze modelovat konjunkci (ani disjunkci). Uvaºujmeformule ϕ(P,Q) prom¥nných P,Q tvo°ené pouze spojkami z {¬,⇔} Vlastnost kaºdétakové formule ϕ je, ºe p°i zám¥n¥ P,Q na ¬P,¬Q se pravdivostní hodnota ϕ ne-zm¥ní, ν(ϕ(P,Q)) = ν(ϕ(¬P,¬Q)). (Rozmyslete!) Proto nem·ºe platit ϕ(P,Q) |=|P ∧Q. (Jiný zp·sob d·kazu m·ºe být, ºe vý²e uvedené formule ϕ(P,Q) mají prav-divostní tabulku obsahující vºdy sudý po£et 1. Proto nemohou být ekvivalentní sP ∧Q.)

(4) ϕ |=| (P ∧Q ∧R) ∨ (¬P ∧Q ∧R) ∨ (P ∧ ¬Q ∧R) ∨ (P ∧Q ∧ ¬R).

Rezolu£ní metoda

V této £ásti popí²eme metodu, jak rychle rozhodnout, je-li formule logickým d·sledkemn¥jaké zadané mnoºiny formulí. K tomu vyuºijeme V¥tu 11, která nám logický d·sledekredukuje na splnitelnost mnoºiny formulí.

Problem splnitelnosti mnoºiny formulí má velkou praktickou d·leºitost. Metoda prav-divostní tabulky, vhodná pro formule s nízkým po£tem prom¥nných, roste z hlediska po£tuoperací exponenciáln¥ s po£tem prom¥nných. Nap°. p°i 100 prom¥nných, by tabulkovoumetodu nezvládl ani nejvýkon¥j²í po£íta£.

K popisu rezolu£ní metody pot°ebujeme n¥kolik nových termín·. Klauzule je kaºdádisjunkce literál·, θ1 ∨ · · · ∨ θn. S klauzulí jsme se uº setkali (i kdyº jsme tento termínnepouºívali) ve tvaru CNF. Tvar CNF je vlastn¥ konjunkcí klauzulí.

M¥jme klauzuli ψ = θ1 ∨ θ2 ∨ · · · ∨ θn. M·ºeme ji rovn¥º psát ve tvaru

{θ1, θ2, . . . , θn},

kde £árka nahrazuje logickou spojku ∨. Tak se m·ºeme na klauzuli dívat jako na mnoºinuliterál· ψ = {θ1, θ2, . . . , θn}. To nám umoºní mluvit nap°. o sjednocení klauzulí nebomnoºinovém rozdílu klauzulí £i o prázdné klauzuli. Navíc tato konvence eliminuje jak po°adíliterál·, tak jejich opakování v klauzuli: θ1 ∨ θ2 ∨ θ1 je jednodu²e {θ1, θ2}.

De�nice 17. �ekneme, ºe klauzule ψ1 a ψ2 jsou v rezolu£ní relaci podle literálu θ, pokudjedna z nich obsahuje θ a druhá ¬θ.

M¥jme dv¥ klauzule ψ1 a ψ2 v rezolu£ní relaci podle θ, ºe θ ∈ ψ1 a ¬θ ∈ ψ2. Rezolventaklauzulí ψ1 a ψ2 podle θ je nová klauzule ozna£ená

Rθ(ψ1, ψ2) =(ψ1 \ {θ}

)∪(ψ2 \ {¬θ}

).

Dv¥ klauzule ψ1 = {P1, Q,R} a ψ2 = {¬Q,R,R1,¬Q2} jsou v rezolu£ní relaci podle Q.Jejich rezolventa vznikne tak, ºe z první odebereme Q, ze druhé ¬Q a zbytky sjednotíme:

RQ(ψ1, ψ2) = {P1, R,R1,¬Q2}.

22


Klauzule mohou být v rezolu£ní relaci i podle více neº jednoho literálu. Nap°. klauzuleψ3 = {P1, Q,¬R} je s klauzulí ψ2 v rezolu£ní relaci podle Q i podle R. M·ºeme vytvo°itrezolventy podle kaºdého z literál· Q a R:

RQ(ψ3, ψ2) = {P1,¬R,R,R1,¬Q2}, RR(ψ3, ψ2) = {P1, Q,¬Q,R1,¬Q2}.

Pokud nastane p°ípad, ºe dvojice klauzulí je {P} a {¬P}, pak rezolventa podle P je práznáklauzule, RP (P,¬P ) = ∅. Prázdná klauzule není splnitelná. (Pozor, prázdná mnoºina klau-zulí splnitelná je!)

Nyní popí²eme postup, jak zjistit zda {ϕ1, . . . , ϕm} |= ϕ pomocí tzv. rezolu£ní metody.Podle V¥ty 11 sta£í testovat splnitelnost mnoºiny {ϕ1, . . . , ϕm,¬ϕ}.

Algoritmus rezolu£ní metody.

1. V²echny formule v mnoºin¥ {ϕ1, . . . , ϕm,¬ϕ} p°epí²eme do CNF a vytvo°íme mno-ºinu Σ = {ψ1, ψ2, . . . , ψn} klauzulí.

2. Redukce po£tu klauzulí:

(a) Klauzule, které jsou tautologiemi, vynecháme.

(b) Obsahuje-li n¥jaká neprázdná klauzule ψ′ jinou klauzuli ψ, ψ′ ⊃ ψ, klauzuli ψ′

vynecháme.

(c) Obsahuje-li klauzule ψ takový literál θ, ºe opa£ný literál ¬θ se ve zbylých klau-zulích nevyskytuje, klauzuli ψ vynecháme.

3. Zvolíme si literál θ, podle kterého lze vytvá°et rezolventy a k mnoºin¥ Σ p°idámev²echny moºné rezolventy podle θ.

4. Odebereme v²echny klauzule obsahující θ nebo ¬θ, výslednou mnoºinu ozna£íme jakoΣ a vracíme se do bodu 2.

Celý proces kon£í vºdy v bod¥ 3. Bu¤ tam jako výstup celého algoritmu vznikne prázdnáklauzule, coº je nesplnitelná mnoºina. V tom p°ípad¥ je i p·vodní mnoºina Σ nesplni-telná, a tedy {ϕ1, . . . , ϕm} |= ϕ. Nebo uº nebude existovat ºádný literál, podle kterého lzedále vytvá°et rezolventy. To znamená, ºe výstupem je splnitelná mnoºina. Tím také Σ jesplnitelná a {ϕ1, . . . , ϕm} 6|= ϕ.

P°íklad. Pomocí rezolu£ní metody zjist¥te, zda Q ∨ S je logickým d·sledkem mnoºiny{P ∨Q, R⇒ S, ¬P ∨ S, ¬Q ∨R}.

Krok 1. Nejprve p°evedeme v²echny formule v mnoºin¥ do tvaru CNF. Krom¥ R ⇒S uº ostatní formule v poºadovanám tvaru jsou, takºe s vyuºitím pravidla o eliminaciimplikace pí²eme

R⇒ S |=| ¬R ∨ S.

Zbývá k t¥mto formulím p°idat negaci testovaného d·sledku:

¬(Q ∨ S) |=| ¬Q ∧ ¬S.

Problem jsme redukovali na zji²óvání splnitelnosti £i nesplnitelnosti mnoºiny klauzulí Σ ={P ∨Q, ¬R ∨ S, ¬P ∨ S, ¬Q ∨R, ¬Q, ¬S}.

23


Krok 2. Klauzule ¬Q ∨ R obsahuje klauzuli ¬Q. Proto klauzuli ¬Q ∨ R vynecháme.Máme te¤ mnoºinu

Σ = {P ∨Q,¬R ∨ S,¬P ∨ S,¬Q,¬S}.

V ní se vyskytuje literál ¬R bez svého prot¥j²ku R. Proto vypustíme i klauzuli ¬R ∨ S.Do 3. kroku algoritmu vstupujeme s mnoºinou

Σ = {P ∨Q,¬P ∨ S,¬Q,¬S}.

Dal²í kroky jsou zachyceny v následující tabulce, kterou si vysv¥tlíme.

S P Q

P ∨Q 1¬P ∨ S 1¬Q 0¬S 0

¬P 0Q 1

∅

Na po£átku vyplníme první sloupec tabulky zadanými klauzulemi.Krok 3. Zvolíme prom¥nnou, podle které budeme vytvá°et rezolventy. Zde jsme se

rozhodli pro S. (Pro tuto volbu nebyl ºádný zvlá²tní d·vod, mohli jsme zvolit jakoukoliprom¥nnou P , Q, S.) Zvolenou prom¥nnou S napí²eme do druhého sloupce nahoru. Vtomto sloupci vyzna£íme symbolem 1 °ádky s formulí obsahující S, a symbolem 0 °ádky, kdeje formule obsahující ¬S. Pak vytvo°íme v²echny rezolventy podle S, tj. v²echny kombinace°ádk· s 0 a 1. Zde nám p°ibyla jedna rezolventa ¬P p°ipsaná dol· do druhého sloupce.

Krok 4. Z dal²ího postupu (uº navºdy) vylou£íme v²echny formule mající na svém°ádku vepsaný symbol 0 nebo 1.

Mnoºina klauzulí vzniklá po Kroku 4 je {P ∨Q,¬Q,¬P}. S ní se vracíme do Kroku 2.�ádná redukce te¤ k dispozici není, proto p°istupujeme ke Kroku 3.

Krok 3. Zvolili jsme prom¥nnou P pro vytvá°ení rezolvent a napsali ji do t°etího sloupce.Vyzna£íme °ádky, kde je formule obsahující P nebo ¬P symbolem 1 nebo 0 a vytvo°ímev²echny mnoºné rezolventy. Zde p°ibyla pouze jediná rezolventa Q, která je dopsaná dot°etího sloupce dolu. Krok 4 te¤ redukuje mnoºinu klauzulí na {¬Q,Q}. V této chvíli uºvidíme, ºe dal²í rezolventa bude prázdná klauzule, zadaná mnoºina je tak nesplitelná aQ ∨ S je logickým d·sledkem. V tabulce je pro úplnost £tvrtý sloupec dopln¥n.

P°íklad. Zjistíme, zde formule ¬(P∨(¬Q⇒ ¬R)

)je logický d·sledek mnoºiny {S∨(¬Q⇒

R), ¬(S ∧ ¬T ), (¬S ∧ P )⇒ Q, ¬T ∨R, ¬T ⇒ ¬(Q ∧R)}.Krok 1. Formule p°evedeme do tvaru CNF. (Krom¥ t°etí formule, ta uº ve tvaru CNF

je.)

S ∨ (¬Q⇒ R) |=| S ∨Q ∨R,¬(S ∧ ¬T ) |=| ¬S ∨ T,

(¬S ∧ P )⇒ Q |=| S ∨ ¬P ∨Q,¬T ⇒ ¬(Q ∧R) |=| T ∨ ¬Q ∨ ¬R.

24


Zbývá p°evést negaci testovaného d·sledku:

P ∨ (¬Q⇒ ¬R) |=| P ∨Q ∨ ¬R.

Úlohu jsme p°evedli na otázku, zda je £i není splnitelná mnoºina

Σ = {S ∨Q ∨R, ¬S ∨ T, S ∨ ¬P ∨Q, ¬T ∨R, T ∨ ¬Q ∨ ¬R, P ∨Q ∨ ¬R}.

Krok 2. Zde k ºádné redukci nedochází. P°epí²eme si formule do tabulky a za£nemeKrok 3.

Krok 3. Budeme vytvá°et rezolventy nap°. podle T . Ve sloupci s ozna£ením T mámesymbolem 1 ozna£eny °ádky, kde se vyskytuje T a symbolem 0 °ádky s výskytem ¬T .Rezolventa z formulí ve 2. a 4. °ádku je ¬S ∨ R. Tu zapí²eme dol· do druhého sloupce.Rezolventa formulí ve 4. a 5. °ádku je tautologie, kterou vynecháme.

T

S ∨Q ∨R x¬S ∨ T 1

S ∨ ¬P ∨Q x¬T ∨R 0

T ∨ ¬Q ∨ ¬R 1P ∨Q ∨ ¬R x

¬S ∨RKrok 4. Po odebrání klauzulí obsahujících T nebo ¬T zbývá mnoºina

Σ = {S ∨Q ∨R, S ∨ ¬P ∨Q, P ∨Q ∨ ¬R, ¬S ∨R},

se kterou se vracíme do Kroku 2.Krok 2. V²imneme si, ºe literálQ se zde vyskytuje bez prot¥j²ku ¬Q. Formule obsahující

Q m·ºeme vynechat. V tabulce jsou ozna£ené x. Zbyla jediná formule ¬S ∨ R, která jesplnitelná. Proto ¬

(P ∨ (¬Q⇒ ¬R)

)není logický d·sledek zadané mnoºiny formulí.

N¥kdy v pr·b¥hu rezolu£ní metody k vytvá°ení rezolvent v·bec nedojde. To kdyº semnoºina klauzulí p°i Kroku 2 zredukuje na prázdnou mnoºinu.

P°íklad. Pomocí rezolu£ní metody zjist¥te, zda P ⇒ (¬Q ∨ R) je logickým d·sledkemmnoºiny {(R ∧ T )⇒ S, S ⇒ (P ⇔ Q), (P ∨R)⇒ S}.

P°evedeme v²echny formule v mnoºin¥ do tvaru CNF a nakonec p°idáme negaci testo-vaného záv¥ru.

(R ∧ T )⇒ S |=| ¬R ∨ ¬T ∨ S.S ⇒ (P ⇔ Q) |=| ¬S ∨ (P ⇔ Q)

|=| ¬S ∨((P ⇒ Q) ∧ (Q⇒ P )

)|=| ¬S ∨

((¬P ∨Q) ∧ (¬Q ∨ P )

)|=| (¬S ∨ ¬P ∨Q) ∧ (¬S ∨ ¬Q ∨ P ).

(P ∨R)⇒ S |=| (¬P ∧ ¬R) ∨ S|=| (¬P ∨ S) ∧ (¬R ∨ S).

¬(P ⇒ (¬Q ∨R)

)|=| ¬(¬P ∨ ¬Q ∨R)

|=| P ∧Q ∧ ¬R.

25


Vzniklé klauzule napí²eme do prvního sloupce tabulky a za£neme s redukcí podle Kroku 2.

¬R ∨ ¬T ∨ S x¬S ∨ ¬P ∨Q x¬S ∨ ¬Q ∨ P x

¬P ∨ S x¬R ∨ S x

PQ¬R x

Klauzule ¬R z posledního °ádku je obsaºena v klauzulích na 1. a 5. °ádku. Tyto klauzulevynecháme (nazna£eno symbolem x v prvním sloupci). Klauzule Q v p°edposledním °ádkuje obsaºena v klauzuli na 2. °ádku. Rovn¥º P je £ástí klauzule na 3. °ádku. Proto klauzulez 2. a 3. °ádku také vypou²tíme. Po této redukci zbyly £ty°i klauzule (nemají x v prvnímsloupci). V nich se literál S vyskytuje bez svého prot¥j²ku ¬S. Klauzuli ze 4. °ádku vy-pou²tíme (nazna£eno symbolem x ve druhém sloupci). Z·stala mnoºina {P,Q,¬R}. Ta jezjevn¥ splnitelná. M·ºeme v²ak pokra£ovat v redukci podle bodu 2(c) algoritmu a vynechati klauzule P,Q,¬R. Zbyde prázdná mnoºina, která je vºdy splnitelná. Proto P ⇒ (¬Q∨R)není d·sledkem zadané mnoºiny formulí.

Podívejme se je²t¥ jednou na algoritmus rezolu£ní metody. Kroky 2 − 4 modi�kujívstupní mnoºinu klauzulí tak, ºe k ní p°idají v²echny rezolventy podle zvoleného literáluθ a následn¥ odstraní v²echny klauzule obsahující θ nebo ¬θ. Abychom mohli algoritmusprohlásit za korektní, musíme ov¥°it, ºe vstupní a výstupní (tj. modi�kovaná) mnoºinaklauzulí jsou ekvivalentní z hlediska splnitelnosti. Ov¥°ení korektnosti je v následující v¥t¥.

V¥ta 18. M¥jme mnoºinu klauzulí Σ = {ψ1, ψ2, . . . , ψn} a literál θ. Ozna£íme si mnoºinu

Σ0 := {ψ ∈ Σ | ψ obsahuje θ nebo ¬θ}.

Pak Σ je splnitelná práv¥, kdyº je splnitelná mnoºina

Σ̃ := Σ ∪ {Rθ(ψi, ψj) | ψi, ψj jsou v rezolu£ní relaci podle θ} \ Σ0.

D·kaz. Tvrzení je ve tvaru ekvivalence, musíme tak dokázat dv¥ implikace.P°edpokládejme, ºe Σ je splnitelná, tj. existuje pravdivostní ohodnocení ν, ve kterém

jsou v²echny klauzule v Σ pravdivé. V prvním kroku ukáºeme, ºe v tomto ohodnocení jsoupravdivé i v²echny rezolventy podle θ.

M¥jme klauzule ψi, ψj ∈ Σ, které jsou v rezolu£ní relaci podle θ: θ ∈ ψi a ¬θ ∈ ψj . Je-liν(θ) = 1, pak nutn¥

ν(ψj \ {¬θ}

)= 1,

nebo´ celá klauzule ψj je pravdivá v ohodnocení ν. Tím ov²em je pravdivá i kaºdá klauzuleobsahující ψj , specieln¥ rezolventa. Je-li naopak ν(θ) = 0, musí být pravdivá klauzuleψi\{θ}, a tedy i rezolventa. V²echny rezolventy p°idané k mnoºin¥ Σ jsou tak v ohodnoceníν pravdivé. To znamená, ºe mnoºina

Σ ∪ {Rθ(ψi, ψj) | ψi, ψj jsou v rezolu£ní relaci podle θ}

26


je splnitelná. Tím je splnitelná i kaºdá její podmnoºina, specieln¥ Σ̃.Pro d·kaz opa£né implikace p°edpokládejme, ºe mnoºina

Σ̃ = Σ ∪ {Rθ(ψi, ψj) | ψi, ψj jsou v rezolu£ní relaci podle θ} \ Σ0

je splnitelná pomocí pravdivostního ohodnocení ν. Je d·leºité si v²imnout, ºe ºádná klau-zule v této mnoºin¥ neobsahuje θ ani ¬θ. Na²ím plánem je roz²í°it ohodnocení ν i na literálθ tak, aby se v²echny klauzule v mnoºin¥ Σ0 staly pravdivými.

Podívejme se na mnoºinu t¥ch klauzulí ψ ∈ Σ0, které obsahují literál θ, ale neobsahují¬θ. Jestli pro v²echny takové klauzule platí, ºe ν(ψ \ {θ}) = 1, poloºíme ν(θ) = 0. Tatovolba zaru£uje, ºe v²echny klauzule v Σ0 jsou interpretovány jako pravdivé.

Zbývá moºnost, ºe existuje n¥jaká klauzule ψi ∈ Σ0 obsahující θ a p°itom ν(ψi \{θ}

)=

0. V tom p°ípad¥ poloºíme ν(θ) = 1. Jak to vypadá nyní s pravdivostními hodnotami ostat-ních klauzulí v mnoºin¥ Σ0? Obsahuje-li klauzule literál θ, je z°ejm¥ pravdivá. V opa£némp°ípad¥ máme klauzuli ψj ∈ Σ0, která obsahuje ¬θ (a neobsahuje θ). Z p°edpokladu víme,ºe rezolventa Rθ(ψi, ψj) je pravdivá v ohodnocení ν, tj. je pravdivá klauzule(

ψi \ {θ})∪(ψj \ {¬θ}

).

Protoºe první £ást pravdivá není, musí být pravdivá druhá. To v²ak znamená, ºe je pravdivái celá klauzule ψj . Ukázali jsme, ºe ohodnocení ν lze vºdy roz²í°it na literál θ tak, aby vmnoºin¥ Σ0 byly v²echny klauzule pravdivé.

Protoºe Σ = (Σ \ Σ0) ∪ Σ0, m·ºeme d·kaz uzav°ít: První mnoºina Σ \ Σ0 obsahujeklauzule pravdivé v ohodnocení ν podle p°edpokladu a o druhé mnoºin¥ Σ0 jsme to práv¥ukázali. �

Cvi£ení.

(1) Rozhodn¥te pomocí rezolu£ní metody, zda platí

(a){

(P ⇒ Q)⇒ R, (P ∧R)⇔ S, Q ∨ ¬S ∨ T, T ⇒ (S ∧Q ∧R)}|= ¬T ∨ S.

(b) {P ⇒ (Q ∧R), (P ∨ S)⇔ T, Q ∨ ¬R ∨ S, Q⇒ S} |= ¬Q ∧R.(c)

{(P ⇒ Q)⇒ (R⇒ S), (Q⇒ R)⇒ (S ⇒ P )

}|= (R⇒ (P ∨ S)) ∧ ((Q ∧R)⇒ S).

(d) {(R ∧ T )⇒ S, S ⇒ (P ⇔ Q), T ∨ ¬S, (P ∨ S ∨R)⇒ S}|= (P ∧ ¬Q)⇒ R.

(e){P ⇒ ¬(R ∨Q), (Q ∧ S)⇒ ¬P, ¬S ∨R, R⇔ ¬(P ∧ S)

}|= R⇒ S.

Výsledky.

(1) (a) P°evodem do CNF vznikne mnoºina klauzulí

P ∨R, ¬Q ∨R, ¬P ∨ ¬R ∨ S, P ∨ ¬S, R ∨ ¬S, Q ∨ ¬S ∨ T, S ∨ ¬T, Q ∨ ¬T,R ∨ ¬T, T, ¬S,

která není splnitelná. ¬T ∨ S je d·sledekem.

27


(b) P°evodem do CNF vznikne mnoºina klauzulí

¬P ∨Q, ¬P ∨R, ¬P ∨ T, ¬S ∨ T, P ∨ S ∨ ¬T, Q ∨ ¬R ∨ S, ¬Q ∨ S,Q ∨ ¬R,

která je splnitelná. ¬Q ∧R není d·sledekem.

(c) P°evodem do CNF vznikne mnoºina klauzulí

P ∨ ¬R ∨ S, ¬Q ∨ ¬R ∨ S, P ∨Q ∨ ¬S, Q ∨R, R, R ∨ ¬S, ¬P ∨Q,¬P ∨R, ¬P ∨ S, Q ∨ ¬S, R ∨ ¬S, ¬S,

která není splnitelná. (R⇒ (P ∨ S)) ∧ ((Q ∧R)⇒ S)) je d·sledekem.

(d) P°evodem do CNF vznikne mnoºina klauzulí (po vypu²t¥ní tautologií)

¬R ∨ S ∨ ¬T, ¬P ∨Q ∨ ¬S, P ∨ ¬Q ∨ ¬S, ¬S ∨ T, ¬P ∨ S, ¬R ∨ S, P,¬Q, ¬R,

která je splnitelná. (P ∧ ¬Q)⇒ R není d·sledekem.

(e) P°evodem do CNF vznikne mnoºina klauzulí

¬P ∨ ¬R, ¬P ∨ ¬Q, ¬P ∨ ¬Q, ¬P ∨ ¬S, R ∨ ¬S, P ∨R, R ∨ S, R, ¬S,

která je splnitelná. R⇒ S není d·sledekem.

28

Nahlédnutí do predikátové logiky.

Abeceda a syntaxe

V této £ásti se podíváme na roz²í°ení výrokové logiky, na tzv. predikátovou logiku, n¥kdytaké nazývanou logika prvního °ádu.

Výroková logika, i kdyº má zcela základní d·leºitost, p°ece jen postrádá v¥t²í výrazovoua formula£ní schopnost pot°ebnou nejen v matematice. Podívejme se nap°íklad na výrok

�Za kaºdým úsp¥²ným muºem stojí ambiciózní ºena.�

Výroková logika by poskytla pouze jeho pravdivostní hodnotu. Nás v²ak te¤ nezajímápravdivostní hodnota, ale vnit°ní struktura výroku. �ekneme jej v trochu jiné form¥:

�Je-li n¥kdo úsp¥²ným muºem, pak za ním stojí ambiciózní ºena.�

Te¤ je jasné, ºe má tvar implikace. M·ºeme v p°eformulaci pokro£it je²t¥ dále do tvaru,který není p°íli² elegantní, nicmén¥ více odhaluje logickou strukturu.

�Je-li x úsp¥²ný muº, pak existuje ambiciózní ºena y, stojící za muºem x.�

Krom¥ objekt· ozna£ených prom¥nnými x, y se zde vyskytují i jejich vlastnosti: �být mu-ºem�, �být ºenou� , �být úsp¥²ný� a �být ambiciózní� . Dokonce zde objevíme i relaci mezix, y, a to �objekt y stojí za objektem x� . Ozna£íme si tyto vlastnosti:

M(x) · · · x je muº,Z(x) · · · x je ºena,U(x) · · · x je úsp¥²ný,A(x) · · · x je ambiciózní,

S(y, x) · · · y stojí za x.

S tímto ozna£ením m·ºeme ud¥lat dal²í krok ve formalizaci.

�Kdykoli x spl¬uje M(x) a U(x), pak existuje y, ºe Z(y), A(y) a S(y, x).�

Zbývá nahradit slova �kdykoli� a �existuje� . K tomu slouºí tzv. kvanti�kátory, obecný ∀ aexisten£ní ∃. První znamená �pro kaºdý� nebo �pro jakýkoli� , druhý pak �existuje� . Te¤uº jsme schopni p°epsat p·vodní výrok v £ist¥ formálním tvaru:

∀x(M(x) ∧ U(x)⇒ ∃y Z(y) ∧A(y) ∧ S(y, x)

).

Vlastnosti p°i°azené objekt·m se nazývají predikáty. To je nový pojem, který výrokoválogika nemá. Krom¥ predikát· je abeceda predikátové logiky roz²í°ena o dal²í sloºky.

29


De�nice 19. Abeceda predikátové logiky je tvo°ena symboly uvedenými v následující ta-bulce.

Symbol Název Význam(, ) závorky

¬,∧,∨,⇒,⇔ logické spojky∃ existen£ní kvanti�kátor existuje ...∀ obecný kvanti�kátor pro v²echny ...

x, y, z, . . . prom¥nné prom¥nnéa, b, c, . . . konstanty individuální objektyf, g, h, . . . funk£ní symboly objektyF,G,H, . . . predikáty vlastnosti objekt·

Podíváme se na nové prvky abecedy podrobn¥ji. Význam kvanti�kátor· je jasný ztabulky. Obecný kvanti�kátor se £asto reprezentuje i frázemi �kaºdý� , �jakýkoli� nebo�kdykoli� . Existen£ní kvanti�kátor m·ºe mít krom¥ významu �existuje� i interpretaci�n¥jaký� nebo �pro n¥jaký� .

Prom¥nné zastupují jednotlivé objekty. M·ºeme je indexovat, nap°. x1, x2, . . . , takºejich je v principu nekone£n¥ mnoho. Je moºné také p°edem speci�kovat, v jaké mnoºin¥prom¥nné uvaºujeme. Tato mnoºina se pak nazývá univerzum. Nap°. °ekneme-li, ºe uni-verzum je mnoºina R reálných £ísel, pak v²echny prom¥nné budou reálná £ísla. �ekneme-li,ºe univerzum je mnoºina v²ech lidí, pak prom¥nné x, y, z, . . . budou ozna£ovat lidi. Uni-verzum je de�ni£ní obor kvanti�kátor·. Není-li univerzum p°edem ur£ené, pak je tvo°enov²emi objekty.

N¥které prvky v univerzu m·ºeme odli²it od ostatních tím, ºe jim dáme speci�ckájména. Takové objekty se nazývají konstanty. V p°ípad¥ univerza R to mohou být £ísla0, π, e atd. Je-li univerzum mnoºina lidí, pak konstanty mohou být nap°. a = Julius Caesearnebo b = Ema Destinová apod.

V matematice se pracuje s funkcemi. V predikátové logice se nazývají funk£ní symboly.Funk£ní symbol f o n prom¥nných je zobrazení

f : Un −→ U ,

kde U je univerzum. Máme-li zvoleno U = R, pak funk£ní symboly jsou nap°.

f(x) = x2, g(x, y) = x+ y, h(x1, . . . , xn) =√x21 + · · ·+ x2n, atd.

Je-li U = {lidé}, pak f(x) m·ºe ozna£ovat otce £lov¥ka x, g(x, y, z) nejchyt°ej²ího z osobx, y, z apod.

O významu predikát· jsme se zmínili v souvislosti s úvodním p°íkladem. Setkali jsmese s predikáty M , Z, U a A jedné prom¥nné a predikátem S dvou prom¥nných. Obecn¥ kekaºdému predikátu a funk£nímu symbolu je p°i°azeno £íslo n, tzv. arita. Udává, na kolikaprom¥nných p°íslu²ný symbol závisí. V p°ípad¥ n = 1 a n = 2 uºíváme názvy �unární� a�binární� . Na n-ární predikát F také m·ºeme pohlíºet jako na zobrazení,

F : Un −→ {výroky}.

Z toho je patrný základní rozdíl mezi funk£ním symbolem a predikátem. Hodnota funk£níhosymbolu je vºdy prvek univerza (tj. objekt), zatímco hodnota predikátu je výrok.

30


P°íklad. Ozna£me p°i univerzu U = {lidé} následující konstantu, funk£ní symbol a pre-dikát:

a = Rembrandt, f(x) = otec £lov¥ka x, F (x) ... x je otcem.

Pak f(a) je Rembrandt·v otec a f(f(a)) Rembrandt·v d¥d z otcovy strany. F (a) je výrok�Rembrandt je otcem� a sloºení F (f(a)) výrok �Rembrandt·v otec je otcem�. Sloºení vopa£ném po°adí f(F (a)) nemá smysl, nebo´ by ozna£ovalo £lov¥ka, který je otcem výrokuF (a). Stejn¥ nesmyslné je F (F (a)).

Pou£ení z p°ede²lého p°íkladu je, ºe predikáty nelze dosazovat do jiných predikát·nebo do funk£ních symbol·. Uvedeme si nyní p°esná syntaktická pravidla pro sestavovánísprávných formulí predikátové logiky.

De�nice 20. Term je bu¤ prom¥nná nebo konstanta nebo f(t1, . . . , tn), kde f je n-árnífunk£ní symbol a t1, . . . , tn jsou termy.

Term je ekvivalentní tomu, co jsme d°íve nazývali objekt. M·ºeme si pov²imnout, ºede�nice má podobnou induktivní strukturu jako De�nice 2 formule ve výrokové logice.Prom¥nné a konstanty bychom mohli nazývat termy nultého °ádu. Termy prvního °ádu sesestávají z term· nultého °ádu spolu s výrazy vzniklými dosazením term· nultého °ádu dofunk£ních symbol·. A tak postupujeme dále k term·m vy²²ích °ád·.

Následující krok je de�nice atomické formule. Atomická formule hraje v predikátovélogice stejnou roli jako hraje výroková prom¥nná ve výrokové logice.

De�nice 21. M¥jme n ≥ 0, termy t1, . . . , tn (ne nutn¥ r·zné) a n-ární predikát F . Pak

F (t1, . . . , tn)

je atomická formule.

Protoºe jsme dovolili, aby po£et term· v predikátu F byl i n = 0, dostali jsme vtomto krajním p°ípad¥ vlastn¥ výrokovou prom¥nnou. Z tohoto nadhledu m·ºeme výrokovéprom¥nné povaºovat za atomické formule vzniklé z 0-árního predikátu.

Nyní jsme p°ipraveni de�novat formuli v prediktové logice.

De�nice 22. Formule predikátové logiky spl¬uje jeden z následujících poºadavk·:

(i) Atomická formule je formule.

(ii) Jsou-li ϕ a ψ formule, pak (¬ϕ), (ϕ∧ψ), (ϕ∨ψ), (ϕ⇒ ψ) a (ϕ⇔ ψ) jsou formule.

(iii) Je-li ϕ formule a x prom¥nná, pak ∀xϕ a ∃xϕ jsou formule.

Stejn¥ jako ve výrokové logice u£iníme i zde úmluvu, která zabrání naduºívání závorek.Vn¥j²í závorky psát nebudeme. K preferencím vazeb mezi logickými spojkami p°idámenavíc, ºe kvanti�kátory váºí siln¥ji neº v²echny ostatní logické spojky.

Poslední poznámka se týká znaménka rovnosti, =. Nepat°í do abecedy predikátovélogiky jak je zavedena v De�nici 19. Abychom mohli rovnost uºívat m¥li bychom si ozna£itspeciální predikát nap°.

I(x, y) . . . x a y jsou totoºné.

V²ude pak místo x = y psát I(x, y). Je to jednak nepohodlné a jednak rovnítko je natolikzaºitý symbol, ºe si ho k abeced¥ predikátového logiky jednodu²e p°idáme a budeme hobez obav uºívat.

31


Cvi£ení.

(1) Který z následujících výraz· jsou formule predikátové logiky?

(a) ∀x F (a, x),

(b) ¬(∃y G(y)⇒ G(b)

),

(c) F ∧ (x)G(x),

(d) ∃x ∃x H(x, x),

(e) G(a) ∧ ∀a H(a), a je konstanta,

(f) ∀x∀y∃x (F (x, z)⇒ H(y)),

(g) ∃F F (x, y),

(h) ∃z∀x h(x, z), kde h(x, z) je funk£ní symbol.

Výsledky.

(1) (a) Je formule, jde o atomickou fomuli F (x, a) s kvanti�kátorem.

(b) Je formule, jde o negaci kvanti�kované formule G(y)⇒ G(b).

(c) Není formule, výraz (x) nemohl vzniknout povolenými operacemi.

(d) Je formule, i kdyº zopakovaní ∃x nemá p°íli² smysl, nicmén¥ neporu²uje pravidlaDe�nice 22.

(e) Není formule, kvanti�kovat p°es konstanty není povoleno.

(f) Je formule, formule (F (x, z)⇒ H(y)) je t°ikrát kvanti�kovaná.

(g) Není formule, nelze kvanti�kovat p°es predikáty.

(h) Není formule, nebo´ h(x, z) není atomická formule.

Formalizace výrok·

I v predikátové logice existuje analogie de Morganových pravidel, zde se týká zám¥ny negacea kvanti�kátoru. Je-li ϕ formule, pak

¬(∀x ϕ) je to samé jako ∃x ¬ϕ.

Analogicky,¬(∃x ϕ) je to samé jako ∀x ¬ϕ.

Následuje-li n¥kolik kvanti�kátor· za sebou, uvedená pravidla aplikujeme opakovan¥. Nap°.

¬(∀x∀y∃z ϕ

)je to samé jako ∃x∃y∀z ¬ϕ.

Podívejme se nyní nakolik je d·leºité po°adí kvanti�kátor· ve formuli. Jedná-li o kvan-ti�kátory stejného typu, lze po°adí libovoln¥ m¥nit.

∀x∀y F (x, y) je to samé jako ∀y∀x F (x, y).

32


Analogicky,∃x∃y F (x, y) je to samé jako ∃y∃x F (x, y).

V p°ípad¥ r·zných kvanti�kátor· je situace naprosto odli²ná. Krom¥ kvanti�kátor· lzetotiº zam¥nit i prom¥nné. Tím vzniknou £ty°i moºné kombinace a kaºdá z nich má obecn¥jiný význam. Jako ilustrace poslouºí následující p°íklad.

P°íklad. M¥jme univerzum U = {lidé} a predikát O(x, y) s významem �x oklamal y� .Vypí²eme si v²echny £ty°i varianty po°adí a k nim jejich významy.

∀x∃y O(x, y) Kaºdý n¥koho oklamal.

∀y∃x O(x, y) Kaºdého n¥kdo oklamal.

∃x∀y O(x, y) N¥kdo oklamal v²echny.

∃y∀x O(x, y) N¥koho oklamali v²ichni.

P°esný význam kvanti�kátoru ∃ je �existuje alespo¬ jeden� . �asto je t°eba kvanti-�kovat také formulace �existuje práv¥ jeden� nebo �existuje nejvý²e jeden� . Ukáºeme sijakou formalizaci mají taková slovní spojení. Ozna£me si predikátem V (x) n¥jakou obecnouvlastnost objektu x. Výrok �Existuje alespo¬ jeden objekt s vlastností V � má jednoduchouformalizaci,

∃x V (x).

O n¥co sloºit¥j²í je �Existuje nejvý²e jeden objekt s vlastností V � . Znamená to, ºe bu¤neexistuje ºádný objekt s vlastností V nebo existuje práv¥ jeden objekt s vlastností V .Nejefektivn¥j²í zp·sob formalizace spo£ívá v tom, ºe vylou£íme existenci dvou r·znýchobjekt· s vlastností V :

∀x∀y V (x) ∧ V (y)⇒ (x = y).

A kone£n¥ �Existuje práv¥ jeden objekt s vlastností V � je spojení obou vý²e uvedenýchvýrok·: (

∃x V (x))∧(∀x∀y V (x) ∧ V (y)⇒ (x = y)

).

Cvi£ení.

(1) Formalizujte následující výroky.

(a) Kaºdá v¥c je totoºná sama se sebou.

(b) Nic se neli²í od v²eho.

(c) V²echno je s n¥£ím totoºné.

(d) Jsou-li dv¥ v¥ci totoºné s t°etí v¥cí, jsou v²echny t°i v¥ci identické.

(e) V²echny v¥ci jsou totoºné sami se sebou práv¥, kdyº ºádná v¥c se neodli²ujesama od sebe.

(f) Existují práv¥ dva objekty.

(2) Pomocí predikátu Z(x, y): �x zná y� formalizujete v univerzu U = {lidé} následujícívýroky.

33


(a) Kaºdý n¥koho zná.

(b) N¥kdo zná v²echny.

(c) V²ichni znají jednoho.

(d) Kaºdý zná n¥koho, kdo ho nezná.

(e) N¥kdo zná v²echny, kte°í ho znají.

(f) Existuje-li n¥kdo, kdo nezná sám sebe, pak ho znají v²ichni ostatní.

(3) Pomocí uvedených predikát· a funk£ních symbol· formalizujte následující výroky.

(a) Alespo¬ dva lidé vynalezli parní stroj. (C(x): x je £lov¥k, V (x, y): x vynalezl y,a = parní stroj.)

(b) Nejvý²e dva lidé vynalezli parní stroj. (C(x): x je £lov¥k, V (x, y): x vynalezl y,a = parní stroj.)

(c) Nikdo krom¥ Dostojevského nenapsal �Zlo£in a trest� . (C(x): x je £lov¥k,N(x, y):x napsal y, a = Dostojevskij, b = Zlo£in a trest.)

(d) Nejnadan¥j²í fyzik je Einstein. (F (x): x je fyzik, N(x, y): x je nadan¥j²í neº y,e = Einstein.)

(4) Pomocí uvedených predikát· formalizujte následující výroky.

(a) Existuje v¥c leºící mezi libovolnými jinými v¥cmi. (M(x, z, y): x leºí mezi y az.)

(b) Mezi kaºdými dv¥ma v¥cmi leºí op¥t jedna v¥c. (M(x, z, y): x leºí mezi y a z.)

(c) Mezi kaºdými dv¥ma v¥cmi leºí práv¥ jedna v¥c. (M(x, z, y): x leºí mezi y a z.)

(d) N¥kdo má v²echno ²testí. (C(x): x je £lov¥k,M(x, y): x má y, K(x): x je kousek²t¥stí.)

(e) V jisté dob¥ na ºádném míst¥ nikdo neºil. (D(x): x je doba, M(x): x je místo,C(x): x je £lov¥k, Z(x, y, z): x ºil v y b¥hem z.)

(f) N¥koho lze klamat stále, v²echny lze klamat po jistou dobu, ale nelze v²echnyklamat stále. (D(x): x je doba, C(x): x je £lov¥k, K(x, y, z): x klame y b¥hemz.)

(5) Pomocí uvedených predikát· a funk£ních symbol· formalizujte následující výroky.

(a) Nejvý²e jeden £lov¥k si koupí obraz od Ra�aela, pokud je v·bec n¥jaký Ra�ael·vobraz na prodej. (C(x): x je £lov¥k, R(x): x je Rafael·v obraz, P (x): x je naprodej, K(x, y): x si koupí y.)

(b) Krom¥ Bacha a Vivaldiho existuje práv¥ jediný dal²í barokní skladatel. (b = J.S. Bach, v = A. Vivaldi, B(x): x je barokní skladatel.)

(c) Kardinál Borgia bude papeºem, bude-li volit sám sebe a budou-li ho volit ale-spo¬ dva dal²í kardinálové. (b = Alexander Borgia, K(x): x je kardinál, P (x):x je papeº, V (x, y): x volí y.)

34


(d) Portrétoval-li v·bec n¥kdo císa°e Maxmiliána, pak to mohl být práv¥ jedinýz dvojice Tizian nebo Veronese. (m = císa° Maxmilián II, t = Tizian, v =Veronese, P (x, y): x namaloval portrét y.)

(e) Aº na dva, ºádný jiný náv²t¥vník nep°i²el pozd¥. (N(x): x je náv²t¥vník, P (x):x p°i²el pozd¥.)

Výsledky.

(1) (a) ∀x (x = x).

(b) ∀x∃y (x = y).

(c) Stejné jako (b).

(d) ∀x∀y∀z (x = z) ∧ (y = z)⇒(

(x = y) ∧ (y = z) ∧ (z = x)).

(e) ∀x (x = x)⇔ ¬(∃y ¬(y = y)

), tj. ∀x (x = x)⇔ ∀y (y = y).

(f) ∃x∃y(¬(x = y) ∧ ∀z (z = x) ∨ (z = y)

).

(2) (a) ∀x∃y Z(x, y).

(b) ∃x∀y Z(x, y).

(c) ∃x∀y Z(y, x).

(d) ∀x∃y Z(x, y) ∧ ¬Z(z, x).

(e) ∃x∀y (¬Z(y, x)⇒ Z(x, y)).

(f) ∀x (¬Z(x, x)⇒ ∀y Z(y, x)).

(3) (a) ∃x∃y C(x) ∧ C(y) ∧ V (x, a) ∧ V (y, a) ∧ ¬(x = y).

(b) ∀x∀y∀z C(x) ∧ C(y) ∧ C(z) ∧ V (x, a) ∧ V (y, a) ∧ V (z, a)⇒(x = y) ∨ (y = z) ∨ (z = x).

(c) ∀x C(x) ∧N(x, b)⇒ (x = a).

(d) ∀x F (x)⇒ N(e, x).

(4) (a) ∃x∀y∀ M(x, y, z).

(b) ∀x∀y∃z M(z, x, y).

(c) ∀x∀y(∃z M(z, x, y) ∧ ∀w M(w, x, y)⇒ (z = w)

).

(d) ∃x C(x) ∧(∀y K(y)⇒M(x, y)

).

(e) ∃x D(x) ∧(∀y∀z C(y) ∧M(z)⇒ ¬Z(y, z, x).

(f)(∃x∀y∃z C(x) ∧D(y) ∧ C(z) ∧K(z, x, y)

)∧(

∃x D(x) ∧(∀y∃z C(y) ∧ C(z) ∧K(z, y, x)

))∧

¬(∀x∀y∃z D(x) ∧ C(y) ∧ C(z) ∧K(z, y, x)

).

(5) (a) ∀x(R(x) ∧ P (x)⇒

(∀y∀z C(y) ∧ C(z) ∧K(y, x) ∧K(z, x)⇒ (y = z)

)).

35


(b) B(b) ∧B(v) ∧ ∃x(B(x) ∧ ¬(x = b) ∧ ¬(x = v)∧(

∀y B(y)⇒ (y = b) ∨ (y = v) ∨ (y = x))).

(c)(V (b, b) ∧ ∀x∀y K(x) ∧K(y) ∧ V (x, b) ∧ V (y, b) ∧ ¬(x = y)

)⇒ P (b).

(d) ∀x P (x,m)⇒((x = t) ∧ ¬(x = v)

)∨((¬(x = t) ∧ (x = v)

).

(e) ∃x∃y N(x) ∧N(y) ∧ P (x) ∧ P (y) ∧ ¬(x = y)∧(∀z N(z) ∧ ¬(z = x) ∧ ¬(z = y)⇒ ¬P (z)

).

36

Date post:	20-Jan-2021
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

Výroková logika. · 2020. 1. 15. · Výroková logika. Pokud bychom m¥li de noatv pojem logika...

Documents