logica cu predicate de ordinul i curs 1 -...

Logica cu predicate de ordinul ICurs 1 - Sintaxa

Stefan Ciobaca

9 Noiembrie 2015

Logica de predicate de ordinul I (LP1)

1. o noua logica, mai expresiva decat LP

2. ın engleza: first-order logic (FOL)

LP1 ın loc de LP - motivat, ie

Vreau sa modelez ın LP urmatorul rat, ionament: “S, tiu ca daca suntom atunci sunt muritor s, i ca sunt om. Deci sunt muritor.”Fie p, q ∈ A doua variabile propozit, ionale.

1. p - “sunt om”

2. q - “sunt muritor”

In logica propozit, ionala, p → q, p |= q corespunde rat, ionamentuluide mai sus.

LP1 ın loc de LP - motivat, ie

Vreau sa modelez urmatorul rat, ionament: “S, tiu ca daca cinevaeste om atunci acea persoana este muritor. S, tiu ca Socrates esteom. Deci Socrates este muritor.”(imposibil de modelat ın LP).Privire fugara ın LP1:

1. P(x) - “x este om”

2. Q(x) - “x este muritor”

3. S - “Socrates”

In LP1, avem ∀x .(P(x)→ Q(x)),P(S) |= Q(S).

LP1

1. variabile, simboluri funct, ionale, termeni

2. simboluri predicative, formule

3. pozit, ii

4. aparit, ii legate/libere, variabile legate/libere

5. substitut, ii

Not, iunea de termen (sau term)

1. Fixam X - o mult, ime infinit numarabila de simboluri numitevariabile (a nu se confunda cu variabilele propozit, ionale dinLP).

2. Fixam F = {F0,F1,F2, . . .}, unde:

2.1 F0 este mult, imea simbolurilor funct, ionale de aritate 0.2.2 F1 este mult, imea simbolurilor funct, ionale de aritate 1.2.3 F2 este mult, imea simbolurilor funct, ionale de aritate 2.2.4 . . .


F - mult, ime indexata de simboluri funct, ionale.

1. F0 - simboluri constante,

2. F1 - simboluri funct, ionale unare,

3. F2 - simboluri funct, ionale binare,

4. F3 - simboluri funct, ionale ternare,

5. Fn - simboluri funct, ionale n-are.

Exemplu

Fie X = {x , y , z , x1, x2, x3, . . .}. Fie F0 = {c}, F1 = {h} s, iF2 = {f , g}.


Alfabetul termenilor este AlfT = {′(′,′ )′} ∪ X ∪ F0 ∪ F1 ∪ . . ..Termenii sunt s, iruri de caractere peste AlfT , definit, i astfel:

Definit, ie

Mult, imea T (a termenilor) este definita inductiv astfel:

1. orice variabila x ∈ X este termen: x ∈ T2. orice simbol constant c ∈ F0 este termen: c ∈ T3. daca n ∈ {1, 2, . . .}, f ∈ Fn este un simbol funct, ional de

aritate n s, i t1, t2, . . . , tn ∈ T sunt termeni, atunci f (t1, . . . , tn)este termen.


Exemplu

In continuarea exemplului de mai sus: fieX = {x , y , z , x1, x2, x3, . . .}. Fie F0 = {c}, F1 = {h} s, iF2 = {f , g}, avem urmatorii termeni:

x ∈ T y ∈ T x3 ∈ T c ∈ Th(x) ∈ T h(y) ∈ T h(c) ∈ T

g(x , y) ∈ T f (c , c) ∈ T f (c , y) ∈ Tf (h(x), y) ∈ T g(h(c), h(c)) ∈ T f (c , y) ∈ T

f

(g(

f (x , y), h(c)), f (c , c)

)∈ T

1. orice variabila x ∈ X este termen: x ∈ T2. orice simbol constant c ∈ F0 este termen: c ∈ T3. daca n ∈ {1, 2, . . .}, f ∈ Fn este un simbol funct, ional de

