Discrete Mathematics
Course information
- Cousrse Number：01112201
- Term: 2025 Spring
- Class Times: (Tues, Thurs: 10:00 am - 11:35 am)
- Venue: Building An, A 110
- Office Hours：Friday 2-4pm or Appointment reserved
- Location: Tongji School of SEM Building A, 1229
-
Discrete Mathematics is what one needs to talk about most problems in computer science which involves discrete objects such as bits, integers, files in a directory, nodes in a network, etc. At the end of this course, students will be comfortable understanding and using this language. The other main objective is to read, write, and understand rigorous mathematical proofs of propositions involving these discrete objects.
-
I will post lecture slides for every class. There is no required textbook. However, the course will loosely follow a text by Kenneth H. Rosen, Discrete Mathematics and Its Application（Eight Edition）, 屈婉玲 耿素云 张立昂, 离散数学. Again, it is not necessary to buy this text
- Advanced Mathematics (Calculus), Linear Algebra, Data Structures, and a strong background in high school mathematics, which you can recall very well.
Course Description and Goals:
Text Book
Miscellaneous
Prerequisites
Lectures
The following schedule is tentative and subject to change. Rosen is short for Discrete Mathematics and Its Application（Eight Edition）, and 耿素云 is short for 离散数学. Readings in Rosen are optional, in case you want extra background on the subject or a different presentation from a second point of view.
| Date | Topic | Readings | |
| 1 | Feb 25 | Overview; Sets and Operations（Set definition and its notation）
|
[Rosen: 2.1 Sets;2.2 Set Operations] [耿素云: 3.1 集合的基本概念；3.2 集合的基本运算] |
| 2 | Feb 27 | 1.2 Sets and Operations(①Subset and equality of sets;②Empty set and universal set;③Set operations ; ④Venn diagram representation of set operations) |
[Rosen: 2.1 Sets;2.2 Set Operations] [耿素云: 3.1 集合的基本概念；3.2 集合的基本运算] |
| 3 | Mar 4 | 1.2 Set Operations (Proof of Identity);1.3 Proof Methods(①Direct Proof Method; Proof by Contrapositive; ②Proof by Contradiction; ②Proof by Exhaustive; ③Proof by cases; ④Constructive Proof Method)；⑤Non-Constructive Proof Method; ⑥Vacuous Proof Method) |
[Rosen: 1.7 Introduction to Proofs;1.8 Proof Methods and Strategies；5 Induction and Recur] |
| 4 | Mar 6 | 1.3 Proof Methods(⑦Trivial Proof Method;⑧Recursive Definition) |
[Rosen: 1.8 Proof Methods and Strategies；5 Induction and Recur] |
| 5 | Mar 11 | 2.1 Basic Concepts of Propositional Logic(①Propositions and Connectives; ②Propositional Formulas and Their Classification) |
[Rosen: 1.1 Propositional Logic] [耿素云: 1.1 命题符号化及联结词;1.2 命题公式及分类] |
| 6 | Mar 13 | 2.2 Propositional logic equivalence transformations（①Equivalence Expressions and Equivalence Calculus; ②Connective Complete Set） |
[Rosen: 1.1 Propositional Logic] [耿素云: 1.3 等值演算;1.5 联结词全功能集] |
| 7 | Mar 18 | 2.3 logical normal form（①Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) ; ②Principal Disjunctive Normal Form (PDNF) and Principal Conjunctive Normal Form (PCNF)） |
[Rosen: 1.1 Propositional Logic] [耿素云:1.4 范式 ] |
| 8 | Mar 20 | 3.1 Basic Concepts of First-Order Logic(①The Limitations of Propositional Logic . ②Individual Terms, Predicates, and Quantifiers.③Symbolization of First-Order Logic.) |
[Rosen: 1.4 Predicates and Quantifiers] [耿素云: 2.1 一阶逻辑基本概念;2.2 一阶逻辑合式公式及解释 ] |
| 9 | Mar 25 |
3.1 Basic Concepts of First-Order Logic(④ First-Order Logic Formulas and Classification .)；3.2 Equivalence Calculus of First-Order Logic (①First-Order Logic Equivalences and Substitution Rules Basic Equivalences Substitution Rules, Renaming Rules. ②First-Order Logic Prefix Forms.) |
[Rosen: 1.4 Predicates and Quantifiers] [耿素云: 2.3 一阶逻辑等值式与前束范式] |
| 10 | Mar 27 | 4.1 Definition and Representation of Relations(①Ordered Pairs and Cartesian Product. ②Definition of Binary Relations. ③Representation of Binary Relations.) |
[Rosen: 9.1 Relationships and Their Properties. 9.3 Representing of Relations.] [耿素云: 4.1 集合的笛卡儿积与二元关系] |
| 11 | Apr 1 | 4.2 Relational Operation(①Basic Operations of Relations.②Power Operations of Relations.)4.3 Properties of Relations(①Definition and Determination of Relation Properties ) |
[Rosen: 9.2 N-ary Relations and Their Application] [耿素云: 4.2 关系的运算] |
| 12 | Apr 3 | 4.3 Properties of Relations(①Definition and Determination of Relation Properties ②Closure of Relations.) |
[Rosen: 9.1 Relations and Their Properties.9.4 Closures of Relations] [耿素云: 4.3 关系的性质;4.4 关系的闭包] |
| 13 | Apr 8 | 4.3 Properties of Relations(②Closure of Relations.);4.4 Equivalence Relations and Partial Order Relations(①Equivalence Relations. ②Equivalence Classes and Quotient Sets. ③Partition of a Set.④Partial Order Relations.⑤Partially Ordered Sets and Hasse Diagrams.) |
[Rosen: 9.5 The equivalence Relations.9.6 Partial orderings] [耿素云: 4.5 等价关系和偏序关系] |
| 14 | Apr 10 | 5.1 Function Definition and Properties（①Definition of a Function.） |
[Rosen: 2.3 Functions ] [耿素云: 4.6 函数的定义和性质；4.7 函数的复合和反函数] |
| 15 | Apr 15 | 5.1 Function Definition and Properties（②Image and Preimage of a Function.③Properties of a Function.）;5.2 Composition of Functions and Inverse Functions(①Composition of Functions.②Inverse Functions.)5.3 Relational Algebra(①Algebra, Algebraic Systems, and Branches of lgebra.②Relational Algebra and Its Operations.③Applications of Relational Algebra) |
[Rosen: 2.3 Functions; 3.3 Complexity of Algorithms；2.3.3 Inverse Functions and Composition of Functions] [耿素云: 4.6 函数的定义和性质；4.7 函数的复合和反函数] |
| 16 | Apr 17 | 6.1 Basic Concepts of Graphs（①Undirected and Directed Graphs.②Vertex Degree and the Handshaking Lemma.） |
[Rosen: 10.1 Graphs and Graph Models；10.3 Representing Graphs and Graph Isomorphism ] [耿素云: 5.1 无向图及有向图] |
| 17 | Apr 22 | 6.1 Basic Concepts of Graphs（③Common Types of Graphs.④Subgraphs and Complements.⑤ Graph Isomorphism.） |
[Rosen: 10.1 Graphs and Graph Models；10.3 Representing Graphs and Graph Isomorphism ] [耿素云: 5.1 无向图及有向图] |
| 18 | Apr 24 | 6.2 Graph Connectivity（①Paths and Circuits. ②Connectivity and Connectedness in Undirected Graphs. ③Connectivity and Classification in Directed Graphs.）6.3 Matrix Representations of Graphs（①Incidence Matrix of an Undirected Graph. ②Incidence Matrix of a Directed Acyclic Graph.③Adjacency Matrices of Directed and Undirected Graphs. |
[Rosen: 10.4 Connectivity; 10.3.4 The incidence Matrices；10.3.3 Adjacency matrices; 10.2 Graphs Terminology and Special Types of Graphs；] [耿素云: 5.2 通路, 回路和图的连通性; 5.3 图的矩阵表示;] |
| 19 | Apr 29 | 6.3 Matrix Representations of Graphs（③Adjacency Matrices of Directed and Undirected Graphs. ④Reachability Matrix of a Graph.）6.4 Several Special Types of Graphs（①Bipartite Graphs.） |
[Rosen: 10.3.4 The incidence Matrices；10.3.3 Adjacency matrices; 10.2 Graphs Terminology and Special Types of Graphs；10.5 Euler and Hamilton paths ] [耿素云: 5.3 图的矩阵表示; 6.1 二部图；6.2 欧拉图] |
| 20 | May 1 | ||
| 21 | Mar 6 | 6.4 Several Special Types of Graphs（ ②Eulerian Graphs. ③Hamiltonian Graphs.④Planar Graphs ） |
[Rosen: 10.5 Euler and Hamilton paths；10.7 Planar Graphs；10.8 Graph Coloring ] [耿素云: 6.3 哈密顿图；6.4 平面图] |
| 22 | Mar 8 | 6.4 Several Special Types of Graphs（ ④Planar Graphs ）. 7.1 Undirected Trees （①Definition and Properties of Undirected Trees .②Spanning Trees） |
Notes: [ps(CH6),] [ps(CH7),] [pdf(CH6)] [pdf(CH7)]. [Rosen: 10.5 Euler and Hamilton paths.10.7 Planar Graphs.10.8 Graph Coloring ] [耿素云: 6.4 平面图] |
| 23 | May 13 | 7.1 Undirected Trees （②Spanning Trees）. 7.2 Rooted Trees and Their Applications（① Rooted Trees and Their Classifications.②Optimal Trees and the Huffman Algorithm.③ Optimal Prefix Codes.④Traversals of Rooted Trees and Their Applications.） |
[Rosen: 11.1 Introduction Trees.11.4 Spanning Trees.11.5 Minimum Spanning Trees. 11.2 Applications Trees.11.3 Tree Traversal] [耿素云: 7.1 无向树及生成树; 7.2 根树及其应用] |
| 24 | May 15 | 8.1 Prime Numbers(①The Division Algorithm. ② Prime and Composite Numbers. ). |
[Rosen: 4.3 Primes and Greatest common Divisor.] [耿素云: ] |
| 25 | May 20 | 8.1 Prime Numbers( ② Prime and Composite Numbers. ③ The Fundamental Theorem of Arithmetic . ④ Primality Testing – Sieve Method). 8.2 Greatest Common Divisor and Least Common Multiple（①Common divisor and Greatest common divisor (GCD).②Common multiple and Least common multiple (LCM). |
[Rosen: 4.3 Primes and Greatest common Divisor.] [耿素云: ] |
| 26 | May 22 | 8.2 Greatest Common Divisor and Least Common Multiple（③Euclidean algorithm (for finding the GCD).④Relatively prime (coprime)) 8.3 Congruence( ①Congruence.) |
[Rosen: 4.3 Primes and Greatest common Divisor.4.4 Solving Congruences] [耿素云: ] |
| 27 | May 27 | 8.3 Congruence( ②Modular Arithmetic.③Equivalence Class modulo m.) 8.4 Linear Congruence Equations and the Chinese Remainder Theorem(①Linear Congruences Modular Inverses. ② The Chinese Remainder Theorem.③ Arithmetic Operations with Large Integers.） |
[Rosen: 4.4 Solving Congruences.] [耿素云: ] |
| 28 | May 29 | 8.5 Euler's Theorem and Fermat's Little Theorem(①Fermat's Little Theorem. ②Euler's Totient Function. ③Euler's Theorem.) 9.1 Binary Operations and Their Properties(① Binary and Unary Operations . ) |
Notes: [ps(CH8)] [pdf(CH8)]. [pdf(CH9)] [pdf(CH9)]. [Rosen: 4.4 Solving Congruences.] [耿素云:9.1 二元运算及其性质] |
| 29 | Jun 3 | 9.1 Binary Operations and Their Properties(① Binary and Unary Operations . ② Properties of Binary Operations.) 9.2 Algebraic Systems（① Definition and Examples of Algebraic Systems.） |
[Rosen: ] [耿素云:9.1 二元运算及其性质] |
| 30 | Jun 5 | 9.2 Algebraic Systems（② Subalgebraic Systems and Product Algebraic Systems. ③Homomorphisms and Isomorphisms of Algebraic Systems.） |
[Rosen: ] [耿素云: 9.1 二元运算及其性质. 9.2 代数系统.] |
| 31 | Jun 10 |
9.3 Several Typical Algebraic Systems( ① Semigroups and Idempotent Elements. ② Groups. ) |
[Rosen: ] [耿素云: 9.3 几个典型的代数系统] |
| 32 | Jun 17 | 9.3 Several Typical Algebraic Systems(② Groups. ③ Rings and Fields. ) |
[Rosen: ] [耿素云: 9.3 几个典型的代数系统] |
| 33 | Jun 19 | 9.3 Several Typical Algebraic Systems( ③ Rings and Fields. ④Lattices and Boolean Algebras. ) |
[Rosen: ] [耿素云: 9.2 代数系统. 9.3 几个典型的代数系统] |
| 34 | Jun 24 |
Grading
| Grading | Percentage | Instruction |
|---|---|---|
| Discussion Attendance | 5% | When I took the course, I tried my best to attend every discussion and ask questions whenever I was confused! |
| Intermediate exams | 60% | There will be 5-10 in-class exams, each with 5 problems. Electronic devices are not allowed. |
| Final exam | 35% | Electronic devices are not allowed. Students are permitted to bring a single A4 sheet into the exam room to record essential information. |
Policies
Attend all classes including X-hours, of which I may use all of.
Students are expected to be respectful of their peers and the instructor. This includes not talking while others are talking, not using electronic devices in class, and not engaging in any other behavior that is disruptive to the learning environment.
- All exams (include Intermediate exams) submitted for credit must be your own (without help for any electronic devices).
- If you feel that the grader has not graded accurately then you should compose an email/wechat clearly writing down which problem and your reason why you think the grading is incorrect. If you are unsatisfied by the grader's response, then you can email the me (kejiwei@tongji.edu.cn) for a full regrade. I will look at the entire problem set and re-grade it completely.
Learning Objectives
- be able to read mathematical notation and terminology fluently
- become comfortable with mathematical thinking that allows you to write clean, logical, proofs
- become familiar with a number of discrete structures that are used throughout computer science
- achieve a certain clarity of thinking and expression that (as a side effect) enables you to write correct and efficient code more easily.
Policies
Attend all classes including X-hours, of which I may use all of.
Students are expected to be respectful of their peers and the instructor. This includes not talking while others are talking, not using electronic devices in class, and not engaging in any other behavior that is disruptive to the learning environment.
All exams (include Intermediate exams) submitted for credit must be your own (without help for any electronic devices).
If you feel that the grader has not graded accurately then you should compose an email/wechat clearly writing down which problem and your reason why you think the grading is incorrect. If you are unsatisfied by the grader's response, then you can email the me (kejiwei@tongji.edu.cn) for a full regrade. I will look at the entire problem set and re-grade it completely.
教学资料
作业
-
作业一
发布日期：2025-02-27
截止日期：2025-??-??
下载作业