Inteligenta Artificiala - Limbaje de ordinul I

Limbaje de ordinul I

Obiective

Durata: 3 ore

1. Limbajul de calcul propozitional

Sintaxa si semantica calculului propozitional

Calculul propozitional a fost definit de Whitehead si Rusell (1910) in celebra carte “Principia Mathematica”. Importanta matematica a calculului propozitional este deosebita, acesta stand la baza definirii oricarui sistem logic formal. Calculul propozitional modern se bazeaza pe dezvoltarile si modernizarile aduse ulterior de Hilbert si Ackermann.

1.1.1. Vocabularul limbajului de calcul propozitional

Vocabularul limbajului este format din urmatoarele categorii de simboluri:

- Variabilele propozitionale notate prin simbolurile a, b, c,…,a₁, b₁, c₁, …. Multimea variabilelor propozitionale (propozitiilor) se noteaza in cele ce urmeaza cu V;

- Conectivele logice (conjunctie), (disjunctie) si (negatie);

- Parantezele rotunde “(” si “)”;

1.1.2. Sintaxa calculului propozitional

Definitia 1

Multimea formulelor (enunturilor sintactic corecte) ale calculului propozitional, multime notata cu P, se defineste recursiv prin urmatoarele reguli:

simbolurile propozitionale apartin lui P:

daca a, bIP atunci a b, a b a, (a)IP

o combinatie de simboluri din V apartine lui P daca si numai dac 616i86g 9; ea se obtine prin aplicarea de un numar finit de ori a regulilor 1) si 2).

Se considera algebra (B₂, ,’) unde B₂= si, pentru orice x, yIB , operatiile si ‘ sunt definite de relatiile:

x y=min=xy;  (1)

x y=max=x+y-xy;

x’=1–x.

Propozitia 1. Algebra (B₂, ,’) este o algebra booleana.

1.1. Semantica limbajului de calcul propozitional

Definirea semanticii calculului propozitional presupune definirea unei functii I:P B , care sa atribuie fiecarei formule o valoare de adevar. Dat fiind faptul ca functia I da o semnificatie formulelor limbajului P, permitand interpretarea acestora, aceasta este denumita interpretare.

