|
|
|
Calculul propozitional este acea parte a logicii care se ocupa cu analiza propozitiilor din punct de vedere al compunerii lor corecte cu ajutorul operatiilor logice si al studiului valorilor de adevar pentru enunturile compuse in acest fel. Se poate vorbi despre un limbaj al calculului propozitional, care este un limbaj formal, oferind o prima posibilitate de a formaliza limbajul natural (completarea facandu-se prin limbajul calculului cu predicate).
Orice limbaj presupune existenta unui alfabet, care precizeaza simbolurile folosite, a unei sintaxe stabilind cum pot fi combinate in limbajul respectiv simbolurile admise si a unei semantici, stabilind semnificatia combinatiilor admise de sintaxa.
1. Sintaxa calculului propozitional
Numim alfabetul calculului propozitional multimea Sp = Sp = V L , unde V este o multime infinit numarabila de simboluri, care se numesc variabile propozitionale. Acestea vor fi notate cu p, q, r, eventual cu indici p1, p2, . . ., iar L = este multimea operatiilor logice.
Numim cuvant peste un alfabet S o succesiune finita de elemente din S. Multimea tuturor cuvintelor peste alfabetul S se noteaza cu S*. Ne vor interesa cuvintele peste alfabetul calculului propozitional, multimea acestora notandu-se cu Sp*. Elementele multimii Sp* le vom nota cu A, B, C etc.
Un cuvant A Sp* se numeste formula in calculul propozitional (notam multimea formulelor in calculul propozitional cu Fp) daca si numai daca indeplineste una din conditiile:
1) A V (A este o variabila propozitionala);
2) A = (7 B) unde B Fp
3) A = (B # C) unde B, C Fp iar # L .
Se poate observa ca definitia de mai sus este una de tip recursiv, deoarece entitatea definita este descrisa chiar pe baza entitatii de acelasi tip (in cazurile 2 si 3). Totodata, ea poate fi privita si ca fiind de tip inductiv, in care 1 asigura pasul initial, iar 2 si 3 asigura pasul inductiv. Rezulta ca este formula in calculul propozitional o variabila propozitionala, negatia unei formule scrisa intre paranteze, sau compunerea a doua formule prin una din operatiile logice binare (conjunctie, disjunctie, implicatie sau echivalenta), compunere cuprinsa intre paranteze.
Folosirea stricta a definitiei formulei in calculul propozitional presupune manevrarea unui numar mare de paranteze. Pentru simplitate, A Fp poate fi reprezentata printr-un cuvant mai simplu A', obtinut din A prin renuntarea, omiterea unor paranteze, cu conditia ca din cuvantul redus A' sa se poata reconstitui in mod unic formula A, pe baza urmatoarelor 3 reguli de reconstituire:
1) restabilirea parantezelor se face in ordine pentru: 7, , , , ;
2) daca A Fp atunci cuvantul 77 . . . 7A reprezinta formula (7 (7 (. . . (7A)). . .) );
3) daca A1, A2, . . . An Fp si # atunci cuvantul A1 # A2 #. . . #An
reprezinta formula (. . . ((A1 # A2) #. . . #An
Regula 1) de mai sus fixeaza prioritatea operatiilor in calculul propozitional - prioritara este negatia, urmata de conjunctie, disjunctie, implicatie si echivalenta, iar regulile 2) si 3) arata ca reconstituirea se face de la stanga la dreapta. Practic, se cauta de la stanga la dreapta cea mai prioritara operatie logica in jurul careia se poate reconstitui o formula, se reconstituie, s.a.m.d.
2. Semantica pentru calculul propozitional
Se numeste evaluare a formulelor in calculul propozitional extensia unica a oricarei functii v : V la Fp, extensie pe care o vom nota tot cu v, v : Fp (este vorba despre prelungirea obisnuita din teoria functiilor, a functiei v, definita pe multimea variabilelor propozitionale, la multimea formulelor in calculul propozitional).
In logica, prin propozitie intelegem un enunt care poate fi ori adevarat ori fals. Oricarei propozitii i se asociaza o valoare de adevar: este sau adevarata - si atunci spunem ca are valoarea de adevar 1 - sau este falsa - si atunci spunem ca are valoarea de adevar 0.
Nici o propozitie nu este in acelasi timp si adevarata si falsa.
Propozitiile interogative sau exclamative ale limbii nu sunt propozitii in logica. De asemenea, definitiile nu sunt propozitii. De exemplu, enuntul 'un numar intreg divizibil cu 2 se numeste numar par' nu este o propozitie. Insa enuntul "orice numar par este divizibil cu 2" este propozitie si are valoarea de adevar 1.
Operatori logici
Cu ajutorul operatorilor logici, din una sau doua propozitii date se pot forma noi propozitii a caror valoare de adevar depinde numai de valoarea de adevar a propozitiilor date. Vom indica aceasta valoare de adevar cu ajutorul unor tabele: in partea stanga a tabelului apar toate valorile de adevar posibile ale propozitiilor date iar in partea dreapta, valoarea de adevar a propozitiei nou formate.
Operatorii logici sunt: negatia, disjunctia, conjunctia, implicatia, echivalenta.
|
|
a
|
b
|
non a
|
1
|
0
|
0
|
0
|
1
|
1 |
Negatia unei propozitii a este propozitia 'non a' sau 'nu este adevarat ca a' care se noteaza a. Propozitia a este adevarata daca si numai daca propozitia a este falsa. Valoarea de adevar a propozitiei a in este indicata in tabelul alaturat (tabela de adevar a negatiei):
Negatia
Exemplu: Propozitia b = 'nu este adevarat ca 9 este numar par' care coincide cu '9 nu este numar par' este negatia propozitiei
a = '9 este numar par'
Propozitia a este falsa si propozitia b = a este adevarata.
Disjunctia propozitiilor
|
|
a
|
b
|
a b
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0 |
Disjunctia propozitiilor a si b este propozitia 'a sau b' care se noteaza a b. Propozitia a b este falsa daca si numai daca ambele propozitii a si b sunt false. Tabela de adevar a disjunctiei este prezentata in tabelul alaturat.
Exemplu: Propozitia: '7 este numar prim sau 6 este numar impar' este adevarata. Fiind disjunctia a doua propozitii dintre care una este adevarata.
Conjunctia propozitiilor
|
|
a
|
b
|
a b
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0 |
Conjunctia propozitiilor a si b este propozitia 'a si b' care se noteaza a b. Propozitia a b este adevarata daca si numai daca ambele propozitii a si b sunt adevarate. Tabela de adevar a conjunctiei este prezentata in tabelul alaturat.
Exemplu: Propozitia: '7 este numar prim si 6 este numar impar' este o propozitie falsa fiind conjunctia a propozitiilor: '7 este numar prim' si '6 este numar impar", prima fiind adevarata iar a doua falsa.
Implicatia propozitiilor
|
|
a
|
b
|
a b
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1 |
Implicatia propozitiilor a si b este propozitia 'a implica b' care se mai poate citi 'daca a atunci b' sau 'din a rezulta b' si se noteaza a b. Propozitia a b se mai numeste si implicatia de sursa a si capat b, Ea este o propozitie falsa, daca si numai daca sursa este o propozitie adevarata, iar capatul o propozitie falsa. Tabela de adevar a implicatiei este prezentata in tabelul alaturat.
Exemplu: Propozitia: 'daca 5 este numar prim, atunci 6 + 2 = 4' este o propozitie falsa fiind o implicatie a carei sursa este o propozitie adevarata, in timp ce capatul este o propozitie falsa.
Echivalenta propozitiilor
|
|
a
|
b
|
a b
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1 |
Echivalenta propozitiilor a si b este propozitia 'a echivalent cu b' care se mai poate citi 'a daca si numai daca b' si se noteaza a b. Propozitia a b este o propozitie adevarata daca si numai daca propozitiile a si b au aceeasi valoare de adevar. Tabela de adevar a echivalentei este prezentata in tabelul alaturat.
Exemplu: Propozitia: '4 > 5 daca si numai daca 1 + 1 = 3' este o propozitie adevarata, fiind echivalenta a doua propozitii ambele false.
Daca propozitia a b este adevarata, scriem a b si spunem ca propozitiile a si b sunt echivalente logic.
Calculul propozitional studiaza din punct de vedere
logic expresiile obtinute din literele p, q, r, etc,
cu ajutorul operatorilor logici: 
dupa anumite reguli. Literele p, q, r, , se numesc
variabile propozitionale sau formule elementare iar expresiile
obtinute din ele cu ajutorul operatorilor logici se numesc formule,
regulile de formare a formulelor fiind urmatoarele:
variabilele propozitionale p, q, r, , sunt formule;
daca A si B sunt formule, atunci
sunt formule.
Exemplu: Expresiile de mai jos sunt formule ale calculului propozitional
p, (p). ((r
s) (p)), (r
(s (p)), ((p
(q)
(p q))
Deoarece abundenta parantezelor in
unele formule devine greoaie, perechea de paranteze exterioare nu se mai scrie,
iar ordinea in care se aplica operatorii logici este urmatoarea:
Astfel, expresiile date ca exemple mai sus se scriu astfel:
p p. r s p, r (s p), p q (p q
Daca intr-o formula in scrierea careia intra variabilele propozitionale p, q, r, etc inlocuim aceste variabile cu diverse propozitii, obtinem o noua propozitie a carei valoare de adevar depinde numai de valoarea de adevar atribuita variabilelor propozitionale componente. O formula a calculului propozitional se numeste lege, tautologie sau formula identic adevarata daca orice valoare de adevar ar avea variabilele propozitionale care intra in compunerea sa, valoarea de adevar a propozitiei obtinute este 1.
Pentru a demonstra ca o anumita formula a calculului propozitional este o tautologie, atribuim variabilelor propozitionale care intra in compunerea ei valori de adevar in toate modurile posibile si calculam de fiecare data, pe baza tabelelor de adevar ale operatorilor logici, valoarea de adevar a formulei; daca de fiecare data valoarea de adevar obtinuta este 1, inseamna ca formula respectiva este o tautologie.
Exemple:
Legea tertului exclus
a
a
aa
1
0
1
0
1
1
Legea negarii implicatiei:
a
b
ab
b
ab
ab
ab
ab
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
1
0
0
0
1
0
0
1
1
0
0
1
Legea silogismului:
a
b
c
ab
bc
(abbc
a c
abca c
1
1
1
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
In virtutea acestor tautologii putem scrie:
p q) pq
pqq r (pr)
Alte exemple de tautologii, ale caror demonstratii se pot realiza in mod analog, sunt:
p q
(legea de reflexivitate);
p q p
pq p
(legile de idempotenta);
pq qp
pq q p
(legile de comutativitate);
pqr
pqr
pq
rpqr
(legile de asociativitate);
pq
rpq)pr)
pq
rpq)pr)
(legile de distributivitate);
p p
(legea dublei negatii);
pqqp
p qqp
pq)pq
pq p
qqp
ppqq
pqp
rpr
pqpq
p
q)pq
legile lui De Morgan
Legile calculului propozitional si in special cele date mai sus ca exemple sunt importante deoarece pe baza lor se fac rationamentele logice si deci demonstratiile in matematica.
