A Brief Summary for Exam

离散数学考试加油！！！

Propositions

命题 (Propositions)

  • Definition (定义): A proposition is a declarative sentence that is either true or false.
    命题是一个陈述句，它的真假是确定的。
  • Truth value (真值): The truth value of a proposition is either true (T) or false (F).
    命题的真值是“真”或“假”。

Propositional Symbols

命题符号 (Propositional Symbols)

  • Definition (定义): A propositional symbol represents a proposition. For example, $ p, q, r $ are commonly used symbols for propositions.
    命题符号代表一个命题。例如，$ p, q, r $ 是常用的命题符号。

Operators

运算符 (Operators)

  • Negation (\(\neg\)): The negation of a proposition $ p $ is $ p $, meaning "not $ p $." If $ p $ is true, $ p $ is false, and vice versa.
    否定 (\(\neg\))：命题 $ p $ 的否定是 $ p $，表示“不是 $ p $”。如果 $ p $ 为真，$ p $ 为假，反之亦然。
  • Conjunction (\(\land\)): The conjunction of two propositions $ p $ and $ q $ is $ p q $, meaning "both $ p $ and $ q $." It is true only when both $ p $ and $ q $ are true.
    合取 (\(\land\))：命题 $ p $ 和 $ q $ 的合取是 $ p q \(，表示“\) p $ 和 $ q $ 都为真”。当且仅当 $ p $ 和 $ q $ 都为真时，$ p q $ 才为真。
  • Disjunction (\(\lor\)): The disjunction of $ p $ and $ q $ is $ p q $, meaning "either $ p $ or $ q $." It is false only when both $ p $ and $ q $ are false.
    析取 (\(\lor\))：命题 $ p $ 和 $ q $ 的析取是 $ p q $，表示“要么 $ p $，要么 $ q $”。当且仅当 $ p $ 和 $ q $ 都为假时，$ p q $ 才为假。
  • Implication (\(\rightarrow\)): The implication $ p q $ means "if $ p $, then $ q $." It is false only when $ p $ is true and $ q $ is false.
    蕴含 (\(\rightarrow\))：命题 $ p q $ 表示“如果 $ p $，那么 $ q $”。当且仅当 $ p $ 为真且 $ q $ 为假时，$ p q $ 才为假。
  • Biconditional (\(\leftrightarrow\)): The biconditional $ p q $ means "$ p $ if and only if $ q $." It is true when $ p $ and $ q $ have the same truth value.
    双条件 (\(\leftrightarrow\))：命题 $ p q $ 表示“当且仅当 $ p $ 和 $ q $ 具有相同的真值时”。

Truth Tables

真值表 (Truth Tables)

  • Definition (定义): A truth table is a table used to show the truth values of a compound proposition based on the truth values of its components.
    真值表是用于显示复合命题的真值的表格，基于其组成部分的真值。

Composite Propositions

复合命题 (Composite Propositions)

  • Definition (定义): A composite proposition is a proposition formed by combining two or more simpler propositions using logical operators.
    复合命题是通过逻辑运算符组合两个或更多简单命题形成的命题。

Tautology and Contradiction

重言式与矛盾式 (Tautology and Contradiction)

  • Tautology (重言式): A tautology is a proposition that is always true, no matter the truth values of the individual components.
    重言式是一个无论组成部分的真值如何，始终为真的命题。
  • Contradiction (矛盾式): A contradiction is a proposition that is always false.
    矛盾式是一个始终为假的命题。

Equivalence of Propositional Statements

命题的等价性 (Equivalence of Propositional Statements)

  • Definition (定义): Two propositional statements are equivalent if they have the same truth value in all cases.
    两个命题等价，当且仅当它们在所有情况下具有相同的真值。

Equivalence Laws

等价律 (Equivalence Laws)

  • Definition (定义): Equivalence laws are a set of rules used to transform one proposition into an equivalent proposition. Examples include:
    等价律是用于将一个命题转化为等价命题的一组规则。例如：
    • De Morgan's Laws:
      • $ (p q) p q $
      • $ (p q) p q $
        德摩根定律：
      • $ (p q) p q $
      • $ (p q) p q $

Proving Equivalence

证明命题等价 (Proving Equivalence)

  • By Truth Table (通过真值表): Construct the truth table for both propositions and compare the results. If their truth values match for every possible input, the propositions are equivalent.
    通过真值表：构造两个命题的真值表，并比较结果。如果它们对每种可能的输入的真值都匹配，那么这两个命题是等价的。
  • By Equivalence Laws (通过等价律)： Apply the equivalence laws to transform one proposition into another.
    通过等价律：应用等价律将一个命题转化为另一个命题。

Predicates

谓词 (Predicates)

  • Definition (定义): A predicate is a statement that contains one or more variables and becomes a proposition when the variables are replaced by specific values.
    谓词是一个包含一个或多个变量的陈述，当变量被特定值替代时，它变成一个命题。
    Example:
    • $ P(x) $: "x is a prime number."
      例如：
      • $ P(x) $：“x 是一个质数。”

Universal and Existential Quantifiers

全称量词与存在量词 (Universal and Existential Quantifiers)

  • Universal Quantifier (\(\forall\)): The universal quantifier is used to express that a predicate holds for all elements in a domain. It is read as "for all."
    全称量词 (\(\forall\))：用于表示一个谓词对某个领域中的所有元素都成立。读作“对于所有”。
    Example:
    • $ x , P(x) $: "For all $ x $, $ x $ is a prime number."
      例如：
      • $ x , P(x) $：“对于所有 $ x \(，\) x $ 是一个质数。”
  • Existential Quantifier (\(\exists\)): The existential quantifier is used to express that there exists at least one element in the domain for which the predicate holds. It is read as "there exists."
    存在量词 (\(\exists\))：用于表示在某个领域中存在至少一个元素使得谓词成立。读作“存在”。
    Example:
    • $ x , P(x) $: "There exists an $ x $ such that $ x $ is a prime number."
      例如：
      • $ x , P(x) $： “存在一个 $ x $，使得 $ x $ 是一个质数。”

Duality of Universal and Existential Quantifiers

全称量词与存在量词的对偶性 (Duality of Quantifiers)

  • Duality: The universal quantifier and the existential quantifier are duals of each other. This means that:

    • The negation of a universal statement becomes an existential statement, and vice versa.
    • 对偶性： 全称量词与存在量词是对偶的。这意味着：
      • 全称命题的否定变成存在命题，反之亦然。

    Example:

    • $ x , P(x) x , P(x) $
      例如：
      • $ x , P(x) x , P(x) $

Predicates Becoming Propositions

谓词变为命题 (When Predicates Become Propositions)

  • A predicate becomes a proposition when all of its variables are replaced by specific values.
    当谓词的所有变量都被特定值替代时，谓词变为命题。
    Example:
    • $ P(x) $: "x is an even number."
    • If $ x = 4 $, $ P(4) $ becomes the proposition "4 is an even number," which is true.
      例如：
      • $ P(x) $：“x 是偶数。”
      • 如果 $ x = 4 \(，\) P(4) $ 变成命题“4 是偶数”，这是对的。

Instantiation and Quantification of Variables

变量的实例化与量化 (Instantiation and Quantification of Variables)

  • Instantiation (实例化): Replacing a variable in a predicate with a specific value, making it a proposition.
    实例化：将谓词中的变量替换为特定值，使其成为命题。
    Example:
    • $ x , P(x) $: "For all $ x $, $ P(x) $ is true."
    • If we instantiate $ x $ with $ 2 $, we get $ P(2) $: "2 is even."
      例如：
      • $ x , P(x) $：“对于所有 $ x \(，\) P(x) $ 都为真。”
      • 如果我们实例化 $ x $ 为 $ 2 $，我们得到 $ P(2) $：“2 是偶数。”
  • Quantification (量化): The process of applying a quantifier (either universal or existential) to a predicate.
    量化：对谓词应用量词（全称量词或存在量词）的过程。

Nested Quantifiers

嵌套量词 (Nested Quantifiers)

  • Definition (定义): Nested quantifiers are quantifiers that appear within the scope of another quantifier. They can be used to express more complex logical relationships.
    嵌套量词是出现在另一个量词范围内的量词。它们可以用来表达更复杂的逻辑关系。
    Example:
    • $ x , y , P(x, y) $: "For all $ x $, there exists a $ y $ such that $ P(x, y) $ is true."
      例如：
      • $ x , y , P(x, y) $： “对于所有 $ x $，存在一个 $ y $，使得 $ P(x, y) $ 为真。”

Quantifiers with Negation

量词与否定 (Quantifiers with Negation)

  • Universal Quantifier with Negation:
    $ x , P(x) x , P(x) $
    The negation of a universal quantifier turns it into an existential quantifier.
    全称量词与否定：
    $ x , P(x) x , P(x) $
    全称量词的否定变为存在量词。

  • Existential Quantifier with Negation:
    $ x , P(x) x , P(x) $
    The negation of an existential quantifier turns it into a universal quantifier.
    存在量词与否定：
    $ x , P(x) x , P(x) $
    存在量词的否定变为全称量词。

Logical Expressions with Predicates, Operators, and Quantifiers

由谓词、运算符和量词构成的逻辑表达式 (Logical Expressions Formed by Predicates, Operators, and Quantifiers)

  • A logical expression can include predicates, operators (such as $ , , , $), and quantifiers (universal or existential). These expressions allow us to represent complex logical relationships between variables.
    逻辑表达式可以包含谓词、运算符（如 $ , , , $）和量词（全称量词或存在量词）。这些表达式使我们能够表示变量之间的复杂逻辑关系。
    Example:
    • $ x , y , (P(x, y) Q(x, y)) $: "For all $ x $, there exists a $ y $ such that both $ P(x, y) $ and $ Q(x, y) $ are true."
      例如：
      • $ x , y , (P(x, y) Q(x, y)) $： “对于所有 $ x $，存在一个 $ y $，使得 $ P(x, y) $ 和 $ Q(x, y) $ 都为真。”

Rules of Inference

推理规则 (Rules of Inference)

  • Definition (定义): Rules of inference are logical rules used to derive conclusions from premises. These rules are essential for constructing valid arguments and proofs.
    推理规则是用来从前提推导结论的逻辑规则。这些规则对于构建有效的论证和证明至关重要。

