ELEMENTE DE

LOGICA MATEMATICA

D 1. ELEMENTE DE CALCULUL PROPOZITIILOR

Notiunea de propozitie. Se numeste propozitie un enunt despre care stim ca este advarat sau fals, insa nu si una alta simultan.

Exemple. Consideram enunturile: 1)In orice triunghi suma unghiurilor sale este egala cu 180s ; 2) ,,3+2=5''; 3)''2>5'' 4) Balena este un mamifer'' ; 5) Planeta Venus este satelit al Pamantului''.

Toate aceste enunturi sunt propozitii, deoarece despre fiecare putem sa stim daca este adevarata sau falsa. De exemplu 1),2) si 4) sunt propozitii adevarate, iar 3) si 5) sunt propozitii false.

Observatie. O clasa foarte larga de propozitii adevarate o constituie teoremele din matmatica.

Sa consideram enunturile 1),,x+2=5'' ; 2)''x-1<4'' 3)''Deschide usa!'' ; 4)''Numarul x divide numarul y'' ; 5)''Atomul de aur este galben'.

Se observa ca 1), 2), 3), 4) si 5) sunt enunturi pentru care conditia de mai sus(de afi adevarat sau fals) nu este indeplinita. Mai exact enunturile 1), 2) si 4) au caracter variabil, enuntul 3) este o porunca despre care este lipsit de sens sa afirmam ca este adevarata sau falsa, enuntul 5) este absurd, deoarece e lipsit de sens sa vorbim despre culoarea unui atom.

Valoare de adevar. Daca o propozitie este adevarata, spunem ca ea are valoarea de adevar ,adevarul' si vom nota valoarea de adevar, in acest caz, prin semnul 1 sau A; cand propozitia este falsa spunem ca ea are valoarea de adevar ,falsul' si vom nota valoarea de adevar prin semnul 0 sau F.

Observatie. 0 si 1 sunt aici simboluri fara inteles numeric.

Vom nota propozitiile cu literele p, q, r sau p₁, p₂,, p₃ . Acestea se pot compune cu ajutorul asa-numitilor conectori logici ,non' , ,si' , ,sau' dand propozitii di ce in ce mai complexe.

Negatia propozitiilor. Negatia propozitiei p este propozitia non p care se noteaza p si care este adevarata cand p este falsa si falsa cand p este adevarata. Valoarea de adevar a propozitiei p este data in tabelul urmator:

De exemplu, consideram propozitia p: Balena este un mamifer. Negatia p este propozitia : Non balena este un mamifer sau, in limbajul obisnuit : Balena nu este un mamifer. In acest caz p este o prpozitie falsa

Conjunctia propozitiilor. Conjunctia propozitiilor p, q este propozitia care se citeste p si q, notata p q si care este adevarata atunci si numai atunci cand fiecare din propozitiile p, q este adevarata.

De exemplu, sa consideram propozitiile p: ,2+4+6' si q: ,Luna este satelit al Pamantului'. In acest exemplu p q este o propozitie adevarata deoarece p, q sunt amandoua adevarate. Deseori in loc de p q se mai foloseste notatia p&q.

Disjunctia propozitiilor. Disjunctia propozitiilor p, q este propozitia care se citeste p sau q, notata p v q, si care este adevarata atunci si numai atunci cand este adevarata cel putin una din propozitiile p, q.

De exemplu consideram propozitiile p: 2>3 si q: balena este un peste. Propozitia p v q este o propozitie falsa deoarece ambele propozitii sunt false.

Propozitiile care se obtin din prpozitiile p, q, r, numite propozitii simple, aplicand de un numar finit de ori conectorii logici '' ʌ , v'' se vor numi propozitii compuse. Calculul propozitiilor studiaza propozitiile compuse din punctul de vedere al adevarului sau falsului in raport cu valorile logice ale propozitiilor simple care le compun.

Implicatia propozitiilor. Sa consideram propozitia compusa ( ﾡ p) v q a carei valoare de adevar rezulta din tabela urmatoare:

Observam ca propozitia compusa ( ﾡ p) v q este falsa atunci si numai atunci cand p este adevarata si q falsa, in celelalte cazuri fiind adevarata.

