Výroková a predikátová logika - VI

Výroková a predikátová logika - VI Petr Gregor KTIML MFF UK

ZS 2013/2014

Petr Gregor (KTIML MFF UK)

Výroková a predikátová logika - VI

ZS 2013/2014

1 / 24

Predikátová logika

Úvod

Predikátová logika Zabývá se tvrzeními o individuích, jejich vlastnostech a vztazích. I (x) ∧ Z (o(x), r)

“Je inteligentní a její otec zná pana rektora.” ˇ x je promenná, reprezentuje individuum,

r je konstantní symbol, reprezentuje konkrétní individuum, o je funkˇcní symbol, reprezentuje funkci, I , Z jsou relaˇcní (predikátové) symboly, reprezentují relace (vlastnost “být inteligentní” a vztah “znát”). (∀x)(∃y)(y = o(x))

“Každý má otce.”

(∀x) je všeobecný (univerzální) kvantifikátor (každé x), ˇ (∃y) je existenˇcní kvantifikátor (nejaké y), = je (binární) relaˇcní symbol, reprezentuje identickou relaci.



ZS 2013/2014

2 / 24

Základní syntax PL

Jazyk

Jazyk Jazyk 1. ˇrádu obsahuje ˇ promenné x, y, z, . . . , x0 , x1 , . . . (spoˇcetneˇ mnoho), ˇ množinu všech promenných znaˇcíme Var, funkˇcní symboly f , g , h, . . . , vˇcetneˇ konstantních symbolu˚ c, d, . . . , což jsou nulární funkˇcní symboly, relaˇcní (predikátové) symboly P, Q, R, . . . , pˇrípadneˇ symbol = (rovnost) jako speciální relaˇcní symbol, ˇ kvantifikátory (∀x), (∃x) pro každou promennou x ∈ Var, logické spojky ¬, ∧, ∨, →, ↔ závorky ( , ) , [ , ] , { , } , . . .

Každý funkˇcní i relaˇcní symbol S má danou aritu (ˇcetnost) ar(S) ∈ N. ˇ výrokové promenné, ˇ Poznámka Oproti výrokové logice nemáme (explicitne) lze je zavést jako nulární relaˇcní symboly. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

3 / 24


Jazyk

Signatura jazyka ˇ Logické symboly jsou promenné, kvantifikátory, logické spojky a závorky. Mimologické symboly jsou funkˇcní a relaˇcní symboly kromeˇ rovnosti. Rovnost (obvykle) uvažujeme zvlášt’. Signatura je dvojice hR, Fi disjunktních množin relaˇcních a funkˇcních symbolu˚ s danými aritami, pˇriˇcemž žádný z nich není rovnost. Signatura urˇcuje všechny mimologické symboly. Jazyk je dán signaturou L = hR, Fi a uvedením, zda jde o jazyk s rovností cˇ i bez rovnosti. Jazyk musí obsahovat alesponˇ jeden relaˇcní symbol (mimologický nebo rovnost). Poznámka Význam symbolu˚ není v jazyce urˇcen, napˇr. symbol + nemusí reprezentovat standardní sˇcítání.



ZS 2013/2014

4 / 24


Jazyk

Pˇríklady jazyku˚ Jazyk obvykle uvádíme výˇctem mimologických symbolu˚ s pˇrípadným ˇ upˇresnením, zda jde o funkˇcní cˇ i relaˇcní symboly a jakou mají aritu. Následující pˇríklady jazyku˚ jsou všechny s rovností. L = h i je jazyk cˇ isté rovnosti, L = hci ii∈N je jazyk spoˇcetneˇ mnoha konstant, L = h≤i je jazyk uspoˇrádání, L = hEi je jazyk teorie grafu, ˚

L = h+, −, 0i je jazyk teorie grup, ˇ L = h+, −, ·, 0, 1i je jazyk teorie teles,

L = h−, ∧, ∨, 0, 1i je jazyk Booleových algeber, L = hS, +, ·, 0, ≤i je jazyk aritmetiky, kde ci , 0, 1 jsou konstantní symboly, S, − jsou unární funkˇcní symboly,

+, · , ∧, ∨ jsou binární funkˇcní symboly, E, ≤ jsou binární relaˇcní symboly. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