Definitia 2. Se numeste interpretare orice morfism al algebrelor (P, ) si (B₂,

Din definitia 2 rezulta ca orice interpretare I, I:P B , satisface urmatoarele proprietati oricare ar fi formulele a, bIP

I(a b)=I(a) I(b)=max;  (2)

I(a b)=I(a) I(b)=min;

I( a)=1-I(a).

Remarca 1. Avand in vedere ca in calculul propozitional orice interpretare satisface prin definitie proprietatile (2), rezulta ca valoarea de adevar a oricarei formule FIP este bine determinata de valorile de adevar atribuite de interpretarea I variabilelor propozitionale. Daca in formula F apar n variabile propozitionale atunci exista 2ⁿ interpretari posibile ale formulei F (functii I).

O interpretare asociaza fiecarei formule FIP o valoare de adevar notata I(F)IB₂, convenind ca valoarea de fals=0, iar valoarea de adevarat=1.

Notand cu x₁, x₂,…,x_n variabilele care apar in F, atunci pentru orice interpretare I, valoarea de adevar a formulei F este data de o relatie de forma:

I(F)=I(F(x₁, x₂,…,x_n))=f(I(x₁), I(x₂),…,I(x_n))  (3)

In aceasta viziune, fiecare formula F poate fi echivalata cu o functie logica f.

Pe multimea P se introduc doua conective (operatii) noi, si , numite implicatie logica, respectiv echivalenta logica, a caror semantica este definita dupa cum urmeaza:

(4)

(5)

Oricare ar fi formulele a, bIP, se obtine urmatoarea semnificatie a conectivelor si

Definitia Se spune ca formula FIP este consistenta daca exista o interpretare I pentru care I(F)=1 (pentru care formula este adevarate). O formula care nu este consistenta se numeste inconsistenta. O multime de formule este consistenta daca exista o interpretare I pentru care I(F₁)= I(F₂)=… =I(F_n)=1 (pentru care toate formulele sunt adevarate).

Remarca 2. Multimea este consistenta daca si numai dac 616i86g 9; formula F₁ F F_n este consistenta.

Definitia 4. O formula FIP se numeste valida sau irefutabila daca este adevarata in orice interpretare, adica I, I(F)=1. O formula valida se mai numeste si tautologie. O formula care nu este valida este denumita invalida.

Ex.: a a.

Remarca O formula invalida poate fi adevarata intr-o interpretare particulara, in timp ce o formula inconsistenta este intotdeauna falsa.

Relatiile dintre conceptele de validitate, consistenta, invaliditate, inconsistenta si valorile de adevar luate de expresii pentru combinatiile de valori de adevar ale formulelor atomice componente sunt ilustrate in tabelul de mai jos.

Se observa existenta unei categorii de expresii, care nu sunt nici intotdeauna valide, nici intotdeauna inconsistente. Astfel de expresii, care pentru unele combinatii ale valorilor de adevar ale formulelor atomice componente iau valoarea 'adevarat', iar pentru alte combinatii ale valorilor de adevar ale formulelor atomice componente iau valoarea 'fals', sunt denumite expresii contingente.

Definitia 5. Fie S= P o multime de formule si CIP o formula. Se spune ca C este deductibila semantic din S sau C este o consecinta logica a lui S, daca pentru orice interpretare I pentru care I(F₁)=I(F₂)=…=I(F_n)=1 avem I(C)=1. Se noteaza acest fapt prin

╞ C (6)

Remarca 4. Se spune ca expresia ╞ C este o teorema, constituind ipoteza, iar C concluzia teoremei respective. Semnul “╞ “ este denumit simbol de asertare a validitatii.

Remarca 5. Daca multimea premizelor este vida, teorema se rescrie sub forma ╞ C, ceea ce semnifica faptul ca C este o tautologie (adevarata in orice ipoteza). Avand in vedere acest aspect, orice tautologie a calculului propozitional poate fi considerata o teorema. De asemenea, a demonstra teorema ╞ C revine in a demonstra ca formula F₁ F F_n C este o tautologie, adica ╞ F₁ F F_n C.

Exista anumite tautologii ale calculului propozitional denumite axiome, prin asertarea carora se pot deduce toate celelalte tautologii ale limbajului. Sistemul axiomatic al calculului propozitional, definit de Hilbert si Ackermann are la baza urmatoarele axiome:

i) ╞ A A A principiul tautologiei;

ii) ╞ A A B principiul aditiunii;

iii) ╞ A B B A principiul comutativitatii;

iv) ╞ (A B ((C A (C B principiul insumarii.

Principiul deductiei

Propozitia 2. (Principiul deductiei)

Se spune ca ╞C daca si numai daca este inconsistenta.

Echivalenta logica

Definitia 6. Doua formule F₁, F₂IP se numesc echivalente daca, pentru orice interpretare I, exista egalitatea I(F₁)=I(F₂): F₁ ≈ F₂ I I(F₁)=I(F₂).

Ex.:

a (a b) ≈ a

a a ≈ a

Propozitia Relatia de echivalenta logica are urmatoarele proprietati:

i)  F G ≈ G F; F G ≈ G F (comutativitate)

ii)                F (G H) ≈ (F G) H; F (G H) ≈ (F G) H (asociativitate)

iii)              F (G H) ≈ (F G) (F H); F (G H)≈ (F G) (F H)

iv)              F F ≈ F, F F ≈ F (idempotenta)

v)                F (F G) ≈ F, F (F G) ≈ F (absorbtie)

vi)              F F ≈ t;  F F≈ f

vii)            F) ≈ F (principiul dublei negatii)

viii)          (F G) ≈ F G

(F G) ≈ F G (De Morgan)

oricare ar fi formulele F, G, H P, t=true, f=false.

2. Metode de demonstrare a teoremelor in limbajul de calcul propozitional

Exista mai multe metode prin care se poate verifica daca o anumita formula este sau nu o teorema (o tautologie) a calculului propozitional. Cele mai cunoscute dintre acestea sunt prezentate in continuare.

Metode semantice

Se considera o formula F=F(x₁,x₂,…,x_n)IP si se doreste demonstrarea (sau infirmarea) faptului ca F este o tautologie. Metodele semantice au la baza definitia 4 si constau in verificarea faptului ca in orice interpretare formula F este adevarata. Pentru aceasta se construieste tabelul valorilor de adevar asociat formulei F. Tabelul va contine cate o coloana pentru fiecare din simbolurile propozitionale x₁, x₂,…,x_n si o coloana pentru formula F, eventual cateva coloane auxiliare care sa faciliteze evaluarea lui I(F). Numarul de linii al tabelului este 2ⁿ, fiecare din acestea corespunzand unei interpretari a formulei F.

