Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
V´yrokov´a logika Jan Hora ˇ a zemˇ Cesk´ edˇ elsk´ a univerzita
17. ˇr´ıjna 2011
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
U makl´eˇre J´ a: Dobr´y den, r´ad bych koupil nˇejak´y svˇetl´y byt. Chtˇel bych, aby mˇel dvˇe koupelny a aby byl v domˇe v´ytah. A nemˇel by b´yt nijak extr´emnˇe drah´y. Makl´ eˇr: No, v´ıte, byty se dvˇema koupelnami neb´yvaj´ı levn´e. Kaˇzdopadnˇe nˇejak´e byty, co by se V´am mohly l´ıbit, tady m´am. Ovˇsem, pokud budete trvat na v´ytahu, pak nem˚ uˇzete m´ıt dvˇe koupelny. Ale rozhodnˇe V´am nenab´ıdnu nˇeco tmav´eho, bez v´ytahu a s jednou koupelnou, tak v´aˇzen´emu z´akazn´ıkovi, jako jste Vy (n´asledov´ano slizk´ym u ´smˇevem). A jak tak kouk´am, je tu jeˇstˇe jedna dobr´a zpr´ava, vˇsechny svˇetl´e byty v nab´ıdce maj´ı dvˇe koupelny a v´ytah.
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Z´akladn´ı stavebn´ı kameny I
Definice Element´arn´ı v´yrok je vˇeta, o kter´e m´a smysl rozhodovat, jestli je pravdiv´a, a kterou ch´apeme jako nedˇeliteln´y celek.
I
Pˇr´ıklady I I I
I
M´am dnes narozeniny. 33 = 9. Uvaˇr´ım ˇsvestkov´e knedl´ıky.
Nepˇr´ıklady I I I
Jdi pryˇc. x 2 − 2 ≥ 3x + 2. Jestli budou m´ıt ˇsvestky, uvaˇr´ım ˇsvestkov´e knedl´ıky. Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Nˇekter´e v´yroky jsou sloˇzitˇejˇs´ı
I
Pˇr´ıklady I I I I
I
I I
H: P˚ ujdu dnes veˇcer s Pavlem do hospody. S: NEp˚ ujdeˇs dnes veˇcer s Pavlem do hospody. H: S: JESTLI p˚ ujdeˇs dnes veˇcer s Pavlem do hospody, PAK budou z´ıtra k veˇceˇri bramborov´e ˇsiˇsky s m´akem. (dotyˇcn´y je nem´a r´ad) H: P˚ ujdu dnes veˇcer s Pavlem do hospody A d´am si gul´aˇs se ˇsesti. S: Z˚ ustaneˇs doma NEBO pozvu na v´ıkend svoj´ı maminku. ´ Eˇ TEHDY, KDYZ ˇ H: P˚ ujdu dnes veˇcer do hospody PRAV p˚ ujde Pavel.
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Logick´e spojky
Znaˇcen´ı
N´azev
V´yznam
A0 ,
Negace Konjunkce Disjunkce Implikace Ekvivalence
Nen´ı pravda, ˇze A A a souˇcasnˇe B A nebo B Jestliˇze A, pak B A pr´avˇe tehdy, kdyˇz B
A, ¬A A∧B A∨B A⇒B A⇔B
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Skl´ad´ame v´yroky ve formule
I
Definice I I
I
I
Element´arn´ı v´yroky jsou v´yrokov´e formule. Pokud jsou A, B v´yrokov´e formule, pak jsou v´yrokov´e formule i (¬A), (A ∨ B), (A ∧ B), (A ⇒ B), (A ⇔ B). Jin´e v´yrokov´e formule nejsou.
M´ısto v´yrokov´a formule budeme obvykle ˇr´ıkat jen formule.
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pravda, nepravda, leˇz
I
Element´arn´ı v´yrok m˚ uˇze nab´yvat dvou hodnot, a to PRAVDA/NEPRAVDA, kter´e se znaˇc´ı 1/0.
I
Pravdivost sloˇzitˇejˇs´ıch v´yrokov´ych formul´ı definujeme tak, aby souhlasila s v´yznamem tˇechto spojek v bˇeˇzn´e ˇreˇci: A B A0 A ∧ B A ∨ B A ⇒ B A ⇔ B 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1
I
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady
Pˇr´ıklad Napiˇste pravdivostn´ı tabulku formule A ⇒ (B 0 ⇒ A).
Pˇr´ıklad Napiˇste pravdivostn´ı tabulku formule (A0 ⇔ B) ∧ (B 0 ∨ C )0 .
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Absolutn´ı pravda, absolutn´ı leˇz I
Definice Element´arn´ım v´yrok˚ um obsaˇzen´ym ve v´yrokov´e formuli budeme ˇr´ıkat v´yrokov´e promˇenn´e.
I
Definice Ohodnocen´ı formule je pˇriˇrazen´ı hodnoty pravda ˇci nepravda (0 ˇci 1) kaˇzd´e v´yrokov´e promˇenn´e obsaˇzen´e v t´eto formuli.
I
Definice Tautologie je formule, kter´a je pravdiv´a pˇri kaˇzd´em ohodnocen´ı (tedy m´a ve vˇsech ˇr´adc´ıch pradivostn´ı tabulky jedniˇcky).
I
Definice Kontradikce (spor) je formule, kter´a je pˇri kaˇzd´em ohodnocen´ı nepravdiv´a (m´a ve vˇsech ˇr´adc´ıch nuly). Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Nen´ı ekvivalence jako ekvivalence I
Pˇr´ıklad Napiˇste pravdivostn´ı tabulku formule (A ∨ B 0 ∨ C 0 ) ⇒ (A ∧ B) a na jej´ım z´akladˇe urˇcete, ˇci se jedn´a o tautologii (kontradikci).
I
Znaˇcen´ı Nˇekdy se tautologie/kontradikce znaˇc´ı jen symbolem 1/0.
I
Definice Formule se naz´yv´a splniteln´a, pokud existuje ohodnocen´ı, pˇri kter´em je jej´ı pravdivostn´ı hodnota 1.
I
Definice Dvˇe formule (ˇreknˇeme ϕ a ψ) se naz´yvaj´ı ekvivalentn´ı, pokud nab´yvaj´ı stejn´e pravdivostn´ı hodnoty pˇri vˇsech ohodnocen´ıch (maj´ı stejnou pravdivostn´ı tabulku). Znaˇc´ıme ϕ ≡ ψ. Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady
Pˇr´ıklad Zjistˇete, zda jsou n´asleduj´ıc´ı formule ekvivalentn´ı 1. ϕ = ¬(¬A), ψ = A, 2. ϕ = A ∧ (B ∨ C ), ψ = (A ∧ B) ∨ (A ∧ C ), 3. ϕ = A ⇒ (B ⇒ (C ⇒ (D ⇒ E ))), ψ = A ∨ B ∨ C ∨ D ∨ E , 4. ϕ = (A ∨ B)0 , ψ = A0 ∧ B 0 .
Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Jak je to s t´ım makl´eˇrem? I
A – s v´ytahem
I
B – se dvˇema koupelnami
I
C – svˇetl´y A 1 1 1 1 0 0 0 0
B 1 1 0 0 1 1 0 0
C 1 0 1 0 1 0 1 0
A ⇒ B0 0 0 1 1 1 1 1 1
(A0 ∧ B 0 ∧ C 0 )0 1 1 1 1 1 1 1 0
Jan Hora
V´ yrokov´ a logika
C ⇒ (A ∧ B) 1 1 0 1 0 1 0 1
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady ekvivalentn´ıch formul´ı I I I I I I I I I I I I
¬(¬A) ≡ A, Z´akon dvojit´e negace 0 0 ¬(A ∨ B) ≡ A ∧ B , De Morganova pravidla 0 0 ¬(A ∧ B) ≡ A ∨ B , ¬(A ⇒ B) ≡ A ∧ B 0 , (A ⇔ B) ≡ (A ∧ B) ∨ (A0 ∧ B 0 ), A ∨ A ≡ A, A ∧ A ≡ A, idempotence A ∨ B ≡ B ∨ A, A ∧ B ≡ B ∧ A, komutativita (A ∨ B) ∨ C ≡ A ∨ (B ∨ C ) ≡ A ∨ B ∨ C , asociativita A ∧ (B ∨ C ) ≡ (A ∧ B) ∨ (A ∧ C ), distributivita 0 0 A ∧ A ≡ 0, A ∨ A ≡ 1, A ∨ 1 ≡ 1, A ∨ 0 ≡ A, A ∧ 1 ≡ A, A ∧ 0 ≡ 0. Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Disjunkce konjunkc´ı, konjunkce disjunkc´ı I
Definice V´yrokov´e promˇenn´e a jejich negace se souhrnnˇe naz´yvaj´ı liter´aly.
I
Definice Formule je v disjunktivn´ım tvaru (disjunktivn´ı norm´aln´ı formˇe – DNF), pokud je disjunkc´ı konjunkc´ı liter´al˚ u.
I
Definice Formule je v u ´pln´em disjunktivn´ım tvaru, pokud je v disjunktivn´ım tvaru a kaˇzd´a konjunkce obsahuje vˇsechny v´yrokov´e promˇenn´e nebo jejich negace.
I
Definice Formule je v konjunktivn´ım tvaru (konjunktivn´ı norm´aln´ı formˇe – CNF), pokud je konjunkc´ı disjunkc´ı liter´al˚ u. Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady Pˇr´ıklad Pˇreved’te do disjunktivn´ıho tvaru 1. (A0 ∧ (B 0 ∨ A)), 2. (A0 ⇒ (B ∧ C 0 ))0 , 3. A0 ⇔ (B ∨ C 0 ).
Pˇr´ıklad Pˇreved’te do konjunktivn´ıho tvaru 1. A ∨ (A0 ∧ B 0 )0 , 2. (A0 ⇒ (B ∧ C 0 ))0 , 3. A0 ⇔ B. Jan Hora
V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady Pˇr´ıklad Pˇreved’te do u ´pln´eho disjunktivn´ıho tvaru 1. A ∨ (A0 ∧ B), 2. (A ∧ B) ∨ (B ∧ C 0 ), 3. (A0 ⇒ B 0 ) ∨ (B ∧ C 0 ).
Pˇr´ıklad Napiˇste jakoukoli formuli ϕ s n´asleduj´ıc´ı pravdivostn´ı tabulkou A 1 1 0 0 Jan Hora
B 1 0 1 0
ϕ 1 1 0 1 V´ yrokov´ a logika
Jak jsem potkal logiku Z´ akladn´ı pojmy Pˇrevod formule do (´ upln´ eho) disjunktivn´ıho tvaru
Pˇr´ıklady Pˇr´ıklad Napiˇste jakoukoli formuli ϕ s n´asleduj´ıc´ı pravdivostn´ı tabulkou A 1 1 1 1 0 0 0 0
B 1 1 0 0 1 1 0 0
Jan Hora
C 1 0 1 0 1 0 1 0
ϕ 0 1 1 0 1 0 0 1
V´ yrokov´ a logika