5 / 24


Termy

Termy Jsou výrazy reprezentující hodnoty (složených) funkcí. Termy jazyka L jsou dány induktivním pˇredpisem ˇ (i) každá promenná nebo konstantní symbol je term, (ii) je-li f funkˇcní symbol jazyka L s aritou n > 0 a t0 , . . . , tn−1 jsou termy, pak je i výraz f (t0 , . . . , tn−1 ) term, (iii) každý term vznikne koneˇcným užitím pravidel (i), (ii). ˇ Konstantní term je term bez promenných. Množinu všech termu˚ jazyka L znaˇcíme TermL . Termu, jenž je souˇcástí jiného termu t, rˇíkáme podterm termu t. Strukturu termu mužeme ˚ reprezentovat jeho vytvoˇrujícím stromem. U binárních funkˇcních symbolu˚ cˇ asto používáme infixního zápisu, napˇr. píšeme (x + y) namísto +(x, y). Petr Gregor (KTIML MFF UK)


ZS 2013/2014

6 / 24


Termy

Pˇríklady termu˚ (S(0) + x) · y

a)

0

⊥

¬(x ∧ y)

y

S(0) + x S(0)

¬(x ∧ y) ∨ ⊥

x∧y

x b)

x

y

a) Vytvoˇrující strom termu (S(0) + x) · y jazyka aritmetiky. b) Výrokové formule se spojkami ¬, ∧, ∨, pˇrípadneˇ s konstantami >, ⊥ lze chápat jako termy jazyka Booleových algeber.



ZS 2013/2014

7 / 24


Formule

Atomické formule Jsou nejjednodušší formule. Atomická formule jazyka L je výraz R(t0 , . . . , tn−1 ), kde R je n-ární relaˇcní symbol jazyka L a t0 , . . . , tn−1 jsou termy jazyka L. Množinu všech atomických formulí jazyka L znaˇcíme AFmL . Strukturu atomické formule mužeme ˚ reprezentovat vytvoˇrujícím stromem z vytvoˇrujících podstromu˚ jejích termu. ˚ U binárních relaˇcních symbolu˚ cˇ asto používáme infixního zápisu, napˇr. t1 = t2 namísto = (t1 , t2 ) cˇ i t1 ≤ t2 namísto ≤ (t1 , t2 ). Pˇríklady atomických formulí Z (o(x), r),


x · y ≤ (S(0) + x) · y,


¬(x ∧ y) ∨ ⊥ = ⊥.

ZS 2013/2014

8 / 24


Formule

Formule Formule jazyka L jsou výrazy dané induktivním pˇredpisem (i) každá atomická formule jazyka L je formule, (ii) jsou-li ϕ, ψ formule, pak i následující výrazy jsou formule (¬ϕ) , (ϕ ∧ ψ) , (ϕ ∨ ψ) , (ϕ → ψ) , (ϕ ↔ ψ), ˇ (iii) je-li ϕ formule a x promenná, jsou výrazy ((∀x)ϕ) a ((∃x)ϕ) formule. (iv) každá formule vznikne koneˇcným užitím pravidel (i), (ii), (iii). Množinu všech formulí jazyka L znaˇcíme FmL . Formuli, jež je souˇcástí jiné formule ϕ, nazveme podformule formule ϕ. Strukturu formule mužeme ˚ reprezentovat jejím vytvoˇrujícím stromem.



ZS 2013/2014

9 / 24


Formule

Konvence zápisu ˇ Zavedení priorit binárních funkˇcních symbolu˚ napˇr. + , · umožnuje

ˇ závorky okolo podtermu vzniklého pˇri infixním zápisu vypouštet

symbolem vyšší priority, napˇr. x · y + z reprezentuje term (x · y) + z. ˇ ˇ Zavedení priorit logických spojek a kvantifikátoru˚ umožnuje vypouštet závorky okolo podformule vzniklé spojkou s vyšší prioritou. (1) →, ↔

(2) ∧, ∨

(3) ¬, (∀x), (∃x)

