复旦大学：《离散数学》习题课讲义（李弋）03

Discrete mathematics Yi Li Software school Fudan universit March 12. 2013

. . Discrete Mathematics Yi Li Software School Fudan University March 12, 2013 Yi Li (Fudan University) Discrete Mathematics March 12, 2013 1 / 20

Review of lattice Special Lattice Boolean algebra

Review of Lattice Ideal Special Lattice Boolean Algebra Yi Li (Fudan University) Discrete Mathematics March 12, 2013 2 / 20

Examples of Proof Zenos paradox Zhuang Zi's paradox o Gong Sunlong's"a white horse is not a horse How can you persuade yourself and the others?

Examples of Proof Zeno’s paradox Zhuang Zi’s paradox Gong Sunlong’s “a white horse is not a horse” ... How can you persuade yourself and the others? Yi Li (Fudan University) Discrete Mathematics March 12, 2013 3 / 20

Examples of Proof A×iom The axiom of group theory can be formulated as follows (G1) For all 9, 2: (aoy)ox=ao(yo z G2)Fora∥:xoe=x (G3)For every there is a y such that r y=e.(right Inverse Theorem For every a there is a y such that yo =e. left inverse

Examples of Proof . Axiom . . The axiom of group theory can be formulated as follows: (G1) For all x, y, z: (x ◦ y) ◦ z = x ◦ (y ◦ z). (G2) For all x: x ◦ e = x. (G3) For every x there is a y such that x ◦ y = e. (right inverse) . Theorem . . For every x there is a y such that y ◦ x = e.(left inverse) Yi Li (Fudan University) Discrete Mathematics March 12, 2013 4 / 20

What is LogIc o Premise Argument o Conclusion o Follow o Proof

What is Logic Premise Argument Conclusion Follow Proof Yi Li (Fudan University) Discrete Mathematics March 12, 2013 5 / 20

History of Mathematical Logic Aristotle(384-322 B C. theory of syllogistic o De Morgan(1806-71), Boole(1815-64) Schroder(1841-1902 o Fregel(1848-1925), Russell(18721970) Post(1897-1954), Godel(1906-78), Henkin(1921-2006), Herbrand(1908-31) o Robbinson(1930-): Beth and Smullyan o Leibniz(1646-1716)and Hilbert(1862-1943)

History of Mathematical Logic Aristotle(384-322 B.C.): theory of syllogistic De Morgan(1806-71), Boole(1815-64), Schr¨oder(1841-1902) Frege(1848-1925), Russell(1872-1970) Post(1897-1954), G¨odel (1906-78), Henkin(1921-2006), Herbrand(1908-31) Robbinson(1930-); Beth and Smullyan Leibniz(1646-1716) and Hilbert(1862-1943) Yi Li (Fudan University) Discrete Mathematics March 12, 2013 6 / 20

Introduction to Mathematical Logic o First order logic Propositional Logic o Predicate Logic o high order logic Other type of logic Modal logic Intuitionistic logic ● Temporal logic

Introduction to Mathematical Logic First order logic Propositional Logic Predicate Logic High order logic Other type of logic Modal logic Intuitionistic logic Temporal logic Yi Li (Fudan University) Discrete Mathematics March 12, 2013 7 / 20

Introduction to Mathematical Logic o Proof system Axiom Tableaux o Resolution o Two Components o Semantics o Algorithmic approach

Introduction to Mathematical Logic Proof system Axiom Tableaux Resolution Two Components Syntax Semantics Algorithmic approach Yi Li (Fudan University) Discrete Mathematics March 12, 2013 8 / 20

Order Definition(Partial order A partial order is a set S with a binary relation on S, which is transitive and irreflexive Definition(Linear order) a partial order is a linear order. if it satisfies the trichotomy law:. <y or a=y or y<.. Definition(Well ordering) A linear order is well ordered if every nonempty set A of s has a least element

Order . Definition (Partial order) . . A partial order is a set S with a binary relation < on S, which is transitive and irreflexive. . Definition (Linear order) . . A partial order < is a linear order, if it satisfies the trichotomy law: x < y or x = y or y < x. . Definition (Well ordering) . . A linear order is well ordered if every nonempty set A of S has a least element. Yi Li (Fudan University) Discrete Mathematics March 12, 2013 9 / 20

Countable and infinite Definition( Countable) A set A is countable if there is a one-to-one mapping from a to M Definition(Finite A set A is finite if there is a one-to-one mapping from A to 0, 1,., n-1 for some n EM Definition o If A is not countable, it is uncountable o If A is not finite it is infinite

Countable and Infinite . Definition (Countable) . . A set A is countable if there is a one-to-one mapping from A to N . . Definition (Finite) . . A set A is finite if there is a one-to-one mapping from A to {0, 1, . . . , n − 1} for some n ∈ N . . Definition . . 1. If A is not countable, it is uncountable. 2. If A is not finite, it is infinite. Yi Li (Fudan University) Discrete Mathematics March 12, 2013 10 / 20