1. Fundamentele Logice Ale Informaticii

8/10/2019 1. Fundamentele Logice Ale Informaticii

1/156

vii

Cuprins

Prefa i Introducere 1

Capitolul 1 Funcii booleene 8

1. Algebre booleene. . . . . . . . . . . . . . . . . . . 14

2. Teoreme de reprezentareiforme normale pentru

funciile booleene . . . . . . . . . . . . . . . . . . 22

3. Clase speciale de funcii booleene . . . . . 32

4. Recapitularei Index . . . . . . . . . . . . . . . 39

5. Exerciii. . . . . . . . . . . . . . . . . . . . . . . . . . 41

Capitolul 2 Logica propoziional

(calculul propoziional) 43

1. Logica, parte a filozofiei . . . . . . . . . . . . 45

2. Sintaxa logicii propoziionale. . . . . . . . . 553. Semantica logicii propoziionale . . . . . . 61

4. Forme normale nLP . . . . . . . . . . . . . . 72

5. Decidabilitate nLP . . . . . . . . . . . . . . . 77

6. Formule Horn . . . . . . . . . . . . . . . . . . . . 81

7. Rezoluie nLP . . . . . . . . . . . . . . . . . . . 89

viii Cuprins

8. Rafinri ale rezoluiei:

strategiii restricii . . . . . . . . . . . . . . . . 105

9. Recapitularei Index. . . . . . . . . . . . . . . 111

10. Exerciii . . . . . . . . . . . . . . . . . . . . . . . . . 120

Capitolul 3 Logica (calculul) cu predicate de ordinul I 123

1. Sintaxa logicii cu predicate

de ordinul I . . . . . . . . . . . . . . . . . . . . . . 123

2. Semantica logicii cu predicate

de ordinul I . . . . . . . . . . . . . . . . . . . . . . 141

3. Forme normale nLP1 . . . . . . . . . . . . . 151

4. Decidabilitate nLP1(LP1=) . . . . . . . . 170

5. Rezoluie nLP1 . . . . . . . . . . . . . . . . . . 184

6. Recapitularei Index. . . . . . . . . . . . . . . 187

7. Exerciii . . . . . . . . . . . . . . . . . . . . . . . . . 190

Capitolul 4 Teorii logicei sisteme deductive 193

1. Sisteme deductive . . . . . . . . . . . . . . . . . 196

2. Teorii logice . . . . . . . . . . . . . . . . . . . . . 207

3. Clasificarea sistemelor deductive. . . . . . 217


5. Exerciii . . . . . . . . . . . . . . . . . . . . . . . . . 235


2/156

Cuprins ix

Capitolul 5 Programare logic 238

1. Exemple de programe logicepure . . . . 240

2. Sintaxa programelor logice . . . . . . . . . . 249


4. Exerciii . . . . . . . . . . . . . . . . . . . . . . . . . 260

Anex Rezolvarea exerciiiloriexerciii propuse 267

1. RezolvriCapitolul 1 . . . . . . . . . . . . . . 267



4. RezolvriCapitolul 4 . . . . . . . . . . . . . . 2885. RezolvriCapitolul 5 . . . . . . . . . . . . . . 292

6. Exerciii propuse . . . . . . . . . . . . . . . . . . 302

Bibliografie 312

Capitolul 1

Funcii booleene

Scopul acestui capitol l constituie familiarizarea cititorului cu o

clasparticularde funcii clasa funciilor booleene. Aceste funcii,

dei au o mulime de definiie (undomeniu)i o mulime de valori (un

codomeniu) aparent simple, au proprieti locale i globale foarte utile.

Teoria dezvoltat pentru ele constituie de fapt baza conceptual i

concretasemanticiilogicii propoziionale n sens clasic (i nu numai).

Schimbnd semnificaia simbolurilor 0 i 1 din cifr n valoare de

adevr (fals, respectiv adevrat), a operaiilor + i , etc., din

adunare(de exemplu,adunarea n mulimea numerelor naturalesau

adunarea modulo 2) i opus, n disjuncie, respectiv negaie (caoperaii cu valori de adevr), etc., multe rezultate din logic pot fi

ulterior deduse printr-o simpl traducere. Anumite noiuni i

proprieti specifice funciilor booleene nu sunt direct i neaprat

necesare n studiul logicii formale, astfel nct subiectul nu este tratat n

detaliu.

Vom introduce - ct mai succint i la un nivel informal - i alte

noiuni, notaii sau rezultate necesare pentru mbuntirea nelegerii

majoritatea denaturalgebric([DID]) sau deinformaticelementar

([SOR]). n primul rnd, chiar din manualele de matematicde liceu

sunt bine cunoscute cel puin doumodaliti de aprezentao mulime:

Prin enumerarea elementelor sale. N = {0, 1, 2, ...} estemulimea numerelor naturale.


3/156


4/156


5/156

Fundamentele logice ale Informaticii 13

scriem acest lucru prin b = f(a1, a2, ... , an), dei relaia dintre

elementele vechi i cele noi nu este ntotdeauna de naturfuncional)

i presupunem ceste adevrat P (ai) pentru fiecare ai {1, 2, ..., n}.

Artm ceste adevratP (b).

Observaie. Principiul induciei matematice (naturale)aa cum este

el cunoscut din matematica de liceu, este un caz particular al

principiului induciei structurale (dup cum se observ imediat).Folosim cuvntulprincipiun loc deteorem(care trebuie saib i o

demonstraie aferent) deoarece n cele de mai sus doarstipulm c

formulele (n)P(n) i respectivP(0) (n)(P(n) implic P(n+1))

sunt tare echivalente(n sensul care va fi precizat n Capitolul 2). n

cele de mai sus,P(0) poate fi nlocuit i cu orice P(k),k numr

natural fixat, deoarece i submulimea luiN,{k, k + 1, ... }estebine-

ordonat; n acest caz, locul lui (n) este luat de (n k)).

Echivalena amintit, dei adevrat n anumite situaii (structuri)

particulare, nu este adevrat n sensul general al logicii formale.

Forme particulare ale principiului induciei structurale sunt imetoda

aseriunilor invariante ([DIJ]), folosit pentru demonstrarea

corectitudinii algoritmilor imperativi, sau metoda induciei asupra

unei demonstraii([WIN]), folositpentru demonstrarea unor teoreme

de tip corectitudinei completitudine.

14 Cristian Masalagiu

Noiunile de axiom, teorem, regulde inferen, demonstraie,

raionament, sunt utilizate n acest capitol la modul informal/descriptiv,

ele urmnd a fi precizate n capitolele urmtoare.

1. Algebre booleene

Se presupun cunoscute noiunile i notaiile de baz din

matematica de liceu. n plus, submulimea lui N,

{1, 2, ... ,n} se va nota i cu [n], iar pentru indicarea unui element alunui produs cartezian (numit i tuplu sau n-uplu n cazul n care

numrul n de componente este cunoscut) se vor folosi parantezele

ascuite, nu cele rotunde (exceptnd cazul n care este vorba de

aplicarea unei funcii unui tuplu).

Notm cu Bmulimea {0, 1}i cu FB(n) = {f | f : Bn B}, Bn

reprezentndprodusul cartezianal lui Bcu el nsui, luat de nNori

(Bn = B B ... B). FB(0) va coincide cu B, prin convenie. Vom

pune deci:

n 0

(0)

FB FB

FB

n

B

Observaie. card(FBn) = 22 n

. Cardinalul unei mulimi A va mai fi

notat, atunci cnd nu exist confuzii i cu |A|. Mai mult, dac att

domeniul ct i codomeniul unei funcii sunt mulimi finite, funcia

poate fi dattabelar. O asemenea tabelde definiie va fi numitnc

de pe acumtabelde adevr, dei semnificaia acestui termen poate


6/156


crea anumite confuzii de moment. n cazul unei funcii f FB(n)

(operaie n-ar), tabela de definiie va fi de forma:

x1 x2 ... xn f(x1, x2, ... , xn)

0 0 0 f(0, 0, ... , 0)

0 0 ... 1 f(0, 0, ... , 1)

... ... ... ... ...

1 1 1 1 f(1, 1, ... , 1)

Se mai observcam folosit oordine standardpe Bn , de unde

se poate deriva o ordine standard pentru valorile din codomeniul

funciei. Acest lucru face posibilo reprezentare a funciilor booleene

ca numere n baza 2 i (desigur) ca numere n baza 10.

ntrebare. Putei justifica egalitateacard (FBn) =n22 ?

Indicm cteva funcii importante din FB. Dup cum am

precizat deja, n FB(0) avem doarconstantelecorespunztoare, elemente

ale lui B(prin convenie, acestea suntfuncii de 0 variabile).

Pentru n = 1, cele 4 funcii de o variabil(operaii 1-are sauunare)

suntc0(funciaindentic 0),c1(funciaidentic 1),1B(identitatea) i

(negaia, opusul), date prin:


x c0 c1 1B

0 0 1 0 1

1 0 1 1 0

Pentru n = 2, din totalul celor 16 funcii de douvariabile posibile

(operaii 2-are; binare), cteva dintre cele mai importante sunt: +

(suma,sau adunarea boolean sau disjuncia), (produsulbooleansau conjuncia), (suma modulo 2 sau disjuncia exclusiv) i |

(anticonjunciasauoperaia lui Sheffer):

x y x + y x y x y x | y

0 0 0 0 0 10 1 1 0 1 1

1 0 1 0 1 1

1 1 1 1 0 0

ntrebare.Cte funcii sunt n FB(3) ? Putei da vreun exemplu deasemenea funcie, care saib i o semnificaie cunoscut ?

ntrebare. Putei descoperi singuri metoda standard de

construcie a liniilor unui tabel ca cel de mai sus (ordinea standard pe

Bn)?

Observaie. Funciile binare , + i funcia unar , pot fi privite ca

legi de compoziie internepe mulimea B. Astfel, ntr-un mod cu totul


7/156


similar cu cazurile cunoscute alegrupului,ineluluisaucorpului, tuplul

B = < B, , +, > formeazo algebrboolean, sau algebrBoole

(dupnumelematematicianului G. Boole, 1815 1864).

Definiia 1.1. Se numete algebr boolean un 4-uplu M ,

M = , format din orice mulime nevid M (suportul

algebrei) douoperaii binare,:MM M i o operaie unar

~ :MM, care satisfac condiiile (legile):

1) xy = y x comutativitate(a lui )

2) (x y)z = x (y z) asociativitate(a lui )

3) x(y z) = (x y)(x z) distributivitate (a lui

fade)

4) (x y)y = y absorbie

5) (x (~x))y = y legea contradiciei

i respectiv

1) xy = y x. comutativitate(a lui)

2) (xy)z = x (y z) asociativitate(a lui)

3) x(y z) = (xy)(x z) distributivitate (a lui fade )

4) (xy)y = y absorbie

5) (x(~x))y = y legea tautologiei


Legile (numite impropriu iaxiome) de mai sus nu reprezint

identiti, ele trebuind sfie nelese ca niteecuaii satisfcute pentru

toate valorile variabilelor x, y, z, care sunt nume generice pentru

elemente oarecare dinM. Fiecare dintre cei doi membri reprezintde

fapt (expresiile unor) funcii booleene (numrul de argumente fiind dat

de numrul de nume de variabile distincte care apar n intreaga ecuaie).

Egalitatea nseamnprin urmare egalitatea de funcii. Mai mult, vom

admite fr demonstraie, c ecuaiile reprezint scheme de axiome,adiclegile anterioare precumi cele derivate care vor urma - sunt

adevrate i dac nlocuim (textual) orice apariie a unei funcii

(subexpresii) prin altfunctie (subexpresie). O asemeneaTeoremde

substituieva fi demonstratn capitolul urmtor, n contextul logicii

