Medii de Programare

CAPITOLUL 1.

ELEMENTE DE LOGICĂ MATEMATICĂ ŞI ALGEBRĂ BOOLEANĂ

1.1. Calculul propoziţiilor

1.1.1. Noţiunea de propoziţie

DEFINIŢIA 1.1. Se numeşte propoziţie un enunţ (un ansamblu de cuvinte cărora li s-a dat un sens) despre care se ştie că este sau adevărat sau fals, însă nu simultan şi una şi alta.

Exemple de propoziţii:

1) În orice triunghi suma unghiurilor sale este egală cu 180o;

2) 3+2=5;

3) 2>5;

4) Balena este un mamifer.

5) Planeta Saturn este satelit al Pamântului.

Propoziţiile 1), 2) şi 4) sunt adevărate dar 3) şi 5) sunt false.

O clasă foarte largă de propoziţii adevărate o constituie teoremele din matematică.

Contraexemple (enunţuri care nu sunt considerate propoziţii):

1) x+2=5; (enunţurile cu variabile sunt predicate)

2) Deschide uşa !; (enunţ imperativ)

3) Numărul x divide numărul y; (predicat)

4) Atomul de aur este galben. (enunţ absurd)

1.1.2. Valoare de adevăr

Notăm cu P2 mulţimea propoziţiilor definite după definiţia 1.1.

DEFINIŢIA 1.2. Funcţia v : P2 {0,1} se numeşte funcţia valoare de adevăr. Fiecărei propoziţii din mulţimea propoziţiilor P2 i se ataşează valoarea 1 dacă propoziţia este adevărată, şi valoarea 0 dacă este falsă.

De obicei se vor nota propoziţiile prin litere mici: p,q,r ... şi cu v(p), v(q), v(r)... valorile lor de adevăr.

1.1.3. Operatori (operaţii cu propoziţii)

Cu ajutorul operatorilor definiţi în continuare se pot construi propoziţii compuse.

Negarea propoziţiilor. Negarea propoziţiei este propoziţia "non p", care se notează !p şi care este adevărată când p este falsă şi falsă când p este adevărată.

Valoarea de adevăr a propoziţiei !p este dată în tabela următoare:

Conjucţia propoziţiilor. Conjucţia propoziţiilor p,q este propoziţia care se citeşte "p şi q", notată cu

pΛq, care este adevărată atunci şi numai atunci când fiecare din propoziţiile p, q este adevărată.

Valoarea de adevăr a propoziţiei pΛq este dată în tabela următoare:

Disjuncţia propoziţiilor. Disjuncţia propoziţiilor p, q este propoziţia care se citeşte "p sau q" (notată pVq) şi care este adevărată, atunci şi numai atunci când este adevărată cel puţin una dintre propoziţiile p, q.

Valoarea de adevăr a propoziţiei pVq este dată în tabela următoare:

Implicaţia propoziţiilor. Să considerăm propoziţia compusă ( p)Vq a cărei valoare de adevăr rezultă din tabela urmatoare

Propoziţia (!p)Vq se notează p q şi se numeşte implicaţia propoziţiilor p,q (în acestă ordine); p este ipoteza iar q este concluzia.

Observăm că (!p)Vq este falsă atunci şi numai atunci când p este adevărată şi q falsă, în celelalte cazuri fiind adevărată.

Echivalenţa propoziţiilor. Cu propoziţiile p, q putem forma propoziţia compusă (pq) Λ (qp) care se notează p şi se citeşte "p dacă şi numai dacă q". Din tabela următoare se vede că propoziţia p q este adevărată atunci şi numai atunci când p şi q sunt în acelaşi timp adevărate sau false.