aritate n s, i t1, t2, . . . , tn ∈ T sunt termeni, atunci f (t1, . . . , tn)este termen.

Formule atomice

Vom fixa ın continuare o mult, ime indexata de simboluri predicative:

P = {P0,P1,P2, . . .}.

1. P0 este mult, imea simbolurilor predicative constante,

2. P1 este mult, imea simbolurilor predicative unare,

3. P2 este mult, imea simbolurilor predicative binare iar

4. Pn este mult, imea simbolurilor predicative n-are.

Definit, ie

Mult, imea At, a formulelor atomice, este definita astfel:

1. P0 ⊆ At,

2. daca P ∈ Pn (cu n ≥ 1) s, i t1, . . . , tn ∈ T , atunciP(t1, . . . , tn) ∈ At.

Formule atomice

Exemplu

Fie P0 = {P}, P1 = {Q} s, i P2 = {R} (P3 = P4 = . . . = ∅).Cateva exemple de formule atomice sunt:

P ∈ At

Q(x) ∈ At Q(c) ∈ At Q(f (f (x , y), c)) ∈ At

R(

c , x)∈ At R

(h(x), f (x , y)

)∈ At

R

(f(

f (x , y), f (x , y)), h(c)

)∈ At

Formulele atomice sunt s, iruri de caractere peste alfabetulAlfAt = AlfT ∪ P0 ∪ P1 ∪ P2 ∪ . . . .

Formule LP1

Definit, ie

Mult, imea LP1 (formule din logica de ordinul I) este definitainductiv astfel:

1. At ⊆ LP1;

2. Daca F ∈ LP1, atunci (¬F ) ∈ LP1 s, i (F ) ∈ LP1;

3. Daca F1,F2 ∈ LP1, atunci (F1 ∧ F2) ∈ LP1, (F1 ∨ F2) ∈ LP1

(s, i (F1 → F2) ∈ LP1);

4. Daca F ∈ LP1 s, i x ∈ X , atunci (∀x)(F ) ∈ LP1 (s, i(∃x)(F ) ∈ LP1).

Exemplu

P ∈ LP1

Q(x) ∈ LP1 R(

h(x), f (x , y))∈ LP1 (¬Q(f (x , y))) ∈ LP1

(P ∧ Q(x)) ∈ LP1

(Q(x) ∨ R

(h(x), f (x , y)

))∈ LP1

(Q(x)→ R(x , y)) ∈ LP1 ((Q(x) ∧ P) ∨ Q(y)) ∈ LP1

(∀x)((Q(x) ∨ P(x))) ∈ LP1 ((∃x)(Q(x)) ∨ (¬P)) ∈ LP1

1. At ⊆ LP1;

2. Daca F ∈ LP1, atunci (¬F ) ∈ LP1 s, i (F ) ∈ LP1;

3. Daca F1,F2 ∈ LP1, atunci (F1 ∧ F2) ∈ LP1, (F1 ∨ F2) ∈ LP1

(s, i (F1 → F2) ∈ LP1);

4. Daca F ∈ LP1 s, i x ∈ X , atunci (∀x)(F ) ∈ LP1 (s, i(∃x)(F ) ∈ LP1).

Sumar

Mult, imea termenilor (T ):

t ::= x | c | f (t, . . . , t︸︷︷︸n

) x ∈ X , c ∈ F0, f ∈ Fn

Mult, imea formulelor atomice (At):

a ::= P | Q(t, . . . , t︸︷︷︸n

) P ∈ P0,Q ∈ Pn

Mult, imea formulelor de ordinul I (LP1):

F ::= a | (¬F ) | (F ) | (F ∨ F ) | (F ∧ F ) |(F → F ) | (∀x)(F ) | (∃x)(F ) a ∈ At, x ∈ X

Exemplu

P1 = {P,Q},F0 = {s}

1. P(x) - “x este om”

2. Q(x) - “x este muritor”

