logica matematica cursuri - prof. Ioana Leustean

Logica Matematica si ComputationalaMULTIMI. RELATII. FUNCTII

Ioana LeusteanFMI, UB

Operatii cu multimi

A, B, C , T multimi

A, B TA B = {x T |x A sau x B}A B = {x T |x A si x B}A = {x T |x 6 A}

P(T ) = {A|A T} A B = {(a, b)|a A si b B}

Exemplu. P() = {}, P({}) = {, {}},P({, {}}) = {, {}, {, {}}}, ...Exercitiu. A, B, C TA (B C ) = (A B) (A C )A (B C ) = (A B) (A C )

Multimi. Relatii n-are

n numar natural, n 1A1, . . ., An T multimi ni=1 Ai = {x T |ex . i {1, . . . , n} x Ai} ni=1 Ai = {x T |x Ai or . i {1, . . . , n}} ni=1 Ai = {(x1, . . . , xn)| xi Ai or . i {1, . . . , n}}

Notatie. An = A A n

Definitie

O relatie ntre A1, . . ., An este o submultime a produsuluicartezian

ni=1 Ai . O relatie n-ara pe A este o submultime a lui A

n.

Multimi. Relatii n-are

Exemple

| N N| = {(k , n)| ex . m N a.. mk = n}

Operatii cu relatiii

A, B, C multimi

relatia inversa:daca R A B atunci R1 B A siR1 = {(b, a)|(a, b) R}

compunerea relatiilor:daca R A B si Q B C atunci R Q A C siR Q = {(a, c)|ex . b B (a, b) R si (b, c) Q}

diagonala A = {(a, a)|a A}

Exercitiu(1) Compunerea relatiilor este asociativa.(2) Daca R A B atunci A R = R si R B = R.

Relatiii

A, B multimiR A B (relatie ntre A si B)

Definitie

Relatia R se numeste:

totala: or. a A ex. b B astfel ncat (a, b) R surjectiva : or. b B ex. a A astfel ncat (a, b) R injectiva: or. a1, a2 A or. b B

(a1, b) R si (a2, b) R implica a1 = a2 functionala: or. a A or. b1, b2 B

(a, b1) R si (a, b2) R implica b1 = b2

Functii.

A, B multimi

O functie de la A la B este o relatie totala si functionala, deciR A B este functie dacapentru orice a A exista un unic b B cu (a, b) R.Notatia f : A B are urmatoarea semnificatie:f (a) este unicul element din B care este n relatie cu a.

Astfel functia R A B va fi notata prin fR : A B, unde

b = fR(a) ddaca (a, b) R.

Invers, relatia asociata lui f : A B este Rf = {(a, f (a))|a A} .Vom nota prin 1A : A A functia f (a) = a oricare a A.Evident, R1A = A.

Compunerea functiilor

f : A B si g : B C functiiDefinim g f : A C unde (g f )(a) = g(f (a)).Exercitiu. Rgf = Rf Rg .Spunem ca o functie f : A B este inversabila daca existag : B A astfel ncat g f = 1A si f g = 1B .O bijectie este o functie injectiva si surjectiva.

Exercitiu. O functie este bijectiva ddaca este inversabila.

Functia caracteristica

T multime, A TFunctia caracteristica a lui A n raport cu T este

A : T {0, 1}, A(x) ={

1, x A0, x 6 A

Proprietati

Daca A, B T si x T atunci(1) AB(x) = min {A(x), B(x) } = A(x)B(x)(2) AB(x) = max { A(x),B(x) } =A(x)+B(x)A(x)B(x)(3) A(x) = 1A(x)

Functia caracteristica

T multime, {0, 1}T = {f : T {0, 1}|f funtie }

Propozitie

Exista o bijectie ntre P(T ) si {0, 1}T .Dem. Functiile care stabilesc bijectia sunt

F : P(T ) {0, 1}T , F (A) =AG : {0, 1}T P(T ), G (f ) = {x T |f (x) = 1}Se arata ca F (G (f )) = f si ca G (F (A)) = Aoricare A T si f : T {0, 1}.

Logica Matematica si ComputationalaMULTIMI. RELATII.

II


Principiul Inductiei

Principiul Inductiei

Daca S N astfel ncat:(i) 0 S ,(ii) or. n N (n S n + 1 S),atunci S = N.

Dem. Fie S N a.. (i) si (ii) sunt adevarate. Presupunem caS 6= N, deci exista n0 N \ S . Din (i) rezulta ca n0 6= 0. Din (ii)rezulta ca 1, . . . , n0 1 S , deci n0 S . Am obtinut ocontradictie, deci S = N.

Multimi numarabile

O multime A este numarabila daca exista f : N A functiebijectiva si se numeste cel mult numarabila daca este finita saunumarabila.

Exercitii(1) O reuniune finita de multimi numarabile este numarabila.

(2) O reuniune numarabila de multimi numarabile este numarabila.

(3) Q este numarabila.

Principiul Diagonalizarii


Fie A o multime si R A A o relatie binara pe A. Pentru oricea A definim Ra = {x A | (a, x) R}. FieDR = {x A | (x , x) 6 R} diagonala relatiei R. Atunci DR 6= Rapentru orice a A.

Dem. Presupunem ca exista a A astfel ncat DR = Ra.Sunt posibile doua cazuri: a DR sau a 6 DR .(1) a DR (a, a) 6 R a 6 Ra = DR ,(2) a 6 DR (a, a) R a Da = DR .In ambele cazuri ajungem la o contradictie,deci DR 6= Ra oricare a A.


Propozitie. P(N) nu este numarabila.Dem. Presupunem ca P(N) este numarabila, deci exista o bijectieF : N P(N). DefinimR = {(n, k) N N | k F (n)} N N.Daca n N atunciRn = {k N | (n, k) R} = {k N | k F (n)} = F (n).Principiul diagonalizarii implica DR 6= F (n) pentru orice n N.Dar DR N, deci DR P(N). Deoarece F este bijectiva, rezultaca exista un n0 N astfel ncat F (n0) = DR .Am obtinut o contradictie, deci P(N) nu este numarabila.Observatii. (1) Exista o functie bijectiva ntre P(N) si 2N,unde 2N = {f : N {0, 1} | f functie}.(2) Exista o functie bijectiva ntre 2N si R.In consecinta 2N si R nu sunt numarabile.

Familii de elemente

I , A multimi

O familie de elemente din A indexata de I este o functie f : I A.Notam cu {ai}iI familia f : I A, f (i) = ai or. i I . Vom scrie{ai}i atunci cand I poate fi dedus din context.Daca I = atunci {ai}i este familia vida .Fie {Ai}iI si {Bi}iI familii de submultimi ale unei multimi T .Definim

iI Ai = {x T | ex . i I a.. x Ai}iI Ai = {x T | x Ai or . i I}

Exercitiu.

iI Ai =

iI Ai

Daca I = atunci i Ai = , i Ai = T .

Produsul cartezian

I multime, {Ai}iI familie de multimi indexata de I .Vom nota prin (xi )i o familie de elemente a multimii

i Ai cu

proprietatea ca xi Ai or. i I .Definim

iI Ai = {f : I

i Ai |f (i) Ai or . i I}

= {(xi )i |xi Ai or . i I}.

Exercitiu. Fie I , J multimi(

iI Ai ) (

jJ Bj) =

(i ,j)IJ(Ai Bj)(

iI Ai ) (

jJ Bj) =

(i ,j)IJ(Ai Bj)

Daca I = atunci i Ai = {} = {} este singleton si contineunica functie de la f : .

Operatori de nchidere

T multime

Un operator de nchidere pe T este o functie C : P(T ) P(T )care verifica urmatoarele proprietati oricare A, B T :(I1) A C(A),(I2) A B implica C(A) C(B),(I3) C(C(A)) = C(A).

Exercitiu. Fie X0 T o submultime fixata. AtunciC : P(T ) P(T ) definit prin C(A) = A X0 or. A Teste operator de nchidere.

Operatori de nchidere

Exemplu.

Fie Var o multime de variabile si Form multimea propozitiilor carese pot construi folosind variabile din Var .

Pentru Form definimC() = multimea tuturor formulelor care sunt consecinte ale lui .Functia C : P(Form) P(Form) este un operator de nchidere.

Logica Matematica si ComputationalaRELATII BINARE


Relatii binare

A multime, R A ARelatia binara R se numeste:

reflexiva: (x , x) R or. x A simetrica: (x , y) R implica (y , x) R or. x , y A antisimetrica: (x , y) R si (y , x) R implica x = y

or. x , y A tranzitiva: (x , y) R si (y , z) R implica (x , z) R

or. x , y , z A relatie de preordine: reflexiva, tranzitiva relatie de ordine: reflexiva, antisimetrica, tranzitiva relatie de echivalenta: reflexiva, simetrica, tranzitiva

Relatii binare

Daca A multime si R A A definim:R(R) = R AS(R) = R R1T (R) = n1 Rn, unde Rn = R R

n

pt. n 1, R0 = A

Propozitie

(1) R(R) este reflexiva, S(R) este simetrica, T (R) este tranzitiva.(2) Daca Q A A este reflexiva (simetrica, tranzitiva) si R Q

atunci R(R) Q (S(R) Q, T (R) Q).

Propozitie

R, S, T : P(A A) P(A A) sunt operatori de nchidere.

Relatii binare

Observatie

Fie N multimea numerelor naturale siR = | (relatia de divizibilitate). Atunci S(T (R)) 6= T (S(R)).

Daca A multime si R A A definim E(R) = T (S(R(R))).

Propozitie

(1) E(R) este relatie de echivalenta oricare R A A.(2) Daca Q A A este relatie de echivalenta si

R Q atunci E(R) Q .

Propozitie

E : P(A A) P(A A) este operator de nchidere.

Relatii de echivalenta

Exemple:

Fie k 2 si N N(n1, n2) ddaca ex. x1, x2 0, ex. 0 r < k a..n1 = kx1 + r si n2 = kx2 + r .

Fie f : A B o functie si ker f A Aker f = {(a1, a2) A A | f (a1) = f (a2)}

(X ,E ) un graf neorientat (E X X ), X X(x , y) ddaca x = y sau exista un drum de la x la y .

Fie Var o multime de variabile si Form multimea formulelorcalculului propozitional clasic care se pot construi folosindvariabilele din Var . Definim Form Form prin(,) ddaca formula ( ) ( ) este teorema.

Relatii de echivalenta

Fie A o multime si A A o relatie de echivalenta.Vom nota prin x y faptul ca (x , y) .Pentru orice x A definim x = {y A|x y}

(clasa de echivalenta a lui x).

Un sistem de reprezentanti pentru este o submultime X Acu proprietatea ca oricare a A exista un unic x X astfel ncata x .

Propozitie

Au loc urmatoarele proprietati:(1) x = y x y(2) x y = x 6 y(3) A =

{x |x X} oricare ar fi X A un sistem dereprezentanti pentru .

Partitii

A multime

O partitie a lui A este o familie {Ai}iI de submultimi nevide alelui A care verifica proprietatile:(p1) Ai Aj = oricare i 6= j ,(p2) A =

iI Ai .

Propozitie

(1)Daca {Ai}iI este o partitie a lui A atunci relatiax y ex i I astfel ncat x , y Ai

este relatie de echivalenta pe A.(2) Daca A A este relatie de echivalenta si X A este unsistem de reprezentanti, atunci {x |x X} este o partitie a lui A.(3) Exista o bijectie ntre multimea relatiilor de echivalenta pe A simultimea partitiilor lui A.

Dem. exercitiu

Multimea cat

A multime, A A relatie de echivalenta pe ADefinim A/ = {x |x A} (multimea claselor de echivalenta).Definim p : A A/, p(x) = x or. x A (surjectia canonica).Se observa ca ker p =.

Proprietatea de universalitate a multimii cat

Fie B o multime sif : A B o functie a.. ker f .Atunci exista o unica functief : A/ B a..f (x) = f (x) or. x A.

Ap //

f

A/

f}}B