Considerand teoremele de forma:

F , F₂, …, F_n ╞ C, (7)

unde F₁, F₂ ,…,F_n (virgula in membrul stang are rol de conjunctie) reprezinta ipoteza teoremei (7), iar C concluzia acesteia, se pot utiliza doua metode semantice pentru demonstrarea teoremei.

Metoda directa. Se verifica ca pentru toate interpretarile pentru care premizele sunt simultan adevarata, concluzia este adevarata, adica I, pentru care I(F₁)= I(F₂)=… =I(F_n)=1, avem I(C)=1. Procedeul utilizat este urmatorul. Se marcheaza in tabelul de adevar liniile in care premizele sunt simultan indeplinite si se verifica pentru aceste linii daca in coloana corespunzatoare concluziei toate valorile de adevar sunt egale cu 1.

Metoda inversa. Se verifica ca pentru orice interpretare I, pentru care I(C)=0, cel putin una din premize este nesatisfacuta, adica exista o formula F_i pentru care avem I(F_i)=0. Se construieste tabelul de adevar si se marcheaza liniile in care concluzia este falsa. Pentru aceste linii se verifica ca cel putin una dintre premize nu este satisfacuta.

Remarca 6. Dezavantajul metodelor semantice consta in faptul ca numarul liniilor din tabelul de adevar creste exponential in raport cu numarul variabilelor propozitionale. Acest inconvenient a fost eliminat in cazul metodele sintactice.

Exemplu: Sa se demonstreze, prin metoda directa si –inversa, teorema
a, a b ╞ b (modus ponens).

Concluzie: Teorema este demonstrata!

Sa se demonstreze: A C D, A, B C, B ╞ D.

Metode sintactice

Spre deosebire de metodele prezentate in § 2.1, metodele sintactice opereaza cu simbolurile propozitionale fara a tine cont de semnificatia semantica a formulelor in care acestea apar. Una dintre cele mai cunoscute metode sintactice este algoritmul lui WANG, care este aplicabil teoremelor de forma:

F F F_n ╞ C₁ C C_m (8)

Presupunand ca in membrul stang al simbolului de asertare a validitatii conectiva implicita este , iar in membrul drept , teorema se poate rescrie sub forma:

F , F₂, …, F_n ╞ C₁, C₂…,C_m  (9)

Algoritmul presupune ca formulele sa fie in prealabil aduse la o forma echivalenta care sa nu contina decat conectivele si . Eliminarea conectivelor si se realizeaza tinand cont de urmatoarele echivalente logice:

F G F G, respectiv F G F G ( F G (F G F G (10)

Exemplu: Sa se aduca la forma echivalenta formulele din urmatoarea teorema:

A C D, A, B C, B ╞ D.

Solutie: A C D (A C D A C D B C B C.

In final, teorema se poate scrie in forma echivalenta:

A C D, A, B C, B ╞ D.

Algoritmul lui WANG

1) Se aduce teorema la forma (9).

2) Se executa procedeul iterativ constand prin aplicarea repetata a uneia din operatiile descrise la punctele (2.1)-(2.3) pana la indeplinirea conditiilor de oprire specificate la pasul

2.1. Eliminarea negatiilor:

Daca intr-unul din cei doi membri ai teoremei apare o formula de forma F, atunci formula respectiva se trece in membrul opus suprimandu-se operatorul de negatie.

F ╞ F.

2.2. Eliminarea conectivelor implicite:

a)      Daca in membrul stang apare o formula de forma F=F₁ F , atunci operatorul este suprimat si se pune virgula in locul acestuia.

F F ╞ F₁, F₂.

b)      Daca in membrul drept apare o formula de forma F=F₁ F , atunci operatorul este suprimat si se pune virgula in locul acestuia.

F F ╞ F₁, F₂.

2.3 Descompunerea teoremei:

a)      Daca in membrul stang apare o formula de forma F=F₁ F , atunci teorema respectiva se descompune in doua subteoreme, fiecare dintre acestea continand in locul termenului F=F₁ F cate unul din termenii disjunctiei respective. A demonstra teorema initiala revine in a demonstra cele doua subteoreme astfel generate.