Okolo podformulí vzniklých ¬, (∀x), (∃x) lze závorky vypustit vždy. Mužeme ˚ vypustit závorky i okolo (∀x) a (∃x) pro každé x ∈ Var. ˇ vnejší ˇ závorky mužeme Rovnež ˚ vynechat. (((¬((∀x)R(x))) ∧ ((∃y)P(y))) → (¬(((∀x)R(x)) ∨ (¬((∃y)P(y)))))) ¬∀xR(x) ∧ ∃yP(y) → ¬(∀xR(x) ∨ ¬∃yP(y)) Petr Gregor (KTIML MFF UK)


ZS 2013/2014

10 / 24


Formule

Pˇríklad formule (∀x)(x · y ≤ (S(0) + x) · y) x · y ≤ (S(0) + x) · y x·y x

(S(0) + x) · y y

y

S(0) + x S(0)

x

0

Vytvoˇrující strom formule (∀x)(x · y ≤ (S(0) + x) · y).



ZS 2013/2014

11 / 24


Otevˇrené a uzavˇrené formule

ˇ Výskyt promenné ˇ Necht’ ϕ je formule a x je promenná. ˇ Výskyt promenné x ve ϕ je list vytvoˇrujícího stromu ϕ oznaˇcený x. ˇ Výskyt x ve ϕ je vázaný, je-li souˇcástí nejaké podformule ψ zaˇcínající kvantifikátorem (∀x) nebo (∃x). Není-li výskyt vázaný, je volný. ˇ Promenná x je volná ve ϕ, pokud má volný výskyt ve ϕ. Je vázaná ve ϕ, pokud má vázaný výskyt ve ϕ. ˇ Promenná x muže ˚ být zárovenˇ volná i vázaná ve ϕ. Napˇr. ve formuli (∀x)(∃y)(x ≤ y) ∨ x ≤ z. ˇ Zápis ϕ(x1 , . . . , xn ) znaˇcí, že x1 , . . . , xn jsou všechny volné promenné ˇ tvrdí). ve formuli ϕ. (O nich formule ϕ neco Poznámka Uvidíme, že pravdivostní hodnota formule (pˇri dané interpretaci ˇ symbolu) ˚ závisí pouze na ohodnocení volných promenných. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

12 / 24


Otevˇrené a uzavˇrené formule

Otevˇrené a uzavˇrené formule Formule je otevˇrená, neobsahuje-li žádný kvantifikátor. Pro množinu OFmL všech otevˇrených formulí jazyka L platí AFmL ( OFmL ( FmL . Formule je uzavˇrená (sentence), pokud nemá žádnou volnou ˇ ˇ promennou, tj. všechny výskyty promenných jsou vázané. ˇ pak všechny její Formule muže ˚ být otevˇrená i uzavˇrená zároven, termy jsou konstantní. x+y ≤0

(∀x)(∀y)(x + y ≤ 0) (∀x)(x + y ≤ 0) 1+0≤0

otevˇrená, ϕ(x, y) uzavˇrená (sentence), ani otevˇrená, ani uzavˇrená, ϕ(y) otevˇrená i uzavˇrená

Poznámka Uvidíme, že sentence má pˇri dané interpretaci symbolu˚ pevný ˇ význam, tj. její pravdivostní hodnota nezávisí na ohodnocení promenných. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

13 / 24


Instance a varianty

Instance ˇ Když do formule za volnou promennou x dosadíme term t, požadujeme, aby ˇ o termu t “totéž”, co pˇredtím rˇíkala o promenné ˇ vzniklá formule rˇíkala (nove) x. ϕ(x)

(∃y)(x + y = 1)

pro t = 1 lze ϕ(x/t)

(∃y)(1 + y = 1)

pro t = y nelze

(∃y)(y + y = 1)

“existuje prvek 1 − x”

“existuje prvek 1 − 1” ˇ “1 je delitelné 2”

ˇ Term t je substituovatelný za promennou x ve formuli ϕ, pokud po souˇcasném nahrazení všech volných výskytu˚ x za t nevznikne ve ϕ ˇ žádný vázaný výskyt promenné z t. Pak vzniklou formuli znaˇcíme ϕ(x/t) a zveme ji instance formule ϕ ˇ vzniklá substitucí termu t za promennou x do ϕ. ˇ t není substituovatelný za x do ϕ, práveˇ když x má volný výskyt v nejaké ˇ ˇ podformuli ϕ zaˇcínající (∀y) nebo (∃y) pro nejakou promennou y z t. Konstantní termy jsou substituovatelné vždy. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

14 / 24


Instance a varianty

Varianty ˇ Kvantifikované promenné lze (za urˇcitých podmínek) pˇrejmenovat tak, že vznikne ekvivalentní formule. ˇ Necht’ (Qx)ψ je podformule ve ϕ, kde Q znaˇcí ∀ cˇ i ∃, a y je promenná, tž. 1) y je substituovatelná za x do ψ, a 2) y nemá volný výskyt v ψ. Nahrazením podformule (Qx)ψ za (Qy)ψ(x/y) vznikne varianta formule ϕ v podformuli (Qx)ψ. Postupnou variací jedné cˇ i více podformulí ve ϕ vznikne varianta formule ϕ. Napˇr. (∃x)(∀y)(x ≤ y)

je formule ϕ,

(∃y)(∀y)(y ≤ y)

není varianta ϕ, neplatí 1),

