离散数学期末复习

• 考试结构

  10道选择题(含多选,但答案不超过两个)20分
  3道证明题来自于集合论和代数结构（重难点)

数理逻辑 # 命题逻辑的基本概念

命题与联结词

命题(Proposition)

• 概念：具有唯一真值的陈述句
• 唯一性：或真或假但不能两者都是的
• 命题所用符号：常用小写２６个英文字母
• 经典例子
  • $x=3$ ×
  • 我现在说假话 × （悖论)
  • 请不要吸烟! ×(祈使句)
  • 这朵花真美丽啊！ （感叹句)
• 悖论:既不能为真，也不能为假的陈述句称作 __悖论__。
• 注

  命题是陈述句，陈述句不一定是命题
  命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定

命题分类

• 简单命题：不能被分解成更简单的命题
• 复合命题：简单命题+联结词(Connective)

联结词(Connective)

• 否定联结词(Negation Connective)

  • 符号¬,读作“非”，“否定”
  • 定义：命题 p
    • p的否定式：复合命题“p的否定”（“非p”）
    • 符号：$\neg$ p (符号$\neg$称作否定联结词)
    • $\neg$ p为真当且仅当p为假
  • 例子
    • 今天没有天晴 $\neg$p：今天天晴

• 合取联结词(Conjunctive Connective)

  • 符号$\wedge$,读作“合取”
  • 定义：命题 p，q
    • p与q的合取式：复合命题“p并且q”
    • 符号： $p \wedge q$ (符号$\wedge$称作合取联结词)
    • p$\wedge$q为真当且仅当p和q同时为真
  • 例子
    • 王华的成绩很好并且品德很好 $p \wedge q$
      p：王华的成绩很好
      q：王华的品德很好

• 析取联结词(Disjunctive Connective)

  • 符号$\lor$,读作“析取”
  • 定义：命题 p，q
    • p与q的析取式：复合命题“p或q”
    • 符号：$p \lor q$(符号$\lor$称作析取联结词)
    • p$\lor$q为假当且仅当p和q同时为假
  • 例子
    • 小李是学数学或者计算机科学p$\lor$q
      p：小李是学数学
      q：小李是学计算机科学

• 析取联结词 排斥或

  • 符号 $\oplus$
  • 定义：命题 p，q
    符号：p$\oplus$q
    等价于(p$\wedge\neg$q)$\lor$($\neg p\wedge q$)
    p$\oplus$q为假当且仅当p和q同时为假或同时为真
  • 例子：
    小李在教室看书或在图书馆上网
    小李在看书或者听音乐

• 蕴涵联结词(Implication Connective)

  • 符号$\to$,读作“如果…则…”、“蕴涵”
  • 定义：命题 p，q
    p与q的蕴涵式：复合命题“如果p，则q”
    符号：$p \to q$(符号$\to$称作蕴涵联结词)
    $p \to q$为假当且仅当p为真，q为假
  • 例子
    如果天下雨，那么地下湿 $p \to q$
    p：天下雨 , q：地下湿
  • 注
    • q是p的必要条件
    • p为假，$p \to q$永远为真
    • 给定命题$p \to q$
      • 它的逆命题$q \to p$
      • 它的反命题$\neg p\to\neg q$
      • 它的逆反命题 $\neg q \to\neg p$
    • 各种命题关系
      • $ p \to q \Leftrightarrow \neg q\to \neg p$
      • $ q \to p \Leftrightarrow \neg p\to \neg q$

• 等价联结词(Equivalence Connective)

  • 符号$\leftrightarrow$,读作“当且仅当”
  • 定义：命题 p，q
    p与q的等价式：复合命题“p当且仅当q”
    符号：$p \leftrightarrow q$(符号称作等价联结词)
    $p \leftrightarrow q$为真当且仅当p与q真值相同
  • 例子
    当且仅当2+3=5，才有2是素数 $p \leftrightarrow q$
    p： 2+3=5 , q： 2是素数

• 优先级

  • 联结词：$\neg \wedge \lor \to \leftrightarrow$
  • 同括号最优先
  • 同一优先级：从左到右
  • 例子：求于命题$\neg p\lor q\to r$含义相同的是$ ((\neg p)\lor q)\to q $

p	q	$p \wedge q$	$p \lor q$	$p \oplus q$	$p \to q$	$p \leftrightarrow q$
F	F	F	F	F	T	T
F	T	F	T	T	F	F
T	F	F	T	T	T	F
T	T	T	T	F	T	T

命题公式及其赋值

命题公式

• 命题常项(Propositional Constant)：简单命题
• 命题变项(Propositional Variable)：表示命题的变量
  • 真值可以变化的陈述句
  • 命题变项不是命题
  • 命题变项用确定命题代入才能确定真值
  • 命题所用符号：常用小写２６个英文字母
  • 命题变量不同于代数式的变量
    • 如：x+y>4的x，y不是命题变量
• 合式公式（命题公式）(Statement Formula)的递归定义：
  1. 单个命题常项或命题变项是合式公式（原子命题公式）
  2. A为合式公式，则$\neg A$是合式公式
  3. A , B为合式公式,则（$A \wedge B$），（ $A \lor B$），
     （$A \to B$）,（$A \leftrightarrow B$）为合式公式
  4. 有限次应用1-3形成的符号串为合式公式
  • 子公式B：给定合式公式A
    • B是A的一部分
    • B是合式公式
  • 符号说明
    • 大写字母A，B表示合式公式
    • 公式简写法则：
      • 公式最外层括号可以省略
        *（$\neg$ A）的括号可以省略
      • 根据运算符优先级省略括号
      • 省略括号不能影响公式解释
• 公式层次(Level)
  • 若公式A是单个的命题变元，则称A为0层合式
  • 称公式A是$n+1(n≥0)$层公式是指下面情况之一：
    • A＝ ¬B，B是n层公式
    • A＝$B \wedge C$，其中B，C分别为i层和j层公式，且n＝max(i,j)
    • A＝$B ∨ C$ ，其中B，C的层次及n同(b)
    • A＝$B \to C$ ，其中B，C的层次及n同(b)
    • A＝$B ↔ C$ ，其中B，C的层次及n同(b)
  • 若公式A的层次为k，则称A是k层公式
  • 注:层次≠联结词数

命题公式的赋值

• 设$p_1,p_2,\cdots,p_n$是出现在公式$A$中的全部命题变项，给$p_1,p_2,\cdots,p_n$各指定一个真值，称为对$A$的一个 赋值或 解释 。使$A$为1的一组值称为 成真赋值 , 使$A$为0的一组值称为 成假赋值 。

• 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。构造方式：

  • 找出A中命题变项：$p_1,p_2,\cdots,p_n$
  • 列出$2^n$个赋值（2进制加法形式）
  • 从低到高写成公式各个层次
  • 各个赋值：计算各层的真值

• 设A为任一命题公式

  • 重言式(永真式)(Tautology)：v(A)=T，对任意v
  • 矛盾式(永假式)(Contradiction) ：v(A)=F，对任意v
  • 可满足式(Satisfiable) ：v(A)=T，对某个v
  • 关系
    重言式是可满足式，反之不一定成立
  • 真值表判断
    • 重言式：真值表最后一列全为T
    • 矛盾式：真值表最后一列全为F
    • 可满足式：真值表最后一列至少一个T

考试要点

• 主要内容

  命题、真值、简单命题与复合命题、命题符号化
  联结词及复合命题符号化
  命题公式及层次
  公式的类型
  真值表及应用

• 基本要求

  深刻理解各联结词的逻辑关系, 熟练地将命题符号化
  会求复合命题的真值
  深刻理解合式公式及重言式、矛盾式、可满足式等
  熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型

命题逻辑等值演算

• 主要内容：
  • 等值式与基本的等值式
  • 等值演算与置换规则
  • 析取范式与合取范式，主析取范式与主合取范式
  • 联结词完备集(本次不作要求)
• 本章与其他各章的联系
  • 是第一章的抽象与延伸
  • 是后续各章的先行准备

等值式

• 定义:若等价式$A \leftrightarrow B$是重言式，则称A与B等值，记作$A \Leftrightarrow B$，并称$A \Leftrightarrow B$是等值式(Equivalent Expression)

  • 说明
    • 定义中，A, B, $\Leftrightarrow$均为元语言符号
    • A或B中可能有哑元出现.
      例如，在($p \to q$) $ \Leftrightarrow $ (($\neg p \lor q$)$ \lor $ ($\neg r\wedge r$))中，r为左边公式的哑元.
    • 哑元：设公式A，B共含有命题变项$p_1,p_2,\cdots,p_n$，而A或者B不全含这些命题变项，比如A中不含$p_i，p_{(i+1)}$等等，那么这些命题就是公式A的哑元。
    • 用真值表可验证两个公式是否等值