b)      Daca in membrul stang apare o formula de forma F=F₁ F , atunci teorema respectiva se descompune in doua subteoreme, fiecare dintre acestea continand in locul termenului F=F₁ F cate unul din termenii conjunctiei respective. A demonstra teorema initiala revine in a demonstra cele doua subteoreme astfel generate.

3) Conditii de oprire:

1) Daca intr-o teorema (subteorema) apare aceeasi formula F in ambii membri ai simbolului ╞, atunci teorema este demonstrata.

2) Daca nici una din transformarile (2.1)-(2.3) nu mai este aplicabila si conditia (1) ne este satisfacuta, atunci “teorema” este infirmata (nu este de fapt o teorema).

Exemplu:

Fie teorema (T): A C D, A, B C, B ╞ D.

Se descompune T in urmatoarele subteoreme:

(T₁): A, A, B C, B ╞ D A, B C, B ╞ D, A.

(T₂): C, A, B C, B ╞ D

(T₃): D, A, B C, B ╞ D .

C, A, B, B ╞ D C, A, B ╞ D, B.

C, A, C, B ╞ D  A, B ╞ D, C.

Demonstrarea teoremelor utilizand metoda deductiei formale

Definitia 8. Se numeste regula de inferenta un procedeu prin care, pe baza asertarii unor formule F₁, F₂,…, F_n, se poate deduce (infera) o noua formula adevarata C. Se noteaza acest fapt prin

F , F₂,…, F_n ├ C.

Regula este numita consistenta daca genereaza doar acele formule care sunt o consecinta logica a formulelor .

Precizari:

Pentru a emite judecati si aprecieri asupra formulelor scrise in limbajul calculului propozitional, s-au folosit semnele metalingvistice '╞ ' si '├ ', a caror semnificatie este explicata mai jos.

Expresia '╞ A' semnifica faptul ca formula A este valida, deci in tabela de adevar se afla numai valoarea 1, indiferent de valorile de adevar ale propozitiilor atomice componente.

Expresia 'A╞ B' semnifica faptul ca formula B este o consecinta valida a formulei A, deci B va avea valoarea 1 peste tot unde A are valoarea 1.

Expresia '├ A' semnifica faptul ca formula A este deductibila, adica exista o secventa finita de formule astfel incat fiecare formula este fie o axioma, fie se deduce din doua formule precedente prin aplicarea regulei de inferenta modus ponens (regula asupra careia vom reveni ulterior), iar ultima formula a secventei este A.

Expresia 'A├ B' semnifica faptul ca formula B este deductibila din formula A; deci, exista o secventa finita de formule incheiata cu formula B. Fiecare formula componenta (printre care se gaseste si A) poate fi o axioma sau poate fi dedusa din doua reguli precedente prin aplicarea regulei modus ponens,

Cea mai cunoscuta regula de inferenta este regula

A, A→B├ B,

cunoscuta sub numele de modus ponens.

Similar, regula modus tolens afirma ca

A→B, B ├ A.

Exista reguli de introducere sau eliminare a conectivelor logice. Astfel regula

A, B ├ A B

este cunoscuta sub numele de -introducere, in timp ce regula:

A B ├ A si A B ├ B

este denumita -eliminare

Similar, regula:

A B ├ B A

este denumita “ ” eliminare

Definitia 9. Fie S= si C o formula. Se spune ca C este deductibila din S daca exista un sir de formule C₁, C₂,…, C_m=C, a carei ultima formula este C, iar celelalte formule sunt axiome, formule din S sau sunt deduse din doua formule anterioare utilizand regula de inferenta modus ponens.

Exemplul 1. Sa se demonstreze teorema:

├ D.

Demonstratie

A,C ├ A C. ( -introducere)

A C, A C B├ B (modus ponens)

B, B D├ D. (modus ponens)

Principiul rezolutiei

Definirea metodei de demonstrare utilizand principiul rezolutiei necesita definire in prealabil a unor notiuni suplimentare.

Def 1: Se numeste literal un simbol propozitional (literal pozitiv) sau negatia acestuia (literal negativ).

Def 2: Prin atom se intelege o variabila propozitionala.

Def 3: Se numeste clauza este o disjunctie de literali:

C=L₁ L L_n, L_i I C,

unde L_i este un literal pozitiv sau un literal negativ.

