Memorator matematic

I.1. Notiunea de propozitie

Definitia I.1.1. Se numeste propozitie un enunt despre care se poate spune ca este adevarat sau fals, adr nu si adevarat si fals simultan.

Se noteaza cu p,q, P, Q

Ex: 1) - - Q : acesta este un enunt care exprima un adevar, deci o propozitie adevarata.

2) x + 5 = 3, x- N este o propozitie falsa, pentru ca nu exista nici un numar natural astfel ca x + 5 = 3

3) x - y, x,y- N este un enunt despre care nu se poate spune nimic. Deci nu este o propozitie.

Valoarea logica sau valoarea de adevar a unei propozitii. Daca o propozitie p este adevarata se spune ca are valoarea logica sau valoarea de adevar: adevarul; aceasta valoare de adevar se noteaza cu simbolul 1 sau a si scriem v(p) = 1 sau (v)p = a. Daca o propozitie q este falsa, se spune ca are valoarea de adevar: falsul; aceasta valoare de adevar se noteaza cu simbolul 0 sau f si scriem v(q) = 0 sau v(q) = f.

I.2. Operatori logici

Negatia

Definitia I.1.2. Negatia unei propozitii p este propozitia care este falsa cand p este adevarata si este adevarata cand p este falsa. Se noteaza: non p, - p,

Tabela de adevar a propozitiei non p se intocmeste be baza relatiei v(non p) = 1 - v(p).

p non p

1 0

0 1

Conjunctia

Definitia I.2.2. Conjunctia a doua propozitii p si q este propozitia care este adevarata daca si numai daca fiecare propozitie p si q este adevarata.

Se noteaza: p - q

Tabela de adevar a propozitiei p - q este:

p q p - q

1 1 1

1 0 0

0 1 0

0 0 0

Disjunctia

Definitia I.2.3. Disjunctia a doua propozitii p si q este propozitia care este adevarata daca si numai daca cel putin una din propozitiile p, qeste adevarata.

Se noteaza: p - q

Tabela de adevar a propozitiei p - q este:

p q p - q

1 1 1

1 0 1

0 1 1

0 0 0

Implicatia

Definitia I.2.4. Implicatia propozitiilor p si q este propozitia care este falsa daca si numai daca p este adevarata si q este falsa.

Se noteaza: (non p) sau q, p- q si se citeste: "p implica q" sau "daca p, atunci q". Propozitia p este ipoteza, iar propozitia q este concluzia.

Tabela de adevar a propozitiei p- q este:

p q non p (non p)- q

1 1 0 1

1 0 0 0

0 1 1 1

0 0 1 1

Echivalenta logica

Definitia I.2.4. Propozitiile p si q sunt echivalente logic, daca si numai daca p, q sunt adevarate sau false simultan.

Se noteaza (non p)- q si (non q)- p; (p- q) si (q- p); p- q; se citeste: "p echivalent cu q" sau "p daca si numai daca q", "p este conditie necesara si suficienta pentru q".

Tabela de adevar a propozitiei compuse p- q este:

p q non p non q p- q q- p (p- q)- (q- p)

1 1 0 0 1 1 1

1 0 0 1 0 1 0

0 1 1 0 1 0 0

0 0 1 1 1 1 1

I.3. Expresii in calculul propozitiilor

Propozitiile p,q, r, fiind date, cu ajutorul operatorilor logici - , - , - , - , - putem formula diferite expresii, care se numesc formule ale calculului cu propozitii sau expresii logice. Ele se noteaza - sau - (p,q,r, ), - (p,q,r, ).

Inlocuind in - pe p,q,r, cu diferite propozitii obtinem o alta propozitie, adevarata sau nu, a carei valoare de adevar se numeste valoarea expresiei - , obtinuta pentru propozitiile p,q,r, respective.

Definitia I.3.1. O expresie logica - care se reduce la o propozitie adevarata, oricare ar fi propozitiile p,q,r, se numeste tautologie.