formale.

n general, considernd afirmaii(notate generic cu A )peste o

mulime M (suport al unei algebre booleene), care depind doar de

variabile cu valori n M i folosesc doar operaiile amintite, afirmaii

care sunt reprezentate fie prin axiome (Bazadefiniiei structurale), fie

obinute din axiome printr-un anumit raionament utiliznd reguli de

inferen (Pasul constructiv: cu ajutorul regulilor se obin afirmaiinoi, numite iteoreme, din afirmaii vechi), putem definidualelelor,

A

, n felul urmtor: A se obine din A prin nlocuirea simultan

(textual) a tuturor apariiilor luicu i a tuturor apariiilor lui

cu.

Putem extinde conceptuli notaia anterioarlaobiecteoarecare

(afirmaii, dari elemente dinM, funcii pesteM, texte, etc.). Astfel, n


8/156


B, 1 este dualul lui 0 (evident i reciproc,relaia de dualitate fiind o

relaie simetric), duala sumei este produsul, duala unei funcii

oarecare se obine prin dualizareantregiitabele de adevr, etc. ntr-o

algebr boolean oarecare M , se poate arta (demonstraia formal

nefiind esenial pentru scopul acestei lucrri) c exist un (unic)

element nM (notat 0) care satisface n plus ecuaia x ( x~ ) = 0,

precum i un (unic) element1 M, care este dualul lui0, satisfcnd

x ( x~ ) =1 (0fiind desigur distinct de1). Mai mult, relaia de dualitate

esteiidempotent(avem (o) =o, pentru fiecare obiecto), existndi

obiecte autoduale, adic obiecte care satisfac o = o (de exemplu,

funciile 1B, i f FB(3), dat prin f(x, y, z) = x y z, sunt

autoduale). Fiecare axiomi) dinDefiniia 1.1, i[5] are astfel duala

sa, notatacolo prin i). Mai mult, nlocuind ntr-un raionament princare se obine o teorem AA, orice axiom cu duala ei, vom gsi un

raionament (dual), prin care se obine (deduce, demonstreaz)

afirmaia A . Este justificat atunci s adoptm principiul dualitii

pentru B (care, la o privire atent, este i el un caz particular al

principiului induciei structurale). De fapt, pentru fiecaretext (secven

finit de caractere grafice) se poate afla dualul su, dup schema

sugeratanterior. Admitem deci frdemonstraie formalc:

O afirmaie boolean A este adevrat dac i numai dac

duala saA

este adevrat.


ntrebare. Putei arta c funcia f(x, y, z) = x y z este

autodual?

Teorema 1.1. Tuplul B = < B, , +, > este o algebrboolean i

pentru fiecare x Bavem x( x ) = 0i x + ( x ) = 1.

Demonstraie. Conform principiului dualitii, este suficient sartm

csunt adevrate doar axiomele 1) 5) i x( x ) = 0 (n cazul nostru,

este nlocuit de iarde ctre +). Vom privi att membrul stng cti

membrul drept al ecuaiilor ca expresiile unor funcii i vom folosi

tabelele de adevr pentru reprezentarea acestora. Datorit simplitii

calculelor, dintre axiome vom arta doar validitatea lui 4). Avem:

x y x y (x y) + y y0 0 0 0 0

0 1 0 1 1

1 0 0 0 0

1 1 1 1 1

i respectiv:

x x x ( x )

0 1 0

1 0 0

Adevrul axiomei 4) rezult din primul tabel prin comparareapenultimei coloane (care este membrul stng al ecuaiei) cu ultima


9/156


coloan(membrul drept), linie cu linie. Se observ imediat cacestea

coincid, adicfunciile date de expresiile respective sunt egale(dou

funcii sunt egale dacau acelai domeniu i codomeniu i valorile lor

coincid pe fiecare valoare a argumentului).Similar pentru x( x ) = 0 i

cel de-al doilea tabel, cu observaia c nu am mai explicitat coloana

care reprezintmembrul drept (i care este de fapt expresia funcieic0).

O algebr boolean cunoscut este dat de mulimea prilor

(submulimilor) unei mulimi oarecare V, notat 2V, mpreun cu

intersecia, reuniunea i complementara fa de V,

V = < 2V,,U, CV>.

Observaie. Conceptul de algebrbooleaneste prezent n matematic

prin mai multe definiii, nu toate echivalente n orice context ([BIR]).

Smenionm faptul co definiie echivalentcuDefiniia 1.1este:

O algebr boolean este o latice M = care satisface

condiiile suplimentare: Exist(mcar) unprim element,0M, astfel nct x0= x.

Exist(mcar) unultim element,1M, astfel nct x 1= x.

Operaia estedistributivfade operaia.

Pentru fiecare x M, exist un element x M (numit i

complementullui x), astfel nct x x =1i xx =0.


Olatice(i aici sunt mai multe accepiuni matematice ale termenuluii

cteva definiii echivalente pentru o aceeai accepiune) este un triplet

M = , n care ambele operaii satisfac proprietile de

idempoten, comutativitate, asociativitate i absorbie. n plus, n

orice latice (deci i n orice algebrboolean), se poate defini orelaie

de ordine parial(relaie binar, reflexiv, tranzitiv i antisimetric),

prin: xy dac i numai dacx = xy (sau, dual, y = xy). Datorit

acestui fapt, o latice se mai definete i ca fiind o mulime parialordonat(poset)n care toate submulimile finite, nevide, admit mcar

o cea mai mic margine superioar (l.u.b., ) i o cea mai mare

margine inferioar(g.l. b., ).

2. Teoreme de reprezentare i forme normale pentru

funciile booleene

ntr-o algebrboolean(n particular, nB ) sunt valabilei alte

teoreme. Ele pot fi demonstrate fie utiliznd tabelele de adevr, fie

construind un raionament, adicpornind de la axiome (i/sau de la alteteoreme, demonstrate anterior)i utiliznd anumite reguli de inferen.

Sumarizm cteva dintre ele n tabelul urmtor (teoremele sunt notate

cu 6) 13) iar dualele lor respectiv cu 6) 13); am neglijat uneori, de

exemplu n 13)i 13), scrierea lui ).


10/156


6) x = x 6) x = x

7) x x = 0 7) x + x = 1

8) xx = x 8) x + x = x

9) x0 = 0 9) x + 1 = 1

10) x1 = x 10) x + 0 = x

11) x1x2xn = 0 dac i

numai dac exist i[n] astfelnct xi = 0 (oricare ar fi n 2

i oricare ar fi

x1, x2, ..., xn B)

11) x1+ x2+ + xn = 1 dac

i numai dac exist i[n]astfel nct xi= 1 (oricare ar fi

n 2 i oricare ar fi

x1, x2, ..., xn B)

12) x1x2xn = 1 dac i

numai dacpentru fiecare i[n]avem xi = 1 (oricare ar fi n2

i oricare ar fi

x1, x2, ..., xn B)

12) x1+ x2+ + xn = 0 dac

i numai dac pentru fiecarei[n] avem xi = 0 (oricare ar fi

n 2 i oricare ar fi

x1, x2, ..., xn B)

13)

1 2 n 1 2 nx x ... x = x +x + . ..+x

(oricare ar fi n2 i oricare ar

fi x1, x2, ..., xn B)

13)

1 2 n 1 2 nx + x + ...+ x = x x ... x

(oricare ar fi n2 i oricare ar

fi x1, x2, ..., xn B)

Tabelul 1.1.

Din tabel se observ cafirmaia 6) este autodual i acesta putea fi

completat cu generalizarea la n 3 elemente a asociativitii,


comutativitii, distributivitii, precum i cu alte teoreme, etc.

Afirmaiile 13)i 13) se mai numesclegile lui deMorgan.

Exerciiul 1.1. S se demonstreze adevrul afirmaiilor care urmeaz

folosind att tabelele de adevr ct i raionamente, implicnd axiome

(sau alte afirmaii, demonstrate n prealabil) i reguli de inferen

(deducie, demonstraie), cunoscute din matematica de liceu (de

exemplu, cele legate de faptul c egalitatea este o relaie deechivalen,adicestereflexiv, simetric i tranzitiv):

a) 11) din tabelul anterior.

b) x(x + y ) = x.

c) x + xy = x.

d) x +x y = x + y.

e) x+ xy = x+ y.

f) x(x+ y) = xy.

g) x (x + y) = x y.

Rezolvare. Vom lsa aplicarea metodei care utilizeaz tabelele de

adevr pe seama cititorului. De asemenea, vom presupune deja

demonstrate celelalte afirmaii dinTabelul 1.1.a) Procedm prin inducie matematic, afirmaia de demonstrat fiind

(nN)(n2implicP(n)), unde:

P(n): (x1, x2, ..., xn B)( x1x2xn = 0dac i numai dac

(i [n])(xi= 0)).

Baza.n = 2. Se folosesc 9)i 10) dinTabelul 1.1.


11/156


Pas inductiv. Spresupunem cpentru (orice) k2i oricare elemente

x1, x2, ..., xk Bavem:

x1x2xk= 0 atuncii numai atunci cndexisti[k] astfel nct

xi = 0.

Spresupunem faptul ceste adevratP(k) i sartm cP(k + 1)

este adevrat. Fie orice element din B, notat xk+1 i s notm

y = x1x2xk. Atunci avem de demonstrat ceste adevratafirmaia

yxk+1= 0dac i numai dacexisti[k + 1] astfel nct xi = 0,ceea ce este echivalent cu a arta c:

yxk+1= 0dac i numai dacexist i[k] astfel nct xi = 0 sau

xk+1= 0.

Aplicnd acum ipoteza inductiv, rezultcmai trebuie sartm c:

yxk+1= 0dac i numai dacy = 0 sau xk+1= 0.

Ultima afirmaie este ns adevrat din cele deja demonstrate (P(2)

este adevrat).

b) x(x + y) = x. Pornim cu membrul stng i folosind axioma 3)

(distributivitate) gsim x(x + y) = xx + xy. Folosim acum 8) din

Tabelul 1.1, distributivitatea i faptul c egalitatea este o relaie

tranzitiv, pentru a obine x(x + y) = x(1 + y). Din comutativitate i

9) (Tabelul 1.1), se deduce cx(x + y) = x1. Ceea ce trebuia artat

urmeazacum imediat, prin aplicarea lui 10) (Tabelul 1.1).

c) x + xy = x. Rezultdin ultima parte a demonstraiei anterioare.

d) x +x y = x + y. Pornim cu membrul stng al egalitii i l nlocuim

pe x cu x + xy, ceea ce putem face folosind punctul anteriori faptul

cegalitatea este o relaie simetric. Gsim x + x y = x + xy + x y.


Folosind comutativitateai distributivitatea, rezultctrebuie sartm

x + y(x + x ) = x + y. Aplicm acum 7) i apoi 10) (Tabelul 1.1),

pentru a obine ceea ce se cere.

e) x + xy = x + y. n relaia precedentse nlocuiesc toate apariiile

lui x cu x i se folosete apoi 6).

f) x(x + y) = xy. Se folosesc - n ordine distributivitatea, afirmaia

7) (Tabelul 1.1), comutativitateai 10) (Tabelul 1.1).

g)x (x + y) = x y. Din nou, se nlocuiesc simultan toate apariiile luix cuxn relaia precedent i se aplic6).

S trecem n revist i cteva rezultate importante din teoria

general a funciilor booleene, pregtind un suport abstract adecvat

pentru capitolele urmtoare.O primpartedintre enunuri vor fi reluate

pe parcursul lucrrii, ntr-un alt cadru.O a doua parteeste prezentat

mai detaliat n alte cursuri (cum ar fiArhitecturii sisteme de operare).

n sfrit, a treia parte necesit cunotine suplimentare (din acest

motiv, unele demonstraii vor fi omise).