Def 4: Se spune ca o formula F este scrisa in forma normala conjunctiva (FNC) sau in forma clauzala, daca aceasta este o conjunctie de clauze:

F=C₁ C C_m, unde C_i , i=1,..,m, este o clauza.

Multimea clauzelor (formelor clauzale) ale calculului propozitional se va nota cu C.

Def 5: Clauza fara nici un literal este denumita clauza vida si se noteaza cu “ ” sau “nil”. Prin definitie I(

Def 6: Se numeste forma normala disjunctiva (FND) o disjunctie de formule de forma: L₁ L L_n

Aplicand principiul rezolutiei, teorema ╞ C, echivalenta cu F₁ F F_n ╞ C, este demonstrata daca multimea este inconsistenta (principiul deductiei). Pentru ca metoda de derivare prin rezolutie sa poata fi aplicata, trebuie ca formulele din multimea de mai sus (sau formula F₁ F F_n C) sa fie adusa la forma normal conjunctiva (FNC).

Propozitia 9. Orice formula FIP poate fi rescrisa sub o forma clauzala echivalenta.

Demonstratie. Aplicand urmatorul procedeu, orice formula FIP este scrisa sub forma F_CIC si in orice interpretare I(F)=I(F_C), adica (F F_C

Se elimina conectiva , utilizand echivalenta logica (10):

A B (A B A B

Se elimina conectiva , utilizand echivalenta logica (10):

A B A B.

Se aplica relatiile lui De Morgen astfel incat fiecare operator de negatie sa fie aplicat unui singur simbol propozitional:

(A B) A B

(A B) B B

A A, ( ) A, B IP

Se utilizeaza proprietatile de distributivitate ale operatorilor si pentru aducerea formulei la forma clauzala:

A (B C) (A B) (A C) (FNC)

A (B C) (A B) (A C).

Se utilizeaza proprietatile de idempotenta, absorbtie etc. pentru simplificarea FNC obtinute.

Procedeul de demonstrare a teoremelor utilizand metoda deductiei este destul de simplu din punct de vedere teoretic, dar este foarte dificil de implementat pe calculator. Dificultatea consta in alegerea regulii de inferenta aplicabila la un anumit moment, astfel incat in final sa se ajunga la obtinerea scopului dorit. Avand in vedere acest inconvenient, rezolvatoarele automate au la baza o metoda de demonstrare a teoremelor bazata pe principiul rezolutiei datorat lui J. A. Robinson. Avantajul metodei rezolutiei, in raport cu metodele de deductie, consta in faptul ca la demonstrarea teoremelor se utilizeaza o singura regula de inferenta si anume regula rezolutiei definita prin:

a F, a G ├ F G (11)

unde a este o variabila propozitionala, iar F, G sunt clauze ale limbajului P. Formula F G poarta denumirea de rezolvanta clauzelor a F si a G. Doua clauze de tipul celor din membrul stang al relatiei de asertare a deductibilitatii (11) se numesc rezolubile.

Regula rezolutiei poate fi demonstrata imediat: se constata cu usurinta ca pentru orice interpretare I pentru care I(a F)= I( a G)=1 avem fie I(F)=1 fie I(G)=1, deci I(F G)=1.

Propozitia 10. Fie S o multime de clauze S = si R = rez(F_i, F_j) rezolvanta a doua clauze din multimea S. Forma normala conjunctiva S(F₁ F₂ F_n) este echivalenta cu FCN desemnata prin S R(F₁ F₂ F_n R).

Exemplu: Sa se demonstreze regula modus ponens (caz particular al principiului rezolutiei): a, a b ├ b.

a

a b

───────────

b

Def 7: Fie S = o multime de clauze si R o clauza. Se numeste deductie prin rezolutie sau derivare rezolutiva o secventa de clauze R₁, R₂, …, R_n=R cu proprietatea ca pentru orice i = 1..n, R_i este rezolvanta a doua clauze, R_i = rez(F_i1, F_i2), unde F_ikIS sau F_ik= R_i, j<i.

Propozitia 11. O multime de cauze S = este inconsistenta daca si numai daca clauza vida poate fi obtinuta prin rezolutie liniara din multimea S.

Pentru demonstrarea teoremelor utilizand metoda rezolutiei se porneste de la rezultatul prezentat in propozitia 2 (principiul deductiei) si de la rezultatul exprimat prin urmatoarea propozitie.

Teorema 1. (Teorema de consistenta si completitudine) O multime de clauze este inconsistenta daca si numai daca din multimea respectiva se poate deriva prin rezolutie clauza vida.

nil.

Recapituland, pentru a demonstra teorema exprimata prin rel. 6, ╞ C, revine, conform principiului deductiei, la a demonstra ca multimea de clauze S, obtinuta prin scrierea sub forma clauzala a multimii de formule este inconsistenta. In baza teoremei 1, totul se reduce la derivarea clauzei vide din multimea S.

Se spune ca o clauza este factorizata, daca un acelasi literal nu apare de doua ori in contextul clauzei respective. In baza proprietatii de idempotenta a operatiei de disjunctie, orice clauza se poate simplifica prin scrierea o singura data a tuturor literalilor care apar de mai multe ori in cadrul acesteia (operatie denumita factorizare). In caz contrar, algoritmul poate sa cicleze in anumite cazuri particulare.

Algoritmul de demonstrare utilizand regula rezolutiei este prezentat in pseudocod mai jos:

for all F in S do F:=factor(F);

while in S doua clauze rezolubile F₁ si F₂) and ( S) do

begin

R:= rez(F₁,F₂); C:= factor(R); S:=S

end

unde prin rez(F₁,F₂) s-a notat rezolvanta clauzelor F₁ si F₂, iar factor(R) este clauza obtinuta prin factorizarea clauzei R. Conform celor expuse mai sus, teorema este demonstrata daca dupa, terminarea procesului iterativ ilustrat in algoritmul precedent, clauza vida IS

Exemplul 2 Sa se demonstreze, utilizand metoda rezolutiei, teorema A C D, A, B C, B ╞ D..

Rescriind formulele din multimea sub forma clauzala se obtine urmatoarea multime de clauze:

(C₁) A C B

(C₂) B D

(C₃)  A

(C₄)  C

(C₅)  D

de unde procesul rezolutiv se poate desfasura in felul urmator:

(C₆) rez(C₁,C₃)= C B

(C₇)  rez(C₆,C₂)= C D

(C₈)  rez(C₇,C₄)= D.

(C₉)  rez(C₈,C₅)=

si astfel teorema este demonstrata. In Prolog, demonstratia poate fi efectuata astfel:

a.  c. ?-d.

b :- a, c.  d :- b. yes

REZUMAT

Limbajul de calcul propozitional are urmatoarele caracteristici principale:

Are rolul de a stabili validitatea (adevarat sau fals) unor afirmatii intr-un context dat.

Formularile in limbaj natural devin, in limbajul de calcul propozitional, expresii simbolice in care intervin simboluri (propozitii elementare) si conective logice: si ( ), sau ( ), not ( ), implicatie ( ), echivalenta (

Exista 3 categorii de metode pentru demonstrarea unei teoreme: a) metode semantice (directa si inversa), b) metode sintactice (algoritmul lui WANG), c) metoda deductiei formale (regulile de inferenta, principiul rezolutiei)