((∀x)(P(x)→ Q(x)) ∧ P(s)

)→ Q(s)

Exemplu

P2 = {L}

I L(x , y) - “x ıl iubes, te pe y”

1. (∀x)((∃y)(L(x , y)))“everybody has somebody whom they love” (Optimist)

2. (∃y)((∀x)(L(x , y)))“there is someone who everyone loves” (Popular)

3. (∀y)((∃x)(L(x , y)))“everyone is loved by someone” (Hopeless Romantic)

4. http://ctp200.com/comic/27

http://ctp200.com/comic/27

Arborele asociat unui termen

1. daca t = c , c ∈ F0, atunci arb(t) =c

2. daca t = x , x ∈ X , atunci arb(t) =x

3. daca t = f (t1, . . . , tn), f ∈ Fn (n > 0), t1, . . . , tn ∈ T , atunci

arb(t) =

f

()

arb(t1) . . . arb(tn)

Arborele asociat unui termen - exemplu

arb(f (x , h(y))) =

f

()

x h

()

y

Arborele abstract asociat unui termen

1. daca t = c , c ∈ F0, atunci arba(t) =c

2. daca t = x , x ∈ X , atunci arba(t) =x

3. daca t = f (t1, . . . , tn), f ∈ Fn (n > 0), t1, . . . , tn ∈ T , atunci

arba(t) =

f

arba(t1) . . . arba(tn)

Arborele abstract asociat unui termen - exemplu

arb(f (x , h(y))) =

f

x h

y

Arborele asociat unei formule - ¬, ()

I daca F = (¬F1), atunci arb(F ) =

()

¬

arb(F1)

I daca F = (F1), atunci arb(F ) =

()

arb(F1)

Arborele asociat unei formule - P(t1, . . . , tn)

I daca F = P(t1, . . . , tn), atunci

arb(F ) =

P

()

arb(t1) . . . arb(tn)

Arborele asociat unei formule - ∧

I daca F = (F1 ∧ F2), atunci arb(F ) =

()

∧

arb(F1) arb(F2)

Arborele asociat unei formule - ∨

I daca F = (F1 ∨ F2), atunci arb(F ) =

()

∨

arb(F1) arb(F2)

Arborele asociat unei formule - →

I daca F = (F1 → F2), atunci arb(F ) =

()

→

arb(F1) arb(F2)

Arborele asociat unei formule - ∀

I daca F = (∀x)(F1), atunci arb(F ) =

∀x

()

arb(F1)

Arborele asociat unei formule - ∃

I daca F = (∃x)(F1), atunci arb(F ) =

∃x

()

arb(F1)

Exemplu

arb((∃x)((Q ∧ P))) =

∃x

()

()

∧

Q P

Arborele abstract asociat unei formule - ¬, ()

I daca F = (¬F1), atunci arba(F ) =

¬

arba(F1)

I daca F = (F1), atunci arba(F ) = arba(F1)

Arborele abstract asociat unei formule - P(t1, . . . , tn)

I daca F = P(t1, . . . , tn), atunci

arba(F ) =

P

arba(t1) . . . arba(tn)

Arborele abstract asociat unei formule - ∧

I daca F = (F1 ∧ F2), atunci

arba(F ) =

∧

arba(F1) arba(F2)

Arborele abstract asociat unei formule - ∨

I daca F = (F1 ∨ F2), atunci

arba(F ) =

∨

arba(F1) arba(F2)

Arborele abstract asociat unei formule - →

I daca F = (F1 → F2), atunci

arba(F ) =

→

arba(F1) arba(F2)

Arborele abstract asociat unei formule - ∀

I daca F = (∀x)(F1), atunci arba(F ) =

∀x

arba(F1)

Arborele abstract asociat unei formule - ∃

I daca F = (∃x)(F1), atunci arba(F ) =

∃x

arba(F1)

Exemplu

arba((∃x)(Q(x) ∧ P)) =

∃x

