优先级	知识点	真题频率	是否必须掌握
⭐⭐⭐⭐⭐	Predicate Logic（述語論理）	极高（2011、2012、2013、2015、2016、2017、2018、2019、2020 等）	必须
⭐⭐⭐⭐⭐	Resolution Principle（归结法）+ CNF + Skolemization	极高	必须
⭐⭐⭐⭐⭐	Binary Relation（二元关系）	极高	必须
⭐⭐⭐⭐⭐	Graph Theory（图论）	极高	必须
⭐⭐⭐⭐☆	Partial Order（偏序）、Equivalence Relation（等价关系）	很高	必须
⭐⭐⭐⭐☆	Mathematical Induction（数学归纳法）	中高	必须
⭐⭐⭐⭐☆	Power Set（幂集）、Subset（子集）、Chain、Antichain	近两年非常高	必须
⭐⭐⭐☆☆	Boolean Algebra + Logic Function + Minimal SOP	偶尔	建议掌握
⭐⭐☆☆☆	Recurrence（递推）	极少	简单了解即可
⭐⭐☆☆☆	Combinatorics（组合）	偶尔作为证明工具	会基本计数即可

二、从历年真题总结出的知识地图

第一部分：集合（Set）

这一部分不是单独考，而是作为所有题目的基础。

需要掌握：

• element（元素）
• subset（子集）
• proper subset（真子集）
• union（并集）
• intersection（交集）
• difference（差集）
• complement（补集）
• power set（幂集）
• Cartesian product（笛卡尔积）

特别是：

• 2S2^S2S（Power Set）
• ∣S∣|S|∣S∣
• ∣2S∣=2∣S∣|2^S|=2^{|S|}∣2S∣=2∣S∣

近几年经常结合偏序一起考。2026 年直接围绕幂集上的包含关系、链（chain）、反链（antichain）和极大链设计整道题。

第二部分：Relation（二元关系）

这是大阪大学最稳定的考点之一。

必须掌握：

• reflexive
• irreflexive
• symmetric
• antisymmetric
• transitive
• equivalence relation
• partial order
• total order

以及如何证明。

很多年份直接让你判断某关系是否满足这些性质，例如 2009、2010、2012、2016、2019 等。

第三部分：偏序（Partial Order）

近年来权重越来越高。

需要掌握：

• Hasse Diagram
• maximal element
• minimal element
• greatest element
• least element
• chain
• antichain
• maximal chain
• lattice 基础概念
• inclusion order

尤其 2026 年整题都围绕

(2I(n),⊆)(2^{I(n)},\subseteq)(2I(n),⊆)

展开，包括：

• 极大元
• 极小元
• chain
• antichain
• 极大链计数
• 包含指定集合的极大链数量

这是未来最值得投入时间的新热点。

第四部分：Predicate Logic（述语逻辑）

离散数学-CH01-Predicate-Logic 这是近十五年的绝对重点。

需要掌握：

• universal quantifier（∀）
• existential quantifier（∃）
• variable
• predicate
• substitution
• interpretation
• validity
• satisfiable
• unsatisfiable
• 还要能够把自然语言翻译成逻辑公式。

2012、2013、2015、2017、2018、2019、2020 等年份都有大量相关题目。

第五部分：CNF + Resolution Principle

这是必须熟练的技能。

需要做到：

1. 消去 implication。
2. 化 Negation Normal Form。
3. Prenex Form。
4. Skolemization。
5. 转换成 CNF。
6. 使用 Resolution 推导空子句。

大阪大学几乎每隔一年都会考这一套流程。

第六部分：Graph Theory（图论）

募集要项只写了“Graph”，但实际覆盖范围相当丰富。

必须掌握：

• directed graph
• undirected graph
• path
• walk
• cycle
• connected
• strongly connected
• tree
• spanning tree
• degree
• complete graph
• subgraph
• complement graph
• bipartite graph
• matching
• reachability

其中 Matching 在 2014 年单独出过大题，近年来则更多考连通性、补图、染色和组合性质。

第七部分：Boolean Algebra 与 Logic Function

募集要项明确包含：

• Boolean Algebra
• Logic Function
• 最簡積和形（Minimal SOP）

但近年的离散结构卷中直接出现频率不高，更常在数字逻辑背景下考察。

建议掌握：

• Boolean identities
• De Morgan
• Karnaugh Map
• SOP / POS
• Minimal SOP

达到“会化简”的程度即可。

第八部分：Mathematical Induction（数学归纳法）

证明题中偶尔出现。

需要掌握：

• Base Case
• Induction Hypothesis
• Induction Step

例如 2025 年证明图论性质时就明确要求使用数学归纳法。