Common Rules of Inference:

  • Modus Ponens (MP) (肯定前件):
    • If $ P Q $ and $ P $, then $ Q $.
      如果 $ P Q $ 且 $ P $ 为真，则 $ Q $ 为真。
      Example:
      • $ P Q $, $ P $ ⟹ $ Q $
        例如：
        • $ P Q \(，\) P $ ⟹ $ Q $
  • Modus Tollens (MT) (否定后件):
    • If $ P Q $ and $ Q $, then $ P $.
      如果 $ P Q $ 且 $ Q $，则 $ P $。
      Example:
      • $ P Q $, $ Q $ ⟹ $ P $
        例如：
        • $ P Q \(，\) Q $ ⟹ $ P $
  • Resolution (消解法):
    • Resolving two clauses to derive a new clause.
      通过消解两个子句得到一个新子句。
      Example:
      • $ P Q $, $ P $ ⟹ $ Q $
        例如：
        • $ P Q \(，\) P $ ⟹ $ Q $
  • Simplification (简化法):
    • From $ P Q $, infer $ P $ (and also infer $ Q $ similarly).
      从 $ P Q $ 推导出 $ P $（同理也可以推导出 $ Q $）。
      Example:
      • $ P Q $ ⟹ $ P $
        例如：
        • $ P Q $ ⟹ $ P $
  • Addition (加法法):
    • From $ P $, infer $ P Q $.
      从 $ P $ 推导出 $ P Q $。
      Example:
      • $ P $ ⟹ $ P Q $
        例如：
        • $ P $ ⟹ $ P Q $

Universal and Existential Instantiation/Generalization

全称量化与存在量化实例化/泛化 (Universal and Existential Instantiation/Generalization)

  • Universal Instantiation (全称量化实例化):
    If $ x , P(x) $, then $ P(a) $ for any specific value $ a $.
    如果 $ x , P(x) $，则对于任何特定值 $ a \(，\) P(a) $ 都为真。
    Example:
    • $ x , P(x) $ ⟹ $ P(a) $
      例如：
      • $ x , P(x) $ ⟹ $ P(a) $
  • Existential Instantiation (存在量化实例化):
    If $ x , P(x) $, then we can introduce a specific instance $ c $ such that $ P(c) $ is true.
    如果 $ x , P(x) $，则我们可以引入一个特定实例 $ c $，使得 $ P(c) $ 为真。
    Example:
    • $ x , P(x) $ ⟹ $ P(c) $
      例如：
      • $ x , P(x) $ ⟹ $ P(c) $
  • Universal Generalization (全称量化泛化):
    If $ P(a) $ holds for an arbitrary $ a $, then we can generalize to $ x , P(x) $.
    如果 $ P(a) $ 对任意的 $ a $ 都成立，则可以推广为 $ x , P(x) $。
    Example:
    • $ P(a) $ for arbitrary $ a $ ⟹ $ x , P(x) $
      例如：
      • 对任意 $ a \(，\) P(a) $ ⟹ $ x , P(x) $

Valid Argument

有效论证 (Valid Argument)

  • Definition (定义): An argument is valid if and only if the conclusion logically follows from the premises. In a valid argument, it is impossible for the premises to be true and the conclusion false.
    有效论证是指仅当结论从前提中逻辑地推导出来时才成立。在有效论证中，前提为真而结论为假的情况是不可能发生的。
    Example:
    • Premises: $ P $, $ P Q $
    • Conclusion: $ Q $
      例如：
      • 前提：$ P \(，\) P Q $
      • 结论：$ Q $

Construction of Valid Argument using Rules of Inference

使用推理规则构建有效论证 (Construction of Valid Argument Using Rules of Inference)

  • To construct a valid argument, each step must use one of the inference rules, and we should write down each rule used along with the statements involved.
    要构建有效的论证，每一步都必须使用推理规则，并且应该写出每个规则及其使用的陈述。

Example:

  • Premises:

    1. $ P $
    2. $ P Q $

  • Inference:

    1. $ Q $ (from 1 and 2 using Modus Ponens)
      例如：
    • 前提：
      1. $ P $
      2. $ P Q $
    • 推理：
      1. $ Q $（由 1 和 2 使用肯定前件推理得出）

Proof Methods (证明方法)

证明方法 (Proof Methods)

a. Direct Proof (直接证明)

  • Definition (定义): To prove $ P Q $, assume $ P $ is true and show that $ Q $ must follow logically.
    直接证明是证明 $ P Q $，假设 $ P $ 为真并证明 $ Q $ 必须跟随其后。
    Example:
    • To prove: $ P Q $
    • Assume $ P $ is true.
    • Derive $ Q $ logically.
      例如：
      • 证明：$ P Q $
      • 假设 $ P $ 为真。
      • 逻辑地推导出 $ Q $。

b. Indirect Proof (间接证明)

  • Definition (定义): To prove $ P Q $, assume $ Q $ is true and show that this leads to a contradiction, thereby proving $ P Q $.
    间接证明是证明 $ P Q $，假设 $ Q $ 为真并证明这一假设会导致矛盾，从而证明 $ P Q $。
    Example:
    • Assume $ Q $ is true.
    • Derive a contradiction from this assumption.
    • Conclude that $ Q $ must be true, so $ P Q $ holds.
      例如：
      • 假设 $ Q $ 为真。
      • 从这一假设中推导出矛盾。
      • 结论是 $ Q $ 必须为真，因此 $ P Q $ 成立。

c. Proof by Contradiction (反证法)

  • Definition (定义): Assume $ Q $ is true and derive a contradiction (i.e., derive both $ r $ and $ r $ for some $ r $). This contradiction shows that $ Q $ must be true.
    **反证法是假设 $ Q $ 为真并推导出矛盾（即推导出某个 $ r $ 和 $

neg r $）。这个矛盾表明 $ Q $ 必须为真。**
Example:

  • Assume $ Q $.
  • Derive both $ r $ and $ r $.
  • Conclude $ Q $ is true.
    例如：
    • 假设 $ Q $。
    • 推导出 $ r $ 和 $ r $。
    • 结论是 $ Q $ 为真。

Basics of Set Theory

集合理论基础 (Basics)

  • Set (集合): A set is a collection of distinct elements or objects.
    集合是由不同元素或对象构成的集合。
    Example:
    • $ A = {1, 2, 3} $
      例如：
      • $ A = {1, 2, 3} $

Membership, Subsets, Cardinality, and Set Equality

成员关系、子集、基数和集合的相等 (Membership, Subsets, Cardinality, Set Equality)

  • Membership (成员关系): An element $ x $ is a member of a set $ A $ if $ x A $.
    如果元素 $ x $ 属于集合 $ A $，则记作 $ x A $。
    Example:
    • $ 1 A $
      例如：
      • $ 1 A $
  • Subset (子集): A set $ A $ is a subset of $ B $ if every element of $ A $ is also an element of $ B $, denoted $ A B $.
    如果集合 $ A $ 中的每个元素都是集合 $ B $ 的元素，则称 $ A $ 是 $ B $ 的子集，记作 $ A B $。
    Example:
    • $ {1, 2} {1, 2, 3} $
      例如：
      • $ {1, 2} {1, 2, 3} $
  • Cardinality (基数): The cardinality of a set $ A $, denoted $ |A| $, is the number of elements in $ A $.
    集合 $ A $ 的基数，记作 $ |A| $，表示集合 $ A $ 中元素的个数。
    Example:
    • $ |A| = 3 $ for $ A = {1, 2, 3} $
      例如：
      • 对于 $ A = {1, 2, 3} \(，\) |A| = 3 $
  • Set Equality (集合的相等): Two sets $ A $ and $ B $ are equal if they have the same elements, denoted $ A = B $.
    两个集合 $ A $ 和 $ B $ 相等，当且仅当它们包含相同的元素，记作 $ A = B $。
    Example:
    • $ A = B $ if $ A = {1, 2, 3} $ and $ B = {3, 2, 1} $
      例如：
      • 如果 $ A = {1, 2, 3} $ 和 $ B = {3, 2, 1} $，则 $ A = B $

Defining Sets: Enumeration and Builder Function

集合的定义：列举法和生成函数 (Defining Sets: Enumeration and Builder Function)

  • Enumeration (列举法): A set can be defined by listing its elements.
    集合可以通过列举它的元素来定义。
    Example:
    • $ A = {1, 2, 3} $
      例如：
      • $ A = {1, 2, 3} $
  • Builder Function (生成函数): A set can also be defined by a rule or condition that its elements satisfy.
    集合也可以通过其元素满足的规则或条件来定义。
    Example:
    • $ B = {x x } = {2, 3, 5, 7} $
      例如：
      • $ B = {x x } = {2, 3, 5, 7} $

Cartesian Product

笛卡尔积 (Cartesian Product)

  • Definition (定义): The Cartesian product of two sets $ A $ and $ B $, denoted $ A B $, is the set of all ordered pairs $ (a, b) $ where $ a A $ and $ b B $.
    两个集合 $ A $ 和 $ B $ 的笛卡尔积，记作 $ A B $，是所有有序对 $ (a, b) $ 的集合，其中 $ a A $ 且 $ b B $。
    Example:
    • If $ A = {1, 2} $ and $ B = {a, b} $, then $ A B = {(1, a), (1, b), (2, a), (2, b)} $
      例如：
      • 如果 $ A = {1, 2} $ 和 $ B = {a, b} $，则 $ A B = {(1, a), (1, b), (2, a), (2, b)} $

Power Set

幂集 (Power Set)

  • Definition (定义): The power set of a set $ A $, denoted $ (A) $, is the set of all subsets of $ A $, including the empty set and $ A $ itself.
    集合 $ A $ 的幂集，记作 $ (A) $，是所有 $ A $ 的子集的集合，包括空集和 $ A $ 本身。
    Example:
    • For $ A = {1, 2} $, the power set is $ (A) = {, {1}, {2}, {1, 2}} $
      例如：
      • 对于 $ A = {1, 2} $，幂集是 $ (A) = {, {1}, {2}, {1, 2}} $

Set Operations

集合运算 (Set Operations)