O clasde proprieti interesante se referla o metodgeneral

de reprezentare standard a funciilor din FB. ncepnd cu teoremaurmtoare introducem notaiile x1 = x i x0 =x (n sensul cputerea

1 ataat unei expresii o las neschimbat, iar puterea 0 i

adaug o bar).Sremarcm cindicii superiori precedeni nu se

supun principiului dualitii (de exemplu, nu este adevrat c(x1 = x)

coincide cu (x0 = x)).


12/156


Teorema 1.2 ([CAZ1], de descompunere, n sum de termeni).

Pentru fiecare nN*, fFB(n) i fiecare k[n], avem:

1 2 k

1 2 k

1 2 n 1 2 k k+1 n1 2 k, ,..., B

f(x , x ,..., x ) = x x ... x f( , , ..., , x ,..., x )

oricare ar fi x1, x2, ... , xn B.

Demonstraie. Dacxi, i Batunci, direct din notaiile de mai sus,

rezultc:

(*) (x0) = (x)0precumix = 1 dac i numai dacx =.

Folosind 12) (Tabelul 1.1), rezultimediat c, n condiiile teoremei,

1 2 k1 2 kx x ... x = 1 dac i numai dacxi= ipentru fiecare i[k].

Fie acum elementele a1, a2, ... , an B, oarecare, fixate. Conform (*), n

suma

1 2 k

1 2 k

1 2 k k+1 n1 2 k, ,... , B

a a ... a f( , , ..., , a , ..., a )

unul i numai unul dintre factorii 1 2 k1 2 ka a ... a va fi egal cu 1,

adic cel pentru care i = ai, pentru fiecare i [k]. Datorit

comutativitii i legilor 10), 9) i 10) (Tabelul 1.1), rezultcsuma

este egalexact cu f(a1, a2, ... , an).

Este adevrat i teorema dual (de descompunere, n produs de

factori), ambele rezultate fiind folosite pentru demonstrarea

existenei formelor normale pentru funciile booleene. n enunul

teoremei duale, nafara nlocuirii lui + cu i a lui cu , numele


1,2, ... k(ca argumente ale lui f) se nlocuiesc cu aceleai elemente,

dar barate.

Definiia 1.2. Fie nN* i x1, x2, ... , xn B variabile (booleene)

distincte (putem nota mulimea acestora cu X = {x1, x2, ... , xn}, ideea

fiind nsclucrm cu o list, adiccu o colecieordonatde elemente

distincte). Se numete termen (n-ar, peste X) orice produs (uneori,

operatorul de produs este omis, sau supradimensionat)1 2 k

1 2 ki i it = x x ... x , unde 0 k n, 1, 2, . . . , k B i

1i1< i2< ... < ikn.

n definiia precedent, termenul generat pentru k=0 este 1 (prin

convenie). Pentru k = n obinem aa-numiii termeni maximali

(maxtermeni), adic acei termeni n care fiecare dintre variabilele

considerate apare o dat i numai o dat (barat sau nebarat), n

ordinea precizat.

Observaie. ntre mulimea termenilor n-ari t (peste X) i mulimea

n-uplelor peste {0, 1, 2} (aceasta coincide de fapt cu mulimea

{f | f : [n]{0, 1, 2}}) se poate stabili o corespondenbiunivocg,

datde g(t) = , unde, pentru fiecare i[n], avem ei= 0

dacxi apare baratn t, ei = 1 dacxi apare nebaratn t i ei = 2 n rest

(xinu apare n t). Mulimea termenilor n-ari considerai va avea atunci

3n elemente. Raionnd similar pentru cazul maxtermenilor n-ari (n

acest caz, nu este posibil ca vreo variabil considerat s nu apar),


13/156


rezult c exist 2n maxtermeni n-ari distinci (indiferent de numele

celor n variabile diferite fixate prin X).

Consideraiile de natur combinatorial sunt practic indispensabile n

vederea obinerii unor rezultate convenabile.

ntrebare.Putei rescrie att teorema de descompunere cu termeni

cti teorema de descompunere cu factori pentru cazul n = 2 i k = 1 ?

Exemplu. Daclum n = 2 i notm x1cu xi x2cu y, atunci cei 32 = 9

termeni sunt: x, y, x, y, xy, x y, x y,x y, 1. Cei 22 = 4 maxtermeni

sunt: xy, x

y, x ,y

x y.

ntrebare. Sunt adevrate afirmaiile fcute n precedenta

Observaie? Justificai rspunsul.

ntrebare. Fie X = {x, y, z, t}. Este x zt un maxtermen

(peste X) ?

Definiia 1.3. Se numeteformnormaldisjunctiv(n-ar, n N*),

sau (n-)FNDpe scurt, orice sum(finit) de termeni n-ari distinci. Se

numete form normal disjunctiv perfect (n-ar, n N*), sau

(n-)FNDP pe scurt, orice sumde maxtermeni n-ari distinci.


OriceFNDse poate reprezenta i grafic, ca unarbore([KNU],

[LUC]). Datorit comutativitii adunrii putem face abstracie de

ordinea (max)termenilor dintr-o sum,mai exact, considernd oricare

dousume care diferdoar prin ordinea termenilor, le vom privi ca

fiind identice. Vor exista astfel knC 3 forme normale disjunctive n-are

avnd k termeni, 0k3n (prin convenie, pentru k = 0, unica form

care este acceptat i estei perfect, se noteaztot cu 0). n consecin,

numrul total al n-FND urilor va fi:

0 1 3 33 3 3 3

... ... 2n n

n n n nkC C C C .

Analog, numrul total al n-FNDP urilor va fi:

0 1 2 22 2 2 2

... ... 2n n

n n n nkC C C C .

Teorema 1.3([CAZ1]). Orice funcie booleanse poate reprezenta n

mod unic ca oFNDP.

Demonstraie. Fie fixate n N* , fFB(n) i X = {x1, x2, ... , xn}.

AplicndTeorema de descompunere cu termeni pentru f i k = n,

gsim cf se poate scrie sub forma:

1 2 n

1 2 n

1 2 n n 1 2 n1 2, ,..., B

f(x , x , ... , x ) = x x ... x f( , ,..., )

oricare ar fi valorile lui x1, x2, ... , xn din Bi prin urmare avem:

1 2 n

1 2 n

1 2 n n1 2, , ..., B

f(x , x , ... , x ) = x x ... x

,


14/156


15/156


deoarece reamintim - pentru fiecare numr natural n numrul

funciilor booleene n-are este n22 iar numrul formelor disjunctive n-

are este n32 ). Problema anterioar este rezolvabil cu ajutorul

algoritmului lui W. Quine([CAZ1]). Algoritmul lui Quine intrsub

incidena principiului dualitii, astfel nct fcnd modificrile de

rigoare el poate determina i toate formele normale conjunctive

minimale (FNCM)pentru orice funcie boolean.

O problemsimilar, prin rezolvarea creia s-ar putea reduce n

anumite cazuri timpul de procesare a unor texte (expresii, formule,

etc.), este gsirea unui numr minim de operaii booleene

convenabile, cu ajutorul crora s se reprezinte orice funcie

boolean.

Definiia 1.4. Clasafunciilor booleeneelementareeste:

E= { npi | nN*, 1p n, n

pi : Bn B,

npi (x1, x2, ... , xp, ... , xn) = xp}.

Fie n N*, t un numr natural, f, h1, h2, ... , htFB(n)

i g FB(t).

Spunem cf se obine din g, h1, h2, ... , htprinsuperpoziiedacpentrufiecare x = avem:

f(x) = g(h1(x), h2(x), ... , ht(x)).

Fie MFB. Se numeteM-iroricesecven(list) finitf0, f1, ... , fr

de funcii booleene n care fiecare fieste fie dinE U M fie se obine

prin superpoziie din alte funcii, aflate n aceeai listdar naintea lui

fi.


Funciile npi se mai numesciproiecii. Pentru superpoziie vom

utiliza notaia f = SUP(g, h1, h2, ... , ht), iar M va denotamulimea

funciilor care apar ca elemente n M-iruri. Pentru fiecare M dat, M

va fi practic o mulime definit constructiv, n careEU M constituie

mulimea funciilorde baziaroperatorul de superpoziieeste singura

modalitate de a se obinefuncii noi din funcii vechi. Prin urmare, M

este cea mai micmulime care conine proieciile, elementele lui M i

estenchisla superpoziie. Algebric vorbind, se mai spune c M este

nchidereaprin superpoziie a mulimiiEU M. Mse va numinchis

daccoincide cu nchiderea sa.

Teorema 1.5([CAZ1]). O mulime MFB este nchisdac i numai

dac conine funciile elementarei orice superpoziie de funcii din Mse afln M.

Demonstraie. Este imediatdin definiii, demonstraia reprezintnd o

aplicare directa principiului induciei structurale. Astfel, este suficient

sartm c, datM, avem:

Baza.E Mi M M .

Pas inductiv. Pentru fiecare nN*, fiecare tN*, fiecare gFB(t),

fiecare h1, h2, . . . , ht FB(n), fiecare f FB(n), astfel nct

f = SUP(g, h1, h2, ... , ht), avem:Dacg, h1, h2, ... , htM, atunci

fM.

Exemple imediate de mulimi nchise sunt , E i FB. Se poate

arta i c urmtoarele mulimi (infinite) sunt mulimi nchise (a se


16/156


consulta i exerciiile din finalul capitolului, mpreun desigur cu

rezolvrile dinAnex):

T0: mulimea funciilor booleene de oricte argumente care

pstreazpe 0, adicsatisfac f(0, 0, ... , 0) = 0.

T1: dual, mulimea funciilor carepstreazpe 1, adicsatisfac

f(1, 1, ... , 1) = 1.

Aut: mulimea funciilor autoduale (f = f). S notm ca o

proprietate de caracterizare interesant pentru aceastclasdefuncii i faptul c f(x1, x2, ... , xn) = 1 2f(x ,x ,...,x )n . Acest

lucru se obine imediat deoarece tabela de definiie pentru f se

obine din tabela pentru f, nlocuind simultan, peste tot, pe 0 cu

1i pe 1 cu 0.

Mon: mulimea funciilormonotone. Pe Bputem defini o relaie

de ordine natural: 01 (putem pune chiar 0 < 1). Relaia

precedent poate fi extins pe componente la orice produs

cartezian. S considerm dou n-uple = i

= ,i, i B, i [n]. Vom spune c dac

i numai dac i i pentru fiecare i [n] (desigur cvom avea

< dac i numai dac i adic i diferprin

mcar o component). O funcie f FB(n) este monotondac

pentru fiecare,Bn, din rezultf() f().

Lin: mulimea funciilorliniare. Se poate arta mai nti c

tripletul I = este un inel comutativ cu unitatea 1,

izomorf cu inelul claselor de resturi modulo 2 (cele dou

mulimi suport i operaiile corespondente se pot


identifica). Urmeaz c orice funcie boolean se poate

reprezenta unic ca un polinom (eventual, de mai multe

variabile) cu coeficieni n I . Fie astfel o funcie boolean f,

despre care tim deja cse poate scrie ca o sum(boolean) de

termeni. Putem acum folosi egalitile (se pot demonstra uor,

folosind tabelele de adevr ) : x = x 1 i x + y = yx =

= (x1) (y1)1 = x y x y, precum i proprietile

inelelor, pentru a observa coriceFND a lui f devine o sum

modulo 2de termeni (care sunt produse de variabile distincte).

Numrul acestor produse este 2n, deci numrul polinoamelor

modulo 2 este n22 , acelai ca i numrul funciilor booleene

n-are (de unde urmeazunicitateareprezentrii). Spunem co

funcie fFB(n)