∧

Q

x

P

Despre paranteze

La fel cum scriem −3× 4 + 5 ın loc de (((−3)× 4) + 5), vomrenunt,a la paranteze dupa cum urmeaza:

1. vom scrie ¬P(x) ∧ Q(y) ∨ R(x , y) ın loc de(((¬P(x)

)∧ Q(y)

)∨ R(x , y)

)(la fel ca la logica

propozit, ionala).

Ordinea de prioritate: ¬, ∀, ∃,∧,∨,→.

Exemplu

(∀x)(

P(x) ∧ ¬Q(x)→ R(x))

ın loc de

(∀x)

(((P(x) ∧ (¬Q(x))

)→ R(x)

))ın loc de

When in doubt: use parantheses.Observat, ie: cateodata vom scrie ∀x .F ın loc de (∀x)(F ).

Pozit, iile unui termen

Definit, ie

O pozitie p este un sir de numere naturale n1 · . . . · nk . Pentruk = 0, sirul vid este notat cu ε.

Exemplu

Spre exemplu, o pozitie este p = 0 · 2 · 1.


Definit, ie

Pozitiile atasate unui termen, notate pos(t), sunt:

1. pos(c) = {ε}, daca c ∈ F0

2. pos(x) = {ε}, daca x ∈ X3. pos(f (t1, . . . , tn)) = {ε} ∪

⋃i∈{1,...,n} i · pos(ti ), daca f ∈ Fn.

In definitia de mai sus, am notat cu i · P multimea de pozitiiobtinuta din P prin adaugarea numarului i ın fata:i · P = {i · p | p ∈ P}.

Exemplu

Pentru t = f (g(a, b), y), avem pos(t) = {ε, 1, 2, 1 · 1, 1 · 2}.


Exemplu

Pentru t = f (g(a, b), y), avem pos(t) = {ε, 1, 2, 1 · 1, 1 · 2}.

f (ε)

g (1)

a (1 · 1) b (1 · 2)

y (2)


Definit, ie

Fie t un termen si fie p ∈ pos(t) o pozitie a termenului. Termenulaflat la pozitia p ın termenul t, notat t|p este definit astfel:

1. t|ε = t,

2. f (t1, . . . , tn)|i ·p = (ti )|p.

Exemplu

Pentru t = f (g(a, b), y), si p = 1, avem t|p = g(a, b). Dacaq = 1 · 2, atunci t|q = b.

Pozit, iile unei formule

Functia pos se extinde si asupra formulelor:

Definit, ie

1. pos(P(t1, . . . , tn)) = {ε} ∪⋃

i∈{1,...,n} i · pos(ti ),

2. pos(¬F ) = {ε} ∪ 1 · pos(F ),

3. pos(F1 ∧ F2) = pos(F1 ∨ F2) = pos(F1 → F2) ={ε} ∪ 1 · pos(F1) ∪ 2 · pos(F2),

4. pos(∀x .F1) = pos(∃x .F1) = {ε} ∪ 1 · pos(F1).

Pozit, iile unei formule

Termenul sau formula aflat/aflata la pozitia p ın formula F ,notat(a) F |p este:

Definit, ie

1. F |ε = F ,

2. P(t1, . . . , tn)|i ·p = ti |p3. (¬F )|1·p = F |p,

4. (F1 ∧ F2)|i ·p = (F1 ∨ F2)|i ·p = (F1 → F2)|i ·p = (Fi )|p(i ∈ {1, 2}),

5. (∀x .F1)|1·p = (∃x .F1)|1·p = (F1)|p.

Exemplu((∀x)(P(x) ∧ Q(y))

)|1·2 = Q(y)

∀x (ε)

∧ (1)

P (1 · 1)

x (1 · 1 · 1)

Q (1 · 2)

y (1 · 2 · 1)

Aparit, ii ale variabilelor

Multimea variabilelor unui termen t este notata var(t) si estedefinita astfel:

Definit, ie