a. Union (并集)

  • Definition (定义): The union of two sets $ A $ and $ B $, denoted $ A B $, is the set of all elements that are in $ A $ or in $ B $ (or in both).
    两个集合 $ A $ 和 $ B $ 的并集，记作 $ A B $，是所有属于 $ A $ 或 $ B $（或两者）的元素的集合。
    Example:
    • If $ A = {1, 2} $ and $ B = {2, 3} $, then $ A B = {1, 2, 3} $
      例如：
      • 如果 $ A = {1, 2} $ 和 $ B = {2, 3} $，则 $ A B = {1, 2, 3} $

b. Intersection (交集)

  • Definition (定义): The intersection of two sets $ A $ and $ B $, denoted $ A B $, is the set of all elements that are in both $ A $ and $ B $.
    两个集合 $ A $ 和 $ B $ 的交集，记作 $ A B $，是所有既属于 $ A $ 又属于 $ B $ 的元素的集合。
    Example:
    • If $ A = {1, 2} $ and $ B = {2, 3} $, then $ A B = {2} $
      例如：
      • 如果 $ A = {1, 2} $ 和 $ B = {2, 3} $，则 $ A B = {2} $

c. Difference (差集)

  • Definition (定义): The difference of two sets $ A $ and $ B $, denoted $ A - B $, is the set of all elements in $ A $ but not in $ B $.
    **两个集合 $ A $ 和 $ B $ 的差集，记

作 $ A - B $，是所有属于 $ A $ 但不属于 $ B $ 的元素的集合。**
Example:

  • If $ A = {1, 2} $ and $ B = {2, 3} $, then $ A - B = {1} $
    例如：
    • 如果 $ A = {1, 2} $ 和 $ B = {2, 3} $，则 $ A - B = {1} $

d. Complement (补集)

  • Definition (定义): The complement of a set $ A $ in a universal set $ U $, denoted $ A' $, is the set of all elements in $ U $ that are not in $ A $.
    集合 $ A $ 在全集 $ U $ 中的补集，记作 $ A' $，是全集中不属于 $ A $ 的所有元素的集合。
    Example:
    • If $ U = {1, 2, 3} $ and $ A = {1} $, then $ A' = {2, 3} $
      例如：
      • 如果 $ U = {1, 2, 3} $ 和 $ A = {1} $，则 $ A' = {2, 3} $

Set Identity Laws

集合恒等律 (Set Identity Laws)

  • Identity Laws (恒等律):
    • $ A = A $
    • $ A U = A $
      恒等律：
      • $ A = A $
      • $ A U = A $
  • Complement Laws (补集律):
    • $ A A' = U $
    • $ A A' = $
      补集律：
      • $ A A' = U $
      • $ A A' = $

Proving Set Equality

证明集合相等 (Proving Set Equality)

  • By Identity Laws (通过恒等律证明): Use the identity laws to show that two sets are equal.
    通过恒等律： 使用恒等律证明两个集合相等。
  • By Membership Table (通过成员表证明): List the elements of both sets and check if they match.
    通过成员表： 列出两个集合的元素并检查它们是否匹配。

Example:

  • Prove $ A = B $ by showing that each element of $ A $ is in $ B $ and vice versa.
    例如：
    • 通过证明 $ A $ 的每个元素都在 $ B $ 中，反之亦然，来证明 $ A = B $。

Basics of Functions (函数基础)

A function is a relation between a set of inputs (domain) and a set of possible outputs (co-domain) such that each input is related to exactly one output.

函数是输入集合（定义域）和可能输出集合（值域）之间的关系，其中每个输入值都对应一个唯一的输出值。

What is a Function? (什么是函数?)

  • A function $ f $ from set $ A $ to set $ B $ is denoted as $ f: A B $, meaning that for every element $ x A $, there exists exactly one element $ y B $ such that $ f(x) = y $. 从集合 $ A $ 到集合 $ B $ 的函数记作 $ f: A B $，意味着对于每个元素 $ x A $，存在唯一的元素 $ y B $，使得 $ f(x) = y $。

What is Not a Function? (什么不是函数?)

  • A relation where an input has multiple outputs is not a function. 一个输入对应多个输出的关系不是函数。 Example:
    • $ {(1, 2), (1, 3)} $ is not a function because the input $ 1 $ is related to both $ 2 $ and $ 3 $.
      例如：
      • $ {(1, 2), (1, 3)} $ 不是一个函数，因为输入 $ 1 $ 关联了 $ 2 $ 和 $ 3 $。

Domain, Co-domain, Range, Image, and Pre-image (定义域、值域、陪域、像集和原像集)

  • Domain (定义域): The set of all possible inputs for the function.
    定义域： 函数所有可能输入的集合。
    Example:
    • For $ f(x) = x^2 $, the domain could be all real numbers $ $.
      例如：
      • 对于 $ f(x) = x^2 $，定义域可以是所有实数 $ $。
  • Co-domain (陪域): The set of all possible outputs the function could have, not necessarily the actual outputs.
    陪域： 函数可能具有的所有输出集合，但不一定是实际输出。
    Example:
    • For $ f(x) = x^2 $ with domain $ $, the co-domain is $ $.
      例如：
      • 对于 $ f(x) = x^2 $ 和定义域 $ $，陪域是 $ $。
  • Range (值域): The set of actual outputs that the function produces.
    值域： 函数实际产生的输出集合。
    Example:
    • For $ f(x) = x^2 $, the range is $ [0, ) $ if $ x $.
      例如：
      • 对于 $ f(x) = x^2 $，当 $ x $ 时，值域是 $ [0, ) $。
  • Image (像集): The actual outputs (same as range) for a specific input.
    像集： 对于特定输入的实际输出（与值域相同）。
    Example:
    • If $ f(x) = x^2 $ and $ x = 2 $, then the image of $ 2 $ is $ 4 $.
      例如：
      • 如果 $ f(x) = x^2 $ 且 $ x = 2 $，则 $ 2 $ 的像是 $ 4 $。
  • Pre-image (原像集): The set of all elements that map to a given element in the range (or co-domain).
    原像集： 所有映射到给定值域（或陪域）中的元素的集合。
    Example:
    • For $ f(x) = x^2 $, the pre-image of $ 4 $ is $ { -2, 2 } $.
      例如：
      • 对于 $ f(x) = x^2 \(，\) 4 $ 的原像集是 $ { -2, 2 } $。

Types of Functions (函数类型)

  • Injective (One-to-One) Function (单射函数)
    A function $ f: A B $ is injective (one-to-one) if different inputs map to different outputs. In other words, if $ f(a_1) = f(a_2) $, then $ a_1 = a_2 $.
    函数 $ f: A B $ 是单射（一对一）函数，当且仅当不同的输入映射到不同的输出。换句话说，如果 $ f(a_1) = f(a_2) $，则 $ a_1 = a_2 $。
    Example:
    • $ f(x) = 2x $ is injective.
      例如：
      • $ f(x) = 2x $ 是单射。
  • Surjective (Onto) Function (满射函数)
    A function $ f: A B $ is surjective (onto) if every element in the co-domain has at least one element in the domain that maps to it.
    函数 $ f: A B $ 是满射（到射）函数，当且仅当值域中的每个元素至少有一个域中的元素映射到它。
    Example:
    • $ f(x) = x^2 $ with $ A = $ and co-domain $ B = [0, ) $ is surjective.
      例如：
      • $ f(x) = x^2 $，定义域 $ A = $，值域 $ B = [0, ) $，是满射。
  • Bijective (One-to-One Correspondence) Function (双射函数)
    A function $ f: A B $ is bijective if it is both injective and surjective, meaning every element in $ A $ corresponds to exactly one element in $ B $, and every element in $ B $ has a corresponding element in $ A $.
    函数 $ f: A B $ 是双射函数，当且仅当它既是单射又是满射，意味着 $ A $ 中的每个元素对应于 $ B $ 中的一个元素，且 $ B $ 中的每个元素都有一个对应的 $ A $ 中的元素。
    Example:
    • $ f(x) = 2x + 1 $ is bijective.
      例如：
      • $ f(x) = 2x + 1 $ 是双射。

Inverse Function (反函数)

  • A function $ f: A B $ has an inverse $ f^{-1}: B A $ if and only if $ f $ is bijective. The inverse function reverses the mapping: if $ f(a) = b $, then $ f^{-1}(b) = a $.
    当且仅当函数 $ f: A B $ 是双射函数时，它才有反函数 $ f^{-1}: B A $。反函数反转映射：如果 $ f(a) = b $，则 $ f^{-1}(b) = a $。
    Example:
    • If $ f(x) = 2x + 1 $, then $ f^{-1}(x) = $.
      例如：
      • 如果 $ f(x) = 2x + 1 $，则 $ f^{-1}(x) = $。

Composition of Functions (函数的复合)

  • The composition of two functions $ f: A B $ and $ g: B C $ is a new function $ g f: A C $ defined as $ (g f)(a) = g(f(a)) $.
    两个函数 $ f: A B $ 和 $ g: B C $ 的复合是一个新的函数 $ g f: A C $，定义为 $ (g f)(a) = g(f(a)) $。
    Example:
    • If $ f(x) = x + 1 $ and $ g(x) =

2x $, then $ (g f)(x) = g(f(x)) = 2(x + 1) = 2x + 2 $.
例如：
- 如果 $ f(x) = x + 1 $ 且 $ g(x) = 2x $，则 $ (g f)(x) = g(f(x)) = 2(x + 1) = 2x + 2 $。