• 命题

  设A是一个命题公式，含有命题变项$p_1 , p_2 ,\cdots,p_n$，又设$A_1，A_2，…，A_n$是任意的命题公式. 对每个i（$i=1,2,\cdots,n$），把$p_i$在A中的所有出现都替换成$A_i$，所得到的新命题公式记作B. 那么，如果A是重言式，则B也是重言式.

• 等值式模式

  1. 双重否定律 $A \Leftrightarrow \neg\neg A$
  2. 幂等律 $A \Leftrightarrow A \lor A , A\Leftrightarrow A \wedge A $
  3. 交换律 $A \wedge B \Leftrightarrow B \wedge A , A \lor B \Leftrightarrow B \lor A$
  4. 结合律 $(A \lor B) \lor C\Leftrightarrow A \lor (B \lor C) (A \wedge B) \wedge C\Leftrightarrow A \wedge (B \wedge C)$
  5. 分配律 $ (A \lor B) \wedge C\Leftrightarrow (A \wedge C) \lor (B \wedge C)\qquad
     (A \wedge B) \lor C\Leftrightarrow (A \lor C) \wedge (B \lor C)$
  6. 德摩根律 $\neg(A \lor B) \Leftrightarrow \neg A\wedge\neg B , \neg(A \wedge B) \Leftrightarrow \neg A\lor\neg B$
  7. 吸收律 $A \lor (A \wedge B) \Leftrightarrow A , A \wedge (A \lor B) \Leftrightarrow A$
  8. 零律 $A \lor 1 \Leftrightarrow 1 , A \wedge 0 \Leftrightarrow 0$
  9. 同一律 $A \lor 0 \Leftrightarrow A , A \wedge 1 \Leftrightarrow A$
  10. 排中律 $A \lor\neg A \Leftrightarrow 1$
  11. 矛盾律 $A \wedge\neg A \Leftrightarrow 0$
  12. 蕴含等值式 $A \to B \Leftrightarrow \neg A \lor B$
  13. 等价等值式 $A \leftrightarrow B \Leftrightarrow (A \to B)\wedge(B \to A)$
  14. 假言易位 $A \to B \Leftrightarrow \neg B \to \neg A$
  15. 等价否定等值律 $A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$
  16. 归谬论 $(A \to B)\wedge(A \to \neg B)\Leftrightarrow\neg A$

• 等值演算(Equivalent Calculation)：由已知的等值式推演出另外一些等值式的过程

• 置换规则(Replacement Rule)：设φ(A)是含公式A的命题公式， φ(B)是用公式B置换了φ(A)中所有A后得到的命题公式，若$A \Leftrightarrow B$ ，则$φ(A) \Leftrightarrow φ(B)$

  • 说明：
    • 等值演算过程中遵循的重要规则
    • 一个命题公式A，经多次置换，所得到的新公式与原公式等价

析取范式与合取范式

• 析取式、合取式定义

  • 文字(literal): 命题变项及其否定
  • 简单析取式(Simple Disjunction):仅由有限个文字构成的析取式
  • 简单合取式(Simple Conjunction):仅由有限个文字构成的合取式

• 定理:

  1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式
  2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式

• 定义

  • 析取范式(Disjunctive Normal Form):由有限个简单合取式构成的析取式
  • 合取范式(Conjunctive Normal Form):由有限个简单析取式构成的合取式
  • 析取范式与合取范式统称为范式(Normal Form)

• 定理

  $A_i$ 简单合取式, $A_1 \lor \cdots \lor A_n \Leftrightarrow F$ 当且仅当 $A_i \Leftrightarrow F$，对任意$A_i$
  $A_i$ 简单析取式, $A_1 \wedge \cdots \wedge A_n \Leftrightarrow T$ 当且仅当 $A_i \Leftrightarrow T$，对任意$A_i$

• 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式

  • 方法：
    • 步骤一：消去“$\to$”、“$\leftrightarrow$”联结词
    • 步骤二：消去双重否定符，内移否定符（双重否定律、德摩根律）
    • 步骤三：使用分配律

  极小项 Miniterm (极大项 Maxterm):含有n个命题变项的简单合取式 (简单析取式)，并满足

• 每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次
• 第i个命题变项或它的否定式出现在从左算起的第i位上(若无角标，则按字典顺序排列)

  若有ｎ个命题变项，则有$2^n$个极小项（极大项）
  如果我们把不带否定符的命题变项取成1，带否定符的命题变项取成0，那么每一个极小项都对应一个二进制数，因而也对应一个十进制数
  极小项的编码:对应成真赋值,如 $p \wedge q \wedge r$对应$TTT , m_7$
  极大项的编码:对应成假赋值,如 $\neg p \lor \neg q \lor \neg r$对应$TTT , M_7$

定理:设$m_i$和$M_i$是命题变元$p_1 , p_2 ,\cdots,p_n$形成的极小项和极大项,则:

1. $m_i \wedge m_j \Leftrightarrow F (i \neq j)$(一个赋值不可能使两个均为真)
2. $M_i \lor M_j \Leftrightarrow T (i \neq j) $（一个赋值不可能使两个均为假）
3. $\neg m_i \Leftrightarrow M_i , \neg M_i \Leftrightarrow m_i$

• 主范式

  • 主析取范式 Principal Disjunctive Normal Form ：由n个命题变项构成的析取范式中所有的简单合取式都是极小项
  • 主合取范式 Principal Conjunctive Normal Form : 由n个命题变项构成的合取范式中所有的简单析取式都是极大项
  • 定理: 任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。

  • 一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。
  • 一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的
  • 任何一个命题公式都可求得它的主合取范式
  • 一个命题公式的主合取范式是唯一的
  • 在真值表中，令命题公式的真值为“F”的指派就对应其主合取范式的一个极大项
  • 重言式的主合取范式不含任何极大项，为1.
  • 矛盾式的主析取范式不含任何极小项, 为0.
• 主析（合）取范式的用途讨论：
  • 求公式的成真与成假赋值
  • 判断公式类型
  • 判断两个命题公式是否等值
  • 应用主析（合）取范式分析和解决实际问题

联结词的完备集

• “与非”联结词：
  • 符号 $ \uparrow $
  • ($p \uparrow q$)读作：“p与q的否定”
  • $p \uparrow q \Leftrightarrow \neg (p \wedge q)$
• “或非”联结词：
  • 符号：“↓”　
  • ($p \downarrow q$)读作：“p或q的否定”　
  • ($p \downarrow q) \Leftrightarrow \neg(p \lor q) $
• 真值函数F(Truth Function): {$0,1$}$^n \to${$0,1$}
• 联结词完备集S(Complete Set of Connectives):
  • S是一个联结词集合
  • 每一个真值函数都可以由仅含S中的联结词构成的公式表示

  • 定理: $S =\lbrace\neg,\wedge,\lor\rbrace$是联结词完备集
    推论: $S =\lbrace\wedge,\neg \rbrace$是联结词完备集
    $S = \lbrace\uparrow\rbrace , \lbrace\downarrow\rbrace$是联结词完备集。

考试要点

• 主要内容
  • 等值式与等值演算
  • 基本等值式（16组，24个公式）
  • 主析取范式与主合取范式
  • 联结词完备集
• 具体要求

  深刻理解等值式的概念
  牢记基本等值式的名称及它们的内容
  熟练地应用基本等值式及置换规则进行等值演算
  理解文字、简单析取式、简单合取式、析取范式、合取范式的概念
  深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系
  熟练掌握求主范式的方法（等值演算、真值表等）
  会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值
  会将公式等值地化成指定联结词完备集中的公式
  会用命题逻辑的概念及运算解决简单的应用问题

• 解决实际应用问题步骤
  1. 设简单命题并符号化
  2. 用复合命题描述各条件
  3. 写出由复合命题组成的合取式
  4. 将合取式化成主范式
  5. 求成真赋值, 并做出解释和结论

命题逻辑的推理理论

• 主要内容
  • 推理的形式结构
  • 自然推理系统P
• 本章与其他各章的联系
  • 本章是第五章的特殊情况和先行准备

推理的形式结构

• 推理 (Inference) —— 从前提出发推出结论的思维过程

• 证明 (Proof) —— 描述推理正确或错误的过程

• 推理的形式结构

  • 前提：$A_1,\cdots,A_k$
  • 结论：$B$
  • 推理的形式结构： $A_1\wedge\cdots\wedge A_k \to B$
  • 设$\Gamma = \lbrace A_1,\cdots,A_k\rbrace $, 则记前提$\Gamma$推出$B$的推理为$\Gamma\vdash B$为推理的形式结构。
  • 当推理正确，则记为$\Gamma\models B$