Definitia I.3.2. Doua expresii logice - si - se numesc echivalente daca si numai daca pentru orice propozitii p,q,r, cele doua expresii reprezinta propozitii care au aceeasi valoare de adevar. In scris se noteaza - - -

I.4. Notiunea de predicat

Definitia I.4.1. Se numeste predicat sau propozitie cu variabile un enunt care depinde de o variabila sau de mai multe variabile si are proprietatea ca pentru orice valori date variabilelor se obtine o propozitie adevarata sau o propozitie falsa.

Predicatele se noteaza p(z,y,z, ), q(x,y,z, ) si pot fi unare (de o variabila), binare (de doua variabile), ternare (de trei variabile), etc., variabilele x,y,z, luand valori in multimi date.

Definitia I.4.2. Predicatele p(z,y,z, ), q(x,y,z, ) se numesc echivalente daca, oricare ar fi valorile pe care le iau x,y,z, in unul si acelasi domeniu, propozitiile corespunzatoare au aceleasi valori de adevar. Scriem p(z,y,z, )- q(x,y,z, ).

I.5. Cuantificatori

Definitia I.5.1. Fie p(x), cu x- M, un predicat. Daca exista (cel putin) un element x'- M, astfel incat propozitia p(x') este adevarata, atunci scriem - xp(x), (- x)p(x) sau (- x- M)p(x). Simbolul - se numeste cuantificator existential si se citeste "exista".

Definitia I.5.2. Fie p(x) cu x- M, un predicat. Daca p(x) este o propozitie adevarata pentru orice x- M, atunci scriem - xpx, (- x)p(x) sau (- x- M)p(x). Simbolul - se numeste cuantificator universal si se citeste "oricare ar fi".

Proprietatea de comutativitate a cuantificatorilor:

1. (- x)(- y)p(x,y) - (- y)(- x)p(x,y);

2. (- x)( - y)p(x,y) - (- y)( - x)p(x,y);

Reguli de negare:

1. - ((- x)p(x)) - ((- x)- (p(x));

2. - ((- x)p(x)) - ((- x)- (p(x));

3. - ((- x)(- y)p(x,y))- ((- x)(- y)- p(x,y));

4. - ((- x)( - y)p(x,y))- (( - x)( - y)- p(x,y));

I.6. Metoda de demonstratie prin reducere la absurd

Aceasta metoda se bazeaza pe tautologia (p- q) - (non p- non q), care ne arata ca pentru a demonstra ca p- q, este totuna cu a demonstra ca non p- non q.

I.7. Proprietati fundamentale ale operatorilor logici

Oricare ar fi propozitiile p,q,r, avem:

1. non(non p) - p;

2. (p- q) - (q- p) (comutativitatea conjunctiei);

3. ((p- q)- r) - (p- (q- r)) (asociativitatea conjunctiei);

4. (p- q) - (q- p) (comutativitatea disjunctiei);

5. ((p- q) - r) - (p- (q- r)) (asociativitatea discjunctiei);

6. ((p- q)- (q- r))- (p- r) (tranzitivitatea implicatiei);

7. non(p- q) - (non p)- (non q) legile lui de Morgan;

non(p- q) - (non p)- (non q)

8. (p- (q- r)) - ((p- q)- (p- r)) conjunctia este distributiva in raport cu disjunctia si

(p- (q- r)) - ((p- q)- (p- r)) disjunctia este distributiva in raport cu conjunctia

II. Multimi

Moduri de definire a multimilor. Multimile se definesc fie prin indicarea elementelor lor (de pilda {0,1,3} sau {x,y,z}), fie prin specificarea unei proprietati caracteristice a elementelor lor (de exemplu {x- R- x2 - 3x + 2 = 0}).

Multimile se noteaza cu litere mari: A, B, C, X, Y, Z, iar elementele lor cu litere mici: a, b, c,

Apartenenta unui element la o multime. Daca un element a apartine unei multimi A, acesta se noteaza aa si se citeste "a apartine lui A".

Definitie. Multimea vida este multimea care nu are nici un element. Se noteaza cu -