Logica predicatelor Un predicat este un enunt care depinde de una sau mai multe variabile si care are proprietatea ca pentru anumite valori ale variabilelor (valori care pot fi de exemplu numere sau, in general, elemente ale unei multimi) devine o propozitie. Un predicat care depinde de n variabile se numeste predicat n-ar. In particular, pentru n = 1, 2, 3, avem predicate unare, binare si respectiv ternare. Exemple Enuntul: 57948rhm41pce5f a(n) = "3 este un divizor al lui n" este un predicat care depinde de variabila n. Pentru fiecare numar intreg n, a(n) este o propozitie. si anume, daca n este un numar intreg de forma 5k, k numar intreg, atunci a(n) este o propozitie adevarata si pentru toate celelalte valori ale lui n, a(n) este o propozitie falsa. Enuntul: 57948rhm41pce5f a(x, y) = "x + y = 2" hc948r7541pcce este un predicat binar. Pentru orice doua numere reale x si y, a(x, y) este o propozitie. Propozitia a(1, 1) obtinuta dand lui x si y valorile x = 1, y = 1 este o propozitie adevarata, in timp ce propozitia a(0, 1) obtinuta dand lui x si y valorile x = 0, y = 1 este o propozitie falsa. Sa consideram doua predicate unare a(x) si b(x). Cu ajutorul operatorilor logici putem construi si alte predicate unare, anume: a(x), a(x) Ú b(x), a(x) Ù b(x), a(x) ® b(x), a(x) « b(x) De exemplu, predicatul a(x) Ù b(x) este acel predicat c(x) care, pentru fiecare valoare a variabilei x coincide cu propozitia a(x) Ù b(x). De asemenea, putem forma predicatele binare: a(x) Ú b(y), a(x) Ù b(y), a(x) ® b(y), a(x) « b(y) Consecinta logica Predicatul b(x) se numeste consecinta. logica a predicatului a(x) si scriem a(x) Þ b(x) daca pentru orice valoare a variabilei x, propozitia a(x) ® b(x) este adevarata. Tinand. seama de definitia implicatiei, avem a(x) Þ b(x) daca si numai daca pentru orice valoare a variabilei x, propozitia b(x) este adevarata de fiecare data cand propozitia a(x) este adevarata. Exemplu Considerand predicatele: a(x) = "x > 0" si b(x) = "x2 > 0" care au sens pentru x numar real, avem: a(x) Þ b(x) Echivalenta logica Predicatele a(x) si b(x) sunt echivalente logic si scriem a(x) Û b(x) daca pentru orice valoare a variabilei x propozitia a(x) « b(x) este adevarata. Conform definitiei echivalentei, avem a(x) Û b(x) daca si numai daca pentru orice valoare a variabilei x, propozitiile a(x) si b(x) au aceeasi valoare de adevar. Exemplu Considerand predicatele: a(x) = "x < 0" si b(x) = "x 0" care au sens pentru x numar real, avem: a(x) Û b(x) si a(x) Û b(x) Relatiile de consecinta logica si echivalenta logica pot fi definite si intre predicate n-are, unde n > 2, intr-un mod evident. De exemplu, daca consideram predicatele: x > y, y > 0 si x2 > y2 care au sens cand x si y sunt numere reale, avem: x > y, y > 0 Þ x2 > y2 De asemenea: (x – y = 2) Û x – y ¹ 2. In matematica, orice teorema se formuleaza – de regula – spunand ca un anumit predicat este consecinta logica a unui alt predicat, deci are forma: a(x1, x2, ..., xn) Þ b(y1, y2, ..., yn) Exemple · Teorema "Inaltimile unui triunghi sunt concurente" are forma: a(x, y, z) Þ b(x, y, z) unde a(x, y, z) este predicatul "x, y, z sunt inaltimile unui triunghi" si b(x, y, z) este predicatul "x, y, z sunt concurente". · Teorema "Diagonalele unui romb sunt perpendiculare"are forma: a(x, y) Þ b(x, y) unde a(x, y) este predicatul "x, y sunt diagonalele unui romb" si b(x, y) este predicatul "x, y sunt perpendiculare". Propozitii universale si existentiale Propozitii universale Fie a(x) un predicat unar. Propozitia "pentru orice valoare permisa a variabilei x, a(x) este o propozitie adevarata" se numeste propozitia universala asociata predicatului a(x) si se noteaza ("x)a(x). De exemplu, daca a(x) si b(x) sunt doua predicate, avem: a(x) Þ b(x) daca si numai daca propozitia: ("x)a(x) ® b(x) este adevarata. De asemenea, a(x) Û b(x) daca si numai daca propozitia: ("x)a(x) « b(x) este adevarata. Considerand predicatul: "x2 > 0", unde x este un nmnar real, propozitia: ("x)(x2 ³ 0) este o propozitie adevarata. Propozitia: ("x)(x2 > 0) nu este insa o propozitie adevarata. Intr-adevar, avem predicatul: a(x) = "x2 > 0", unde x este un numar real si propozitia a(0) nu este o propozitie adevarata. Propozitii existentiale Propozitia existentiala asociata unui predicat unar oarecare a(x) este "exista cel putin o valoare x0 a variabilei x astfel ca a(x0) sa fie o propozitie adevarata" si se noteaza ($x)a(x). De exemplu, considerand predicatul: a(x) = "x + 2 = 0", unde x este numar intreg, propozitia: ($x)(x + 2 = 0) este adevarata, deoarece pentru x = –2, propozitia a(–2) = "–2 + 2 = 0" este adevarata. Putem insa considera si predicatul: a(x) = "x + 2 = 0", unde x este numar natural. Atunci, propozitia ($x)a(x) nu este o propozitie adevarata. Sa presupunem predicatul a(x) definit numai pentru un numar finit de valori ale variabilei x, anume x1, x2,..., xn. Atunci: ("x)a(x) Û a(x1) Ù a(x2) Ù ... Ù a(xn) ($x)a(x) Û a(x1) Ú a(x2) Ú ... Ú a(xn) Tinind seama de legile lui De Morgan, rezulta: ("x)a(x) Û a(x1) Ú a(x2) Ú ... Ú a(xn) Û ($x)(a(x)) In mod analog: ($x)a(x) Û ("x)(a(x)) Regulile de negatie stabilite mai sus, sunt valabile si in cazul general. Deci, pentru orice predicat unar a(x), avem: ("x)a(x) Û ($x)(a(x)) ($x)a(x) Û ("x)(a(x)) Fie a(x, y) un predicat binar. Atunci ("x)a(x, y) este un predicat unar, care depinde de variabila y si, prin urmare, putem forma propozitiile: ("y)("x)a(x, y) ($y)("x)a(x, y) si In mod analog, ($x)a(x, y) este un predicat unar care depinde de variabila y, deci, putem forma propozitiile: ("y)($x)a(x, y) ($y)($x)a(x, y) Exemplu Sa consideram predicatul binar a(x,y) = "x < y", unde x, y sunt numere reale. Propozitia: ("y)("x)a(x, y) este o propozitie falsa deoarece, de exemplu, a(2,1) este o propozitie falsa. Propozitia: ($y)("x)a(x, y) este o propozitie falsa deoarece pentru o valoare oarecare y = y0 a variabilei y0, propozitia a(y0 + 1, y0) sunt insa propozitii adevarate. Regulile de negatie pentru propozitiile de tip universal-existential asociate predicatelor binare se obtin din regulile de negatie pentru predicatele unare. De exemplu: (("y)($x)a(x.y)) Û ($y)(($x)a(x.y)) Û ($y)("x)(a(x.y)) (($y)($x)a(x.y)) Û ("y)(($x)a(x.y)) Û ("y)($x)(a(x.y)) Majoritatea definitiilor din matematica sunt predicate care se construiesc cu ajutorul altor predicate deja definite. Astfel, daca x | y sunt numere intregi, predicatul x | y (adica "x divide pe y") inseamna ($q)(y = qx). Spunem ca predicatul x | y este echivalent prin definitie cu predicatul ($q)(y = qx) si scriem:
Analog, daca x si y sunt numere naturale, avem definitia:
Pentru a exemplifica regulile de negatie stabilite mai sus, sa explicitam si negatia predicatelor x | y si "x este numar prim", adica, sa explicitam ce inseamna ca "x nu divide pe y" (se scrie x y) si "x nu este numar prim": x y Û ("q)(y ¹ qx) "x nu este numar prim" Û (x = 0) Ú (x = 1) Ú ($y)(y | x Ù y ¹ 1 Ù y ¹ x). Teorema directa In matematica, o teorema este o propozitie adevarata care stabileste ca unul sau mai multe obiecte matematice poseda o anumita proprietate. De regula orice teorema se poate enunta sub forma unei propozitii conditionale (din punct de vedere gramatical) construita cu ajutorul cuvintelor "daca... atunci...". Exemplu Teorema lui Pitagora: "Intr-un triunghi dreptunghic suma patratelor catetelor este egala cu patratul ipotenuzei" se poate pune sub forma: "daca x este ipotenuza si y, z catetele unui triunghi dreptunghic, atunci x2 = y2 – z2". Asa cum am mai vazut, forma generala a unei teoreme este: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) unde a(x1, x2, ..., xn) si b(x1, x2, ..., xn) sunt predicate n-are. Predicatul a(x1, x2, ..., xn) se numeste ipoteza teoremei, iar b(x1, x2, ..., xn) se numeste concluzia teoremei. Prin demonstratia unei teoreme: a(x1, x2, ..., xn) Þ b(x1, x2, ..., xn) intelegem un sir de propozitii adevarate de forma: ai(x1, x2, ..., xn) Þ ai+1(x1, x2, ..., xn) cu i = 1, 2, ..., k – 1, unde ai = a si ak = b. Aceste propozitii sunt teoreme deja demonstrate sau axiome (teoreme care se accepta fara demonstratie) sau sunt propozitii adevarate in virtutea legilor calculului propozitional (rationamente logice). Teorema initiala a(x1, x2, ..., xn) Þ b(x1, x2, ..., xn) este adevarata in virtutea regulii silogismului. De obicei acest sir de propozitii nu se indica explicit (demonstratiile ar deveni prea greoaie si dificil de urmarit), insa el trebuie avut in vedere. Exemplul 1: Sa consideram teorema: "Daca d este numar intreg ireductibil si divide produsul a doua numere intregi x, y, atunci d divide cel putin pe unul dintre ele". Ipoteza teoremei este predicatul: a(d, x, y) = "d este numar intreg ireductibil si d | xy" iar concluzia este: b(d, x, y) = "d | x sau d | y" Pentru demonstratie, constatam mai intai ca, datorita faptului ca formula: (p Ù q Ùr ® s) ® (p Ù q ® r Ú s) este o tautologie. Deci propozitia p Ù q ® r Ú s este adevarata cand p Ù q Ùr ® s este adevarata. Astfel, este suficient sa demonstram teorema: "Daca d este numar intreg ireductibil, d | xy si d x Þ d | y". Luam: p = "d numar intreg ireductibil"; q = "d | xy"; r = "d | x"; s = "d | y". In virtutea proprietatilor numerelor intregi ireductibile si a celui mai mare divizor comun avem: "d este numar intreg ireductibil si d x" Þ (d, x) = 1 Þ Luam: p = "d este numar intreg ireductibil si d x"; q = "($k)($l)(kyd + Ixy = y)"; r = "d | xy" Conform celor de mai sus, avem p Þ q si deoarece formula: (p ® q) ® (p Ù r ® q Ú r) este o tautologie, avem p Ù r ® q Ú r, adica d este numar intreg ireductibil si d x si d | xy Þ ($k)($l)(kyd + Ixy = y) si d | xy. Evident, avem: ($k)($l)(kyd + Ixy = y) si d | xy Þ d | y Din legea silogismului rezulta: d este numar intreg ireductibil si d x si d | xy Þ a | y si teorema este demonstrata. Bineinteles, uzual nu mai facem apel la tautologiile indicate aici in mod explicit, acestea fiind subintelese. Forma a(x1, x2, ..., xn) Þ b(x1, x2, ..., xn) a unei teoreme trebuie avuta in vedere si in cazurile cele mai simple. De exemplu, teorema: "2 este numar prim" are forma a(x) Þ b(x) unde a(x) este predicatul: "x = 2" si b(x) este predicatul: "x este numar prim". Exemplul 2: Egalitatea:
este o teorema de forma: a(x) Þ b(x) unde:
b(x) = "x = 2" Pentru a demonstra teorema, observam ca:
x3 = 14 – 3x Þ x3 + 3x – 14 = 0 Þ (a – 2)(x2 + 2x + 7) = 0 Þ x = 2, deoarece x este numar real si ecuatia x2 + 2x + 7 = 0 nu are radacini reale. Din acest motiv, un rationament de forma: "ridicam la cub ambii membri ai egalitatii
si obtinem:
adica:
ceea ce este evident", este gresit. Teorema reciproca Sa consideram teorema: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) care exprima faptul ca predicatul b(x1, x2, ..., xn) este consecinta logica predicatului a(x1, x2, ..., xn). Daca si predicatul a(x1, x2,..., xn) este consecinta logica a predicatului b(x1, x2, ..., xn), are loc si teorema: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn), teorema care se numeste reciproca teoremei date. Deci, teorema reciproca a unei teoreme se obtine luand concluzia teoremei date ca ipoteza si ipoteza teoremei date drept concluzie. Bineinteles, daca teorema directa este adevarata, nu este necesar ca si teorema reciproca sa fie adevarata. Daca avem: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) si b(x1, x2,..., xn) Þ a(x1, x2, ..., xn) adica, daca si teorema directa si teorema reciproca sunt adevarate, atunci predicatele a(x1, x2, ..., xn) si b(x1, x2, ..., xn) sunt echivalente logic, deci avem: a(x1, x2, ..., xn) Û b(x1, x2, ..., xn) Exemplu Consideram teorema: "Daca a = b, atunci a3 = b3" unde a si b sunt numere reale. Ea are forma: x = y Þ x3 = y3 Reciproca acestei teoreme este: x3 = y3 Þ x = y adica, "daca a3 = b3 atunci a = b". Bineinteles si teorema directa si teorema reciproca sunt adevarate. Avem deci: x = y Û x3 = y3 Astfel, teorema directa si teorema reciproca se pot contopi intr-un singur enunt: "a = b daca si numai daca a3 = b3". Demonstratiile teoremei directe si a teoremei reciproce se pot face simultan printr-un sir de echivalente logice. Conditie necesara si suficienta In cazul in care: a(x1, x2,..., xn) Û b(x1, x2, ..., xn) se mai spune ca a(x1, x2,..., xn) este conditie necesara pentru b(x1, x2, ..., xn) si ca b(x1, x2, ..., xn) este conditie suficienta pentru a(x1, x2,..., xn). De multe ori apar enunturi care afirma echivalenta logica a doua sau mai multe predicate. De exemplu: fie x si y numere reale. Urmatoarele afirmatii sunt echivalente:
Demonstratia completa a unui astfel de enunt (a unei astfel de teoreme) se poate face fie demonstrand i) Û ii) si i) Û iii), fie demonstrand i) Û ii) Þ iii) Þ i). Teorema contrara Sa consideram teorema: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) care exprima faptul ca predicatul b(x1, x2, ..., xn) este consecinta logica a predicatului a(x1, x2, ..., xn). Daca si predicatul b(x1, x2, ..., xn) este conse-cinta logica a predicatului a(x1, x2, ..., xn), atunci are loc teorema: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) care se numeste contrara teoremei date. Deci, teorema contrara a unei feoreme se obtine inlocuind ipoteza si concluzia teoremei date prin negatiile lor. Exemplu Consideram teorema: "Daca produsul a doua numere reale este zero, atunci cel putin unul din ele este zero". Ea are forma: "xy = 0 Þ x = 0 Ú y = 0" Contrara acestei teoreme este: "xy ¹ 0 Þ x = 0 Ù y ¹ 0" adica, "Daca produsul a doua numere reale este diferit de zero, atunci ambele numere sunt diferite de zero". Metoda demonstratiei prin reducere la absurd Fiind data o teorema: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) putem, forma: Datorita tautologiei: (p ® q) ® (p «q) din calculul propozitional, teorema directa: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) este adevarata daca si numai daca contrara reciprocei sale b(x1, x2, ..., xn) Þa(x1, x2, ..., xn) este adevarata. Pe aceasta observatie se bazeaza metoda demonstratiei prin reducere la absurd, prin care, in loc sa demonstram teorema directa, demonstram contrara reciprocei. Metoda demonstratiei prin reducere la absurd este foarte utila in matematica, deoarece de multe ori demonstratia teoremei directe este foarte dificila. Exemplu: Sa consideram teorema: "Daca x si y sunt numere reale astfel incit x2 + y2 = 0, atunci x = 0 si y = 0". Ea are forma: x2 + y2 = 0 Þ x = 0 Ù y = 0 Contrara reciprocei este teorema: x ¹ 0 Ú y ¹ 0 Þ x2 + y2 ¹ 0 adica: "Daca x si y sunt numere reale si cel putin unul din ele este diferit de zero, atunci x2 + y2 ¹ 0". Am numit teorema orice propozitie adevarata care stabileste ca unul sau mai multe obiecte matematice poseda o anumita proprietate. Dar, de obicei, astfel de rezultate se numesc propozitii si numai rezultatele cele mai importante, cu o semnificatie deosebita poarta numele de teoreme. De regula, propozitiile care rezulta imediat din alte teoreme sau propozitii se numesc corolarii. Rezultatele care pregatesc demonstratia unei propozitii mai complicate sau a unei teoreme se numesc leme.
Þ ($k)($l)(kd + lx = 1) Þ ($k)($l)(kyd + Ixy = y).
teorema reciproca:a(x1, x2,..., xn) Þ b(x1, x2, ..., xn)
teorema contraraa(x1, x2,..., xn) Þ b(x1, x2, ..., xn)
teorema contrara reciprocei
teorema reciproca contrareib(x1, x2,..., xn) Þ a(x1, x2, ..., xn)