Dem. exercitiu

Cardinali

Doua multimi A si B sunt echipotente daca exista o functiebijectiva f : A B. In acest caz scriem A ' B.Propozitie. Urmatoarele proprietati sunt adevarate:(i) A ' A,(ii) A ' B implica B ' A,(iii) A ' B si B ' C implica A ' C .Relatia de echipotenta este o relatie de echivalenta. Pentru omultime A definim cardinalul lui A ca fiind |A| = {B | A ' B}.Doua multimi finite sunt echipotente daca si numai daca au acelasinumar de elemente. Cardinalul unei multimi finite este numarul deelemente.

Exista multimi infinite care nu sunt echipotente: N 6' 2N.|N| = 0 (aleph-zero) ,20 = |2N| = |R| = c (puterea continuului)

Monoidul cuvintelor

Un alfabet este o multime de simboluri.Un cuvnt este un sir finit de simboluri din alfabet.

Fie A un alfabet. Definim A+ = {a1 . . . an | n 1, a1, . . . , an A}si A = A+ {} unde este cuvntul vid.Operatia de concatenare : A A A se defineste prin

(a1 . . . an) (b1 . . . bk) = a1 . . . anb1 . . . bk(A, , ) este un monoid si se numestemonoidul cuvintelor peste alfabetul A.

Pentru doua cuvinte w , w A definimw w daca si numai daca au acelasi numar de litere.Exercitiu. este relatie de echivalenta pe A si A/ ' N.

Logica Matematica si ComputationalaRELATII BINARE


Relatii binare

A multime, R A ARelatia binara R se numeste:

reflexiva: (x , x) R or. x A simetrica: (x , y) R implica (y , x) R or. x , y A antisimetrica: (x , y) R si (y , x) R implica x = y

or. x , y A tranzitiva: (x , y) R si (y , z) R implica (x , z) R

or. x , y , z A relatie de preordine: reflexiva, tranzitiva relatie de ordine: reflexiva, antisimetrica, tranzitiva relatie de echivalenta: reflexiva, simetrica, tranzitiva

Relatii binare

Fie A multime si R A A o relatie de preordine. Definimx y ddaca (x , y) R si (y , x) R.Propozitie. este relatie de echivalenta pe A.Dem. exercitiu

Pe A/ definim x y (x , y) R.Lema. este bine definita, adicax x1, y y1 si (x , y) R implica (x1, y1) R.Dem. exercitiu

Propozitie. este relatie de ordine pe A/ .Dem. exercitiu

Relatii binare

Exemple. Dezvoltati constructia anterioara pentru:

A = Z (N \ {0})R = {((z1, n1), (z2, n2)) A A|z1 n2 z2 n1}Aratati ca A/' Q.

A = NN = {f : N N | f functie}Fie f , g A. Spunem ca f O(g) dacaex. c > 0 n R si n0 N a.. f (n) cg(n) or. n n0.R = {(f , g) A A|f O(g)} este relatie de preordine.f g f O(g) si g O(f ) este relatie de echivalentaPentru f A clasa de echivalenta a lui f se noteaza (f ) sise numeste rata de crestere (rate of growth) a functiei f .

Relatii binare

Daca A si B sunt multimi, definimA B ddaca ex. f : A B functie injectiva.Relatia este preordine. DefinimA B ddaca A B si B A.Relatia este o relatie de echivalenta.Teorema Cantor-Scroder-Bernstein.Daca exista doua functii injective f : A B si g : B Aatunci A ' B.Relatia de ordine pe cardinali este definita prin:

|A| |B| ddaca A B ddaca ex. f : A B functie injectiva.

UserCross-Out

UserCross-Out

UserCross-Out

UserCross-Out

Logica Matematica si ComputationalaMULTIMI PARTIAL ORDONATE

LATICI


Multimi partial ordonate

O multime partial ordonata (mpo) este o pereche (A,R), unde Aeste o multime si R este o relatie de ordine pe A.

Exemple.

(P(T ),) unde T este o multime, (N,), (N, |) cu | relatia de divizibilitate, (Pf (A,B),) undeA, B sunt multimi,Pf (A,B) = {f : A B|f functie partiala},f g = dom(f ) dom(g) si f (a) = g(a) or. a dom(f )Relatiile de ordine sunt uzual notate cu .Daca (A,) este mpo si :=1 atunci(A,) este mpo.

Multimi total ordonate

Fie (A,) mpo. Doua elemente a1, a2 A se numesccomparabile daca a1 a2 sau a2 a1.Exemplu. In (N, |) elementele 2 si 4 sunt comparabile, darelementele 3 si 7 nu sunt comparabile.

O relatie de ordine partiala se numeste totala (liniara) dacaoricare doua elemente sunt comparabile. O multime totalordonata este o pereche (A,) unde A este o multime si este orelatie de ordine totala pe A. Pentru multimile total ordonate estefolosita si denumirea de lant.

Exemplu. (LR,lex) este lant, unde LR este multimea cuvintelordin DEX, iar lex este relatia de ordine lexicografica.

Produsul cartezian de lanturi

Fie (A1,1), (A2,2) lanturi.Pe A1 A2 definim relatia de ordine pe componente(x1, x2) (y1, y2) x1 1 y1 si x2 2 y2.(A1 A2,) este mpo.Daca |A1|, |A2| 2 atunci (A1 A2,) nu e lant.

Exemplu. In R R elementele (2, 3) si (4, 1) nu sunt comparabile.Pe A1 A2 definim relatia de ordine lexicografica(x1, x2) lex (y1, y2) (x1 1 y1 si x1 6= y1) sau

(x1 = y1 si x2 2 y2).(A1 A2,) este lant.

Exercitiu. Definiti relatia de ordine lexicografica pe produsulcartezian a n lanturi (A1,1), , (An,n).

Elemente minimale si maximale

Fie (A,) mpo. Un element e A se numesteelement minimal daca (a e a = e);prim element (minim) daca e a or a A;element maximal daca (e a a = e);ultim element (maxim) daca a e or a A.

Exemplu. In mpo ({2, 4, 5, 10, 12, 20, 25}, |), elementele minimalesunt 2 si 5, iar elementele maximale sunt 12, 20, 25.

Orice minim (maxim) este element minimal (maximal).Invers nu este adevarat.

Diagrame Hasse

x y este reprezentat prin y

x

segment crescator

Exemplu. ({2, 4, 5, 10, 12, 20, 25}, |) este reprezentata prin12 20