Principiul rezolutiei utilizeaza o singura regula de inferenta si anume regula rezolutiei, ceea ce permite implementarea ei in rezolvatoarele automate.

EXERCITII SI PROBLEME PROPUSE

Exercitiul 1. Sa se arate ca:

a b ≈ a b

(a b) a b

(a b) a b

a b ≈ a b) (b a) ≈ (b a) a b)

Aplicatie: a – daca e soare; b – e frumos.

Exercitiul 2. Sa se demonstreze utilizand pe rand metodele 2.1, 2.2 si 2.4 urmatoarele teoreme de baza ale calculului propozitional:

i)            ╞ A (B A

ii)          ╞ (A B ((A (B C (A C

iii)        ╞ (A (A B B

iv)        ╞ A (B A B

v)          ╞ (A B A

vi)        ╞ (A B B

vii)      ╞ A A B

viii)            ╞ B A B

ix)        ╞ (A C ((B C (A B C

x)          ╞ (A B ((A B A

xi)        A A

xii)      ╞ (A B ((B A (A B

xiii)            ╞ (A B (A B

xiv)            ╞ (A B) (B A

xv)      (A B A B

xvi)            (A B A B

Exercitiul Convertiti urmatoarele formule in forma clauzala:

(a (b c d Raspuns: a d b c d

(a b) (c d) Raspuns: a b c a b d c d a c d b

a b) (c d) Raspuns: a c a d, b c, b d.

Exercitiul 4. Sa se demonstreze, aplicand principiul rezolutiei, urmatoarele teoreme:

a c, a b c a b

a, a c, a b c a b c

b, e c e d, a d a b ╞ c

Problema 1:

Tom nu merge la biserica si Hary nu merge la biserica este falsa. Daca Alice nu merge la biserica, atunci Hary nu merge la biserica. Daca Tom merge la biserica, atunci Hary merge la biserica.

Demonstrati ca Alice merge la biserica.

a – Alice merge la biserica; b – Tom merge la biserica; c – Hary merge la biserica.

b c), a c, b c ╞ a.

Problema 2:

Celebrul explorator, antropolog, etnograf, muzicolog, botanist, optician si inventator Max de Wax a studiat un timp obiceiurile barbatilor de pe o mica si uitata insula din oceanul Pacific. Iata sinteza insemnarilor sale:

Toti ce care cunosc vechea limba a acestei populatii poarta ochelari.

Nici un filatelist nu are nepoti.

Toti cei ce frecventeaza unicul club de pe insula sunt stangaci.

Nici unul dintre insularii care nu stie sa inoate nu cultiva trandafiri.

Toti cei ce nu au nepoti canta la cimpoi.

Toti cei ce poarta haine cadrilate frecventeaza clubul.

Numai filatelistii nu vorbesc vechea limba a acestei populatii.

Nici un stangaci nu canta la cimpoi.

Toti cei care stiu sa inoate poarta haine cadrilate.

Intorcandu-se acasa, Max si-a amintit ca a omis un lucru foarte important: nu a stabilit ce legatura exista intre purtatul ochelarilor si cultivarea trandafirilor. A vrut sa se intoarca pe insula, dar, cercetandu-si cu atentie notitele, si-a dat seama ca cei care cultiva trandafiri poarta ochelari.

Demonstrati concluzia lui Max de Wax, utilizand principiul rezolutiei.

P₁– cunosc vechea limba  P₆– este stangaci

P₂– poara ochelari P₇– stie sa inoate

P₃– este filatelist P₈– cultiva trandafiri

P₄– are nepoti P₉– canta la cimpoi

P₅– frecventeaza clubul P₁₀– poarta haine cadrilate

1. P₁ P₂ 6. P₁₀ P₅

P₃ P₄ 7. P₁ P₃

P₅ P₆ 8. P₆ P₉

P₇ P₈ 9. P₇ P₁₀

P₄ P₉  Concluzie: P₈ P₂

TEST DE AUTOEVALUARE

Regula de inferenta, denumita modus ponens, se exprima prin:

a.       A B├ A B

b.      A, A B├ B

c.       A B, B├ A

Se numeste clauza:

a.       O regula de inferenta.

b.      O disjunctie de literari.

c.       Un atom.

Regula rezolutiei este definita prin:

a.       A C, A B ├ C B

b.      A C, A B ├ C B

c.       A B, A C ├ B C

O multime de clauze S= este inconsistenta daca:

a.       S nu este rezolutiva.

b.      Daca si numai dac 616i86g 9; clauza vida poate fi obtinuta din multimea S.

c.       Daca S se poate factoriza.

Regula modus tolens afirma ca:

a.       A B, A |- A

b.      A B A B A B

c.       A B B |- A

Sa se precizeze care dintre urmatoarele echivalente logice este adevarata:

a.       a b ≈ a b.

b.      a b ≈ a b.

c.       a b ≈ a b.

O formula F este scrisa in forma normala conjunctiva daca aceasta este:

a.       Clauza vida.

b.      Conjunctie de clauze.

c.       Regula modus tolens.

Proprietatea de distributivitate a operatorului este:

a.       A B C A B A C

b.      A B C A B A C

c.       A B C A B A C

Pentru demonstrarea teoremelor in limbaj de calcul propozitional se poate utiliza o singura regula de inferenta si anume:

a.       Regula silogismului.

b.      Regula rezolutiei .

c.       Regula modus ponens.

Daca un acelasi literal nu apare de doua ori in contextul clauzei respective se spune ca aceasta este:

a.       Rezolutibila.

b.      O instanta.

c.       Factorizata.

Raspuns

1. b 6. a

2. b 7. b

c 8. a

4. b 9. b

5. c 10.c

vvv