• 逻辑(语义)蕴涵(Logical Entailment)：给定$A_1,\cdots,A_k$和B

  • 对任意赋值v:
    • 如果$v(A_i)=T$,则$v(B)=T$
    • 或者存在$A_j$，使得$v(A_j)=F$
  • 称由前提$A_1,\cdots,A_k$ 推出结论B的推理是有效的
  • 符号：$\lbrace A_1,\cdots,A_k\rbrace$ $ \models B$
  • 注意: 推理正确不能保证结论一定正确
  • 定理 $\lbrace A_1,\cdots,A_k\rbrace$ $\models B$ 当且仅当 $A_1\wedge\cdots\wedge A_k \to B$ 为重言式
  • 蕴涵元符号: $\Rightarrow$
  • $A_1,\cdots,A_k \Rightarrow B$ 代表$\lbrace A_1,\cdots,A_k\rbrace$ $\models B$

• 推理定律

序号	公式	名称
1	$A\Rightarrow(A \lor B)$	附加律
2	$(A \wedge B) \Rightarrow A$	化简律
3	$(A \to B)\wedge A \Rightarrow B$	假言推理
4	$(A \to B)\wedge \neg B \Rightarrow \neg A$	拒取式
5	$(A \lor B)\wedge\neg B \Rightarrow A$	析取三段论
6	$(A \to B)\wedge(B \to C)\Rightarrow(A \to C)$	假言三段论
7	$(A \leftrightarrow B)\wedge(B \leftrightarrow C)\Rightarrow(A \leftrightarrow C)$	等价三段论
8.1	$(A \to B)\wedge(C \to D)\wedge(A \lor C)\Rightarrow(B \lor D)$	构造性二难
8.2	$(A \to B)\wedge(\neg A \to B) \Rightarrow B$	构造性二难（特殊）
9	$(A \to B)\wedge(C \to D)\wedge(\neg B \lor \neg D)\Rightarrow(\neg A \lor \neg C)$	破坏性二难

自然推理系统P

• 自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑推理规则推出结论的过程
• 一个形式系统 I (Formal System) 由下面四个部分组成：
  (1) 非空的字母表，记作 A(I).
  (2) A(I) 中符号构造的合式公式集，记作 E(I).
  (3) E(I) 中一些特殊的公式组成的公理集，记作 $A_X(I)$.
  (4) 推理规则集，记作 R(I).
  记$I=<A(I),E(I),A_X(I),R(I)>$, 其中$<A(I),E(I)>$是 I 的 形式语言系统, $<A_X(I),R(I)>$ 是 $I$ 的形式演算系统.
• 自然推理系统 P (Natural Deduction System)定义如下:
  • 字母表
    (1) 命题变项符号：$p, q, r, …, p_i, q_i, r_i,\cdots$
    (2) 联结词符号：$\neg,\wedge,\lor,\to,\leftrightarrow$
    (3) 括号与逗号：(, ), ，
  • 合式公式
  • 推理规则
    (1) 前提引入规则
    (2) 结论引入规则
    (3) 置换规则
    (4) 9条推理定律和结论引入可得（4）~（12）
• 构造证明方法
  • 附加前提证明法
    $(A_1,\cdots,A_k) \to (A \to B)$ 转化为 $A_1,A_2,\cdots,A_k,A\vdash B$
  • 归谬法
    $(A_1\wedge\cdots\wedge A_k) \to B$ 转化为 $(A_1\wedge\cdots\wedge A_k)\wedge\neg B$为矛盾式

考试要点

• 主要内容
  • 推理的形式结构
  • 判断推理是否正确的方法
    真值表法
    等值演算法
    主析取范式法
  • 推理定律
  • 自然推理系统P
  • 构造推理证明的方法
    直接证明法
    附加前提证明法
    归谬法(反证法)
• 基本要求
  • 理解并记住推理形式结构的两种形式：
    1. $A_1\wedge\cdots\wedge A_k \to B$
    2. 前提：$A_1,\cdots,A_k$
       结论：$B$
  • 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）
  • 牢记 P 系统中各条推理规则
  • 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法
  • 会解决实际中的简单推理问题

一阶逻辑基本概念

• 本章的主要内容
  一阶逻辑命题符号化
  一阶逻辑公式、解释及分类
• 本章与其他章的联系
  克服命题逻辑的局限性
  是第五章的先行准备

一阶逻辑命题符号化

• 命题逻辑的表示能力缺陷
  • 命题演算的基本单元为简单命题
  • 不能研究命题的结构、成分和内部逻辑的特征
  • 不能表达二个原子命题所具有的共同特征，无法处理一些简单又常见的推理
• 个体词（Individual Term）：研究对象中独立存在的具体或抽象的个体
  • 个体常项：具体或特定的个体词
    • 南京，东南大学，1，2
  • 个体变项：抽象或泛指的个体词
    • x,y,z
    • 取值范围称为个体域或论域
  • 空集不能作为论域
  • 全总个体域：宇宙间一切事物
• 谓词（Predicate）：刻画个体词性质及个体词之间的关系的词
  • 谓词常项：具体性质或关系的谓词
    • F(a,b)：小王和小李是同学
    • G(x)：x是有理数
  • 谓词变项：抽象或泛指的性质或关系的谓词
    • L(x,y)：x,y具有关系L
• n元谓词$P(x_1,…,x_n)$
  • $P(x_1,…,x_n)$: $D^n \to \lbrace F,T\rbrace$，D为个体域
  • 不带个体变项的谓词为0元谓词。当为谓词常项时， 0元谓词即命题
• 量词（Quantifier）：表示个体常项或变项之间数量关系的词
• 全称量词$\forall$（ Universal Quantifier ）： $\forall x$表示个体域里的所有个体x

  对应日常语言中的“一切的”、“所有的”等
  一元谓词F(x)个体域为D， $\forall xF(x)$真值
  $\forall xF(x)$为真：$F(a)$为真，对所有$a \in D$
  $\forall xF(x)$为假：$F(a)$为假，对某个$a \in D$
  $\forall x\forall yG(x,y)$：个体域里所有个体x,y有关系G
  $\forall x\forall yG(x,y)$为真：G(a,b)为真，对所有$a,b \in D$
  $\forall x\forall yG(x,y)$为假：G(a,b)为假，对某对$a,b \in D$

• 存在量词$\exists$（Existential Quantifier ）： $\exists x$表示个体域里有一个个体x

  对应日常语言中的“存在”、“有一个”等
  一元谓词F(x)个体域为D， $\exists xF(x)$真值
  $\exists xF(x)$为真：F(a)为真，存在某个$a \in D$
  $\exists xF(x)$为假：F(a)为假，对任意$a \in D$
  $\exists x\exists yG(x,y)$：个体域里存在个体x,y有关系G

• 全称量词与存在量词联合
  • $\forall x\exists yG(x,y)$：个体域里任意x,存在个体y, x, y有关系G
  • $\exists x\forall yG(x,y)$：个体域里存在x和所有个体y都有关系G
• $\forall xF(x), \exists xF(x), F(x)$的联系、区别
  • $F(x)$是不能确定真值的谓词
  • $\forall xF(x), \exists xF(x)$都是命题
  • x称为约束变元
• 谓词逻辑符号化几点说明
  • 不同的个体域，符号化形式可能不一样，命题真值也可能不同
  • 一般默认是全总个体域，即包含一切个体
  • 特性谓词：描述个体变元取值范围的谓词
    • 全称量化中，特性谓词常作为蕴涵式的前件
      $\forall x(M(x) \to F(x))$
    • 存在量化中，特性谓词常作为合取项之一
      $\exists x(M(x) \wedge F(x))$
  • 根据命题的实际意义选取全称量词或存在量词
  • 多个量词同时出现时，不能随意颠倒顺序

一阶逻辑公式及其解释

• 一阶谓词语言ℒ（ First-order Predicate Language）的字母表（ Alphabet）

  • 非逻辑符号
    • 个体常项符号
    • 函数符号
    • 谓词符号
  • 逻辑符号
    • 个体变项符号
    • 量词符号
    • 联结词符号
    • 括号与逗号

• 一阶谓词语言ℒ的项（Term）：

  • 个体常项符号和个体变项符号是项
  • 若$f(x_1,…,x_n)$是n元函数符号，$t_1,…,t_n$是n个项，则$f(t_1,…,t_n)$是项
  • 有限次使用以上两项生成的符号串才是项

• 一阶谓词语言ℒ的原子公式（Atomic Formula）：

  $F(x_1,…,x_n)$为n元谓词符号
  $t1,…,tn$为n个项
  $F(t_1,…,t_n)$为ℒ的原子公式