este liniardacreprezentarea sa (unic) subformde polinom modulo 2 are aspectul:

c0 c1 x1 c2 x2 ... cn xn, ci B, i [n].

Observaie. Se poate arta ctoate mulimile anterioare sunt nebanale,

adicnu coincid nici cu FB, nici cuE, nici cu .

Exemplu([CAZ1]). Funcia f(x, y, z) = xz + x y z + x y z este

liniardeoarece avem succesiv:

f(x, y, z) = comutativitate, distributivitate

= xz +x z(y + y ) = tim cy+ y= 1

= xz +x z = folosind a + b = ab a b

= xz x z xz x z = tim cxz x z = 0


17/156


= x z x z = folosinda = a 1

= x z (x 1) (z1) = distributivitate

= x z x z x z 1 = folosind a a = 0

= x z 1.

Definiia 1.5. O mulime de funcii booleene este complet dac

nchiderea sa coincide cu FB. O mulime complet se numete baz

dacestemaximal(adicnici o submulime proprie a sa nu mai estecomplet).

Observaie. Se arat relativ simplu cmulimea {c0,c1, f, }, unde f

este dat prin f(x, y, z) = xyz, este o baz. Mulimea {, +, }

este complet(ceea ce se aratdirect, folosind definiiile), dar nu este

baz pentru catt { , } ct i { , +} sunt complete (acest lucru

rezultdin legile lui deMorgan, care ne spun cdisjuncia se exprim

cu ajutorul negaiei i conjunciei i dual, conjuncia se exprim cu

ajutorul negaiei i disjunciei). Poate surprinztor, {+, } nu este

complet, dar { | } (care nu este inclusn nici una dintre mulimileT0,

T1, Aut, Mon, Lin) este complet i desigur baz (ne bazm peegalitile x= x | x i xy = (x | y) | (x | y)). Prin urmare, dac ne

reamintim de unul dintre scopurile enunate (exprimarea tuturor

funciilor booleene cu ajutorul unui numr minim de funcii), mulimea

{|} ar fi candidatul ideal. Din pcate, operatorul lui Sheffer (|) nu

este prea comod (din punct de vedere al gndirii umane) astfel nct

exprimrile celorlalte funcii devin complicate i greu de reinut. Este


de dorit sse gseasco cale de mijloc, prin care sse pstreze ntr-

adevr ct maipuine funcii ntr-o baz, dar acestea sfie iuor de

neles/manipulat.

Acceptm fr demonstraie (Teorema 1.7 a fost ns deja

demonstrat implicit, prin comentariile anterioaree), urmtoarele

rezultate ([CAZ1], aceastreferinnefiind sursa primar):

Teorema 1.6 (E. L. Post). O mulime de funcii booleene este complet

dac i numai dacnu este inclusn nici una dintre mulimileT0, T1,

Aut, Mon, Lin.

Teorema 1.7. Orice bazconine cel mult patru funcii i exist baze

compuse din una, dou, treii patru funcii.

Teorema 1.8. Orice mulime nchisde funcii booleene fie este inclus

cel puin n una dintre mulimileT0, T1, Aut, Mon, Lin, fie coincide cu

FB.

Teorema 1.9. MulimileT0, T1, Aut, Mon, Linsunt precomplete (o

mulime M de funcii booleene este precompletdacpentru orice alt

funcie fM, mulimea M U{f} este complet).

E. L. Posta determinat chiartoatemulimile nchise de funcii

booleene nc din anul 1941, ct i relaiile de incluziune ntre ele i

anumite baze. ncse fac cercetri n legturcu extinderea rezultatelor


18/156


19/156


Este poate bine smenionm faptul cam preferat unIndexn

ordinea paginilor i nu n ordine alfabetic, tocmai pentru cinsistm

asupra necesitii parcurgerii secveniale a materialului.

5.Exerciii

1. Completai demonstraiaTeoremei 1.1, adicartai validitatea

legilor 1), 2), 3), 5), 1) 5)i x + ( x ) = 1, utiliznd tabelele

de adevr.2. Artai cV = < 2V,,U, CV> este o algebrboolean, oricare

ar fi mulimea (nevid) V. n plus, demonstrai c 0 = i

1=V.

3. Artai adevrul afirmaiilor rmase nedemonstrate dinTabelul

1.1.4. Justificai egalitatea card(FBn) =

n22 .

5. Fie mulimea termenilor n-ari t, construii peste mulimea

variabilelor booleene distincte (ordonate) X = {x1, x2, ... , xn},

precumi mulimea n-uplelor peste {0, 1, 2}. Artai cexisto

funcie bijectiv g, care identific aceste mulimi, dat prin

g(t) = , unde, pentru fiecare i[n], avem ei= 0

dacxiapare baratn t, ei= 1 dac xiapare (nebarat) n t i

ei= 2 n rest (adic xinu apare n t). De asemenea, artai c

exist (mcar) o coresponden bijectiv ntre mulimea

n-uplelor peste {0, 1, 2} i mulimea de funcii

{f | f : [n]{0, 1, 2}}. Deducei cmulimea termenilor n-ari


considerai va avea 3n elemente i cvor exista 2n maxtermeni

n-ari distinci.

6. S se gseasc FNDP i FNPC pentru funcia definit prin

tabelul:

x y z f(x, y, z)

0 0 0 0

0 0 1 1

0 1 0 10 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 1

7. Justificai faptul c mulimile T0, T1, Aut, Mon, Lin sunt

infinite. Artai cT0este mulime nchis.

8. Artai cmulimea M = {, +, } este o mulime completde

funcii booleene.

9. Artai cfuncia boolean + este o funcie monoton.10. Artai cI = este un inel comutativ cu unitatea1i

c el este izomorf cu R= , inelul claselor de

resturimodulo 2.

11. Artai cfuncia booleanf(x, y, z) = x y+ y z nu este liniar

(acolo unde nu exist confuzii, operatorul nu va fi scrisexplicit).


20/156


21/156


22/156


23/156


24/156


25/156


n finalul paragrafului, pentru a introduce i o notoptimist,

prezentm una dintre cele mai mari demonstraii cunoscute n

literatura tiinific a afirmaiei Oamenii de tiin nu vor ctiga

niciodatla fel de muli bani ca directorii executivi ai unor companii

de succes. n acest scop vom porni de la postulatele (axiomele)

Cunoaterea nseamnputere iTimpul nseamnbani, pe care le vom

folosi sub forma prescurtat: cunoatere = putere i respectiv

timp = bani. Ca inferene, le vom utiliza pe cele mai simple (imediate,

cu afirmaii categorice), la care adugm altele la fel de simple,

cunoscute din matematica elementar. Plecm astfel de la axioma

suplimentar:

muncputere

timp

Folosind axiomele iniiale i proprietile relaiei de egalitate, printr-o

inferensimpldeducem:

munccunoa tere

bani

Aplicnd acum o proprietate a proporiilor, gsim:

m un c= ban ic u n o a tere

Cititorul poate trage singur concluzia care se impune pentru situaia n

carecunoaterese apropie de (tinde la) valoarea zero.

Ca o concluzie, situaiile neplcute descrise anterior trebuie

evitate sau eliminate. Acest lucru se poate face doar prin translatareaprilor de limbaj ntr-un mecanism formal bine pus la punct, pe care-l


vom descrie ncepnd cu seciunea/paragraful urmtoare/urmtor.

Enunul unora dintre exerciiile care urmeazeste reluat n2.10.

Exerciiul 2.1. Oteorem, n sensul matematicii de liceu, arei ea

ipoteze i concluzii. Scriei simbolic forma general a unei teoreme

(directe), utiliznd propoziii elementare (variabile propoziionale) i

conectori logici. Scriei apoi teorema reciproc, contrara teoremei

directe i contrara reciprocei. Exist vreo legtur ntre acestea, n

ceea ce privete valoarea lor de adevr? Dai un exemplu deteorem

de caracterizare (A dac i numai dac B). Putei specifica altfel

rezultatul exprimat de teorem, astfel nct sfie separat - puse n

evidencondiia necesar icondiia suficient ?

Exerciiul 2.2. S considerm definiia limitei unui ir dat de

numere reale, avnd ca valoare un numr real dat, definiie exprimat

cu ajutorul vecintilor care sunt intervale simetrice fade punctul

considerat. S se exprime simbolic (n sensul matematicii de liceu,

folosindicuantificatorii) aceastdefiniiei sse negeformulaastfel

gsit.

Exerciiul 2.3. Exprimai simbolic, ca o formul n sensul

exerciiilor anterioare propoziiaDac mi-e sete, beau ap . Negai

formula i apoi rescriei rezultatul n limbaj natural. Dacai fi negat

direct propoziia iniial, ai fi obinut acelai lucru?

n restul capitolului, cteva dintre concepte/rezultate/exemple

sunt din [MAS1] (trebuie sprecizm co parte dintre acestea provin,

la origine, din [SCH]).


26/156


2. Sintaxa logicii propoziionale

Vom trece direct la prezentarea sintaxei formale a logicii

propoziionale (calculului propoziional). Logica propoziional, aa

cum am sugerat deja, va fi numele unei mulimi de formule

(propoziionale), notatLPL

sau, prescurtat,LP i definitstructural n

cele ce urmeaz.

Definiia 2. 1. Fie o mulime numrabil de variabile propoziionale

(formule elementare, formule atomice pozitive, atomi pozitivi),

A = {A1, A2, }. Fie, de asemenea, C = {, , } mulimea

conectorilor/conectivelor logici/logicenon(negaia),sau(disjuncia),

respectiv i (conjuncia) i P = { ( , ) } mulimea parantezelor

(rotunde).Formulele(elementele luiLP) vor fi cuvinte (expresii bine

formate) pestealfabetulL =AU CU P:

Baza(formulele elementare sunt formule).ALP.

Pas constructiv(obinere formule noi din formule vechi).

(i) DacFLP atunci (F)LP.

(ii) DacF1, F2LPatunci ( F1 F2)LP.

(iii) DacF1, F2LPatunci ( F1F2 )LP.

(iv) DacFLPatunci (F)LP.

(v) Nimic altceva nu este formul.


Putem privi o formul F ca fiind reprezentat de un arbore binar

(arborele ataat lui F, notat Arb(F)), n modul urmtor (procedm

structural, conform definiiei luiLP):

Definiia 2.2.

Baza. F = A A. Atunci arborele ataatlui F (sau, arborele care

reprezintF), este:

Pas constructiv.

(i) Fie F = (F1)i spresupunem cse cunoate arborele ataat lui F1,

Arb(F1). Atunci, arborele ataat lui F va fi (ceva similar se obine

pentru (iv), adicpentru cazul F = (F1)):

(iii) Fie F = (F1F2)i spresupunem cse cunosc att arborele ataat

lui F1ct i arborele ataat lui F2, adic Arb(F1) respectiv Arb(F2).

Atunci arborele ataat lui F va fi (pentru F = (F1F2) se obine ceva

similar):

A

( )

Arb(F1)


27/156


Dei au un rol pur sintactic, neschimbnd cu nimic semantica

formulelor n care apar, parantezele rotunde au fost din anumite

motive tehnice privite mai sus ca un operator pre&post-fixat. Dac

introducem oordine stnga-dreaptape mulimea succesorilor imediaiai fiecarui nod (implicit, pentru o formul este valabil ordinea de

scriere a literelor n cuvntul respectiv, exceptnd paranteza nchis

), care are acelai numr de ordine cu paranteza deschis (

corespunztoare), atunci se observ cfiecrei formule i corespunde

un arbore ataat unic i fiecrui arbore ordonat G (cu nodurile

etichetate cu elemente din L ) i corespunde o unic formul din LP

(pentru care G este arborele ataat). Definim structural i mulimea

subformulelor oricrei formule date F (notat subf(F)). Admitem

