semestr jaro 2011
IB101
Vyrokov ´ a´ logika
´ • teorie logick´ych spojek chapan´ ych jako pravdivostn´ı funkce
• zab´yva´ se zpusoby tvoˇren´ı v´yroku˚ pomoc´ı spojek a vztahy mezi pravdivost´ı ˚ ruzn´ ˚ ych v´yroku˚
• pouˇz´ıva´ specifick´y jazyk sloˇzen´y z v´yrokov´ych symbolu, ˚ logick´ych spojek a ´ zavorek
1/??
semestr jaro 2011
IB101
´ Zakladn´ ı pojmy – vyrok ´
• v´yrok : tvrzen´ı nebo jazykov´y v´yraz, o jehoˇz (ne)pravdivosti lze uvaˇzovat • syntakticka´ klasifikace v´yroku: ˚ ´ ´ a´ jeho vlastn´ı – jednoduch´y v´yrok : neobsahuje zˇ adnou logickou spojku (ˇzadn ´ nen´ı v´yrokem); cˇ ast pˇr´ıklad: prˇs´ı – sloˇzen´y v´yrok : obsahuje alesponˇ jednu logickou spojku; ´ prˇs´ı je jednoduch´ym v´yrokem, pˇr´ıklad: nen´ı pravda, zˇ e prˇs´ı (vlastn´ı cˇ ast nen´ı pravda, zˇ e je logickou spojkou)
2/??
semestr jaro 2011
IB101
Vyrok ´ – pˇr´ıklady
• pˇr´ıklady v´yroku: ˚ ˇ hodin – je pet –
2+3=5
– pokud nenap´ısˇ eˇs ukoly a neuklid´ısˇ , nepujdeme do kina ´ ˚
• pˇr´ıklady v´yrazu, ˚ ktere´ nejsou v´yroky: – kolik je hodin? –
2+3
– napiˇs ukoly a uklidˇ ´
3/??
semestr jaro 2011
IB101
´ Zakladn´ ı pojmy – pravdivostn´ı funkce
´ ı) pravdivostn´ı funkce: funkce pˇriˇrazuj´ıc´ı n-tic´ım pravdivostn´ıch hodnot • (n-arn´ ˇ nekterou pravdivostn´ı hodnotu pravda (1, true apod.) nebo nepravda (0, false apod.) ´ jazyce a; definujme ji • pˇr´ıklad: oznaˇcme funkci dvou argumentu˚ v pˇrirozenem ˇ zˇ e oba argumenty (v´yroky) tak, zˇ e jej´ı hodnota bude 1 (pravda) v pˇr´ıpade, ´ V ostatn´ıch pˇr´ıpadech (alesponˇ jeden argument bude budou pravdive. ´ funkce 0. nepravdiv´y) bude hodnota teto Petr je doma a Pavel odjel na hory. ´ pak hodnota Jsou-li v´yroky Petr je doma i Pavel odjel na hory pravdive, funkce a je v tomto pˇr´ıpadeˇ 1. Pokud je napˇr´ıklad v´yrok Pavel odjel na hory nepravdiv´y, je hodnota funkce 0.
4/??
semestr jaro 2011
IB101
Spojky vyrokov ´ e´ logiky I
´ ´ • pravdivostn´ı hodnota sloˇzeneho v´yroku je jednoznaˇcneˇ dana pravdivostn´ımi hodnotami jeho sloˇzek ´ ı spojka je funkc´ı pˇriˇrazuj´ıc´ı uspoˇradan ´ • n-arn´ e´ n-tici pravdivostn´ıch hodnot urˇcitou pravdivostn´ı hodnotu ´ ˇ • poˇcet vˇsech ruzn´ ych n-tic) je vzhledem ke dvema ˚ ych argumentu˚ (uspoˇradan´ ´ roven 2n pravdivostn´ım hodnotam ´ ı funkce (n = 1) jsou uspoˇradan ´ Pˇr.: moˇzne´ argumenty pro unarn´ e´ ”jednice” ´ ı funkce (n = 2) existuj´ı cˇ tyˇri (1), (0); jejich poˇcet je 21 = 2. Pro binarn´ ´ (22 = 4) moˇzne´ argumenty – uspoˇradan e´ dvojice (0, 0), (0, 1), (1, 0), ´ ı funkce existuje osm moˇzn´ych argumentu˚ atd. (1, 1). Pro ternarn´
5/??
semestr jaro 2011
IB101
Spojky vyrokov ´ e´ logiky II
´ ı spojku jako totaln´ ´ ı pravdivostn´ı funkci lze zadat pravdivostn´ı • kaˇzdou n-arn´ ´ ıch – kaˇzdemu ´ ´ ´ tabulkou o 2n ˇradc´ moˇznemu argumentu (uspoˇradan e´ n-tici) ˇ a´ pravdivostn´ı hodnota je pˇriˇrazena nejak Pˇr.:
p, q – symboly reprezentuj´ıc´ı argumenty, F – definovana´ spojka p
q
F
1
1
0
1
0
1
0
1
1
0
0
0 2n
´ ´ ıch spojek je 2 ; unarn´ ´ ı jsou cˇ tyˇri, binarn´ ´ ıch • poˇcet vzajemn eˇ ruzn´ ˚ ych n-arn´ ´ ıch 256 atd. je 16, ternarn´
6/??
semestr jaro 2011
IB101
´ ı a unarn´ ´ ı vyrokov Nularn´ ´ e´ spojky ´ ı pravdivostn´ı funkce (nezavisl ´ ´ em ´ argumentu) jsou konstanty • nularn´ e´ na zˇ adn ´ 0, 1 odpov´ıdaj´ıc´ı pravdivostn´ım hodnotam ´ ı (jednoargumentove) ´ spojky: • unarn´
p
F1
F2
F3
F4
1
1
1
0
0
0
1
0
1
0
´ Uvedene´ spojky naz´yvame takto: ´ ı verum, F1 – unarn´ ´ ı projekce p, F2 – unarn´ ´ ı unarn´ ´ ı funkce F3 – negace p (ozn. ¬p); jedina´ netrivialn´ ´ ı falsum. F4 – unarn´
7/??
semestr jaro 2011
IB101
´ ı vyrokov Binarn´ ´ e´ spojky ∨, ∧
• ∨ – disjunkce (alternativa; a nebo, OR) ´ ˇ AND) ∧ – konjunkce (a zarove n, p
q
∨
∧
1
1
1
1
1
0
1
0
0
1
1
0
0
0
0
0
ˇ zneˇ se pouˇz´ıva´ infixov´y zapis ´ • beˇ (napˇr. p ∨ q ) ´ ı na poˇrad´ı argumentu˚ • spojky ∧, ∨ jsou komutativn´ı – hodnota funkce nezavis´
8/??
semestr jaro 2011
IB101
´ ı vyrokov Binarn´ ´ e´ spojky ⇒, ⇔
• ⇒ – implikace (jestliˇze p, pak q ; pˇredpoklad ⇒ dusledek) ˚ ´ eˇ tehdy, kdyˇz; iff – if and only if) ⇔ – ekvivalence (prav p
q
⇒
⇔
1
1
1
1
1
0
0
0
0
1
1
0
0
0
1
1
• ⇔ je komutativn´ı, ⇒ ne • p ⇒ q : inverzn´ı ¬p ⇒ ¬q , konverzn´ı q ⇒ p, kontrapozitivn´ı ¬q ⇒ ¬p
9/??
semestr jaro 2011
IB101
ˇ ı binarn´ ´ ı vyrokov Dals´ ´ e´ spojky
´ • spojky zaj´ımave´ z informatickeho hlediska: – XOR – nonekvivalence, negace ekvivalence (nebo ve vyluˇcovac´ım smyslu; eXclusive OR) – negace konjunkce (Shefferova funkce, NAND) – negace disjunkce (Nicodova funkce, NOR)
• dalˇs´ı spojky: – negace implikace (inhibice) ´ ı verum a falsum – binarn´ ´ ı projekce p, q a jejich negac´ı – binarn´ – opaˇcna´ (konverzn´ı; q
⇒ p) implikace a jej´ı negace
10/??
semestr jaro 2011
IB101
Symbolicky´ jazyk vyrokov ´ e´ logiky • abeceda 1. v´yrokove´ symboly:
p, q, r, s, . . ., pˇr´ıpadneˇ p1 , p2 , p3 . . .
2. symboly pro spojky: 3. pomocne´ symboly:
¬, ∨, ∧, ⇒, ⇔
(, )
´ eˇ utvoˇrena´ formule (dale ´ jen formule) • spravn 1. kaˇzd´y v´yrokov´y symbol je formule (tzv. atomicka´ formule) 2. je-li v´yraz A formule, pak ¬(A) je formule 3. jsou-li v´yrazy A, B formule, pak take´ (A) ∨ (B), (A) ∧ (B),
(A) ⇒ (B), (A) ⇔ (B) jsou formule ´ 4. nic jineho nen´ı formule ´ ´ • zavorkov a´ konvence: zavorky lze vynechat, pokud to nen´ı na ujmu ´ jednoznaˇcnosti formule
11/??
semestr jaro 2011
IB101
Jazyk vyrokov ´ e´ logiky – pˇr´ıklady
Pˇr´ıklad 1:
• v´yrazy p, q, r jsou formulemi dle bodu 1 definice formule ´ • v´yrazy ¬p, ¬¬q jsou formulemi dle bodu 2 (a zavorkov e´ konvence)
• p ∧ q, ¬¬q ∨ r, ¬p ⇒ r jsou formulemi dle bodu 3 • (p ∧ q) ⇒ (¬¬q ∨ r) je formul´ı dle bodu 3 ˇ z formul´ı dle bodu 3 • ((p ∧ q) ⇒ (¬¬q ∨ r)) ⇔ (¬p ⇒ r) je rovneˇ Pˇr´ıklad 2:
• v´yrazy pqr, ⇔ r, p∨ nejsou formulemi
12/??
semestr jaro 2011
IB101
´ jazyce Reprezentace vyrok ´ u˚ v pˇrirozenem
Pˇr´ıklad: ˇ ´ • veta: Pokud rychle nap´ısˇ eˇs ukoly a venku bude hezky, pujdeme na prochazku ´ ˚ ˇ nebo pojedeme na koupaliˇste.
• oznaˇcen´ı jednoduch´ych v´yroku˚ v´yrokov´ymi symboly: p – rychle nap´ısˇ eˇs ukoly ´ q – venku bude hezky ´ r – pujdeme na prochazku ˚ s – pojedeme na koupaliˇsteˇ ´ jazyce: (p ∧ q) ⇒ (r ∨ s) • reprezentace v symbolickem ´ • poznamka: pˇrevod nemus´ı b´yt vˇzdy jednoznaˇcn´y
13/??
semestr jaro 2011
IB101
´ Semantika vyrokov ´ e´ logiky • Pravdivostn´ı ohodnocen´ı (interpretace) je funkce pˇriˇrazuj´ıc´ı vˇsem atomick´ym ´ ´ formul´ım dane´ uvahy pravdivostn´ı hodnoty (tj. kaˇzdemu v´yrokovemu symbolu ´ pˇriˇrad´ı 0 nebo 1). Valuace je rozˇs´ıˇren´ı interpretace z atomick´ych na vˇsechny formule dle tabulky pro v´yrokove´ spojky (pˇriˇrad´ı 0 nebo 1 napˇr. i p ∧ ¬q ). ˇ • Interpretace I splnuje formuli A (formule je pravdiva´ v I , resp. odpov´ıdaj´ıc´ı valuace I 0 (A) = 1), pokud 1.
A je v´yrokov´y symbol a I(A) = 1
2.
ˇ A je ¬B a I nesplnuje B , resp. I 0 (B) = 0
3.
ˇ A je tvaru B ∧ C a I splnuje B i C , resp. I 0 (B) = I 0 (C) = 1
4.
ˇ A je B ∨ C a I splnuje B nebo C , resp. I 0 (B) = 1 nebo I 0 (C) = 1
5.
ˇ ˇ A je tvaru B ⇒ C a I nesplnuje B nebo splnuje C , resp. I 0 (B) = 0 nebo I 0 (C) = 1
6.
ˇ ˇ A je B ⇔ C a I splnuje B i C nebo I nesplnuje B i C , resp. I 0 (B) = I 0 (C)
14/??
semestr jaro 2011
IB101
Interpretace – pˇr´ıklady I
Pˇr´ıklad 1: ˇ Mejme formuli ((p ∧ q)
´ ⇒ (¬¬q ∨ r)) ⇔ (¬p ⇒ r) a nasleduj´ ıc´ı interpretaci I : I(p) = 1, I(q) = 0, I(r) = 1 ˇ ˇ • dle bodu 1 I splnuje p a r, nesplnuje q ˇ • dle bodu 2 I nesplnuje ¬¬q a ¬p ˇ • dle bodu 3 I nesplnuje p∧q ˇ • dle bodu 4 I splnuje ¬¬q ∨ r ˇ • dle bodu 5 I splnuje ¬p ⇒ r a (p ∧ q) ⇒ (¬¬q ∨ r) ˇ • dle bodu 6 I splnuje ((p ∧ q) ⇒ (¬¬q ∨ r)) ⇔ (¬p ⇒ r)
15/??
semestr jaro 2011
IB101
Interpretace – pˇr´ıklady II Pˇr´ıklad 2a: ˇ Mejme formuli (¬p ∧ q)
⇒ p a interpretaci I : I(p) = 0, I(q) = 1
ˇ ˇ • dle bodu 1 I splnuje q a nesplnuje p ˇ • dle bodu 2 I splnuje ¬p ˇ • dle bodu 3 I splnuje ¬p ∧ q ˇ • dle bodu 5 I nesplnuje (¬p ∧ q) ⇒ p Pˇr´ıklad 2b: ˇ ´ z formuli a jinou interpretaci I1 : I1 (p) Mejme tuteˇ
= 1, I1 (q) = 0
ˇ ˇ • dle bodu 1 I1 splnuje p a nesplnuje q ˇ • dle bodu 2 I1 nesplnuje ¬p ˇ • dle bodu 3 I1 nesplnuje ¬p ∧ q ˇ • dle bodu 5 I1 splnuje (¬p ∧ q) ⇒ p
16/??
semestr jaro 2011
IB101
´ ı Modely, logicke´ vyplyv ´ an´
ˇ ˇ • Mejme formuli ¬p ∨ p; vˇsechny moˇzne´ interpretace (existuj´ı dve: ˇ ı tuto formuli. I(p) = 1, I1 (p) = 0) splnuj´ ˇ ana ´ Formule, ktera´ je splnov kaˇzdou interpretac´ı, se naz´yva´ tautologie. ˇ ana ´ ´ • Formule ¬p ∧ p nen´ı splnov zˇ adnou z moˇzn´ych interpretac´ı; takove´ ´ formule naz´yvame kontradikce. ´ je-li splnov ˇ ana ´ • Formule A je splnitelna, alesponˇ jednou interpretac´ı. Tuto interpretaci oznaˇcujeme jako model formule A. ´ pokud existuje interpretace splnuj´ ˇ ıc´ı kaˇzdou • Mnoˇzina formul´ı T je splnitelna, ´ formuli z T. Tuto interpretaci naz´yvame modelem mnoˇziny T. ´ • Formule A logicky vypl´yva´ (na zaklad eˇ v´yrok. logiky) z mnoˇziny T, pokud pro ˇ kaˇzd´y model I mnoˇziny T I splnuje A. Zapisujeme T |= A.
17/??
semestr jaro 2011
IB101
Tautologie ´ ´ • symbolick´y zapis |= A (logicky vypl´yvaj´ı z prazdn e´ mnoˇziny formul´ı)
• tautologi´ı existuje nekoneˇcneˇ mnoho Pˇrehled vybranych ´ tautologi´ı I
• tautologie s jedin´ym v´yrokov´ym symbolem: ´ p ⇒ p (zakon totoˇznosti) ´ p ∨ ¬p (zakon vylouˇcen´ı tˇret´ıho) ´ ¬(p ∧ ¬p) (zakon sporu) ´ p ⇔ ¬¬p (zakon dvoj´ı negace) ˇ • nekter e´ zobrazovac´ı tautologie: (p ∧ q) ⇔ ¬(¬p ∨ ¬q) (p ∨ q) ⇔ ¬(¬p ∧ ¬q) (p ⇒ q) ⇔ (¬p ∨ q) (p ⇔ q) ⇔ ((¬p ∨ q) ∧ (p ∨ ¬q))
18/??
semestr jaro 2011
IB101
Pˇrehled vybranych ´ tautologi´ı II ´ • algebraicko-logicke´ zakony: komutativn´ı:
(p ∧ q) ⇔ (q ∧ p) (p ∨ q) ⇔ (q ∨ p) (p ⇔ q) ⇔ (q ⇔ p) asociativn´ı:
((p ∧ q) ∧ r) ⇔ (p ∧ (q ∧ r)) ((p ∨ q) ∨ r) ⇔ (p ∨ (q ∨ r)) ((p ⇔ q) ⇔ r) ⇔ (p ⇔ (q ⇔ r)) distributivn´ı:
(p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r)) (p ∨ (q ∧ r)) ⇔ ((p ∨ q) ∧ (p ∨ r))
19/??
semestr jaro 2011
IB101
Pˇrehled vybranych ´ tautologi´ı III
• charakteristiky implikace: p ⇒ (q ⇒ p) (z. simplifikace) (p ∧ ¬p) ⇒ q (p ⇒ q) ⇔ (¬q ⇒ ¬p) (z. kontrapozice) ´ ı premis) (p ⇒ (q ⇒ r)) ⇔ ((p ∧ q) ⇒ r) (sluˇcovan´ ´ ena ˇ (p ⇒ (q ⇒ r)) ⇔ (q ⇒ (p ⇒ r)) (zam premis) ((p ⇒ q) ∧ (q ⇒ r)) ⇔ (p ⇒ r) (tranzitivita) • transformaˇcn´ı tautologie: idempotence:
(p ∧ p) ⇔ p; (p ∨ p) ⇔ p absorbce:
(p ∧ (p ∨ q)) ⇔ p; (p ∨ (p ∧ q)) ⇔ p ´ de Morganovy zakony:
¬(p ∧ q) ⇔ (¬p ∨ ¬q); ¬(p ∨ q) ⇔ (¬p ∧ ¬q)
20/??
semestr jaro 2011
IB101
ˇ Nekter e´ vlastnosti tautologi´ı I
´ ˇ o implikaci (semantick´ • Veta y modus ponens): jsou-li formule A a A ⇒ B tautologie, pak i B je tautologie. Dukaz: sporem. Nechˇt plat´ı |= A a |= A ⇒ B . Nechˇt existuje interpretace ˚ ˇ ıc´ı B (tj. B nen´ı tautologie). I splnuje ˇ I (pro v´yr. symboly z A a B ) nesplnuj´ ˇ ˇ A (protoˇze A je tautologie). Tedy I nesplnuje A ⇒ B , neboˇt splnuje Aa ˇ ´ ame ´ nesplnuje B . Dostav spor s pˇredpokladem, zˇ e A ⇒ B je tautologie. ˇ umoˇznuje ˇ ´ Pozn.: veta z´ıskat z tautologi´ı daneho tvaru dalˇs´ı tautologie. ˇ o implikaci: • aplikace vety V´ıme, zˇ e p ⇒ p a (p ⇒ p) ⇒ (q ⇒ (p ⇒ p)) jsou tautologie. Pak take´ q ⇒ (p ⇒ p) je tautologie.
21/??
semestr jaro 2011
IB101
ˇ Nekter e´ vlastnosti tautologi´ı II
´ ˇ ˇ o dedukci (semantick • Veta a´ varianta): mejme formule A1 , A2 , . . . An , B , ´ eˇ kdyˇz kde n ≥ 1. Pak plat´ı, zˇ e A1 , A2 , . . . An−1 , An |= B prav A1 , A2 , . . . An−1 |= An ⇒ B . ˇ ekvivalence sporem. Dukaz: oba smery ˚ ˇ umoˇznuje ˇ ´ et ˇ platne´ usudky Pozn.: veta (opakovan´ym pouˇzit´ım) pˇrevad na ´ tautologie a naopak. ˇ o dedukci: • aplikace vety ˇ o dedukci V´ıme, zˇ e plat´ı p ∨ q, p ∧ ¬q |= ¬q . Pak dvoj´ı aplikac´ı vety dostaneme tautologii |= (p ∨ q) ⇒ ((p ∧ ¬q) ⇒ ¬q). ˇ rte, zˇ e jde skuteˇcneˇ o tautologii. Oveˇ
22/??
semestr jaro 2011
IB101
Klasifikace formul´ı vyrokov ´ e´ logiky I ˇ ı pravdivosti formul´ı pro vˇsechny moˇzne´ • tabulkova´ metoda – zjiˇsten´ interpretace Pˇr´ıklad 1: formule (p ∨ q)
⇔ (p ∧ q)
p
q
(p
∨
q)
⇔
(p
∧
q)
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
´ (podformul´ıch) dane´ formule (v´yrok. symboly, • vyhodnocen´ı: po sloˇzkach negace,. . . ,cela´ formule) ´ ´ • zapis pravdivostn´ı hodnoty: v ˇradku s pˇr´ısluˇsnou interpretac´ı pod vyhodnocovanou spojku (v´yr. symbol)
23/??
semestr jaro 2011
IB101
Klasifikace formul´ı vyrokov ´ e´ logiky II
Pˇr´ıklad 2: formule (p ∧ ¬p)
p
p
∧
¬p
1
1
0
0
0
0
0
1
• dle v´ysledn´ych pravdivostn´ıch hodnot cele´ formule (tuˇcneˇ vyznaˇcen´y sloupec ´ v pˇredchoz´ıch tabulkach) rozliˇsujeme – kontradikce: vˇsechny v´ysledne´ pravdivostn´ı hodnoty rovny nule – splnitelne´ formule: alesponˇ jedna v´ysledna´ pravdivostn´ı hodnota rovna ´ modely jsou interpretace uvedene´ v ˇradc´ ´ ıch, kde je v´ysledna´ jedne; pravdivostn´ı hodnota formule rovna jedne´ – tautologie: vˇsechny v´ysledne´ pravdivostn´ı hodnoty rovny jedne´
24/??
semestr jaro 2011
IB101
ˇ ı typy uloh Dals´ ´ I ˇ zda je mnoˇzina formul´ı T = {p ∨ q, p ∧ ¬q} splnitelna. ´ • Zjistete,
p
q
p∨q
p ∧ ¬q
1
1
1
0
1
0
1
1
0
1
1
0
0
0
0
0
´ jedin´ym modelem je interpretace uvedena´ na vyznaˇcenem ´ T je splnitelna, ˇradku ´ tabulky.
• Vypl´yva´ formule ¬q logicky z mnoˇziny T? ´ jazyce) (+ stejne´ typy uloh formulovan´ych v pˇrirozenem ´ ´ P´ısˇ eme Ano, pro vˇsechny modely T (viz pˇredch. tab.) je ¬q pravdiva. ´ ´ ´ p ∨ q, p ∧ ¬q |= ¬q (schema usudku platneho na zaklad eˇ v´yrokove´ logiky). ´
25/??
semestr jaro 2011
IB101
ˇ ı typy uloh Dals´ ´ II
ˇ ren´ı tautologi´ı tvaru implikace metodou protipˇr´ıkladu: ⇒ je nepravdiva´ • oveˇ pouze pro pravdiv´y pˇredpoklad a nepravdiv´y dusledek. Pro tuto variantu – za ˚ ˇ r´ıme pˇredpokladu nepravdivosti dusledku – pro pˇr´ısluˇsne´ interpretace oveˇ ˚ (ne)pravdivost pˇredpokladu.
• pˇr´ıklad: p ⇒ (q ⇒ p) – pˇredpoklad:
´ q ⇒ p ne p pravdiva,
– jedina´ moˇznost nepravdivosti q
´ p ne ⇒ p: q pravdiva,
– spor s pˇredpokladem pravdivosti p
26/??
semestr jaro 2011
IB101
´ ´ spojek vyrokov Upln y´ system ´ e´ logiky
´ ´ ´ rit libovolnou • prostˇrednictv´ım systemu spojek {¬, ∧, ∨} jsme dokazali vyjadˇ ´ pravdivostn´ı funkci (spojku); lib. mnoˇzinu spojek s touto vlastnost´ı naz´yvame ´ upln´ spojek ´ ym systemem ´ • upln´ spojek jsou napˇr´ıklad {¬, ∧}, {¬, ∨}, {¬, ⇒} ´ ymi systemy ´ ´ rit • existuj´ı i jednoprvkove´ upln lib. pravdivostn´ı funkci lze vyjadˇ ´ e´ systemy: pouze pomoc´ı Shefferovy funkce (negace konjunkce, ozn. | ), stejnou vlastnost ma´ i Nicodova funkce (negace disjunkce, ozn. .|.) Pˇr. (p ∨ q) ⇔ ((p | p) | (q | q))
27/??
semestr jaro 2011
IB101
Dualita konjunkce a disjunkce I ´ ´ • vztah mezi ∧ a ∨ naz´yvame dualita, tyto spojky jsou vzajemn eˇ ´ ı komplementarn´ ˇ o dualiteˇ I: nechˇt A, B obsahuj´ı pouze spojky ¬, ∧, ∨. Nechˇt A0 , B 0 • Veta ´ enou ˇ ´ ´ ı formou vzniknou z A, B zam spojek ∧ a ∨ (formuli A0 naz´yvame dualn´ k A). Pak plat´ı: ´ eˇ kdyˇz |= ¬A0 (resp. |= ¬A prav ´ eˇ kdyˇz |= A0 ) 1. |= A prav 2. pokud |= A ⇒ B , pak |= B 0 ⇒ A0 3. pokud |= A ⇔ B , pak |= B 0 ⇔ A0 ˇ (bod 3): • pˇr´ıklad vyuˇzit´ı vety A = p ∧ (q ∨ r), B = (p ∧ q) ∨ (p ∧ r) A0 = p ∨ (q ∧ r), B 0 = (p ∨ q) ∧ (p ∨ r) v´ıme, zˇ e |= (p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r)); pak take´ |= (p ∨ (q ∧ r)) ⇔ ((p ∨ q) ∧ (p ∨ r))
28/??
semestr jaro 2011
IB101
Dualita konjunkce a disjunkce II ˇ o dualiteˇ II: nechˇt A, B obsahuj´ı pouze spojky ¬, ∧, ∨. Nechˇt A∗ , B ∗ • Veta ´ enou ˇ vzniknou z A, B zam spojek ∧ a ∨ a nahrazen´ım vˇsech atomick´ych formul´ı jejich negacemi (se zjednoduˇsen´ım ¬¬). Pak plat´ı: 1. |= ¬A ⇔ A∗ 2. pokud |= A ⇒ B , pak |= B ∗ ⇒ A∗ 3. pokud |= A ⇔ B , pak |= A∗ ⇔ B ∗
• pˇr´ıklad konstrukce A∗ : A = (p ∧ q) ∨ (p ∧ ¬r) A∗ = (¬p ∨ ¬q) ∧ (¬p ∨ r) ˇ rme, zˇ e A∗ je ekvivalentn´ı ¬A: oveˇ ¬A = ¬((p ∧ q) ∨ (p ∧ ¬r)) ⇔ ¬(p ∧ q) ∧ ¬(p ∧ ¬r) ⇔ (¬p ∨ ¬q) ∧ (¬p ∨ r) = A∗
29/??
