Date post: | 24-Feb-2018 |
Category: |
Documents |
Upload: | bogdan-cojocaru |
View: | 329 times |
Download: | 1 times |
of 34
7/24/2019 Logica Matematica - Curs1
1/34
Logica Matematica siComputationala
Anul I, Semestrul I 2015/2016Laurentiu Leustean
Pagina web: http://imar.ro/~leustean/
In prezentarea acestui curs sunt folosite partial slideurile Ioanei Leustean
dinSemestrul I 2014/2015.1
http://imar.ro/~leustean/http://imar.ro/~leustean/http://imar.ro/~leustean/https://sites.google.com/site/illogmcc/https://sites.google.com/site/illogmcc/https://sites.google.com/site/illogmcc/http://imar.ro/~leustean/7/24/2019 Logica Matematica - Curs1
2/34
Ce este logica?
logike tekhne= stiinta rationamentelor; logos= cuvant,
rationament
Aristotel (IV i.e.n.)
http://plato.stanford.edu/
entries/aristotle-logic/
primul studiu formal al logicii
a studiatsilogismele, deductiiformate din doua premize si o
concluzie.
Barbara
Premiza Toti oamenii sunt muritori.Premiza Grecii sunt oameni.
Concluzie Deci grecii sunt muritori.2
http://plato.stanford.edu/entries/aristotle-logic/http://plato.stanford.edu/entries/aristotle-logic/http://plato.stanford.edu/entries/aristotle-logic/http://plato.stanford.edu/entries/aristotle-logic/7/24/2019 Logica Matematica - Curs1
3/34
Logica si Informatica
... a computing machine isreally a logic machine. Its circuitsembody the distilled insights of aremarkable collection of logicians,
developed over century.Nowadays, as computertechnology advances with suchbreathtaking rapidity, as weadmire the truly accomplishments
of the engineers, it is all too easyto overlook the logicians whoseideas made it all possible. Thisbook tells their story.
3
7/24/2019 Logica Matematica - Curs1
4/34
Gottfried Wilhelm Leibniz (1646 -1716)
Visul lui Leibniz un limbaj matematic universal (lingua characteristica
universalis) n care toata cunoasterea umana poate fiexprimata si reguli de calcul (calculus ratiocinator) pentru aderiva, cu ajutorul masinilor, toate relat iile logice:
If controversies were to arise,there would be no more need ofdisputation between twophilosophers than between twoaccountants. For it would sufficeto take their pencils in theirhands, and say to each other:
Calculemus - Let us calculate.4
7/24/2019 Logica Matematica - Curs1
5/34
George Boole (1815-1864)
The Mathematical Analysis of Logic (1847),The Laws of
Thought(1854): a initiat analiza rationamentelor logice prinmetode asemanatoare calculului algebric.
Silogismele lui Aristotel sunt despreclasede obiecte, care potfi studiate algebric.
The design of the followingtreatise is to investigate thefundamental laws of theoperations of the mind by which
reasoning is performed; to giveexpressions to them in thesymbolic language of calculus,and upon this foundation toestablish the science of logic and
constructs its methods.5
7/24/2019 Logica Matematica - Curs1
6/34
Gottlob Frege (1848-1925)
Begriffschrift(1847)
A introdus sintaxa formala: obiecte, predicate, functii;conectori propozitionali; cuantificatori.
A inventat logica de ordinul ntai.
van Heijenoort, From Frege to Godel, 1967:
perhaps the most important single work ever written inlogic.
Exemplu: Toti oamenii sunt mortali.
Pentru orice x, daca x esteom, atunci xeste mortal.
x(Man(x) Mortal(x)).6
7/24/2019 Logica Matematica - Curs1
7/34
Georg Cantor (1848-1925)
A inventat teoria multimilor.
A definit numere cardinale, ordinale.
A dezvoltat o teorie matematica ainfinitului.
Hilbert:
No one shall be able to expel usfrom the paradise that Cantorcreated for us.
7
7/24/2019 Logica Matematica - Curs1
8/34
Georg Cantor (1848-1925)
Aristotel: Infinitum Actu Non Datur - nu exista infinitactual. Leibniz: I am so in favor of the actual infinite that instead of
admitting that Nature abhors it, I hold that Nature makesfrequent use of it everywhere.
Gauss: I protest above all the use of an infinite quantity as acompleted one, which in mathematics is never allowed.
Frege: For the infinite will eventually refuse to be excludedfrom arithmetics . . . Thus we can foresee that this issue willprovide for a momentous and decisive battle.
Poincare: grave disease infecting mathematics. Kroneckerdespre Cantor: scientific charlatan, corrupter of
youth Wittgenstein: utter nonsense
Mittag-Lefflerdespre lucrarile lui Cantor: about one hundredyears too soon.8
7/24/2019 Logica Matematica - Curs1
9/34
Criza fundamentelor matematicii
Scrisoarea luiBertrand RussellcatreFrege(16 iunie, 1902):
I find myself in agreement with you in all essentials . . . I find inyour work discussions, distinctions, and definitions that one seeks
in vain in the work of other logicians . . . There is just one pointwhere I have encountered a difficulty.
Frege, apendix laThe Fundamental Laws of Arithmetic, Vol. 2:
There is nothing worse that can happen to a scientist than tohave the foundation collapse just as the work is finished. I havebeen placed in this position by a letter from Mr. Bertrand Russell.
9
7/24/2019 Logica Matematica - Curs1
10/34
Criza fundamentelor matematicii
Conform teoriei naive a multimilor, orice colectie definibila estemultime. Fie U multimea tuturor multimilor.
Paradoxul lui Russel (1902)
Fie R={A U |A /A}. Atunci Reste multime, deci RU.
Obtinem ca R /R RR.
Criza fundamentelor matematicii Paradoxul lui Russel Sistemul logic al lui Fregeinconsistent
a declansat criza fundamentelor matematicii (foundations ofmathematics)
s-a dezvoltat teoria axiomatica a multimilor: Zermelo-Fraenkel(ZF),ZFC: ZF+ Axioma alegerii (Axiom of Choice)
10
7/24/2019 Logica Matematica - Curs1
11/34
David Hilbert (1862-1943)
unul dintre matematicieniide varf ai generatiei sale
unul dintre fondatorii teorieidemonstratiei si logiciimatematice
lista sa de 23 probleme
deschise (1902) a influentatfoarte mult matematicasecolului XX
11
7/24/2019 Logica Matematica - Curs1
12/34
Programul lui Hilbert
Programul lui Hilbert (1921)
Sa se formalizeze matematica si sa se stabileasca urmatoarele:
Matematica esteconsistenta: un enunt matematic si negatiasa nu pot fi demonstrate simultan.
Matematica estecompleta: toate enunturile matematiceadevarate pot fi demonstrate.
Matematica estedecidabila: exista o regula mecanica pentru adetermina daca un enunt matematic dat este adevarat sau fals
12
7/24/2019 Logica Matematica - Curs1
13/34
Programul lui Hilbert
Hilbert a fost convins ca aceste obiective pot fi atinse:
Every mathematical problem must necessarily be susceptible to anexact statement either in the form of an actual answer to thequestion asked, or by the proof of the impossibility of its solution.
Once a logical formalism is established one can expect that asystematic, so-to-say computational, treatment of logic formulas is
possible, which would somewhat correspond to the theory ofequations in algebra.
13
7/24/2019 Logica Matematica - Curs1
14/34
Kurt Godel (1906-1978)
Teoremele de incompletitudine ale lui Godel (1931-33) Incompletitudinea aritmeticii obisnuite.
Imposibilitateade a demonstra consistenta teoriei multimilor.
Au marcat esecul programului lui Hilbert.
Este considerat cel mai mare logician alsecolului XX.
A introdus functiile calculabile.
A demonstrat teorema de completitudinea logicii de ordinul l.
A demonstrat ca Axioma Alegerii siIpoteza Continuumului sunt consistente
cu axiomele teoriei multimilor.14
7/24/2019 Logica Matematica - Curs1
15/34
Kurt Godel (1906-1978)
John von Neumann:
Kurt Godels achievement in modern logic is singular andmonumental - indeed it is more than a monument, it is a landmark
which will remain visible far in space and time .... The subject oflogic has certainly completely changed its nature and possibilitieswith Godels achievement.
Revista TIME (19 martie 1999)
Godel a fost inclus in lista cu cei mai importanti 20 oameni destiinta si ganditori ai secolului XX.
15
7/24/2019 Logica Matematica - Curs1
16/34
Problema de decizie (Entscheidungsproblem)
Hilbert si Ackermann (1928): Exista un algoritm pentru averifica daca o anumita formula din logica de ordinul ntai esteadevarata?
Cu alte cuvinte: Este logica de ordinul ntai decidabila?
16
7/24/2019 Logica Matematica - Curs1
17/34
Alan Turing(1912-1954)
Turing, On computable numbers, with an application to the
Entscheidungsproblem, Proc. London Math. Soc. 42 (1936).
a demonstrat ca logica de ordinul ntai estenedecidabila(rezultat obtinut independent deChurch(1936)).
a introdus masina Turing (universala) pentru a formaliza
notiunea de algoritm.
parintele informaticii siinteligentei artificiale
masina Turing universalaeste model al calculatoareloractuale
17
7/24/2019 Logica Matematica - Curs1
18/34
Alan Turing(1912-1954)
Revista TIME (19 martie 1999)Turing a fost inclus in lista cu cei mai important i 20 oameni destiinta si ganditori ai secolului XX:
Virtually all computers today from10 million supercomputers to
the tiny chips that power cell phones and Furbies, have one thingin common: they are all von Neumann machines, variations onthe basic computer architecture that John von Neumann, buildingon the work of Alan Turing, laid out in the 1940s.
Premiul Turing http://amturing.acm.org/
decernat anual de catre Association for Computing Machinery(ACM) pentru contributii n informatica
este considerat un Premiu Nobel pentru Informatica18
http://amturing.acm.org/http://amturing.acm.org/7/24/2019 Logica Matematica - Curs1
19/34
Logica si Informatica
E. W. Dijkstra,The next fifty years (EWD1243a). E.W. DijkstraArchive. Center for American History, University of Texas atAustin:
Computing and Computing Science unavoidably emerge as anexercise in formal mathematics or, if you wish an acronym, asexercise in VLSAL (Very Large Scale Application of Logic).
Aaron R. Bradley, Zohar Manna,The Calculus of ComputationDecision Procedures with Applications to Verification, Springer,
2007:Logic is the calculus of computation.
Georg Gottlob, Logic and Artificial Intelligence, VSL 2014:
Computer science is the continuation of logic by other means.19
https://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1243a.htmlhttps://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1243a.htmlhttp://link.springer.com/book/10.1007/978-3-540-74113-8http://link.springer.com/book/10.1007/978-3-540-74113-8http://vsl2014.at/media-seminar/http://vsl2014.at/media-seminar/http://link.springer.com/book/10.1007/978-3-540-74113-8https://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1243a.html7/24/2019 Logica Matematica - Curs1
20/34
Logica si Informatica
Aplicatii ale logicii n informatica: calculabilitate si complexitate
arhitectura calculatoarelor (circuite logice)
software engineering (verificare, model checking)
limbaje de programare (semantica, programare logica,programare functionala)
baze de date (algebre de relatii, teoria modelelor finite)
inteligenta artificiala
criptografie si securitate
J. Y. Halpern, R. Harper, N. Immerman, P.G.Kolaitis, M.Y. Vardi,V.Vianu, On the Unusual Effectiveness of Logic in ComputerScience, Bulletin of Symbolic Logic 7(2001)
20
7/24/2019 Logica Matematica - Curs1
21/34
Logica si Informatica n Romania
Grigore C. Moisil (1906-1973)
Computer Pioneer Award of IEEE Computer Society
S. Marcus, Grigore C. Moisil: A life becominga myth, 2006.
As a professor of the Bucharest University, hewas the first to teach there mathematicallogic. Articulating logic and automata, Moisilwas well prepared to organize the Romaniandevelopment in the emergent field of
Computer Science...we can say that 1957 isthe date of birth of Romanian ComputerScience, under the guidance of ProfessorMoisil and with the collaboration of engineersand mathematicians.
21
7/24/2019 Logica Matematica - Curs1
22/34
PRELIMINARII
22
7/24/2019 Logica Matematica - Curs1
23/34
Operatii cu multimi
Fie A, B, T multimi a.. A, BT.
A B = {xT |xA sau xB}
A B = {xT |xA si xB}
A \ B = {xT |xA si x /B}
CTA = T\ A={xT |xA}
CTA se mai noteaza si A cand Teste clar din context.
Notatii: N ={0, 1, 2, . . .} este multimea numerelor naturale;N = N \ {0}; Z este multimea numerelor ntregi; R este multimea
numerelor reale;Q
este multimea numerelor rationale.Multimea partilorlui T este P(T) ={A | A T}. Se mai noteazasi 2T.
Exemplu. P() ={},P({}) ={, {}},
P({, {}}) ={, {}, {{}}, {, {}}}.23
7/24/2019 Logica Matematica - Curs1
24/34
Produsul cartezian
Notam cu (a, b)perechea ordonataformata din a si b(care suntcomponentele lui (a, b)).
Observatii: (a, b)= (b, a); (a, b)={a, b}; (7, 7) este o perecheordonata valida; doua perechi ordonate (a, b) si (c, d) sunt egaleddaca a=c si b=d. In teoria multimilor, (a, b) se defineste cafiind multimea{{a}, {a, b}}.
Definitie
Produsul carteziana doua multimi A si Beste definit astfel:
A B={(a, b)| a A si bB}
Exercitiu.
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)24
7/24/2019 Logica Matematica - Curs1
25/34
Relatii binare
DefinitieOrelatie binara ntre A si Beste o submultime a produsuluicartezianA B.O relatie binara pe A este o submultime a lui A2.
Exemple
| N N
|= {(k, n)| exista m N a.. mk=n}
7/24/2019 Logica Matematica - Curs1
26/34
Operatii cu relatii
Fie A, B, C multimi.
Daca RA B, atuncirelatia inversa R1 B A estedefinita astfel:
R1 ={(b, a)| (a, b) R}.
Daca RA B si QB C, atuncicompunerealorR QA Ceste definita astfel:
R Q={(a, c)| exista bB a.. (a, b) R si (b, c) Q}.
Diagonalalui A este A ={(a, a)| a A}.
Exercitiu
Compunerea relatiilor este asociativa.
Daca RA Batunci A
R=R si R B
=R.
26
7/24/2019 Logica Matematica - Curs1
27/34
Functii
Definitie
Ofunctieeste un triplet (A, B, R), unde A si B sunt multimi, iarRA Beste o relatie cu proprietatea ca pentru orice a Aexista un unic bB cu (a, b) R.
Vom nota o functie (A, B, R) prin f :A B, simbolul f avand
urmatoarea semnificatie: fiecarui element xA corespunde unsingur element f(x) B a.. (x, f(x)) R.
Spunem ca f :A B estedefinita pe A cu valori n B, A senumestedomeniul de definitieal functiei f si B se numestedomeniul valorilorlui f.
Notatie: BA este multimea functiilor de la A la B.
Definitie
Ofunctie partialade la A la Beste o functie f :CB, unde C
este o submultime a lui A.27
7/24/2019 Logica Matematica - Curs1
28/34
Functii
Notatii: Fie f :A Bo functie, X A si Y B.
f(X) ={f(x)| xX} esteimaginea directaa lui X prin f;f(A) esteimaginealui f.
f1(Y) ={xX |f(x) Y}esteimaginea inversaa lui Yprin f.
Definitie
Fie f :A Bo functie
f esteinjectivadaca pentru orice x1, x2A, x1=x2 implicaf(x
1)=f(x
2) (sau, echivalent, f(x
1) =f(x
2) implica
x1 =x2).
f estesurjectivadaca pentru orice yBexista xA a..f(x) =y(sau, echivalent, f(A) =B).
f estebijectivadaca f este injectiva si surjectiva.
28
F ii
7/24/2019 Logica Matematica - Curs1
29/34
Functii
Fie f :A B si g :BC doua functii. Compunerealorg f
este definita astfel:g f :A C, (g f)(x) =g(f(x)) pentru orice xA.
Functia identicaa lui A: 1A:A A, 1A(x) =x.
Definitie
O functief :A B esteinversabiladaca exista g :BA astfelncat g f = 1A si f g= 1B.
Exercitiu. O functie este bijectiva ddaca este inversabila.
DefinitieSpunem ca A esteechipotentacu Bdaca exista o bijectief :A B. Notatie: A B.
Exercitiu. A este echipotenta cu BddacaBeste echipotenta cu A.
De aceea, spunem de obicei ca A si Bsunt echipotente. 29
F i i i
7/24/2019 Logica Matematica - Curs1
30/34
Functia caracteristica
Definitie
Fie A, T multimi a.. A T. Functia caracteristicaa lui A nraport cu T este definita astfel:
A:T {0, 1}, A(x) =
1, daca xA
0, daca x /A
ProprietatiDaca A, BT si xT atunci
AB(x) = min{A(x), B(x)}= A(x) B(x)
AB(x) = max{A(x), B(x)}= A(x) +B(x) A(x) B(x)
A(x) = 1 A(x).
Observatie
Functia caracteristica se poate folosi pentru a arata ca doua
multimi sunt egale: A=B ddaca A=B. 30
F ilii
7/24/2019 Logica Matematica - Curs1
31/34
Familii
Fie I o multime nevida.
Fie A o multime. Ofamiliede elemente din A indexata de I este ofunctief :I A. Notam cu (ai)iI familia f :I A, f(i) =aipentru orice iI. Vom scrie si (ai)i sau (ai) atunci cand I estededusa din context.
Daca fiecarei iI i este asociata o multime Ai, obtinem ofamilie(indexata) de multimi(Ai)iI.
Fie (Ai)iIo familie de submultimi ale unei multimi T. Reuniunea
si intersectia familiei (Ai)iI sunt definite astfel:iI
Ai = {xT | exista iI a.. xAi}
iIAi = {xT | pentru orice iI, xAi}
31
P d l t i l i f ilii
7/24/2019 Logica Matematica - Curs1
32/34
Produsul cartezian al unei familii
Fie I o multime nevida, si (Ai)iIfamilie de multimi indexata de I.
Produsul cartezianal familiei (Ai)iI se defineste astfel:
iIAi =
f :I
iIAi |f(i) Aipentru orice iI
= {(xi)iI |xiAipentru orice iI}.
Pentru orice jI, aplicatia j :iI
AiAj, j((xi)iI) =xj se
numesteproiectie canonicaa lui iI
Ai. j este surjectiva.
Exercitiu. Fie I, J multimi nevide. Atunci
iI AijJBj= (i,j)IJAiBj si iI AijJBj= (i,j)IJAiBj.32
I {1 n}
7/24/2019 Logica Matematica - Curs1
33/34
I ={1, . . . , n}
Fie n numar natural, n1, I ={1, . . . , n} si A1
, . . ., An
T.
(xi)iI = (x1, . . . , xn), un n-tuplu (ordonat)
iI
Ai=n
i=1
Ai siiI
Ai=n
i=1
Ai
iI
Ai=n
i=1
Ai=A1 An si An =A A
n
Definitie
Orelatien-ara ntre A1, . . ., An este o submultime a produsuluicartezian
ni=1Ai.
O relatien-ara pe A este o submultime a lui An. Daca R esterelatien-ara, spunem ca n estearitatealui R.
33
Buna ordonare si inductie
7/24/2019 Logica Matematica - Curs1
34/34
Buna ordonare si inductie
Principiul bunei ordonari
Orice submultime nevida a lui N are un cel mai mic element.
Principiul inductiei
Fie S Nastfel ncat:
(i) 0 S si(ii) pentru orice n N, daca nS, atunci n+ 1 S.
Atunci S= N.
Dem.: Fie S N a.. (i) si (ii) sunt adevarate. Presupunem ca
S= N, deci N \ S=. Fie n0 cel mai mic element din N \ S. Din(i) rezulta ca n0= 0. Deoarece 1, . . . , n0 1 S, din (ii) rezultaca n0S. Am obtinut o contradictie. Prin urmare, S= N.
Observatie
Principul bunei ordonari si principiul inductiei sunt echivalente. 34