Discrete Mathematics(ID) Spring 2013 Lecture 3: Introduction to logic 1 Overview What is a mathematical proof? How can proofs be justified? are there limitations to provability? To what extent can machines carry out mathematical proofs? We do also concern about what is the relationship between logic and computer science. Logic is profound and abstract, even much more abstract than abstract algebra. Finally, we do care about what we can learn from this course In this lecture, we first give a brief history of mathematical logic. Then we define a partial order and represent tree in an approach other than the way in last semester 2 Brief history of logic The history of logic is very long. We can even trace back to the era before systematic arithmetic occurred. Aristotle(384-322 B.C.E. ) introduced theory of syllogistic, the source of modern logic Before 19th century, logic was the garden only for philosophers From then on, logic was enriched and formalized, by mathematicians, such as De Morgan(1806-71) Boole(1815-64), and Schroder(1841-1902). Frege(1848-1925) made logic systematic and helpful to mathematics. He then established a connection between arithematics and logic. In the late of 1900s, logic became the powerful tool to expel the root of the third mathematical crisis. From now on. logic is the world of mathematicians In this course, we only introduce essential part of first order logic, which is the corner stone of whole logic building. Furthermore, it consists of propositional logic and predict logic, the former can be embedded into the latter Based on first order logic, we can introduce seconder order logic and even much higher order logic as you wish. There are also some other type of logic system, e. g, modal logic, intuitionistic logic, and temporal logic. Classic logic only has two value0 and 1. There is also a system called multiple-value Mathematical logic is aim to formalize the pattern of human deduction but not completely. It can be divided into two threads: syntax and semantics. Post(1897-1954) found the connection between syntax and semantics. He proved completeness and soundness theorem in propositional logic Godel(1906-78)proved completeness in predicate logic, which was a very important contribution Herbrand (1908-31), who disliked existences proof, gave a construct method. Henkin tried to find a model for a given set of sentences Several proof systems have been introduced for different reasons. However, they have the sameDiscrete Mathematics (II) Spring 2013 Lecture 3: Introduction to Logic Lecturer: Yi Li 1 Overview What is a mathematical proof? How can proofs be justified? are there limitations to provability? To what extent can machines carry out mathematical proofs? We do also concern about what is the relationship between logic and computer science. Logic is profound and abstract, even much more abstract than abstract algebra. Finally, we do care about what we can learn from this course. In this lecture, we first give a brief history of mathematical logic. Then we define a partial order and represent tree in an approach other than the way in last semester. 2 Brief History of Logic The history of logic is very long. We can even trace back to the era before systematic arithmetic occurred. Aristotle(384-322 B.C.E.) introduced theory of syllogistic, the source of modern logic. Before 19th century, logic was the garden only for philosophers. From then on, logic was enriched and formalized, by mathematicians, such as De Morgan (1806-71), Boole (1815-64), and Schr¨oder (1841-1902). Frege (1848-1925) made logic systematic and helpful to mathematics. He then established a connection between arithematics and logic. In the late of 1900s, logic became the powerful tool to expel the root of the third mathematical crisis. From now on, logic is the world of mathematicians. In this course, we only introduce essential part of first order logic, which is the corner stone of whole logic building. Furthermore, it consists of propositional logic and predict logic, the former can be emmbedded into the latter. Based on first order logic, we can introduce seconder order logic and even much higher order logic as you wish. There are also some other type of logic system, e.g., modal logic, intuitionistic logic, and temporal logic. Classic logic only has two value 0 and 1. There is also a system called multiple-value logic. Mathematical logic is aim to formalize the pattern of human deduction but not completely. It can be divided into two threads: syntax and semantics. Post(1897-1954) found the connection between syntax and semantics. He proved completeness and soundness theorem in propositional logic. G¨odel(1906-78) proved completeness in predicate logic, which was a very important contribution. Herbrand(1908-31), who disliked existences proof, gave a construct method. Henkin tried to find a model for a given set of sentences. Several proof systems have been introduced for different reasons. However, they have the same 1