(∃u)(∀v)(u ≤ v)

je varianta ϕ,

(∃x)(∀x)(x ≤ x)

není varianta ϕ, neplatí 2).



ZS 2013/2014

15 / 24

Základní sémantika PL

Struktury

Struktury S = hS, ≤i uspoˇrádaná množina, kde ≤ je reflexivní, antisymetrická, tranzitivní binární relace na S,

G = hV , Ei neorientovaný graf bez smyˇcek, kde V je množina vrcholu, ˚

E je ireflexivní, symetrická binární relace na V (sousednost), Zp = hZp , +, −, 0i grupa sˇcítání celých cˇ ísel modulo p, ˇ Q = hQ, +, −, ·, 0, 1i teleso racionálních cˇ ísel.

P(X ) = hP(X ), −, ∩, ∪, ∅, X i potenˇcní algebra nad množinou X , N = hN, S, +, ·, 0, ≤i standardní model aritmetiky (pˇrirozených cˇ ísel), koneˇcné automaty a další modely výpoˇctu, relaˇcní databáze, . . .



ZS 2013/2014

16 / 24


Struktury

Struktura pro jazyk Necht’ L = hR, Fi je jazyk a A je neprázdná množina.

Realizace (interpretace) relaˇcního symbolu R ∈ R na A je libovolná relace R A ⊆ A ar(R) . Realizace rovnosti na A je relace IdA (identita).

Realizace (interpretace) funkˇcního symbolu f ∈ F na A je libovolná

funkce f A : A ar(f ) → A. Realizace konstantního symbolu je tedy prvek z A. Struktura pro jazyk L (L-struktura) je trojice A = hA, RA , F A i, kde

A je neprázdná množina, zvaná doména (univerzum) struktury A, RA = hR A | R ∈ Ri je soubor realizací relaˇcních symbolu˚ (relací),

F A = hf A | f ∈ Fi je soubor realizací funkˇcních symbolu˚ (funkcí). Strukturu pro jazyk L nazýváme také model jazyka L. Tˇrída všech modelu˚ jazyka L se znaˇcí M (L). Napˇr. struktury pro jazyk L = h≤i jsou hN, ≤i, hQ, >i, hX , Ei, hP(X ), ⊆i pokud X 6= ∅.



ZS 2013/2014

17 / 24


Pravdivostní hodnota

Hodnota termu Necht’ t je term jazyka L = hR, Fi a A = hA, RA , F A i je struktura pro L. ˇ Ohodnocení promenných v množineˇ A je funkce e : Var → A.

Hodnota t A [e] termu t ve struktuˇre A pˇri ohodnocení e je daná pˇredpisem x A [e] = e(x) pro každé x ∈ Var,

A (f (t0 , . . . , tn−1 ))A [e] = f A (t0A [e], . . . , tn−1 [e]) pro každé f ∈ F.

ˇ pro konstantní symbol c je c A [e] = c A . Speciálne, Je-li t konstantní term, jeho hodnota v A nezávisí na ohodnocení e. ˇ Hodnota termu v A závisí pouze na ohodnocení jeho promenných. Napˇr. hodnota termu x + 1 ve struktuˇre N = hN, +, 1i pˇri ohodnocení e