• 一阶谓词语言ℒ的合式公式(谓词公式)(Predicate Formula)：

  1. 原子公式是合式公式
  2. A为合式公式，则$\neg A$是合式公式
  3. A，B为合式公式,则$(A\wedge B), (A \lor B), (A \to B), (A \leftrightarrow B)$为合式公式
  4. 如A是合式公式，则$\forall xA, \exists xA$也是合式公式
  5. 只有有限次应用1-4构成的符号串才是合式公式

• 一张图解释
  $个体词\xrightarrow{ 函数 }项\xrightarrow{ 谓词 }原子公式\xrightarrow{ 联结词和量词 }合式公式$

• 辖域(Scope)：紧接在量词后面括号内的合式公式

• 自由变元与指导变元

  • 指导变元(Guide Variable)：出现在量词辖域内的变元x
  • 自由变元(Free Variable) ：非约束出现的变元

• 闭式(封闭公式)(Closed Formula)：不含自由出现的个体变项的公式

• 如何赋予合式公式含义？

  定义域
  函数变项需要指定具体函数
  谓词变项需要指定具体谓词

• 解释（Explanation）：非逻辑符号集L生成的一阶语言ℒ，ℒ的解释I由4部分组成

  • 非空个体域$D_I$
  • I将任意一个个体常项符号$a \in L$映射到$D_I$上的个体$a*$
  • I将任意一个n元函数$f \in L$映射到$D_I$上的n元函数$f*: (D_I)^n \to D_I$
  • I将任意一个n元谓词$F \in L$映射到$D_I$上的n元关系$R_F$

• $I$下的赋值$\sigma$: 对每一个个体变项符号$x$指定$D_I$中的一个值$\sigma(x)$
  设公式$A$, 规定：在解释$I$和赋值$\sigma$下

  • 取个体域$D_I$
  • 若$A$中含个体常项符号$a$就把它替换成$\overline a$
  • 若$A$中含函数符号$f$就把它替换成$\overline f$
  • 若$A$中含谓词符号$F$就把它替换成$\overline F$
  • 若$A$中含自由出现的个体变项符号$x$就将它替换成$\sigma(x)$
    这样得到的公式记为$A’$,称为$A$在$I$下的解释。

• 合式公式分类：公式A

  • 重言式(永真式)（Tautology）：A在任意的解释下为真
  • 矛盾式(永假式)（Contradiction）：A在任意的解释下为假
  • 可满足式（Satisfiable）： A在某个解释下为真

• 设$A_0$是含命题变项$p_1,p_2,\cdots,p_n$的命题公式，$A_1,A_2,\cdots,A_n$是n个谓词公式，用$A_i(1<=i<=n)$处处代替$A_0$中的$p_i$,所得公式$A$称为$A_0$的代换实例(Substitution Instance)

  • 如$F(x) \to G(x),\forall xF(x) \to \exists yG(y)$都是$p \to q$的代换实例。

• 重言式的代换实例都是永真式，矛盾式的代换实例都是永假式

考试要点

• 主要内容
  • 个体词、谓词、量词
  • 一阶逻辑命题符号化
  • 一阶语言L
    项、原子公式、合式公式
  • 公式的解释
    量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释
  • 公式的类型
    永真式(逻辑有效式)、矛盾式(永假式)、可满足式
• 基本要求
  • 准确地将给定命题符号化
  • 理解一阶语言的概念
  • 深刻理解一阶语言的解释
  • 熟练地给出公式的解释
  • 深刻理解永真式、矛盾式、可满足式的概念, 会判断简单公式的类型

等值演算与推理

• 本章的主要内容
  • 一阶逻辑等值式与基本的等值式
  • 置换规则、换名规则、代替规则
  • 前束范式
• 一阶逻辑推理理论
  • 本章与其他各章的关系
  • 本章的先行基础是前四章
  • 本章是集合论各章的先行基础

等值式与置换规则

• 等值式(Equivalence)：公式A,B的等价式$A \leftrightarrow B$为永真式，记作$A \Leftrightarrow B$. 称$A \Leftrightarrow B$是等值式。

• 第一类等值式：命题逻辑的重言式的代换实例(重言式的代换实例都是永真式)

• 第二类等值式：

  • 消去量词等值式
    设个体域为有限集$D=\lbrace a_1,a_2,\cdots,a_n \rbrace$,则有
    (1) $\forall xA(x)\Leftrightarrow A(a_1)\wedge A(a_2)\wedge\cdots\wedge A(a_n)$
    (2) $\exists xA(x)\Leftrightarrow A(a_1)\lor A(a_2)\lor\cdots\lor A(a_n)$
  • 量词否定等值式
    设公式$A(x)$含有自由出现的个体变项$x$,则
    (1) $\neg\forall xA(x)\Leftrightarrow\exists x\neg A(x)$
    (2) $\neg\exists xA(x)\Leftrightarrow\forall x\neg A(x)$
  • 量词辖域收缩与扩张等值式
    x在公式A(x)中自由出现，但不在B中自由出现
    $$
    \begin{split}
    \forall x(A(x) \lor B) &\Leftrightarrow \forall xA(x) \lor B
    \newline
    \forall x(A(x) \wedge B) &\Leftrightarrow \forall xA(x) \wedge B
    \newline
    \forall x(A(x) \to B) &\Leftrightarrow \exists xA(x) \to B
    \newline
    \forall x(B \to A(x)) &\Leftrightarrow B \to \forall xA(x)
    \newline
    \exists x(A(x) \lor B) &\Leftrightarrow \exists xA(x) \lor B
    \newline
    \exists x(A(x) \wedge B) &\Leftrightarrow \exists xA(x) \wedge B
    \newline
    \exists x(A(x) \to B) &\Leftrightarrow \forall xA(x) \to B
    \newline
    \exists x(B \to A(x)) &\Leftrightarrow B \to \exists xA(x)
    \end{split}
    $$
  • 量词分配等值式
    x在公式A(x)和B(x)中自由出现
    (1) $\forall x(A(x)\wedge B(x))\Leftrightarrow \forall xA(x) \wedge \forall xB(x)$
    (2) $\exists x(A(x)\lor B(x))\Leftrightarrow \exists xA(x) \lor \exists xB(x)$
    (3) $\exists x(A(x)\to B(x))\Leftrightarrow \forall xA(x) \to \exists xB(x)$
    注意:全称量词对析取无分配律，存在量词对合取无分配律
  • 即以下等值式不成立(x在公式A(x)和B(x)中自由出现)
    • $\forall x(A(x)\lor B(x))\Leftrightarrow \forall xA(x) \lor \forall xB(x)$
    • 提示：任意实数，或者是有理数或者是无理数，或者任意实数是有理数，或者任意实数是无理数
    • $\exists x(A(x)\wedge B(x))\Leftrightarrow \exists xA(x) \wedge \exists xB(x)$
    • 提示：存在实数，既是有理数又是无理数;存在实数是有理数，并且存在实数是无理数

• 规则

  • 置换规则
    • 设$\Phi(A)$是含公式$A$的公式, $\Phi(B)$是用公式$B$取代$\Phi(A)$中所有的A之后所得到的公式，那么，若$A \Leftrightarrow B$ 则 $\Phi(A) \Leftrightarrow \Phi(B)$
    • 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里$A,B$是一阶逻辑公式。
  • 换名规则
    • 设$\Phi(A)$为一公式, 将A中某量词辖域中的一个约束变项的所有出现及相应的指导变元全部改成该量词辖域中未曾出现过的某个个体变项符号，公式中其余部分不变，将所得公式记作$A’$,则$A’ \Leftrightarrow A$.

一阶前束范式

• 前束范式(Prenex Normal)：一阶逻辑公式满足
  • 量词都出现在公式最前面
  • 量词的辖域一直延伸到公式末
  • 形如$Q_1x_1Q_2x_2 \cdots Q_kx_k B$
  • Q为$\exists$或$\forall$，B不含量词
• 前束范式存在定理：一阶逻辑任何公式都存在等值的前束范式
  • 将公式中的联接词$\to、\leftrightarrow$换为$\wedge,\lor,\neg$
  • 利用量词否定等值式把深入到原子公式前
  • 利用换名规则或代替规则
  • 利用量词辖域的扩张收缩律把量词移到全式的最前面
  • 注意哪些既约束出现又自由出现的个体变项. 在求前束范式时，要通过换名消去既约束出现又自由出现的个体变项。

一阶逻辑的推理理论

• 推理定律
  除命题逻辑中的11个推理规则外，还有4个消去、引入量词规则:

  1. 全称量词消去规则(简记为$\forall -$)
     $\forall xA(x) \Rightarrow A(y)$

2. 全称量词引入规则(简记为$\forall +$)
   $A(y) \Rightarrow \forall xA(x)$
