复旦大学：《离散数学》PPT教学课件（赵一鸣）11/28

期中测验时间: 11月4日 课件集合,关系,函数,基数组合数学

❖ 期中测验时间： ❖ 11月4日 ❖ 课件 集合，关系，函数，基数,组合数学

.o I Introduction to Set Theory ◆1 Sets and subsets &o Representation of set: Listing elements, Set builder notion, Recursive definition ☆∈,c,C 今P(4) &2. Operations on Sets 4. Operations and their properties A=?B AcB and b ca ☆ Or Properties Theorems, examples, and exercises

❖ ⅠIntroduction to Set Theory ❖ 1. Sets and Subsets ❖ Representation of set: ❖ Listing elements, Set builder notion, Recursive definition ❖ , ,  ❖ P(A) ❖ 2. Operations on Sets ❖ Operations and their Properties ❖ A=?B ❖ AB, and B A ❖ Or Properties ❖ Theorems, examples, and exercises

.3. Relations and Properties of relations reflexive ,irreflexive o symmetric asymmetric antisymmetric ◆ Transitive Closures of relations ☆r(R),S(R),t(R)= Theorems, examples, and exercises %4 Operations on Relations %Inverse relation, Composition Theorems, examples, and exercises

❖ 3. Relations and Properties of relations ❖ reflexive ,irreflexive ❖ symmetric , asymmetric ,antisymmetric ❖ Transitive ❖ Closures of Relations ❖ r(R),s(R),t(R)=? ❖ Theorems, examples, and exercises ❖ 4. Operations on Relations ❖ Inverse relation, Composition ❖ Theorems, examples, and exercises

&o 5. Equivalence relation and Partial order relations % Equivalence Relation 冷 equivalence class oo Partial order relations and Hasse Diagrams .o Extremal elements of partially ordered sets s maximal element, minimal element &o greatest element, least element &upper bound, lower bound &o least upper bound, greatest lower bound &o Theorems, examples, and exercises

❖ 5. Equivalence Relation and Partial order relations ❖ Equivalence Relation ❖ equivalence class ❖ Partial order relations and Hasse Diagrams ❖ Extremal elements of partially ordered sets: ❖ maximal element, minimal element ❖ greatest element, least element ❖ upper bound, lower bound ❖ least upper bound, greatest lower bound ❖ Theorems, examples, and exercises

%86 Everywhere functions s one to one, onto, one-to-one correspondence &o Composite functions and Inverse functions 8 Cardinality y. 8 Theorems, examples, and exercises

❖ 6.Everywhere Functions ❖ one to one, onto, one-to-one correspondence ❖ Composite functions and Inverse functions ❖Cardinality, 0 . ❖ Theorems, examples, and exercises

l Combinatorics 61. Pigeonhole principle &o Pigeon and pigeonholes ☆ example, exercise

❖II Combinatorics ❖1. Pigeonhole principle ❖ Pigeon and pigeonholes ❖ example，exercise

☆2。 Permutations and combinations Permutations of sets combinations of sets 8 circular permutation Permutations and combinations of multisets ◆ Formulae &inclusion-exclusion principle generating functions &integral solutions of the equation

❖2. Permutations and Combinations ❖ Permutations of sets, Combinations of sets ❖ circular permutation ❖ Permutations and Combinations of multisets ❖ Formulae ❖ inclusion-exclusion principle ❖ generating functions ❖ integral solutions of the equation

g Applications of Inclusion-Exclusion principle ☆ example, exercise Applications generating functions and Exponential generating functions 冷ex=1+x+x2/2!++x/n!+. 令x+x2/2!+,+x/n!+,=ex-1 冷e=1-x+x2/2!+…+(-1)x"/n!+…; 冷1+x212!+,+x2n(2n)!+,=(e+ex)/2; 冷x+x3!+…+x2n+1(2n+1)!+…=(ex-e-x)/2; %o examples, and exercises 3. recurrence relation 4 Using Characteristic roots to solve recurrence relations Using Generating functions to solve recurrence relations .examples, and exercises

❖ Applications of Inclusion-Exclusion principle ❖ example,exercise ❖ Applications generating functions and Exponential generating functions ❖ e x=1+x+x2 /2!+…+xn /n!+…; ❖ x+x2 /2!+…+xn /n!+…=ex -1; ❖ e -x=1-x+x2 /2!+…+(-1)nx n /n!+…; ❖ 1+x2 /2!+…+x2n/(2n)!+…=(ex+e-x )/2; ❖ x+x3 /3!+…+x2n+1/(2n+1)!+…=(ex -e -x )/2; ❖ examples, and exercises ❖ 3. recurrence relation ❖ Using Characteristic roots to solve recurrence relations ❖ Using Generating functions to solve recurrence relations ❖ examples, and exercises

Chapter 5 Graphs . the puzzle of the seven bridge in the Konigsberg, o on the Pregel B c 7777x D

Chapter 5 Graphs ❖ the puzzle of the seven bridge in the Königsberg, ❖ on the Pregel

B 画只日 D (b)的