4 10 25

2 5

Sortarea topologica

Este folosita n probleme de planificare. Presupunem ca un projecteste format din mai multe procese care se conditioneaza intre ele:procesul p nu poate ncepe decat dupa terminarea procesului q.Multimea proceselor devine astfel multime partial ordonata (P,).Se pune problema gasirii unei secvente de executie a proceselor.

O relatie de ordine totala / P P este compatibila cu relatia deordine partiala daca x y x / y oricare x , y P.Determinarea unei relatii de ordine totale compatibile cu o relatiede ordine partiala data se numeste sortare topologica.

Algoritm de sortare topologica

Intrare: (P,) mpo, n = |P| k := 1

while P 6= {pk := un element minimal al lui P;

P := P \ {pi};k := k + 1}Iesire: p1 / / pn este o ordonare totala compatibila

Sortare topologica

12 20

4 10 25

2 5x1 := 2

12 20

4 10 25

5x2 := 5

Sortare topologica

12 20

4 10 25x3 := 25

12 20

4 10x4 := 4

...

2 / 5 / 25 / 4 / 10 / 12 / 20Solutia nu este unica.

Multimi bine ordonate

O mpo (A,) este bine ordonata daca orice submultime nevida asa are prim element.

Observatie. Orice multime bine ordonata este lant.

Principiul Bunei Ordonari. N este bine ordonata (fata de relatia deordine uzuala).

Demonstratii folosind PBO

Vrem sa dem P(n). Presupunem C := {n|P(n) este falsa} estenevida. Conform PBO, multimea C are un prim element n0. Dacase obtine o contradictie, atunci C este vida, deci P(n) esteadevarata oricare n N.Exercitiu. Aratati ca daca n 8 n N atunci n poate fi scris casuma dintre un multiplu de 3 si un multiplu de 5.

PBO PI

Principiul Inductiei. Daca S N astfel ncat:(i) 0 S ,(ii) or. n N (n S n + 1 S),atunci S = N.

PBO PIFie C = N \ S . Presupunem ca C 6= . Aplicand PBO, multimeaC are un prim element n0. Observam ca n0 6= 0, decin0 1 N \ C Rezulta ca n0 1 S . Din (ii), obtinem n0 S ,ceea ce contrazice faptul ca n0 C . Deci C = , adica S = N.

PBO PI

PI PBOPentru orice n N fie P(n) urmatoarea proprietate:or. E N cu E {0, , n} 6= are prim element.Definim S = {n N | P(n)adevarata}.Este clar ca 0 S .Presupunem ca n N a.si demonstram ca n + 1 S . Fie E Ncu E {0, , n + 1} 6= . Daca E {0, , n + 1} = {n + 1}atunci n + 1 este prim element pentru E . Altfel E {0, , n} 6= deci, aplicnd ipoteza de inductie, rezulta ca E are prim element.

Din PI rezulta S = N, deci P(n) este adevarata pentru orice n N.Daca E N, E 6= , atunci exista n E si P(n) e adevarata.In consecinta, E are prim element.

Infimum si supremum

Fie (A,) mpo. Un element a A se numesteminorant al lui X daca a x or. x X ;majorant al lui X daca x a or. x X ;infimum al lui X daca a este cel mai mare minorant(a este ultim element in multimea minorantilor lui X );

supremum al lui X daca a este cel mai mic majorant(a este prim element in multimea majorantilor lui X ).

Exercitiu. Infimumul (supremumul) unei multimi, daca exista, este unic.

Infimumul (supremumul) lui X l vom nota inf X (sup X ).Daca X = {x1, x2} atunci notam inf{x1, x2}, sup{x1, x2}.

Exemple

(R,), X = (3, 4], Y = Nmultimea majorantilor lui X este [4,),4 este ultim element pt. X ,multimea minorantilor lui X este (, 3],3 este infimum pt. X ,Y nu are majoranti (ultim element, supremum),multimea minorantilor lui Y este (, 0),0 este prim element pt. Y .

(N, |), X = {n1, n2}sup X = sup{n1, n2} = cmmmc{n1, n2}inf X = inf{n1, n2} = cmmdc{n1, n2}({2, 4, 5, 10, 12, 20, 25}, |), X = {12, 20, 25}X nu are minoranti si nici majoranti

(P(T ),), X P(T )sup X = {Y |Y X}, inf X = {Y |Y X}

CPO. Latici

CPOO mpo completa (CPO) este o multime partial ordonata(C ,) cu proprietatile:

C are prim element ,sup X exista pentru orice lant X C .

Exemplu. (Pf (A,B),) este CPO.LaticeO mpo (L,) este latice daca sup{x1, x2} si inf{x1, x2} existaoricare ar fi x1, x2 L. Laticea (L,) este completa dacainf X si sup X exista oricare ar fi X L.Exemplu. (P(A),) este latice completa.Exercitiu.

(a) Orice latice completa este CPO.(b) Orice latice completa are prim si ultim element.

Functie crescatoare. Puncte fixe.

Functie crescatoare

Daca (A,A) si (B,B) sunt mpo atunci o functie f : A Beste crescatoare daca a1 A a2 f (a1) B f (a2) or. a1, a2 A.Functie continua

Daca (A,A) si (B,B) sunt CPO atunci o functie f : A Beste continua daca pentru orice lant {an|n N} din A

f (sup{an|n N}) = sup{f (an)|n N}.Exercitiu. Orice functie continua este crescatoare.

Punct fixUn element a A este punct fix al unei functii f : A A daca

f (a) = a.

Teoreme de punct fix

Teorema Knaster-Tarski pentru latici complete

Fie (L,) latice completa si F : L L o functie crescatoare.Atunci a = inf{x L|F(x) x} este cel mai mic punct fix alfunctiei F.

Teorema Knaster-Tarski pentru CPO

Fie (C ,) o CPO si F : C C o functie continua. Atuncia = sup{Fn()|n N} cel mai mic punct fix al functiei F.

Observam ca n ipotezele ultimei teoreme secventaF0() = F() F2() Fn() este un lant, deci a exista.

Teoreme de punct fix

Exemplu.Pf (N,N) CPO, : N N, (k) nedefinita or. k NF : Pf (N,N) Pf (N,N)

F(g)(k) :=

1, k = 0k g(k 1), k > 0 si g(k 1) e definitanedefinit, altfel

Deoarece F este continua, conform Teoremei Knaster-Tarski, celmai mic punct fix al functiei F este f = sup{Fn()|n N}.

f (k) = F(f )(k) :=

1, k = 0k f (k 1), k > 0 si f (k 1) e definitanedefinit, altfel

f este functia factorial.

Teoremele de punct fix sunt folosite in semantica denotationalapentru a defini semantica instructiunii while.

Knaster-Tarski pentru CPO

Demonstratie.Fie (C ,) CPO si F : C C functie continua.(I) a = sup{Fn()|n N} este punct fix.

F(a) = F(sup{Fn()|n N})= sup{F(Fn())|n N} (continuitate)= sup{Fn+1()|n N}= sup{Fn()|n N} = a

(II) a este cel mai mic punct fix.Fie b un alt punct fix, i.e. F(b) = b. Demonstram prin inductiedupa n 1 ca Fn() b. Pentru n = 0, F0() = b deoarece este prim element. Daca Fn() b, atunci Fn+1() F(b),deoarece F este crescatoare. Dar F(b) = b, deci Fn+1() b.

Knaster-Tarski pentru laticicomplete

Demonstratie.Fie (L,) latice completa si F : C C functie crescatoare.(I) a = inf{x L|F(x) x} este punct fix.Fie X := {x L|F(x) x} si fie x X . Atunci a x , deciF(a) F(x) x . Am demonstrat ca F(a) x oricare x X , deciF(a) este un minorant pentru X . In consecinta, F(a) a.Observam ca F(a) X , deci a F(a). Din F(a) a si a F(a)rezulta F(a) = a.

(II) a este cel mai mic punct fix.Fie b un alt punct fix, i.e. F(b) = b.Atunci b X , deci a b.

Latici

Definitia L1.O mpo (L,) este latice daca sup{x1, x2}, inf{x1, x2}exista oricare x1, x2 L.Infimumul (supremumul) devin operatii pe L: : L L L, x1 x2 := sup{x1, x2}, : L L L, x1 x2 := inf{x1, x2}.Propozitia L1-2.

Urmatoarele identitati sunt satisfacute:

asociativitate:(x y) z = x (y z), (x y) z = x (y z),comutativitate: x y = y x , x y = y x ,absorbtie: x (x y) = x , x (x y) = x .

Demonstratie. exercitiu.

Laticea (L,) devine structura algebrica (L,,).

Definitia Algebrica a Laticilor

Definitia L2.O latice este o structura algebrica (L,,) unde si suntoperatii binare asociative, comutative si care verifica proprietatilede absorbtie.

Lema. x y = y x y = x or. x , y L.Demonstratie. Daca x y = y , atunci x = x (x y) = x y .Propozitia L2-1.

Fie (L,,) in sensul Definitiei L2. Definimx y x y = y x y = x .Atunci (L,) este latice in sensul Definitiei L1. In plussup{x , y} = x y , inf{x , y} = x y or. x , y L.Demonstratie. exercitiu.

