复旦大学：《离散数学 Discrete Mathematics》英文讲稿_03

Discrete mathematics Yi Li Software school Fudan universit March 13. 2012

Discrete Mathematics Yi Li Software School Fudan University March 13, 2012 Yi Li (Fudan University) Discrete Mathematics March 13, 2012 1 / 20

Review of lattice o Special Lattice ● Boolean Algebra

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

Examples of Proof Zenos paradox o Zhuang Zis 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 13, 2012 3 / 20

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

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. Theorem For every x there is a y such that y ◦ x = e. Yi Li (Fudan University) Discrete Mathematics March 13, 2012 4 / 20

What is LogIc Premise Argument o Conclusion o Follow o Proof

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

History of Mathematical Logic Aristotle(384-322 B. C ) theory of syllogistic De morgan(1806-71), Boole(1815-64) Schroder(1841-1902 o Fregel(1848-1925), Russell(18721970) ●Post(1897-1954),Gode(190678), Henkin(?) 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(??), Herbrand(1908-31) Robbinson(1930-); Beth and Smullyan Leibniz(1646-1716) and Hilbert(1862-1943) Yi Li (Fudan University) Discrete Mathematics March 13, 2012 6 / 20

Introduction to Mathematical Logic o First order logic Propositional Logic o Predicate logic High order lo o Other type of logic ● Modal logic o 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 13, 2012 7 / 20

Introduction to Mathematical Logic o Proof system Axiom Tablea o Resolution ° Two Components 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 13, 2012 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:a<y or I=y or y<a. 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 13, 2012 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∈M 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 13, 2012 10 / 20