implicit faptul cFsubf(F) dac i numai dacF este subcuvnt al

lui Fi FLP (cu alte cuvinte, F1i F2, n cele ce urmeaz, sunt tot

formule).

( )

Arb(F1) Arb(F1)


Definiia 2.3.

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

Pas constructiv.

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

(ii) F = (F1F2). Atunci subf(F) = subf(F1)Usubf(F2)U{ (F1F2) }.

(iii) Analog cu (ii) pentru cazul F = (F1 F2) (nlocuind peste tot,

simultan,cu).(iv) F = (F1). Atunci subf(F) = subf(F1)U{ (F1) }

Observaie. Nu se admit alte posibiliti pentru scrierea unei formule,

dect cele fixate prinDefiniia 2.1. Existde altfel un algoritm care

rezolv problema de decizie: Dat orice cuvnt w L * (adic orice

secvenfinitde caractere dinL ) sse deciddacw LP. Conform

[JUC] de exemplu, notaiaL * (algebric,L * este monoidul liber generat

de L ) se explicprin aceea cmulimea cuvintelor (secvenelor finite

de simboluri) aparinnd unui alfabet cel mult numrabil formeazun

monoid fa de operaia de concatenare (de juxtapunere a

literelor/cuvintelor). Elementul neutru, este cuvntul fr nici o liter

(cuvntul vid) i este notat cu e. Algoritmul menionat se termin

pentru fiecare intrarewL *, cu rspunsul (ieirea) DA dacwLP

i NU dacwLP. Oproblemde decizieare doar alternativa de

rspuns DA/NU i aici este un caz particular al problemei de

apartenen pentru un limbaj de tip 2. Revenind, A1 A2, nu este


28/156


29/156


prezent n definiia algebrelor booleene, rezultatele privind sintaxa

fiind, n general, separate de cele privind semantica. Se numeteclauz

orice disjuncie (finit) de literali. Se numete clauz Horno clauz

care are cel mult un literal pozitiv. Oclauzpozitiveste o clauzcare

conine doar literali pozitivi, iar o clauz negativ va conine doar

literali negativi. Oclauz Horn pozitiv va conine exact un literal

pozitiv (dar, posibil,i literali negativi).

3. Semantica logicii propoziionale

Semantica (nelesul)unei formule propoziionale este, conform

principiilor logicii aristotelice, o valoare de adevr (asauf), obinutn

mod determinist, care este independentde context, etc. Notnd de la

nceput pea cu 1 i pe fcu 0, astfel nct sputem lucra cu algebra

boolean B = < B, , +, >, noiunea principaleste cea deasignare

(interpretare, structur).

Definiia 2.4. Orice funcieS,S:A Bse numeteasignare.

Teorema 2.1 (de extensie). Pentru fiecare asignare Sexist o unic

extensie a acesteia, S : LP B (numit tot structur sau

interpretare), care satisface:

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

(ii)S((F)) = (F)'S , pentru fiecare FLP.

(iii)S((F1F2) ) =S(F1) S(F2), pentru fiecare F1, F2LP.


(iv)S((F1F2) ) =S(F1) +S(F2), pentru fiecare F1, F2LP.

Demonstraie. FieS:A B. Definim funciaS:LP B, structural,

prin:

Baza.S(A) =S(A), pentru fiecare AA.

Pas constructiv.

(a) DacF = (F1), atunciS(F) = 1'(F )S .

(b) DacF = (F1F2), atunciS(F) =S(F1) S(F2).

(c) DacF = (F1F2), atunciS(F) =S(F1) +S(F2).

Este evident c S este o extensie a lui S, proprietatea (i) fiind

satisfcut imediat conform pasuluiBaza de mai sus. De asemenea,

definiiile (a) (c) dinPasul constructivasigursatisfacerea punctelor

(ii) (iv) din enun, deoarece orice formul din LP, dac nu este

elementar, are una dintre cele trei forme considerate (cazul F = (F1)

este mult prea simplu pentru a fi tratat separat). Mai rmne sartm

c S este funcietotal(adic,ataeazfiecrui element din domeniu

un element i numai unul din codomeniu) i c ea esteunica funcie

care satisface (i) (iv). Acest lucru se face prininducie structural,

trebuind sartm cpentru fiecare FLP, este adevratP(F), undeP(F) este:Oricare ar fi asignareaS, valoareaS(F) exist(ca element

al lui B) i este unic, adicS este funcie, i oricare altfuncieS

care satisface (i) (iv), satisfaceS(F)=S(F).

Baza. Fie F = A Ai orice asignareS. Cum Seste funcie (total)

prin definiie i avemS(A) =S(A), tot prin definiie (Seste extensia


30/156


luiS), este imediat faptul cS(A) exist i este unicn sensul precizat

(orice alt posibil Strebuie sfie tot o extensie a luiS).

Pas inductiv. Vom arta doar cazul F = ( F1), celelalte dou

(F = (F1F2)i F = (F1F2) ) fiind similare. Presupunem prin urmare

P(F1) ca fiind adevrat i demonstrm cP(F) este adevrat. Fie orice

asignareS. Faptul cS(F) exist(ca element al lui B) i este unic(n

sensul precizat), rezultdin nou imediat, din ipoteza inductiv (S(F1)

exist i este unic), din definiia negaiei n B(tim cS(F) = 1(F )'S )

i a faptului corice altStrebuie ssatisfacpunctul (ii) din teorem.

De acum nainte nu vom face nici o diferen, nici mcar

notaional, ntre asignare i structur (intrerpretare). Se observc

dat orice formul F LP i orice structur S, este suficient s

cunoatem valorile luiSn variabilele propoziionale care aparn F

(pentru fiecare F LP, vom nota cu prop(F) mulimea atomilor

pozitivi care apar n F, saupeste care este construit F). Vom numi

asignare (structur) complet pentru F, orice funcieparial Scare

este definit exact (sau, mcar) pe prop(F)A i cu valori n B.

Aceasta, n cazul n care F este cunoscut, poate fi identificat cu o

funcie totalpeA.Putem conchide chiar cnLP valoarea de adevr

a unei formule se deduce n mod unic din valoarea de adevr a

subformulelor(se mai spune clogica propoziionalareproprietatea


de extensionalitate). Vom mai pune S(F) S((F)) pentru fiecare

FLP.

Exerciiul 2.5. Definii structural prop(F), pentru fiecare FLP.

Fr alte precizri, vom lucra n continuare doar cu structuri

complete pentru mulimile de formule (o structureste completpentru

o mulime de formule dac este complet pentru fiecare element din

acea mulime) care ne intereseazla momentul dat.

Definiia 2.5. O formulF LPse numete satisfiabildacexist

mcar o structur S (complet) pentru care formula este adevrat

(S(F) = 1). Se mai spune n acest caz c S este model pentru F(simbolic, se mai scrieSF). O formulestevalid(tautologie)dac

orice structur este model pentru ea. O formul este nesatisfiabil

(contradicie)daceste falsn orice structur(S(F) = 0, pentru fiecare

S, sauSF, pentru fiecareS).

Teorema 2.2. O formulF LPeste validdac i numai dac(F)

este contradicie.

Demonstraie. FLP este validdac i numai dacpentru fiecare

structurSavemS(F) = 1, adic (conform ii),Teorema 2.1) dac i


31/156


numai dacS((F) ) = 1 = 0 (definiia negaiei), ceea ce nseamnc

(F) este o contradicie.

Clasa tuturor formulelor propoziionale LP, este astfel

partiionat n (mulimile indicate mai jossunt ntr-adevr nevide i

disjuncte):

TautologiiF

Formule satisfiabile dar nevalideF (F)

Contradicii( F)

Tabelul 2.1

n tabelul anterior linia punctat poate fi considerat drept o

oglindn care se reflectadevrul.

Definiia 2.6. Douformule F1, F2 LP se numesctare echivalente

dacpentru fiecarestructurSele au aceeai valoare de adevr, adic

S(F1) =S(F2) (simbolic, vom scrie F1 F2). F1 i F2se numescslab

echivalentedacF1satisfiabilimplicF2satisfiabil i reciproc (vom

scrie F1 s F2, ceea ce nseamn c dac exist S 1 astfel nct

S1(F1) = 1, atunci exist S 2 astfel nctS 2(F2) = 1 i reciproc). O

formulFLPesteconsecinsemanticdintr-o mulime de formule

GLP, dacpentru fiecare structurcorectS(aceasta nseamnaici


faptul cSeste definitcel puin pentru toate variabilele propoziionale

care apar fie n F fie n elementele lui G), dacS satisface G(adic

avemS(G) = 1 pentru fiecare G G)atunciSsatisface F(simbolic,

vom scrieGF).

Observaie. Relaiile is suntrelaii de echivalen(binare) peLP,

n sens matematic (adicsuntreflexive,simetrice itranzitive) i prin

urmareLPpoate fipartiionatn clase de ehivalencorespunztoare,

obinndu-semulimile ctLP/, respectiv LP/s. Mai mult, privind

,, ca nite operatori (de fapt, ar trebui s-i considermmpreun

cu parantezele pe care le introduc, vezi iExerciiul 2.4), atunci relaia

estecompatibil (la stnga i la dreapta) cu acetia ([IP]), astfel

nct considernd 4-uplulLP = , se poate arta cacesta

formeazo algebrboolean(homomorfcu B = < B, , +, >, dup

cum sugereazTeorema de extensie).

Teorema 2.3. Fie GLPiG= { G1, G2, , Gn }LP. Urmtoarele

afirmaii sunt echivalente:(i) G este consecinsemanticdinG.

(ii) (1

n

i Gi)G este tautologie.

(iii) (1

n

i Gi) G este contradicie.


32/156


Demonstraie.

(i) implic (ii). Presupunem prin reducere la absurd c

F = (1

n

i Gi)G nu este tautologie, dei G este consecinsemantic

din G. Rezult c existo structurSpentru care F este fals, adic

S(1

n

i Gi) = 1 iS(G) = 0. Prin urmare, pentru fiecare i [n] avem

S(Gi) = 1 i ca urmareS(G) = 0. n concluzie, existo structurSastfelnctS(G) = 1 iS(G) = 0. Acest lucru este absurd pentru cG este

consecinsemanticdinG.

(ii) implic (iii). Procedm din nou prin reducere la absurd, adic

presupunem cdei (1

n

i Gi)G este tautologie, (

1

n

i Gi) G nu

este contradicie. Aceast nseamn c F1 = (1

n

i Gi) G este

tautologie, dar F2= (1

n

i Gi) G este satisfiabil. Prin urmare, exist

o structurSastfel nctS(F2) = 1 (i, desigur,S(F1) = 1). DinS(F2) = 1

rezultS((1

n

i Gi)) S(G) = 1, adicS((

1

n

i Gi)) = 1i S(G) = 1.

n consecin, S( (1

n

i Gi ) ) = 0 i S(G) = 0. Pentru c

S(F1) = S((1

n

i

Gi )) + S(G), avem S(F1) = 0, ceea ce este absurd

deoarece F1 este tautologie.


(iii) implic (i). Presupunem prin reducere la absurd c

F = (1

n

i

Gi) G este contradicie, dar G nu este consecinsemantic

dinG. Atunci existo structurScare satisface toate formulele dinG

dar nu satisface G. Prin urmare, avemS((1

n

i Gi)) = 1iS(G) = 0, adic

S((1

n

i Gi)) = 1iS(G) = 1. CumS((

1

n

i Gi) G) =S((

1

n

i Gi))S(G),

rezult c existSastfel nct S((1

n

i Gi) G) = 1, deci F nu este

contradicie (absurd).

n teorema anterioar am renunat la anumite paranteze,

respectnd prioritile/conveniile fcute. Vom face i pe viitor acest