Latici marginiteO latice este marginita daca are prim si ultim element. Primulelement se noteaza cu 0, iar ultimul element se noteaza cu 1.O latice marginita va fi notata prin (L,, 0, 1), iar ca structuraalgebrica prin (L,,, 0, 1). Se observa ca:x 0 = x , x 0 = 0, x 1 = 1, x 1 = x or. x L.Elementul x este complement al lui y daca x y = 1 si x y = 0.O latice este complementata daca orice element are cel putin uncomplement.

Exemplu. Determinati elementele complementate n laticile:

1

x y z

0

1

w

0

Algebre BooleO latice (L,,) este distributiva daca, or x , y L:x (y z) = (x y) (x z) si x (y z) = (x y) (x z).LemaIntr-o latice distributiva si marginita, un element are cel mult uncomplement.Demostratie. Fie y1, y2 complemente pentru x . Obtinemy1 = y1 1 = y1 (y2 x) = y1 y2 = y2 (y1 x) = y2 1 = y2

O algebra Boole este o latice distributiva si complementata cuprim si ultim element.Daca B este o algebra Boole, atunci pentruorice element exista un unic complement. Putem defini o operatie

: B B prin x := complementul lui x .O algebra Boole este o structura algebrica

(B,,, , 0, 1).

Algebra Boole

Definitie.

O algebra Boole este o structura (A,,, , 0, 1) care satisfaceurmatoarele identitati:

(L1) (x y) z = x (y z), (x y) z = x (y z),(L2) x y = y x , x y = y x ,(L3) x (x y) = x , x (x y) = x ,(D) x (y z) = (x y) (x z), x (y z) = (x y) (x z),(P) x 0 = x , x 0 = 0,(U) x 1 = x , x 1 = 1,(C) x x = 1, x x = 0.

Exemple fundamentale. ({0, 1},,, , 0, 1), (P(T ),,, , ,T )

Logica Matematica si ComputationalaALGEBRE BOOLE I


Scurt istoric

1854 George Boole: The Laws of Thought

All the operations of Language, as an instrument of reasoning,may be conducted by a system of signs composed of thefollowing elements: literal symbols, ...signs of operation, ...the sign of identity =. And these symbols of Logic are in theiruse subject to definite laws, partly agreeing with and partlydiffering from the laws of the corresponding symbols in thescience of Algebra.

1904 Edward V. Huntington: Sets of Independent Postulates forthe Algebra of Logic

1936 Marshall H. Stone: The Theory of Representations ofBoolean Algebras

1938 Claude E. Shannon: A Symbolic Analysis of Relay andSwitching Circuits

Algebra Boole

O algebra Boole este o latice distributiva si complementata cuprim si ultim element.In consecinta, o algebra Boole este o structura

(A,,, , 0, 1)care satisface urmatoarele identitati:


Exemple

L2 = ({0, 1},,, , 0, 1), (P(T ),,, , ,T ) Algebra Lindenbaum-Tarski a calculului propozitional. Multimea evenimentelor asociate unui experiment. Multimea nchis-deschisilor unui spatiu topologic.Exercitiu. Daca (Ai ,i ,i ,i , 0i , 1i ) sunt algebre Boole oricare1 i n atunci A1 An este algebra Boole cu operatiiledefinite pe componente.

Diagrame Hasse

r0

@@r r rr r r

r@

@

@@

@@

a b c

x y z

1

rr rr

@@

@@

00

01

11

10

a = z , b = y , c = x

Reguli de calcul

(A,,, , 0, 1) algebra Boole x y = 1 si x y = 0 y = x ,y = y 1 = y (x x) = (y x) (y x) = y x =(y x) 0 = (y x) (x x) = x (y x) = x 1 = x principiul dublei negatii: x = x ,Atat x , cat si x satisfac ecuatiile care definesc n mod uniccomplementul lui x .

x y x z y z , x z y z x y x y = 0 x y = 1 y xx y x y y y x y = 0x y = 0 y = y 0 = y (x y) = y x x y

Reguli de calcul

(A,,, , 0, 1) algebra Boole

si sunt idempotentex x = x x = xx x = x (x (x x)) = x , x x = x (x (x x)) = x Legile lui De Morganx y = x y , x y = x y .Se demonstreaza ca x y satisface ecuatiile care definesc n modunic complementul lui x y .

Principiul dualitatii

Expresii Booleene

Multimea expresiilor Booleene cu variabilele v1, . . ., vn estedefinita recursiv astfel: v1, . . ., vn , 0, 1 sunt expresii, dc. E1, E2 sunt expresii at. E1, E1 E2, E1 E2 sunt expresii.Vom nota E (v1, . . . , vn) o expresie cu variabilele v1, . . ., vn.

Duala unei expresii

Daca E (v1, . . . , vn) este o expresie, atunci expresia dualaEd(v1, . . . , vn) se obtine interschimbnd 1 cu 0 si cu .Exemplu. E (x , y , z) = x (y z) Ed(x , y , z) = x (y z).Exercitiu. Ed(v1, . . . , vn) = E (v1, . . . , vn)

Principiul dualitatii

E1(v1, . . . , vn) = E2(v1, . . . , vn) Ed1 (v1, . . . , vn) = Ed2 (v1, . . . , vn).

Functii Booleene

Functiile Booleene sunt folosite n reprezentarea circuitelorelectronice. O functie Booleana de grad n este o functief : Ln2 L2. O astfel de functie poate fi descrisa printr-un tabel.

x y z f (x , y , z)0 0 0 00 0 1 00 1 0 1 m1 = x y z0 1 1 01 0 0 1 m2 = x y z1 0 1 1 m3 = x y z1 1 0 1 m4 = x y z1 1 1 1 m5 = x y z

Orice functie Booleana poate fi definita printr-o expresie Booleana.

f (x , y , z) = m1 m2 m3 m4 m5 = = x (y z).Demonstratiile n cadrul calculului propozitional!

Operatiile , , +

(A,,, , 0, 1) algebra Boole x y := x yx y x y = 1,x (y x) = 1, (x y) ((y z) (x z)) = 1. x y := (x y) (y x)x y = 1 x = y ,x y = x y , (x y) z = x (y z). x + y := (x y)d = (x y) (y x)x + x = 0, x + y = y + x ,x + z (x + y) (y + z).Operatia (x , y) 7 x + y are proprietatile unei distante.

Inele Boole

(A,,, , 0, 1) algebra BooleDefinim x + y := (x y) (y x) si x y := x y .Propozitie

R(A) = (A,+, , 0, 1) este inel cu x x = x oricare x A.Demonstratia: exercitiu.

Un astfel de inel se numeste inel Boole.Oricarei algebre Boole i se poate asocia un inel Boole.

Inele Boole

(R,+, , 0, 1) inel Boole(inel unitar cu x x = x oricare x R)

x y + y x = 0, y x = (x y)(x + y) (x + y) = x + y x + x y + y x + y = x + y x + x = 0, x = x x y = y xx y = (x y) = y xDefinim x y := x + y + x y si x y := x y .Propozitie

B(R) = (R,+, , 0, 1) este algebra Boole.Demonstratia: exercitiu.

Inele Boole Algebre Boole

Propozitie

Fie (R,+, , 0, 1) un inel Boole si (A,,, , 0, 1) o algebra Boole. R si R(B(R)) coincid ca inele Boole.

Operatia din B(R) este definita prin x y := x + y + x y ,iar operatia + din R(B(R)) este x + y := (x y) (y x).Observam ca x = 1 + x . Trebuie sa aratam ca x + y = x + y .

A si B(R(A)) coincid ca algebre Boole.Operatia + din R(A) este definita prinx + y := (x y) (y x), iar operatia din B(R(A)) estex y := x + y + x y . Trebuie sa aratam ca x y = x y .

Inelele Boole si algebrele Boole sunt clase de structuri echivalente.

Exemple fundamentale

Camp de multimi (field of sets)A P(X ) cu astfel incat A siX1, X2 A X1 X2, X1 X2, X1 A.Atunci (A,,, , ,A) este o algebra Boole de multimi. F {0, 1}X astfel ncat 0, 1 F sif1, f2 F f1 f2, f1 f2, f1 F ,unde, oricare x X , 0(x) := 0, 1(x) := 1, f1 := f1(x),(f1 f2)(x) := f1(x) f2(x), (f1 f2)(x) := f1(x) f2(x).Atunci (F ,,, , 0, 1) este o algebra Boole de functii.Teorema de reprezentare a lui Stone afirma ca orice algebra Boolepoate fi reprezentata printr-o algebra Boole care are una dinformele de mai sus. In continuare vom demonstra aceasta teorema.

Notiuni de algebra universala

Urmatoarele notiuni se definesc pentru orice clasa de structurialgebrice:

subalgebra, morfism, izomorfism, scufundare, congruenta.

Vom defini aceste notiuni pentru algebrele Boole.

Exercitiu. Definiti notiunile de subalgebra, morfism si congruentapentru latici ca structuri algebrice.

Subalgebre

(A,,, , 0, 1) algebra BooleDefinitieFie S A astfel incat 0, 1 S si

x , y S x y , x y , x S .Atunci (S ,,, , 0, 1) este o algebra Boole, unde , si suntrestrictiile operatiilor din A.In acest caz spunem ca S este o subalgebra a lui A.

