Logica Matematica - Curs1

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/


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/


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


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


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


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/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


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


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


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


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


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


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


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


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


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


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


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/


19/34


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.html


20/34


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


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


22/34

PRELIMINARII

22


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


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


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}


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


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


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


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


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


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


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}


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


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

Logica Matematica - Curs1

Documents

Transcript of Logica Matematica - Curs1