Programare logică

An universitar 2015 – 2016

Anul II, Semestrul II

Vasile Alaiba <alaiba@info.uaic.ro>

http://profs.info.uaic.ro/~alaiba

Facultatea de Informatică, Universitatea „Al.I.Cuza” Iaşi

Recapitulare Logică

În prima parte a cursului vom face

recapitularea principalelor noțiuni de Logică

de care vom avea nevoie în acest semestru

Materialul suport va fi actualizat de la curs la

curs.

Urmăriți data ultimei actualizări:

29 februarie 2016

Sintaxa LP

Fie o mulţime de variabile propoziţionale, A

= {A1, A2, … }, mulţimea conectorilor logici

C = {, , } şi P = { ( , ) } mulţimea

parantezelor.

Formulele vor fi cuvinte peste alfabetul

L = A U C U P

Sintaxa LP

Baza (formulele elementare sunt formule). A LP .

Pas constructiv.

(i) Dacă F LP atunci ( F) LP.

(ii)Dacă F1, F2 LP atunci ( F1 F2 ) LP.

(iii) Dacă F1, F2 LP atunci ( F1 F2 ) LP.

(iv) Dacă F LP atunci (F) LP.

Arborele asociat unei formule

Să se construiască arborele asociat formulei:

A \/ B /\ C

B /\ (C \/ B /\ A)

B -> A /\ B \/ A

Mulțimea subformulelor

Baza. F = A A. Atunci subf(F) = {A}.

Pas constructiv.

(i) F = ( F1). Atunci subf(F) = subf(F1) U { ( F1) }.

(ii) F = (F1 F2). Atunci subf(F) = subf(F1) U subf(F2)

U { (F1 F2) }.

(iii) F = (F1 F2). Atunci subf(F) = subf(F1) U

subf(F2) U { (F1 F2) }. (iv) F = (F1). Atunci subf(F) = subf(F1) U { (F1) }

Mulțimea subformulelor

Să se construiască mulțimea subformulelor

asociate formulei:

A \/ B /\ C

B -> A /\ B \/ A

Semantica LP Orice funcţie S, S : A B se numeşte asignare.

Pentru fiecare asignare S există o unică extensie a acesteia,

S’ : LP B (numită structură sau interpretare), care

satisface:

(i) S’(A) = S(A), pentru fiecare A A.

(ii) S’(( F)) = S’(F) , pentru fiecare F LP.

(iii) S’((F1 F2) ) = S’(F1) • S’(F2), pentru fiecare F1, F2 LP.

(iv) S’((F1 F2) ) = S’(F1) + S’(F2), pentru fiecare F1, F2 LP.

Exercițiu

Fie F = A \/ B /\ ~C

Determinati o structură S astfel încât S(F) = 1

Determinati o structură S astfel încât S(F) = 0

Satisfiabilitate

O formulă F LP se numeşte satisfiabilă dacă

există măcar o structură S pentru care S(F) = 1

O formulă este validă (tautologie) dacă pentru

orice structură S, S(F) = 1

O formulă este nesatisfiabilă (contradicţie)

dacă pentru orice structură S, S(F) = 0

Forme normale în LP

Formă normală conjunctivă (FNC)

Clauze

Formă normală conjunctivă (FNC)

O formulă F LP se află în FNC dacă este o

conjuncţie de disjuncţii de literali, adică o conjuncţie

de clauze. Simbolic:

miLLF ji

n

jji

n

j

m

i

ii