Propozitia compusa ( ﾡ p) v q se noteaza p→q si se citeste daca p atunci q sau p implica q. Ea se numeste implicatia propozitiilor p, q ( in aceasta ordine).In implicatia p→q , p se numeste ipoteza sau antecedentul implicatiei, iar propozitia q se numeste concluzia sau consecventul implicatiei

Echivalenta propozitiilor Cu propozitiile p, q putem forma propozitia compusa (p→q) (q→p), care se noteaza p↔q si se citeste p daca si numai daca q.

Formule echivalente in calculul propozitional

Asa cum in clasele mici cu literele a, b, c, si simbolurile +, ,-, : , putem forma expresiile algebrice, asa si in calcul propozitional cu literele p, q, r, (sau p₁ , p₂ ,p₃ ,) si cu simbolurile conectorilor logici: ,→,↔ , putem sa formam diverse expresii numite formule ale calculului proportional.

Formulele calculului proportional le notam cu literele α, β, γ, δ, .

Exemple: p⋁ q, (p⋁ q) ⋀ r, p⋀q) p⋀q) p⋁ r) → p, ﾡ p →q sunt formule ale calculului propozitional.

Data o formula α = α ( p, q, r, ) in scrierea careia intra literele p, q, r, ori de cate ori inlocuim literele p, q, r, , cu diverse propozitii obtinem o noua propozitie

( adevarata sau falsa ) care se va numi valoarea formulei α pentru propozitiile p, q, r, date.

Observatie Cititorul poate sa faca imediat legatura cu valoarea unei expresii algebrice pentru diverse valori numerice date literelor ce o compun.

O formula α ( p, q, r, ) care are valoarea o propozitie adevarata indiferent cum sunt propozitiile p, q, r, se numeste formula identic adevarata sau tautologie.

Doua formule,α si β, in scrierea carora intra literele p,q, r, se zic echivalente daca si numai daca pentru orice inlocuire a literelor p, q, r, cu diverse propozitii, valorile celor doua formule sunt propozitii (compuse) care au aceeasi valoare de adevar.

Cand doua formule α si β, sunt echivalente scriem α ≡ β .

D      ELEMENTE DE CALCULUL predicatelor

Notiunea de predicat are o importanta deosebita in matematica.. Fara a exagera, aproape orice teorema din matematica este un enunt ce contineunul sau mai multe predicate.

Un enunt care depinde de una sau mai multe variabile si are proprietatea ca pentru orice ,valori' date variabilei corespunde o propozitie adevarata sau falsa se numeste predicat sau propozitie cu variabile. Predicatele sunt unare, binare, ternare etc., dupa cum depind respect de 1, 2, 3 variabile. Ori de cate ori definim un predicat trebuie sa indicam si multimile in care variabilele iau valori.

Cuantificatorul existential ( ) si cuantificatorul universal (

Strans legata de notiunea de predicat apare notiunea de cuantificator. Fie predicatul unar p(x) unde x desemneaza un element oarecare din multimea E. Putem forma enuntul: exista cel putin un x din E astfel incat p(x), care noteaza ( x)p(x). Acest enunt este o propozitie care este adevarata cand exista cel putin un element x₀ din E astfel incat propozitia p(x₀) este adevaratasi este falsa cand nu exista nici un x₀ din E astfel incat p(x₀) sa fie adevarata. Cu predicatul p(x) putem forma si enuntul :oricare ar fi x din E are loc p(x) care se noteaza ( x) p(x). Acest enunt este o propozitie care este adevarata daca pentru orice element x₀ din E p(x₀) este adevarata, fiind falsa in cazul in care exista cel putin un x₀ din E pentru care E p(x₀) este falsa.

Echivalenta predicatelor. Doua predicate p( x, y, z), q(x, y, z) se zic echivalente si scriem p( x, y, z) q(x, y, z) daca oricum am alege valorile variabilelor x_{0 ,} y_0, z₀ pentru care propozitia p(x_{0 ,} y_0, z₀ ) si q(x_{0 ,} y_0, z₀ ) au aceeasi valoare de adevar. Daca oricum am alege valorile variabilelor x_{0 ,} y_0, z₀ pentru care propozitia p(x_{0 ,} y_0, z₀ ) este adevaratezulta csi propozitia q(x_{0 ,} y_0, z₀ ) este adevarata, vom scrie p( x, y, z) q(x, y, z) Se vede ca p( x, y, z) q(x, y, z) atunci si numai atunci cand p( x, y, z) q(x, y, z) si q( x, y, z) p(x, y, z)

Reguli de negatie. Fie p(x) un predicat unar, unde x desemneaza un element din multimea E. Atunci :

p(x)) ≡( x) p(x)