Definitions of Relations (关系的定义)

  • (Binary) Relation from A to B (从 A 到 B 的二元关系)
    A binary relation $ R $ from set $ A $ to set $ B $ is a subset of the Cartesian product $ A B $, which consists of ordered pairs $ (a, b) $ where $ a A $ and $ b B $.
    从集合 $ A $ 到集合 $ B $ 的二元关系 $ R $ 是笛卡尔积 $ A B $ 的一个子集，它由有序对 $ (a, b) $ 组成，其中 $ a A \(，\) b B $。
    Example:
    • If $ A = {1, 2} $ and $ B = {a, b} $, then $ R = {(1, a), (2, b)} $ is a relation from $ A $ to $ B $.
      例如：
      • 如果 $ A = {1, 2} $ 和 $ B = {a, b} $，则 $ R = {(1, a), (2, b)} $ 是从 $ A $ 到 $ B $ 的关系。
  • Relation on A (集合 A 上的关系)
    A relation $ R $ on set $ A $ is a subset of $ A A $, consisting of ordered pairs $ (a, b) $ where $ a, b A $.
    集合 $ A $ 上的关系 $ R $ 是笛卡尔积 $ A A $ 的一个子集，它由有序对 $ (a, b) $ 组成，其中 $ a, b A $。
    Example:
    • If $ A = {1, 2, 3} $, then $ R = {(1, 1), (2, 3)} $ is a relation on $ A $.
      例如：
      • 如果 $ A = {1, 2, 3} $，则 $ R = {(1, 1), (2, 3)} $ 是集合 $ A $ 上的关系。
  • n-ary Relation (n元关系)
    An $ n $-ary relation $ R $ is a subset of $ A_1 A_2 A_n $, consisting of ordered $ n $-tuples $ (a_1, a_2, , a_n) $ where $ a_i A_i $ for $ i = 1, 2, , n $.
    n元关系 $ R $ 是 $ A_1 A_2 A_n $ 的一个子集，它由有序的 $ n $-元组 $ (a_1, a_2, , a_n) $ 组成，其中 $ a_i A_i \(，\) i = 1, 2, , n $。
    Example:
    • If $ A_1 = {1, 2} $, $ A_2 = {a, b} $, then a 2-ary relation could be $ R = {(1, a), (2, b)} $.
      例如：
      • 如果 $ A_1 = {1, 2} \(，\) A_2 = {a, b} $，则 2 元关系可能是 $ R = {(1, a), (2, b)} $。
  • Functions as Special Cases of Relations (函数是关系的特例)
    A function is a special case of a binary relation where each element in the domain is related to exactly one element in the co-domain. In contrast, a general binary relation may relate one element to multiple elements.
    函数是二元关系的特例，其中定义域中的每个元素都与陪域中的一个元素关联。相比之下，一般的二元关系可能将一个元素与多个元素关联。
    Example:
    • $ f(x) = x + 1 $ is a function (each $ x $ is related to exactly one $ y $), but $ R = {(1, 2), (1, 3)} $ is not a function, as 1 is related to both 2 and 3.
      例如：
      • $ f(x) = x + 1 $ 是一个函数（每个 $ x $ 只与一个 $ y $ 关联），但 $ R = {(1, 2), (1, 3)} $ 不是函数，因为 $ 1 $ 同时与 $ 2 $ 和 $ 3 $ 关联。

2. Properties of Relations (关系的性质)

Relations can have various properties, which can be identified based on their structure.

关系可以具有多种性质，可以通过它们的结构来识别。

Reflexive / Irreflexive (自反 / 非自反)

  • A relation $ R $ on set $ A $ is reflexive if for every element $ a A $, $ (a, a) R $.
    集合 $ A $ 上的关系 $ R $ 是自反的，当且仅当对于每个 $ a A $，都有 $ (a, a) R $。
    Example:
    • $ R = {(1, 1), (2, 2), (3, 3)} $ is reflexive on $ A = {1, 2, 3} $.
      例如：
      • $ R = {(1, 1), (2, 2), (3, 3)} $ 在集合 $ A = {1, 2, 3} $ 上是自反的。
  • A relation $ R $ is irreflexive if for no element $ a A $, $ (a, a) R $.
    如果对于集合 $ A $ 中的任何元素 $ a $，都没有 $ (a, a) R $，则关系 $ R $ 是非自反的。
    Example:
    • $ R = {(1, 2), (2, 3)} $ is irreflexive on $ A = {1, 2, 3} $.
      例如：
      • $ R = {(1, 2), (2, 3)} $ 在集合 $ A = {1, 2, 3} $ 上是非自反的。

Symmetric / Asymmetric / Antisymmetric (对称 / 非对称 / 反对称)

  • A relation $ R $ is symmetric if for every pair $ (a, b) R $, $ (b, a) R $.
    关系 $ R $ 是对称的，当且仅当对于每个 $ (a, b) R $，都有 $ (b, a) R $。
    Example:

    • $ R = {(1, 2), (2, 1)} $ is symmetric.
      例如：
      • $ R = {(1, 2), (2, 1)} $ 是对称的。

  • A relation $ R $ is asymmetric if for no pair $ (a, b) R $, $ (b, a) R $.
    关系 $ R $ 是非对称的，当且仅当对于任何 $ (a, b) R $，都没有 $ (b, a) R $。
    Example:

    • $ R = {(1, 2), (2, 3)} $ is asymmetric.
      例如：
      • $ R = {(1, 2), (2, 3)} $ 是非对称的。

  • A relation $ R $ is antisymmetric if for all pairs $ (a, b) $ and $ (b, a) R $, $ a = b $.
    关系 $ R $ 是反对称的，当且仅当对于所有的对 $ (a, b) $ 和 $ (b, a) R $，都有 $ a = b $。
    Example:

    • $ R = {(1, 2), (2, 1), (3, 3)} $ is not antisymmetric.
      例如：

      • $ R = {(1, 2), (2, 1), (3, 3)} $ 不是反对称的。

Transitive (传递性)

A relation $ R $ is transitive if whenever $ (a, b) R $ and $ (b, c) R $, it follows that $ (a, c) R $.
关系 $ R $ 是传递的，当且仅当对于所有的 $ (a, b) R $ 和 $ (b, c) R $，都有 $ (a, c) R $。
Example:

  • $ R = {(1, 2), (2, 3), (1, 3)} $ is transitive.
    例如：
    • $ R = {(1, 2), (2, 3), (1, 3)} $ 是传递的。

Combining Relations (关系的组合)

  • Union of Relations (关系的并集)
    $ R_1 R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $.
    并集 $ R_1 R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $。

  • Intersection of Relations (关系的交集)
    $ R_1 R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $.
    交集 $ R_1 R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $。

  • Difference of Relations (关系的差集)
    $ R_1 - R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $.
    差集 $ R_1 - R_2 = {(a, b) (a, b) R_1 (a, b) R_2 } $。

  • Composition of Relations (关系的复合)
    The composition of $ R_1 $ and $ R_2 $, denoted $ R_1 R_2 $, consists of all pairs $ (a, c) $ such that there exists a $ b $ where $ (a, b) R_1 $ and $ (b, c) R_2 $.
    关系 $ R_1 $ 和 $ R_2 $ 的复合，记作 $ R_1 R_2 $，由所有的有序对 $ (a, c) $ 组成，其中存在一个 $ b $，使得 $ (a, b) R_1 $ 且 $ (b, c) R_2 $。

Representing Relations: $ R $ from $ A $ to $ B $ (关系的表示：$ R $ 从 $ A $ 到 $ B $)

1. Set of Ordered Pairs (有序对集合)

A relation $ R $ from $ A $ to $ B $ is represented as a set of ordered pairs:
$ R = { (a, b) aRb (a, b) A B } $
关系 $ R $ 从集合 $ A $ 到集合 $ B $ 被表示为有序对集合：
$ R = { (a, b) aRb (a, b) A B } $

  • Example (例子):
    If $ A = {1, 2} $ and $ B = {x, y} $, and the relation is $ R = {(1, x), (2, y)} $, then the relation is the set of ordered pairs $ {(1, x), (2, y)} $.
    例如：
    如果 $ A = {1, 2} $ 和 $ B = {x, y} $，并且关系是 $ R = {(1, x), (2, y)} $，那么该关系就是有序对集合 $ {(1, x), (2, y)} $。

2. 0 – 1 Matrix (0-1 矩阵)

A relation $ R $ from $ A $ to $ B $ can be represented by a $ |A| |B| $ matrix, where each element $ m_{ij} $ is 1 if the pair $ (a_i, b_j) $ belongs to the relation, and 0 otherwise.
关系 $ R $ 从 $ A $ 到 $ B $ 可以通过一个 $ |A| |B| $ 矩阵表示，其中每个元素 $ m_{ij} $ 为 1，如果有序对 $ (a_i, b_j) $ 属于该关系，否则为 0。

  • Example (例子):
    If $ A = {1, 2} $ and $ B = {x, y} $, and $ R = {(1, x), (2, y)} \(, the matrix would look like this:\) \[\begin{matrix} m_{11} = 1 & m_{12} = 0 \\ m_{21} = 0 & m_{22} = 1 \end{matrix}\] $
    例如：
    如果 $ A = {1, 2} $ 和 $ B = {x, y} $，并且关系是 $ R = {(1, x), (2, y)} \(，那么矩阵表示为：\) \[\begin{matrix} m_{11} = 1 & m_{12} = 0 \\ m_{21} = 0 & m_{22} = 1 \end{matrix}\] $

3. Directed Graph (有向图)

A relation $ R $ from $ A $ to $ B $ can also be represented as a directed graph $ (V, E) $, where $ V = A B $ (or $ V = A $ if the relation is on $ A $) and the edges $ E $ represent the ordered pairs in the relation.
关系 $ R $ 从 $ A $ 到 $ B $ 还可以表示为一个有向图 $ (V, E) $，其中 $ V = A B $（如果关系定义在 $ A $ 上，则 $ V = A $），边 $ E $ 表示关系中的有序对。

  • Example (例子):
    If $ A = {1, 2} $ and $ B = {x, y} $, and $ R = {(1, x), (2, y)} $, the directed graph would have two vertices (1, 2, x, y) and directed edges from 1 to x, and 2 to y.
    例如：
    如果 $ A = {1, 2} $ 和 $ B = {x, y} $，并且关系是 $ R = {(1, x), (2, y)} $，则有向图将包含两个顶点（1，2，x，y）和从 1 到 x，以及从 2 到 y 的有向边。

