1
Predik´ atov´ a logika
1.1
Syntax
Podobnˇe jako ve v´ yrokov´e logice zaˇcneme nejprve se syntax´ı predik´atov´e logiky, kter´a n´am ˇr´ık´a, co jsou spr´ avnˇe utvoˇren´e formule predik´atov´e logiky. V dalˇs´ı ˇc´asti tohoto textu si pak vysvˇetl´ıme, jak´ y mohou m´ıt formule v´ yznam (s´emantiku). Definice 1.1 Jazyk predik´atov´e logiky L se skl´ ad´a z n´asleduj´ıc´ıch ˇc´ast´ı: 1. Logick´ ych symbol˚ u: • spoˇcetn´e mnoˇziny objektov´ ych promˇenn´ ych Var = {x, y, z, . . .}, • v´ yrokov´ ych logick´ ych spojek ¬, ∧, ∨, ⇒, ⇔, • obecn´eho (univerz´aln´ıho) kvantifik´ atoru ∀ a existeˇcn´ıho kvantifik´ atoru ∃, 2. Speci´aln´ıch (mimologick´ ych) symbol˚ u: • mnoˇziny predik´atov´ ych symbol˚ u R = {P, Q, R, . . .}, • mnoˇziny konstatn´ıch symbol˚ u C = {a, b, c, . . .}, • mnoˇziny funkˇcn´ıch symbol˚ u F = {f, g, h, . . .}, 3. Pomocn´ ych symbol˚ u: z´avorky a ˇc´arka. Kaˇzd´ y predik´atov´ y a funˇcn´ı symbol m´a danou aritu (ˇcetnost). Tyto symboly tedy mohou b´ yt un´ arn´ı, bin´ arn´ı, tern´arn´ı atd. Obecnˇe mluv´ıme o n-arn´ım predik´atov´em nebo funkˇcn´ım symbolu. Dodejme, ˇze jazyk˚ u predik´atov´e logiky je mnoho. V´ ybˇer konkr´etn´ıho jazyka z´avis´ı na tom, co chceme predik´atovou logikou formalizovat. Nicm´enˇe logick´e a pomocn´e symboly jsou u kaˇzd´eho jazyka stejn´e. Liˇs´ı se tedy jen ve speci´aln´ıch symbolech. Proto budeme zkr´ acenˇe jazyk L zapisovat jako mnoˇzinu speci´aln´ıch symbol˚ u, tj. L = R ∪ C ∪ F. Napˇr. pokud chceme formalizovat vlastnosti re´ aln´ ych ˇc´ısel, m˚ uˇze n´aˇs jazyk vypadat tˇreba takto L = {+, ·, 0, 1, =, ≤}, kde +, · jsou bin´ arn´ı funkˇcn´ı symboly, ≤, = jsou bin´ arn´ı predik´atov´e symboly a 0, 1 jsou konstantn´ı symboly. Neˇz budeme definovat pojem formule v predik´atov´e logice, mus´ıme nadefinovat pojem termu. Definice 1.2 Mnoˇzina L-term˚ u jazyka L je definov´ ana tˇemito pravidly: 1. Kaˇzd´ a promˇenn´a a kaˇzd´ y konstatn´ı symbol je term. 2. Jestliˇze f je funkˇcn´ı symbol arity n a t1 , . . . , tn jsou termy, pak f (t1 , . . . , tn ) je tak´e term. 3. Nic, co nevzniklo koneˇcn´ ym pouˇzit´ım 1 a 2, nen´ı term. Pokud bude jazyk L jasn´ y z kontextu, budeme m´ısto o L-termech mluvit jen o termech. Mejmˇe jazyk L obsahuj´ıc´ı un´ arn´ı funkˇcn´ı symbol f , bin´ arn´ı funkˇcn´ı symbol + a konstantn´ı symbol 0. Pak n´asleduj´ıc´ı jsou pˇr´ıklady L-term˚ u: • x + 0 (m´ısto +(x, y) p´ıˇseme x + y), • 0 + (0 + (0 + 0)), • f (f (x) + f (0 + 0)). Nyn´ı jiˇz m˚ uˇzeme nadefinovat pojem formule. Zaˇcneme s atomick´ ymi formulemi, kter´e si lze pˇredstavit jako z´akladn´ı formule, z kter´ ych budeme budovat sloˇzitˇejˇs´ı formule pouˇzit´ım logick´ ych spojek a kvantifik´ ator˚ u.
1
Definice 1.3 Necht’ L je jazyk. Atomick´ a L-formule je predik´atov´ y symbol P aplikovan´ y na tolik term˚ u, kolik je jeho arita. Tj. pro n-´arn´ı P ∈ R a termy t1 , . . . , tn je P (t1 , . . . , tn ) atomick´ a L-formule. Definice 1.4 Necht’ L je jazyk. Mnoˇzina L-formul´ı je definov´ ana tˇemito pravidly: 1. Kaˇzd´ a atomick´ a L-formule je L-formule. 2. Jsou-li ϕ a ψ dvˇe L-formule, pak (¬ϕ), (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⇒ ψ), (ϕ ⇔ ψ) jsou opˇet L-formule. 3. Je-li ϕ L-formule a x promˇenn´a, pak (∀xϕ) a (∃xϕ) jsou opˇet L-formule. 4. Nic, co nevzniklo koneˇcn´ ym pouˇzit´ım 1 aˇz 3, nen´ı formule. Pokud bude jazyk L jasn´ y z kontextu, budeme m´ısto o L-formul´ıch mluvit jen o formul´ıch. Podobnˇe jako ve v´ yrokov´e logice budeme nˇekter´e z´avorky v z´apisu formul´ı vynech´avat. Pˇrednˇe budeme opˇet vynech´avat vnˇejˇs´ı z´avorky. D´ale v pˇr´ıpadech, kdy budou chybˇet z´avorky, budeme pˇredpokl´adat, ˇze symboly ¬, ∀, ∃ maj´ı vˇetˇs´ı prioritu neˇz ∧, ∨, ⇒, ⇔. Takˇze napˇr´ıklad ∀yP (x, y) ⇒ Q(x, y) znamen´a ((∀yP (x, y)) ⇒ (Q(x, y))). D´ale poˇrad´ı symbol˚ u ¬, ∀, ∃ ve formuli urˇcuje poˇrad´ı v jak´em se aplikuj´ı. Napˇr´ıklad p´ıˇseme ∃x¬∀y∃zR(x, y, z) m´ısto (∃x(¬(∀y(∃z(R(x, y, z)))))). Definice 1.5 Necht’ ϕ je formule. Pojem podformule budeme definovat induktivnˇe n´asledovnˇe: 1. Pokud je ϕ atomick´ a formule, pak α je podformule ϕ pr´avˇe tehdy, kdyˇz α = ϕ. 2. Pokud ϕ = ¬ψ, pak α je podformule ϕ pr´avˇe tehdy, kdyˇz α = ϕ nebo α je podformul´ı ψ. 3. Pokud ϕ = ψ ⋄ χ pro ⋄ ∈ {∧, ∨, ⇒, ⇔}, pak α je podformule ϕ pr´avˇe tehdy, kdyˇz α = ϕ nebo α je podformul´ı ψ nebo α je podformul´ı χ. 4. Pokud ϕ = Qxψ pro Q ∈ {∀, ∃}, pak α je podformule ϕ pr´avˇe tehdy, kdyˇz α = ϕ nebo α je podformul´ı ψ. Pˇ r´ıklad 1.6 Necht’ ϕ je formule ∃x∀yP (x, y) ∨ ∀x∃yQ(x, y), kde P a Q jsou bin´ arn´ı predik´atov´e symboly. Podformule ϕ jsou ∃x∀yP (x, y), ∀yP (x, y), P (x, y), ∀x∃yQ(x, y), ∃yQ(x, y), Q(x, y) a ϕ sama. Vˇsimˇete si, ˇze formule P (x, y)∨∀x∃yQ(x, y), kter´a se vyskytuje jako ˇc´ast ϕ, nen´ı podformule ϕ. Definice 1.7 Mˇejme formuli ϕ a promˇennou x, kter´a se vyskytuje ve ϕ. • V´ yskyt promˇenn´e x je v´ azan´y ve ϕ, jestliˇze se x vyskytuje v nˇejak´e podformuli formule ϕ tvaru ∃xψ nebo ∀xψ. • V opaˇcn´em pˇr´ıpadˇe mluv´ıme o voln´em v´ yskytu. Pˇ r´ıklad 1.8 Uvaˇzujme formuli v jazyku s un´ arn´ım funˇcn´ım symbolem f , bin´ arn´ım funkˇcn´ım symbolem + a bin´ arn´ımi predik´atov´ ymi symboly <, = ∃x(x < y ∧ ∀y(z + f (y) = x)) . • v´ yskyt promˇenn´e z je voln´ y, • vˇsechny tˇri v´ yskyty promˇenn´e x jsou v´ azan´e, • promˇenn´a y m´a prvn´ı v´ yskyt voln´ y a druh´e dva v´ azan´e.
2
Definice 1.9 Necht’ ϕ je formule. • Pokud m´a formule ϕ pouze v´ azan´e v´ yskyty promˇenn´ ych, pak se naz´ yv´a sentence (uzavˇren´a formule). • Pokud m´a formule ϕ pouze voln´e v´ yskyty promˇenn´ ych, pak se naz´ yv´a otevˇren´ a formule. Pˇ r´ıklad 1.10
• ∀z∀y∃x(x < y ∧ ∀y(z + f (y) = x)) je sentence,
• x < y ∧ (z + f (y) = x) je otevˇren´a formule, • ∃x(x < y ∧ ∀y(z + f (y) = x)) nen´ı ani uzavˇren´a ani otevˇren´a, • 0 < f (f (0)) je uzavˇren´a i otevˇren´a. Definice 1.11 Necht’ ϕ je formule jej´ıˇz promˇenn´e, kter´e maj´ı voln´e v´ yskyty, jsou mezi x1 , . . . , xn . Pak ϕ budeme znaˇcit ϕ(x1 , . . . , xn ). Mˇejme termy t1 , . . . , tn . Pak ϕ(t1 , . . . , tn ) oznaˇcuje formuli, kde je kaˇzd´ y voln´ y v´ yskyt promˇenn´e xi nahrazen termem ti . Kdykoliv budeme tuto notaci pouˇz´ıvat, budeme vˇzdy pˇredpokl´adat, ˇze ˇz´adn´ y z term˚ u ti neobsahuje promˇennou, kter´a m´a v´ azan´ y v´ yskyt ve ϕ. Napˇr. kdyˇz ϕ(x) je ∃y¬(x = y), pak nen´ı dovolen´e ps´ at ϕ(y). D˚ uvod t´eto konvence bude patrn´ y pozdˇeji. Pokud ϕ(x, y) je napˇr. ∃z(x + y < z), t1 = 0 a t2 = f (0) + y, pak ϕ(0, f (0) + y) oznaˇcuje formuli ∃z(0 + (f (0) + y) < z).
1.2
S´ emantika
Definice 1.12 Mˇejme jazyk L = R ∪ C ∪ F. Struktura pro jazyk L (L-struktura) je nepr´ azdn´a mnoˇzina A (universum) spolu se zobrazen´ım J−K, kter´e splˇ nuje n´asleduj´ıc´ı body: 1. kaˇzd´emu predik´atov´emu symbolu P ∈ R arity n pˇriˇrazuje podmnoˇzinu JP K mnoˇziny An , tj. n-´arn´ı relaci na mnoˇzinˇe A, 2. kaˇzd´emu konstatn´ımu symbolu a ∈ C pˇriˇrazuje prvek JaK z A, 3. kaˇzd´emu funkˇcn´ımu symbolu f ∈ F arity n pˇriˇrazuje zobrazen´ı Jf K : An → A. 4. Pokud m´ame v R symbol =, pak J=K = {(a, a) | a ∈ A}. Pˇ r´ıklad 1.13 Uvaˇzujme jazyk L s bin´ arn´ım predik´atov´ ym symbolem H, konstatn´ım symbolem 0. L-struktura je napˇr. dvojice hA, J−Ki, kde A = {a, b, c, d}, J0K = c, JHK = {(a, b), (a, c), (b, c), (c, d), (d, a), (d, b)} . L-struktury budeme zkr´ acenˇe oznaˇcovat tuˇcnou variantou t´ehoˇz p´ısmene, kter´ ym je oznaˇceno universum. D´ale m´ısto interpretace JP K ve struktuˇre A pro P ∈ L budeme ps´ at P A . Pokud je jazyk L koneˇcn´ y, budeme strukturu zapisovat jako n-tici. Napˇr. pro strukturu z pˇr´ıkladu nahoˇre: A = hA, H A , 0A i . Pˇ r´ıklad 1.14 Mˇejme jazyk L s bin´ arn´ımi predik´aty ≤, =, bin´ arn´ımi funkˇcn´ımi symboly +, · a dvˇemi konstantami 0, 1. L-struktura je napˇr. R = hR, +R , ·R , 0R , 1R , ≤R i, kde ≤R je interpretov´ ano jako bin´ arn´ı relace “menˇs´ı nebo rovno” na re´ aln´ ych ˇc´ıslech, tj. ≤R je mnoˇzina 2 R {(a, b) ∈ R | a je menˇs´ı nebo rovno b}, 0 se realizuje jako re´ aln´e ˇc´ıslo nula, 1R se realizuje R jako re´ aln´e ˇc´ıslo jedna, + se interpretuje jako sˇc´ıt´ an´ı re´ aln´ ych ˇc´ısel a ·R se interpretuje jako n´asoben´ı re´ aln´ ych ˇc´ısel. Strukturu R budeme naz´ yvat struktura re´ aln´ ych ˇc´ısel. Predik´ atov´ y symbol = se v z´apisu R = hR, +R , ·R , 0R , 1R , ≤R i ˇcasto vynech´av´ a, protoˇze kdykoliv se objev´ı v nˇejak´e formuli je jeho interpretace vˇzdy stejn´ a viz Definice 1.12. V pˇr´ıpadech, jako je tento, kdy maj´ı symboly +, ·, 0, 1, ≤ “obvykl´ y” v´ yznam, si dovol´ıme ned˚ uslednost a budeme ps´ at R = hR, +, ·, 0, 1, ≤i. 3
Kdyˇz m´ame definov´ an pojem struktury, m˚ uˇzeme definovat pojem pravdivosti formule ve struktuˇre. Zamˇeˇr´ıme se na sentence, protoˇze pt´at se, jestli plat´ı napˇr. atomick´ a formule x+y < 1 nem´ a smysl. Nicm´enˇe m´a smysl se pt´at, jestli napˇr. plat´ı sentence ∀x∃y(x + y < 1). Nejprve vˇsak mus´ıme ˇr´ıct, jak se poˇc´ıt´ a hodnota termu. Definice 1.15 Mˇejme strukturu A a t term bez promˇenn´ ych (tj. obsahuje jen konstanty a funkˇcn´ı symboly). Pak jeho hodnotu tA v A definujeme takto: • Je-li term t konstatn´ı symbol c ∈ C, pak jeho hodnota je tA = cA . A • Je-li t = f (t1 , . . . , tn ) pro f ∈ F a ti termy, pak jeho hodnota je tA = f A (tA 1 , . . . , tn ).
Pˇ r´ıklad 1.16 Necht’ R je struktura re´ aln´ ych ˇc´ısel z pˇr´ıkladu 1.14 a t = (1 + 1) · (1 + (1 + 0)). Pak tR = 4. Nyn´ı jiˇz m˚ uˇzeme definovat pojem pravdivosti. Necht’ A je L-struktura. Budeme induktivnˇe definovat pravdivost L-sentence ϕ ve struktuˇre A. Znaˇcen´ı A |= ϕ. V opaˇcn´em pˇr´ıpadˇe budeme ps´ at A 6|= ϕ. Zaˇcneme definic´ı pro atomickou sentenci ϕ = P (t1 , . . . , tn ). Protoˇze ϕ je sentence a neobsahuje ˇz´adn´e kvantifik´ atory, nem˚ uˇze obsahovat ˇz´adn´e promˇenn´e. Tud´ıˇz m˚ uˇzeme spoˇc´ıtat hodnoty tA i A A podle Definice 1.15. M´a smysl tedy definovat A |= ϕ pr´avˇe tehdy, kdyˇz (tA 1 , . . . , tn ) ∈ P . D´ale si uk´ aˇzeme, jak definovat provadivost pro sloˇzitˇejˇs´ı sentence v z´avislosti na jej´ıch podformul´ıch. • Necht’ ϕ = ¬ψ. Pak A |= ϕ pr´avˇe tehdy, kdyˇz A 6|= ψ (tj. ψ je nepravdiv´a v A). • Necht’ ϕ = ψ ∧ χ. Pak A |= ϕ pr´avˇe tehdy, kdyˇz A |= ψ a A |= χ. • Necht’ ϕ = ψ ∨ χ. Pak A |= ϕ pr´avˇe tehdy, kdyˇz A |= ψ nebo A |= χ. • Necht’ ϕ = ψ ⇒ χ. Pak A 6|= ϕ pr´avˇe tehdy, kdyˇz A |= ψ a A 6|= χ. • Necht’ ϕ = ψ ⇔ χ. Pak A |= ϕ pr´avˇe tehdy, kdyˇz bud’ A |= ψ a A |= χ nebo A 6|= ψ a A 6|= χ. Posledn´ı, co zb´ yv´a je nadefinovat pravdivost sentenc´ı tvaru ϕ = ∀xψ a ϕ = ∃xψ. Pokud ψ neobsahuje voln´ y v´ yskyt promˇenn´e x, pak definujeme A |= ϕ pr´avˇe tehdy, kdyˇz A |= ψ. V ostatn´ıch pˇr´ıpadech rozˇs´ıˇr´ıme n´aˇs jazyk L tak, aby obsahoval konstantn´ı symboly pro vˇsechny prvky universa A. Definice 1.17 Necht’ L je jazyk a A je L-struktura. Pak LA je jazyk, kter´ y vznikne z L pˇrid´ an´ım konstatn´ıch symbol˚ u pro kaˇzd´ y prvek A, tj. LA = L∪{ca | a ∈ A}. Symbolem AC pak oznaˇcujeme LA -strukturu, kter´a vznikne z A interpretac´ı Jca K = a. Symboly ca , a budeme obˇcas ztotoˇzn ˇovat. Pravdivost sentence ϕ nyn´ı m˚ uˇzeme definovat pomoc´ı pravdivosti v LA -struktuˇre AC . Necht’ ϕ = ∀xψ(x). Pak A |= ϕ pr´avˇe tehdy, kdyˇz pro vˇsechny a ∈ A plat´ı AC |= ψ(ca ). Pokud ϕ = ∃xψ(x). Pak A |= ϕ pr´avˇe tehdy, kdyˇz existuje a ∈ A takov´e, ˇze AC |= ψ(ca ). Pojem pravdivosti sentence ve struktuˇre A rozˇs´ıˇr´ıme na formule ϕ(x1 , . . . , xn ), co nejsou sentencemi tak, ˇze z nich sentence udˇel´ame. Definujeme A |= ϕ(x1 , . . . , xn ) pr´avˇe tehdy, kdyˇz A |= ∀x1 · · · ∀xn ϕ(x1 , . . . , xn ). Pˇ r´ıklad 1.18 Necht’ L = {R}, kde R je bin´ arn´ı predik´at. Uvaˇzujme L-strukturu A = hA, RA i, A kde R = {(p, q), (p, r), (q, r)}. Urˇcete, jestli 1. A |= ¬∃x R(x, x), 2. A |= ∀x∀y∀z((R(x, y) ∧ R(y, z)) ⇒ R(x, z)).
4
q
r p
Obr´ azek 1: Relace RA na mnoˇzinˇe A. ˇ sen´ı Struktura A se skl´ Reˇ ad´a z nosn´e mnoˇziny A a bin´ arn´ı relace RA . M˚ uˇzeme si ji tedy zobrazit jako orientovan´ y graf. 1. Podle definice pravdivosti m´ame, ˇze A |= ¬∃x R(x, x) pr´avˇe tehdy, kdyˇz A 6|= ∃x R(x, x). Takˇze mus´ıme zjistit, jestli je sentence ∃x R(x, x) nepravdiv´a v A. Opˇet podle definice pravdivosti to znamen´a, ˇze neexistuje a ∈ A takov´e, ˇze (a, a) ∈ RA . Inspekc´ı prvk˚ u RA zjist´ıme, ˇze takov´e a skuteˇcnˇe neexistuje, a tud´ıˇz A |= ¬∃x R(x, x). Neform´alnˇe ˇreˇceno n´am sentence ¬∃x R(x, x) ˇr´ık´a, ˇze ve v´ yˇse uveden´em grafu neexituje ˇz´adn´ y bod, ze kter´eho by vedla ˇsipka do nˇeho samotn´eho. 2. Podle definice pravdivosti m´ame, ˇze A |= ∀x∀y∀z((R(x, y)∧R(y, z)) ⇒ R(x, z)) pr´avˇe tehdy, kdyˇz pro vˇsechna a, b, c ∈ A plat´ı AC |= (R(a, b) ∧ R(b, c)) ⇒ R(a, c). Jelikoˇz implikace je neplatn´ a jen v pˇr´ıpadech, kdy plat´ı pˇredpoklad a neplat´ı z´avˇer, staˇc´ı zjistit, jestli tento pˇr´ıpad m˚ uˇze nastat. Pˇredpoklad R(a, b) ∧ R(b, c) lze splnit jedinˇe tak, ˇze a = p, b = q a c = r. V tomto pˇr´ıpadˇe ale plat´ı i z´avˇer R(a, c), protoˇze (p, r) ∈ RA . Z toho vypl´ yv´a, ˇze implikaci nelze uˇcinit nepravdivou, takˇze A |= ∀x∀y∀z((R(x, y) ∧ R(y, z)) ⇒ R(x, z)). Zkr´acenˇe ˇreˇceno sentence ∀x∀y∀z((R(x, y) ∧ R(y, z)) ⇒ R(x, z)) ˇr´ık´a, ˇze relace RA je tranzitivn´ı, coˇz je opˇet z obr´ azku dobˇre patrn´e. Pˇ r´ıklad 1.19 Necht’ ϕ je sentence ∀x∃y(x = y + y). Uvaˇzujme strukturu R = hR, +, ·, 0, 1, ≤i a podobnˇe strukturu cel´ ych ˇc´ısel Z = hZ, +, ·, 0, 1, ≤i, kde symboly +, ·, 0, 1, ≤ maj´ı bˇeˇzn´ y v´ yznam. Rozhodnˇete jestli plat´ı n´asleduj´ıc´ı tvrzen´ı: 1. R |= ϕ, 2. Z |= ϕ. ˇ sen´ı Pˇripomeˇ Reˇ nme, ˇze symbol = je v kaˇzd´e struktuˇre interpretov´ an jako identick´ a relace na nosn´e mnoˇzinˇe, tj. jako rovnost. 1. Sentence ϕ je pravdiv´a ve struktuˇre R pr´avˇe tehdy, kdyˇz pro vˇsechna a ∈ R existuje b ∈ R takov´e, ˇze a = b + b. To jistˇe pro re´ aln´a ˇc´ısla plat´ı, protoˇze m˚ uˇzeme za b vz´ıt prvek a/2 ∈ R. Z toho plyne, ˇze R |= ϕ. 2. Pro strukturu Z postupujeme podobnˇe. Tady ovˇsem vid´ıme, pro nˇekter´ a a ∈ Z nemus´ı existovat b ∈ Z takov´e, ˇze a = b + b. Napˇr. pro a = 3. Vhodn´e b existuje, jen pokud je a dˇeliteln´e dvˇemi. Z toho plyne, ˇze Z 6|= ϕ. Definice 1.20 Necht’ L je jazyk, ϕ je L-formule a A je L-struktura. Pokud A |= ϕ, pak naz´ yv´ame A model ϕ. Podobnˇe pokud M je mnoˇzina L-formul´ı, pak A naz´ yv´ame model M , pokud pro vˇsechny ψ ∈ M plat´ı A |= ψ. Definice 1.21 Necht’ L je jazyk a ϕ je L-formule. Pak 5
• ϕ naz´ yv´ame tautologi´ı, pokud A |= ϕ pro kaˇzdou L-strukturu A (tj. kaˇzd´e A je model ϕ), • ϕ naz´ yv´ame splnitelnou, pokud existuje L-struktura A takov´ a, ˇze A |= ϕ (tj. existuje model ϕ), • ϕ naz´ yv´ame nesplnitelnou (kontradikc´ı), pokud neexistuje L-struktura A takov´ a, ˇze A |= ϕ (tj. neexistuje model ϕ). Definice 1.22 Necht’ L je jazyk a M je mnoˇzina L-formul´ı. Pak • M naz´ yv´ame splnitelnou, pokud existuje model M , • M naz´ yv´ame nesplnitelnou, pokud neexistuje model M . ˇ Definice 1.23 Necht’ L je jazyk. Rekneme, ˇze L-sentence ϕ je s´emantick´ ym d˚ usledkem (konsekventem) mnoˇziny L-sentenc´ı S, pokud kaˇzd´ y model mnoˇziny S je tak´e modelem sentence ϕ. Znaˇc´ıme S |= ϕ. M´ısto {ψ} |= ϕ p´ıˇseme ψ |= ϕ a m´ısto ∅ |= ϕ p´ıˇseme |= ϕ. Pozn´ amka 1.24 V predik´atov´e logice m´a symbol |= v´ıce v´ yznam˚ u. V´ yˇse definovan´ y v´ yznam je analogick´ y s v´ yznanem |= ve v´ yrokov´e logice. Druh´ y v´ yznam je v´ yznam pravdivosti formule ve struktuˇre.
6
