1
Formule predik´ atov´ e logiky
Jazyk predik´atov´e logiky L se skl´ ad´a z logick´ ych symbol˚ u (objektov´e promˇenn´e, logick´e spojky, kvantifik´ atory), mimologick´ ych symbol˚ u (predik´ atov´e, funkˇcn´ı a konstatn´ı symboly) a pomocn´ ych symbol˚ u (z´avorky a ˇc´arka). Termy jazyka L (L-termy) se definuj´ı induktivnˇe pomoc´ı objektov´ ych promˇenn´ ych, konstantn´ıch a funˇcn´ıch symbol˚ u takto: (1) kaˇzd´ a promˇenn´a a konstatn´ı symbol je term; (2) pokud t1 , . . . , tn jsou termy a f je n-´arn´ı funkˇcn´ı symbol, pak f (t1 , . . . , tn ) je term. Mˇejme n-´arn´ı predik´atov´ y symbol P a termy t1 , . . . , tn . Pak P (t1 , . . . , tn ) je atomick´ a formule. Pojem formule se opˇet definuje induktivnˇe takto: (1) kaˇzd´ a atomick´ a formule je formule; (2) pokud ψ je formule, pak ¬ψ, ∀xψ, ∃xψ jsou formule; (3) pokud ϕ a ψ jsou formule, pak ϕ ◦ ψ je formule pro ◦ ∈ {∧, ∨, ⇒, ⇔}. Pˇ r´ıklad 1.1 Pro n´asleduj´ıc´ı formule napiˇste jak´e termy se v nich nach´azej´ı a vyjmenujte vˇsechny jej´ı podformule. 1. ϕ = ¬∃x∀y((x · (y + y) ≤ x + y) ∧ (x = y + 1)), jazyk formule ϕ obsahuje konstatn´ı symbol 1, bin´ arn´ı funkˇcn´ı symboly +, · a bin´ arn´ı predik´atov´e symboly ≤, =. 2. ψ = ∀x(P (f (c), g(f (x), x)) ⇒ ∃yQ(g(f (f (x)), f (y)), c, c)), jazyk formule ψ obsahuje konstatn´ı symbol c, un´ arn´ı funkˇcn´ı symbol f , bin´ arn´ı funkˇcn´ı symbol g, bin´ arn´ı predik´atov´ y symbol P a tern´arn´ı predik´atov´ y symbol Q. ˇ sen´ı Reˇ 1. Termy vyskytuj´ıc´ı se ve formuli ϕ jsou argumenty predik´atov´ ych symbol˚ u, tj. x·(y +y), x+y, x, y + 1. Podformule ϕ jsou x · (y + y) ≤ x + y, x = y + 1, (x · (y + y) ≤ x + y) ∧ (x = y + 1), ∀y((x · (y + y) ≤ x + y) ∧ (x = y + 1)), ϕ. 2. Termy vyskytuj´ıc´ı se ve formuli ψ jsou argumenty predik´atov´ ych symbol˚ u, tj. f (c), g(f (x), x), g(f (f (x)), f (y)), c. Podformule ψ jsou P (f (c), g(f (x), y)), Q(g(f (f (x)), f (y)), c, c), ∃yQ(g(f (f (x)), f (y)), c, c), P (f (c), g(f (x), x)) ⇒ ∃yQ(g(f (f (x)), f (y)), c, c), ψ. Pˇ r´ıklad 1.2 Urˇcete, kter´e z n´asleduj´ıc´ıch formul´ı jsou sentence. U kaˇzd´eho v´ yskytu promˇenn´e uved’te, jestli je voln´ y nebo v´ azan´ y. 1. ϕ = ∀y∃z(∃xP (y, x, z) ∨ ¬P (f (x), f (y), z)), kde P je tern´arn´ı predik´atov´ y symbol a f un´ arn´ı funkˇcn´ı symbol. 2. ϕ = ¬∀xQ(x) ⇔ ∀y∃x(¬Q(x) ⇒ R(x, y)), kde Q je un´ arn´ı predik´atov´ y symbol, R je bin´ arn´ı predik´atov´ y symbol. 3. ϕ = Q(a) ⇒ (R(g(f (a), b), b) ∧ ¬Q(b)), kde a, b jsou konstatn´ı symboly, Q je un´ arn´ı predik´ atov´ y symbol, R je bin´ arn´ı predik´atov´ y symbol a f je un´ arn´ı funkˇcn´ı symbol. ˇ sen´ı Reˇ 1. V tomto pˇr´ıpadˇe vˇsechny v´ yskyty promˇenn´ ych y, z jsou v´ azan´e. Promˇenn´a x m´a prvn´ı dva v´ yskyty v´ azan´e a posledn´ı voln´ y. Protoˇze formule ϕ obsahuje alespoˇ n jeden voln´ y v´ yskyt, ϕ nen´ı sentence. 2. V tomto pˇr´ıpadˇe jsou vˇsechny v´ yskyty v´ azan´e, tud´ıˇz je ϕ sentence. 3. V posledn´ım pˇr´ıpadˇe ϕ neobsahuje ˇz´adn´e voln´e v´ yskyty, protoˇze neobsahuje ˇz´adn´e promˇenn´e. Tud´ıˇz je ϕ sentence.
1
2
Pravdivost formul´ı ve struktuˇ re
Neˇz uvedeme konkr´etn´ı pˇr´ıklady, zopakujme si definici pravdivosti ve struktuˇre. Necht’ L je nˇejak´ y jazyk. Strukturu A pro jazyk L (L-struktura) tvoˇr´ı mnoˇzina prvk˚ u A (zvan´a univerzum) a zobrazen´ı, kter´e pˇriˇrazuje kaˇzd´emu konstantn´ımu symbolu a ∈ L prvek aA ∈ A, kaˇzd´emu n-´arn´ımu predik´atov´emu symbolu P ∈ L pˇriˇrad´ı n-´arn´ı relaci P A ⊆ An a kaˇzd´emu n-´arn´ımu funkˇcn´ımu symbolu f ∈ L pˇriˇrad´ı zobrazen´ı f A : An → A. Pˇ r´ıklad 2.1 Pˇr´ıkladem struktury pro jazyk obsahuj´ıc´ı konstantn´ı symboly a, b, bin´ arn´ı predik´atov´ y symbol P a bin´ arn´ı funkˇcn´ı symbol f , je napˇr. ˇctveˇrice R = hR, aR , bR , P R , f R i, kde R je mnoˇzina re´ aln´ ych ˇc´ısel, aR = 1, bR = 5, P R = {(c, d) ∈ R2 | c ≤ d} a f R (c, d) = c + d, tj. P se interpretuje jako bin´ arn´ı relace “menˇs´ı nebo rovno” a f jako sˇc´ıt´ an´ı. Pokud m´ame danou strukturu A pro jazyk L, m˚ uˇzeme urˇcit hodnotu kaˇzd´eho termu, pokud neobsahuje promˇenn´e. Hodnota tA termu t ve struktuˇre A je definov´ ana induktivnˇe, tj. • pokud t = a, kde a je konstantn´ı symbol, pak tA = aA , A • pokud t = f (t1 , . . . , tn ), kde f je n-´arn´ı funkˇcn´ı symbol, pak tA = f A (tA 1 , . . . , tn ).
Pˇ r´ıklad 2.2 Vezmˇeme interpretaci R definovanou v´ yˇse. Pak hodnota termu t = f (f (a, f (b, a)), b) je tR = f R (f R (aR , f R (bR , aR )), bR ) = (1 + (5 + 1)) + 5 = 12 . Nyn´ı jiˇz m˚ uˇzeme definovat pojem pravdivosti sentence ϕ v dan´e L-struktuˇre A (znaˇc´ıme A |= ϕ). Nejprve rozˇs´ıˇr´ıme n´aˇs jazyk L o nov´e konstatn´ı symboly, LA = {ca | a ∈ A}, a definujeme LA C = a) a zbytek se interpretuje strukturu AC . Ta interpretuje konstantn´ı symboly ca jako a (tj. cA a stejnˇe jako ve struktuˇre A. Pravdivost ϕ ve struktuˇre A se potom definuje pomoc´ı struktury AC . • pokud ϕ = P (t1 , . . . , tn ), kde P je n-´arn´ı predik´atov´ y symbol a t1 , . . . , tn termy, pak A |= ϕ A A ) ∈ P , , . . . , t pr´avˇe tehdy, kdyˇz (tA n 1 • pokud ϕ = ¬ψ, kde ψ je formule, pak A |= ϕ pr´avˇe tehdy, kdyˇz A 6|= ψ, • pokud ϕ = ψ ◦ χ, kde ψ, χ jsou formule a ◦ ∈ {∧, ∨, ⇒, ⇔}, pak se pravdivost ϕ urˇc´ı z pravdivost´ı ψ a χ stejnˇe jako ve v´ yrokov´e logice. • pokud ϕ = ∀xψ(x), kde ψ je formule a x promˇenn´a, pak A |= ϕ pr´avˇe tehdy, kdyˇz pro vˇsechny a ∈ A plat´ı AC |= ψ(ca ). • pokud ϕ = ∃xψ(x), kde ψ je formule a x promˇenn´a, pak A |= ϕ pr´avˇe tehdy, kdyˇz existuje a ∈ A takov´e, ˇze AC |= ψ(ca ). Abychom zjednoduˇsili notaci, budeme jm´ena ca prvk˚ u a ztotoˇzn ˇovat. Bude pak moˇzno ps´ at, ˇze A |= ∀xψ(x) pr´ avˇe tehdy, kdyˇz pro vˇsechny a ∈ A plat´ı AC |= ϕ(a). Pojem pravdivosti rozˇsiˇrujeme i na formule s voln´ ymi v´ yskyty promˇenn´ ych. Necht’ ϕ(x1 , . . . , xn ) je formule, kde promˇenn´e x1 , . . . , xn se vyskytuj´ı volnˇe ve ϕ. Pak definujeme A |= ϕ(x1 , . . . , xn ) pr´avˇe tehdy, kdyˇz A |= ∀x1 · · · ∀xn ϕ(x1 , . . . , xn ). Pˇ r´ıklad 2.3 Mˇejme jazyk obsahuj´ıc´ı jeden bin´ arn´ı predik´atov´ y symbol Q a k nˇemu strukturu A = hA, QA i, kde A = {0, 1, 2, 3} a QA = {(0, 2), (1, 2), (2, 2), (2, 3)}. Zjistˇete pro n´asleduj´ıc´ı sentence, jestli jsou pravdiv´e v A. a) ϕ = ∃x∀y ¬Q(x, y). b) ϕ = ∃x∃y(Q(x, y) ∧ Q(y, x)). c) ϕ = ∃x∀y(Q(x, y) ⇔ ¬Q(y, y)).
2
ˇ sen´ı Reˇ a) A |= ϕ pr´ avˇe tehdy, kdyˇz existuje prvek univerza a ∈ A takov´ y, ˇze pro vˇsechny prvky univerza b ∈ A plat´ı, ˇze (a, b) 6∈ QA . Jin´ ymi slovy existuje a ∈ A takov´e, ˇze vˇsechny dvojice prvk˚ u z univerza, kter´e maj´ı jako prvn´ı sloˇzku a, nepatˇr´ı do QA . Vid´ıme tedy, ˇze pro a = 3 je toto splnˇeno, protoˇze QA neobsahuje ˇz´adnou dvojici s prvn´ı sloˇzkou rovnou 3. Takˇze A |= ϕ. b) A |= ϕ pr´ avˇe tehdy, kdyˇz existuj´ı prvky univerza a, b ∈ A takov´e, ˇze (a, b) ∈ QA a z´aroveˇ n A (b, a) ∈ Q . Jin´ ymi slovy sentence ˇr´ık´a, ˇze existuje dvojice v QA takov´ a, ˇze i jej´ı varianta s pˇrehozen´ ymi sloˇzkami je tak´e v QA . Vid´ıme, ˇze jedin´a dvojice, kter´a toto splˇ nuje je (2, 2) ∈ A Q . Takˇze pro a = b = 2 plat´ı, ˇze (a, b) ∈ QA a (b, a) ∈ QA , tj. A |= ϕ. c) A |= ϕ pr´ avˇe tehdy, kdyˇz existuje prvek univerza a ∈ A takov´ y, ˇze pro vˇsechny prvky univerza b ∈ A plat´ı, ˇze (a, b) ∈ QA pr´avˇe tehdy, kdyˇz (b, b) 6∈ QA . Tzn. ˇze bud’ (a, b) ∈ QA a z´aroveˇ n (b, b) 6∈ QA nebo (a, b) 6∈ QA a z´aroveˇ n (b, b) ∈ QA (napiˇste si DNF v´ yrokov´e formule α ⇔ ¬β). Probereme jednotliv´e moˇznosti pro prvek a. a = 0: Vid´ıme, ˇze (0, 2) ∈ QA a z´aroveˇ n (2, 2) ∈ QA . Takˇze prvek a = 0 nesplˇ nuje naˇs´ı podm´ınku. a = 1: Podobnˇe jako minule m´ame (1, 2) ∈ QA a z´aroveˇ n (2, 2) ∈ QA , takˇze ani pro a = 1 to neplat´ı. a = 2: Stejnˇe tak tady m´ame (2, 2) ∈ QA a z´aroveˇ n (2, 2) ∈ QA , takˇze zase nic. a = 3: V tomto pˇr´ıpadˇe neexistuje dvojice v QA , kter´a by mˇela na prvn´ı sloˇzce 3. Nicm´enˇe vid´ıme, ˇze napˇr pro (3, 0) 6∈ QA a z´aroveˇ n (0, 0) 6∈ QA . Takˇze v tomto pˇr´ıpadˇe nen´ı naˇse podm´ınka splnˇena. Shrnuto vˇse dohromady, A 6|= ϕ, protoˇze pro ˇz´adnou moˇznou hodnotu a nebylo splnˇeno AC |= ∀y(Q(a, y) ⇔ ¬Q(y, y)). Pˇ r´ıklad 2.4 Mˇejme interpretaci R z pˇr´ıkladu 2.1. Pro kaˇzdou n´asleduj´ıc´ı formuli ϕ, zda-li plat´ı R |= ϕ. a) ϕ = P (f (x, y), a) ∧ ¬P (a, y). b) ϕ = ∃y(P (f (x, y), a) ∧ ¬P (a, y)). c) ϕ = ∀x∀y((P (x, a) ∧ P (a, y)) ⇒ P (x, y)). ˇ sen´ı Reˇ a) Protoˇze ϕ nen´ı sentence, zjiˇst’ujeme tedy, jestli plat´ı R |= ∀x∀yϕ(x, y). Pˇripomeˇ nme, ˇze P se interpretuje v R jako ≤, f jako + a a jako 1. Formule ϕ je tedy pravdiv´a v R pr´avˇe tehdy, kdyˇz pro vˇsechny r, s ∈ R plat´ı RC |= P (f (r, s), a) ∧ ¬P (1, s), tj. pro vˇsechny r, s ∈ R plat´ı r + s ≤ 1 a 1 > s. To ale neplat´ı, protoˇze napˇr. pro s = 2 nen´ı pravda, ˇze 1 > s. Tud´ıˇz R 6|= ϕ. b) V tomto pˇr´ıpadˇe m´ame stejnou formuli jako pˇredt´ım, aˇz na existenˇcn´ı kvantifik´ ator na zaˇc´atku formule. Promˇenn´a y ted’ nen´ı voln´a, takˇze nyn´ı zjiˇst’ujeme, jestli R |= ∀xϕ(x). Podobnˇe jako v pˇredchoz´ım bodˇe, R |= ∀xϕ(x) pr´avˇe tehdy, kdyˇz pro vˇsechny r ∈ R existuje s ∈ R takov´e, ˇze r + s ≤ 1 a 1 > s. Takov´e s ∈ R existuje. Abychom splnili nerovnici r + s ≤ 1, mus´ı platit s ≤ 1 − r. Staˇc´ı tedy vz´ıt za s libovoln´e re´aln´e ˇc´ıslo ostˇre menˇs´ı min{1 − r, 1}. Tud´ıˇz R |= ϕ. c) Formule ϕ je v tomto pˇr´ıpadˇe sentence. Podle definice pravdivosti R |= ϕ pr´avˇe tehdy, kdyˇz pro vˇsechny r, s ∈ R plat´ı RC |= (P (r, a) ∧ P (a, s)) ⇒ P (r, s). To znamen´a, ˇze pro vˇsechny r, s ∈ R mus´ı platit, ˇze r ≤ 1 a 1 ≤ s implikuje r ≤ s. To ale plat´ı, protoˇze ≤ je tranzitivn´ı bina´arn´ı relace na R. Tud´ıˇz R |= ϕ. 3
Pˇ r´ıklad 2.5 Mˇejme jazyk obsahuj´ıc´ı bin´ arn´ı predik´atov´ y symbol =, bin´ arn´ı funkˇcn´ı symbol · a konstantn´ı symbol 0. Necht’ Q = hQ, ·, 0i je struktura, kde Q je mnoˇzina racion´ aln´ıch ˇc´ısel, · je bˇeˇzn´e n´asoben´ı racion´ aln´ıch ˇc´ısel a 0 je racion´ aln´ı ˇc´ıslo nula. Zjistˇete pro n´asleduj´ıc´ı sentence, jestli jsou pravdiv´e v Q. a) ∀x∃y(y · y = x). b) ∀x∀y(¬(x = 0) ⇒ ∃z(x · z = y)). ˇ sen´ı Reˇ a) Pˇreˇcteme si, co sentence a) ˇr´ık´a. Pro kaˇzd´e racion´ aln´ı ˇc´ıslo p existuje racion´ aln´ı ˇc´ıslo q takov´e, ˇze q · q = p. To ale neplat´ı, protoˇze napˇr. pro p = 2 neexistuje racion´ aln´ı ˇc´ıslo q takov´e, ˇze q · q = 2. Takˇze sentence z bodu a) nen´ı pravdiv´a v Q. b) Pˇreˇcteme si opˇet, co sentence b) ˇr´ık´a. Pro kaˇzd´ a racion´ aln´ı ˇc´ısla p, q pokud p 6= 0, pak existuje racion´ aln´ı ˇc´ıslo r takov´e, ˇze p · r = q. Toto tvrzen´ı je pravdiv´e, protoˇze kdyˇz p 6= 0, m˚ uˇzeme za r vz´ıt pod´ıl pq ∈ Q. Pak je totiˇz splnˇeno p · pq = q. Takˇze sentence z bodu b) je pravdiv´a v Q. Pˇ r´ıklad 2.6 Mˇejme jazyk obsahuj´ıc´ı bin´ arn´ı predik´atov´e symboly ≤, = a struktury N = hN, ≤i, Z = hZ, ≤i, Q = hQ, ≤i, kde N je mnoˇzina pˇrirozen´ ych ˇc´ısel, Z je mnoˇzina cel´ ych ˇc´ısel, Q mnoˇzina racion´ aln´ıch ˇc´ısel a ≤ je bˇeˇzn´e uspoˇra´d´an´ı. 1. Najdˇete sentenci ϕ takovou, ˇze Z |= ϕ a N 6|= ϕ. 2. Najdˇete sentenci ψ takovou, ˇze Q |= ψ a Z 6|= ψ. ˇ sen´ı Obecnˇe v takov´ Reˇ ychto typech pˇr´ıklad˚ u mus´ıme naj´ıt nˇejakou vlastnost, kterou se jednotliv´e struktury liˇs´ı, a pak se j´ı snaˇzit popsat v dan´em jazyce. 1. Typick´ a vlastnost, kter´a odliˇsuje N od Z, je existence nejmenˇs´ıho prvku. V´ıme, ˇze 0 je nejmenˇs´ı prvek N, kdeˇzto cel´a ˇc´ısla nejmenˇs´ı prvek nemaj´ı. Sentence ϕ by tedy mˇela vyjadˇrovat neexistenci nejmenˇs´ıho prvku. Pak bude platit v Z a nebude platit v N. Prvek a je nejmenˇs´ı v˚ uˇci ≤, pokud plat´ı ∀y(a ≤ y). Kdyˇz chceme ˇr´ıci, ˇze neexituje takov´e a, dostaneme sentenci ϕ = ¬∃x∀y(x ≤ y) . 2. Nyn´ı potˇrebujeme rozliˇsit racion´ aln´ı a cel´a ˇc´ısla. Typickou vlastnost´ı odliˇsuj´ıc´ı tyto mnoˇziny je tato vlastnost: pro kaˇzd´e dvˇe ˇc´ısla a, b takov´e, ˇze a < b, existuje c takov´e, ˇze a < c < b. Tuto vlastnost maj´ı racion´ aln´ı ˇc´ısla a nemaj´ı ji cel´a ˇc´ısla. Popiˇsme tuto vlastnost pomoc´ı formule. Nejprve si ukaˇzme jak vyj´ adˇrit, ˇze a je ostˇre menˇs´ı neˇz b. To lze zapsat takto (a ≤ b) ∧ ¬(a = b). Oznaˇcme ψ< (x, y) formuli (x ≤ y) ∧ ¬(x = y). ∀x∀y(ψ< (x, y) ⇒ ∃z(ψ< (x, z) ∧ ψ< (z, y))) . Rozepsano ∀x∀y
3
(x ≤ y) ∧ ¬(x = y) ⇒ ∃z (x ≤ z) ∧ ¬(x = z) ∧ (z ≤ y) ∧ ¬(z = y) .
Tautologie, kontradikce, splniteln´ e sentence
Pˇripomeˇ nme, ˇze sentenci ϕ naz´ yv´ame tautologie, pokud je pravdiv´a v kaˇzd´e struktuˇre. Naopak ϕ naz´ yv´ame nesplnitelnou sentenc´ı (tak´e kontradikc´ı), pokud nen´ı pravdiv´a v ˇz´adn´e struktuˇre. Sentence, kter´e jsou pravdiv´e alespoˇ n v jedn´e struktuˇre naz´ yv´ame splniteln´e. Vˇsimnˇete si, ˇze speci´alnˇe kaˇzd´ a tautologie je i splniteln´a, ale splniteln´a nemus´ı b´ yt tautologie. 4
Pˇ r´ıklad 3.1 Zjistˇete pro kaˇzdou n´asleduj´ıc´ı sentenci, jestli je tautologie, kontradikce nebo splniteln´a (ale ne tautologie). a) ∃x P (x) ⇒ ∀x P (x). b) ∀x(P (x) ∧ Q(x)) ⇔ (∀x P (x) ∧ ∀x Q(x)). c) ∀x(P (x) ∨ Q(x)) ⇒ (∀x P (x) ∨ ∀x Q(x)). d) ∀x P (x) ∧ ∃x ¬P (x). e) ∃x∀y Q(x, y) ⇒ ∃z Q(z, z). f) ∀x∃y Q(x, y) ⇒ ∃z Q(z, z). g) ∃x Q(x, f (x)) ⇒ Q(f (x), f (x)) . ˇ sen´ı Reˇ a) Sentence ˇr´ık´a, ˇze pokud existuje prvek univerza, kter´ y m´a vlastnost P , pak uˇz ji mus´ı m´ıt vˇsechny prvky. Takov´ a vˇec samozˇrejmˇe nemus´ı platit vˇzdy, napˇr. ve struktuˇre N = hN, P N i, kde P N = {2n | n ∈ N} je mnoˇzina sud´ ych pˇrirozen´ ych ˇc´ısel, to neplat´ı, protoˇze existuje sud´e pˇrirozen´e ˇc´ıslo (napˇr. 2), ale nen´ı pravda, ˇze vˇsechny pˇrirozen´ a ˇc´ısla jsou sud´a (napˇr. 3). Sentence tedy nem˚ uˇze b´ yt tautologie. Sentence je tedy bud’ kontradikce nebo splniteln´a. Protoˇze implikaci utvoˇr´ıme jednoduˇse pravdivou, pokud uˇcin´ıme jej´ı pˇredpoklad nepravdiv´ y, ′ je zˇrejm´e, ˇze existuje interpretace, kde je naˇse sentence pravdiv´a. Napˇr. pro N′ = hN, P N i, ′ kde P N = ∅, je ∃x P (x) nepravdiv´a, a tud´ıˇz je naˇse sentence v t´eto interpretaci pravdiv´a. Shrnuto sentence z bodu a) je splniteln´a, ale ne tautologie. b) Sentence z bodu b) je ekvivalence. Ta je pravdiv´a pokud jsou bud’ oba jej´ı argumenty pravdiv´e nebo oba nepravdiv´e. Necht’ A = hA, P A , QA i je libovoln´a struktura. Pod´ıv´ame se, jestli m˚ uˇze b´ yt tato podm´ınka splnˇena. Nejprve pˇredpokl´adejme, ˇze A |= ∀x(P (x) ∧ Q(x)). Mus´ıme uk´azat, ˇze i A |= ∀x P (x) ∧ ∀x Q(x). Z pravdivosti ∀x(P (x) ∧ Q(x)) plyne, ˇze pro kaˇzd´ y prvek a ∈ A plat´ı, ˇze a ∈ P A a z´aroveˇ n a ∈ QA . Jin´ ymi slovy P A = QA = A. Z toho ale plyne, ˇze A |= ∀x P (x) a zrovna tak A |= ∀x Q(x). Tud´ıˇz je v t´eto struktuˇre pravdiv´a i konjunkce tˇechto sentenc´ı ∀x P (x) ∧ ∀x Q(x). Nyn´ı pˇredpokl´adejme, ˇze A 6|= ∀x(P (x) ∧ Q(x)). Tj. existuje prvek a ∈ A takov´ y, ˇze a 6∈ P A A A nebo a 6∈ Q . Pˇredpokl´adejme, ˇze napˇr. a 6∈ P (druh´ y pˇr´ıpad by se dˇelal analogicky). Tzn. ˇze P A 6= A, a tedy A 6|= ∀x P (x). Tud´ıˇz je v t´eto struktuˇre nepravdiv´a i konjunkce sentenc´ı ∀x P (x) ∧ ∀x Q(x). Uk´azali jsme, ˇze oba argumenty ekvivalence jsou bud’ oba pravdiv´e nebo oba nepravdiv´e v libovoln´e struktuˇre. Tzn. ˇze sentence z bodu b) je tautologie. c) Sentence z bodu c) je implikace, kter´a je pravdiv´a, pokud uk´aˇzeme, ˇze z pravdivosti jej´ıho pˇredpokladu plyne pravdivost jej´ıho z´avˇeru. Necht’ A = hA, P A , QA i je libovoln´a struktura. Pˇredpokl´adejme, ˇze A |= ∀x(P (x) ∨ Q(x)). Tzn. ˇze pro kaˇzd´ y prvek univerza a ∈ A plat´ı, ˇze a ∈ P A nebo a ∈ QA . Jin´ ymi slovy P A ∪ QA = A. Pod´ıvejme se, jestli za t´eto podm´ınky mus´ı platit z´avˇer naˇs´ı implikace ∀x P (x) ∨ ∀x Q(x). Aby byla sentence ∀x P (x) ∨ ∀x Q(x) pravdiv´a muselo by platit P A = A nebo QA = A. Takov´e tvrzen´ı, ale z naˇseho pˇredpokladu P A ∪ QA = A neplyne. Napˇr. pro A = N, P A = {2n | n ∈ N} sud´a pˇrirozen´ a ˇc´ısla a QA = N \ P A lich´a pˇrirozen´ a ˇc´ısla, m´ame P A ∪ QA = N, ale nen´ı pravda, ˇze by vˇsechna ˇc´ısla byla sud´a nebo lich´a, tj. P A 6= A a QA 6= A. Sentence z bodu c) tedy nen´ı tautologie. Nicm´enˇe je splniteln´a. Pokud bychom napˇr. vzali A = N, P A = N a za QA cokoli, pak je z´avˇer naˇs´ı implikace ∀x P (x) ∨ ∀x Q(x) pravdiv´ yv A, a tud´ıˇz je pravdiv´a i cel´a implikace. Shrnuto sentence z bodu c) nen´ı tautologie, ale je splniteln´ a, protoˇze existuje struktura, kde je pravdiv´a. 5
d) Sentence z bodu d) je konjunkce, kter´a je pravdiv´a, pokud jsou pravdiv´e oba jej´ı argumenty ∀x P (x) a ∃x ¬P (x). Oba argumenty jsou zˇrejmˇe splniteln´e sentence, ale ne tautologie. Cel´a konjunkce tedy nem˚ uˇze b´ yt tautologie. Pod´ıvejme se, jestli je moˇzn´e naj´ıt strukturu, kde jsou pravdiv´e oba tyto argumenty. Necht’ A = hA, P A i je libovoln´a struktura. Pokud A |= ∀x P (x), pak P A = A. Naopak pokud A |= ∃x ¬P (x), pak existuje prvek a ∈ A takov´ y, ˇze a 6∈ P A , tj. P A 6= A. Vid´ıme, ˇze podm´ınky P A = A a P A 6= A nelze splnit z´aroveˇ n. Z toho plyne, ˇze v kaˇzd´e interpretaci, kde je ∀x P (x) pravdiv´e nen´ı pravdiv´e ∃x ¬P (x) a naopak. Neboli neexistuje struktura, kde by byly pravdiv´e obˇe sentence ∀x P (x) a ∃x ¬P (x). Sentence z bodu d) je tedy nesplniteln´ a. e) Sentence z bodu e) je implikace, kter´a je nepravdiv´a jedinˇe tehdy, kdyˇz m´a pravdiv´ y pˇredpoklad a nepravdiv´ y z´avˇer. Necht’ A = hA, QA i je struktura takov´ a, ˇze A |= ∃x∀y Q(x, y). Zjist´ıme, jestli m˚ uˇze nastat A 6|= ∃z Q(z, z). Z pˇredpokladu A |= ∃x∀y Q(x, y) plyne, ˇze existuje a ∈ A takov´ y, ˇze pro vˇsechna b ∈ A m´ame (a, b) ∈ QA . Speci´alnˇe tedy pro b = a m´ame (a, a) ∈ QA . Tud´ıˇz A |= ∃z Q(z, z). Zjistili jsme tedy, ˇze pokud v nˇejak´e struktuˇre je pˇredpoklad implikace pravdiv´ y, je tam pravdiv´ y i z´avˇer. Sentece z bodu e) je tedy tautologie, protoˇze v libovoln´e strutuˇre bud’ plat´ı pˇredpoklad, a pak plat´ı i z´avˇer, nebo neplat´ı pˇredpoklad, a pak je implikace pravdiv´a nez´avisle na z´avˇeru. f) Sentence z bodu f) se liˇs´ı od bodu e) jen prohozen´ım kvantifik´ ator˚ u v pˇredpokladu implikace. Podobnˇe jako pˇredt´ım necht’ A = hA, QA i je struktura takov´ a, ˇze A |= ∀x∃y Q(x, y). To znamen´a, ˇze pro kaˇzd´ y prvek a ∈ A existuje prvek ba ∈ A takov´ y, ˇze (a, ba ) ∈ QA . Vˇsimˇete si, ˇze prvek ba je indexov´ an prvkem a a to z toho d˚ uvodu, ˇze pro r˚ uzn´e prvky a, a′ ∈ A mohou b´ yt obecnˇe prvky ba , ba′ r˚ uzn´e. Pt´ ame se, jestli za tohoto pˇredpokladu mus´ı platit A |= ∃z Q(z, z), tj. jestli mus´ı existovat prvek c ∈ A takov´ y, ˇze (c, c) ∈ QA . Takov´ y prvek, ale zˇrejmˇe existovat nemus´ı. Uvaˇzujme napˇr. strukturu, kde A = {0, 1} a QA = {(0, 1), (1, 0)}. Pak plat´ı, ˇze pro kaˇzd´ y prvek a ∈ A existuje ba ∈ A takov´e, ˇze (a, ba ) ∈ QA (konkr´etnˇe pro a = 0 m´ame ba = 1 a pro a = 1 m´ame ba = 0) a z´aroveˇ n neexistuje c ∈ A takov´e, ˇze (c, c) ∈ QA . V t´eto struktuˇre tedy sentence z bodu f) neplat´ı, a tud´ıˇz to nen´ı tautologie. Nicm´enˇe je to splniteln´a sentence, protoˇze bude pravdiv´a napˇr. v kaˇzd´e struktuˇre, kde bude pravdiv´ y z´avˇer implikace. Tedy napˇr. pro jednoprvkovou strukturu A = hA, QA i, kde A = {0} a QA = {(0, 0)}. g) Necht’ A = hA, QA , f A i je struktura, tj. QA ⊆ A × A a f A : A → A. Podle definice pravdivosti A |= ∃x Q(x, f (x)) ⇒ Q(f (x), f (x)) pr´avˇe tehdy, kdyˇz existuje a ∈ A takov´e, ˇze AC |= Q(a, f (a)) ⇒ Q(f (a), f (a)). Pokud by existovalo a ∈ A takov´e, ˇze (a, f A (a)) 6∈ QA , pak by byl neplatn´ y pˇredpoklad Q(a, f(a)) a implikace by tud´ıˇz byla pravdiv´a, tj. platilo by A |= ∃x Q(x, f (x)) ⇒ Q(f (x), f (x)) . To nast´ av´ a napˇr. v kaˇzd´e struktuˇre, kde QA = ∅. Sentence z bodu g) je tedy splniteln´a. Zjistˇeme, jestli je to tautologie. Pˇredpokl´adejme, ˇze A je struktura, kde pro vˇsechny a ∈ A m´ame (a, f A (a)) ∈ QA , tzn. pˇredpoklad implikace Q(a, f (a)) je splnˇen pro kaˇzd´e a ∈ A. Z tohoto pˇredpokladu plyne, ˇze f A ⊆ QA , kdyˇz ch´apeme zobrazen´ı f A jako bin´ arn´ı relaci na A. Plyne ale z tohoto pˇredpokladu, ˇze (f A (a), f A (a)) ∈ QA ? Uk´aˇzeme, ˇze ne. Necht’ A = hA, QA , f A i, kde A = {0, 1}, QA = {(0, 1), (1, 0)} a f A (0) = 1, f A (1) = 0. Vˇsimˇete si, ˇze QA = f A . Tud´ıˇz pro vˇsechny A A A a ∈ A m´ame (a, f A (a)) ∈ QA , ale pro ˇz´adn´ e a ∈ A nen´ı pravda, ˇze (f (a), f (a)) ∈ Q . Takˇze A 6|= ∃x Q(x, f (x)) ⇒ Q(f (x), f (x)) . Sentence z bodu g) tedy nen´ı tautologie.
4
Splniteln´ e a nesplniteln´ e mnoˇ ziny sentenc´ı
Pˇripomeˇ nme, ˇze mnoˇzina sentenc´ı M se naz´ yv´a splniteln´a, pokud existuje jej´ı model, tj. existuje struktura A takov´ a, ˇze A |= ϕ pro kaˇzdou ϕ ∈ M . Pokud takov´ a struktura neexistuje naz´ yv´ame mnoˇzinu M nesplnitelnou. Uvˇedomte si, ˇze zjiˇst’ovat, jestli je jednoprvkov´ a mnoˇzina sentenc´ı M = {ϕ} splniteln´ a, znamen´a vlastnˇe zjistit, zda-li je splniteln´a ϕ. Pˇ r´ıklad 4.1 Zjistˇete pro kaˇzdou n´asleduj´ıc´ı mnoˇziny sentenc´ı, jestli jsou splniteln´e ˇci nesplniteln´e.
6
a) M1 = {∀x R(x, x), ∀x∀y(R(x, y) ⇒ R(y, x)), ∀x∀y∀z((R(x, y) ∧ R(y, z)) ⇒ R(x, z))}. b) M2 = {∀x(¬P (x) ∨ ¬Q(x)), ∀x(P (x) ⇒ Q(x))}. c) M3 = {∀x(P (x) ∨ Q(x)), ¬∃x(P (x) ∧ Q(x)), ¬(P (c) ⇔ ¬Q(c))}. ˇ sen´ı Reˇ a) Vid´ıme, ˇze vˇsechny sentence z M1 se t´ ykaj´ı bin´ arn´ıho predik´atov´eho symbolu R. Chceme zjistit, jestli je M1 splniteln´ a, tj. chceme naj´ıt strukturu A = hA, RA i, kde jsou pravdiv´e vˇsechny sentence z M1 . Interpretace RA symbolu R je nˇejak´a bin´ arn´ı relace na A. Mus´ıme tedy zjistit, jestli existuje mnoˇzina A a bin´ arn´ı relace RA na A takov´ a, ˇze jsou pravdiv´e vˇsechny sentence z M1 . Pˇreˇcteme si, co jednotliv´e sentence o R ˇr´ıkaj´ı. Prvn´ı ˇr´ık´a, ˇze pro kaˇzd´e a ∈ A plat´ı (a, a) ∈ RA . Druh´ a ˇr´ık´a, ˇze pro kaˇzd´e a, b ∈ A pokud (a, b) ∈ RA , A pak (b, a) ∈ R . Posledn´ı ˇr´ık´a, ˇze pro kaˇzd´e a, b, c ∈ A pokud (a, b) ∈ RA a (b, c) ∈ RA , pak (a, c) ∈ RA . Jin´ ymi slovy RA m´a b´ yt reflexivn´ı, symetrick´ a a tranzitivn´ı relace, tj. ekvivalence. Protoˇze ekvivalence existuj´ı (napˇr. pro A = N je RA = {(n, n) | n ∈ N} ekvivalence) je mnoˇzina M1 splniteln´a. b) Chceme naj´ıt strukturu A = hA, P A , QA i, ve kter´e jsou vˇsechny sentence z M2 pravdiv´e. Un´arn´ı predik´atov´e symboly se budou interpretovat jako podmnoˇziny A, tj. P A ⊆ A a QA ⊆ A. Pˇreˇctˇeme si, co ˇr´ıkaj´ı sentence z M2 . Prvn´ı ˇr´ık´a, ˇze pro kaˇzd´e a ∈ A plat´ı, ˇze a 6∈ P A nebo a 6∈ QA . Z toho plyne, ˇze P A ∩ QA = ∅, protoˇze kdyˇz a ∈ P A , pak nutnˇe a 6∈ QA . Druh´ a sentence ˇr´ık´a, ˇze pro kaˇzd´e a ∈ A pokud a ∈ P A , pak a ∈ QA . Jin´ ymi slovy vˇsechny prvky z P A patˇr´ı do QA , tj. P A ⊆ QA . Takˇze mus´ıme zvolit P A a QA tak, aby platilo P A ∩ QA = ∅ a z´aroveˇ n P A ⊆ QA . To udˇelat lze, napˇr. pokud A je libovoln´a nepr´ azdn´ a mnoˇzina, QA = U a P A = ∅, pak P A ∩ QA = ∅ ∩ A = ∅ a P A = ∅ ⊆ A = QA . Takˇze mnoˇzina M2 je splniteln´ a. Vˇsimnˇete si, ˇze pokud bychom pˇridali do M2 sentenci ∃x P (x) vyˇzaduj´ıc´ı nepr´ azdnost P A , pak se mnoˇzina M2 stala nesplnitelnou. c) Opˇet chceme naj´ıt strukturu A = hA, P A , QA i, ve kter´e jsou vˇsechny sentence z M3 pravdiv´e. Un´arn´ı predik´atov´e symboly se budou interpretovat jako podmnoˇziny A, tj. P A ⊆ A a QA ⊆ A. Konstantn´ı symbol c se interpretuje jako prvek univerza, tj. cA ∈ A. Pˇreˇctˇeme si, co ˇr´ıkaj´ı prvn´ı dvˇe sentence. Prvn´ı ˇr´ık´a, ˇze pro vˇsechna a ∈ A plat´ı a ∈ P A nebo a ∈ QA . Jin´ ymi slovy P A ∪ QA = A. Druh´ a sentence ˇr´ık´a, ˇze neexistuje a ∈ A takov´e, ˇze a ∈ P A a A A z´aroveˇ n a ∈ Q . Jin´ ymi slovy P ∩ QA = ∅. Takˇze aby byly splnˇeny prvn´ı dvˇe sentence, mus´ı b´ yt podmnoˇziny P A a QA disjunktn´ı a jejich sjednocen´ı cel´e univerzum A. Pod´ıvejme se, jestli se za tˇechto podm´ınek d´a splnit i tˇret´ı sentence. Tˇret´ı sentence ˇr´ık´a, ˇze nen´ı pravda, ˇze cA ∈ P A pr´ avˇe tehdy, kdyˇz cA 6∈ QA . Mus´ıme zvolit cA tak, aby byla ekvivalence P (c) ⇔ ¬Q(c) nepravdiv´a, tj. bud’ cA ∈ P A a cA ∈ QA nebo cA 6∈ P A a cA 6∈ QA . Prvn´ı pˇr´ıpad nen´ı moˇzn´ y, protoˇze P A ∩ QA = ∅. V druh´em pˇr´ıpadˇe z cA 6∈ P A plyne, ˇze cA ∈ QA , A A protoˇze P ∪Q = A. To je ale spor, protoˇze nem˚ uˇze z´aroveˇ n platit cA ∈ QA a cA 6∈ QA . To A znamen´a, ˇze at’ uˇz zvol´ıme prvek c jakkoliv, tˇret´ı sentence nebude nikdy pravdiv´a, pokud budou pravdiv´e prvn´ı dvˇe. Takˇze M3 je nesplniteln´ a. Splnitelnost ˇci nesplnitelnost mnoˇziny sentenc´ı m˚ uˇzeme tak´e zjistit pomoc´ı rezoluˇcn´ı metody. Nicm´enˇe pokud je mnoˇzina splniteln´ a rezoluˇcn´ı algoritmus se nemus´ı zastavit, a pokud se zastav´ı, znamen´a to, ˇze ˇz´adn´ a dalˇs´ı rezolventa jiˇz nejde vyrobit, coˇz b´ yv´a ˇcasto na pap´ıˇre pracn´e ovˇeˇrit. Pˇ r´ıklad 4.2 Rozhodnˇete rezoluˇcn´ı metodou, jestli jsou mnoˇziny M2 a M3 z pˇr´ıkladu 4.1 splniteln´e ˇci nesplniteln´e. ˇ sen´ı Reˇ
7
M2 : Najdeme nejprve ekvisplnitelnou mnoˇzinu sentenc´ı S pro M2 . Prvn´ı sentence z M2 je jiˇz klausule, takˇze s tou nemus´ıme nic dˇelat. U druh´e staˇc´ı nahradit implikaci pomoc´ı negace a disjunkce, takˇze dostaneme ∀x(¬P (x) ∨ Q(x)). Ekvisplniteln´ a mnoˇzina sentenc´ı pro M2 tedy je S = {¬P (x) ∨ ¬Q(x), ¬P (y) ∨ Q(y)} . Pro jistotu jsme pˇrejmenovali promˇenn´e u druh´e sentence. Rezoluˇcn´ı algoritmus m˚ uˇze v tomto pˇr´ıpadˇe vyrobit jen jednu rezolventu, a to ¬P (x). Protoˇze ˇz´adn´ a dalˇs´ı rezolventa nejde vyrobit a pr´ azdnou klausuli F jsme neobdrˇzeli, je mnoˇzina M2 splniteln´a. M3 : Najdeme opˇet ekvisplnitelnou mnoˇzinu sentenc´ı S pro M3 . Prvn´ı sentence z M2 je jiˇz klausule, takˇze s tou nemus´ıme nic dˇelat. Druhou je potˇreba pˇrev´est do prenexn´ıho norm´aln´ıho tvaru. Distribuc´ı existenˇcn´ıho kvantifik´ atoru pˇres negaci dostaneme ∀x ¬(P (x) ∧ Q(x)). Pouˇzit´ım De Morganova z´akonu obdrˇz´ıme jiˇz klausuli ∀x(¬P (x) ∨ ¬Q(x)). Posledn´ı sentenci je potˇreba pˇrev´est do CNF. Pravdivostn´ı tabulka pro v´ yrokovou formuli ¬(p ⇔ ¬q) je p 0 0 1 1
¬(p ⇔ ¬q) 1 0 0 1
q 0 1 0 1
Ekvivalentn´ı formule v CNF je tedy (p ∨ ¬q) ∧ (¬p ∨ q). Takˇze tˇret´ı sentenci m˚ uˇzeme ekvivalentnˇe pˇrepsat na (P (a) ∨ ¬Q(a)) ∧ (¬P (a) ∨ Q(a)) . Ekvisplniteln´ a mnoˇzina sentenc´ı pro M3 tedy je S = {P (x) ∨ Q(x), ¬P (y) ∨ ¬Q(y), P (a) ∨ ¬Q(a), ¬P (a) ∨ Q(a)} . Pro jistotu jsme pˇrejmenovali promˇenn´e u druh´e sentence. Rezoluˇcn´ı metoda n´am d´av´ a: 1. 2. 3. 4. 5. 6. 7.
P (x) ∨ Q(x) ¬P (y) ∨ ¬Q(y) P (a) ∨ ¬Q(a) ¬P (a) ∨ Q(a) Q(a) ¬Q(a) F
1,4,{x/a} 2,3,{y/a} 5,6.
Protoˇze jsme obdrˇzeli v pr˚ ubˇehu rezoluˇcn´ıho algoritmu pr´azdnou klausuli F je mnoˇzina klausul´ı S nesplniteln´ a, a tud´ıˇz i mnoˇzina sentenc´ı M3 je nesplniteln´ a.
8
