Logică matematică și computațională

CU1

X-multime nevida

P(X)- multime partilor lui X

1) ,) asociativitate 2) ,) comutativitate

3) A A=A,A)A=A idempotenta

4) A (A)B)=A, A)(A B)=A absortia

5) A (B)C)=(A B))(A C) distributivitatea

A)(B C)=(A)B) (A)C)

6) A =A, A) = ;

7) A =A, A) = , A)X=A, A X=X

Algebra Boole: Structrui de baza ale cursurilor

Def. O algebra boole este o structura algebrica de forma (B,÷,ø,>,0,1) in care ÷, ø operartii binare ,> - operatie unara, 0,1 constante => a.i incat urmatoarele identitati sunt adevarate in B (÷,ø  reuniune si intersectie )

1) ÷, ø asociative 2) ÷, ø comutative 3) XøX=X; X÷X=X;

4) X÷(XøY)=X Xø(X÷Y)=X 5) ÷,ø distributive 6) 0øX=0 0÷X=X

7) 1øX=X 1÷X=1 8) Xø =0 X÷ =1

Ex1. Primul Exemplu de algebra boole este ( P(x), ,),>, ,X)

Ex2. L2=(0,1)

Ex 3. Fie B o algebra boole , X- multimea `

BX-def-f:X->B Fie f,g ap. BX

Definim: f÷g:X->B (f÷g)(x)=f(x)÷g(x), ( ) x X

føg:X->B (føg)(x)=f(x)øg(x), ( ) x X

:X->B (x)= , ( ) x X

0:X->B 0(x)=0, ( ) x X

1:X->B 1(x)=1, ( ) x X

Ex..4 Algebra Boole putere

Fie B- o algebra Boole oarecare at. Consideram Bn=BxBx&&xB( de n ori ) = {(x1,&.,xn) , n>=1 ap. N| xi B,i=1..n} Pe multimea Bn definim ÷,ø,>

Fie x,y Bn, x=(x1,&..,xn), y=(y1,..........y2)

x÷y=(x1÷y1,...,xn÷yn),xøy=(x1øy1,&,xnøyn), =( 1,...., n)

Operatiile pe componente sunt facute in algebra Boole B

Not 0n=(0,&,0)(de n ori) (Bn,÷,ø,0n,1n)

1n=(1,&,1)(de n ori)

Ex.5 Algebra Boole a fuunctiilor boolene in n variabile

Not BFn(B) Bn Àin:Bn->B Àin =proiectia a i-a;

Àin(x1,&,xn)=xi i=1..n, n proiectii

Multimea functiilor booleene BFn(B) se introduce prin urmatoarele conditii

I proiectiile Àin sunt functii booleene II 0n,1n functii booleene

III Dc. f ,g BFn(x)=> f÷g, føg BFn(x) IV f BFn(x) => BFn(x)

Obs. Avem de aface cu o definitie prin inductie, consta in momentul 0 al inductile , care este asigurat de conditiile I, II

Tercerea de la k la k+1 este asigurata de cond III, IV. Se mai numeste si inductie structurala. BFn(B) Bn-inchisa la operatiile Booleene din Bn

-contine functia 0n ,1n

(BFn(B),÷,ø,>,0n,1n)  algebra Boole a functiilor Booleene in n variabile

BFn(b) subalgebra a lui Bn(inchisa la operatii si la constante )

Bn B=x÷y Bn xøy Bn Bn

(Ai)i I-familia Ai, cand i parcurge multimea I

i IàAi

={x|ex. i I,x Ai} x óex. i I,x Ai

={x|or. i I,x Ai} x ó or i I,x Ai

Curs 4.Latici

sup(x,y)=m <=> (x,ydm) si (x,ydm => mdm); inf(x,y)=n <=>(ndx,y) si (ndx,y => ndn)

Def latice:

1)o multime(L,d) ai or.x,yÎL ex. sup(x,y) si inf(x,y);

2)o structura algebrica (L, Ú,Ù) ai:

a) Ú, Ù asoc; b) Ú, Ùcomut; c)xÙx=x; xÚx=x idempotenta;

d)xÙ(xÚy)=x; xÚ (xÙy)=x; absorbtia;

Prop1:def 1 <=>def 2

dem: 1=>2 Pp ca or. x,yÎL,ex. sup(x,y) si inf(x,y).Definim xÚy=sup(x,y) si xÙy=inf(x,y). Arat ca cele doua operatii verifica axiomele a)-d) Dem asoc. Ú

sup(x,sup(y,z))(not. cu m)=sup(sup(x,y),z)=sup(x,y,z)

a)x<=m;b)y<=m;c)z<=m;d)Daca x<=a, y<=a,z<=a=>m<=a =>de demonstrat

b) y<=sup(y,z)<=sup(x,sup(y,z))=m;c)z<=sup(y,z)<=sup(x,sup(y,z))=m;

d)x<=a,y<=a,z<=a=>sup(y,z)<=a=>sup(x,sup(y,z))<=a =>QED

Restul de dem asem.

2=>1 Pp ca ex. Ú,Ù care verifica a)-d).

Se cere sa definim pe L o rel d de ordine partiala a.i. ex. sup(x,y),inf(x,y), or. x,y ap. L

Definim xdy <=>xÙy=x<=>xÚy=y si inf(x,y)=xÙy, sup(x,y)= xÚy Dem refl.,simetria, tranz , si dem ca inf(x,y)=xÙy, sup(x,y)= xÚy, verificand definitia. Obs.:Def1 proneste de la o rel de ordine si def2 este o def ecuationala.

Latice distributiva

D1: (xÙy) Úz=(xÚz)Ù(yÚz) D2: duala (xÚy)Ùz=(xÙz)Ú(yÙz)

Spunem ca m este cel mai mare dintr-o latice daca xdm, "xÎL(daca m exista,e unic).Il notam cu 1. Pe cel mai mic il notam cu 0.

0dxd1 si 0Ùx=0;0Úx=x;1Ùx=x;1Úx=1;, or.x ap. L