Converting Between Representations (三种表示之间的转换)

  1. From Set of Ordered Pairs to 0-1 Matrix (从有序对集合到 0-1 矩阵)
    For each pair $ (a_i, b_j) R $, set $ m_{ij} = 1 $, otherwise $ m_{ij} = 0 $.
    对于关系中的每一对 $ (a_i, b_j) R $，设置 $ m_{ij} = 1 $，否则 $ m_{ij} = 0 $。

  2. From Set of Ordered Pairs to Directed Graph (从有序对集合到有向图)
    Create a vertex for each element in $ A $ and $ B $, then draw a directed edge from $ a_i $ to $ b_j $ for each $ (a_i, b_j) R $.
    为 $ A $ 和 $ B $ 中的每个元素创建一个顶点，然后为每个 $ (a_i, b_j) R $ 从 $ a_i $ 到 $ b_j $ 画一个有向边。

  3. From 0-1 Matrix to Set of Ordered Pairs (从 0-1 矩阵到有序对集合)
    For each $ m_{ij} = 1 $, include $ (a_i, b_j) $ in the set of ordered pairs.
    对于每个 $ m_{ij} = 1 $，将 $ (a_i, b_j) $ 包含在有序对集合中。

  4. From Directed Graph to Set of Ordered Pairs (从有向图到有序对集合)
    For each directed edge from vertex $ a_i $ to vertex $ b_j $, include $ (a_i, b_j) $ in the set of ordered pairs.
    对于从顶点 $ a_i $ 到顶点 $ b_j $ 的每条有向边，将 $ (a_i, b_j) $ 包含在有序对集合中。

Closure of Relations (关系的闭包)

Definition (定义):

The closure of a relation $ R $ is obtained by adding the minimum number of ordered pairs to $ R $ to ensure that the relation has a certain property $ P $.
关系 $ R $ 的闭包是通过向 $ R $ 添加最少的有序对，使得该关系具有某个属性 $ P $ 而得到的。

  • $ R' R $: The closure $ R' $ contains $ R \(, meaning it includes all the original pairs of the relation. **\) R' R $**：闭包 $ R' $ 包含 $ R $，即它包括关系中的所有原始有序对。

  • Property $ P $: The relation $ R' $ has the property $ P $, which could be reflexivity, symmetry, transitivity, or any other desired property.
    属性 $ P $：关系 $ R' $ 具有属性 $ P $，该属性可以是自反性、对称性、传递性或任何其他期望的属性。

  • If $ R'' R $ and $ R'' $ has property $ P $, then $ R'' R' $, meaning that $ R' $ is the smallest relation with property $ P $ that contains $ R $.
    如果 $ R'' R $ 且 $ R'' $ 具有属性 $ P $，则 $ R'' R' $，这意味着 $ R' $ 是包含 $ R $ 的具有属性 $ P $ 的最小关系。

Hence, $ R' $ is called the $ P $-closure of $ R \(. **因此，\) R' $ 被称为 $ R $ 的 $ P $-闭包。**

Types of Closures (闭包的类型)

  1. Reflexive Closure (自反闭包)
    The reflexive closure $ r(R) $ of a relation $ R $ is the smallest reflexive relation that contains $ R $. It is obtained by adding the minimal number of pairs $ (a, a) $ for all $ a A $ (the domain of the relation) that are not already in $ R $.
    自反闭包 $ r(R) $ 是包含关系 $ R $ 的最小自反关系。通过添加所有 $ a A $（关系的定义域）中尚未包含在 $ R $ 中的最小数量的对 $ (a, a) $ 来得到它。

    • Formally (形式化定义):
      $ r(R) = R $
      where $ $ is the diagonal set $ {(a, a) a A} $.
      其中 $ $ 是对角线集合 $ {(a, a) a A} $。

    • Example (例子):
      If $ R = {(1, 2), (2, 3)} $ and $ A = {1, 2, 3} $, then the reflexive closure $ r(R) $ would be $ {(1, 2), (2, 3), (1, 1), (2, 2), (3, 3)} $.

  1. Symmetric Closure (对称闭包)
    The symmetric closure $ s(R) $ of a relation $ R $ is the smallest symmetric relation that contains $ R $. It is obtained by adding the pairs $ (b, a) $ whenever $ (a, b) R $ and $ (b, a) R $.
    对称闭包 $ s(R) $ 是包含关系 $ R $ 的最小对称关系。通过每当 $ (a, b) R $ 且 $ (b, a) R $ 时，添加对 $ (b, a) $ 来得到它。

    • Formally (形式化定义):
      $ s(R) = R R^{-1} $
      where $ R^{-1} $ is the inverse of $ R $, i.e., the set $ {(b, a) (a, b) R} $.
      其中 $ R^{-1} $ 是 $ R $ 的逆，即集合 $ {(b, a) (a, b) R} $。

    • Example (例子):
      If $ R = {(1, 2), (2, 3)} $, then the symmetric closure $ s(R) $ would be $ {(1, 2), (2, 3), (2, 1), (3, 2)} $.

  1. Transitive Closure (传递闭包)
    The transitive closure $ t(R) $ of a relation $ R $ is the smallest transitive relation that contains $ R $. It is obtained by adding the pairs $ (a, c) $ whenever there exists a sequence of pairs $ (a, b) $ and $ (b, c) $ in $ R $, such that $ (a, c) $ is not already in $ R $.
    传递闭包 $ t(R) $ 是包含关系 $ R $ 的最小传递关系。通过每当 $ R $ 中存在一对序列 $ (a, b) $ 和 $ (b, c) $，且 $ (a, c) $ 尚未包含在 $ R $ 中时，添加对 $ (a, c) $ 来得到它。

    • Formally (形式化定义):
      The transitive closure can be described as:
      $ t(R) = R {(a, c) b (a, b) R (b, c) R} $
      传递闭包可以描述为：
      $ t(R) = R {(a, c) b (a, b) R (b, c) R} $

    • Example (例子):
      If $ R = {(1, 2), (2, 3)} $, then the transitive closure $ t(R) $ would be $ {(1, 2), (2, 3), (1, 3)} $.

  • Reflexive Closure (自反闭包): Adds missing pairs $ (a, a) $ for all $ a A $.
  • Symmetric Closure (对称闭包): Adds the inverse of each pair $ (a, b) $, i.e., $ (b, a) $, if not already present.
  • Transitive Closure (传递闭包): Adds pairs $ (a, c) $ if there is a sequence of pairs $ (a, b) $ and $ (b, c) $ in $ R $.

Equivalence Relations (等价关系)

Definition (定义):

An equivalence relation on a set $ A $ is a relation $ R $ that satisfies the following three properties:

等价关系是集合 $ A $ 上的一种关系 $ R $，它满足以下三种性质：

  1. Reflexive (自反性): For all $ a A $, $ aRa $.
    自反性：对于所有 $ a A $，都有 $ aRa $。

  2. Symmetric (对称性): For all $ a, b A $, if $ aRb $, then $ bRa $.
    对称性：对于所有 $ a, b A $，如果 $ aRb $，则 $ bRa $。

  3. Transitive (传递性): For all $ a, b, c A $, if $ aRb $ and $ bRc $, then $ aRc $.
    传递性：对于所有 $ a, b, c A $，如果 $ aRb $ 且 $ bRc $，则 $ aRc $。

Equivalence Class (等价类)

  • An equivalence class of an element $ a A $ with respect to the equivalence relation $ R $ is the set of all elements $ b A $ that are related to $ a $ by $ R $.
    等价类是相对于等价关系 $ R $ 来说，包含所有与元素 $ a A $ 通过关系 $ R $ 相关的元素 $ b A $ 的集合。

  • The equivalence class of $ a $ is denoted by $ [a]_R $, and it is defined as:
    **元素 $ a $ 的等价类记作 $ [a]_R \(，定义为：**\) [a]_R = { b A bRa } $ **for all $ b A $, if $ bRa $, then $ b _R $.**
    **对于所有 $ b A $，如果 $ bRa $，则 $ b _R $。**

  • If $ aRb $, then the equivalence classes $ [a]_R $ and $ [b]_R $ are equal:
    **如果 $ aRb $，则等价类 $ [a]_R $ 和 $ [b]_R $ 是相等的：** $ [a]_R = [b]_R $ and the intersection of the two equivalence classes is non-empty:
    且这两个等价类的交集非空： $ [a]_R _R $

  • If $ a $ is not related to $ b $ (i.e., $ a b $), then their equivalence classes are disjoint:
    **如果 $ a $ 不与 $ b $ 相关（即 $ a b \(），则它们的等价类是不相交的：**\) [a]_R _R _R _R = $

Partition of a Set (集合的划分)

A set $ A $ is partitioned into equivalence classes by an equivalence relation $ R $ if the following conditions hold:

集合 $ A $ 被等价关系 $ R $ 划分为等价类，当且仅当满足以下条件：

  1. Non-emptiness (非空性): Each equivalence class $ A_i $ is non-empty, i.e., $ A_i $ for all $ i I $, where $ I $ is the index set.
    每个等价类 $ A_i $ 是非空的，即对于所有 $ i I $，有 $ A_i $，其中 $ I $ 是索引集。

  2. Disjointness (互不相交性): If $ i j $, then the equivalence classes $ A_i $ and $ A_j $ are disjoint, i.e., $ A_i A_j = $.
    如果 $ i j $，则等价类 $ A_i $ 和 $ A_j $ 互不相交，即 $ A_i A_j = $。

  3. Union (并集性): The union of all equivalence classes is equal to the set $ A \(, i.e.,\) _{i I} A_i = A $ **所有等价类的并集等于集合 $ A \(，即：**\) _{i I} A_i = A $

Thus, equivalence classes of a relation $ R $ on a set $ A $ partition the set $ A $ into disjoint subsets.
因此，关系 $ R $ 在集合 $ A $ 上的等价类将集合 $ A $ 划分为互不相交的子集。

  • An equivalence relation is reflexive, symmetric, and transitive.
    等价关系是自反的、对称的和传递的。

  • Equivalence class $ [a]_R $ is the set of elements related to $ a $ under $ R $.
    等价类 $ [a]_R $ 是与 $ a $ 在关系 $ R $ 下相关的所有元素的集合。

  • If $ aRb $, then $ [a]_R = [b]_R $, and the intersection of their equivalence classes is non-empty.
    如果 $ aRb $，则 $ [a]_R = [b]_R $，且它们的等价类的交集非空。

  • A set $ A $ is partitioned into equivalence classes by $ R $ if:

    1. Each equivalence class is non-empty.
    2. Equivalence classes are disjoint.
    3. The union of equivalence classes is $ A $.

    集合 $ A $ 被关系 $ R $ 划分为等价类，当且仅当：

    1. 每个等价类是非空的。
    2. 等价类互不相交。
    3. 等价类的并集是 $ A $。

Partial Orderings (偏序关系)

Definition (定义):

A partial ordering on a set $ A $ is a binary relation $ $ that satisfies the following three properties:

偏序关系是集合 $ A $ 上的二元关系 $ $，它满足以下三个性质：

  1. Reflexive (自反性): For all $ a A $, $ a a $.
    自反性：对于所有 $ a A $，都有 $ a a $。

  2. Antisymmetric (反对称性): For all $ a, b A $, if $ a b $ and $ b a $, then $ a = b $.
    反对称性：对于所有 $ a, b A $，如果 $ a b $ 且 $ b a $，则 $ a = b $。

  3. Transitive (传递性): For all $ a, b, c A $, if $ a b $ and $ b c $, then $ a c $.
    传递性：对于所有 $ a, b, c A $，如果 $ a b $ 且 $ b c $，则 $ a c $。

Comparable and Incomparable (可比与不可比)

  • Comparable (可比): Two elements $ a $ and $ b $ in $ A $ are said to be comparable if either $ a b $ or $ b a $.
    可比：集合 $ A $ 中的两个元素 $ a $ 和 $ b $，如果满足 $ a b $ 或 $ b a $，则称它们为可比元素。

  • Incomparable (不可比): Two elements $ a $ and $ b $ in $ A $ are said to be incomparable if neither $ a b $ nor $ b a $.
    不可比：集合 $ A $ 中的两个元素 $ a $ 和 $ b $，如果既不满足 $ a b $，也不满足 $ b a $，则称它们为不可比元素。

Types of Orderings (序关系的类型)

  • Totally Ordered (全序): A set $ A $ is totally ordered under a relation $ $ if every pair of elements in $ A $ is comparable. That is, for all $ a, b A $, either $ a b $ or $ b a $.
    全序：如果集合 $ A $ 中的每一对元素都可比，则称集合 $ A $ 在关系 $ $ 下为全序。即，对于所有 $ a, b A $，要么 $ a b $，要么 $ b a $。

  • Well-Ordered (良序): A set $ A $ is well-ordered if it is totally ordered and every non-empty subset of $ A $ has a least element.
    良序：如果集合 $ A $ 是全序的，且 $ A $ 的每个非空子集都有最小元素，则称集合 $ A $ 为良序。

  • Lexicographic Order (字典序): A set $ A $ of tuples is lexicographically ordered if the first components of the tuples are ordered first, then the second components, and so on.
    字典序：如果集合 $ A $ 是元组的集合，并且按元组的第一个分量排序，然后是第二个分量，以此类推，则称集合 $ A $ 为字典序。

Hasse Diagrams (哈斯图)

A Hasse diagram is a graphical representation of a partial order. It is drawn by:

  • Vertices representing the elements of the set.
  • Edges representing the relations between elements, where an edge from $ a $ to $ b $ indicates that $ a b $ and there is no element $ c $ such that $ a c b $.
    哈斯图是偏序关系的图形表示。它由以下部分组成：
    • 顶点代表集合中的元素。
    • 边表示元素之间的关系，边从 $ a $ 到 $ b $ 表示 $ a b $，且不存在元素 $ c $ 使得 $ a c b $。

Maximal and Minimal Elements (最大元素和最小元素)

  • Maximal Element (最大元素): An element $ m A $ is maximal if there is no element $ x A $ such that $ m < x $ (i.e., $ m x $ and $ m x $).
    最大元素：元素 $ m A $ 被称为最大元素，如果没有元素 $ x A $ 满足 $ m < x $（即 $ m x $ 且 $ m x $）。

  • Minimal Element (最小元素): An element $ m A $ is minimal if there is no element $ x A $ such that $ x < m $ (i.e., $ x m $ and $ x m $).
    最小元素：元素 $ m A $ 被称为最小元素，如果没有元素 $ x A $ 满足 $ x < m $（即 $ x m $ 且 $ x m $）。

Greatest and Least Elements (最大元素与最小元素)

  • Greatest Element (最大元素): An element $ g A $ is the greatest element if for all $ x A $, $ x g $.
    最大元素：元素 $ g A $ 被称为最大元素，如果对于所有 $ x A $，都有 $ x g $。

  • Least Element (最小元素): An element $ l A $ is the least element if for all $ x A $, $ l x $.
    最小元素：元素 $ l A $ 被称为最小元素，如果对于所有 $ x A $，都有 $ l x $。

Upper Bound and Lower Bound (上界与下界)

  • Upper Bound (上界): An element $ u A $ is an upper bound of a subset $ B A $ if for all $ b B $, $ b u $.
    上界：元素 $ u A $ 是子集 $ B A $ 的上界，如果对于所有 $ b B $，都有 $ b u $。

  • Lower Bound (下界): An element $ l A $ is a lower bound of a subset $ B A $ if for all $ b B $, $ l b $.
    下界：元素 $ l A $ 是子集 $ B A $ 的下界，如果对于所有 $ b B $，都有 $ l b $。

  • Least Upper Bound (lub, 最小上界): The least upper bound (lub) of a subset $ B A $ is the smallest element $ u A $ that is an upper bound of $ B $.
    最小上界：子集 $ B A $ 的最小上界（lub）是集合 $ A $ 中的最小的上界元素 $ u $。

  • Greatest Lower Bound (glb, 最大下界): The greatest lower bound (glb) of a subset $ B A $ is the largest element $ l A $ that is a lower bound of $ B $.
    最大下界：子集 $ B A $ 的最大下界（glb）是集合 $ A $ 中最大的下界元素 $ l $。

  • Partial ordering is a binary relation that is reflexive, antisymmetric, and transitive.
    偏序关系是一个自反的、反对称的和传递的二元关系。

  • Comparable elements are those that are related by the ordering, while incomparable elements are those that are not.
    可比元素是指通过偏序关系相关的元素，不可比元素则是指没有相关性的元素。

  • **Tot

ally ordered** sets have a total relation between all elements, while well-ordered sets additionally have a least element in every non-empty subset.
全序集合中所有元素都有一个完整的偏序关系，良序集合则是每个非空子集都有最小元素。

  • Hasse diagrams visually represent partial orders, with vertices for elements and edges showing the relations.
    哈斯图通过顶点和边来可视化偏序关系。

  • Maximal, minimal, greatest, and least elements help to describe the structure of ordered sets, and upper and lower bounds provide limits on subsets.
    最大、最小、最大元素和最小元素描述了有序集合的结构，而上界和下界则提供了子集的极限。

Graphs (图论) – Sections 8.1 – 8.8

Definitions (定义)

  • Graph (图): A graph $ G $ consists of a set of vertices $ V $ and a set of edges $ E $ where each edge is a pair of vertices.
    图：图 $ G $ 由一组顶点 $ V $ 和一组边 $ E $ 组成，每条边是两个顶点的有序或无序对。

  • Vertex (顶点): A point in a graph, denoted by $ v $.
    顶点：图中的一个点，通常用 $ v $ 表示。

  • Edge (边): A connection between two vertices, denoted by $ (u, v) $ for undirected graphs or $ (u v) $ for directed graphs.
    边：两个顶点之间的连接，对于无向图用 $ (u, v) $ 表示，指向图用 $ (u v) $ 表示。

Simple, Undirected, and Directed Graphs (简单图、无向图和有向图)

  • Simple Graph (简单图): A graph without loops or multiple edges between any pair of vertices.
    简单图：没有环路或任意两顶点之间没有多重边的图。

  • Undirected Graph (无向图): A graph where edges have no direction. An edge between vertices $ u $ and $ v $ is denoted $ (u, v) $.
    无向图：边没有方向。两个顶点 $ u $ 和 $ v $ 之间的边用 $ (u, v) $ 表示。

  • Directed Graph (有向图): A graph where edges have direction. An edge between vertices $ u $ and $ v $ is denoted $ (u v) $.
    有向图：边有方向。两个顶点 $ u $ 和 $ v $ 之间的边用 $ (u v) $ 表示。

Degree of Vertex (顶点的度)

  • Degree (度): The degree of a vertex is the number of edges incident to it.
    度：顶点的度是与它相连的边的数量。

  • Indegree (入度): In a directed graph, the indegree of a vertex $ v $ is the number of edges directed toward $ v $.
    入度：在有向图中，顶点 $ v $ 的入度是指向 $ v $ 的边的数量。

  • Outdegree (出度): In a directed graph, the outdegree of a vertex $ v $ is the number of edges directed away from $ v $.
    出度：在有向图中，顶点 $ v $ 的出度是从 $ v $ 指向其他顶点的边的数量。

Special Graphs (特殊图)

  • Complete Graph (完全图): A graph in which every pair of distinct vertices is connected by a unique edge.
    完全图：每一对不同的顶点都有一条独特的边相连的图。

  • Bipartite Graph (二分图): A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.
    二分图：图的顶点可以分为两个不相交的集合，并且每一条边都连接一个集合中的顶点和另一个集合中的顶点。

  • Complete Bipartite Graph (完全二分图): A bipartite graph in which every vertex in one set is connected to every vertex in the other set.
    完全二分图：每个集合中的每个顶点都与另一个集合中的每个顶点相连接的二分图。

  • N-Cube (n-立方体): A graph representing the vertices and edges of an $ n $-dimensional cube. The vertices represent all binary sequences of length $ n $, and an edge exists between two vertices if their sequences differ in exactly one position.
    n-立方体：表示 $ n $-维立方体的顶点和边的图。顶点表示长度为 $ n $ 的所有二进制序列，如果两个序列在一个位置上有所不同，则它们之间有一条边。

Subgraph (子图)

  • Subgraph (子图): A subgraph of a graph $ G $ is a graph formed by a subset of the vertices and edges of $ G $.
    子图：图 $ G $ 的子图是由 $ G $ 的顶点和边的子集组成的图。

Adjacency (邻接)

  • Adjacency (邻接): Two vertices $ u $ and $ v $ are adjacent if there is an edge between them. In undirected graphs, this means $ (u, v) $ is an edge, and in directed graphs, it means $ (u v) $.
    邻接：如果两个顶点 $ u $ 和 $ v $ 之间有一条边，则称它们为邻接。在无向图中，这意味着存在边 $ (u, v) $，在有向图中，这意味着存在边 $ (u v) $。