s e(x) = 2 je (x + 1)N [e] = 3.



ZS 2013/2014

18 / 24



Hodnota atomické formule Necht’ ϕ je atomická formule tvaru R(t0 , . . . , tn−1 ) jazyka L = hR, Fi a A = hA, RA , F A i je struktura pro L.

A Hodnota Hat (ϕ)[e] formule ϕ ve struktuˇre A pˇri ohodnocení e je ( A 1 pokud (t0A [e], . . . , tn−1 [e]) ∈ R A , A Hat (R(t0 , . . . , tn−1 ))[e] = 0 jinak. A pˇriˇcemž =A je IdA , tj. Hat (t0 = t1 )[e] = 1 pokud t0A [e] = t1A [e], jinak 0.

Je-li ϕ sentence, tj. všechny její termy jsou konstantní, její hodnota v A nezávisí na ohodnocení e.

ˇ Hodnota ϕ v A závisí pouze na ohodnocení jejích (volných) promenných. Napˇr. hodnota formule ϕ tvaru x + 1 ≤ 1 ve struktuˇre N = hN, +, 1, ≤i pˇri N ohodnocení e je Hat (ϕ)[e] = 1 práveˇ když e(x) = 0.



ZS 2013/2014

19 / 24



Hodnota formule Hodnota H A (ϕ)[e] formule ϕ ve struktuˇre A pˇri ohodnocení e je A H A (ϕ)[e] = Hat (ϕ)[e] pokud ϕ je atomická,

H A (¬ϕ)[e] = −1 (H A (ϕ)[e])

H A (ϕ ∧ ψ)[e] = ∧1 (H A (ϕ)[e], H A (ψ)[e])

H A (ϕ ∨ ψ)[e] = ∨1 (H A (ϕ)[e], H A (ψ)[e])

H A (ϕ → ψ)[e] = →1 (H A (ϕ)[e], H A (ψ)[e])

H A (ϕ ↔ ψ)[e] = ↔1 (H A (ϕ)[e], H A (ψ)[e]) H A ((∀x)ϕ)[e] = min(H A (ϕ)[e(x/a)]) a∈A

H A ((∃x)ϕ)[e] = max(H A (ϕ)[e(x/a)]) a∈A

kde −1 , ∧1 , ∨1 , →1 , ↔1 jsou Booleovské funkce dané tabulkami a e(x/a) pro a ∈ A znaˇcí ohodnocení získané z e nastavením e(x) = a.

ˇ Pozorování H A (ϕ)[e] závisí pouze na ohodnocení volných promenných ve ϕ. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

20 / 24


Platnost (pravdivost)

Platnost pˇri ohodnocení ˇ (platí) ve struktuˇre A pˇri ohodnocení e, pokud Formule ϕ je splnena A H (ϕ)[e] = 1. Pak píšeme A |= ϕ[e], v opaˇcném pˇrípadeˇ A 6|= ϕ[e]. Platí A |= ¬ϕ[e]

A |= (ϕ ∧ ψ)[e]

A |= (ϕ ∨ ψ)[e]

A |= (ϕ → ψ)[e]

A |= (ϕ ↔ ψ)[e]

A |= (∀x)ϕ[e] A |= (∃x)ϕ[e]

⇔

⇔

⇔

⇔

⇔

⇔ ⇔

A 6|= ϕ[e]

A |= ϕ[e] a A |= ψ[e]

A |= ϕ[e] nebo A |= ψ[e]

A |= ϕ[e] implikuje A |= ψ[e] A |= ϕ[e] práveˇ když A |= ψ[e]

A |= ϕ[e(x/a)] pro každé a ∈ A ˇ A |= ϕ[e(x/a)] pro nejaké a∈A

Pozorování Necht’ t je substituovatelný za x do ϕ a ψ je varianta ϕ. Pak pro každou strukturu A a ohodnocení e platí 1) A |= ϕ(x/t)[e] práveˇ když A |= ϕ[e(x/a)] pro a = t A [e], 2) A |= ϕ[e] práveˇ když A |= ψ[e]. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

