curs logica matematica si computationala anul i
DESCRIPTION
Cursul integrala de Logica Matematica si Computationala predat la Facultatea de Matematica si Informatica, Universitatea BucurestiTRANSCRIPT
-
5/26/2018 Curs Logica matematica si Computationala anul I
1/56
LOGICA MATEMATICA SICOMPUTATIONALA
Sem. I, 2013 - 2014
Ioana LeusteanFMI, UB
MULTIMI. RELATII
Operatii cu multimi
A, B, C, T multimi
A, B T
A B={x T|x A sau x B}A B={x T|x A si x B}A= {x T|xA}
P(T) = {A|A T}
A B={(a, b)|a A si b B}
Exemplu. P() = {},P({}) = {, {}},P({, {}}) = {, {}, {, {}}}, ...
Exercitiu. A, B, CT
A (B C) = (A B) (A C)A (B C) = (A B) (A C)
Multimi. Relatii n-are
n numar natural, n 1A1, . . ., An T multimi
ni=1Ai ={x T|ex. i {1, . . . , n} x Ai}n
i=1Ai ={x T|x Ai or. i {1, . . . , n}}
n
i=1Ai={(x1, . . . , xn)| xiAi or. i {1, . . . , n}}
Notatie. An =A A n
Definitie
O relatie ntre A1,. . ., An este o submultime a produsului
cartezian ni=1Ai. O relatien-ara pe A este o submultime a lui An.
-
5/26/2018 Curs Logica matematica si Computationala anul I
2/56
Multimi. Relatii n-are
Exemple
| N N|= {(k, n)| ex. m Na.. mk= n}
-
5/26/2018 Curs Logica matematica si Computationala anul I
3/56
Compunerea functiilor
f :A B si g :B C functii
Definimg f :A Cunde (g f)(a) = g(f(a)).
Exercitiu. Rgf =Rf Rg.
Spunem ca o functief :A B este inversabila daca existag :B A astfel ncat g f = 1A si f g= 1B.
O bijectieeste o functie injectiva si surjectiva.
Exercitiu. O functie este bijectiva ddaca este inversabila.
Functia caracteristica
T multime, A T
Functia caracteristicaa lui A n raport cu T este
A: T {0, 1}, A(x) = 1, x A
0, x
A
Proprietati
Daca A, B T si x T atunci
(1) AB(x) = min {A(x), B(x)} = A(x)B(x)
(2) AB(x) = max { A(x),B(x)} =A(x)+B(x)A(x)B(x)
(3) A
(x) = 1A(x)
Functia caracteristica
T multime, {0, 1}T ={f :T {0, 1}|f funtie}
Propozitie
Exista o bijectie ntre P(T) si{0, 1}T.
Dem. Functiile care stabilesc bijectia sunt
F :P(T) {0, 1}T, F(A) =A
G :{0, 1}T P(T), G(f) = {x T|f(x) = 1}
Se arata ca F(G(f)) = f si ca G(F(A)) = Aoricare A T si f :T {0, 1}.
Principiul Inductiei
Principiul Inductiei
Daca S Nastfel ncat:(i) 0 S,(ii) or. n N(n S n + 1 S),atunciS= N.
Dem. Fie S Na.. (i) si (ii) sunt adevarate. Presupunem caS= N, deci exista n0 N \ S. Din (i) rezulta can0= 0. Din (ii)rezulta ca 1, . . . , n0 1 S, deci n0 S. Am obtinut ocontradictie, deci S= N.
-
5/26/2018 Curs Logica matematica si Computationala anul I
4/56
Multimi numarabile
O multime A estenumarabila daca exista f : NA functiebijectiva si se numestecel mult numarabila daca este finita saunumarabil a.
Exercitii(1) O reuniune finita de multimi numarabile este numarabil a.
(2) O reuniune numarabila de multimi numarabile este numarabila.
(3)Q este numarabila.
Principiul Diagonalizarii
Principiul Diagonalizarii
Fie A o multime si R A A o relatie binara p e A. Pentru oricea A definim Ra = {x A |(a, x) R}. FieDR={x A | (x, x)R} diagonala relatiei R. Atunci DR=Ra
pentru oricea A.
Dem. Presupunem ca existaa A astfel ncat DR=Ra.Sunt posibile doua cazuri: a DR sau a DR.
(1) a DR(a, a)R a Ra = DR,(2) a DR(a, a) R a Da = DR.
In ambele cazuri ajungem la o contradictie,deci DR=Ra oricarea A.
Principiul Diagonalizarii
Propozitie. P(N) nu este numarabila.
Dem. Presupunem caP(N) este numarabila, deci exista o bijectieF : N P(N). DefinimR= {(n, k) NN |k F(n)} NN.Daca n N atunciRn = {k N |(n, k) R}={k N |k F(n)}= F(n).Principiul diagonalizarii implicaDR=F(n) pentru orice n N.DarDR N, deci DR P(N). Deoarece F este bijectiva, rezultaca exista un n0 Nastfel ncat F(n0) = DR.Am obtinut o contradictie, deciP(N) nu este numarabila.
Observatii. (1) Exista o functie bijectiva ntreP(N) si 2N,unde 2N ={f : N {0, 1} | f functie}.
(2) Exista o functie bijectiva ntre 2N siR.In consecinta 2N si R nu sunt numarabile.
Familii de elemente
I, A multimi
Ofamiliede elemente din A indexata de Ieste o functief :IA.
Notam cu {ai}iI familia f :I A, f(i) = ai or. i I. Vom scrie{ai}i atunci cand Ipoate fi dedus din context.Daca I = atunci{ai}i este familia vida .
Fie{Ai}iI si {Bi}iI familii de submult imi ale unei multimi T.Definim
iIAi={x T| ex. i I a.. x Ai}iIAi={x T| x Ai or. i I}
Exercitiu.
iIA i=
iIA i
Daca I = atunci iAi=, iAi =T.
-
5/26/2018 Curs Logica matematica si Computationala anul I
5/56
Produsul cartezian
I multime, {Ai}iIfamilie de multimi indexata de I.
Vom nota prin (xi)io familie de elemente a multimii
iAi cuproprietatea ca xiAi or. i I.
Definim iIA i={f :I iAi|f(i) Ai or. i I}={(xi)i|xiAi or. i I}.Exercitiu. Fie I, J multimi(
iIA i) (jJBj) =
(i,j)IJ(Ai Bj)
(
iIA i) (jJBj) =
(i,j)IJ(Ai Bj)
Daca I = atunci
iAi={} = {} este singleton si contineunica functie de la f: .
Operatori de nchidere
T multime
Un operator de nchidere pe Teste o functieC: P(T) P(T)care verifica urmatoarele proprietati oricareA, B T:
(I1) A C(A),(I2) A B implica C(A) C(B),(I3)C(C(A)) = C(A).
Exercitiu. Fie X0 T o submultime fixata. Atunci
C: P(T) P(T) definit prinC(A) = A X0 or. A T
este operator de nchidere.
Operatori de nchidere
Exemplu.Fie Varo multime de variabile si Form multimea propozitiilor carese pot construi folosind variabile din Var.
Pentru Form definim
C() = multimea tuturor formulelor care suntconsecinteale lui .
FunctiaC: P(Form) P(Form) este un operator de nchidere.
RELATII BINARE. RELATII DE ORDINE.
RELATII DE ECHIVALENTA
-
5/26/2018 Curs Logica matematica si Computationala anul I
6/56
Relatii binare
A multime, R A A
Relatia binara R se numeste:
reflexiva: (x, x) R or. x A
simetrica: (x, y) R implica (y, x) R or. x, yA antisimetrica: (x, y) R si (y, x) R implica x=y
or. x, yA
tranzitiva: (x, y) R si (y, z) R implica (x, z) Ror. x, y, z A
relatie de preordine: reflexiva, tranzitiva
relatie de ordine: reflexiva, antisimetrica, tranzitiva
relatie de echivalenta: reflexiva, simetrica, tranzitiva
Relatii binare
Daca A multime si R A A definim:
R(R) = R AS(R) = R R1
T(R) =
n1Rn, unde Rn =R R
npt. n 1, R0 = A
Propozitie
(1)R(R) este reflexiva,S(R) este simetrica, T(R) este tranzitiva.(2) Daca Q A A este reflexiva (simetrica, tranzitiva) si R Q
atunciR(R) Q (S(R) Q,T(R) Q).
Propozitie
R,S,T :P(A A) P(A A) sunt operatori de nchidere.
Relatii binare
Observatie
FieN multimea numerelor naturale si
R= | (relatia de divizibilitate). Atunci S(T(R))=T(S(R)).
Daca A multime si R A A definimE(R) = T(S(R(R))).
Propozitie
(1)E(R) este relatie de echivalenta oricareR A A.(2) Daca Q A A este relatie de echivalenta si
R Qatunci E(R) Q .
Propozitie
E :P(A A) P(A A) este operator de nchidere.
Relatii de echivalenta
Exemple:
Fie k 2 si NN(n1, n2) ddaca ex. x1, x2 0, ex. 0 r
-
5/26/2018 Curs Logica matematica si Computationala anul I
7/56
Relatii de echivalenta
Fie A o multime si A A o relatie de echivalenta.Vom nota prinx yfaptul ca (x, y).
Pentru oricex A definim x= {yA|x y}(clasa de echivalenta a lui x).
Unsistem de reprezentantipentru este o submultime XAcu proprietatea ca oricarea A exista un unic x Xastfel ncata x.
Propozitie
Au loc urmatoarele proprietati:(1) x= y x y(2) x y= xy(3) A =
{x|x X} oricare ar fiXA un sistem de
reprezentanti pentru.
Partitii
A multime
O partitiea lui A este o familie{Ai}iI de submultimi nevide alelui A care verifica proprietatile:(p1)A i Aj= oricarei=j,(p2)A =
iIAi.
Propozitie
(1)Daca{Ai}iIeste o partitie a lui A atunci relatia
x y ex i Iastfel ncat x, yAi
este relatie de echivalenta pe A.(2) Daca A A este relatie de echivalenta si XA este unsistem de reprezentanti, atunci {x|x X} este o partitie a lui A.(3) Exista o bijectie ntre multimea relatiilor de echivalenta pe A simultimea partitiilor lui A.
Dem. exercitiu
Multimea cat
A multime, A A relatie de echivalenta pe A
DefinimA/ = {x|x A} (multimea claselor de echivalenta).
Definimp: A A/, p(x) = x or. x A (surjectia canonica).Se observa ca ker p = .
Proprietatea de universalitate a multimii cat
Fie Bo multime sif :A Bo functie a.. ker f.Atunci exista o unica functief :A/ Ba..f(x) = f(x) or. x A.
Ap
f
A/
fB
Dem. exercitiu
Cardinali
Doua mult imi A si B sunt echipotentedaca exista o funct iebijectiva f :A B. In acest caz scriem A B.Propozitie. Urmatoarele proprietati sunt adevarate:
(i)A
A
,(ii)A B implica B A,(iii)A B si B C implica A C.
Relatia de echipotenta este o relatie de echivalenta. Pentru omultime A definim cardinalul lui A ca fiind|A|= {B| A B}.
Doua mult imi finite sunt echipotente daca si numai daca au acelasinumar de elemente. Cardinalul unei multimi finite este numarul deelemente.
Exista mult imi infinite care nu sunt echipotente: N 2N.
|N|= 0 (aleph-zero) ,20 =|2N|= |R|= c (puterea continuului)
-
5/26/2018 Curs Logica matematica si Computationala anul I
8/56
Monoidul cuvintelor
Unalfabet este o multime de simboluri.Uncuvnteste un sir finit de simboluri din alfabet.
Fie A un alfabet. Definim A+ ={a1 . . . an| n 1, a1, . . . , an A}si A =A+ {} unde este cuvntul vid.
Operatia de concatenare : A A A se defineste prin(a1 . . . an) (b1 . . . bk) = a1 . . . anb1 . . . bk
(A, , ) este un monoid si se numestemonoidul cuvintelor peste alfabetul A.
Pentru doua cuvinte w, w A definimw w daca si numai daca au acelasi numar de litere.
Exercitiu. este relatie de echivalenta pe A si A/ N.
Relatii binare
Fie A multime si R A A o relatie de preordine. Definimx yddaca (x, y) R si (y, x) R.
Propozitie. este relatie de echivalenta pe A.
Dem. exercitiuPeA/ definim x y (x, y) R.
Lema. este bine definita, adicax x1, yy1 si (x, y) R implica (x1, y1) R.Dem. exercitiu
Propozitie. este relatie de ordine pe A/.Dem. exercitiu
Relatii binare
Exemple. Dezvoltati constructia anterioara pentru:
A= Z (N \ {0})R
= {((z1,
n1), (
z2,
n2))
A
A|z1
n2
z2
n1}Aratati ca A/ Q.
A= NN ={f : N N | f functie}
Fie f, gA. Spunem ca f O(g) dacaex. c> 0 nR si n0 Na.. f(n) cg(n) or. n n0.
R= {(f, g) A A|f O(g)} este relatie de preordine.
f g f O(g) si g O(f) este relatie de echivalenta
Pentruf A clasa de echivalenta a lui f se noteaza (f) si
se numeste rata de crestere(rate of growth) a functiei f.
Relatii binare
Daca A si B sunt multimi, definimA Bddaca ex. f :A B functie injectiva.
Relatia este preordine. Definim
A B ddaca A B si B A.
Relatia este o relatie de echivalenta.
Teorema Cantor-Scroder-Bernstein.Daca exista doua functii injective f :A B si g :B AatunciA B.
Relatia de ordine pe cardinali este definita prin:
|A| |B| ddaca A Bddaca ex. f :A B functie injectiva.
-
5/26/2018 Curs Logica matematica si Computationala anul I
9/56
MULTIMI PARTIALORDONATE. LATICI.TEOREME DE PUNCT FIX
Multimi partial ordonate
O multime partial ordonata (mpo) este o pereche (A, R), unde Aeste o multime si Reste o relat ie de ordine pe A.
Exemple.
(P(T), ) unde Teste o multime,
(N, ), (N, |) cu| relatia de divizibilitate,
(Pf(A, B), ) undeA, B sunt multimi,Pf(A, B) = {f :A B|f functie partiala},f g = dom(f) dom(g) si f(a) = g(a) or. a dom(f)
Relatiile de ordine sunt uzual notate cu.Daca (A, ) este mposi :=1 atunci(A, ) este mpo.
Multimi total ordonate
Fie (A, ) mp o. Doua elemente a1, a2 A se numesccomparabiledaca a1 a2 sau a2 a1.
Exemplu. In (N, |) elementele 2 si 4 sunt comparabile, darelementele 3 si 7 nu sunt comparabile.
O relatie de ordine partiala se numeste totala (liniara) dacaoricare doua elemente sunt comparabile. Omultime totalordonataeste o pereche (A, ) unde A este o multime si este orelatie de ordine totala pe A. Pentru multimile total ordonate estefolosita si denumirea de lant.
Exemplu. (LR, lex) este lant, undeLR este multimea cuvintelordin DEX, iar
lexeste relatia de ordine lexicografica.
Produsul cartezian de lanturi
Fie (A1, 1), (A2, 2) lanturi.
PeA1 A2 definimrelatia de ordine pe componente(x1, x2) (y1, y2) x1 1 y1 si x2 2 y2.(A1 A2, ) este mpo.Daca|A1|, |A2| 2 atunci (A1 A2, )nu e lant.
Exemplu. InR R elementele (2, 3) si (4, 1) nu sunt comparabile.
PeA1 A2 definimrelatia de ordine lexicografica(x1, x2)lex (y1, y2) (x1 1 y1 si x1=y1) sau
(x1 = y1 si x22 y2).(A1 A2, ) este lant.
Exercitiu. Definiti relatia de ordine lexicografica pe produsulcartezian an lanturi (A1, 1), , (An, n).
-
5/26/2018 Curs Logica matematica si Computationala anul I
10/56
Elemente minimale si maximale
Fie (A, ) mpo. Un element e A se numeste
element minimal daca (a e a = e);
prim element (minim) daca e a or a A;
element maximal daca (e a a = e);
ultim element (maxim) daca a e ora A.
Exemplu. Inmpo({2, 4, 5, 10, 12, 20, 25}, |), elementele minimalesunt 2 si 5, iar elementele maximale sunt 12, 20, 25.
Orice minim (maxim) este element minimal (maximal).Invers nu este adevarat.
Diagrame Hasse
x yeste reprezentat prin y
x
segment crescator
Exemplu. ({2, 4, 5, 10, 12, 20, 25}, |) este reprezentata prin
12 20
4 10 25
2 5
Sortarea topologica
Este folosita n probleme de planificare. Presupunem ca un project
este format din mai multe procese care se conditioneaza intre ele:procesulpnu poate ncepe decat dupa terminarea procesului q.Multimea proceselor devine astfel multime partial ordonata (P, ).Se pune problema gasirii unei secvente de executie a proceselor.
O relatie de ordine totala P Peste compatibila cu relat ia deordine partiala daca x y x y oricarex, y P.Determinarea unei relatii de ordine totale compatibile cu o relatiede ordine partiala data se numeste sortare topologica.
Algoritm de sortare topologica
Intrare: (P, ) mpo, n = |P| k := 1
while P={pk:= un element minimal al lui P;
P :=P\ {pi};
k :=k+ 1}
Iesire: p1 pn este o ordonare totala compatibila
-
5/26/2018 Curs Logica matematica si Computationala anul I
11/56
Sortare topologica
12 20
4 10 25
2 5x1:= 2
12 20
4 10 25
5x2:= 5
Sortare topologica
12 20
4 10 25x3 := 25
12 20
4 10x4 := 4
...
2 5 25 4 10 12 20Solutia nu este unica.
Multimi bine ordonate
Ompo(A, ) estebine ordonata daca orice submultime nevida asa are prim element.
Observatie. Orice multime bine ordonata este lant.
Principiul Bunei Ordonari. N este bine ordonata (fata de relatia deordine uzuala).
Demonstratii folosind PBO
Vrem sa dem P(n). Presupunem C :={n|P(n) este falsa} estenevida. Conform PBO, multimea Care un prim element n0. Dacase obtine o contradictie, atunci Ceste vida, deci P(n) esteadevarata oricaren N.
Exercitiu. Aratat i ca daca n 8 nN atunci n poate fi scris casuma dintre un multiplu de 3 si un multiplu de 5.
PBO PI
Principiul Inductiei. Daca S N astfel ncat:
(i) 0 S,(ii) or. n N(n S n + 1 S),atunciS= N.
PBO PIFie C = N \ S. Presupunem caC=. Aplicand PBO, multimeaC are un prim element n0. Observam can0= 0, decin0 1 N \ CRezulta ca n0 1 S. Din (ii), obtinem n0 S,ceea ce contrazice faptul can0 C. Deci C =, adica S= N.
-
5/26/2018 Curs Logica matematica si Computationala anul I
12/56
PBO PI
PI PBOPentru oricen N fie P(n) urmatoarea proprietate:
or. E N cu E {0, , n} = are prim element.
DefinimS= {n N | P(n)adevarata}.
Este clar ca 0 S.Presupunem can Na.si demonstram ca n + 1 S. Fie E Ncu E {0, , n+ 1} =. Daca E {0, , n+ 1}={n+ 1}atuncin + 1 este prim element pentruE. AltfelE {0, , n} =deci, aplicnd ipoteza de inductie, rezulta caE are prim element.
Din PI rezultaS= N, deci P(n) este adevarata pentru oricen N.Daca E N, E=, atunci exista n E si P(n) e adevarata.In consecinta, E are prim element.
Infimum si supremum
Fie (A, ) mpo. Un element a A se numeste
minorantal lui X daca a x or. x X;
majorant al lui X daca x a or. x X;
infimum al lui X daca a este cel mai mare minorant(a este ultim element in multimea minorant ilor luiX);
supremum al lui X daca a este cel mai mic majorant(a este prim element in multimea majorantilor lui X).
Exercitiu. Infimumul (supremumul) unei multimi, daca exista, este unic.
Infimumul (supremumul) lui X l vom nota inf X (sup X).Daca X ={x1, x2} atunci notam inf{x1, x2}, sup{x1, x2}.
Exemple
(R, ), X = (3, 4], Y = Nmultimea majorantilor luiXeste [4, ),4 este ultim element pt. X,multimea minorantilor lui Xeste (, 3],
3 este infimum pt. X,Y nu are majoranti (ultim element, supremum),multimea minorantilor lui Y este (, 0),0 este prim element pt. Y .
(N, |), X ={n1, n2}sup X= sup{n1, n2}= cmmmc{n1, n2}inf X= inf{n1, n2}= cmmdc{n1, n2}
({2, 4, 5, 10, 12, 20, 25}, |), X ={12, 20, 25}Xnu are minoranti si nici majoranti
(P(T), ),X P(T)supX =
{Y|Y X }, infX =
{Y|Y X }
CPO. Latici
CPOO mpo completa (CPO) este o mult ime partial ordonata(C, ) cu proprietatile:
C are prim element, sup X exista pentru oricelant XC.
Exemplu. (Pf(A, B), ) este CPO.
LaticeO mpo(L, ) este latice daca sup{x1, x2} si inf{x1, x2} existaoricare ar fix1, x2 L. Laticea (L, ) estecompleta dacainf X si sup X exista oricare ar fi XL.Exemplu. (P(A), ) este latice completa.
Exercitiu.(a) Orice latice completa este CPO.(b) Orice latice completa are prim si ultim element.
-
5/26/2018 Curs Logica matematica si Computationala anul I
13/56
Functie crescatoare. Puncte fixe.
Functie crescatoare
Daca (A, A) si (B, B) sunt mpoatunci o functief :A Bestecrescatoaredaca a1A a2 f(a1)B f(a2) or. a1, a2 A.
Functie continuaDaca (A, A) si (B, B) sunt CPO atunci o functief : A Bestecontinua daca pentru orice lant {an|n N} din A
f(sup{an|n N}) = sup{f(an)|n N}.
Exercitiu. Orice functie continua este crescatoare.
Punct fixUn element a A estepunct fix al unei functiif :A A daca
f(a) = a.
Teoreme de punct fix
Teorema Knaster-Tarski pentru latici complete
Fie (L, ) latice completa si F : L L o functie crescatoare.Atunci a = inf{x L|F(x) x} este cel mai mic punct fix alfunctiei F.
Teorema Knaster-Tarski pentru CPO
Fie (C, ) o CPO si F : CCo functie continua. Atuncia= sup{Fn()|n N} cel mai mic punct fix al functiei F.
Observam ca n ipotezele ultimei teoreme secventaF0() = F() F2() Fn() este un lant, deci a exista.
Teoreme de punct fix
Exemplu.Pf(N,N) CPO, : N N,(k) nedefinita or. k NF: Pf(N,N) Pf(N,N)
F(g)(k) := 1, k
= 0k g(k 1), k> 0 si g(k 1) e definitanedefinit, altfel
DeoareceF este continua, conform Teoremei Knaster-Tarski, celmai mic punct fix al functiei F este f= sup{Fn()|n N}.
f(k) = F(f)(k) :=
1, k= 0k f(k 1), k> 0 si f(k 1) e definitanedefinit, altfel
feste functia factorial.
Teoremele de punct fix sunt folosite in semantica denotationalapentru a defini semantica instructiunii while.
Knaster-Tarski pentru CPO
Demonstratie.Fie (C, ) CPO si F : CC functie continua.
(I) a = sup{Fn
()|n N} este punct fix.F(a) = F(sup{Fn()|n N})= sup{F(Fn())|n N} (continuitate)= sup{Fn+1()|n N}= sup{Fn()|n N}= a
(II)a este cel mai mic punct fix.Fie bun alt punct fix, i.e. F(b) = b. Demonstram prin inductiedupan 1 caFn() b. Pentrun = 0,F0() = bdeoarece este prim element. Daca Fn() b, atunci Fn+1() F(b),deoareceF este crescatoare. DarF(b) = b, deci Fn+1() b.
-
5/26/2018 Curs Logica matematica si Computationala anul I
14/56
Knaster-Tarski pentru laticicomplete
Demonstratie.Fie (L, ) latice completa si F : CC functie crescatoare.(I) a = inf{x L|F(x) x} este punct fix.Fie X :={x L|F(x) x} si fie x X. Atunci a x, deciF(a) F(x) x. Am demonstrat caF(a) x oricarex X, deciF(a) este un minorant pentruX. In consecinta,F(a) a.Observam caF(a) X, deci a F(a). DinF(a) a si a F(a)rezultaF(a) = a.
(II)a este cel mai mic punct fix.Fie bun alt punct fix, i.e. F(b) = b.Atuncib X, deci a b.
Latici
Definitia L1.O mpo(L, ) este latice daca sup{x1, x2}, inf{x1, x2}exista oricarex1, x2 L.
Infimumul (supremumul) devin operatii pe L:: L L L, x1 x2:= sup{x1, x2},
: L L L, x1 x2:= inf{x1, x2}.Propozitia L1-2.
Urmatoarele identitati sunt satisfacute:
asociativitate:(x y) z= x (y z), (x y) z=x (y z),
comutativitate: x y=y x, x y=y x,
absorbtie: x (x y) = x, x (x y) = x.
Demonstratie. exercitiu.
Laticea (L, ) devine structura algebrica (L, , ).
Definitia Algebrica a Laticilor
Definitia L2.O latice este o structura algebrica (L, , ) unde si suntoperatii binare asociative, comutative si care ver ifica proprietatilede absorbtie.
Lema. x y =y x y=x or. x, y L.Demonstratie. Daca x y=y, atunci x=x (x y) = x y.
Propozitia L2-1.
Fie (L, , ) in sensul Definitiei L2. Definimx y x y=y x y =x.Atunci (L, ) este latice in sensul Definitiei L1. In plussup{x, y}= x y, inf{x, y}= x y or. x, y L.
Demonstratie. exercitiu.
Latici marginiteO latice este marginita daca are prim si ultim element. Primulelement se noteaza cu 0, iar ultimul element se noteaza cu 1.O latice marginita va fi notata prin (L, , 0, 1), iar ca structuraalgebrica prin (L, , , 0, 1). Se observa ca:
x 0 = x, x 0 = 0, x 1 = 1, x 1 = x or. x L.Elementulxestecomplemental lui ydaca x y= 1 si x y= 0.O latice este complementatadaca orice element are cel putin uncomplement.
Exemplu. Determinati elementele complementate n laticile:
1
x y z
0
1
w
0
-
5/26/2018 Curs Logica matematica si Computationala anul I
15/56
Algebre BooleO latice (L, , ) estedistributiva daca, or x, yL:x (y z) = (x y) (x z) si x (y z) = (x y) (x z).
LemaIntr-o latice distributiva si marginita, un element are cel mult uncomplement.Demostratie. Fie y1, y2 complemente pentru x. Obtinemy1 = y1 1 = y1 (y2 x) = y1 y2= y2 (y1 x) = y2 1 = y2
O algebra Booleeste o latice distributiva si complementata cuprim si ultim element.Daca B este o algebra Boole, atunci pentruorice element exista un unic complement. Putem defini o operatie
:B B prinx:= complementul luix.O algebra Boole este o structur a algebrica
(B, , , , 0, 1).
ALGEBRE BOOLE
Scurt istoric
1854 George Boole: The Laws of Thought
All the operations of Language, as an instrument of reasoning,
may be conducted by a system of signs composed of the
following elements: literal symbols, ...signs of operation, ...the sign of identity=. And these symbols of Logic are in theiruse subject to definite laws, partly agreeing with and partly
differing from the laws of the corresponding symbols in the
science of Algebra.
1904 Edward V. Huntington: Sets of Independent Postulates forthe Algebra of Logic
1936 Marshall H. Stone:The Theory of Representations ofBoolean Algebras
1938 Claude E. Shannon: A Symbolic Analysis of Relay andSwitching Circuits
Algebra Boole
O algebra Booleeste o latice distributiva si complementata cuprim si ultim element.In consecinta, o algebra Boole este o structura
(A, , , , 0, 1)
care satisface urmatoarele identitati:
(L1) (x y) z= x (y z), (x y) z=x (y z),
(L2) x y=y x, x y =y x,
(L3) x (x y) = x, x (x y) = x,
(D) x (y z) = (x y) (x z),x (y z) = (x y) (x z),
(P) x 0 = x, x 0 = 0,
(U) x 1 = x, x 1 = 1,
(C) x x= 1, x x= 0.
-
5/26/2018 Curs Logica matematica si Computationala anul I
16/56
Exemple
L2= ({0, 1}, , , , 0, 1),
(P(T), , , , , T)
Algebra Lindenbaum-Tarski a calculului propozitional. Multimea evenimentelor asociate unui experiment.
Multimea nchis-deschisilor unui spatiu topologic.
Exercitiu. Daca (Ai, i, i,i , 0i, 1i) sunt algebre Boole oricare
1 i n atunci A1 An este algebra Boole cu operatiiledefinite pe componente.
Diagrame Hasse
0
a b c
x y z
1
00
01
11
10
a= z, b= y, c=x
Reguli de calcul
(A, , , , 0, 1) algebra Boole x y= 1 si x y= 0 y=x,
y =y 1 = y (x x) = (y x) (y x) = y x=(y x) 0 = (y x) (x x) = x (y x) = x 1 = x
principiul dublei negatii: x=x,
Atat x, cat si x satisfac ecuatiile care definesc n mod uniccomplementul lui x.
x y x z y z, x z y z
x y x y= 0 x y= 1 y x
x y x y y y x y = 0
x y= 0 y =y 0 = y (x y) = y x x y
Reguli de calcul
(A, , , , 0, 1) algebra Boole
si sunt idempotentex x= x x=x
x x= x (x (x x)) = x, x x= x (x (x x)) = x
Legile lui De Morganx y =x y, x y=x y.
Se demonstreaza cax y satisface ecuatiile care definesc n modunic complementul lui x y.
-
5/26/2018 Curs Logica matematica si Computationala anul I
17/56
Principiul dualitatii
Expresii Booleene
Multimea expresiilor Booleene cu variabilele v1, . . ., vn estedefinita recursiv astfel: v1, . . ., vn , 0, 1 sunt expresii, dc. E1, E2 sunt expresii at. E1, E1 E2, E1 E2 sunt expresii.
Vom nota E(v1, . . . , vn) o expresie cu variabilelev1, . . ., vn.
Duala unei expresii
Daca E(v1, . . . , vn) este o expresie, atunci expresia dualaEd(v1, . . . , vn) se obtine interschimbnd 1 cu 0 si cu .
Exemplu. E(x, y, z) = x (y z) Ed(x, y, z) = x (y z).
Exercitiu. Ed(v1, . . . , vn) = E(v1, . . . , vn)
Principiul dualitatii
E1(v1, . . . , vn) = E2(v1, . . . , vn) Ed
1(v1, . . . , vn) = E
d
2(v1, . . . , vn).
Functii Booleene
Functiile Booleene sunt folosite n reprezentarea circuitelorelectronice. Ofunctie Booleana de grad n este o functief :Ln2 L2. O astfel de functie poate fi descrisa printr-un tabel.
x y z f (x, y, z)0 0 0 00 0 1 00 1 0 1 m1= x y z0 1 1 01 0 0 1 m2= x y z1 0 1 1 m3= x y z1 1 0 1 m4= x y z1 1 1 1 m5= x y z
Orice functie Booleana poate fi definita printr-o expresie Booleana.
f(x, y, z) = m1 m2 m3 m4 m5= = x (y z).
Demonstratiile n cadrul calculului propozitional!
Operatiile , , +
(A, , , , 0, 1) algebra Boole
x y :=x y
x y x y= 1,x (y x) = 1, (x y) ((y z)(x z)) = 1.
x y := (x y) (y x)
x y = 1 x=y,x y =x y, (x y) z=x (yz).
x+ y := (x y)d = (x y) (y x)
x+ x= 0, x+ y=y+ x,x+ z (x+ y) (y+ z).
Operatia (x, y)x+ y are proprietatile unei distante.
Inele Boole
(A, , , , 0, 1) algebra Boole
Definimx+ y := (x y) (y x) si x y :=x y.Propozitie
R(A) = (A, +, , 0, 1) este inel cu x x=x oricarex A.
Demonstratia: exercitiu.
Un astfel de inel se numesteinel Boole.Oricarei algebre Boole i se poate asocia un inel Boole.
-
5/26/2018 Curs Logica matematica si Computationala anul I
18/56
Inele Boole
(R, +, , 0, 1) inel Boole(inel unitar cu x x=x oricarex R)
x y+ y x= 0, y x=(x y)(x+ y) (x+ y) = x+ y x+ x y+ y x+ y=x+ y
x+ x= 0, x= x
x y=y xx y=(x y) = y x
Definimx y :=x+ y+ x y si x y :=x y.
Propozitie
B(R) = (R, +, , 0, 1) este algebra Boole.
Demonstratia: exercitiu.
Inele Boole Algebre Boole
Propozitie
Fie (R, +, , 0, 1) un inel Boole si (A, , , , 0, 1) o algebra Boole.
R siR(B(R)) coincid ca inele Boole.
Operatia din B(R) este definita prinx y :=x+ y+ x y,iar operatia+ din R(B(R)) este x+ y := (x y) (y x).Observam cax= 1 + x. Trebuie sa aratam cax+ y=x+ y.
A si B(R(A)) coincid ca algebre Boole.
Operatia + din R(A) este definita prinx+ y := (x y) (y x), iar operatia din B(R(A)) estex y :=x+ y+ x y. Trebuie sa aratam ca x y=x y.
Inelele Boole si algebrele Boole sunt clase de structuri echivalente.
Exemple fundamentale
Camp de mult imi (field of sets)A P(X) cu astfel incat A siX1, X2 A X1 X2, X1 X2, X1 A.Atunci (A, , , , , A) este o algebra Boole de multimi.
F {0, 1}X astfel ncat 0, 1 F sif1, f2 F f1 f2, f1 f2, f1 F,unde, oricarex X,0(x) := 0,1(x) := 1, f1:= f1(x),(f1 f2)(x) := f1(x) f2(x), (f1 f2)(x) := f1(x) f2(x).Atunci (F, , , , 0, 1) este o algebra Boole de functii.
Teorema de reprezentare a lui Stoneafirma ca orice algebra Boole
poate fi reprezentata printr-o algebra Boole care are una dinformele de mai sus. In continuare vom demonstra aceasta teorema.
Notiuni de algebra universala
(A, , , , 0, 1), (B, B, B, , 0B, 1B) algebre Boole
Fie S A astfel incat 0, 1 S six, yS x y, x y, x S.
Atunci (S, , ,
, 0, 1) este o algebra Boole, unde , si
sunt restrictiile operatiilor dinA. In acest caz spunem ca Seste osubalgebraa lui A.
O functief :A Beste un morfism de algebre Boole
daca: f(0A) = 0B, f(1A) = 1B, f(x) =f(x),f(xAy) = f(x) Bf(y), f(xAy) = f(x) Bf(y)or. x, y A. Un morfism injectiv se numeste scufundare. Unizomorfismeste un morfism bijectiv.
Ocongruenta pe A este o relatie A A de echivalentacare verifica urmatoarele proprietati:
x y x y, x1 y1 si x2 y2 x1 x2 y1 y2 x1 x2 y1 y2.
-
5/26/2018 Curs Logica matematica si Computationala anul I
19/56
Constructia algebrei cat
Constructia algebrei cat
Pe multimea claselor de echivalenta A/ definim:
x y := x y, x y := x y, x :=x.
Atunci (A/ , , , , 0, 1) este o algebra Bo ole.
Exercitiu. Aratat i ca functiap: A A/ , definita prinp(x) := xeste morfism de algebre Boole.
Exemplu
A= {x1x2 xn | xi {0, 1} oricarei}, unde n N, n 1
(A, , , , 0 0, 1 1) este algebra Boole, unde operatiile sunt
definite pe componente
Fie k {1, . . . , n} si 1 n1< n2 < < nk n.
Definimx1x2 xn y1y2 yn xni =yni oricare 1 ik.
Atunci este o congruenta pe A.
Exercitiu. Demonstrati ca Lk2 A/ .
Filtre si Ideale
In unele clase de structuri (inele, module, grupuri, algebre Boole)congruentele sunt unic determinate de submultimi particulare.
(A
, , ,
, 0, 1) algebra BooleDefinitie
O submultime FA se numeste filtrudaca:
1 F,
x F, x y y F,
x, yF x y.
Un filtru F se numeste propriudaca 0F (F=A).
Exercitiu. Notiunea duala este cea de ideal. Definiti notiunea deideal folosind principiul dualizarii.
Filtre
Exemple.
{1} este filtru.
Multimea {{a
}, 1} este filtru in P({a
,b
}). Daca A este o algebra Boole, atunci multimea
[a) := {x A | a x}
este filtru oricarea A. Observam ca [a) este propriu daca sinumai daca a = 0.
Daca f :A Beste un morfism de algebre Boole atunci
f1({1}) = {x A|f(x) = 1}
este filtru in A.
Fie A o algebra Boole si FA. Daca F este filtru si subalgebraa lui A, atunci F =A.
-
5/26/2018 Curs Logica matematica si Computationala anul I
20/56
Filtre si congruente
(A, , , , 0, 1) algebra Boole
Teorema
(1) Daca FA filtru, definim FA A prin
xF y x y F x yF si y x F.
Atunci Feste o congruenta pe A.(2) Daca A A este o congruenta pe A, definim
F:= 1 = {x A | x 1}.
Atunci F este filtru n A.
(3) Daca FA este un filtru si A A este o congruenta,atunciF =FF si =F.
Exista o bijectie ntre filtre si congruente. Vom nota
A/F :=A/ F
Demonstratie.
(1), (2) exercitiu.
(3) Daca Feste un filtru si x A, atuncix FF xF 1 x 1 Fx F.
Fie congruenta si x y in A. Atuncix y yy, deci x y 1si, similar, y x 1. Rezulta x y 1,deci x yF, adica xF y.Am demonstrat ca F.Invers, fie xF y, adica x y Fy.Rezulta x y 1, deci x y1 si y x 1.Obtinem x= x 1 x (x y) = x ysi, similar, y x y. Asadar x y siam demonstrat ca F .
Filtrele cubului
A=
0
a b c
x y z
1
F0= {0, a, b, c, x, y, z, 1},F1 = {a, x, y, 1}, F2= {b, x, z, 1}, F3 = {c, y, z, 1}F4 = {x, 1}, F5 = {y, 1}, F6= {z, 1}
uF1 v u v F1 a u v si a vu.
Exercitiu. Demonstrati ca uF1 v a u= a v or. u, v A.Exercitiu. Determinati algebra cat pentru filtreleF0, . . ., F7 .
Ultrafiltre
(A, , , , 0, 1) algebra Boole
Teorema de caracterizare a ultrafiltrelorPentru un filtru propriuFA urmatoarele afirmatii sunt
echivalente:
(1) x F xF or. x A,
(2) x y F x F sau yF or. x, y A,
(3) FU, Ufiltru propriu F =U.
DefinitieUn ultrafiltrueste un filtru propriu care verifica proprietatileechivalente de mai sus. Observam ca ultrafiltrele sunt elementemaximale in multimea filtrelor proprii, ordonata cu incluziunea.
Exercitiu. F este ultrafiltru A/FL2
-
5/26/2018 Curs Logica matematica si Computationala anul I
21/56
Caracterizarea ultrafiltrelorDemonstratia.
(1 2) Implicatia este evidenta.Fie x, y A astfel ncat x yF si xF. Atunci x F,deci (x y) x= y x F. Deoarece y x y, rezultay F.
(2 3) Fie Uun filtru propriu astfel ncat FU. Presupunem caexista x U\ F. Deoarece 1 = x x F si xF, rezultax F. In consecinta x U, deci x x= 0 U. Contrazicemfaptul ca Ueste propriu, deci presupunerea a fost eronata.Rezulta U=F.
(3 1) Fie x A astfel ncat xF. DacaU:={a A| exista f F astfel incat f x a}atunciU este filtru, FU si x U (exercitiu). DeoareceU=F, rezulta ca Unu e propriu, deci 0 U. Asadar existaf Fastfel ncat f x=O, adica f x.Am demonstrat cax F.
Filtrele cubului
A=
0
a b c
x y z
1
F0= {0, a, b, c, x, y, z, 1}
F1 = {a, x, y, 1}, F2= {b, x, z, 1}, F3 = {c, y, z, 1} ultrafiltre
F4 = {x, 1}, F5 = {y, 1}, F6= {z, 1}
Existenta ultrafiltrelor
Fie (A, , , , 0, 1) algebra Boole.
Multimea filtrelor proprii ale algebreiA este nevida, deoarece{1} este filtru propriu n orice algebra Boole.
Pentru a demonstra existenta ultrafiltrelor folosim un rezultatechivalent cuAxioma alegerii n sistemul axiomaticZermelo-Fraenkel, si anumeLema lui Zorn.
Lema lui ZornFie (P, ) ompocu proprietatea ca orice lant C P aremajorant. Atunci Pare cel putin un element maximal.
Existenta ultrafiltrelor
Propozitie
Daca x= 0 in A atunci exista un ultrafiltruUastfel ncat x U.
Dem. Daca P= {F| Ffiltru propriu, x F}, atunci (P, ) estempo. Obervam ca P este nevida, deoarece [x) este propriu, deci[x) P. FieCun lant dinP si V :=
{F| F C }. Atunci V este
un filtru (exercitiu) si a V, deci V este majorant pentruC. Amdemonstrat ca orice lant are un majorant, deci Lema lui Zornasigura exitenta unui element maximal U inP. Aratam ca U esteultrafiltru n A. Fie U U, unde U este un filtru propriu. Atuncix U, deci U P. Cum Ueste maximal n P, obtinem U=U.
-
5/26/2018 Curs Logica matematica si Computationala anul I
22/56
Existenta ultrafiltrelor
Propozitie
Daca x= 0 n A atunci exista un ultrafiltruUastfel ncat x U.
Corolar 1. Multimea ultrafiltrelor este nevida.
Corolar 2.
{U A | Uultrafiltru}= {1}.
Dem. Fie x Uoricare ar fiUultrafiltru si presupunem cax= 1.Atunci x= 0, deci exista un ultrafiltru Vastfel ncat x V.Rezulta 0 =x x V, ceea ce contrazice faptul caV esteultrafiltru.
Teorema de reprezentare a lui Stone
Pentru orice algebra Boole A exista o mult ime X si un morfisminjectivd :A P(X).
Observatie
Orice algebra Boole este izomorfa cu o algebra Boole de multimi:
A d(A) P(X).
CorolarPentru orice algebra BooleA exista o multime X si un morfisminjectivd :A LX2.
Dem. Este consecinta a faptului caP(X) LX2.
Teorema de reprezentare a lui Stone
Demonstratie.
Fie A o algebra Boole si fie U multimea ultrafiltrelor luiA. Definimd: A P(U) prin d(a) := {U U | a U}.
Fie x, yA si U U.U d(x) x U xU U d(x)
U d(x y) x y U x U sau yU U d(x) d(y)
Am demonstrat cad(x) = d(x) si d(x y) = d(x) d(y),deci deste un morfism Boolean.
Fie x, yA astfel ncat d(x) = d(y). Atuncid(x y) = d(x) d(y) = U, adicax y
{U| U ultrafiltru inA}.
Rezulta x y= 1, deci x=y.Am demonstrat cad este un morfism injectiv.
Stone duality
Fie A o algebra Boole si U multimea ultrafiltrelor luiA.
DefinimUa= {U U |a U} oricarea A siUI =
{Ua| a I} pentru orice idealIA.
{UI |I ideal} defineste o topologie peU (U, ) este compact Hausdorff {Ua| a A} este o baza de nchisi-deschisi (clopen sets)
Un astfel de spat iu topologic se numete spatiu Boolean.
Teorema
A = ({Ua| a A}, , , , U0, U1) este algebra Boole, unde
Ua Ub= Uab, Ua Ub= Uab, (Ua) =Ua, U0 = ,
U1= U
A A
Orice algebra Boole este izomorfa cu algebra nchis-deschisilor unui
spatiu topologic.
-
5/26/2018 Curs Logica matematica si Computationala anul I
23/56
Atomi
(A, , , , 0, 1) algebra Boole
Definitie
Elementele minimale n A \ {0} se numescatomi. AlgebraA se
numeste atomica daca pentru oricex= 0 exista un atom a Aastfel ncat a x.
Exercitiu
a este atom [a) este ultrafiltru.
Exercitiu
Daca A este atomica atunci x=
{aA| a atom, a x} or. x= 0.
Exemple
A= Ln2 aren atomi:(0, . . . , 0), (1, 0, . . . , 0),. . ., (0, . . . , 0, 1)
B= P(X) are atomii de forma{x} cu x X.
C P(R) unde
C = {,R}{[a1, b1) . . . [an, bn)|n 1, a1 < b1< . . .
-
5/26/2018 Curs Logica matematica si Computationala anul I
24/56
Inceputurile logicii
Aristotel (sec. IV i.e.n.)
primul studiu formal al logicii
a studiat silogismele, deductii formate din douapremize si o concluzie.
Premiza Toti oamenii sunt muritori.Premiza Toti grecii sunt oameni.Concluzie Toti grecii sunt muritori.
Silogismele
Patru tipuri de enunturi (AffIrmo nEgO)A: Toti X sunt Y. (universal afirmativ)E: Nici un X nu este Y. (universal negativ)
I: Unii X sunt Y . (particular afirmativ)O: Unii X nu sunt Y . (particular negativ)
Un silogism este format din doua premize si o concluzie,fiecare avand una din formele A E I O.
Premiza majoraPremiza minoraConcluzia
Silogismele
Barbara Festino
Premiza Toti oamenii sunt muritori. Nici un caine nu este pisica.Premiza Toti grecii sunt oameni. Unele carnivore sunt pisici.
Concluzie Toti grecii sunt muritori. Unele carnivore nu sunt caini.
Felapton AIOPremiza Nici unXnu este Y. TotiX sunt Y.Premiza TotiX sunt Z. Unii Z sunt Y.Concluzie Unii Znu sunt Y. Unii Znu sunt X.
Adevarat pentru X = Fals
256 silogisme,15 valide,
24 valide daca X, Y, Z=
Gottfried Wilhelm Leibniz, 1646 -1716lingua characteristica universalis, calculus ratiocinator
If controversies were to arise, there would be no more needof disputation between two philosophers than between two
accountants. For it would suffice to take their pencils in theirhands, and say to each other: Calculemus - Let us calculate.
George Boole, 1815-1864The Mathematical Analysis of Logic (1847)
The design of the following treatise is to investigate thefundamental laws of the operations of the mind by whichreasoning is performed; to give expressions to them in thesymbolic language of calculus, and upon this foundation toestablish the science of logic and constructs its methods.
-
5/26/2018 Curs Logica matematica si Computationala anul I
25/56
Logica algebrica
Analiza rationamentelor prin metode asemanatoare calcululuialgebric.
x multimea oamenilor,y multimea muritorilor,z multimea grecilor.
BarbaraPremiza Toti oamenii sunt muritori. x(1 y) = 0 x=xyPremiza Toti grecii sunt oameni. z(1 x) = 0 z= zxConcluzie Toti grecii sunt muritori. z(1 y) = 0 z=zy
Dem. z=zx= z(xy) = (zx)y=zy
Logica algebrica
Exemplu. Fie a , b, c si d proprietati ale substantelor care potinterac tiona n cadrul unui exp eriment. Se cunosc urmatoarele:(1) a si bapar simultan apare numai una dintre c si d,(2) b si capar simultan fie a si dapar simultan,
fie nu apare nici una,(3) nici una dintre a si bnu apare nici una dintre c si dnu apare,(4) nici una dintre c si d nu apare nici una dintre a si bnu apare.
Demonstrati ca:(a) nici una dintre a si bnu apare nu apare nicic,(b) a , b si cnu apar simultan.
Logica algebrica
Fie A, B, C si Dmultimile substantelor care au, respectiv,propr ietatile a , b, c si d.
(1) a si bapar simultan cu siguranta apare una dintre c si d,A B (C D) (D C)
(2) b si capar simultan fie a si dapar simultan,fie nu apare nici una,
B C(A D) (A D)
(3) nici una dintre a si bnu apare nici una dintre c si dnu apare,A B C D
(4) nici una dintre c si d nu apare nici una dintre a si bnu apare.
C D A B
Logica algebrica
Notam AB= A B. FolosimA B AB=.
Ipotezele:
(1) AB(C D)(C D) = (2) BC(A D)(A D) = (3) A B(C D) = (4) C D(A B) =
Concluzia:(1) A B CA BC =
Demonstratia:A B(C D) = A BC A BD= A BC = si A BD=
(2)exercitiu.
-
5/26/2018 Curs Logica matematica si Computationala anul I
26/56
CALCULUL PROPOZITIONAL CLASIC PC
Logica matematic a Friedrich Ludwig Gottlob Frege, Begriffsschrift, 1879
(a formula language, modeled upon that of arithmetic, forpure thought)
Giuseppe Peano, Formulario Mathematico, 1894-1908 Bertrand Russell si Alfred North Whitehead
Principia Mathematica, 1910-1913
David Hilbert, Hilberts Pogram , 1921Once a logical formalism is established one can expect that asystematic, so-to-say computational, treatment of logicformulas is possible, which would somewhat correspond to thetheory of equations in algebra.
Kurt GodelTeorema de completitudine a calculului cu predicate (1929),Teoremele de incompletitudine (1931)
Alfred TarskiThe Concept of Truth in Formalized Languages(1935),
On the Concept of Logical Consequence(1936)
Calculul propozitional
O propozitieeste un enunt care poate fiadevarat(1) sau fals(0).
Propozitiile sunt notate simbolic (, , , ) si suntcombinate cu ajutorul conectorilor logici (, ,, ,).
Exemplu.
Fie propozitia: Azi este vineri, deci avem curs de logica.Cine este?Propozitiaeste: Azi este vieri si nu avem curs de logica.
Calculul propozitional
Exemplu.
Daca trenul ntarzie si nu sunt taxiuri la gara,
atunci Ion ntarzie la ntalnire.
Trenul ntarzie. Ion nu ntarzie la ntalnire.
In consecinta, sunt taxiuri la gara.
= trenul ntarzie = sunt taxiuri la gara= Ion ntarzie la nt alnire
Rationamentul anterior poate fi reprezentat formal astfel:{( ) ,, }
-
5/26/2018 Curs Logica matematica si Computationala anul I
27/56
Sintaxa si semantica
Un sistem logic are doua componente: sintaxa si semantica.
Notiunile sintactice sunt descrise formal, simbolic.Principalele notiuni sintactice sunt: limbajul, formulele,teoremele, notiunea de demonstratie. Simbolul este sintacticsi are urmatoarea semnificatie: notam prin faptul caformula este demonstrabila din multimea de formule .
Semantica asociaza un nteles, o interpretare notiunilorsintactice si defineste riguros notiunea de formula universaladevarat a (tautologie). Alte notiuni semantice importantesunt: evaluarile (interpretarile), modelele, multimile de formulesatisfiabile. Simbolul |= este semantic si are urmatoareasemnificatie: notam prin |= faptul ca formula esteadevarata ori de cate ori toate formulele din sunt adevarate.
Sintaxa PC
Limbajul. Formulele.
Limbajul PC este format din:
o multime infinta de variabile propozit ionale:Var={v1, v2, . . . , vn, . . .}
conectori logici: (unar), (binar)
paranteze: ( , ).
Formulele PC se definesc recursivastfel:
(F0) orice variabila propozi tionala este formula,
(F1) daca este formula, atunci () este formula,
(F2) daca si sunt formule, atunci ( ) este formula,
(F3) orice formula se obtine aplicand regulile (F0), (F1), (F2) de
un numar finit de ori.
Limbajul. FormuleleExemple. v1 (v2),v1v2 nu sunt formule . ((v1 v2) (v1)), ((v1 v2))sunt formule.
Vom presupune ca are precedenta cea mai mare si vom puneparantezele numai atunci cand sunt necesare. Astfel formula((v1 v2) (v1)) o vom scrie (v1 v2) v1.
Conectori derivati
Pentru si formule oarecare, definim urmatoarele prescurtari: := :=( ) := ( ) ( )
In aceasta prezentare a calculului propozitional am considerat si drept conectori principali. Conectorii derivati, , suntdefiniti folosind conectorii principali.
-
5/26/2018 Curs Logica matematica si Computationala anul I
28/56
Limbajul. Formulele.
Multimea formulelor se defineste echivalent n modul urmator:
Multimea formulelor este intersectia tuturor multimilor W decuvinte (siruri finite de simboluri din limbaj) care ver ifica
urmatoarele proprietati:
contin variabilele propozitionale,
sunt nchise la (daca Watunci () W ),
sunt nchise la (daca 1, 2 Watunci (1 2) W).
Vom nota cu Form multimea formulelor PC.
Inductia structurala
Principiul inductiei pe formule
FieP() o proprietate a formulelor astfel ncat:
P(v) este adevarata oricarev Var,
daca P() este adevarata, atunci P() este adevarata
oricare Form, daca P() si P() sunt adevarate, atunci P( ) este
adevarata oricare, Form.
Atunci P() este adevarata pentru orice formula Form.
Dem. Fie W ={ Form| P()adevarata}. Din ipoteze rezultaca VarW si Weste nchisa la si. Deoarece Form esteintersectia multimilor W cu proprietatile de mai sus, rezultaForm W, deci W =Form.
Sistemul deductivVom prezenta sistemul deductiv al PC in stilul Hilbert, carepresupune existenta mai multor axiome si foloseste ca regula dedeductiemodus ponens. Alte modalitati de prezentare a unuisistem de deductiv sunt deductia naturala si calculul cu secventi
(sisteme Gentzen).AxiomeleOricare ar fi, si formule ale PC, urmatoarele formule suntaxiome:
(A1) ( )
(A2) (( )) (() ( ))
(A3) ( ) ( ).
Regula de deductie
MP (modus ponens) ,
Demonstratie. Teoreme
DefinitieO demonstratieeste o secventa de formule 1, . . .,n astfelncat, pentru fiecarei {1, . . . , n}, una din urmatoarele condit iieste satisfacuta:
i este axioma,
i se obtine din formulele anterioare prin MP:exista j, k
-
5/26/2018 Curs Logica matematica si Computationala anul I
29/56
Teoreme ale PC
Lema 1. Pentru orice formula avem .
Dem.
(1) ( (( ) )) (( ( ))()) (A2)
(2) (( ) ) (A1)(3) ( ( )) ( ) (1),(2), MP(4) () (A1)(5) (3), (4), MP
Exercitiu. Daca1,. . ., n este o demonstratie,atunci i oricarei {1, . . . , n}.
Deductia din ipoteze
Fie o multime de formule.
Definitie
O -demonstratie(demonstratie din ipotezele) este osecventa de formule1,. . .,n astfel ncat, pentru fiecarei {1, . . . , n}, una din urmatoarele conditii este satisfacuta:
ieste axioma sau i, i se obtine din formulele anterioare prin MP.
O formula este -teoremadaca exista o -demonstratie1, . . .,n astfel incat n = . Notam prin faptul ca este-teorema. Observam ca este echivalent cu .O formula este demonstrabila din (consecinta sintactica alui ) daca .Daca este o mult ime de formule atunci notam prin faptulca oricare .
Deductia din ipoteze
Exemplu.
Daca Ana merge n excursie, atunci Maria merge n excursie.Daca Maria merge n excursie, atunci Elena merge n excursie.In consecinta, daca Ana merge n excursie, atunci Elena merge nexcursie.
v1 = Ana merge n excursiev2 = Maria merge n excursiev3 = Elena merge n excursie
Trebuie sa demonstram ca{v1 v2, v2 v3} v1 v3.
Exercitiu. Daca si atunci .
TD (Herbrand, 1930)
Teorema deductiei pentru PC
{}
unde este o multime de formule, iar si sunt formule in PC.
Dem. Daca , atunci:(1) {} ( {})(2) {} ( {})(3) {} (1), (2), MP
Presupunem ca {} si demonstram ca .
-
5/26/2018 Curs Logica matematica si Computationala anul I
30/56
Teorema deductiei pentru PCDem. (continuare)Fie1,. . .,n= o demonstratie pentru din ipotezele {}.Demonstram ca i prin inductie dupa 1 i n.Daca i= 1, atunci 1 este axioma sau 1 {}. Daca1= , atunci deoarce . Daca 1 sau 1este axioma, atunci 1 si avem:
(1) 1(2) 1 ( 1) (A1)(3) 1 (1), (2), MP
Presupunem ca k oricarek
-
5/26/2018 Curs Logica matematica si Computationala anul I
31/56
Reguli de deductie
O regula de deductie are forma
1 1, . . . , n n
.
A demonstra o regula de deductie derivata revine la a deduceconcluzia din premisele1 1,. . ., n n.
Exemplu. Folosind teorema deductiei se demonstreaza regula:
{}
Reguli de deductie derivate
Observatie
Daca atunci demonstr am regula de deductie
astfel:
(1) (premisa)(2) (-teorema)(3) (1), (2), MP.
Exemplu. ,
Dem.(1) (premisa)(2) (premisa)(3) ( ) (( ) ( )) (Lema 2)(4) (1), (2), 2 MP.
Reguli de deductie derivate
Modus tollens
,
Dem.
(1) (premiza)(2) ( ) ( ) (Lema 8)(3) (1), (2), MP(4) (premiza)(5) (3), (4), MP
Reguli de deductie derivate
Reductio ad absurdum
{} , {}
Dem.
(1) {} (premiza)(2) {} (premiza)(3) {} ( ( )) (Lema 4)(4) {} ( ) (1), (2), (3), 2 MP(5) ( ) TD(6) ( ( )) (()) (A3)(7) () (5), (6), MP(8) (Lema 1)(9) (7), (8), MP
-
5/26/2018 Curs Logica matematica si Computationala anul I
32/56
Semantica PC
Evaluare (Interpretare)
Valori de adevarMultimea valorilor de adevar este{0, 1} pe care consideramoperatiile de algebra Boole.
Definitie
O evaluare(interpretare) este o functiee: Var {0, 1}.
TeoremaPentru orice evaluaree: Var {0, 1} exista o unica functiefe: Form {0, 1} care verifica urmatoarele proprietati:
(e0) fe(v) = e(v) oricarevVar,
(e1) fe() = fe() oricare Form,
(e2) fe( ) = fe() fe() oricare, Form.
Dem. Vom demonstra atat existenta, cat si unicitatea, prin
inductie structurala pe formule.
Evaluare
Existenta. FieSmultimea tuturor secventelor finite de simboluridin limbajul PC. Definim recursiv functia partiala fe: S {0, 1}astfel:
fe(v) := e(v) oricarev Var,
daca S si fe() este definita, atunci fe() := fe(),
daca 1,2 S si fe(1), fe(1) sunt definite, atuncife(1 2) := fe(1) fe(2).
Consideram proprietateaP() = fe() este definita .Aplicand principiului induct iei structurale deducem ca P() esteadevarata oricare Form. In consecinta fe este definita pentru
orice formula si satisface evident proprietatile cerute.
Evaluare
Unicitate. Fie g :Form {0, 1} o functie care extindee si
satisface (e0), (e1), (e2).Consideram proprietateaP() = fe() si g() coincid.Observam ca:
fe(v) = g(v) = e(v) oricarev Var,
daca fe() = g(), atunci fe() = fe() = g() = g(),
daca fe() = g() si fe() = g(), atuncife( ) = fe() fe() = g() g() = g( ),oricare, Form.
Conform principiului inductiei structurale,P() este adevarata
oricare Form, deci fe() = g() oricare Form.
-
5/26/2018 Curs Logica matematica si Computationala anul I
33/56
Tautologii. Modele
Definitie
O evaluare e: Var {0, 1} estemodel al unei formuledaca fe() = 1.
O formula este satisfiabiladaca admite un model. Omultime de formule este satisfiabila daca exista o evaluare
e: Var {0, 1} astfel ncat fe() = 1 oricare . O formula este tautologie (valida,universal adevarata)
daca fe() = 1 pentru orice evaluaree: Var {0, 1}. Notamprin|= faptul ca este o tautologie.
Fie o mult ime de formule. O formula este tautologie(consecinta semantica a lui ) daca orice model al lui este si model pentru , i.e.fe() ={1} fe() = 1 oricaree: Var {0, 1}.
Notam prin |= faptul ca este o -tautologie.
Metoda tabelului
Vrem sa demonstram ca o formula este tautologie: |=
Daca v1,. . ., vn variabilele care apar n, atuncicele 2n evaluari posibile e1, . . ., e2n pot fi scrise ntr-un tabel:
v1 v2 . . . vn e1(v1) e1(v2) . . . e1(vn) fe1()e2(v1) e2(v2) . . . e2(vn) fe2()
... ...
... ...
...e2n(v1) e2n(v2) . . . e2n(vn) fe2n ()
Fiecare evaluare corespunde unei linii din tabel.
Corectitudinea
Teorema. Orice-teorema este -tautologie.
|=
oricare ar fi Form si Form.
In particular, daca atunci |=.Dem. Fie e: Var {0, 1} astfel ncat fe() = 1 oricare .Trebuie sa aratam ca fe() = 1.Fie1, . . ., n = o demonstratie pentru din ipotezele .Demonstram ca fe(i) = 1 prin inductie dupa 1 i n.Pentrui= 1, 1 este axioma sau 1 . Daca 1 , atuncife() = 1 deoarece eeste un model al lui . Daca 1 este axioma,se verifica fe(1) = 1 prin calcul direct (exercitiu).Presupunem cafe(k) = 1 oricarek< i si demonstram cafe(i) = 1. Daca ieste axioma sau i atunci procedam camai sus. Altfel, exista j, k
-
5/26/2018 Curs Logica matematica si Computationala anul I
34/56
Multimi inconsistente
Definitie
O multime de formule se numesteinconsistenta daca nu esteconsistenta, i.e. oricare Form .
PropozitiePentru o multime Form sunt echivalente:
(1) este inconsistenta,
(2) exista Form, si .
Dem. (1) (2) este evidenta.(2) (1) se demonstreaza folosind teorema ( ).
Multimi inconsistente
Propozitie
Pentru Form si Form sunt echivalente:
(1) {} este inconsistenta,
(2) .
Dem. (1) (2) {} TD ( ) (teorema)
(2) (1) rezulta folosind propozitia anterioara, deoarece {} si {} .
Multimi consistente
Propozitie
Pentru orice multime consistenta Form exista o multime Form cu urmatoarele proprietati:
,
este consistenta,
oricare Form, sau ,
oricare, Form sau .
Dem. Se arata ca multimeaC= { Form | consistenta, }.este inductiv ordonata (orice lant dinCare un majorant). Aplicand
Lema lui Zorn,Care un element maximal, .Evident si este consistenta.
Multimi consistente
Dem. (continuare)Demonstram ca implica oricare Form.Presupunem ca exista Form astfel ncat si .Deoarece {}, rezulta ca {} esteinconsistenta, deci . Dar , deci este inconsistenta.Obtinem o contradictie, deci este nchisa la deductia sintactica.
Fie Form astfel ncat . Rezulta ca {} esteinconsistenta, . Asadar sau oricare Form.
Fie, Form astfel ncat . Daca , atunci . Asadar si , deci . Am aratat ca sau . Invers, daca sau obtinem folosind teorema ( ), respectiv ( ).
-
5/26/2018 Curs Logica matematica si Computationala anul I
35/56
Completitudine
Teorema de completitudine extinsa
Orice multime consistenta este satisfiabila.
Dem. Fie Form o multime consistenta. Trebuie sademonstram ca are un model. Fie multimea obtinuta prinaplicarea propozitiei anterioare. Definime: Var {0, 1} prin
e(v) = 1 daca v, e(v) = 0 daca v.FieP() = fe() = 1 . Demonstram prin inductiestructurala ca P() este adevarata pentru orice Form. Dindefinitia evaluarii e, P(v) este adevarata oricarevVar.Presupunem caP() si P() sunt adevarate. Avemfe() = 1 fe() = 0 ,fe() = fe() fe() = 1 fe() = 0 saufe() = 1 sau .Conform principiului inductiei structurale,P() este adevaratapentru orice Form, adica fe() = 1 .
Deoarece , eeste un model al lui .
Completitudine
Teorema de completitudine
-teoremele si -tautologiile coincid, i .e.
|=
oricare are fi Form si Form.In particular, |=.
Dem. corectitudinea.
Presupunem ca . Atunci si {} esteconsistenta. Fie e: Var {0, 1} un model pentru {}.Obtinem fe() ={1} si fe() = 1, deci fe() = 0. Din ipoteza,orice model al lui este si model al lui , deci fe() = 1. Amajuns la o contradictie, deci presupunerea noastra a fost falsa. Inconsecinta, .
Conectorii derivati
Conectori derivati
Pentru si formule oarecare, definim urmatoarele prescurtari: := :=( ) := ( ) ( )
Exercitiu. Daca e: Var {0, 1} evaluare, atuncife( ) = fe() fe(),fe( ) = fe() fe(),fe() = fe() fe().
Conectori derivati
Aratati ca v1 (v2 (v1 v2)).
Aplicand teorema de completitudine, aceasta revine la a demonstra|=v1 (v2 (v1 v2))
v1 v2 v1 (v2 (v1 v2))0 0 10 1 11 0 11 1 1
-
5/26/2018 Curs Logica matematica si Computationala anul I
36/56
Sintaxa si Semantica
LemaSunt echivalente:
(1) ,
(2) fe() fe() oricaree: Var {0, 1} evaluare.
LemaSunt echivalente:
(1) ,
(2) fe() = fe() oricaree: Var {0, 1} evaluare.
Dem. exercitiu
Algebra Lindenbaum-Tarski
LINDA
Algebra Lindenbaum-Tarski
Daca pe Form definim relatia binar a prin
si ,
atunci au lo c urmatoarele proprietati:
(1) este o relatie de echivalenta,
(2) LINDA= (Form/, , , , 0, 1) este o algebra Boole, unde
:= , := , :=,1 := , 0 :={ | 1}.
Algebra LINDA se numeste algebra Lindenbaum-Tarski a PC.
LINDADem. (1) Relatia este reflexiva, simetrica si tranzitiva deoarece: si
(2) Trebuie sa demonstram ca operatiile sunt bine definite: 1, 1 1 1 1, 1 1 si 1 fe() = fe(1) si fe() fe(1) oricareeevaluare fe() fe() = fe(1) fe(1) oricareeevaluare fe( ) = fe(1 1) oricareeevaluare 1 1Analog pentru,.
Ecuatiile algebrelor Boole devin teoreme n PC. De exemplu, averifica distributivitatea n LINDA revine la a demonstra ca
( ( )) (( ) ( )). Datorita teoremei decompletitudine, acest lucru se poate demonstra sintactic sausemantic.
-
5/26/2018 Curs Logica matematica si Computationala anul I
37/56
LINDA
Dem.(continuare)Aratam ca 1 = { | } si 0 ={ | }.Fie si doua teoreme. Din (A1), ( ), deci si, similar, . Rezulta , deci oricare doua
teoreme sunt echivalente.Daca teorema si , atunci . Aplicand MP,rezul ta . Orice formula echivalenta cu o teorema este teorema.Asadar teoremele formeaza o clasa distincta.Daca atunci, din (A1) obtinem oricare . Aceastanseamna ca n LINDA, deci 1 ={ | }.
Observatie. 1 e clasa teoremelor, asadar
= 1 n LINDA.
LINDA
LemaDaca v=u Var, atunci v= u n LINDA .
Dem. Deoarece v=uputem defini o evaluare e: Var {0, 1}
astfel ncat e(v)=e(u). In consecinta fe(v)=fe(u), decivu.
TeoremaPentru orice evaluaree: Var {0, 1} exista un unicmorfism de algebre Boole fe: LINDA L2 astfel ncatfe(v) = e(v) oricarev Var.
LINDA
Dem. Var
e
Form
fe
Form/
femorfism{0, 1}
Definim fe() := fe().Daca = , atunci , deci fe() = fe().Am aratat ca definitia este independenta de reprezentanti.Demonstram ca fe este morfism:
fe() = fe( ) = fe() = fe() = fe(),fe( ) = fe() fe() (exercitiu).Fie g: LINDA {0, 1} un morfism astfel ncat g(v) = e(v)
oricare v Var. Se demonstreaza prin inductie structurala cag() = fe() oricare Form, deci g=fe.
SAS
Algebra
Sintaxa Semantica
TeoremaPentru Form, sunt echivalente:
(1) ,
(2) = 1 n LINDA,
(3) |=.
-
5/26/2018 Curs Logica matematica si Computationala anul I
38/56
SAS
( ) (( ) ( ))
Demonstratia sintactica
(1) { , , } ()( ) (teorema)(2) { , , } (ip oteza)
(3) { , , } (1), (2), MP(4) { , , } (ip oteza)(5) { , , } (3), (4), MP(6) { , , } (ipoteza)(7) { , , } (5), (6), MP(8) { , } TD(9) { } ( ) ( ) TD(10) ( ) (( ) ( )) TD
SAS
Demonstratia semantica
|= (v1 v2)((v1 v3) (v2 v3))
Metoda tabelului
v1 v2 v3 (v1 v2) ((v1 v3) (v2 v3))
0 0 0 10 0 1 1...
... ...
...1 1 1 1
Lema substitutiei. Fieo formula siv1,. . ., vn variabilele careapar n . Fie(1, . . . , n) formula obtinuta nlocuind vi cu ioricare i {1, . . . , n}. Daca |=atunci |=(1, . . . , n).
Rezulta |= ( ) (( ) ( ))
SAS
Demonstratia algebrica
( ) (( ) ( ))
Daca := () (( ) ( )), atunci:= ( ) (( ) ( )) in LINDA .
Notam a := , b:= , c:= si obtinem
= (a b) ((a c) (b c))= (a b) ((a c) c b)= (a b) b (a c) c= (a b) (a c) = 1
Am aratat ca = 1 in LINDA, deci .
CALCULUL PROPOZITIONAL CLASICForme normale
-
5/26/2018 Curs Logica matematica si Computationala anul I
39/56
Metoda tabelului
Vrem sa demonstram ca o formula este tautologie: |=
Daca v1,. . ., vn variabilele care aparin , atuncicele 2n evaluari posibile e1, . . ., e2n pot fi scrise ntr-un tabel:
v1 v2 . . . vn e1(v1) e1(v2) . . . e1(vn) fe1()e2(v1) e2(v2) . . . e2(vn) fe2()
... ...
... ...
...e2n(v1) e2n(v2) . . . e2n(vn) fe2n ()
Fiecare evaluare corespunde unei linii din tabel.
Exemplu
Aratati ca|=v1 (v2 (v1 v2)).
v1 v2 v1 (v2 (v1 v2))0 0 10 1 1
1 0 11 1 1
Acest tabel defineste o functieF :{0, 1}2 {0, 1}x1 x2 F(x1, x2)
0 0 10 1 11 0 11 1 1
Functia asociata unei formule
Fie o formulav1, . . ., vn variabilele care apar n,e1,. . ., e2n evaluarile posibile. Tabelul asociat
v1 v2 . . . vn
... ... ... ... ...ek(v1) ek(v2) . . . ek(vn) fek()
... ...
... ...
...
defineste functiaF: {0, 1}n {0, 1}
x1 x2 . . . xn F(x1, . . . , xn)...
... ...
... ...
ek(v1) ek(v2) . . . ek(vn) fek()...
...
...
...
...
Functia asociata unei formuleFie o formula cu variabilelev1,. . ., vn.
Definitie
Functia asociata lui este F: {0, 1}n {0, 1} definita prin
F(x1, . . . , xn) = fe(),
unde e(v1) = x1, e(v2) = x2,. . ., e(vn) = xn
Definitie
O functie Booleana n n variabile este o functie
F :{0, 1}n {0, 1}.
F este o functie Booleana pentru orice .
TeoremaDaca si sunt formule cu variabilele v1,. . ., vn, atunci
|= F= F
Dem. exercitiu
-
5/26/2018 Curs Logica matematica si Computationala anul I
40/56
Caracterizarea functiilor Booleene
Teorema FBPentru orice functie Booleana H: {0, 1}n {0, 1} exista oformula cu n variabile astfel ncat H= F.
Dem. Daca x {0, 1}n atuncix= (x1, . . . , xn). DefinimT ={x {0, 1}n|H(x) = 1} si F ={x {0, 1}n|H(x) = 0},
1 := xTxi=1vi xi=0 vi,2 :=
xF
xi=1
vi
xi=0vi
.
F1(y1, . . . , yn) = 1exista x Tastfel ncat
xi=1
yi
xi=0yi= 1
xi=1yi= 1 si
xi=0
yi = 1 xi=yi oricarei {1, . . . , n} (y1, . . . , yn) = x T H(y1, . . . , yn) = 1.
Similar F2(y1, . . . , yn) = 0 H(y1, . . . , yn) = 0.
Am demonstrat caH= F1 =F2 .
Exemplu
Fie H: {0, 1}3 {0, 1} descrisa prin tabelul:
x y z H (x, y, z)0 0 0 0 M1= x y z0 0 1 0 M2= x y z0 1 0 1 m1= x y z0 1 1 0 M3= x y z1 0 0 1 m2= x y z1 0 1 1 m3= x y z1 1 0 1 m4= x y z1 1 1 1 m5= x y z
H(x, y, z) = m1 m2 m3 m4 m5
H(x, y, z) = M1 M2 M3
FND si FNC
Definitie
Un literal este o variabila sau negatia unei variabile.
O forma normala disjunctiva (FND) este o disjunct iede conjunctii de literali.O forma normala conjuctiva (FNC) este o conjunctiede disjunctii de literali.
TeoremaPentru orice formula exista o FND1 si o FNC 2 astfel ncat|= 1 si |= 2
Dem. Fie1 si 2 formulele definite n demonstratia teoremeianterioare pentruH= F. Atunci F= F1 = F2 .
FNCOrice formula p oate fi adusa la FNC prin urmatoarele transformari:
1. nlocuirea implicatiilor si echivalentelor
, ( ) ( )
2. regulile De Morgan
( ) ,( ) ,
3. principiului dublei negatii
4. distributivitatea
( ) ( ) ( ),( ) ( ) ( )
-
5/26/2018 Curs Logica matematica si Computationala anul I
41/56
Exemple
1. Determinati FNC pentru formula(p q) (p q) (p q) (p q) (p q) (p q)
(p q) (p q)(p p q) (q p q)
2. Determinati FNC pentru formula((p q) q) ((p q) q)p q q
Satisfiabilitate
Definitie
Fie o multime de formule. Un model al lui este o evaluaree: Var {0, 1} cu fe() ={1}. Multimea estesatisfiabiladaca are un model.O formula este consecinta (semantica) a lui (|=) dacaorice model al lui este si model pentru.
Teorema.Sunt echivalente:
{1, . . . , n} |=,
{1, . . . , n, } nu este satisfiabila,
1 . . . n nu este satisfiabila.
Dem. exercitiu
SAT [problema NP-completa (Stephen Cook 1971)]
Fiind data o formula (n forma normala conjunctiva) exista o
evaluaree: Var {0, 1} astfel ncat fe() = 1?
CALCULUL PROPOZITIONAL CLASICClauze. Rezolutie. Algoritmul Davis-Putnam.
Rezolutia
Rezolutia propozitionala este o regula de deductie pentrucalculul propozitional clasic.
Multe demonstratoare automate si SAT-solvere au la bazarezolutia.
Utilizand rezolut ia se poate construi un demonstrator automatcorect si complet pentru calculul propozitional, fara alteteoreme si reguli de deductie.
Limbajul PROLOG este fundamentat de rezolutie.
Rezolutia este o metoda de verificare a satisfiabilitatii
pentru formule n forma clauzala.
-
5/26/2018 Curs Logica matematica si Computationala anul I
42/56
Clauze
DefinitiiUnliteral este o variabila sau negatia unei variabile.O clauza este o multime finita de literali:C ={L1, . . . , Ln}, unde L1, . . ., Ln sunt literali.O clauza C estetriviala daca exista p Var astfel incat p,
p C.
O clauza C ={L1, . . . , Ln} este satisfabila daca formulaL1 . . . Ln este satisfiabila. Daca e: Var {0, 1} este oevaluare vom notae(C) := fe(L1 . . . Ln).
Clauza vida :={} nu este satisfiabila (disjunctie indexata de ).
O multime de clauze S= {C1, . . . , Cm}este satisfiabila daca existao evaluare e: Var {0, 1} astfel incat e(Ci) = 1 oricarei {1, . . . , m}.
Clauze
ObservatiePutem identificaclauzaC ={L1, . . . , Ln} cu L1 . . . Ln,multimea de clauzeS= {C1, . . . , Cm} cu C1 . . . Cm.
clauza disjunctie de literali
multime de clauze FNC
DefinitieCclauza, S multime de clauzeVar(C) = {p Var|p C saup C},Var(S) =
{Var(C)|C S }.
Exemple
1. p,r, q sunt literali.
2. {p, r},{r, r},{q, p}, {q, p, r} sunt clauze.
3. S= {{p, r}, {r, r}, {q, p}, {q, p, r}}este satisfiabila.Dem. Considerame(p) = e(q) = 1.
4. S= {{p, q}, {r, q}, {p}, {r}} nu este satisfiabila.Dem. Daca exista o evaluare ecare satisfaceC, atuncie(p) = e(r) = 1. Rezulta e(q) = 0, decife({p, q}) = fe(p q) = 0. In consecinta,{p, q} nu esatisfacuta de e.
5. O multime de clauze triviale este intotdeauna satisfiabila.
Proprietati
Propozitie
Fie C, D clauze si T,S,U multimi de clauze. Urmatoareleimplicatii sunt adevarate.
(p1)CD, C satisfiabila Dsatisfiabila(p2)C Dsatisfiabila C satisfiabila sau Dsatisfiabila
(p3)pVar(C) C {p}, C {p} satisfiabile
(p4)S T, T satisfiabila Ssatisfiabila
(p5) Fie p Var si U,T, S multimi de clauze astfel incat
pVar(U),or. T T (p T sipT),or. S S (pS si p S).
Atunci Usatisfiabila U T ,U Ssatisfiabile
Dem. exercitiu
Regula Rezolutiei
-
5/26/2018 Curs Logica matematica si Computationala anul I
43/56
Regula Rezolutiei
Rez C1 {p}, C2 {p}
C1 C2
unde{p, p} C1= si {p, p} C2= .
Propozitie
Regula Rezolutiei pastreaza satsifiabilitatea, i.e.
{C1 {p}, C2 {p}} satisfiabila C1 C2 satisfiabila.Dem. Fie e: Var {0, 1} este o evaluare astfel incate(C1 {p}) = e(C2 {p}) = 1.Daca e(p) = 1 atunci e(C2) = 1,deci e(C1 C2) = 1. Similar pentru e(p) = 0.Invers, presupunem cae(C1 C2) = 1, deci e(C1) = 1 saue(C2) = 1. Daca e(C1) = 1 consideram e
:Var {0, 1} oevaluare cu e(v) = e(v) daca vVar(C1) si e
(p) = 0. Atuncie(C1) = e(C1) = 1, deci e
(C1 {p}) = 1.De asemeneae(C2 {p}) = e
(C2) e(p) = 1, deci e este model pentru
multimea de clauze{C1 {p}, C2 {p}}.
Exemple
{p}, {p}
{p}, {p, q}
{q}
AtentieAplicareasimultana a regulii pentru doua variabile diferit estegresita. De exemplu
{p, q}, {p, q}
contrazice rezultatul anterior, deoarece{{p, q}, {p, q}} estesatisfiabila (e(p) = e(q) = 1).Aplicarea corecta a Regulii Rezolutiei este
{p, q}, {p, q}
{q, q}.
Derivare prin rezolutie
DefinitieFieSo multime de clauze. O derivare prin rezolutiedin Seste osecventa finita de clauze astfel incat fiecare clauza este dinS sau
rezulta din clauze anterioare prin rezolutie.ExempluS= {{p, q}, {q, r, s}, {p}, {r}, {s}}O derivare prin rezolutie pentru din SesteC1= {s} ( S)C2= {q, r, s} ( S)C3= {q, r} (C1, C2, Rez)C4= {r} ( S)C5= {q} (C3, C4, Rez)C6= {p, q} ( S)C7= {p} (C5, C6, Rez)
C8= {p} ( S)C9= (C7, C8, Rez)
Algoritmul Davis-Putnam(DP)
Intrare: S multime nevida de clauze netriviale.S1:= S; i:= 1;
P1. viVar(Ci);
T1
i :={C Si|viC};T0i :={C Si|viC};Ti :=T
0i T
1i ;
Ui :=;
P2. ifT0i = and T1i = then
Ui :={C1\ {vi} C0\ {vi}|C1 T1i , C0 T0i };
P3. Si+1= (Si\ Ti) Ui; Si+1= Si+1\ {C Si+1|C triviala};
P4. ifSi+1= then SATelse if Si+1 then NESAT
else{i:=i+ 1; go to P1}.Run DP
http://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.htmlhttp://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.htmlhttp://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.htmlhttp://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.htmlhttp://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.htmlhttp://www.math.uwaterloo.ca/~snburris/htdocs/LOGIC/ST_ALGORS/st_dp.html -
5/26/2018 Curs Logica matematica si Computationala anul I
44/56
Exemplu
S1:= S= {{p, q, s}, {r, q}, {p, r}, {p}, {r}, {s}}
v1 := p; T11 :={{p, r}, {p}}; T
01 :={{p, q, s}};
U1 := {{r, q, s}, {q, s}};S2:= {{r, q}, {r}, {s}, {r, q, s}, {q, s}}; i:= 2;
v2 := q; T12 :={{r, q, s}, {q, s}}; T
02 :={{r, q}};
U2 := {{r, q, r}, {s, r}};S3:= {{r}, {s}, {s, r}}; i:= 3;
v3 := r; T13 :={{r}}; T03 :={{s, r}}; U3 := {{s}};
S4:= {{s}, {s}}; i:= 4;
v4 := s; T14 :={{s}}; T
04 :={{s}}; U4:= {};
S5:= {}In consecinta,S nu este satisfiabila
Exemplu
S1:= S= {{p, r}, {q, p}, {q, p, r}}
v1 := r; T11 :={{q, p, r}}; T
01 :={{p, r}};
U1 := {{q, p, p}};S2:= {{q, p}}; i:= 2;
v2 := q; T12 :={{q, p}}; T
02 :=;
U2 := ;S3:= In consecinta, Seste satisfiabila
Algoritmul DP
FieSo multime finita de clauze si n este numarul de variabile careapar inS. Algoritmul DP se opreste deoareceVar(Si+1) Var(Si). Daca n este numarul de variabile care apar
inS, atunci exista unn
0n
astfel incatVar
(Sn0+1) = , deciSn0+1= sau Sn0+1= {}.Pentru simplitate, vom presupune in continuare ca n0= n.
Propozitie
Si satisfiabila Si+1 satisfiabilaoricare i {1, . . . , n 1}.
Dem. Fie i {1, . . . , n 1}. Stim caSi+1= (Si\ Ti) Ui.Consideram cazurileUi = si Ui=.DacaUi=, atunciT
0i = sau T
1i = si Si = (Si+1 Ti). Ne
aflam in ipotezele proprietatii (p5) . Din (p4) si (p5) obtinemconcluzia dorita.
Algoritmul DP
Dem. cotinuare
DacaUi=, notam Ci :=Si\ Ti. In consecinta Si=Ci Ti siSi+1= Ci Ui.Observam ca fiecare clauza dinUi se obtineaplicand Regula Rezolutiei pentru doua clauze dinTi. Amdemonstrat ca Regula Rezolutiei pastreaza satisfiabilitatea:
Ui satisfiabila Tisatisfiabila.
Au loc urmatoarele echivalente:Si =Ci Tisatisfiabila Ci,Ti satisfiabile Ci,Ui satisfiabile Ui Ti =Si+1 satisfiabila.
Al i l DP R l i
-
5/26/2018 Curs Logica matematica si Computationala anul I
45/56
Algoritmul DP
Teorema DPAlgoritmul DP este corect si complet, i.e. S nu este satisfiabiladaca si numai daca iesirea algoritmului DP este{}.
Dem. Din propozitia anterioara,Snu este satisfiabila daca sinumai dacaSn nu este satisfiabila. Fie punica variabilapropozitionala care apare inSn.DacaSn= {{p}} atunciSn este satisfiabila deoarece e(p) = 1este un model. Daca Sn = {{p}}atunciSn este satisfiabiladeoarecee(p) = 0 este un model. In ambele cazuri Sn+1= {}.
DacaSn= {{p}, } sau Sn= {{p},} atunci Sn nu estesatisfiabila si Sn+1= {}. Daca Sn = {{p}, {p}}sauSn= {{p}, {p},} atunci Sn nu este satisfiabila, putem aplicaRegula Rezolutiei si obtinem Sn+1= {}.
Se observa ca Sn nu este satisfiabila daca si numai daca
Sn+1= {
}.
Rezolutia
ObservatieAlgoritmul DP cu intrareaSse termina cu {} daca si numaidaca exista o derivare prin rezolutie a clauzei vide din S.
TeoremaDacaSeste o multime finita nevida de clauze, sunt echivalente:
S nu este satisfiabila,
exista o derivare prin rezolutie a clauzei vide din S.
Regula Rezolutiei este corecta si completa pentru PC.
Forma clauzala
DefinitieFie o formula si C1 Cn o FNC astfel incat|= C1 Cn. Spunem ca multimea de clauze{C1, , Cn} este forma clauzalaa lui .
Lemasatisfiabila C1 Cn satisfiabila {C1, , Cn}satisfiabilaDem. exercitiu
DefinitieDaca ={1, . . . , n} este o multime de formule atunci o formaclauzala pentru esteS:=S1 S n undeSi este formaclauzala pentrui oricarei.
Lema satisfiabila SsatisfiabilaDem. exercitiu
Demonstratii prin rezolutie
TeoremaFie o multime finita de formule, o formula si So formaclauzala pentru {}. Sunt echivalente:
(1) |=,
(2) {} nu e satisfiabila,
(3) S nu este satisfiabila,
(4) exista o derivare prin rezolutie a clauzei vide din S.
ObservatieTeorema este adevarata si pentru multime oarecare.Demonstratia foloseste compacitatea calculului propozitional:o multime de formule este satisfiabila daca si numai daca orice
submultime finita a sa este satisfiabila.
E l E l
-
5/26/2018 Curs Logica matematica si Computationala anul I
46/56
Exemplu
A demonstra ca |=p (q p) revine la a demonstra ca{(p (q p))} nu e satisfiabila.Pentru aceastadeterminam o forma clauzala pentru(p (q p)) siaplicam DP.
Determinam FNC pentru(p (q p)):
(p (q p)) (p q p) p q pForma clauzala este S= {{p}, {q}, {p}}.
Aplicam DP:{{p}, {q}, {p}}{{p}, {p}}{}
S nu este satisfiabila deoarece exista o derivare prin rezolutie aclauzei vide din S. In consecinta, |=p (q p).
Exemplu
Cercetati daca{p q} |=p q. Aceasta revine cercetasatisfiabilitatea multimii ={p q, (p q)}.
O forma clauzala pentrup qeste {{p, q}}. O forma clauzalapentru (p q) este{{p, q}}.Forma clauzala pentru esteS= {{p, q}, {p, q}}.
Aplicam DP:{{p, q}, {p, q}}{{q, q}}{} (multimea vida)
In acest cazS este satisfiabila, deci {p q}|=p q.
ExempluCercetati daca{p, p (q r)} |=p (p q r).Determinam forma clauzala pentru{p, p (q r), (p (p q r))}.
Forma clauzala a lui peste{{p}}.
p (q r) p q r (FNC)Forma clauzala a lui p (q r) este{{p, q, r}}.
(p (p q r)) (p (p q r)) p (p q r))Forma clauzala a lui (p (p q r)) este{{p}, {p, q, r}}.
Aplicam DP:{{p}, {p, q, r}, {p}, {p, q, r}}{{q, r},, {q, r}}
{{r},
}{}Este adevarat ca{p, p (q r)} |=p (p q r)
Concluzie
Fie o multime de formule si o formula.Notam prin Rezfaptul ca exista o derivare prin rezolutie a
clauzei vide
dintr-o forma clauzala a lui {}. In acest cazspunem ca se demostreaza prin rezolutie din .
TeoremaSunt echivalente:
|=,
Rez.
Folosind rezolutia (fara alte axiome si reguli de deductie) se poateconstrui un demonstrator automat pentru PC.
C l l l di t P t
-
5/26/2018 Curs Logica matematica si Computationala anul I
47/56
CALCULUL CU PREDICATE
Calculul cu predicate- Prezentareinformala
Introduce predicatelesi cuantificatorii.Un predicat este o functie cu valori booleene P :X 0, 1.
Exista doi cuantificatori: existential () si universal ().
Varful x are cel putin doi vecini diferiti
yz(y=z E(x, y) E(x, z))Fiecare varf are cel putin doi vecini distincti.
xyz(y=z E(x, y) E(x, z))
Calculul cu predicate- Prezentareinformala
Fie Xo multime nevida si presupunem ca pentru fiecarex X,sunt definite doua predicateP(x) si Q(x). Cercetati dacaurmatorul enunt este adevarat sau fals.
((x P(x)) (x Q(x))) (x(P(x) Q(x)))
Enuntul nu este intotdeauna adevarat. FieX = N siP(x) : x este numar par,Q(x) : x este multiplu de3.Atunci x P(x) este falsa, deci (x P(x)) (x Q(x)) esteadevarata. Pe de alta parte,P(2) Q(2) este falsa, decix(P(x) Q(x) este falsa. Obtinem o implicatie cu premisaadevarata si concluzia falsa (10), care este falsa.
Calculul cu predicate- Prezentareinformala
Fie Xo multime nevida si presupunem ca pentru fiecarex X,este definit predicatul P(x). Cercetati daca urmatorul enunt esteadevarat sau fals.
yx(P(y) P(x))
Exemplu: Xeste multimea studentilor din anul I siP(x) : eu il cunosc pe xEnuntul este intotdeauna adevarat. Analizam doua cazuri:1. Exista un y0 X a.i. P(y0) este falsa; atunci P(y0) P(x)este adevarata oricarex, deci enuntul este adevarat.2. P(x) este adevarata oricarex X; evident, enuntul este
adevarat in acest caz.
Li b j d di l I
-
5/26/2018 Curs Logica matematica si Computationala anul I
48/56
LOGICA DE ORDINUL ILimbaj de ordinul I. Structura de ordinul I.
Limbaj de ordinul I
Unlimbaj de ordinul I are urmatoarele componente:
(i) o multime numarabila Var={v1, v2, v3 . . .} de variabile;
(ii) o multime F de simboluri de functii; oricareF F arearitatea n 1;
(ii) o multime R de simboluri de relatii; oricareR R arearitatea m 1;
(iii) o multime Cde simboluri de constante;
(iv) conectorii si ;
(v) simbolul de egalitate =;
(vi) cuantificatorul universal;
(vii) parantezele (, ).
FieL un limbaj de ordinul I.
Termeni. Formule atomice
Termeniilui L se definesc inductiv astfel:
(T1) o variabila este termen;
(T2) un simbol de constanta este termen;
(T3) daca F Fare aritatean si t1, . . . , tn sunt termeni, atunciF(t1, . . . , tn) este termen.
TermL := multimea termenilor luiL.
Formulele atomiceale lui L sunt expresiile de forma:
(At1) t1= t2, unde t1 si t2 sunt termeni;
(At2) R(t1 . . . tn), unde R Rn si t1, . . . , tn sunt termeni.
FAtomL := multimea formulelor atomice ale lui L
Formule
Formulelelui L au urmatoarea definitie inductiva:(F1) o formula atomica este formula,
(F2) daca este formula, atuncieste formula,
(F3) daca si sunt formule, atunci este formula,
(F4) daca este formula si xeste variabila, atunci xesteformula.
FormL := multimea formulelor luiL
E l
-
5/26/2018 Curs Logica matematica si Computationala anul I
49/56
Conectorii,, si cuantificatorul existential sunt introdusiprin urmatoarele abrevieri:
:=
:= ( )
:= ( ) ( )
x := x.
Se considera ca si au precedenta mai mare decat ,,.Astfelx este (x) si nu x( ).
Exemplu
L1 : F={s},R = {P}, C= {0},unde aritatea(s) = 1, aritatea(P) = 1.
Exemple de termeni: 0, s(0), s(s(0)),s(s(s(0))), x, s(x),s(s(x)),s(s(s(x))),. . .FAtom= {t1= t2|t1, t2 Term} {P(t)|t termen}
Exemple de formule:x(0= s(x))xy(s(x)= s(y) x= y)P(0) (x(P(x) P(s(x))) xP(x)) (schema inductiei)
Exemplu
L2 : R = ,F={s, +}, C= {0},
unde aritatea(s) = 1, aritatea(+) = 2.Exemple de termeni: 0, s(0), s(s(0)), +(0, 0),+(s(s(0)), +(0, s(0))), +(s(0), s(s(s(s(0))))), x, s(x), s(s(x)),+(x, x), +(x, s(x)) , . . .
Pentru +(x, y) putem folosi notatia x+ y, deci+(s(s(0)), +(0, s(0))) se poate scrie s(s(0)) + (0 +s(0))
Exemple de formule:xy(x+ y=y+ x)xyz((x+ y) +z=x+ (y+ z))
Exemplu
L3 : R = {R},F=C= , unde aritatea(R) = 2.
Term= Var, FAtom= {R(x, y)|x, yVar} {x=y|x, y Var}
Exemple de formule:xR(x, x)xy(R(x, y) R(y, x))xyz((R(x, y) R(y, z)) R(x, z))xyv(R(x, v) R(y, v) z((R(x, z) R(y, z)) R(v, z)))
L structura Exemple
-
5/26/2018 Curs Logica matematica si Computationala anul I
50/56
L-structura
OL - structura are forma
A= (A, FA, RA, CA)
unde
A= este o multime, FA ={FA|F F } este o multime de operatii pe A astfel
incat, daca Fare aritatean atunci FA :An A,
RA ={RA|R R} este o multime de relatii pe A astfelincat, daca Rare aritatean atunci RA An,
CA ={cA A|c C} este o multime de constante.
MultimeaA se numeste universulstructuriiA.
DacaR = 0, atunci A se numeste structura algebrica.DacaF=C= 0, atunciA se numeste structura relationala.
Exemple
L1 : F= {s},R = {P},C= {0}N = (N, sN, PN, 0N) undesN : N N, sN(n) := n2
PN N, PN ={n|n este impar }0N := 1
L2 : R =,F={s, +}, C= {0}N = (N, sN, 0N) undesN : N N, sN(n) := n + 1,+N : NN N, +N(n, m) := n +m,0N := 0
L3 : R ={R}, F=C= X = (X, RX) unde(X, ) multime partial ordonata si RX :=
Interpretare (evaluare)
FieA o L structura.
O interpretare (evaluare) a luiL in A este o functie e: Var A.
Dacae: Var A este o interpretare sit TermL atunci definiminductiv valoarea tA(e) astfel:
daca t= vVar, atunci tA(e) := e(v),
daca t= c C, atunci tA(e) := cA,
daca t= F(t1, . . . , tn), atuncitA(e) := FA(tA1 (e), . . . , t
An (e)).
eFieA o L structura sie: VarA o interpretare.
Definim e :FormL {0, 1} astfel:
t1 = t2e= 1 tA
1 (e) = tA
2 (e), R(t1, . . . , tn)e= 1 (t
A1 (e), . . . , t
An (e)) R
A
NotatieDacae: VarA este o interpretare sia A definim interpretareae[x a] : Var A prin
e[x a](v) =
e(v) daca v=x,a daca v =x.
e=e,
e=e e
xe= 1 e[xa] = 1 oricare a A.
Exemplu
-
5/26/2018 Curs Logica matematica si Computationala anul I
51/56
Propozitie
(1) xe=
aA e[xa],
(2) xe= 1 exista a A, e[xa]= 1,
(3) xe= aA e[xa].Dem. (2)xe= 1 xe= 1
xe= 1 xe= 0 exista a A e[xa] = 0 exista a A e[xa]= 1
Exemplu
L1 : F={s},R = {P}, C= {0}N = (N, sN, PN, 0N) unde 0N := 1sN : N N, sN(n) := n2, PN N, PN ={n|n este impar }
e: Var N, e(x) = 3, e(y) = 4
t= s(s(x)), tN(e) = sN(sN(e(x))) = (32)2 = 81t= s(s(y)), tN(e) = sN(sN(e(y))) = (42)2 = 256
P(z)e= 1 e(z) PN e(z) este impar
P(x)e= 1 si P(y)e= 0
Model. Formula valida
FieA o L-structura si FormL. Spunem caA estemodel al luidaca e= 1 oricare ar fie: VarA o interpretare. Notam
prinA |= faptul ca A este model al lui .Spunem ca este formula universal adevarata (valida) dacaA |= oricare ar fiA o L-structura. Notam prin|= faptul ca este universal adevarata.
Fie o multime de formule. O structura A este model al lui dacaA este model pentru fiecare . Notam prinA |= faptulca A este model al lui .
Spunem ca o formula esteconsecinta semantica a lui dacaorice model al lui este si model al lui . Notam prin |=faptul ca este consecinta semantica a lui .
Exemplu
L1 : F={s},R = {P}, C= {0}N = (N, sN, PN, 0N) unde 0N := 1,
s
N
: N N, sN
(n) := n2
, PN
N, PN
={n|n este impar }N |=x(P(x) P(s(x)))Notam = x(P(x) P(s(x))) si fie e: Var N
e= 1 P(x) P(s(x))e[xn] = 1 oricare n N P(x)e[xn] P(s(x))e[xn] = 1 oricare n N P(x)e[xn] = 0 sauP(x)e[xn] = P(s(x))e[xn]= 1
oricare n N e[x n](x)PN sau e[x n](x) = e[x n](sN(x)) PN
oricare n N
(n este par) sau (n si n2
sunt impare) oricaren Nceea ce este intodeauna adevarat
Variabile libere Enunturi
-
5/26/2018 Curs Logica matematica si Computationala anul I
52/56
Variabile libere. Enunturi
Var() := multimea variabilelor care apar in.
MultimeaVL() a variabilelor libereale unei formule poate fidefinita si prin inductie dupa formule:
VL() = Var(), daca este formula atomica;VL() = VL();VL() = VL() VL();VL(x) = VL() {x}.
O variabila v Var() care nu este libera se numeste legata in .Unenunt al lui L este o formula fara variabile libere.
Prin notatia t(x1, . . . , xn) intelegem ca Var(t) {x1, . . . , xn}, iarprin notatia(x1, . . . , xn) intelegem ca VL() {x1, . . . , xn}.
FieA o L-structura.
Propozitie
Dacae1, e2: VarA sunt interpretari, atunci
e1(v) = e2(v) oricarevVL() e1 =e2
oricare ar fi formula.
ObservatieDaca este un enunt atunci e1 = e2 oricare ar fie1,e2 : Var A doua interpretari. Vom notaA:= e pentrueo interpretare. In acest caz
A |= A= 1.
Propozitie
Pentru o formula(x1, . . . , xn) sunt echivalente:
A |=,
A |=x1 xn(x1, . . . , xn).
NotatieFieA o L-structura si(x1, . . . , xn)(VL() {x1, . . . , xn})Dacaa1, . . ., an A notam
A |=[a1, . . . , an] e= 1 unde e(x1) = a1, . . . e(xn) = an.
Exemplu
|=x(P(x) Q(x)) ((xP(x)) (xQ(x)))
FieA o structuraL-structura.
x(P(x) Q(x)) ((xP(x)) (xQ(x)))A= 1x(P(x) Q(x))A ((xP(x)) (xQ(x)))A= 1A |=x(P(x) Q(x)) implicaA |= (xP(x)) (xQ(x))
Presupunem caA |=x(P(x) Q(x)). Atunci A |=P[a] Q[a]oricare a A.
DacaA |=xP(x), atunci A |=P[a] oricarea A. DarA |=P[a] Q[a] oricarea A, deci A |=Q[a] oricarea A.RezultaA |=xQ(x). Am demonstrat ca
A |=xP(x) implica A |=xQ(x),
deci A |= (xP(x)) (xQ(x)).
Exemplu
-
5/26/2018 Curs Logica matematica si Computationala anul I
53/56
Exemplu
L1 : F={s},R = {P}, C= {0},unde aritatea(s) = 1, aritatea(P) = 1.
Fie :={1, 2, 3}, unde1 = x(0= s(x)),2 = xy(s(x)= s(y) x=y),3 = P(0) (x(P(x) P(s(x))) xP(x)) (schema inductiei)
Nat= (N, sN, PN, 0N) unde 0N := 0,sN : N N, sN(n) := n + 1, PN = N
Nat|= (axiomatizarea Peano a numerelor naturale)
LOGICA DE ORDINUL ISintaxa
L limbaj de ordinul I
O axioma a lui L este o formula care are una din formele:
(A1) ( )
(A2) ( ( )) (()())(A3) ( ) ( )
(A4) x( ) (x x)
(A5) x
(A6) x daca xVar()
(E1) x(x= t) daca xVar(t)
(E2) t1= t2 ( ), daca si sunt formule atomice si se obtine din prin inlocuireaunei aparitii a lui t1 in cu t2.
(MP) ,
si (GEN) x
(generalizarea)
Deductia din ipoteze
Fie o multime de formule.
DefinitieO demonstratie din ipotezele este o secventa de formule1, . . .,n astfel incat una din urmatoarele conditii estesatisfacuta oricarei {1, . . . , n}:
ieste axioma sau i,
i se obtine din formulele anterioare prin MP:exista j, k
-
5/26/2018 Curs Logica matematica si Computationala anul I
54/56
TautologiiO formula FormL se numeste tautologie daca f() = 1oricare ar fif :FormL {0, 1} o functie care satisfaceurmatoarele proprietati:(T1)f() = f(),(T2)f( ) = f() f()f este numita funct ie de adevar (truth valuation).
Propozitie
Orice tautologie este teorema.
Teorema lui PostDaca 1, . . .,n, FormL astfel ncat1 (2 (n ) ) este tautologie, atunci1,. . ., n implica .
Observatie
Exista form