Degree Sum Formulas (度数和公式)

  • For Undirected Graphs (无向图): The sum of the degrees of all vertices in an undirected graph is twice the number of edges.
    无向图：无向图中所有顶点的度数之和等于边数的两倍，公式为：
    $ _{v V} (v) = 2|E| $

  • For Directed Graphs (有向图): The sum of the indegrees is equal to the sum of the outdegrees, and both are equal to the total number of edges.
    有向图：有向图中所有顶点的入度之和等于所有顶点的出度之和，两者都等于边的数量，公式为：
    $ {v V} ^-(v) = {v V} ^+(v) = |E| $

Summary (总结)

  • Simple Graphs do not contain loops or multiple edges between any two vertices.
    简单图：不包含环路或任意两顶点之间的多重边。

  • Undirected Graphs have edges that do not have direction, while Directed Graphs have edges with direction.
    无向图：边没有方向，而有向图：边有方向。

  • Degree describes the number of edges connected to a vertex.
    度描述了与顶点连接的边的数量。

  • Special Graphs include complete graphs, bipartite graphs, complete bipartite graphs, and n-cubes.
    特殊图包括完全图、二分图、完全二分图和 n-立方体。

  • Subgraphs are formed by taking a subset of the vertices and edges from the original graph.
    子图是通过取原图的顶点和边的子集来形成的。

  • Adjacency refers to the relationship between two vertices that are connected by an edge.
    邻接是指通过边连接的两个顶点之间的关系。

  • Degree Sum Formulas give relationships between the number of vertices, edges, and degrees in a graph.
    度数和公式给出了图中顶点、边和度数之间的关系。

Euler and Hamilton Path (欧拉路径与哈密顿路径)

Definitions (定义)

  • Euler Path (欧拉路径): A path in a graph that visits every edge exactly once.
    欧拉路径：图中的一条路径，它恰好访问每一条边一次。

  • Euler Circuit (欧拉回路): An Euler path that starts and ends at the same vertex.
    欧拉回路：一条欧拉路径，它的起点和终点是同一个顶点。

  • Hamiltonian Path (哈密顿路径): A path in a graph that visits every vertex exactly once.
    哈密顿路径：图中的一条路径，它恰好访问每个顶点一次。

  • Hamiltonian Circuit (哈密顿回路): A Hamiltonian path that starts and ends at the same vertex.
    哈密顿回路：一条哈密顿路径，它的起点和终点是同一个顶点。

Necessary and Sufficient Conditions for Euler Circuits and Paths (欧拉回路与路径的必要与充分条件)

  • Euler Path (欧拉路径) Conditions:
    • Necessary condition: The graph must be connected, except possibly for isolated vertices.
    • Sufficient condition: A graph has an Euler path if it has exactly two vertices with odd degrees (or zero odd degree vertices for an Euler circuit).
      欧拉路径条件：
    • 必要条件：图必须是连通的，可能有孤立的顶点。
    • 充分条件：图有欧拉路径当且仅当它恰好有两个顶点的度数是奇数（或者对于欧拉回路，所有顶点的度数都是偶数）。
  • Euler Circuit (欧拉回路) Conditions:
    • Necessary and sufficient condition: A connected graph has an Euler circuit if and only if every vertex has an even degree.
      欧拉回路条件：
    • 必要且充分条件：一个连通图当且仅当它的每个顶点的度数都是偶数时，才有欧拉回路。

Sufficient Conditions for Hamilton Circuits (哈密顿回路的充分条件)

  • Sufficient Condition: A graph will have a Hamiltonian circuit if it is complete (i.e., there is an edge between every pair of vertices).
    哈密顿回路的充分条件：如果一个图是完全图（即每对顶点之间都有边），则它必定有哈密顿回路。

  • Dirac’s Theorem: A graph with $ n $ vertices will have a Hamiltonian circuit if every vertex has a degree of at least $ $.
    Dirac 定理：对于一个有 $ n $ 个顶点的图，如果每个顶点的度数至少为 $ $，则它必定有哈密顿回路。

Shortest Path Problems (最短路径问题)

  • Weighted Graph (加权图): A graph in which each edge has a weight or cost associated with it, typically representing distance, time, or some other metric.
    加权图：图中每条边都与一个权重或成本相关，通常代表距离、时间或其他度量。

  • Shortest Path Problem (最短路径问题): The problem of finding the path between two vertices that minimizes the total edge weight.
    最短路径问题：寻找两顶点之间的路径，使得路径上所有边的权重和最小。

Dijkstra’s Algorithm (Dijkstra 算法)

  • Dijkstra's Algorithm: An algorithm for finding the shortest paths from a source vertex to all other vertices in a graph with non-negative edge weights.
    Dijkstra 算法：一种用于在带有非负边权的图中找到从源顶点到所有其他顶点的最短路径的算法。

    Steps:

    1. Initialize distances: set the distance to the source vertex as 0 and to all other vertices as infinity.
    2. Select the vertex with the smallest tentative distance and update the distances to its adjacent vertices.
    3. Repeat until all vertices have been processed.
      步骤：
    4. 初始化距离：将源顶点的距离设置为 0，所有其他顶点的距离设置为无穷大。
    5. 选择具有最小临时距离的顶点，并更新其邻接顶点的距离。
    6. 重复直到所有顶点都被处理。

The Traveling Salesman Problem (旅行商问题)

  • Traveling Salesman Problem (TSP): The problem of finding the shortest possible route that visits each city exactly once and returns to the origin city.
    旅行商问题：寻找一条最短的路线，要求每个城市恰好访问一次，并返回到起点城市。

  • Approximation Algorithm (近似算法): Due to the NP-hard nature of the TSP, finding an exact solution is computationally expensive, so approximation algorithms (such as the greedy algorithm) are used to find a near-optimal solution.
    近似算法：由于 TSP 是 NP 难题，精确解法计算量很大，因此使用近似算法（如贪心算法）来寻找近似最优解。

  • Euler Paths and Circuits (欧拉路径与回路):

    • Euler path: Visits every edge exactly once.
    • Euler circuit: A Euler path that starts and ends at the same vertex.
    • Necessary and sufficient conditions for Euler paths and circuits are based on vertex degree.

  • Hamiltonian Paths and Circuits (哈密顿路径与回路):

    • Hamiltonian path: Visits every vertex exactly once.
    • Hamiltonian circuit: A Hamiltonian path that starts and ends at the same vertex.
    • Sufficient conditions for Hamiltonian circuits include complete graphs and Dirac's theorem.

  • Shortest Path Problem (最短路径问题):

    • Involves finding the minimum weight path between vertices in a weighted graph.
    • Dijkstra’s algorithm is a well-known method for solving this problem in graphs with non-negative weights.

  • Traveling Salesman Problem (旅行商问题):

    • A classic optimization problem to find the shortest route that visits all cities exactly once and returns to the origin.
    • Approximation algorithms are often used due to the NP-hard nature of the problem.

Planar Graphs (平面图)

Definitions (定义)

  • Planar Graph (平面图): A graph that can be embedded in the plane, meaning it can be drawn on a plane without any edges crossing.
    平面图：可以嵌入平面中的图，意味着它可以在平面上绘制而不产生任何边交叉。

  • Planar Representation of a Graph (图的平面表示): A drawing of a planar graph in the plane such that no edges cross each other.
    图的平面表示：平面图的绘制方式，使得图中的边不交叉。

Euler’s Formula (欧拉公式)

  • Euler’s Formula for Planar Graphs: For a connected planar graph with \(v\) vertices, \(e\) edges, and \(r\) regions (including the outer region), the formula is:
    欧拉公式：对于一个连通平面图，它有 \(v\) 个顶点，\(e\) 条边，和 \(r\) 个区域（包括外部区域），公式为：

    $ r = e - v + 2 $

    • \(v\): Number of vertices.
    • \(e\): Number of edges.
    • \(r\): Number of regions (including the outer region).

Corollaries (推论)

  1. Corollary 1 (推论 1): For any connected planar graph, the following inequality holds:

    $ e 3v - 6 $

    This is a consequence of Euler’s formula for planar graphs with \(v \geq 3\) vertices.
    推论 1：对于任何连通的平面图，以下不等式成立：

    $ e 3v - 6 $

    这是欧拉公式的一个推论，适用于顶点数 \(v \geq 3\) 的平面图。

  2. Corollary 2 (推论 2): In a planar graph, each region is bounded by at least 3 edges (i.e., no region can be bounded by fewer than 3 edges).
    推论 2：在平面图中，每个区域至少由三条边界定（即，任何区域的边数不能少于三条）。

Kuratowski’s Theorem (Kuratowski 定理)

  • Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of either \(K_5\) (the complete graph on 5 vertices) or \(K_{3,3}\) (the complete bipartite graph on two sets of 3 vertices).
    Kuratowski 定理：一个图是平面图当且仅当它不包含 \(K_5\)（5个顶点的完全图）或 \(K_{3,3}\)（两个3顶点集合的完全二分图）的子图。

Necessary and Sufficient Conditions for Planarity (平面图的必要与充分条件)

  • Necessary and Sufficient Conditions for Planarity: A graph is planar if and only if it does not contain a subgraph homeomorphic to \(K_5\) or \(K_{3,3}\), as per Kuratowski's theorem.
    平面图的必要与充分条件：一个图是平面图当且仅当它不包含同胚于 \(K_5\) 或 \(K_{3,3}\) 的子图，依据Kuratowski 定理。

Graph Coloring (图着色)

Chromatic Number (色数)

  • Chromatic Number (色数): The minimum number of colors required to color the vertices of a graph such that no two adjacent vertices share the same color.
    色数：将图的顶点着色所需的最小颜色数，使得任何两个相邻的顶点颜色不同。

  • Notation: The chromatic number of a graph \(G\) is denoted by \(\chi(G)\).
    记法：图 \(G\) 的色数记作 \(\chi(G)\)。