x) p(x) ≡( x) p(x)

(aici semnul ≡ desemneaza faptul ca cele doua prop. au aceesi valoare de adevar)

D 3. TEOREMA CONTRARA

1.Structura unei teoreme. O clasa foarte larga de propozitii adevarate o constituie teoremele din matematica. Exemple : 1) In orice triunghi, suma unghiurilor sale este egala cu 180^o 2)In orice triunghi, lungimea oricarei laturi este mai mica decat suma lungimilor celorlalte doua si mai mare ca diferenta lor 3) In orice triunghi dreptunghic patratul lungimii ipotenuzei este egal cu suma patratelor lungimilor catetelor. Fiecare teorema stabileste ca un obiect matematic sau un ansamblu de obiecte matematice poseda o anumita proprietate. Cum se obtin teormele? Studiind matematica elementara se poate constata ca toate teoremele ei se deduc prin demonstratii, adica printr-un sir de rationamente logice, sau cum se mai spune, prin silogisme, din cateva propozitii fundamentale numite axiome, care se accepta a fi adevarate fara demonstratie.

Aproape orice teorema se poate enunta sub forma ,,daca., atunci.''. Partea intai, care incepe cu cuvantul daca se numeste ipoteza teoremei, partea a doua, cea care incepe cu cuvantul atunci se numeste concluzia teoremei.

Sa luam de exemplu teorema : ,, intr-un triunghi dreptunghic patratul lungimii ipotenuzei este egal cu suma patratelor lungimilor catetelor''. Aceasta teorema se poate pune sub forma : ,,daca ABC este un triunghi dreptunghic, atunci patratul lungimii ipotenuzei este egal cu suma patratelor lungimilor catetelor''. Aici ipoteza este ,, ABC este un triunghi dreptunghic'' iar concluzia este ,,patratelor lungimii ipotenuzei este egal cu suma patratelor lungimilor catetelor''.

Teoremele se pot pune sub forma implicatiei: (1) p(x, y, z.) q(x, y, z) care reprezinta notatia prescurtata a propozitiei (1') x)( y)( z).. p(x, y, z.)→ q(x, y, z) In implicatia (1) predicatul p(x, y, z.) constituie ipoteza teoremei, iar q(x, y, z) constituie concluzia teoremei.

2.Teorema contrara. Sa consideram urmatoarea teorema: ,,un patrulater este pararelogram, atunci diagonalele sale se taie in parti egale''. Din aceasta teorema formam urmatorul enunt : daca un patrulater nu este paralelogram, atunci diagonalele sale nu se taie in parti egale. Acest enunt este o propozitie adevarata, deci o teorema. Cum am obtinut acesta noua teorema? Se observa ca ea s-a obtinut din prima, inlocuind ipoteza si concluzia prin negatiile lor

Data o teorema, propozitia care se obtine din teorema data inlocuind ipoteza si concluzia ei prin negatiile lor se numeste contrara teoremei date . In cazul ca aceasta propozitie este adevarata ea se numeste teorema contrara a teoremei date.

Observatie. Pentru a enunta corect contrara teoremei, este foarte important sa stim sa negam corect.

In termeni ai calculului cu predicate daca

p(x, y, z.) q(x, y, z) este teorema data, atunci contrara teoremi este propozitia (2) x)( y)( z)..( p(x, y, z.)→ q(x, y, z))

In cazul ca (2) este o propozitie adevarata atunci (2) se scrie sub forma

p(x, y, z.) q(x, y, z)

si constituie teorema contrara a teoremei (1).