3. 存在量词消去规则(简记为$\exists -$)
   $(\exists xA(x))\wedge (A(y) \to B) \Rightarrow B$或$A(y)\to B \Rightarrow \exists xA(x)\to B$
4. 存在量词引入规则(简记为$\exists +$)
   $A(y) \Rightarrow \exists xA(x)$ 或 $B \to A(y) \Rightarrow B \to \exists xA(x)$

集合论 * 本部分的主要内容 + 集合代数----集合的概念和基本运算 + 关系----二元关系的表示、运算、性质、特殊的关系 + 函数----函数定义、性质、运算 + 集合的基数----集合的等势、集合的基数 * 本部分的基本要求 + 掌握集合及其相关的基本概念 + 熟练掌握集合以及关系、函数的基本运算 + 了解和使用基本的证明方法

集合代数

• 主要内容
  • 集合的基本概念—-属于、包含、幂集、空集、文氏图等
  • 集合的基本运算—-并、交、补、差等
  • 集合恒等式—-集合运算的算律、恒等式的证明方法
• 与后面各章的关系 : 是集合论后面各章的基础

集合的基本概念

• 集合是能作为整体论述的事物的集体，又称为类、族、搜集
• 组成集合的每个事物叫做这个集合的元素或成员。用符号$\in$表示某个元素属于某个集合，$\notin$表示不属于
• 任意元素，对于某一集合而言 ，或属于该集合，或者不属于，二者必居其一，不可兼得。这也符合命题演算中，命题要么是真，要么是假的二值逻辑
• 有限集合的元素的个数称为该集合的基数或势,记为$|A|$。
  • 外延公理：两个集合A和B相等，即A=B，当且仅当他们有相同的成员（也就是，A的每一元素是B的一个元素而B的每一个元素也是A的一个元素）。
  • 用逻辑符号表达是： $A=B \Leftrightarrow \forall x(x \in A \leftrightarrow x \in B)$
• 集合间的包含关系、相等、子集、真子集、空集
• 本章中讨论的集合和元素都是限于某一论述域的。我们记该论述域为$E$，又称为全集合。
• 含有n个元素的集合简称n元集，它的含有$m$个$(m≤n)$元素的子集称为它的m元子集。
• 幂集合
  • 定义：由集合$A$的所有子集（包括空集及A本身）所组成的集合叫做A的幂集。
  • 记以 $P(A)$,即 $P(A) ={B|B \subseteq A}$
  • 一个给定集合的幂集是唯一的
  • 设A为一个有限集，A的基数为$|A|$，则$P(A)$的基数$|P(A)|=2|A|$

集合的运算与集合恒等式

• 定义
  1. A和B的并记为$A∪B$ , 是集合 $A∪B={x|x∈A∨ x∈B}$
  2. A和B的交记为$A∩B$ , 是集合 $A∩B={x|x∈A∧x∈B}$
  3. A和B的差，或B关于A的 __相对补__，记为$A－B$,是集合 $A－B ={x|x∈A∧x \notin B}$
  4. 设A，B是两集合，集合$(A-B)∪(B-A)$称为集合A，B的 __对称差__，记作$A \bigoplus B$。即$A \bigoplus B={x \bigoplus (x \bigoplus A∧x \bigoplus B)∨(x \bigoplus B∧x \bigoplus A)}$
     $A \bigoplus B =(A∪B)-(A∩B)$
  5. 设E是论述域而A是E的子集。A的（绝对）补，记为～A，是集合$～A＝E－A＝{x|x∈E∧x \notin A}={x \notin A}$
  6. 设$A$为集合, $A$的元素的元素构成的集合称作$A$的 广义并,记作$\cup A$,符号化表示为$\cup A = \lbrace x|\exists z(z\in A \wedge x\in z)\rbrace$
  7. 设$A$为 非空集合(否则无意义), $A$的所有元素的公共元素构成的集合称作$A$的广义交,记作$\cap A$,符号化表示为$\cap A = \lbrace x|\forall z(z\in A \to x\in z)\rbrace$
• 称广义并、广义交、幂集、绝对补运算为一类运算，并、交、相对补、对称差运算为二类运算.
  • 一类运算优先于二类运算.
  • 一类运算之间由右向左顺序进行.
  • 二类运算之间由括号决定先后顺序.

有穷集的计数

• 文氏图(Venn Diagrams)：利用图来图解全集的各子集的关系的图，称为文氏图。
  （1）全集合E用一个大矩形表示
  （2）设A是E的一个子集，A用圆形表示
  （3）通常在图中画有阴影的区域表示新组成的集合
• 包含排斥定理(容斥原理):
  $|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|=|S|-\sum_{i=1}^{n}|A_i|+\cdots+{(-1)}^n|A_1 \cap A_2 \cap\cdots\cap A_n|$
• 欧拉函数(了解)
  欧拉函数$\phi$是数论中的一个重要函数，设$n \in N_+ ,\phi(n)$表示$\lbrace 0,1,\cdots,n-1\rbrace$中与$n$互素的数的个数.
  $\phi(n) =n\sum_{i=1}^{k}(1-\frac{1}{p_i})$

集合恒等式

名称	公式
幂等律	$A \cup A = A$
	$A \cap A = A$
结合律	$(A \cup B)\cup C = A \cup (B \cup C)$
	$(A \cap B)\cap C = A \cap (B \cap C)$
交换律	$A \cup B = B \cup A$
	$A \cap B = B \cap A$
分配律	$A \cup (B \cap C) = (A \cup B)\cap(A \cup C)$
	$A \cap (B \cup C) = (A \cap B)\cup(A \cap C)$
同一律	$A \cup \emptyset = A$
	$A \cap E = A$
零律	$A \cup E = E$
	$A \cap \emptyset = \emptyset$
排中律	$A \cup $~$A = E$
矛盾律	$A \cap $~$A = \emptyset$
吸收律	$A \cup(A \cap B) = A$
	$A \cap(A \cup B) = A$
德摩根律	$A-(B \cup C)=(A-B)\cap(A-C)$
	$A-(B \cap C)=(A-B)\cup(A-C)$
	$(B \cup C) = $ ~$B \cap $$C$
	$(B \cap C) = $ ~$B \cup $$C$
	~$\emptyset = E$
	~$E = \emptyset$
双重否定律	~~$A=A$

二元关系

• 主要内容
  • 有序对与笛卡儿积
  • 二元关系的定义与表示法
  • 关系的运算
  • 关系的性质
  • 关系的闭包
  • 等价关系与划分
  • 偏序关系
• 本章与后面各章的关系
  • 是函数的基础
  • 是图论的基础

有序对与笛卡儿积

• 有序对（序偶）：由两个元素$x,y$(允许x=y)按给定顺序排列组成的二元组合
  • 符号化：$<x,y>$
  • x为第一元素，y为第二元素
• 笛卡尔积A×B：集合A中元素为第一元素，集合B中元素为第二元素的有序对集$A×B={<x，y>|x \in A \wedge y \in B}$
  • 如A，B均是有限集，$|A|=m,|B|=n$,则必有$|A \times B|=mn$
• 笛卡儿积性质
  • 对于任意集合A，$A \times \emptyset = \emptyset，\emptyset \times A=\emptyset$
  • 一般不满足交换律，当$A\neq\emptyset \wedge B\neq\emptyset \wedge A \neq B时，A \times B \neq B \times A$
  • 一般不满足结合律，即当A，B，C均非空时，$(A \times B) \times C \neq A \times (B \times C)$
• 对任意三个集合A，B，C有
  （1）$A\times(B∪C)=(A \times B) ∪(A \times C)$
  （2）$A\times(B∩C)=(A \times B)∩(A \times C)$
  （3）$(B∪C)\times A=(B\times A) ∪(C \times A)$
  （4）$(B∩C)\times A=(B \times A)∩(C \times A)$
  （5）$A \subseteq C \wedge B \subseteq D \Leftrightarrow A×B \subseteq C×D$

二元关系

• 关系是指事物之间（个体之间）的相互联系
• 二元关系R：满足下列条件之一的集合
  • 集合非空，且它的元素都是有序对
  • 集合为空集
• $A,B$是集合，$A \times B$的子集叫做从A到B的一个二元关系
• 特殊的二元关系
  • 全域关系$E_A＝A \times A$
  • 恒等关系$I_A＝{<x，x>|x∈A}$
  • 空关系$\emptyset$
  • 小于等于关系 $L_A = \lbrace<x,y>|x,y \in A,x<=y$
  • 整除关系 $D_A = \lbrace<x,y>|x,y \in A,x|y$
  • 包含关系 $R_\subseteq=\lbrace<x,y>|x,y \in A,x \subseteq y$