21 / 24


Platnost (pravdivost)

Platnost ve struktuˇre Necht’ ϕ je formule jazyka L a A je struktura pro L. ϕ je pravdivá (platí) ve struktuˇre A, znaˇceno A |= ϕ, pokud A |= ϕ[e] pro každé ohodnocení e : Var → A. V opaˇcném pˇrípadeˇ píšeme A 6|= ϕ. ϕ je lživá v A, pokud A |= ¬ϕ, tj. A 6|= ϕ[e] pro každé e : Var → A. ˇ Pro každé formule ϕ, ψ, promennou x a strukturu A platí (1) (2) (3) (4)

A |= ϕ

⇒

A 6|= ¬ϕ

A |= ϕ ∨ ψ

⇐

A |= ϕ nebo A |= ψ

A |= ϕ ∧ ψ A |= ϕ

⇔ ⇔

A |= ϕ a A |= ψ A |= (∀x)ϕ

Je-li ϕ sentence, je ϕ pravdivá v A cˇ i lživá v A a tedy implikace (1) platí i ˇ Je-li navíc ψ sentence, také implikace (3) platí i obrácene. ˇ obrácene. ˇ ϕ, tj. Z (4) plyne, že A |= ϕ práveˇ když A |= ψ, kde ψ je generální uzáver ˇ formule (∀x1 ) · · · (∀xn )ϕ, v níž x1 , . . . , xn jsou všechny volné promenné ϕ. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

22 / 24


Teorie - sémantika

Platnost v teorii Teorie jazyka L je libovolná množina T formulí jazyka L (tzv. axiomu). ˚ Model teorie T je L-struktura A taková, že A |= ϕ pro každé ϕ ∈ T ,

znaˇcíme A |= T .

Tˇrída modelu˚ teorie T je M (T ) = {A ∈ M (L) | A |= T }. Formule ϕ je pravdivá v T (platí v T ), znaˇcíme T |= ϕ, pokud A |= ϕ pro každý model A teorie T . V opaˇcném pˇrípadeˇ píšeme T 6|= ϕ. Formule ϕ je lživá v T , pokud T |= ¬ϕ, tj. je lživá v každém modelu T . Formule ϕ je nezávislá v T , pokud není pravdivá v T ani lživá v T . Je-li T = ∅, je M (T ) = M (L) a teorii T vynecháváme, pˇrípadneˇ ˇríkáme “v logice”. Pak |= ϕ znaˇcí, že ϕ je pravdivá ((logicky) platí, tautologie).

Dusledek ˚ T je množina θL (T ) všech sentencí jazyka L pravdivých v T , tj. θL (T ) = {ϕ ∈ FmL | T |= ϕ a ϕ je sentence}. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

23 / 24


Teorie - sémantika

Pˇríklad teorie Teorie uspoˇrádání T jazyka L = h≤i s rovností má axiomy x≤x

(reflexivita)

x≤y ∧ y≤x → x=y

x≤y ∧ y≤z → x≤z

(antisymetrie) (tranzitivita)

Modely T jsou L-struktury hS, ≤S i, tzv. uspoˇrádané množiny, ve kterých platí

axiomy T , napˇr. A = hN, ≤i nebo B = hP(X ), ⊆i pro X = {0, 1, 2}.

Formule ϕ ve tvaru x ≤ y ∨ y ≤ x platí v A, ale neplatí v B, nebot’ napˇr. B 6|= ϕ[e] pˇri ohodnocení e(x) = {0}, e(y) = {1}, je tedy nezávislá v T .

Sentence ψ ve tvaru (∃x)(∀y)(y ≤ x) je pravdivá v B a lživá v A, je tedy ˇ nezávislá v T . Píšeme B |= ψ, A |= ¬ψ. rovnež Formule χ ve tvaru (x ≤ y ∧ y ≤ z ∧ z ≤ x) → (x = y ∧ y = z) je

ˇ pravdivá v T , píšeme T |= χ, totéž platí pro její generální uzáver. Petr Gregor (KTIML MFF UK)


ZS 2013/2014

24 / 24

Výroková a predikátová logika - VI

Recommend Documents