lucru, fra-l mai meniona explicit.

Teorema 2.4. Sunt adevrate urmtoarele echivalene (tari, pentru

oricare F, G, H LP):

(a)FF F (a)F F F (idempoten)(b)FG G F (b)FG = GF(comutativitate)

(c)( F G ) H

F( GH )

(c) (F G) H F (G H)

(asociativitate)

(d)F ( G H )

(FG)(FH)

(d)F( GH )(FG)(FH)

(distributivitate)(e)F( F G )F (e)F ( F G )F(absorbie)

F d l l i l I f i ii 69 70 C i i M l i


33/156


(f) F F (legea dublei negaii)

(g) ( FG ) F G

(g) ( F G ) F G (legile luideMorgan)

(h)FG F (h) F G G (legile validitii,

adevratedoar dacF este tautologie)

(i)FG F (i) F G G (legile contradiciei,

adevratedoar dacF este contradicie)Demonstraie. Vom arta doar una dintre echivalene i anume(i). Fie

F LP orice contradicie i GLP. Fie orice structur S. Atunci

S(F G) = S(F)S(G) = 0, conform Tabelului 1.1 (punctul 9)) i

faptului cF este contradicie. Aceeai valoare o are i membrul drept

din(i).

Se poate arta, de exemplu, prin inducie matematic, faptul c

asociativitatea, distributivitateai legile lui deMorgan se extind pentru

orice numr finit de formule.

Teorema 2.5 (de substituie). Fie H LP, oarecare. Fie orice

F, G LP astfel nct F este o subformul a lui H i G este tare

echivalentcu F. Fie H formula obinutdin H prin nlocuirea (unei

apariii fixate a) lui F cu G. Atunci H H.

Demonstraie. Intuitiv, teorema spune cnlocuind ntr-o formulo

subformulcu o formulechivalent, obinem o formulechivalentcu


cea iniial. Vom proceda prin inducie structural, avnd de artat

teorema din metalimbaj(H LP)P(H), unde

P(H): (F, G, HLP)(((Fsubf(H))i

(H se obine din H nlocuind o apariie fixata lui F cu G)i

(F G))H H).

Baza. H = A A. S artm c P(A) este adevrat. Fie F, G,

H LP, astfel nct F subf(H), H se obine din H nlocuind

apariia aleasa lui F cu G, iar F G. Trebuie sartm cH H.Dar, din Fsubf(H)i subf(H) = {A}, rezultcF = A ( care coincide

cu H). Prin urmare, H = G. Avem acum F = H, G = H i F G, de

unde urmeazimediat cH H.

Pas inductiv. Trebuie tratate separat situaiile care urmeaz.

(i)H = (

H1).Presupunem c P(H1) este adevrat i demonstrm cP(H) este adevrat. Fie F subf(H) = subf(H1)U {( H1)}. Dac

F = ( H1 ) ( = H), suntem ntr-o situaie similar cu cea din Baza,

deoarece raionamentul se face din nou asupra ntregii formule H. Fie o

apariie fixata lui Fsubf(H1)subf(H)i considerm orice GLP

astfel nct GF. nlocuind pe F cu G n H, nseamnn acelai timp a

nlocui pe F cu G n H1. Notnd cu H respectiv H1 formulele obinute,

putem aplica ipoteza inductiv (P(H1) este adevrat) i obinem c

H1 H1. Revenind, tim c H = ( H1), H = ( H1) i H1 H1.

Rezult imediat c HH (vezi iObservaia care precede imediat

Teorema 2.3iV.2.8dinAnex).

Fundamentele logice ale Informaticii 71 72 Cristian Masalagiu


34/156


(ii)H = (H1 H2).Presupunem c P(H1) i P(H2) sunt adevrate i

demonstrm c P(H) este adevrat. Fie orice F subf((H1H2)) =

subf(H1)Usubf(H2)U{(H1H2)}. DacF = ( H1H2 ) ( = H) suntem

din nou ntr-un caz similar cu cel din Baza. S considerm c

F subf(H1) (apariia deja fixat), cazul F subf(H2) tratndu-se

similar. Fie orice GLPastfel nct G F. A nlocui pe F cu G n H

nseamn, n acelai timp, a nlocui pe F cu G n H1(H2rmnnd

neschimbat). Vom nota cu H respectiv H1, formulele obinute dupaceste nlocuiri. Aplicnd ipoteza inductiv (P(H1) este adevrat),

rezult imediat c H1 H1. Revenind, tim c H = (H1 H2),

H = (H1H2) i H1H1. Obinem imediat cHH (putem folosi

direct faptul deja amintit, ceste compatibilcu operaiile, respectiv

cu conjuncia).

(iii)H = (H1 H2). Se demonstreazanalog cu cazul precedent.

Pentru a nu exista confuzii ntre limbajul de baz (LP) i

metalimbajul n care exprimm afirmaiiledespreelementele luiLP, n

cele de mai sus (precum i n continuare) am notatimplicaiacuiar

conjuncia prin i. Deocamdat am pstrat notaia clasic pentrucuantificatorul universal(), deoarece el nu apare explicit nLP.

Rezultatele obinute ne permit practic s tratm formulele din

LP ntr-un mod similar cu funciile booleene, dac ne intereseaz

probleme de natursemantic. Astfel, vom nota cu0orice contradicie

i cu 1orice tautologie i vom accepta principiul dualitii (rolul lui


i + lundu-l respectiv , dup cum se poate deduce chiar din

Teorema 2.4). De asemenea, vom folosi tabelele de adevr pentru a

gsi n mod direct semantica (valoarea de adevr a) unei formule ntr-ostructurdat.

Nu apare astfel surprinztoare tematica paragrafului urmtor,

privind existenaformelor normale.

4. Forme normale n LP

Spre deosebire de cazul funciilor booleene, vom studia pentru

nceput formele normale conjunctive i formele normale disjunctive

simultan.

Definiia 2.7. O formul F LP se afl n form normal

conjunctiv (FNC, pe scurt) dac este o conjuncie de disjuncii de

literali, adicoconjuncie de clauze. Simbolic:

inm

i, ji= 1 j 1

F ( L )

(notmin

i i,jj=1

C L , i[m] ).

Similar, FLPeste nformnormaldisjunctiv (FND, pe scurt),daceste odisjuncie de conjuncii de literali.

n cele de mai sus Li,jAU .

Exemplu. F = (A(BC)) este nFNCiar G = ((A B)(AC))este nFND, dacA, B, CA.



35/156


Teorema 2.6. Pentru fiecare formul F LP exist cel puin dou

formule F1, F2LP, F1aflatnFNC i F2aflatn FND, astfel nctFF1 i FF2(se mai spune cF1i F2 sunt oFNC, respectiv oFND,

pentru F).

Demonstraie. Pentru a demonstra afirmaia necesar, (F)P(F) n

metalimbaj, unde

P(F): exist F1 LP, aflat n FNC i exist F2LP, aflat nFND,astfel nctF F1i FF2,

procedm prin inducie structural.

Baza. F = AA. Aceastformuleste att nFNCcti nFND, deci

putem lua F1= Ai F2= A.

Pas inductiv. Trebuie tratate cazurile corespunztoare definiiei

constructive a luiLP.

(i)F = ( G).Presupunem c P(G) este adevrat i demonstrm c

P(F) este adevrat. Din ipoteza inductivrezultcexistformulele

G1, aflatn FNC i G2, aflatn FND, astfel nct GG1 i G G2.

Atunci, de exemplu, G G1 i, aplicnd legile lui deMorgan, gsim:

i in nm m

i,j i,ji=1 j 1 i=1 j 1

( ( L )) ( ( ( L )))

.

n ultima formulputem aplica unde este cazul legea dublei negaii

i apoi putem nlocui elementele de formaLi,jcu ji,L , obinnd astfel o

FNDpentru F. Analog, dacpornim cu G2, care este oFNDpentru G,

vom obine oFNCpentru F.


(ii) F = (G H). Presupunem c afirmaiile P(G) i P(H) sunt

adevrate i artm c P(F) este adevrat. Din faptul cP(G) este

adevratrezult c exist G1, aflatnFNC i satisfcnd G G1,astfel nct:

G1 = 11 nm

i,ji=1 j 1( ( L ))

i

Cu totul similar, pentru cP(H) este adevrat, nseamncexistH1,

aflatnFNC

i satisf

cnd HH

1:

H1= 22 nm

i, ji=1 j 1( ( L ))

i

Atunci, G H G1 H1 i este evident cultima formuleste tot o

conjuncie de disjuncii, adiceste oFNC, notatF1, pentru F. Pentru a

obine o FND, F2, pentru F, pornim de la o FND, G2, pentru G i o

FND, H2, pentru H. Atunci F = G H G2H2, de unde obinem

imediat o FND pentru F, notat F2, dac se aplic mai nti

distributivitatea generalizata conjunciei fade disjuncie i apoi,n

interiorul subformulelor, a disjunciei fade conjuncie.

(iii)F = (G H). Procedm analog ca n cazul anterior.

Teorema precedentsugereazexistena unuialgoritm recursiv

pentru obinerea simultan a unei FNC i a unei FND, pentru orice

formul propoziional. Putem folosi ns i tabelele de adevr i

modalitile de gsire a formelor normale conjunctive/disjunctive

(perfecte) descrise nCapitolul 1.



36/156


Exemplu. Gsii o formul F LP construit peste mulimea de

variabile propoziionale {A, B, C} i care s satisfac condiia: n

tabelul de adevr standard care o descrie,o schimbare i numai unan secvena produce schimbarea valorii

corespunztoare de adevrS(F). Dacncepem secvena S(F) cu 0,

atunci F este descrisde tabelul:

A B C F

S(A) S(B) S(C) S(F)0 0 0 0

0 0 1 1 *

0 1 0 1 *

0 1 1 0

1 0 0 0

1 0 1 1 *

1 1 0 1 *

1 1 1 0

Se poate construi apoi direct din tabel mcar o formul(sau dou) care

i corespunde semantic, formul ce se afl nFND (i/sau FNC). De

fapt vom folosi algoritmul de construcie a FNDP (FNCP) pentru o

funcie boolean. Conform Capitolului 1, acesta poate fi exprimat

astfel: se fixeazliniile avnd 1 n ultima coloan(cele marcate cu *

n tabel); pentru fiecare asemenea linie se construiete o conjuncie de

literali (apar toi, cu bar sau fr): dac valoarea unei variabile(atom pozitiv) este 0 n tabel, atunci variabila se trece n conjucia


respectiv negat, iar dac valoarea ei este 1, atunci ea apare

nenegat; formula final, aflat n FND(P), este disjuncia tuturor

acestor conjuncii. Prin urmare, putem pune F = (A B C) (A B C) (A B C) (A B C). Gsii, analog, o

FNC(P)

Conform teoremei anterioare, precum i datoritcomutativitii

i idempotenei disjunciei, comutativitii i idempotenei conjunciei

(repetarea unui element, fie el literal sau clauz, este nefolositoare din

punctul de vedere al (ne)satisfiabilitii unei formule), este justificat

scrierea ca mulimi a formulelor aflate n FNC. Astfel, dacF este n

FNC (Definiia 2.7), vom mai scrie F = {C1, C2, ... , Cm} (nu uitm

totui cvirgula aici provine dintr-o conjuncie), unde, pentru fiecare