• 给出一个关系的方法有3种：集合表达式、关系矩阵和关系图。
• 设$A=\lbrace x_1,x_2,\cdots,x_n \rbrace$, $R$是$A$上的关系，令
  $$
  r_{ij}=
  \begin{cases}
  1 & 若x_i R x_j \newline
  0 & 若x_i \not R x_j
  \end{cases}
  $$
• 关系图，直接由关系矩阵作图即可。

关系的运算

• 设R是二元关系
  • R中所有有序对的第一元素构成的集合称作$R$的$定义域$,记作$domR$,形式化表示为$domR=\lbrace x|\exists y (<x,y> \in R)\rbrace$
  • R中所有有序对的第二元素构成的集合称作$R$的$定义域$,记作$ranR$,形式化表示为$ranR=\lbrace y|\exists x (<x,y> \in R)\rbrace$
  • R的定义域和值域的并集称作R的域，记作$fldR$,形式化表示为$fldR=domR \cup ranR$
• 设R为二元关系，R的逆关系，简称为R的逆，记作$R^{-1}$,其中$R^{-1}=\lbrace<x,y>|<y,x> \in R\rbrace$
• 设$F,G$为二元关系，G对F的 __右复合__记作$F \circ G$,其中$F \circ G=\lbrace<x,y>|\exists t(<x,t> \in F\wedge<t,y>\in G$
• 设$R$为二元关系，A是集合,
  • R在A上的 限制 记作$R \upharpoonright A=\lbrace<x,y>|xRy \wedge x \in A\rbrace$
  • A在R下的 像 记作$R[A]$,其中$R[A]=ran(R \upharpoonright A)$
• 优先顺序：
  • 逆运算优先于其他运算
  • 关系运算优先于集合运算
  • 没有规定优先权的运算以括号决定运算顺序
• 设F是任意的关系，则
  • $(F^{-1})^{-1} = F$
  • $domF^{-1}=ranF,ranF^{-1}=domF$
• 设$F,G,H$是任意的关系，则
  • $(F \circ G) \circ H = F \circ (G \circ H)$
  • $(F \circ G)^{-1}=G^{-1} \circ F^{-1}$
• 设$R$为$A$上的关系,则$R \circ I_A = I_A \circ R = R$
  • $R \circ (S∪T)=R \circ S∪R \circ T$
  • $R \circ (S∩T) \subseteq R \circ S∩R \circ T$
  • $(S∪T) \circ X=S \circ X∪T \circ X$
  • $(S∩T) \circ X \subseteq S \circ X∩T \circ X$
• 设$R$为关系,$A,B$为集合，则
  • $R↾(A∪B) = R↾A∪R↾B$
  • $R[A∪B] = R[A]∪R[B]$
  • $R↾(A∩B) = R↾A∩R↾B$
  • $R[A∩B] \subseteq R[A]∩R[B]$
• 设$R$为$A$上的关系，n为自然数，则R的n次幂定义为
  • $R^0=\lbrace<x,x>|x \in A\rbrace=I_A$
  • $R^{n+1}=R^n \circ R$
  • 定理: 设R是集合A上的关系，$m,n∈N$
    • $R^m \circ R^n=R^{m+n}$
    • $(R^m)^n=R^{mn}$
    • 证明思路：使用归纳法并利用复合关系的结合律
  • 定理：设A为n元集，R是A上的关系，则存在自然数$s$和$t$，使得$R^s=R^t$

关系的性质

• 若$\forall x(x \in A \to <x,x> \in R)$，则称$R$在$A$上是 __自反__的。

• 若$\forall x(x \in A \to <x,x> \notin R)$,则称$R$在$A$上是 __反自反__的。

  • 关系矩阵的特点？
    自反关系的关系矩阵的对角元素均为1
    反自反关系的关系矩阵的对角元素均为0
  • 关系图的特点？
    自反关系的关系图中每个顶点都有环
    反自反关系的关系图中每个顶点都没有环
  • 定理：R是A上的关系，则：
    R是自反关系的充要条件是$I_A \subseteq R$
    R是反自反关系的充要条件是$R∩IA=Ф$

• 若$\forall x\forall y(x,y \in A \wedge <x,y> \in R \to <y,x> \to R$,则称$R$为$A$上 __对称__的关系。

  • 关系矩阵特点？
    对称关系的关系矩阵是对称矩阵
  • 关系图特点？
    如果两个顶点之间有边，一定是一对方向相反的边（无单边）
  • 定理： R在A上对称当且仅当$R=R^{-1}$

• 若$\forall x\forall y(x,y \in A \wedge <x,y> \in R \wedge <y,x> \in R \to x=y$,则称$R$为$A$上 __反对称__的关系。

  • 反对称关系矩阵和关系图特点？
    若$r_{ij}=1$，且$i≠j$， 则$r_{ji}=0$
  • 如果两个顶点之间有边，一定是一条有向边（无双向边）
  • 定理： R在A上反对称当且仅当$R∩R{-1} \subseteq IA$

• 设$R$为A上的关系，若$\forall x\forall y\forall z(x,y,z\in A \wedge <x,y>\in R\wedge <y,z> \in R \to <x,z> \in R$,则称$R$为$A$上 __传递__的关系。

  • 传递关系关系图特点？
    如果结点a能通过有向弧组成的有向路径通向结点x,则a必须有有向弧直接指向x,否则R就不是传递的
  • 定理：R在A上传递当且仅当$R \circ R \subseteq R$

关系的闭包

• 定义：R是非空集合A上的关系,若A上另外有一个关系R’满足如下三条：

  • $R’$是自反的(对称的，传递的）
  • $R \subseteq R’$
  • A上任何一个满足以上两条的关系$R”$，均有$R’ \subseteq R”$
    称关系R’为R的自反(对称,传递)闭包,记作$r(R) (s(R),t(R))$

  • R’是在R的基础上添加有序对
  • 添加元素的目的是使R’具有自反性(对称性,传递性)
  • 添加后使之具有自反性(对称性,传递性)的所有关系中R’是最小的一个

• 定理

  • $r(R)=R \cup R^0$
  • $s(R)=R \cup R^{-1}$
  • $t(R)=R \cup R^2 \cup \cdots$

• 给定关系$R，r(R)，s(R)，t(R)$的关系矩阵分别为$M , M_r , M_s , M_t$,那么：

  • $Mr=M+E$
  • $Ms=M+M$
  • $Mt=M+M2+M3+…$

• 关系图分别为$G，G_r，G_s，G_t$，那么：

  • 考察G的每个顶点，如果没有环就加上一个环，最终得到的是Gr
  • 考察G的每一条边，如果有一条从$x_i到x_j$的单向边，则在G中加一条$x_j到x_i$的反方向边，最终得到$G_s$
  • 考察G的每个顶点$xi$,找出从$x_i$出发的所有2步，3步，…，n步长的路径。设路径的终点为$x_{j1},x_{j2},…,x_{jk}$。如果没有从$x_i$到$x_{jl}$的边，就加上这条边，最终得到$G_t$

• 定理：设A是一集合，R是A上的二元关系，则有：

  • R是自反的当且仅当$r(R)＝R$
  • R是对称的当且仅当$s(R)＝R$
  • R是可传递的当且仅当$t(R)＝R$

• 定理：设A是集合，R1和R2是A上的二元关系，$R1 \subseteq R2$，则有：

  • $r(R1) \subseteq r(R2)$
  • $s(R1) \subseteq s(R2)$
  • $t(R1) \subseteq t(R2)$

• 定理：设X是一集合，R是X上的二元关系，则有：

  • 若R是自反的，则$s(R),t(R)$也自反
  • 若R是对称的，则$r(R),t(R)$也对称
  • 若R是可传递的，则$r(R)$也可传递

等价关系与划分

• 若非空集合A上的关系R, 满足自反、对称、可传递，则称R为A上的 __等价关系__。即若$<x,y> \in R$,称$x$等价于$y$,记作$x$~$y$.
• 设$R$为非空集合$A$上的等价关系，$\forall x \in A$,令$[x]_R = \lbrace y|y \in A \wedge xRy\rbrace$ ,称为x关于R的等价类,简称为x的等价类。简记为$[x]$或$\overline{x}$
  • 等价类$[x]_R$是一个集合，$[x]_R \subseteq A ([x]R$是A的子集)
  • $[x]_R$中的元素是在A中，所有与x具有等价关系R的元素所组成的集合
  • 在等价关系中的关系图中，一个最大连通子图中的点就是一个等价类
• 定理
  • 设A是一个集合，R是A上的等价关系，$xRy$当且仅当$[x]=[y]$
  • 设A是一个集合，R是A上的等价关系，对于所有$x,y∈A$，或者$[x]=[y]$，或者$[x]∩[y]=Ø$
  • 设R是集合A上的等价关系，则$A=∪{[x]|x \in A}$
• 设$R$为非空集合$A$上的等价关系,以$R$的所有等价类作为元素的集合称为$A$关于$R$的 __商集__，记作$A/R$，即：$A/R=\lbrace[x]_R|x \in A\rbrace$
• 设$A$为非空集合,若$A$的子集族$\pi(\pi\subseteq P(A)$,是A的子集构成的集合）满足下列条件:
  • $\emptyset\notin\pi$
  • $\forall x\forall y(x,y\in\pi\wedge x\neq y \to x\cap y = \emptyset$
  • $\cup\pi = A$
    则称$\pi$是$A$的一个 划分,称$\pi$中的元素为$A$的划分块。

等价关系与划分有一一对应关系
划分到等价关系转化：A是一非空集合，S是A的一个划分，下述关系必定是一个等价关系
$R={<x,y> | x, y\in A \wedge x,y在S的同一划分}$
等价关系到划分的转化：设A是非空集合，R是A上的等价关系。R的商集是A的划分

偏序关系

• 次序在现实生活中常见：
  小于，包含等
• 研究序理论的动机：
  • 研究一般次序关系
  • 推导出一般序关系的性质
  • 这些关系可以应用于所有特定的序关系
• 设$R$为非空集合A上的关系。如果$R$是自反、__ 反 对称__和传递的,则称R为A上的 __偏序关系__。记作$≼$，设$≼$ 为偏序关系,如果$<x,y>\in≼$,则记作$x≼y$，读作”x小于等于y”
• 设$≼$为非空集合$A$上的偏序关系，定义
  • $\forall x,y\in A,x<y\Leftrightarrow x≼y\wedge x\neq y$
  • $\forall x,y\in A,x与y可比\Leftrightarrow x≼y\lor y≼x$
• 设$R$为非空集合$A$上的偏序关系，如果$\forall x,y\in A,x,y$均可比，则称$R$为A上的全序关系（线序关系）
• 集合$A$和$A$上的偏序关系$≼$一起称作 __偏序集__，记作$<A,≼>$
• 设$<A,≼>$为偏序集，$\forall x,y\in A$,如果$x<y$且不存在$z\in A$使得$x<z<y$，则称$y$覆盖$x$.
• 哈斯图思路
  • 哈斯图思路：
  • 所有结点的自回路均省略
  • 省略所有弧上的箭头,适当排列A中元素的位置,如$a≼b$,则a画在b的下方
  • 如$a≼b,b≼c$,则必有$a≼c$, a到b有边, b到c有边,则a到c的无向弧省略
  • 条件2，3等于说如果b覆盖a,则画一条从a到b的弧线，否则不画
• 最小(大)元：设$<A, ≼>$是偏序集,集合$B \subseteq A$
  • 最大元$b∈B$：$\forall a∈B$,均有$a≼b$
  • 最小元$b∈B$：$\forall a∈B$,均有$b≼a$
  • 如果A的子集B存在最大(小)元素,则最大(小)元素是唯一的
  • 最大(小)元可能不存在
• 极大(小)元：设$<A, ≼>$是偏序集,$B \subseteq A$
  • 极大元$b∈B$：$\forall a∈B,如b≼a,则a＝b$
  • 不存在$a∈B$，$b≺a$
  • 极小元$b∈B$：$\forall a∈B,如a≼b,则a＝b$
  • 不存在$a∈B$，$a≺b$
  • 说明
    • 极大元未必是最大元
    • 极大元未必是唯一的
    • 如果B是有限集,则B必存在极大元
    • 最大元就是极大元
• 上(下)界：设$<A, ≼>$是偏序集, $B \subseteq A, a∈A$
  • B的上界a：对每个$b∈B,有b≼a$
  • B的下界a：对每个$b∈B,有a≼b$
  • 上下界不一定唯一
• 上(下)确界：设$<A, ≼>$是偏序集, $B \subseteq A$
  • 最小上界：$C=\lbrace b|b为B的上界\rbrace$的最小元
  • 最大下界：$D=\lbrace b|b为B的下界\rbrace$的最大元
  • 说明
    • B的最小元一定是B的下界，同时也是B的最大下界；B的最大元一定是B的上界，同时也是B的最小上界
    • 最小上界或最大下界可能不存在
    • 若存在最小上界或最大下界，是唯一的
• 拓扑排序：给定一个非空有限的偏序集合$<A,≼’>$，构造出一个全序集合$<A, ≼>$ ，使得每当$a≼’b$有$a≼b$，方法如下：
  • 选取A的极小元a，使a是<A, ≼>列表表示中的第一个元素
  • 对子集$A-{a}$重复这一过程，每次一个新的极小元素被找到，它在$<A,≼>$的列表表示中成为下一个元素
  • 重复这一过程，直到A的元素被抽完

考试要点

• 有序对：
  由两个元素x，y按给定顺序排列组成的二元组合
• 笛卡儿积：
  集合A中元素为第一元素，集合B中元素为第二元素的有序对集
• 二元关系R：
  满足下列条件之一的集合：
  集合非空，且它的元素都是有序对
  集合为空集
• 从A到B的关系：
  A，B是集合，A×B的任何子集所定义的二元关系
• A上的关系：
  A=B
  空关系，全域关系，恒等关系，包含关系
• 关系的表示法：
  集合表达式、关系矩阵、关系图
• 关系的八种运算
• 关系运算的五种性质
• 关系的三种闭包
• A上的等价关系
• 商集
• 等价类
• 划分
• A上的偏序关系和偏序集
  基本要求

  熟练掌握关系的三种表示法
  能够判定关系的性质，以及等价关系、偏序关系
  掌握含有关系运算的集合等式
  掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念
  计算$A \times B, dom R, ranR, fldR, R^{-1}, R \circ S , R^n , r(R), s(R), t(R)$
  求等价类和商集A/R
  给定A的划分$\pi$，求出$\pi$所对应的等价关系
  求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界
  掌握基本的证明方法
  证明涉及关系运算的集合等式
  证明关系的性质、证明关系是等价关系或偏序关系

函数

函数的定义与性质

• $B^A$求法 $B^A=\lbrace f|f:A\to B\rbrace$
  • $A=\lbrace 1, 2, 3\rbrace, B=\lbrace a,b \rbrace$，求$B^A$(PPT_Chapter 8 Page8)
• 函数的像、完全原像概念（课本P146）
• 单满双射概念(课本P147) -> 判断函数类型
  • 例8.4 (1)(2)(5)
  • 例8.5 (1)(2)(6)(7)
  • 构造双射函数 例8.6 (1)
• 常用函数(课本P150)
  • 常函数
  • 恒等函数
  • 单调函数
  • 特征函数(PPT_Chapter 8 Page18)
  • 自然映射(PPT_Chapter 8 Page20)

函数的复合与反函数

• 会求函数的复合函数$F \circ G$(PPT_Chapter 8 Page25)
• 复合函数的单满双射性质（课本P153）
• 逆函数（反函数）必须是双射函数

双射函数与集合的基数

• 等势(存在从A到B的双射函数)
  • 会判断两个集合是否等势（课本P156-159）、
  • 具有自反、对称、传递性。
• 康托定理：(1) $N\not\approx R$ (2) 对任意集合A都有$A\not\approx P(A)$
• 优势（存在A到B的单势函数，则称B优势于A,记作$A≼·B$）、真优势
  • 性质：自反性、传递性
  • $A≼·B \wedge B≼·A \to A\approx B$
• 自然数集合(课本P162)
  • 空集和后继$n^+$定义而来
  • 三歧性
  • 有穷集当且仅当它与某个自然数集等势，否则称为无穷集。
• 基数
  • 对于有穷集合A，称与A等势的那个唯一自然数为A的基数,记作$cardA$或(|A|)
    • 即$card A = n \Leftrightarrow n$
    • 基数即为集合中不同元素的个数
  • 自然数集合$N$的基数记作$ℵ_0$(阿列夫零)
  • 实数集$R$的基数记作$ℵ$（阿列夫)
  • 会求集合基数（课本P163)
• 可数集($cardA≤ℵ_0$)
  • 如$\lbrace a,b,c,\rbrace , N , Z , Q$
  • 不可数集如$R , (0,1) $

代数结构 # 代数系统 ## 二元运算及其性质 * 二元运算 - 封闭与不封闭 - 存在性与唯一性 * 一元运算 - 在R上求平方根（不满足唯一性和存在性) * __交换律、结合律__ * __幂等律__ - $forall x \in S , x \circ x = x$ - $x$称为幂等元 * __分配律与吸收律__(课本P180) * (左、右)单位元（也称为幺元） * (左、右)零元（PPT_Chapter 9 Page20) * (左、右)逆元(逆元存在性是对集合中的元素而言的) - 证明定理设Z是集合, \*是Z上的二元运算,并且是可结合的，运算\*的幺元是1。若$x∈Z$有左逆元和右逆元,则它的左逆元等于右逆元,且逆元是唯一的。(PPT_Chapter 9 Page24) - 综合练习题(PPT_Chapter 9 Page50、52) * __消去律__(课本P183)

代数系统

• 代数系统组成（非空集合、运算、特异元素（代数常数））
• 同类型代数系统:具有相同个数的运算、代数常数，且对应运算的元数相同
• 运算封闭(PPT_Chapter 9 Page37)
• 子代数系统
  • 会判断子代数系统 如：$<N,->$不是$<Z,->$的子代数系统
  • 平凡子代数（最大、最小子代数）
  • 真子代数
• 积代数、因子代数
  • 积代数的运算性质与因子代数相同
  • $e_1,e_2$是子代数的代数常数,则$<e_1,e_2>$是积代数的代数常数
  • 如果$x,y$是子代数的可逆元素,则$<x,y>$是积代数的可逆元素,逆元是$<x^{-1},y^{-1}>$
  • 积代数保留了因子代数的分配律和吸收律，但不保留消去律。（课本P188）

代数系统的同态与同构

• 同态(映射)概念(课本P189)
  • 单同态、满同态、双同态（同构)
  • 自同态
  • 零同态
• 说明：判别或证明同态映射的方法
  (1) 先判断（或证明）f 是$G_1$到$G_2$的映射$f:G_1 \to G_2$. 如果已知$f:G_1 \to G_2$，则这步判断可以省去.
  (2) $\forall x, y\in G1$, 验证 $f(x \times y) = f(x) \times f(y)$
  (3) 判断同态性质只需判断函数的单射、满射、双射性即可.

群与环

群的定义及性质

• 群分类
  • 半群：代数系统上成立结合律。
  • 幺半群（独异点）: 有幺元的半群
  • 群（幺半群且每个元素均有逆元)
  • Klein四元群
  • 会验证群类型(定义验证，注意运算封闭性)
• 概念
  • 有限群、无限群
  • 群的阶
  • 平凡群
  • 交换群(阿贝尔群)
  • 群中元素的幂(PPT_Chapter 10 Page12)
  • 群中元素的阶（也叫周期）,记作$|a|=k$(k为使$a^k=e$成立的最小正整数)
• 幂运算性质
• 证明消去律和定理10.3、例10.7(课本P197-198)

子群

• 子群就是群的子代数
  • 真子群
  • 子群说明：<H,*>是子群, 则
    • H对于运算*是封闭的
    • G的幺元e在H内
    • H的每个元素的逆元仍在H内(对逆运算封闭)。至于运算的结合律,由于在G中成立,对于H必然成立
    • 如H构成子群,必然是非空的,至少有幺元e
  • 证明和使用子群判定定理(课本P199)
  • 会求由$a$的幂次生成的子群,记作$<a>=\lbrace a^k|k\in Z\rbrace$
  • 中心（群中所有可交换元素构成的集合）
• 子群格
  • 会画哈斯图

证明方法

• 证明群中元素相等的基本方法就是用结合律、消去律、单位元及逆元的惟一性、群的幂运算规则等对等式进行变形和化简.
• 证明子集相等的基本方法就是证明两个子集相互包含
• 证明与元素的阶相关的命题，如证明阶相等，阶整除等. 证明两个元素的阶r 和 s 相等或证明某个元素的阶等于r，基本方法是证明相互整除.在证明中可以使用结合律、消去律、幂运算规则以及关于元素的阶的性质. 特别地，可能用到a为1阶或2阶元的充分必要条件是$a^{-1} = a$

格与布尔代数

格的定义与性质

• 格：偏序集中任意元素均有最小上界和最大下界
  • $x\lor y$表示最小上界
  • $x\wedge y$表示最大下界
  • 幂集格
• 对偶命题
• 格的运算$\lor \wedge$满足交换、幂等、结合、吸收律($a\lor(a\wedge b)=a, a\wedge(a\lor b)=a$)
  • 注意这里的$\lor \wedge$是最小上界和最大下界
• 格的代数系统定义
  • 证明定理11.2(课本P225)
  • 对应定理(PPT_Chapter 11 Page15)
• 子格

分配格、有补格与布尔代数

• 分配格
  • 会判断分配格
    • $L$是分配格当且仅当$L$中不含与钻石格、五角格同构的子格.
    • 小于5元的格都是分配格
    • 任何一条链都是分配格
• 有补格
  • 全上界、全下界、有界格
  • 补元(PPT_Chapter 11 Page28)
  • 有界分配格补元若存在则唯一。
  • 有界格中所有元素补元均存在则称为 有补格
• 布尔代数（布尔格)
  • 
  • 也叫有补分配格，记作$<B,\wedge,\lor,’,0,1>$其中$’$为求补运算
  • 集合代数、命题代数(PPT_Chapter 11 Page39)
  • __定理11.7 必看__（双重否定律与德摩根律）
  • 等价定义（交换律、分配律、同一律、补元律）
• 原子

图论 知识点过于零散，且多为信息学竞赛/ACM竞赛中重复知识，只针对部分概念： 考试重点：欧拉图、哈密顿图、最小生成树、树的遍历 # 图的基本概念 ## 图 * 顶点数称作图的 __阶__，n个顶点的图称作n阶图。 * 零图：无边图；n阶零图记作$N_n$. 一阶零图$N_1$称为平凡图。 * 空图：顶点集为空集,符号化为:$\emptyset$ * 标定图与非标定图:给顶点和边加上符号 * 有向图的无向化的无向图称为基图。 * 边与端点的关联次数:0,1,2 * 点相邻:有边相连； 边相邻:共点 * 孤立点:无边关联的点 * (闭)邻域、关联集、先驱、后继 * __平行边__：即重边，平行边的边数称为 __重数__ * 简单图:不含平行边、环(离散数学中的环即是自环)的图称为 __简单图__ * 度数（入度、出度）、最大度、最小度 * 悬挂顶点：度数为1的顶点。与之关联的边称作 __悬挂边__。 * __握手定理__ - 无向图中，所有顶点的度数之和等于边数的两倍 - 有向图中，所有顶点的度数之和等于边数的两倍;所有顶点的入度和等于所有顶点的出度和，都等于边数。 - 推论:奇度顶点的个数是偶数。 * 度数列、可(简单)图化 - 非负整数列可图化当且仅当$\sum_{i=1}^{n}d_i$为偶数 - 设$G$为$n$阶无向简单图,则$\Delta (G)\leq n-1$ * 图同构 * n阶无向完全图、n阶完全图、n阶有向完全图、n阶竞赛图、k-正则图 * 母图、子图、导出子图 * 补图、自补图

通路与回路

(课本P301)

• 通路，简单通路，初级通路（路径）
• 回路，简单回路，圈

图的连通性

• 顶点之间连通
  • 连通图，连通分支，距离
  • 点割集，割点，边割集，割边（桥）
• 点连通度，边连通度
  • 强连通，单向连通，弱连通

图的矩阵表示

• 关联矩阵
• 邻接矩阵
• 可达矩阵

欧拉图与哈密顿图

欧拉图

• 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.
• 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.
• 欧拉图——具有欧拉回路的图.
• 半欧拉图——具有欧拉通路而无欧拉回路的图.
  • 规定平凡图为欧拉图.
  • 环不影响图的欧拉性.
• 判定欧拉图(课本P317)

哈密顿图

(1) 哈密顿通路——经过图中所有顶点一次仅一次的通路.
(2) 哈密顿回路——经过图中所有顶点一次仅一次的回路.
(3) 哈密顿图——具有哈密顿回路的图.
(4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图.

几点说明：

平凡图是哈密顿图.
哈密顿通路是初级通路，哈密顿回路是初级回路.
环与平行边不影响哈密顿性.
哈密顿图的实质是能将图中的所有顶点排在同一个圈上

判定哈密顿图 (课本P321)

最短路问题等

树

• 无向树及生成树
  • 无向树的定义 (包括等价定义)
  • 无向树的性质
• 生成树
  • 定义，由连通图构造 __最小生成树的克鲁斯克尔算法__。
• 根树及其应用
  • 有向树及根树的定义，
  • 家族树，有序树，r叉树的概念
  • 最优二叉树的概念和哈夫曼算法，二叉树周游

资料合集

来自由薛晖老师离散QQ群 :

来自外班同学:

【update】删去课件，可自行前往老师主页下载。

来自外班同学:

点击下载 计科考试真题

来自倒数第二节复习课:
百度云 提取码: ue34