h1q3qt
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: 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: a(x, y) = "x + y = 2" 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
Þ
Þ ($k)($l)(kd + lx = 1) Þ ($k)($l)(kyd + Ixy = y).
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: teorema reciproca: a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) teorema contrara a(x1, x2,..., xn) Þ b(x1, x2, ..., xn) teorema contrara reciproceiteorema reciproca contrarei b(x1, x2,..., xn) Þ
a(x1, x2, ..., xn)
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.