Exemplu. Daca A = P({a, b, c}) atunci care din multimileS1 := {, {a}, {b}, {a, b},A} si S2 := {, {a}, {b, c},A}

este subalgebra a algebrei Boole (A,,, , ,A) ?

Morfisme Booleene

(A,A,A, , 0A, 1A), (B,B ,B , , 0B , 1B) algebre BooleDefinitie

O functie f : A B este un morfism de algebre Boole daca: f (0A) = 0B , f (1A) = 1B , f (x) = f (x), f (x A y) = f (x) B f (y), f (x A y) = f (x) B f (y).

Un morfism injectiv se numeste scufundare.

IzomorfismUn izomorfism este un morfism bijectiv. Spunem ca algebreleBoole A si B sunt izomorfe daca exista un izomorfism f : A B.In acest caz scriem A ' B.Exercitiu. Daca f : A B este un izomorfism de algebre Booleatunci f 1 : B A este de asemenea un izomorfism.

Exemple

r0

@@r r rr r r

r@

@

@@

@@

a b c

x y z

1

rr rr

@@

@@

00

01

11

10

A B

f : A B definit prinf (a) = f (b) = f (c) = 01 si f (x) = f (y) = f (z) = 10e un morfism surjectiv

g : B A definit prin g(10) = a si g(01) = zeste o scufundare

Algebre izomorfe

Consideram urmatoarele algebre Boole:

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1

,C = (P({a, b, c}),,, , ,C )D = ({0, 1}3,,, , 000, 111)Atunci A ' C ' D

Structurile izomorfe sunt identice modulo redenumire.

Congruente

(A,,, , 0, 1) algebra BooleDefinitieO congruenta pe A este o relatie A A care verificaurmatoarele proprietati:

este relatie de echivalenta, x y x y , x1 y1 si x2 y2 x1 x2 y1 y2 x1 x2 y1 y2.

Constructia algebrei cat

Pe multimea claselor de echivalenta A/ definim:

x y := x y , x y := x y , x := x .

Atunci (A/,,, , 0, 1) este o algebra Boole.

Constructia algebrei catDemonstratie.

Fie (A,,, , 0, 1) o algebra Boole si o congruenta pe A. Pemultimea claselor de echivalenta A/ definim:

x y := x y , x y := x y , x := x .

Demonstram ca definitiile operatiilor pe clase de echivalenta suntindependente de reprezentanti, i.e.x = z , y = u x y = z u, x y = z u, x = z .Daca x = z atunci x z .Deoarece este congruenta, obtinemx z , deci x = z . Am demonstrat ca definitia operatiei nalgebre cat este corecta.

Demonstrarea identitatilor este imediata:x x = x x = x x = 1.Exercitiu. Aratati ca functia p : A A/, definita prin p(x) := xeste morfism de algebre Boole.

Exemplu

A = {x1x2 xn | xi {0, 1} oricare i}, unde n N, n 1(A,,, , 0 0, 1 1) este algebra Boole, unde operatiile suntdefinite pe componente

Fie k {1, . . . , n} si 1 n1 < n2 < < nk n.Definim x1x2 xn y1y2 yn xni = yni oricare 1 i k.Atunci este o congruenta pe A.Exercitiu. Demonstrati ca Lk2 ' A/.

Logica Matematica si ComputationalaALGEBRE BOOLE I


Algebra Boole

O algebra Boole este o latice distributiva si complementata cuprim si ultim element.In consecinta, o algebra Boole este o structura

(A,,, , 0, 1)care satisface urmatoarele identitati:


Diagrame Hasse

r0

@@r r rr r r

r@

@

@@

@@

a b c

x y z

1

rr rr

@@

@@

00

01

11

10

a = z , b = y , c = x


Camp de multimi (field of sets)A P(X ) cu astfel incat A siX1, X2 A X1 X2, X1 X2, X1 A.Atunci (A,,, , ,A) este o algebra Boole de multimi.

F {0, 1}X astfel ncat 0, 1 F sif1, f2 F f1 f2, f1 f2, f1 F ,unde, oricare x X , 0(x) := 0, 1(x) := 1, f1 := f1(x),(f1 f2)(x) := f1(x) f2(x), (f1 f2)(x) := f1(x) f2(x).Atunci (F ,,, , 0, 1) este o algebra Boole de functii.Teorema de reprezentare a lui Stone afirma ca orice algebra Boolepoate fi reprezentata printr-o algebra Boole care are una dinformele de mai sus. In continuare vom demonstra aceasta teorema.


Camp de multimi (field of sets)A P(X ) cu astfel incat A siX1, X2 A X1 X2, X1 X2, X1 A.Atunci (A,,, , ,A) este o algebra Boole de multimi. F {0, 1}X astfel ncat 0, 1 F sif1, f2 F f1 f2, f1 f2, f1 F ,unde, oricare x X , 0(x) := 0, 1(x) := 1, f1 := f1(x),(f1 f2)(x) := f1(x) f2(x), (f1 f2)(x) := f1(x) f2(x).Atunci (F ,,, , 0, 1) este o algebra Boole de functii.

Teorema de reprezentare a lui Stone afirma ca orice algebra Boolepoate fi reprezentata printr-o algebra Boole care are una dinformele de mai sus. In continuare vom demonstra aceasta teorema.


Camp de multimi (field of sets)A P(X ) cu astfel incat A siX1, X2 A X1 X2, X1 X2, X1 A.Atunci (A,,, , ,A) este o algebra Boole de multimi. F {0, 1}X astfel ncat 0, 1 F sif1, f2 F f1 f2, f1 f2, f1 F ,unde, oricare x X , 0(x) := 0, 1(x) := 1, f1 := f1(x),(f1 f2)(x) := f1(x) f2(x), (f1 f2)(x) := f1(x) f2(x).Atunci (F ,,, , 0, 1) este o algebra Boole de functii.Teorema de reprezentare a lui Stone afirma ca orice algebra Boolepoate fi reprezentata printr-o algebra Boole care are una dinformele de mai sus. In continuare vom demonstra aceasta teorema.

Notiuni de algebra universala

(A,,, , 0, 1), (B,B ,B , , 0B , 1B) algebre Boole Fie S A astfel incat 0, 1 S si

x , y S x y , x y , x S .Atunci (S ,,, , 0, 1) este o algebra Boole, unde , si sunt restrictiile operatiilor din A. In acest caz spunem ca Seste o subalgebra a lui A.

O functie f : A B este un morfism de algebre Booledaca: f (0A) = 0B , f (1A) = 1B , f (x) = f (x),f (x A y) = f (x) B f (y), f (x A y) = f (x) B f (y)or. x , y A. Un morfism injectiv se numeste scufundare. Unizomorfism este un morfism bijectiv.

O congruenta pe A este o relatie A A de echivalentacare verifica urmatoarele proprietati:

x y x y , x1 y1 si x2 y2 x1 x2 y1 y2 x1 x2 y1 y2.



Pe multimea claselor de echivalenta A/ definim:

x y := x y , x y := x y , x := x .

Atunci (A/,,, , 0, 1) este o algebra Boole.

Exercitiu. Aratati ca functia p : A A/, definita prin p(x) := xeste morfism de algebre Boole.

Exemplu



Exemplu


Fie k {1, . . . , n} si 1 n1 < n2 < < nk n.Definim x1x2 xn y1y2 yn xni = yni oricare 1 i k.Atunci este o congruenta pe A.

Exercitiu. Demonstrati ca Lk2 ' A/.

Exemplu



Filtre si Ideale

In unele clase de structuri (inele, module, grupuri, algebre Boole)congruentele sunt unic determinate de submultimi particulare.

(A,,, , 0, 1) algebra BooleDefinitie

O submultime F A se numeste filtru daca: 1 F , x F , x y y F , x , y F x y .

Un filtru F se numeste propriu daca 0 6 F (F 6= A).Exercitiu. Notiunea duala este cea de ideal. Definiti notiunea deideal folosind principiul dualizarii.

Filtre si Ideale




Un filtru F se numeste propriu daca 0 6 F (F 6= A).

Exercitiu. Notiunea duala este cea de ideal. Definiti notiunea deideal folosind principiul dualizarii.

Filtre si Ideale




Un filtru F se numeste propriu daca 0 6 F (F 6= A).Exercitiu. Notiunea duala este cea de ideal. Definiti notiunea deideal folosind principiul dualizarii.

Filtre

Exemple.

{1} este filtru. Multimea {{a}, 1} este filtru in P({a, b}). Daca A este o algebra Boole, atunci multimea

[a) := {x A | a x}este filtru oricare a A. Observam ca [a) este propriu daca sinumai daca a 6= 0. Daca f : A B este un morfism de algebre Boole atunci

f 1({1}) = {x A|f (x) = 1}este filtru in A.

Fie A o algebra Boole si F A. Daca F este filtru si subalgebraa lui A, atunci F = A.

Filtre

Exemple.

{1} este filtru. Multimea {{a}, 1} este filtru in P({a, b}).

Daca A este o algebra Boole, atunci multimea[a) := {x A | a x}

este filtru oricare a A. Observam ca [a) este propriu daca sinumai daca a 6= 0. Daca f : A B este un morfism de algebre Boole atunci