1. var(c) = ∅ (daca c ∈ F0)

2. var(x) = {x} (daca x ∈ F0)

3. var(f (t1, . . . , tn)) =⋃

i∈{1,...,n} var(ti )

Similar, se defineste var(F ) ca fiind multimea variabilelor dintr-oformula F .In mod alternativ,var(t) = {x ∈ X | exista p ∈ pos(t) a.i. t|p = x}.


Definit, ie

O aparitie a unei variabile x ıntr-o formula F (respectiv intr-untermen t) este o pozitie p a.i. F |p = x (respectiv t|p = x).

Definit, ie

O aparitie p a unei variabile y ıntr-o formula F este legata daca,exista un prefix q a lui p astfel incat F |q = ∀x .G sau F |q = ∃x .G(daca pe drumul de la aparitia respectiva spre radacina arboreluiformulei gasim un nod ∀x sau ∃x).O aparitie p a unei variabile y ıntr-o formula F este libera daca nueste legata.

Exemplu

F = (∀x .P(x)) ∧ Q(x)

∧ (ε)

∀x (1)

P (1 · 1)

x (1 · 1 · 1)

Q (2)

x (2 · 1)


Definit, ie

Multimea variabilelor unei formule care au cel putin o aparitielegata se noteaza bound(F ):

1. bound(P(t1, . . . , tn)) = ∅,2. bound(¬F1) = bound(F1),

3. bound(F1 ∧ F2) = bound(F1 ∨ F2) = bound(F1 → F2) =bound(F1) ∪ bound(F2),

4. bound(∀x .F1) = bound(∃x .F1) = bound(F1) ∪ {x}.

Exemplu

bound

((∀x .(

P(x)))∨ R(x , y)

)= {x}


Definit, ie

Multimea variabilelor unei formule care au cel putin o aparitielibera se noteaza free(F ):

1. free(P(t1, . . . , tn)) = var(t1) ∪ . . . ∪ var(tn),

2. free(¬F1) = free(F1),

3. free(F1 ∧ F2) = free(F1 ∨ F2) = free(F1 → F2) =free(F1) ∪ free(F2),

4. free(∀x .F1) = free(∃x .F1) = free(F1) \ {x}.

Atentie! free(F ) si bound(F ) pot avea elemente ın comun.

Exemplu

free

((∀x .(

P(x)))∨ R(x , y)

)= {x , y}


Exemplu

Fie F = P(x) ∧ ∀x .Q(x , y). Prima aparitie a lui x este libera.Singura aparitie a lui y este libera. A doua aparitie a lui x estelegata. Avem var(F ) = {x , y}, bound(F ) = {x} sifree(F ) = {x , y}.

Substitut, ii (forma triangulata)

Definit, ie

O substitutie elementara este o pereche formata dintr-o variabila xsi un termen t, notata [x/t].

Definit, ie

O substitutie (nu neaparat elementara) este un sir[x1/t1] · . . . · [xn/tn] de subtitutii elementare.

Observat, ii: daca n = 0, obtinem substitutia vida, care se noteazacu ε; daca n = 1, obt, inem o substitut, ie elementara.Substitutiile se noteaza cu σ, τ, σ0, τ1, σ

′, etc.


Definit, ie

Termenul obtinut prin aplicarea unei substitutii elementareσ = [x/t0] la un termen t, notat ın format sufix tσ, este definitastfel:

1. cσ = c, daca c ∈ F0,

2. xσ = t0,

3. yσ = y, daca y ∈ X si x 6= y,

4. f (t1, . . . , tn)σ = f (t1σ, . . . , tnσ).

Practic, fiecare aparitie a variabilei x este ınlocuita cu t0.

Exemplu

Fie σ = [x/h(a)] s, i t = f (x , g(x , b)).Atunci tσ = f (h(a), g(h(a), b)).


Definit, ie

Formula obtinuta prin aplicarea unei substitutii elementareσ = [x/t0] la o formula F , notata ın format sufix Fσ, este definitaastfel:

1. P(t1, . . . , tn)σ = P(t1σ, . . . , tnσ),

2. (¬F )σ = ¬(Fσ),

3. (F1opF2)σ = (F1σ)op(F2σ) (pentru orice op ∈ {∧,∨,→}),

4. (∀y .F )σ = ∀y .(Fσ) daca y ∈ X si x 6= y,

5. (∃y .F )σ = ∀y .(Fσ) daca y ∈ X si x 6= y,

6. (∀x .F )σ = F ,

7. (∃x .F )σ = F .

Practic, fiecare aparitie libera a variabilei x este ınlocuita cu t0.

Exemplu

Fie formula F =(∀x .P(x)

)∧ P(x) s, i substitut, ia elementara

σ = [x/h(y)].

Atunci Fσ =(∀x .P(x)

)∧ P(h(y)).

Substitut, ie permisa

Definit, ie

O formula F accepta o substitutie elementara [x/t] dacabound(F ) ∩ var(t) = ∅.Observat, ie: mai folosim expresia “[x/t] este permisa pentru F ” ınloc de “F accepta [x/t]”.

Exemplu

Fie F = ∀x .P(y) s, i σ = [y/h(x)].Avem Fσ = ∀x .P(h(x)).Formula F nu accepta substitut, ia σ.


Definit, ie

Termenul obtinut prin aplicarea unei substitutiiσ = [x1/t1] · . . . · [xn/tn] la un termen t, notat ın format sufix tσ,este definit astfel:

tσ =

(((t[x1/t1])[x2/t2]

). . .

)[xn/tn].

Practic, pentru aplicarea unei substitutii generale, se aplica, perand si ın ordine, fiecare substitutie elementara.

Exemplu

Fie t = f (x) s, i σ = [x/h(y)] · [y/a].

Atunci tσ =(

f (x)[x/h(y)])[y/a] = f (h(y))[y/a] = f (h(a)).


Definit, ie

Formula obtinuta prin aplicarea unei substitutiiσ = [x1/t1] · . . . [xn/tn] la o formula F , notata ın format sufix Fσ,este definita astfel:

Fσ =

(((F [x1/t1])[x2/t2]

). . .

)[xn/tn].

Exemplu

Fie F =(∀x .P(y)

)∧ P(x) s, i σ = [x/h(y)] · [y/a].

Atunci Fσ = ∀x .P(a) ∧ P(h(a)).


Definit, ie

O formula F accepta o substitutie (generala) [x1/t1] · . . . · [xn/tn]daca F accepta [x1/t1], F accepta [x2/t2], . . ., F accepta [xn/tn].

Observatie. Definitia de mai sus este echivalenta cu definitiaurmatoare:

Definit, ie (alternativ)

O formula F accepta o substitutie (generala) [x1/t1] · . . . · [xn/tn]daca F accepta [x1/t1], F [x1/t1] accepta [x2/t2], . . .,F ([x1/t1] · . . . · [xn−1/tn−1]) accepta [xn/tn].


Definit, ie

O substitutie [x1/t1] · . . . · [xn/tn] este normalizata daca, pentruorice termen t si pentru orice permutare {i1, . . . , in} = {1, . . . , n} aprimelor n numerale naturale nenule, avem:

t([x1/t1] · . . . · [xn/tn]) = t([xi1/ti1 ] · . . . · [xin/tin ]).

Altfel spus, o substitutie este normalizata daca ordinea aplicariisubstitutiilor elemenatare nu este importanta.

Exemplu

Fie σ = [x/h(y)] · [y/a]. Substitut, ia σ nu este normalizata.Fie t = f (x). Avem tσ = f (h(a)) darf (x)([y/a] · [x/h(y)]) = f (h(y)).Substitut, ia σ′ = [x/h(a)] · [y/a] este normalizata.

logica cu predicate de ordinul i curs 1 -...

Documents