,C notam ,)( ,1

i,11

Clauze (1)

Clauză

Este orice disjuncţie (finită) de literali.

Clauză Horn

Este o clauză care are cel mult un literal pozitiv.

Clauză pozitivă

Este o clauză care conţine doar literali pozitivi

Clauze (2)

Clauză negativă

Este o clauză care conţine doar literali negativi.

Clauză definită (definite clause)

Clauză Horn pozitivă

Conţine exact un literal pozitiv

Formule Horn

O formulă în FNC în care toate clauzele sunt

Horn

Scrierea implicațională

A \/ B \/ C == A /\ B -> C

A \/ B == A /\ B -> 0

A == 1 -> A

Exercițiu

Să se aplice algoritmul Horn formulei:

F = ( A D ) ( C A D )

( A B ) D E

F = (D \/ A) /\ (A \/ B) /\ A /\ (B \/ C) /\ (C \/ D)

Rezoluție în LP

Fie clauzele C1, C2 , R.

R = ResL(C1, C2) (R este rezolventul lui C1,

C2), dacă există un literal L C1 astfel încât

L C2 şi R = (C1 \ {L}) U (C2 \ { L })

F este nesatisfiabilă dacă şi numai dacă

Res*(F).

Exerciții

Găsiți o respingere pentru formula: F = {{A, B, C}, {A}, {A, B, C}, {A, B}}

Sintaxa LP1 (1)

variabile (funcţionale) X = {x1, x2, …}

simboluri predicative P = {P0, P1, …}

variabile predicative P0

simboluri funcţionale F = {F0, F1, ...}:

constante (funcţionale) F0

conectori logici C1 = {, , }

cuantificatori C2 = universali {(x) | x X} U

existenţiali {( x) | x X}

paranteze P = { (, ) }

Sintaxa LP1 (2)

Alf = X U (U Pi ) U (U Fi ) U C1 U C2 U P

T este mulţimea termilor (funcţionali)

Baza:

X T

Fo T

Pas constructiv:

Pentru fiecare n N*, f Fn, t1, t2, …, t n T,

avem f(t1, t2, …, t n) T.

Sintaxa LP1 (3)

LP1 este dată constructiv

Baza: At – mulţimea formulelor atomice

Po At

Pentru fiecare n N*, P Pn, t1, t2, …, tn T,

avem P(t1, t2, …, tn) At.

Pas constructiv: dacă F, F1, F2 LP1 atunci:

(F) LP1

(F1) (F2) LP1, (F1) (F2) LP1

(x)(F) LP1, ( x)(F) LP1

(F) LP1

Exerciții

Identificați simbolurile care apar în formule.

Construiți mulțimea subformulelor și arborele

asociat.

Formulele:

(∀x)(P(x, a) ∧ Q(y) ∨ (∃z)P(z, x))

(∃x)(∀z)(P(x, y, z) ∨ Q(x)) ∧ (∀x)(Q(x) ∧

∧ R(f(x, z), a))

Variabilă liberă şi legată

Fie F LP1, x X:

x – apariţie legată dacă este parte a unei

subformule G a lui F de forma

G1 = (x)(G)

G2 = (x)(G)

x – apariţie liberă în caz contrar.

Substituții

Substituție elementară este o pereche de tipul [x/t], unde x X, t T.

Prin substituţie vom înţelege o secvenţă finită de forma s = [x1/t1]•[x2/t2]• … •[xn/tn], nN, xi X, ti T.

O substituţie s se aplică unei formule F, rezultând o formulă G, notată (F)s, care se obţine din F prin înlocuirea fiecărei apariţii libere a variabilei xi cu termul ti, în ordinea dată în s.

Tipuri de substituții

Substituţia elementară [x/t] este permisă pentru F dacă t nu conţine variabile libere care au apariţii legate în F.

O substituţie s este normalizată pentru F dacă (F)s = (F)s’, pentru fiecare s’ care este obţinută din s printr-o permutare a componentelor acesteia, deci ordinea de aplicare a substituţiilor elementare componente nu contează.

Substituţia vidă, notată [], este o secvență de 0 substituții elementare și nu face nicio transformare în formula F căreia îi este aplicată, deci (F)[] = F.

Exerciții

Să se aplice substituția s = [x/f(z)][z/a][y/z]

formulelor:

F1 = (∀x)(P(x, a) ∧ Q(y) ∨ (∃z)P(z, x))

F2 = (∃x)(∀z)(P(x, y, z) ∨ Q(x)) ∧ (∀x)(Q(x) ∧∧ R(f(x, z), a))

F3 = P(x) ∨ P(y) ∧ (∀z)(∃x)Q(f(z), x)

F4 = (∀x)P(x, f(x)) ∧ Q(x) ∨ P(a, f(z))

F5 = (∃x)(∃y)(P(f(x, a), f(a, y)))

Structură: S = <US, IS>

US este o mulţime nevidă

IS : X U P U F

US U [US* B] U [US

* US]

Dacă x X, atunci IS (x) US

Dacă P P n, atunci IS (P) : USn B

Dacă F F n, atunci IS (F) : USn US

Semantica LP1 (1)

Semantica LP1 (2)

Fie S = <US, IS>. Extensia sa este:

S’ : X U P U F U T U LP1

US U [US* B] U [US

* US] U B

Pentru fiecare a X U P U F :

S’(a) = S(a)

Pentru fiecare n N*, t1, t2, … , tn T , f Fn,

astfel încât t = f(t1, t2, …, tn)

S’(t) = S(f)(S’(t1), S’(t2), ... , S’(tn)) (US)

Semantica LP1 (3)

Baza. Fie A At .

A = P P0

S’ = S(P) B

A = P(t1, t2, …, tn), n N*, t1, t2 , ……, tn T

S’ (P) = S(P)(S’ (t1), S’ (t2), ... , S’ (tn)) B

Semantica LP1 (4)

Pas constructiv

F = ( F1 ). Atunci S’(F) = S’(F1)

F = (F1 F2). Atunci S’(F) = S’(F1) • S’(F2)

F = (F1 F2). Atunci S’ (F) = S’(F1) + S’(F2)

F = (x)(G). Atunci S’(F) = 1 ddacă pentru

fiecare u US avem S’[x/u](G) = 1

F = (x)(G). Atunci S’(F) = 1 ddacă există măcar

un u US astfel încât S’[x/u](G) = 1

Exerciții

Pentru formula F determinați o structură

S1 = <US, IS> astfel încât S1(F) = 0 și o altă

structură S2 astfel încât S2(F) = 1.

F = P(x) ∨ P(y) ∧ (∀z)(∃x)Q(f(z), x)

Aplicați substituția s = [x/f(z)][z/b] formulei

F, apoi determinați o structură S astfel încât

S((F)s)=0

F = (∀x) (∃y)(P(x, a) ∧ Q(y) ∨ ¬(∃x)P(z, x))

Forme normale în LP1

Forma normală rectificată (FNR)O formulă F LP1 se numeşte rectificată dacă

nu conţine variabile care apar atât libere cât

şi legate şi

nu are cuantificatori care să lege aceeaşi

variabilă, dar pe poziţii diferite în formulă.

Forme normale în LP1

Forma normală prenex (FNP)

O formulă F LP1 este în formă normală

prenex dacă

F = (○1y1) …(○nyn)G, unde n N, ○i {, }, i

[n], iar

y1, … , yn sunt toate variabilele distincte care apar

(liber) în G.

În plus, G nu mai conţine cuantificatori.

Forme normale în LP1

Forma normală Skolem (FNS)

O formulă F LP1 este în formă normală

Skolem (FNS, pe scurt), dacă

are aspectul F = (x1) … (xk)G, unde G nu mai

conţine cuantificatori (este matricea lui F), iar

x1, x2, … , xk sunt variabile distincte şi reprezintă

exact variabilele care apar în G

Forme normale în LP1

Formă normală Skolem clauzală (FNSC)

O formulă F LP1 este în FNSC dacă

este în FNS şi

matricea sa este în FNC (forma normală

conjuctivă) într-un sens similar cu LP (literalii

reprezentând acum formule atomice din LP1 sau

negaţii ale lor).

Exercițiu

Să se aducă la FNSC formula:

F = (∀x) (∃y)(P(x,z) ∧ Q(y) ∨ (∀z)(∃x)P(z, x))

F = (∀x)(P(x, y) ∧ (∃y)P(y, c))

Unificare

Fie L = {L1, L2, ... , Lk} o mulţime finită, nevidă, de literali

din LP1.

L este unificabilă dacă există o substituţie s astfel încât

card((L)s) = 1.

s se numeşte unificator pentru L.

O substituţie s se numeşte cel mai general unificator

(MGU) pentru o mulţime unificabilă L dacă pentru fiecare

unificator s’ există o substituţie sub astfel încât s’ = s • sub.

Rezoluție în LP1

Fie C1, C2 şi R clauze în LP1, C1 ≠ C2.

R se numeşte rezolvent pentru C1 şi C2 dacă:

(i)Există substituţiile s1 şi s2 astfel încât (C1)s1 şi (C2)s2 nu au

variabile comune.

(ii)Există L1, L2, ... , Lm (C1)s1 şi L’1, L’2, ... , L’n (C2)s2

astfel încât mulţimea: L = { L1, L2, ... , Lm, L’1, L’2, ... ,

L’n} este unificabilă.

(iii)Fie sub un cel mai general unificator pentru L.

R = (((C1)s1 \ {L1, L2, ... , Lm}) U ((C2)s2 \ {L’1, L’2, ... ,

L’n}))sub.

Exercițiu

Demonstraţi utilizând rezoluţia că următoarea

formulă din LP1 este nesatisfiabilă:

F = (∀x)(∀y)(P(x,x)∧( P(x,g(y))∨Q(y)) ∧

∧ Q(f(a)))

F = (x)(y)(( P(x) P(f(c)) Q(y)) P(y)

( P(g(b, x)) Q(b)))