Filtre

Exemple.


[a) := {x A | a x}este filtru oricare a A. Observam ca [a) este propriu daca sinumai daca a 6= 0.

Daca f : A B este un morfism de algebre Boole atuncif 1({1}) = {x A|f (x) = 1}

este filtru in A.


Filtre

Exemple.


[a) := {x A | a x}este filtru oricare a A. Observam ca [a) este propriu daca sinumai daca a 6= 0. Daca f : A B este un morfism de algebre Boole atunci



Filtre si congruente

(A,,, , 0, 1) algebra BooleTeorema

(1) Daca F A filtru, definim F A A prinx F y x y F x y F si y x F .

Atunci F este o congruenta pe A.(2) Daca A A este o congruenta pe A, definim

F := 1 = {x A | x 1}.Atunci F este filtru n A.

(3) Daca F A este un filtru si A A este o congruenta,atunci F = FF si =F .

Exista o bijectie ntre filtre si congruente. Vom nota

A/F := A/F

Demonstratie.(1), (2) exercitiu.

(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .

Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1.

Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .

Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .

Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .

Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.

Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x y

si, similar, y x y . Asadar x y siam demonstrat ca F .


(3) Daca F este un filtru si x A, atuncix FF x F 1 x 1 F x F .Fie congruenta si x y in A. Atuncix y y y , deci x y 1si, similar, y x 1. Rezulta x y 1,deci x y F, adica x F y .Am demonstrat ca F .Invers, fie x F y , adica x y Fy .Rezulta x y 1, deci x y 1 si y x 1.Obtinem x = x 1 x (x y) = x ysi, similar, y x y . Asadar x y siam demonstrat ca F .

Filtrele cubului

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1

F0 = {0, a, b, c, x , y , z , 1},F1 = {a, x , y , 1}, F2 = {b, x , z , 1}, F3 = {c , y , z , 1}F4 = {x , 1}, F5 = {y , 1}, F6 = {z , 1}

u F1 v u v F1 a u v si a v u.Exercitiu. Demonstrati ca u F1 v a u = a v or. u, v A.Exercitiu. Determinati algebra cat pentru filtrele F0, . . ., F7 .

Filtrele cubului

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1


u F1 v u v F1 a u v si a v u.

Exercitiu. Demonstrati ca u F1 v a u = a v or. u, v A.Exercitiu. Determinati algebra cat pentru filtrele F0, . . ., F7 .

Filtrele cubului

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1


u F1 v u v F1 a u v si a v u.Exercitiu. Demonstrati ca u F1 v a u = a v or. u, v A.

Exercitiu. Determinati algebra cat pentru filtrele F0, . . ., F7 .

Filtrele cubului

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1


u F1 v u v F1 a u v si a v u.Exercitiu. Demonstrati ca u F1 v a u = a v or. u, v A.Exercitiu. Determinati algebra cat pentru filtrele F0, . . ., F7 .

Ultrafiltre

(A,,, , 0, 1) algebra BooleTeorema de caracterizare a ultrafiltrelorPentru un filtru propriu F A urmatoarele afirmatii suntechivalente:

(1) x F x 6 F or. x A,(2) x y F x F sau y F or. x , y A,(3) F U, U filtru propriu F = U.

DefinitieUn ultrafiltru este un filtru propriu care verifica proprietatileechivalente de mai sus. Observam ca ultrafiltrele sunt elementemaximale in multimea filtrelor proprii, ordonata cu incluziunea.

Exercitiu. F este ultrafiltru A/F ' L2

Caracterizarea ultrafiltrelorDemonstratia.

(1 2) Implicatia este evidenta. Fie x , y A astfel ncat x y F si x 6 F .

Atunci x F ,deci (x y) x = y x F . Deoarece y x y , rezultay F .

(2 3) Fie U un filtru propriu astfel ncat F U. Presupunem caexista x U \ F . Deoarece 1 = x x F si x 6 F , rezultax F . In consecinta x U, deci x x = 0 U. Contrazicemfaptul ca U este propriu, deci presupunerea a fost eronata.Rezulta U = F .

(3 1) Fie x A astfel ncat x 6 F . DacaU := {a A| exista f F astfel incat f x a}atunci U este filtru, F U si x U (exercitiu). DeoareceU 6= F , rezulta ca U nu e propriu, deci 0 U. Asadar existaf F astfel ncat f x = O, adica f x .Am demonstrat ca x F .


(1 2) Implicatia este evidenta. Fie x , y A astfel ncat x y F si x 6 F . Atunci x F ,deci (x y) x = y x F .

Deoarece y x y , rezultay F .




(1 2) Implicatia este evidenta. Fie x , y A astfel ncat x y F si x 6 F . Atunci x F ,deci (x y) x = y x F . Deoarece y x y , rezultay F .





(2 3) Fie U un filtru propriu astfel ncat F U. Presupunem caexista x U \ F .

Deoarece 1 = x x F si x 6 F , rezultax F . In consecinta x U, deci x x = 0 U. Contrazicemfaptul ca U este propriu, deci presupunerea a fost eronata.Rezulta U = F .




(2 3) Fie U un filtru propriu astfel ncat F U. Presupunem caexista x U \ F . Deoarece 1 = x x F si x 6 F , rezultax F .

In consecinta x U, deci x x = 0 U. Contrazicemfaptul ca U este propriu, deci presupunerea a fost eronata.Rezulta U = F .





(3 1) Fie x A astfel ncat x 6 F .

DacaU := {a A| exista f F astfel incat f x a}atunci U este filtru, F U si x U (exercitiu). DeoareceU 6= F , rezulta ca U nu e propriu, deci 0 U. Asadar existaf F astfel ncat f x = O, adica f x .Am demonstrat ca x F .




(3 1) Fie x A astfel ncat x 6 F . DacaU := {a A| exista f F astfel incat f x a}atunci U este filtru, F U si x U (exercitiu).

DeoareceU 6= F , rezulta ca U nu e propriu, deci 0 U. Asadar existaf F astfel ncat f x = O, adica f x .Am demonstrat ca x F .




(3 1) Fie x A astfel ncat x 6 F . DacaU := {a A| exista f F astfel incat f x a}atunci U este filtru, F U si x U (exercitiu). DeoareceU 6= F , rezulta ca U nu e propriu, deci 0 U.

Asadar existaf F astfel ncat f x = O, adica f x .Am demonstrat ca x F .




(3 1) Fie x A astfel ncat x 6 F . DacaU := {a A| exista f F astfel incat f x a}atunci U este filtru, F U si x U (exercitiu). DeoareceU 6= F , rezulta ca U nu e propriu, deci 0 U. Asadar existaf F astfel ncat f x = O, adica f x .

Am demonstrat ca x F .

Filtrele cubului

A=

r0

@@r r rr r r

r

@@

@@

@@

a b c

x y z

1

F0 = {0, a, b, c, x , y , z , 1}F1 = {a, x , y , 1}, F2 = {b, x , z , 1}, F3 = {c , y , z , 1} ultrafiltreF4 = {x , 1}, F5 = {y , 1}, F6 = {z , 1}

Existenta ultrafiltrelor

Fie (A,,, , 0, 1) algebra Boole.Multimea filtrelor proprii ale algebrei A este nevida, deoarece{1} este filtru propriu n orice algebra Boole.

Pentru a demonstra existenta ultrafiltrelor folosim un rezultatechivalent cu Axioma alegerii n sistemul axiomaticZermelo-Fraenkel, si anume Lema lui Zorn.

Lema lui ZornFie (P,) o mpo cu proprietatea ca orice lant C P aremajorant. Atunci P are cel putin un element maximal.


Fie (A,,, , 0, 1) algebra Boole.Multimea filtrelor proprii ale algebrei A este nevida, deoarece{1} este filtru propriu n orice algebra Boole.Pentru a demonstra existenta ultrafiltrelor folosim un rezultatechivalent cu Axioma alegerii n sistemul axiomaticZermelo-Fraenkel, si anume Lema lui Zorn.

Lema lui ZornFie (P,) o mpo cu proprietatea ca orice lant C P aremajorant. Atunci P are cel putin un element maximal.


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.

Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. Fie C un lant din P si V := {F |F C}. Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P. Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P.

Fie C un lant din P si V := {F |F C}. Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P. Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. Fie C un lant din P si V := {F |F C}.

Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P. Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. Fie C un lant din P si V := {F |F C}. Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C.

Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P. Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. Fie C un lant din P si V := {F |F C}. Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P.

Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 in A atunci exista un ultrafiltru U astfel ncat x U.Dem. Daca P = {F |F filtru propriu, x F}, atunci (P,) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. Fie C un lant din P si V := {F |F C}. Atunci V esteun filtru (exercitiu) si a V , deci V este majorant pentru C. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U in P. Aratam ca U esteultrafiltru n A. Fie U U , unde U este un filtru propriu. Atuncix U , deci U P. Cum U este maximal n P, obtinem U = U .


Propozitie

Daca x 6= 0 n A atunci exista un ultrafiltru U astfel ncat x U.

Corolar 1. Multimea ultrafiltrelor este nevida.

Corolar 2.{U A |U ultrafiltru} = {1}.

Dem. Fie x U oricare ar fi U ultrafiltru si presupunem ca x 6= 1.Atunci x 6= 0, deci exista un ultrafiltru V astfel ncat x V .Rezulta 0 = x x V , ceea ce contrazice faptul ca V esteultrafiltru.


Propozitie

Daca x 6= 0 n A atunci exista un ultrafiltru U astfel ncat x U.Corolar 1. Multimea ultrafiltrelor este nevida.

Corolar 2.{U A |U ultrafiltru} = {1}.

Dem. Fie x U oricare ar fi U ultrafiltru si presupunem ca x 6= 1.Atunci x 6= 0, deci exista un ultrafiltru V astfel ncat x V .Rezulta 0 = x x V , ceea ce contrazice faptul ca V esteultrafiltru.

Teorema de reprezentare a lui Stone

Pentru orice algebra Boole A exista o multime X si un morfisminjectiv d : A P(X ).

Observatie

Orice algebra Boole este izomorfa cu o algebra Boole de multimi:

A ' d(A) P(X ).

CorolarPentru orice algebra Boole A exista o multime X si un morfisminjectiv d : A LX2 .Dem. Este consecinta a faptului ca P(X ) ' LX2 .


Pentru orice algebra Boole A exista o multime X si un morfisminjectiv d : A P(X ).Observatie


A ' d(A) P(X ).





A ' d(A) P(X ).

CorolarPentru orice algebra Boole A exista o multime X si un morfisminjectiv d : A LX2 .

Dem. Este consecinta a faptului ca P(X ) ' LX2 .




A ' d(A) P(X ).



Demonstratie.

Fie A o algebra Boole si fie U multimea ultrafiltrelor lui A. Definimd : A P(U) prin d(a) := {U U | a U}.

Fie x , y A si U U .U d(x) x U x 6 U U d(x)U d(x y) x y U x U sau y U U d(x) d(y)Am demonstrat ca d(x) = d(x) si d(x y) = d(x) d(y),deci d este un morfism Boolean.

Fie x , y A astfel ncat d(x) = d(y). Atuncid(x y) = d(x) d(y) = U , adicax y {U |U ultrafiltru in A}.Rezulta x y = 1, deci x = y .Am demonstrat ca d este un morfism injectiv.


Demonstratie.

Fie A o algebra Boole si fie U multimea ultrafiltrelor lui A. Definimd : A P(U) prin d(a) := {U U | a U}.Fie x , y A si U U .U d(x) x U x 6 U U d(x)

U d(x y) x y U x U sau y U U d(x) d(y)Am demonstrat ca d(x) = d(x) si d(x y) = d(x) d(y),deci d este un morfism Boolean.



Demonstratie.

Fie A o algebra Boole si fie U multimea ultrafiltrelor lui A. Definimd : A P(U) prin d(a) := {U U | a U}.Fie x , y A si U U .U d(x) x U x 6 U U d(x)U d(x y) x y U x U sau y U U d(x) d(y)

Am demonstrat ca d(x) = d(x) si d(x y) = d(x) d(y),deci d este un morfism Boolean.



Demonstratie.

Fie A o algebra Boole si fie U multimea ultrafiltrelor lui A. Definimd : A P(U) prin d(a) := {U U | a U}.Fie x , y A si U U .U d(x) x U x 6 U U d(x)U d(x y) x y U x U sau y U U d(x) d(y)Am demonstrat ca d(x) = d(x) si d(x y) = d(x) d(y),deci d este un morfism Boolean.



Demonstratie.


Fie x , y A astfel ncat d(x) = d(y).

Atuncid(x y) = d(x) d(y) = U , adicax y {U |U ultrafiltru in A}.Rezulta x y = 1, deci x = y .Am demonstrat ca d este un morfism injectiv.


Demonstratie.


Fie x , y A astfel ncat d(x) = d(y). Atuncid(x y) = d(x) d(y) = U , adicax y {U |U ultrafiltru in A}.

Rezulta x y = 1, deci x = y .Am demonstrat ca d este un morfism injectiv.


Demonstratie.


Fie x , y A astfel ncat d(x) = d(y). Atuncid(x y) = d(x) d(y) = U , adicax y {U |U ultrafiltru in A}.Rezulta x y = 1, deci x = y .

Am demonstrat ca d este un morfism injectiv.


Demonstratie.



Stone duality Fie A o algebra Boole si U multimea ultrafiltrelor lui A.Definim Ua = {U U | a U} oricare a A siUI =

{Ua | a I} pentru orice ideal I A.

{UI |I ideal} defineste o topologie pe U (U , ) este compact Hausdorff {Ua | a A} este o baza de nchisi-deschisi (clopen sets)

Un astfel de spatiu topologic se numete spatiu Boolean.

Teorema

A = ({Ua | a A},,, ,U0,U1) este algebra Boole, undeUa Ub = Uab, Ua Ub = Uab, (Ua) = Ua , U0 = ,U1 = U

A ' A

Orice algebra Boole este izomorfa cu algebra nchis-deschisilor unuispatiu topologic.

Stone duality Fie A o algebra Boole si U multimea ultrafiltrelor lui A.Definim Ua = {U U | a U} oricare a A siUI =

{Ua | a I} pentru orice ideal I A. {UI |I ideal} defineste o topologie pe U (U , ) este compact Hausdorff {Ua | a A} este o baza de nchisi-deschisi (clopen sets)

Un astfel de spatiu topologic se numete spatiu Boolean.

Teorema

A = ({Ua | a A},,, ,U0,U1) este algebra Boole, undeUa Ub = Uab, Ua Ub = Uab, (Ua) = Ua , U0 = ,U1 = U

A ' A

Orice algebra Boole este izomorfa cu algebra nchis-deschisilor unuispatiu topologic.

Atomi


Elementele minimale n A \ {0} se numesc atomi. Algebra A senumeste atomica daca pentru orice x 6= 0 exista un atom a Aastfel ncat a x .

Exercitiu

a este atom [a) este ultrafiltru.Exercitiu

Daca A este atomica atunci x ={a A| a atom, a x} or. x 6= 0.

Atomi


Elementele minimale n A \ {0} se numesc atomi. Algebra A senumeste atomica daca pentru orice x 6= 0 exista un atom a Aastfel ncat a x .Exercitiu

a este atom [a) este ultrafiltru.

Exercitiu


Atomi


Elementele minimale n A \ {0} se numesc atomi. Algebra A senumeste atomica daca pentru orice x 6= 0 exista un atom a Aastfel ncat a x .Exercitiu

a este atom [a) este ultrafiltru.Exercitiu


Exemple

A = Ln2

are n atomi:(0, . . . , 0), (1, 0, . . . , 0), . . ., (0, . . . , 0, 1)

B = P(X ) are atomii de forma {x} cu x X . C P(R) unde

C = {,R}{[a1, b1) . . . [an, bn)|n 1, a1 < b1 < . . . < an < bn n R}{(, b1) . . . [an, bn)|n 1, b1 < . . . < an < bn n R}{[a1, b1) . . . [an,)|n 1, b1 < . . . < an n R}

C este o algebra Boole fara atomi.

Exemple

A = Ln2 are n atomi:(0, . . . , 0), (1, 0, . . . , 0), . . ., (0, . . . , 0, 1)




Exemple

A = Ln2 are n atomi:(0, . . . , 0), (1, 0, . . . , 0), . . ., (0, . . . , 0, 1)

B = P(X )

are atomii de forma {x} cu x X .

C P(R) unde



Exemple

A = Ln2 are n atomi:(0, . . . , 0), (1, 0, . . . , 0), . . ., (0, . . . , 0, 1)

B = P(X ) are atomii de forma {x} cu x X .

C P(R) unde



Exemple

A = Ln2 are n atomi:(0, . . . , 0), (1, 0, . . . , 0), . . ., (0, . . . , 0, 1)




Algebre Boole finite

Exercitiu

Orice algebra Boole finita este atomica.

A o algebra Boole finita, At(A) multimea atomilor lui A, U(A)multimea ultrafiltrelor lui A.

Exercitiu

Daca U U si a = {x |x U} atunci a At(A) si U = [a).Exista o bijectie ntre At(A) si U(A).TeoremaDaca A o algebra Boole finita, atunci A ' P(At(A)) siizomorfismul ested : A P(At(A)), d(x) = {a A| a atom, a x} or. x A.Dem. exercitiu


Exercitiu



Exercitiu

Daca U U si a = {x |x U} atunci a At(A) si U = [a).Exista o bijectie ntre At(A) si U(A).

TeoremaDaca A o algebra Boole finita, atunci A ' P(At(A)) siizomorfismul ested : A P(At(A)), d(x) = {a A| a atom, a x} or. x A.Dem. exercitiu


Exercitiu



Exercitiu

Daca U U si a = {x |x U} atunci a At(A) si U = [a).Exista o bijectie ntre At(A) si U(A).TeoremaDaca A o algebra Boole finita, atunci A ' P(At(A)) siizomorfismul ested : A P(At(A)), d(x) = {a A| a atom, a x} or. x A.Dem. exercitiu

Logica Matematica si ComputationalaCALCULUL PROPOZITIONAL CLASIC PC (I)


Inceputurile logicii

Aristotel (sec. IV i.e.n.)

primul studiu formal al logicii a studiat silogismele, deductii formate din doua

premize si o concluzie.

Premiza Toti oamenii sunt muritori.Premiza Toti grecii sunt oameni.Concluzie Toti grecii sunt muritori.

Silogismele

Patru tipuri de enunturi (AffIrmo nEgO)A: Toti X sunt Y . (universal afirmativ)E: Nici un X nu este Y . (universal negativ)I: Unii X sunt Y . (particular afirmativ)O: Unii X nu sunt Y . (particular negativ)

Un silogism este format din doua premize si o concluzie,fiecare avand una din formele A E I O.

Premiza majoraPremiza minoraConcluzia

Silogismele

Barbara FestinoPremiza Toti oamenii sunt muritori. Nici un caine nu este pisica.Premiza Toti grecii sunt oameni. Unele carnivore sunt pisici.Concluzie Toti grecii sunt muritori. Unele carnivore nu sunt caini.

Felapton AIOPremiza Nici un X nu este Y . Toti X sunt Y .Premiza Toti X sunt Z . Unii Z sunt Y .Concluzie Unii Z nu sunt Y . Unii Z nu sunt X .

Adevarat pentru X 6= Fals256 silogisme,15 valide,24 valide daca X , Y , Z 6=

Gottfried Wilhelm Leibniz, 1646 -1716lingua characteristica universalis, calculus ratiocinator

If controversies were to arise, there would be no more needof disputation between two philosophers than between twoaccountants. For it would suffice to take their pencils in theirhands, and say to each other: Calculemus - Let us calculate.

George Boole, 1815-1864The Mathematical Analysis of Logic (1847)

The design of the following treatise is to investigate thefundamental laws of the operations of the mind by whichreasoning is performed; to give expressions to them in thesymbolic language of calculus, and upon this foundation toestablish the science of logic and constructs its methods.

Logica algebrica

Analiza rationamentelor prin metode asemanatoare calcululuialgebric.

x multimea oamenilor,y multimea muritorilor,z multimea grecilor.

BarbaraPremiza Toti oamenii sunt muritori. x(1 y) = 0 x = xyPremiza Toti grecii sunt oameni. z(1 x) = 0 z = zxConcluzie Toti grecii sunt muritori. z(1 y) = 0 z = zy

Dem. z = zx = z(xy) = (zx)y = zy

Logica algebrica

Exemplu. Fie a, b, c si d proprietati ale substantelor care potinterac tiona n cadrul unui experiment. Se cunosc urmatoarele:(1) a si b apar simultan apare numai una dintre c si d ,(2) b si c apar simultan fie a si d apar simultan,

fie nu apare nici una,(3) nici una dintre a si b nu apare nici una dintre c si d nu apare,(4) nici una dintre c si d nu apare nici una dintre a si b nu apare.

Demonstrati ca:(a) nici una dintre a si b nu apare nu apare nici c ,(b) a, b si c nu apar simultan.

Logica algebrica

Fie A, B, C si D multimile substantelor care au, respectiv,proprietatile a, b, c si d .

(1) a si b apar simultan cu siguranta apare una dintre c si d ,A B (C D) (D C )(2) b si c apar simultan fie a si d apar simultan,

fie nu apare nici una,B C (A D) (A D)(3) nici una dintre a si b nu apare nici una dintre c si d nu apare,A B C D(4) nici una dintre c si d nu apare nici una dintre a si b nu apare.C D A B

Logica algebrica

Notam AB = A B. Folosim A B AB = .Ipotezele:(1) AB(C D)(C D) = (2) BC (A D)(A D) = (3) A B(C D) = (4) C D(A B) = Concluzia:(1) A B C A BC = Demonstratia:A B(C D) = A BC A BD = A BC = si A BD = (2) exercitiu.

UserSticky Notedefapt punctul b al dem gasit cu 2 pag in urma

Logica Matematica si ComputationalaCALCULUL PROPOZITIONAL CLASIC PC (I)


Logica matematic a Friedrich Ludwig Gottlob Frege, Begriffsschrift, 1879

(a formula language, modeled upon that of arithmetic, forpure thought)

Giuseppe Peano, Formulario Mathematico, 1894-1908 Bertrand Russell si Alfred North Whitehead

Principia Mathematica, 1910-1913 David Hilbert, Hilberts Pogram , 1921

Once a logical formalism is established one can expect that asystematic, so-to-say computational, treatment of logicformulas is possible, which would somewhat correspond to thetheory of equations in algebra.

Kurt GodelTeorema de completitudine a calculului cu predicate (1929),Teoremele de incompletitudine (1931)

Alfred TarskiThe Concept of Truth in Formalized Languages (1935),On the Concept of Logical Consequence (1936)

Calculul propozitional

O propozitie este un enunt care poate fiadevarat(1) sau fals(0).

Propozitiile sunt notate simbolic (, , , ) si suntcombinate cu ajutorul conectorilor logici (, , , , ).

Exemplu.

Fie propozitia: Azi este vineri, deci avem curs de logica.Cine este ?Propozitia este: Azi este vieri si nu avem curs de logica.

Calculul propozitional

Exemplu.

Daca trenul ntarzie si nu sunt taxiuri la gara,atunci Ion ntarzie la ntalnire.

Trenul ntarzie. Ion nu ntarzie la ntalnire.

In consecinta, sunt taxiuri la gara.

= trenul ntarzie = sunt taxiuri la gara = Ion ntarzie la ntalnire

Rationamentul anterior poate fi reprezentat formal astfel:{( ) , ,} `

Sintaxa si semantica

Un sistem logic are doua componente: sintaxa si semantica. Notiunile sintactice sunt descrise formal, simbolic.

Principalele notiuni sintactice sunt: limbajul, formulele,teoremele, notiunea de demonstratie. Simbolul ` este sintacticsi are urmatoarea semnificatie: notam prin ` faptul caformula este demonstrabila din multimea de formule .

Semantica asociaza un nteles, o interpretare notiunilorsintactice si defineste riguros notiunea de formula universaladevarata (tautologie). Alte notiuni semantice importantesunt: evaluarile (interpretarile), modelele, multimile de formulesatisfiabile. Simbolul |= este semantic si are urmatoareasemnificatie: notam prin |= faptul ca formula esteadevarata ori de cate ori toate formulele din sunt adevarate.

Sintaxa PC

Limbajul. Formulele.

Limbajul PC este format din:

o multime infinta de variabile propozitionale:Var = {v1, v2, . . . , vn, . . .}

conectori logici: (unar), (binar) paranteze: ( , ).

Formulele PC se definesc recursiv astfel:

(F0) orice variabila propozitionala este formula,

(F1) daca este formula, atunci () este formula,(F2) daca si sunt formule, atunci ( ) este formula,(F3) orice formula se obtine aplicand regulile (F0), (F1), (F2) de

un numar finit de ori.

Limbajul. FormuleleExemple. v1 (v2), v1v2 nu sunt formule . ((v1 v2) (v1)), ((v1 v2))sunt formule.

Vom presupune ca are precedenta cea mai mare si vom puneparantezele numai atunci cand sunt necesare. Astfel formula((v1 v2) (v1)) o vom scrie (v1 v2) v1.Conectori derivati

Pentru si formule oarecare, definim urmatoarele prescurtari: := := ( ) := ( ) ( )In aceasta prezentare a calculului propozitional am considerat si drept conectori principali. Conectorii derivati , , suntdefiniti folosind conectorii principali.

Limbajul. Formulele.

Multimea formulelor se defineste echivalent n modul urmator:

Multimea formulelor este intersectia tuturor multimilor W decuvinte (siruri finite de simboluri din limbaj) care verificaurmatoarele proprietati:

contin variabilele propozitionale, sunt nchise la

(daca W atunci () W ), sunt nchise la

(daca 1, 2 W atunci (1 2) W ).Vom nota cu Form multimea formulelor PC.

Inductia structurala

Principiul inductiei pe formule

Fie P() o proprietate a formulelor astfel ncat:

P(v) este adevarata oricare v Var , daca P() este adevarata, atunci P() este adevarata

oricare Form, daca P() si P() sunt adevarate, atunci P( ) este

adevarata oricare , Form.Atunci P() este adevarata pentru orice formula Form.Dem. Fie W = { Form | P()adevarata}. Din ipoteze rezultaca Var W si W este nchisa la si . Deoarece Form esteintersectia multimilor W cu proprietatile de mai sus, rezultaForm W , deci W = Form.

Sistemul deductivVom prezenta sistemul deductiv al PC in stilul Hilbert, carepresupune existenta mai multor axiome si foloseste ca regula dedeductie modus ponens. Alte modalitati de prezentare a unuisistem de deductiv sunt deductia naturala si calculul cu secventi(sisteme Gentzen).

AxiomeleOricare ar fi , si formule ale PC, urmatoarele formule suntaxiome:

(A1) ( )(A2) ( ( )) (( ) ( ))(A3) ( ) ( ).

Regula de deductie

MP (modus ponens),

Demonstratie. Teoreme

DefinitieO demonstratie este o secventa de formule 1, . . ., n astfelncat, pentru fiecare i {1, . . . , n}, una din urmatoarele conditiieste satisfacuta:

i este axioma, i se obtine din formul

logica matematica cursuri - prof. Ioana Leustean

Documents

Transcript of logica matematica cursuri - prof. Ioana Leustean