The Four Color Theorem (四色定理)

  • Four Color Theorem (四色定理): Any planar graph can be colored with no more than four colors, such that no two adjacent regions (or vertices) share the same color.
    四色定理：任何平面图都可以用至多四种颜色着色，使得没有两个相邻的区域（或顶点）颜色相同。

  • Implication: This theorem implies that it is possible to color any map using no more than four colors, ensuring that adjacent regions (countries or states, for example) are colored differently.
    含义：这个定理意味着，可以用最多四种颜色着色任何地图，确保相邻的区域（例如国家或州）颜色不同。

  • Planar Graph (平面图): A graph that can be drawn in the plane without edges crossing.

  • Euler’s Formula (欧拉公式): \(r = e - v + 2\), which relates vertices, edges, and regions in a planar graph.

  • Kuratowski’s Theorem (Kuratowski 定理): A graph is planar if and only if it does not contain a subgraph homeomorphic to \(K_5\) or \(K_{3,3}\).

  • Graph Coloring (图着色): The process of assigning colors to vertices or edges of a graph such that adjacent elements have different colors.

  • Chromatic Number (色数): The minimum number of colors needed for graph coloring.

  • Four Color Theorem (四色定理): States that any planar graph can be colored using no more than four colors.

Trees (树) - Sections 9.1 to 9.6

Definitions (定义)

  • Tree (树): A connected, acyclic graph, meaning there are no cycles and any two vertices are connected by exactly one path.
    树：一个连通的无环图，意味着没有环路，任何两个顶点之间有且只有一条路径。

  • Forest (森林): A collection of disjoint trees, or equivalently, a graph with no cycles.
    森林：多个不相交的树的集合，或者等价地，指的是没有环的图。

  • Subtree (子树): A tree formed by a node (vertex) and all its descendants.
    子树：由一个节点及其所有后代节点形成的树。

Rooted Tree (有根树)

  • Rooted Tree (有根树): A tree in which one vertex is designated as the root, and the rest of the tree is structured hierarchically in terms of parent-child relationships.
    有根树：一棵树，其中一个顶点被指定为根，其余的树是根据父子关系按层级结构排列的。

  • Parent (父节点): A node that has one or more child nodes.
    父节点：一个节点有一个或多个子节点。

  • Child (子节点): A node that is a descendant of another node (its parent).
    子节点：一个节点是另一个节点（它的父节点）的后代。

  • Sibling (兄弟节点): Nodes that share the same parent.
    兄弟节点：共享相同父节点的节点。

  • Ancestor (祖先节点): A node that is on the path from a node to the root.
    祖先节点：在一个节点到根节点的路径上的节点。

  • Descendant (后代节点): A node that is on the path from the root to a given node.
    后代节点：在从根节点到给定节点的路径上的节点。

  • Internal Vertex (内部节点): A node that has at least one child.
    内部节点：有至少一个子节点的节点。

  • Leaf (叶子节点): A node that has no children.
    叶子节点：没有子节点的节点。

  • Level of a Vertex (节点的层次): The distance of a node from the root, measured in edges.
    节点的层次：一个节点到根节点的距离，用边的数量来度量。

  • Height of a Tree (树的高度): The maximum level of any vertex in the tree.
    树的高度：树中任何节点的最大层次。

m-ary Tree (m叉树)

  • m-ary Tree (m叉树): A tree where each internal vertex has at most \(m\) children.
    m叉树：每个内部节点最多有\(m\)个子节点的树。

  • Full m-ary Tree (完全 m叉树): A tree in which every internal vertex has exactly \(m\) children.
    完全 m叉树：每个内部节点恰好有\(m\)个子节点的树。

  • Binary Tree (二叉树): A special case of an m-ary tree where each node has at most two children (left and right).
    二叉树：一种特殊的m叉树，其中每个节点最多有两个子节点（左子节点和右子节点）。

Special Types of Trees (特殊树)

  • Ordered Tree (有序树): A tree where the children of each node are ordered.
    有序树：每个节点的子节点有顺序的树。

  • Balanced Tree (平衡树): A tree in which the height of the left and right subtrees of every node differ by at most one.
    平衡树：每个节点的左右子树的高度差不超过1的树。

  • Binary Search Tree (二叉搜索树): A binary tree in which for each node, the left subtree contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value.
    二叉搜索树：一种二叉树，其中对于每个节点，左子树只包含小于该节点值的节点，右子树只包含大于该节点值的节点。

  • Decision Tree (决策树): A tree used for decision-making, where nodes represent decisions or tests, and branches represent the outcomes of those decisions.
    决策树：用于决策的树，其中节点表示决策或测试，分支表示这些决策的结果。

  • Prefix Code Tree (前缀编码树): A tree where the leaves represent the symbols in a prefix code, and the path to each leaf corresponds to the code for that symbol.
    前缀编码树：一种树，其中叶子节点表示前缀编码中的符号，通向每个叶子的路径对应于该符号的编码。

Tree Traversal (树的遍历)

  • Preorder Traversal (前序遍历): Visit the root first, then recursively visit the left subtree and right subtree.
    前序遍历：先访问根节点，再递归访问左子树和右子树。

  • Prefix (or Polish) Notation (前缀（波兰）表示法): A way of writing expressions where operators precede their operands.
    前缀（波兰）表示法：一种写表达式的方法，其中运算符在操作数之前。

  • Inorder Traversal (中序遍历): Recursively visit the left subtree, visit the root, and then recursively visit the right subtree.
    中序遍历：递归访问左子树，访问根节点，再递归访问右子树。

  • Infix Notation (中缀表示法): A way of writing expressions where operators are between their operands.
    中缀表示法：一种写表达式的方法，其中运算符位于操作数之间。

  • Postorder Traversal (后序遍历): Recursively visit the left subtree, then the right subtree, and finally visit the root.
    后序遍历：递归访问左子树，然后是右子树，最后访问根节点。

  • Postfix (or Reverse Polish) Notation (后缀（逆波兰）表示法): A way of writing expressions where operators follow their operands.
    后缀（逆波兰）表示法：一种写表达式的方法，其中运算符在操作数之后。

Spanning Tree (生成树)

  • Spanning Tree (生成树): A tree that contains all the vertices of the graph and is a subgraph of the original graph.
    生成树：包含图中所有顶点的树，是原图的一个子图。

  • Minimum Spanning Tree (最小生成树): A spanning tree of a graph such that the sum of the edge weights is minimized.
    最小生成树：一棵生成树，使得所有边的权重之和最小化。

  • Greedy Algorithm (贪心算法): An algorithmic approach that makes locally optimal choices at each step with the hope of finding the global optimum.
    贪心算法：一种算法方法，在每一步做出局部最优选择，希望能找到全局最优解。

Types of Questions (问题类型)

Conceptual Questions (概念性问题)

  • Definitions of terms (术语定义): These questions focus on understanding and recalling the definitions of key terms and concepts discussed in the lectures. 术语定义：这些问题侧重于理解和回忆讲座中讨论的关键术语和概念的定义。

True/False Questions (判断题)

  • True/False (判断正误): These questions ask whether a statement is true or false, often testing your understanding of specific properties, theorems, or facts.
    判断正误：这些问题要求判断一个陈述是对还是错，通常测试你对特定性质、定理或事实的理解。

Multiple Choice Questions (选择题)

  • Multiple Choice (多项选择): Questions with several possible answers, where you are required to select the most appropriate one. These questions test both your recall and application of knowledge.
    多项选择：有多个可能答案的问题，要求你选择最合适的答案。这些问题测试你的知识回忆和应用能力。

Simple Questions (简单问题)

  • Simple Questions (简单问题): These questions involve basic understanding and recall of fundamental concepts or facts, usually requiring a straightforward answer.
    简单问题：这些问题涉及对基本概念或事实的基础理解和回忆，通常需要一个直接的答案。

Problem Solving (解题)

  • Work with Small Concrete Example Problems (通过具体例子解题): These questions ask you to solve problems using small, specific examples to demonstrate your problem-solving skills.
    通过具体例子解题：这些问题要求你使用具体的小例子来解决问题，展示你的解题能力。

  • Use Your Knowledge in a Comprehensive Way for Problem-Solving (综合运用知识解题): These questions involve applying a broad range of knowledge to tackle more complex problems or situations.
    综合运用知识解题：这些问题要求你综合运用广泛的知识来解决更复杂的问题或情境。

Proofs (证明)

  • Simple Theorems or Propositions (简单定理或命题): Questions that require proving basic mathematical theorems or propositions, often using direct reasoning or other methods.
    简单定理或命题：需要证明基本数学定理或命题的问题，通常使用直接推理或其他方法。

  • Possible Proof Methods (可能的证明方法): Different methods of proving statements, including:

    • Induction (数学归纳法): A method used to prove statements about natural numbers by proving a base case and then showing that if the statement holds for one case, it holds for the next. 数学归纳法：通过证明基本情况，并展示如果命题对于某一情况成立，则对下一情况也成立，来证明关于自然数的命题。
    • Direct Proof (直接证明): A straightforward approach where the truth of a statement is established by logical deduction from known facts. 直接证明：一种通过已知事实的逻辑推理来建立命题真理的直接方法。
    • Proof by Contradiction (反证法): A method where you assume the opposite of the statement and show that this leads to a contradiction, thereby proving the original statement. 反证法：假设命题的反面并证明这一假设导致矛盾，从而证明原命题的方法。

General Exam Guidelines (考试指南)

  • No questions will be outside of lecture notes (所有问题都在讲座笔记范围内): All questions on the exam will be based on the material covered in class and found in your lecture notes. It is important to focus your studies on these materials.
    所有问题都在讲座笔记范围内：考试中的所有问题都基于课堂上讲授的内容，并出现在讲座笔记中。因此，集中学习这些材料非常重要。

中英对照

connective 连接词

contrapositive 倒置蕴含

biconditional双条件

bitwise operations按位运算

universe of discourse论域

formula公式

normal form范式

literal文字

range值域

axiom公理

fallacy谬误

conjecture猜想

modus ponens假言推理

law of detachment分离规则

modus tollens拒取式

hypothetical syllogism假言三段论

disjunctive syllogism析取三段论

universal instantiation全称量词例示

​ generalization生成

proof by contradiction归谬证明

counterexample反例

cardinality基数

intersection交集

difference差集

symmetric difference对称差

range值域

recursion递归

diagonal realtion对角线关系

transpose转置矩阵

primary key主键

composite key复合键

projection投影

congruence同余

modulo模

partition划分

quotient set商集

lexicographic order字典序

lattice格

compatible相容的

topological拓扑排序

pseudograph伪图

adjacent相邻

incident关联

pendant悬挂点

regular graph正则图

matrix矩阵

entry项

isomorphic同构

homeomorphic同胚的

sibling兄弟

descendant后代

stack栈