i [m], vom pune }L,...,L,L{C ini,i,2i,1i . Mai mult, dac avem

FLPreprezentatca mulime (de clauze) sau ca mulime de mulimi

(de literali) i ne intereseazdoar studiul (ne)satisfiabilitii ei, putem

elimina clauzele C care conin att L ct i L , deoarece L L 1,

1 C1 i deci aceste clauze sunt tautologii (notate generic cu 1).

Tautologiile componente nu au nici o semnificaie pentru stabilirea

valorii semantice a unei formule F aflate nFNC(1C C).



37/156


5. Decidabilitate n LP

LP, cadrul formal propus (realitatea este modelat prinafirmaii, afirmaiile sunt reprezentate ca formule propoziionale),

oferca principalmetodde a rezolva problemele, testarea adevrului

(satisfiabilitii) unor formule. Din punctul de vedere al unui

informatician, trebuie ca pentru clasa de formule admis sexiste un

algoritm care, avnd la intrare orice F LP, se termincu rspunsul

DA, dacF este satisfiabil(sau valid, sau contradicie) i NU n

rest (tiind desigur cputem decide dacun anumitir de caractere este

formul sau nu). n aceast situaie se spune c problema

satisfiabilitii (pe scurt, SAT) pentru LP este rezolvabil

(decidabil). Mai mult, am vrea s gsim asemenea algoritmi pentru

carecomplexitatea timp este rezonabil.

Teorema 2.7 (decidabilitatea SAT). Satisfiabilitatea (validitatea,

nesatisfiabilitatea) formulelor calculului propoziional este decidabiln

timp exponenial.

Demonstraie. Practic, demonstraia (exceptnd complexitatea) a fostdeja fcut, chiar n mai multe moduri. Fie F LP avnd prop(F) =

{A1, A2, , An} =An. Se formeaz, de exemplu nPasul 1al unui

posibil algoritm (notat tot SAT) pentru testarea satisfiabilitii

(validitii, nesatisfiabilitii), tabela de adevr corespunztoare lui F

(Teorema de extensie, Teorema de substituie i legtura dintre


algebrele booleene LP i B stau la baza corectitudinii acestei

construcii) care are forma:

S(A1) S(A2) S(An) S(F)

0 0 0 v1

0 0 1 v2

1 1 1 vm

2n = m

Dactoi vi (i[m]) sunt egali cu 0 atunci F este contradicie, dactoi

vi sunt 1 atunci F este tautologie, iar n rest F este satisfiabil dar

nevalid. Pentru a depista acest lucru, trebuie parcurs, nPasul 2, n

cazul cel mai defavorabil, ntregul tabel, linie cu linie i prin urmare

trebuie efectuate 2n comparaii (F este construit peste n formule

atomice). Dei mai sus nu avem o explicaie formal riguroas a

faptului cSATare timp exponenial, se poate arta cproblema este

chiarNP-complet(conform [AHO]; a se urmri i comentariile care

urmeazimediat dup demonstraie).

Datorit Teoremei de extensie i Teoremei de substituie,

putem construi o tabelde adevr pentru o formulpornind nu de la

variabile, ci chiar de la anumite subformule mai complicate (pentru care

valorile posibile, finale, sunt tot 0 sau 1). Mai mult (se pot consulta

[KNU], [JUC], [LUC] i, n special, [CRO], [AHO], [COR], [BR]),trebuie cutai algoritmi rapizi (eficieni, tratabili), adic avnd


38/156



39/156

6. Formule Horn

Reamintim c o clauz Horn este o disjuncie de literali care

conine cel mult un literal pozitiv.

Definiia 2.8. OformulHorneste o formulaflatnFNC, clauzele

componente fiind (toate) clauze Horn.

Uneori, vom numi tot formulHorni o formulcare este (tare)

echivalent cu o formul de forma considerat n Definiia 2.8. Se

poate arta ([MAS1]) cexistformule propoziionale care nu sunt tare

echivalente cu nici o formulHorn, apariia a mcar doi literali pozitivi

distinci ntr-o clauzfiind decisiv. Formele posibile pentru o formul

Horn sunt (variabilele propoziionale care apar sunt elemente ale luiA):

(i) C =A1 A2 Ak, k 1, kNi

(ii) C =A1 A2 AkB, kN.

Observaie. nafarde reprezentarea ca mulimi, clauzele Horn pot fi

reprezentate subi sub aa-numitaformimplicaional. Vom distinge

cazurile (reamintim c0 i1 denotorice contradicie respectiv oricetautologie):

C = A A (nici un literal negativ, un literal pozitiv). Acest

lucru se mai poate scrie sub forma C 1 A, ceea ce se

justificprin aceea c1A 1A 0A A.

C =A1 A2 Ak(nici un literal pozitiv, mcar un

literal negativ). Vom scrie C A1A2A3Ak0

(folosim din nou definiia implicaieii faptul c0 AA).

C =A1 A2 AkB (exact un literal pozitiv,

mcar un literal negativ). Atunci CA1A2A3AkB,

direct din definiia implicaiei.

C (nici un literal negativ, nici un literal pozitiv). Din

motive tehnice vom folosi i aceast clauz vid (n

reprezentarea clauzelor cu mulimi vom folosi pentru chiar

). Prin convenie, este o clauz de orice tip (inclusiv o

clauzHorn), darnesatisfiabil.

Teorema 2.8. Satisfiabilitatea formulelor Horn este decidabiln timp

liniar.

Demonstraie. Sconsiderm algoritmul:

Algoritm Horn

Intrare: Orice formul Horn, F, reprezentat ca mulime de clauze,clauzele componente fiind clauze Horn diferite de clauza vid i scrise

sub formimplicaional.

Ieire: DA, n cazul n care formula F este satisfiabil(furnizndu-se

i o asignareScare este model pentru F) i NU n caz contrar (F nu

este satisfiabil).



40/156

Metod(de marcare):

Pasul 1. i := 0.

Pasul 2.Ct_timp ((exist n F o clauz C de forma

A1A2A3AkB, cu A1, A2, A3, ... , Akmarcaii

Bnemarcatsau de forma A1A2A3Ak0, cu A1,

A2, A3, ... , Akmarcai)i(i = 0))

execut

Pasul 3.Alegeun asemenea C ca mai sus.

Pasul 4. Dac( C = A1A2A3 Ak B )

atunci

Pasul 5.MarcheazB peste tot n F.

altfel

Pasul 6. i := 1.Sf_Dac

Sf_Ct_timp

Pasul 7. Dac( i = 0 )

atunci

Pasul 8. Scrie DA.

Pasul 9. ScrieS, cuS(A) = 1 dac i numai

dacA apare n Fi estemarcat.

altfel

Pasul 10. Scrie NU.

Sf_Dac.

Artmmai nti calgoritmulse termin pentru fiecare intrare. S

precizm c aciunea de marcare o privim n sens grafic normal,

marcajul care poate fi ataat unei variabile proziionale alegndu-sefrcriterii speciale (spresupunem cel este *, mpreuneventual cu

anumii indici prin care s se identifice n care dintre execuiile

corpului buclei s-a fcut marcarea). Iniial, toate variabilele se

presupun a fi nemarcate. DacF conine clauze de forma1B (care

seconsidera fi de fapt de formaA1A2A3AkB, cu A1,

A2, A3, ... , Ak marcai i B nemarcat), se procedeaz conform

algoritmului, adicse marcheaztoate apariiile lui B n F i se trece la

pasul urmtor. Mai departe, lafiecareexecuie acorpului buclei(Paii

3. i4.), fie se marcheazo variabilpropoziionalnou(nemarcat

nc), fie se iese din execuia buclei. Pentru cnumrul de variabile

peste care este construitformula F este finit, terminarea algoritmuluieste evident. Dacnu existdeloc clauze de tipul1B, algoritmul se

termin fr nici o execuie a corpului buclei, cu rspunsul DA

(formula este satisfiabil) i cu asignarea S, n careS(A) = 0 pentru

fiecare A (care apare n F).

Artmn continuare calgoritmul estecorect. Aceasta nseamncieirea algoritmului satisface ceea ce am dorit, adicrspunsul DA/S

corespunde faptului cformula F furnizatla intrare este satisfiabil(i

SF) iar rspunsul NU corespunde faptului cF este nesatisfiabil.

Vom separa cazurile:

Cazul a). La terminarea execuiei se obine DA i F nu conineclauze C de tipul1B. Dupcum am observat, acest lucru nseamn


41/156



42/156

tipul anterior, sau n una de acelai tip cu aceasta i care are

antecedentul marcat. Prin urmare, n orice S cu S(C) = 1,

trebuie oricum savemS(A) = 1, deci S(A) = 0 i atunci

S(B) = 1 (concecina este cB se marcheaz, deciiS(B) = 1).

Continum raionamentul cuC = A1 A2 B (douvariabile

n antecedent; ambele variabile marcate; B este, nc,

nemarcat), ajungnd din nou la concluzia cpentru fiecareS,

pentru a avea S(C) = 1, trebuie savemS(B) = 1, precum i

S(B) = 1.

Revenind, am artat ntr-adevr c pentru fiecare S astfel nct

S(F) = 1, trebuie savemS(A) = 1 pentru fiecare Amarcatde ctre

algoritm, adicpentru fiecare A care satisface i S(A) = 1 (procesul

descris mai sus se continu pentru oricte variabile prezente n

antecedent, iar numrul acestora este finit). Prin urmare, avem i

S(C) = 0, de unde rezultcS(F) = 0, ceea ce este absurd.

S artm n final calgoritmul Horn are timp de execuie liniar.

Faptul c t(n) O(f(n)), unde f(n) = an + b (a, b N*), rezult

imediat din faptul cla fiecare execuie acorpului bucleisemarcheazo nou variabil. Desigur cpentru a obine n mod real acest lucru

algoritmul trebuie detaliat, n sensul c, de exemplu, nPaiide tip3

(dealegere a unei clauze corespunztoare C), selecia variabilei de

marcat trebuie fcut prin parcurgerea de un numr fix de ori

(independentde numrul de execuii) a listei variabilelor peste care este

construitF.

Exemplu. Saplicm algoritmul de marcare urmtoarei formule Horn:

F = ( A D ) ( C A D ) ( A B ) D E.Scriem nti F ca o mulime de implicaii, obinnd

F = {D A, C A D, A B 0,1D, E 0}. nainte de

prima execuie a corpului buclei, avem i = 0 i toate variabilele sunt

nemarcate.

Prima execuie. Alegem clauza1D (de fapt, nu exist alt

posibilitate). Toate apariiile lui D semarcheazcu *1:

1*D A, C A 1*D , AB 0,1 1*D , E 0.

A doua execuie. Alegem D A (din nou, nu existdect o

unicposibilitate)i A semarcheazpeste tot, cu *2:

1*D 2*A , C 2*A 1*D , 2*A B 0,1 1*D , E 0.

A treia execuie nu mai are loc, deoarece nu mai existclauze

de tipul cerut. Cum valoarea lui i nu s-a modificat (a rmas 0),

rspunsul algoritmului este DA.

Prin urmare, F este satisfiabil i o structurS, model pentru F, este

definitprinS(A) = 1,S(B) = 0,S(C) = 0,S(D) = 1,S(E) = 0.

Am gsit prin urmare o subclasconvenabil (acest lucru este

cumva subiectiv) de formule propoziionale, si anume clasa formulelor

Horn, pentru care testarea satisfiabilitii se poate face ntr-un timp

rezonabil. Dei rezultatele teoretice generale ne spun cnu pot exista

metode sintactice mai bune dact metoda semantic sugerat deAlgoritmul SAT(dacne referim la ntregamulimeLP), existena,



43/156

dovedit de acum, a unor algoritmi care s nu fac apel explicit la

semantic, pare deja a fi un ctig.

7. Rezoluie n LP

Fra restrnge generalitatea, putem presupune c lucrm cu

formule din LP aflate n FNC, reprezentate sub form de mulimi

(finite) de clauze, iar clauzele ca mulimi (finite) de literali.

Definiia 2.9 (rezolvent). Fie clauzele C1, C2 , R. Spunem cR este

rezolventul lui C1, C2 (sau c C1, C2se rezolv n R, sau cR se

obine prin rezoluie ntr-un pas din C1, C2), pe scurt,

R = ResL(C1, C2), dac i numai dacexistun literal L C1 astfel

nct L C2i R = (C1\ {L})U(C2\ {L }).

Vom putea reprezenta acest lucrui grafic, prinarborele de rezoluie:

Vom renuna la scrierea explicita lui L sau/i L n momentul n care

nu existcofuzii.

Observaie. Rezolventul a dou clauze este tot o clauz. Mai mult,

rezolventul a douclauze Horn este tot o clauzHorn. Clauza vid()

C1 C2

R

L L

poate fi obinutprin rezoluie din douclauze de forma C1= {A} i

C2 = {A}. n definiia anterioar putem considera c C1 i C2sunt

diferite ntre ele. Dacele ar coincide, atunci C1 = C2=...L L 1,adicacele clauze sunt tautologii, detectabile sintactic (n acest caz nu

ne mai intereseazalte metode formale de studiere a satisfiabilitii lor).

Exemplu.

Fie formula F = {{A, E,B}, {A, B, C}, {A, D}, {A,D,E}}. S

gsim civa dintre rezolvenii care se pot obine (succesiv) pornind de

cele cele patru clauze care compun F, notate respectiv C1, C2, C3, C4:

Acetia au fost gsii apelnd de fiecare datla C1. i C2poate fi sursa

unui ntreg lan de asemenea rezolveni:

C1 C2 C1 C2 C1 C4

A A B B A A

{A,B,A,D}

E E

{E,B, B, C} {A, E,A, C} {E,B,D,E}

C1 C4



44/156

Muli dintre aceti rezolveni primari nu sunt interesani, fiind

tautologii(datoritfaptului cacele clauze alese spre rezolvare conin

mai mult de un literal de tipul L/L). Procesul poate nscontinua cu

gsirea de noi rezolveni folosindu-i i pe cei obinui din clauzele

iniiale (cum este cazuli mai sus).a.m.d.

n acest moment putem sne punem cel puin dountrebri:

Existcazuri n care procesul anterior (de aflare succesivde

rezolveni noi) nu se termin?

n caz de rspuns negativ i presupunnd c exist o legtur

ntre acest proces sintactic (de obinere de rezolveni) i

satisfiabilitate, se pot obine algoritmi (sintactici, eventual

performani) de testare a satisfiabilitii unor formule?

Rspunsul l vom da n cele ce urmeaz.

C2 C3

A A

{B, C, D} C1

B B

{C, D, A, E}

Teorema 2.9 (lema rezoluiei). Fie oricare formulF LP(aflatn

FNCi reprezentatca mulime de clauze)i R un rezolvent pentru C1,

C2F. Atunci F este tare echivalentcu FU{R}.Demonstraie.

. DacSsatisface FU{R} atunci desigur cSsatisface F, conform

definiiei (o structur satisface o mulime de formule dac satisface

fiecare element din mulime).

. Spresupunem cS

F , adicS

C, pentru fiecare CF. Fie

C1,C2F i R un rezolvent al lor, R = (C1\ {L}) U (C2\ { L}), unde

L C1, L C2.

Cazul 1. S(L) = 1. Atunci S L. Dar tim c S C2. Rezult c

SC2 \ { L}, de undeS(R) = 1.

Cazul 2.S(L) = 0. Analog, artndu-se cSC1 \ {L}.

n teorema anterioar am fi putut considera, n loc de F, o mulime

oarecare de clauze, chiar infinit.

Definiia 2.10. Fie F o mulime oarecare de clauze din LP i C o

clauz. Spunem clista C1, C2, , Cmeste odemonstraie prin

rezoluie (n mai muli pai) a lui C pornind cu F dac sunt

satisfcute condiiile:

(i) Pentru fiecare i[m], fie CiF, fie Cieste obinut prin rezoluie

ntr-un pas din Cj, Ck, cu j, k < i.

(ii) C = Cm.



45/156

n condiiile definiiei, se mai spune cC este demonstrabil

prin rezoluie(pornind cu F, sau, n ipotezele date de F). Mai mult,pentru a spune acest lucru, este suficient ca F sfieinserat(prezent)

ntr-o demonstraie i nu s fie neaprat ultimul element al acesteia.

Intuitiv, o demonstraie prin rezoluie n mai muli pai nseamn o

succesiune finitde rezoluii ntr-un pas, care poate fi reprezentat i

grafic, printr-un arbore (a se vedea exemplul care urmeaz), sau chiar

ca un graf oarecare (dacnu folosim noduri diferite pentru apariiile

distincte ale unei aceleiai clauze). n particular, dac C este clauza

vid, atunci demonstraia respectiv se numete i respingere.

Numrul de paidintr-o demonstraie este dat de numrul de clauze

obinute prin rezoluie ntr-un pas(din clauze anterioare). Acesta poate

fi considerat ca fiind o msura mrimii (lungimii) demonstraiei. Oalt msurpentru o demonstraie reprezentat ca text poate fi chiar

lungimea listei (numrul total de clauze, sau chiar numrul total de

clauze distincte). Dacreprezentm o demonstraie ca un arbore, putem

folosi i msuri specifice, cum ar fiadncimeaarborelui,numrul de

nivele ([IVA]), etc. Convenim s eliminm din orice demonstraie

rezolvenii care conin att L ctiL, aceste clauze fiind tautologiii

deci neinteresante din punctul de vedere al studiului satisfiabilitii

unei formule aflate nFNC.

Exemplu. Fie F = {{A, B, C}, {A}, {A, B, C}, {A, B}}. O

respingere poate fi descrisprin arborele:

Definiia 2.11 (mulimea rezolvenilor unei mulimi de clauze). Fie Fo mulime de clauze dinLP(nu neaprat finit). Notm succesiv:

Res(F) = FU{R | existC1, C2 F astfel nct R = Res(C1, C2)}.

Res(n+1)(F) = Res(Res(n)(F)), nN. Prin Res(0)(F) vom nelege Fi

atunci vom putea punei Res(1)(F) = Res(F).

Res*(F) = (n)ResnN

(F).

Res(n)(F) se va numimulimea rezolvenilor lui F obinui n cel mult

n pai, iar Res*(F)mulimea (tuturor) rezolvenilor lui F.

Observaie. Direct din definiie rezultc:

F = Res(0)(F)Res(1)(F)...Res(n)(F)...Res*(F).

{A, B,C} {A, B, C}

C C

{A, B} {A,B}

B B

{A} {A}

A A



46/156

Putem da atuncii odefiniie structurala lui Res*(F). Vom nota astfel

cu Resc mulimea definitprin:

Baza. F Resc.Pas constructiv: Dac C1, C2 Resc i C = Res(C1, C2), atunci

CResc.

Rmne sartm ccele dou definiii introduc aceeai mulime.

Teorema 2.10. Pentru fiecare FLP, avem Res*(F) = Resc.

Demonstraie. Artm egalitatea prin dublincluziune.

. Demonstrm prin inducie matematic adevrul afirmaiei din

metalimbaj (n)P(n), undeP(n): Res(n)(F)Resc.

Baza. n = 0. Trebuie artat c F = Res(0)(F) Resc, ceea ce este

imediat din definiia lui Resc.

Pas inductiv. Presupunem c Res(n)(F) Resc i artm c

Res(n+1)(F)Resc, ceea ce este din nou imediat din definiia lui Resci

Definiia 2.11. n sfrit, avem Res*(F) Resc, direct dinDefiniia

2.11 i observaia care urmeazacesteia.

. Procedm prin inducie structural, mai exact artm cafirmaia

din metalimbaj (CResc)(CRes*(F)) este adevrat.

Baza. C F. Adevrat, deoarece F = Res(0)(F) Res*(F).

Pas inductiv. Fie C = Res(C1, C2), C1, C2Resc i resupunem cC1,

C2Res*(F). Sartm cC Res*(F). Acest fapt urmeazimediat,

conformDefiniiei 2.11.

De acum nainte vom folosi ambele notaii pentru mulimea

rezolvenilor unei mulimi de clauze. i n Teorema 10 se putea

considera cF reprezinto mulime oarecare de clauze.

Teorema 2.11. Fie F o mulime de clauze dinLP(nu neaprat finit).

O clauzCLPse poate demonstra prin rezoluie pornind cu clauzele

lui F dac i numai dacexistkN, asfel nct CRes(k)(F).

Demonstraie. Fie Fi C fixate ca n enun.

. S presupunem c exist o demonstraie prin rezoluie a lui C

pornind cu F, C1, C2, ... , Cm= C. Este ndeplinitcondiia (i) din

Definiia 2.10 i atunci nseamn c pentru fiecare i [m], avem

Ci Resc, care coincide cu Res*(F), conform Teoremei 2.10. Prin

urmare, conform definiiei lui Res*(F) exist k N, asfel nct

CRes(k)

(F).

. Spresupunem cexistkN, asfel nct CRes(k)(F) (pek l

considerm a fi cel mai mic numr natural care satisface condiia).

Conform Definiiei 2.11, avem Res(j)(F) = Res(Res(j-1)(F)) =

Res(j-1)(F) U {R | exist C1, C2 Res(j-1)(F) astfel nct

R = Res(C1, C2)}, pentru fiecare j [k].Putem conveni chiar ca n a



47/156

doua mulime din reuniunea de mai sus snu punem dect rezolvenii

noi, care nu apar n Res(j-1)(F). Atunci C apare efectiv n Res(k)(F) dar

nui n Res(k-1)

(F). Dack = 0, am terminat (CFi lista formatdoardinC constituie o demonstraie prin rezoluie a lui C). n caz contrar,

mai nticonstruim algoritmic un graf neorientatn felul urmtor: la

Pasul 1punem ca noduri elementele din Res(k)(F), care nu sunt i n

Res(k-1)(F); laPasul 2 punem nodurile din Res(k-1)(F) care nu sunt n

Res(k-2)(F), precum i muchiile corespunztoare care unesc nodurile

puse deja n graf, conform rezoluiilor ntr-un pas din care ele provin,

. a. m. d. n cel mult k + 1 pai, vom plasa n graf i elementele

(folosite) ale lui F, precum i toate muchiile corespunztoare

rezoluiilor ntr-un pas cu ajutorul crora se construiete Res(k)(F).

Considerm acumsubgraful g

1. Fundamentele Logice Ale Informaticii

Documents

Transcript of 1. Fundamentele Logice Ale Informaticii

Referat Didactica Informaticii

bazele informaticii-c++

Fundamentele Marketingului

Fundamentele psihologiei

CAPITOLUL 2. FUNCŢII LOGICE - eprofu · 2017. 8. 12. · CAPITOLUL 2. FUNCŢII LOGICE 32 CAPITOLUL 2. FUNCŢII LOGICE 2.1 AXIOMELE ŞI TEOREMELE ALGEBREI LOGICE Algebra logică are

jocuri logice

Fundamentele Macroeconomiei

Curs Bazele Informaticii

Metodica predarii informaticii

Curs Metodica Predarii Informaticii

Bazele Informaticii Curs

Indrumar laborator Bazele Informaticii EconomiceIndrumar Laborator Bazele Informaticii Economice - V2008

127571728 Metodica Predarii Informaticii

Gheorghe Enescu - Fundamentele logice ale gandirii

Bazele informaticii subiecte.pdf

Curs ID Bazele Informaticii

CERCETĂRI LOGICE II/2 · 2014. 5. 21. · Principalele opere: Cercetări logice(1900–1901; trad. rom. Cercetări logice I, Humanitas, 2007, şi Cercetări logice II/1, Humanitas,

Aplicatiile informaticii

Fundamentele Informaticii - Manual -Sem II

FUNDAMENTELE PEDAGOGIEI