【离散数学】第一章到第七章知识点总结+自己的见解

2023-10-25 19:10:52

第一章 命题逻辑的基本概念

1.1 命题与联结词

命题：非真即假的陈述句

真值：命题陈述句的所表达的判断结果，有两个值（真或假）

简单命题（原子命题）：不能被分解成更简单的命题

复合命题：由简单命题通过联结词联结而成的命题

题型：判断句子是否为命题：

  • 是否为陈述句

  • 是否有唯一真值（不用知道真值的具体值，但一定要知道存在真值）

    2050年元旦是晴天。(√)是否为晴天是客观存在的，是唯一的

    我正在说假话。(×)悖论不是命题

    x + 5 > 6 （x）真值不确定

  • 命题的符号化：使用小写英文字母表示命题，用1或0表示真假。

    2或4是素数。其符号化为：
    p：2是素数；q：4是素数

联结词 符号
否定 ¬ \lnot ¬
合取 ∧ \land ∧
析取 ∨ \lor ∨
蕴涵 → \rightarrow →
等价 ↔ \leftrightarrow ↔

注意点：这个阅读理解的要小心阅读

关于合取式的特殊情况
张三与李四都是三好学生。其符号化为：
p：张三是好学生；q：李四是好学生
张三和李四是同学。其符号化为：
p：张三和李四是同学

蕴含式：设a,b为两个命题，复合命题"如果a,则b"称为a与b的蕴涵式，记作a->b，并称a是蕴涵式的前件，b是蕴涵式的后件。->称作蕴涵式联结词。当且仅当a为真，q为假时，a->b为假。

在自然语言中，如果a，则b，中的前件和后件往往具有某种内在联系，而数理逻辑是研究抽象的推理，前件和后件可以没有任何内在联系，只需要体现出真假即可

联结词的优先顺序： ( , ) , ¬ , ∧ , ∨ , → , ↔ (,),\lnot,\land,\lor,\rightarrow,\leftrightarrow (,),¬,∧,∨,→,↔对于同一优先级，从左到右顺序进行。

1.2 命题公式及其赋值

命题常项（命题常元）：简单命题是命题逻辑中最基本的研究单元，其真值是确定的

命题变项（命题变元）：其真值是1或0；命题变项不是命题

合式公式：将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串。

单个命题变项是合式公式，并称为原子命题公式
合式公式也称命题公式，命题形式，简称为公式
合式公式A中的一部分B也是合式公式，则称B为A的子公式

元语言符号：用来表示任意的合式公式A，B

对象语言符号：用来表示具体的公式，如p,p->q,p∧q等

公式层次的定义：公式A为单个的命题变项，则称A为0层公式。

赋值和解释：设p1,p2,p3…是出现在公式A中的全部命题变项，给p1,p2,p3…各指定一个真值，称为对A的赋值或解释。若这组值使A为1，则称这组值为A的成真赋值，反之。

真值表的构建：构造真值表的具体步骤：

  • 找出公式中所含的全体命题变项p1,p2,p3…（按序号，按字母顺序），列出2n个赋值。从00…00开始，累加
  • 按照从低到高的顺序写出公式的各个层次，并计算真值

公式相等的判定：两个公式A与B的真值表对所有赋值最后一列都相等，那么两者就相等

重言式（永真式）：公式在它的所有赋值下均为真值
矛盾式（永假式）：公式在它的所有赋值下均为假值
可满足式：公式不是矛盾式

公式A，B*同含有命题变项p1,p2,p3…pn，而A或B不全含这些命题变项，例如：A中不含有pi,pi+1…，（i>=2），称这些命题变项为A的哑元。A的真值与哑元无关，但讨论二者相等时，需要将A和B都看成p1,p2,p…pn的命题公式。（都要带上哑元）

第二章 命题逻辑等值演算

2.1 等值式

公式等值的概念：两个命题（A,B）公式构成的等价式 A ↔ B A\leftrightarrow B A↔B为重言式，则AB等值，记 A ⇔ B A\Leftrightarrow B A⇔B

区分点： ⇔ \Leftrightarrow ⇔和 ↔ \leftrightarrow ↔的区别：前者是元语言符号，后者是等价联结词

判断两个公式是否等值的方法：

  • 真值表（一般只写结果，不写中间的过程）判断是否为重言式
  • 等值演算
  • 观察法（一般用来否定）

等值演算公式汇总（对我而言，好多公式不需要记，了解原理即可）

名称 公式（A，B，C是命题公式） 理解
双重否定句 A ⇔ ¬ ¬ A A\Leftrightarrow \lnot \lnot A A⇔¬¬A 负负得正
幂等律 A ⇔ A ∨ A , A ⇔ A ∧ A A\Leftrightarrow A \lor A,A\Leftrightarrow A\land A A⇔A∨A,A⇔A∧A 自身析取合取不变
交换律 A ∨ B ⇔ B ∨ A , A ∧ B ⇔ B ∧ B A\lor B \Leftrightarrow B\lor A,A\land B \Leftrightarrow B \land B A∨B⇔B∨A,A∧B⇔B∧B 命题公式运算没有方向得讲究
结合律 ( A ∨ B ) ∨ C ⇔ A ∨ ( B ∨ C ) ( A ∧ B ) ∧ C ⇔ A ∧ ( B ∧ C ) (A\lor B)\lor C\Leftrightarrow A\lor(B\lor C)\\(A\land B)\land C \Leftrightarrow A\land (B\land C) (A∨B)∨C⇔A∨(B∨C)(A∧B)∧C⇔A∧(B∧C) 同上
分配律 A ∨ ( B ∧ C ) ⇔ ( A ∨ B ) ∧ ( A ∨ C ) A ∧ ( B ∨ C ) ⇔ ( A ∧ B ) ∨ ( A ∧ C ) A\lor(B\land C)\Leftrightarrow(A\lor B)\land(A\lor C)\\A\land (B\lor C)\Leftrightarrow(A\land B)\lor(A\land C) A∨(B∧C)⇔(A∨B)∧(A∨C)A∧(B∨C)⇔(A∧B)∨(A∧C) 析取和合取之间得分配律
德摩根律 ¬ ( A ∨ B ) ⇔ ¬ A ∧ ¬ B , ¬ ( A ∧ B ) ⇔ ¬ A ∨ ¬ B \lnot(A\lor B)\Leftrightarrow \lnot A\land \lnot B,\lnot (A\land B)\Leftrightarrow \lnot A\lor \lnot B ¬(A∨B)⇔¬A∧¬B,¬(A∧B)⇔¬A∨¬B 展开取反
吸收律 A ∨ ( A ∧ B ) ⇔ A , A ∧ ( A ∨ B ) ⇔ A A\lor(A\land B)\Leftrightarrow A,A\land(A\lor B)\Leftrightarrow A A∨(A∧B)⇔A,A∧(A∨B)⇔A 画范围理解
零律 A ∨ 1 ⇔ 1 , A ∧ 0 ⇔ 0 A\lor1\Leftrightarrow1,A\land0\Leftrightarrow0 A∨1⇔1,A∧0⇔0 基本性质得使用，理解就行
同一律 A ∨ 0 ⇔ A , A ∧ 1 ⇔ A A\lor 0\Leftrightarrow A,A\land 1\Leftrightarrow A A∨0⇔A,A∧1⇔A 同上
排中律 A ∨ ¬ A ⇔ 1 A\lor \lnot A\Leftrightarrow1 A∨¬A⇔1 非真比假性质与析取性质
矛盾律 A ∧ ¬ A ⇔ 1 A\land \lnot A\Leftrightarrow1 A∧¬A⇔1 同上
蕴含等值式 A → B ⇔ ¬ A ∨ B A\rightarrow B \Leftrightarrow \lnot A\lor B A→B⇔¬A∨B 将唯一一种假的形式表示出来（对应真值相同）
假言易位 A → B ⇔ ¬ B → ¬ A A\rightarrow B\Leftrightarrow \lnot B\rightarrow \lnot A A→B⇔¬B→¬A 蕴含式逆否命题的概念
等价等值式 A ↔ B ⇔ ( A → B ) ∧ ( B → A ) A\leftrightarrow B\Leftrightarrow(A\rightarrow B)\land(B\rightarrow A) A↔B⇔(A→B)∧(B→A) 等价的条件等于二者蕴含式的合取式
等价否定等值式 A ↔ B ⇔ ¬ A ↔ ¬ B A\leftrightarrow B\Leftrightarrow\lnot A \leftrightarrow \lnot B A↔B⇔¬A↔¬B 等值式的否定也是成立的
归谬论 ( A → B ) ∧ ( A → ¬ B ) ⇔ ¬ A (A\rightarrow B)\land(A\rightarrow \lnot B)\Leftrightarrow\lnot A (A→B)∧(A→¬B)⇔¬A 这种情况下，A为真的话，后面一定为假，所以它只等价于其的否定式

代入实例：就是将具体的公式带入

例：

等值式为： A → B ⇔ ¬ A ∨ B A\rightarrow B \Leftrightarrow \lnot A\lor B A→B⇔¬A∨B

带入： A = p ∨ q ∨ r ;    B = p ∧ q A=p\lor q\lor r;\;B=p\land q A=p∨q∨r;B=p∧q

即： ( p ∨ q ∨ r ) → ( p ∧ q ) ⇔ ¬ ( p ∨ q ∨ r ) ∨ ( p ∧ q ) (p\lor q\lor r)\rightarrow (p\land q)\Leftrightarrow \lnot(p\lor q\lor r)\lor (p\land q) (p∨q∨r)→(p∧q)⇔¬(p∨q∨r)∨(p∧q)

置换规则：如果公式 A ⇔ B A\Leftrightarrow B A⇔B；则 ϕ ( A ) ⇔ ϕ ( B ) \phi(A)\Leftrightarrow \phi(B) ϕ(A)⇔ϕ(B)（简而言之：就是等值演算中公式互换）

2.2 析取范式与合取范式

简单析取（合取）式的概念：由有限个析取（合取）式和否定式构成

简单析取（合取）范式的概念：由有限个简单合取（析取）式通过析取（合取）联结词构成

一个文字既是简单析取式，又是简单合取式

范式存在定理：任一命题公式都存在与之等值的析取范式与合取范式。

题型：求给定范式的步骤：

  • 消去联结词 → , ↔ \rightarrow,\leftrightarrow →,↔
  • 用双重否定律消去双重否定词，用德摩根律内移否定符
  • 使用分配律：求析取范式时使用∧和∨的分配律，求合取范式时使用∨和∧的分配律

命题公式的析取（合取）范式不是唯一的，可以用很多种

极小（极大）项的概念：命题变项或他它的否定式按照下标从小到大或按照字典顺序排列，称这样的简单合取（析取）式为极小（极大）项（简而言之：合取式极小但用于析取方式，析取式极大但用于合取范式）

主析取（合取）范式的概念：所有合取（析取）式都是最小（最大）值组成的析取（合取）范式

记忆：我们使用的是，主析取范式，用的是最小值，析取联结词，置1的条件

极大值的否定式与极小值等值： ¬ m i ⇔ M i \lnot m_i\Leftrightarrow M_i ¬mi​⇔Mi​

注意点：极小项是正常的正负，极大项是反过来的（就是非为1）；极大成假值，极小成真值

主析取范式的作用：

  • 求公式的成真赋值与成假赋值
  • 判断公式的类型
  • 判断两个命题公式是否等值（判断两者的主析取范式是否相等）

2.3 联结词的完备集

n元真值函数的概念： F : { 0 , 1 } n → { 0 , 1 } F:\{0,1\}^n\rightarrow\{0,1\} F:{0,1}n→{0,1}；F的自变量为n个命题变项，定义域 { 0 , 1 } n = { 00...0 , 00...1 , . . . , 11...1 } \{0,1\}^n=\{00...0,00...1,...,11...1\} {0,1}n={00...0,00...1,...,11...1}，由0和1组成长度为n的符号串的全体，值域为 { 0 , 1 } \{0,1\} {0,1}；所以n个命题变项可以构成 2 2 n {2^{2}}^{n} 22n个不同的真值函数-

每一个真值函数都与唯一的一个主析取范式等值；但每个主析取范式对应无穷多个等值的命题公式；每一个命题公式又都又唯一的主析取范式，所以：每个真值函数对应无穷多个等值的命题公式，每个媒体公式对应都对应这唯一的等值的真值函数

联结词完备集的概念：任何n元真值函数都可以由仅含联结词集合中的联结词构成的公式，则该联结词集合为联结词完备集（简而言之：这些联结词通过等值演算可以推出其他所有联结词即成立）

{ ¬ , ∧ , ∨ } \{\lnot,\land,\lor\} {¬,∧,∨}是联结词完备集（只要联结词互相可以推出完备集的话，也是完备集）

p与q的否定式，称作p,q的与非式，记作p↑q，即p↑q⇔¬(p∧q)，符号↑称作与非联结词

p或q的否定式，称作p,q的或非式，记作p↓q，即p↓q⇔¬(p∨q)，符号↓称作与非联结词

{↓},{↑}都是联结词完备集

第三章 命题逻辑的推理理论

3.1 推理的形式结构

有效的结论的概念：设 A 1 , A 2 , . . . , A k 和 B A_1,A_2,...,A_k和B A1​,A2​,...,Ak​和B是命题公式，对其中出现的命题变项的任意一组赋值，或者 A 1 ∧ A 2 ∧ . . . ∧ A k A_1\land A_2\land...\land A_k A1​∧A2​∧...∧Ak​为假，或者 A 1 ∧ A 2 ∧ . . . ∧ A k A_1\land A_2\land...\land A_k A1​∧A2​∧...∧Ak​为真时，B也为真，则称由前提 A 1 , A 2 , . . . , A k A_1,A_2,...,A_k A1​,A2​,...,Ak​推出结论B的推理是有效的，并称B为有效的结论（简而言之：就是前提<注意是合取>当作蕴含式的前件，结论当成蕴含式的后件，全部情况符合蕴含式的条件即正确）记作： { A 1 , A 2 , . . . , A k } ⊨ B \{A_1,A_2,...,A_k\}\vDash B {A1​,A2​,...,Ak​}⊨B（等同于 A 1 ∧ A 2 ∧ . . . ∧ A k ⇒ B A_1\land A_2\land...\land A_k\Rightarrow B A1​∧A2​∧...∧Ak​⇒B）；反之加斜杠；记 { A 1 , A 2 , . . . , A k } ⊢ B \{A_1,A_2,...,A_k\}\vdash B {A1​,A2​,...,Ak​}⊢B为推理的形式结构

⇒ \Rightarrow ⇒是元语言符号，表示蕴含式为重言式

判断推理的形式结构是否正确：

  • 真值表
  • 等值演算
  • 主析取范式

写题过程：①简单命题符号化；②设出前提，结论和推理的形式结构

推理定律

名称 公式 理解（一般只需要考虑前真的情况对后面的影响）
附加律 A ⇒ ( A ∨ B ) A\Rightarrow (A\lor B) A⇒(A∨B) 前真后必真
化简律 ( A ∧ B ) ⇒ A (A\land B)\Rightarrow A (A∧B)⇒A 前真后必真
假言推理 ( A → B ) ∧ A ⇒ B (A\rightarrow B)\land A\Rightarrow B (A→B)∧A⇒B
拒取式 ( A → B ) ∧ ¬ B ⇒ ¬ A (A\rightarrow B)\land\lnot B\Rightarrow \lnot A (A→B)∧¬B⇒¬A
析取三段论 ( A ∨ B ) ∧ ¬ B ⇒ A (A\lor B)\land\lnot B\Rightarrow A (A∨B)∧¬B⇒A
假言三段论 ( A → B ) ∧ ( B → C ) ⇒ ( A → C ) (A\rightarrow B)\land(B\rightarrow C)\Rightarrow(A\rightarrow C) (A→B)∧(B→C)⇒(A→C)
等价三段论 ( A ↔ B ) ∧ ( B ↔ C ) ⇒ ( A ↔ C ) (A\leftrightarrow B)\land (B\leftrightarrow C)\Rightarrow (A\leftrightarrow C) (A↔B)∧(B↔C)⇒(A↔C)
构造性二难 ( A → B ) ∧ ( C → D ) ∧ ( A ∨ C ) ⇒ ( B ∨ D ) ( A → B ) ∧ ( ¬ A → B ) ⇒ B (A\rightarrow B)\land (C\rightarrow D)\land(A\lor C)\Rightarrow(B\lor D)\\(A\rightarrow B)\land (\lnot A\rightarrow B)\Rightarrow B (A→B)∧(C→D)∧(A∨C)⇒(B∨D)(A→B)∧(¬A→B)⇒B
破坏性二难 ( A → B ) ∧ ( C → D ) ∧ ( ¬ B ∨ ¬ D ) ⇒ ( ¬ A ∨ ¬ C ) (A\rightarrow B)\land(C\rightarrow D)\land (\lnot B\lor\lnot D)\Rightarrow(\lnot A\lor\lnot C) (A→B)∧(C→D)∧(¬B∨¬D)⇒(¬A∨¬C)

3.2 自然推理系统

形式系统 I I I的概念：由四个部分组成

  • 非空的字母表 A ( I ) A(I) A(I)
  • A ( I ) A(I) A(I)中符号构造的合适公式集 E ( I ) E(I) E(I)
  • E ( I ) E(I) E(I)中一些特殊的公式组成的公理集 A x ( I ) A_x(I) Ax​(I)
  • 推理规则 R ( I ) R(I) R(I)

I I I记为4元组 < A ( I ) , E ( I ) , A x ( I ) , R ( I ) > <A(I),E(I),A_x(I),R(I)> <A(I),E(I),Ax​(I),R(I)>；其中 < A ( I ) , E ( I ) > <A(I),E(I)> <A(I),E(I)>是 I I I的形式语言系统，而 < A x ( x ) , R ( I ) > <A_x(x),R(I)> <Ax​(x),R(I)>为 I I I的形式演算系统

形式系统分为两类：

  • 自然推荐系统：从任意给定的前提出发，应用系统中的推理规则进行演算，最后得到的命题公式是推理的结论
  • 公理推理系统：从给定的公理出发，应用系统中的推理规则进行推理演算，等到的结论是系统中的重言式，称为系统中的定理（本书未介绍）

自然推荐系统P的定义：

  • 字母表

    • 命题变项符号： p , q , r , . . . , p i , q i , r i , . . . ( i ≥ 1 ) p,q,r,...,p_i,q_i,r_i,...(i\ge1) p,q,r,...,pi​,qi​,ri​,...(i≥1)
    • 联结词符号： ¬ , ∧ , ∨ , → , ↔ \lnot,\land,\lor,\rightarrow,\leftrightarrow ¬,∧,∨,→,↔
    • 括号和逗号： ( ) , (), (),

  • 合式公式

    合式公式（谓词公式，简称公式）：原子公式是合式公式，通过原子公式和逻辑符号组合

  • 推理规则

    • 前提引入规则：在证明的任何步骤都可以引入前提
    • 结论引入规则：在证明的任何步骤所得到结论都可以作为后继证明的前提
    • 置换规则：在证明的任何步骤，命题公式中的子公式都可以用等值的公式置换，得到公式序列中的又一个公式
    • 假言推理规则（分离规则）：公式序列中出现过 A → B A\rightarrow B A→B和 A A A，通过假言推理定律可知 B B B是有效结论
    • 其他同理
    • 合取引入规则：知道 A 和 B A和B A和B，可以知道 A ∧ B A\land B A∧B

构造证明方法：

  • 附加前提证明法：对于结论是 A → B A\rightarrow B A→B的形式，就直接引入前提 A A A，这样只要求出结论 B B B即可证明
  • 归谬法：对于结论是 ¬ A \lnot A ¬A的形式，就先将结论的否定 A A A引入，这样求出结论 ¬ A ∧ A \lnot A\land A ¬A∧A即可

3.3 消解证明法（会写题，要考）

基本做法：把前提中公式和结论的否定都化成等值的合取范式，以这些合取范式中的所有简单析取式作为前提，用消解规则构造证明，得到空式，则证明正确。（只使用了前提引入和消解两条规则）

例题：

前提： q → p , q ↔ s , s ↔ t , t ∧ r q\rightarrow p,q\leftrightarrow s,s\leftrightarrow t,t\land r q→p,q↔s,s↔t,t∧r

结论： p ∧ q ∧ s p\land q\land s p∧q∧s

解：先求前提中各式的合取范式，和结论否定的合取范式
p → p ⇔ ¬ q ∨ p q ↔ s ⇔ ( ¬ q ∨ s ) ∧ ( ¬ s ∨ q ) s ↔ t ⇔ ( ¬ s ∨ t ) ∧ ( ¬ t ∨ s ) t ∧ r ¬ ( p ∧ q ∧ s ) ⇔ ¬ p ∨ ¬ q ∨ ¬ s p\rightarrow p \Leftrightarrow \lnot q\lor p\\ q\leftrightarrow s \Leftrightarrow(\lnot q\lor s)\land(\lnot s\lor q)\\ s\leftrightarrow t \Leftrightarrow(\lnot s\lor t)\land (\lnot t \lor s)\\ t\land r\\ \lnot(p\land q\land s)\Leftrightarrow \lnot p\lor \lnot q\lor \lnot s p→p⇔¬q∨pq↔s⇔(¬q∨s)∧(¬s∨q)s↔t⇔(¬s∨t)∧(¬t∨s)t∧r¬(p∧q∧s)⇔¬p∨¬q∨¬s
前提改成： ¬ q ∧ p , ¬ q ∨ s , ¬ s ∨ q , ¬ s ∨ t , ¬ t ∨ s , t , r , ¬ p ∨ ¬ q ∨ ¬ s \lnot q\land p,\lnot q\lor s,\lnot s\lor q,\lnot s\lor t,\lnot t\lor s,t,r,\lnot p\lor\lnot q\lor \lnot s ¬q∧p,¬q∨s,¬s∨q,¬s∨t,¬t∨s,t,r,¬p∨¬q∨¬s

证明：

  1. ¬ t ∨ s \lnot t\lor s ¬t∨s 前提引入
  2. t t t 前提引入
  3. s s s 12归结
  4. ¬ s ∨ q \lnot s\lor q ¬s∨q 前提引入
  5. q q q 34归结
  6. ¬ q ∨ p \lnot q\lor p ¬q∨p 前提引入
  7. p p p 56归结
  8. ¬ p ∨ ¬ q ∨ ¬ s \lnot p\lor\lnot q\lor\lnot s ¬p∨¬q∨¬s 前提引入
  9. ¬ q ∨ ¬ s \lnot q\lor \lnot s ¬q∨¬s 78归结
  10. ¬ s \lnot s ¬s 59归结
  11. 空式 3 10归结

第四章 一阶逻辑基本概念

一阶逻辑也称作一阶谓词逻辑或谓词逻辑

4.1 一阶逻辑符号化

个体词的基本概念：是指所研究对象中可以独立存在的具体的或抽象的客体。

  • 个体常项表示具体或特定的客体的个体词（一般用a,b,c）
  • 个体变项表示抽象或泛指的个体词（一般用x,y,z），并称个体变项的取值范围为个体域（论域）
  • 全总个体域是由宇宙一切事物组成的

谓词的概念：是用来刻画个体词性质及个体词之间相互关系的词（一般用F,G,H）

例子：

2是整数。

2是个体常项，“…是整数”是谓词，记作F；所以上述句子可以表示为F（2）

x与y具有关系L。

x,y是两个个体变项，L是谓词，该句符号化为L（x,y）

谓词常项，具有确定的关系；谓词变项，关系式未知的。

n元谓词的概念：含有n(n≥1)个谓词变项的谓词P，记作P(x1,x2,…,xn)

当n为1时，P(x1)表示x1具有性质P

当n≥2时，P(x1,x2,…,xn)表示x1,x2,…,xn之间具有关系P

0元谓词：不带个体变项的谓词；当谓词是常项谓词的话，0元谓词为命题

量词的概念：表示个体常项或变项之间数量关系的词

  • 全称量词∀

    ∀x表示个体域中所有个体x

    ∀xF(x)表示个体域里所有个体x都有性质F

  • 存在量词∃（同上）

  • 特征谓词：当使用全总个体域时，为了将事物与其他事物区分开来，需要引入谓词M(x)

一阶命题符号化解题思路:

  • 在所有的情况下，用 → \rightarrow →；在存在的情况下，用 ∧ \land ∧
  • 注意分辨
  • 注意翻译的顺序就是量词的顺序

4.2一阶逻辑公式及其解释

一阶语言的概念：是用于一阶逻辑的形式语言；一阶逻辑是建立在一阶语言上的逻辑体系

非逻辑符号：个体常项符号，函数符号，谓词符号

逻辑符号：个体变项符号，量词符号，联结词符号和括号与逗号

一阶语言的字母表：L是一个非逻辑符号集合，由L生成的一阶语言的字母表如下：

  • 非逻辑符号

    • 个体常项符号（a,b,c,…;ai,bi,ci,…i≥1）
    • 函数符号（f,g,h…;fi,gi,hi…i≥1）
    • 谓词符号（F,G,H…;Fi,Gi,Hi…i≥1）

  • 逻辑符号

    • 个体变项符号（x,y,z…;xi,yi,zi…i≥1）
    • 量词符号（∃，∀）
    • 联结词符号（¬，∧，∨，↔，→）
    • 括号与逗号

一阶语言项的定义：

  • 个体常项符号和个体变项符号是项
  • 若f(x1,x2,x3,…)是n元函数符号，t1,t2,t3…是n个项，则f(t1,t2,t3…)是项

原子公式的概念：F（x1,x2,…）是一阶语言的n(n≥1)元谓词，t1,t2,t3…是一阶语言的n个项，则R(t1,t2,t3…)是一阶语言的原子公式

合式公式（谓词公式，简称公式）：原子公式是合式公式，通过原子公式和逻辑符号组合

概念：在公式∀xA中，x为指导变元，A为量词的辖域，在∀x的辖域中，x的所有出现都称约束出现，A中不是约束出现的其他变项均称为*出现。

∀xF(x,y)，x是约束出现，y是*出现

注意点：在一个公式中，约束出现和*出现是对于特定的辖域中讨论，不能跳辖域讨论

封闭的公式（闭式）：A中不含有*出现的个体变项

解释的概念：对个体域及个体常项符号，函数符号，谓词符号的指定称为解释

赋值的概念：指定*出现的个体变项的值称为赋值

一阶语言（由非逻辑符号集合 L L L）的解释 I I I由下面四个部分组成：

  • 非空个体域 D I D_I DI​
  • 对每一个个体常项符号 a ∈ L a\in L a∈L，有一个 a ‾ ∈ D I \overline{a}\in D_I a∈DI​，称 a ‾ \overline{a} a为 a a a在 I I I中的解释
  • 对每一个n元函数符号 f ∈ L f\in L f∈L，有一个 D I D_I DI​上的n元函数 f ‾ : D 1 n → D I \overline{f}:D_1^n\rightarrow D_I f​:D1n​→DI​，称 f ‾ \overline{f} f​为 f f f在 I I I的解释
  • 对每一个n元谓词符号 F ∈ L F\in L F∈L，有一个 D I D_I DI​上的n元谓词常项 F ‾ \overline{F} F,称 F ‾ \overline{F} F为 F F F在 I I I中的解释

I I I下的赋值 σ \sigma σ：对每一个个体变项符号x指定 D I D_I DI​中的一个值 σ ( x ) \sigma(x) σ(x)

解释的具体解释和赋值下（定义4.7），直接替代即可，解释和赋值后的任何公式都为命题。

特别地，对于闭式，由于没有*出现个体变项符号，所以不要赋值，只需要解释即可。

公式类型

  • 永真式（逻辑有效式）：在任何解释和该解释下的赋值下，公式均为真
  • 矛盾式（永假式）：在任何解释和该解释下的赋值下，公式均为假
  • 可满意式：非永假式即是可满足式

注意点：由于公式中的谓词和函数可以走各种不同的解释，使得情况变得异常复杂，永真式或永假式一般是不可判断的

代换实例：就是把公式中的公式替换会 p , q , r p,q,r p,q,r，再根据公式来判断永真式等

（结论记住了，反过来的）重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。

写题技巧：判断公式是否为永真式或矛盾式

  • 先看是不是重言式或矛盾式的代换实例
  • 不是上面一种情况的话，就语言举例判断

第五章 一阶逻辑等值演算

5.1 一阶逻辑等值式与置换规则

双重否定句变肯定，有两种表达形式

等值式的概念：A,B是一阶逻辑中任意两个公式，如果 A ↔ B A\leftrightarrow B A↔B是永真式，则称A,B等值，记作 A ⇔ B A\Leftrightarrow B A⇔B.称 A ⇔ B A\Leftrightarrow B A⇔B是等值式。

基本等值式：

等值演算中的命题公式换成一阶逻辑公式的16个公式

  • 消去两次等值式

    前 提 ： 个 体 域 为 有 限 域 D = { a 1 , a 2 , . . . , a n } ∀ x A ( x ) ⇔ A ( a 1 ) ∧ A ( a 2 ) ∧ . . . ∧ A ( a n ) ∃ x A ( x ) ⇔ A ( a 1 ) ∨ A ( a 2 ) ∨ . . . ∨ A ( a n ) 前提：个体域为有限域D=\{a_1,a_2,...,a_n\}\\ \forall xA(x)\Leftrightarrow A(a_1)\land A(a_2)\land ...\land A(a_n)\\ \exists xA(x)\Leftrightarrow A(a_1)\lor A(a_2)\lor...\lor A(a_n) 前提：个体域为有限域D={a1​,a2​,...,an​}∀xA(x)⇔A(a1​)∧A(a2​)∧...∧A(an​)∃xA(x)⇔A(a1​)∨A(a2​)∨...∨A(an​)
    理解：就是写题的基础，先消去量词，全称合取，存在析取

  • 量词否定等值式（注意顺序不能乱）
    ¬ ∀ x A ( x ) ⇔ ∃ x ¬ A ( x ) ¬ ∃ x A ( x ) ⇔ ∀ x ¬ A ( x ) \lnot \forall xA(x)\Leftrightarrow \exists x\lnot A(x)\\ \lnot \exists xA(x)\Leftrightarrow \forall x\lnot A(x) ¬∀xA(x)⇔∃x¬A(x)¬∃xA(x)⇔∀x¬A(x)
    理解：并不是所有x都有性质A，存在x没有性质A；不存在x满足性质A，所有x都不满足性质A

  • 量词辖域收缩与扩张等值式
    前 提 ： B 中 不 含 x 的 自 由 出 现 ∀ x ( A ( x ) ∨ B ) ⇔ ∀ x A ( x ) ∨ B ∀ x ( A ( x ) ∧ B ) ⇔ ∀ x A ( x ) ∧ B ∀ x ( A ( x ) → B ) ⇔ ∃ x A ( x ) → B ∀ x ( B → A ( x ) ) ⇔ B → ∀ x A ( x ) ∃ x ( A ( x ) ∨ B ) ⇔ ∃ x A ( x ) ∨ B ∃ x ( A ( x ) ∧ B ) ⇔ ∃ x A ( x ) ∧ B ∃ x ( A ( x ) → B ) ⇔ ∀ x A ( x ) → B ∃ x ( B → A ( x ) ) ⇔ B → ∃ x A ( x ) 前提：B中不含x的*出现\\ \forall x(A(x)\lor B)\Leftrightarrow \forall xA(x)\lor B\\ \forall x(A(x)\land B)\Leftrightarrow \forall xA(x)\land B\\ \forall x(A(x)\rightarrow B)\Leftrightarrow \exists xA(x)\rightarrow B\\ \forall x(B\rightarrow A(x))\Leftrightarrow B\rightarrow \forall xA(x)\\ \exists x(A(x)\lor B)\Leftrightarrow \exists xA(x)\lor B\\ \exists x(A(x)\land B)\Leftrightarrow \exists xA(x)\land B\\ \exists x(A(x)\rightarrow B)\Leftrightarrow \forall xA(x)\rightarrow B\\ \exists x(B\rightarrow A(x))\Leftrightarrow B\rightarrow \exists xA(x) 前提：B中不含x的*出现∀x(A(x)∨B)⇔∀xA(x)∨B∀x(A(x)∧B)⇔∀xA(x)∧B∀x(A(x)→B)⇔∃xA(x)→B∀x(B→A(x))⇔B→∀xA(x)∃x(A(x)∨B)⇔∃xA(x)∨B∃x(A(x)∧B)⇔∃xA(x)∧B∃x(A(x)→B)⇔∀xA(x)→B∃x(B→A(x))⇔B→∃xA(x)
    理解：对于析取合取：无关即无关**；对于蕴含：前件变量词，后件不用变**

  • 量词分配等值式
    ∀ x ( A ( x ) ∧ B ( x ) ) ⇔ ∀ x A ( x ) ∧ ∀ x B ( x ) ∃ x ( A ( x ) ∨ B ( x ) ) ⇔ ∃ x A ( x ) ∨ ∃ x B ( x ) \forall x(A(x)\land B(x)) \Leftrightarrow \forall xA(x)\land\forall xB(x)\\ \exists x(A(x)\lor B(x)) \Leftrightarrow \exists xA(x)\lor \exists xB(x) ∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)
    理解：约束出现的可以直接取出

  • 换名规则：直接可以把约束变项换一个名字

  • 置换规则：如果两公式为等值式，那么两公式的相同函数也是等值式

5.2 一阶逻辑前束范式

前束范式的概念：具有如下形式：Q1x1Q2x2…QkxkB的一阶逻辑公式称作前束范式，其中Qi(1≤i≤k)为∀和∃，B为不含量词的公式（简而言之：量词都在前面）

例如：∀x∃y（F(x)∧G(y)）(√)

∀x（F(x)→∃y（G(y)∧H（x,y）））(×)

前束范式存在定理：一阶逻辑中的任何公式都存在等值的前束范式

求解前束范式：

  • 先通过换名消去即是约束出现又是*出现的个体变项
  • 先消去蕴含式

5.3 一阶逻辑的推理理论

推理结构还是蕴含式

推理定律

  • 命题逻辑推理定律的代换实例（就是用实例带入公式而已）

  • 基本等值式生成的推理定律（一个生两个，互换位置）

  • 一些重要的推理定律

    定律 理解
    ∀ x A ( x ) ∨ ∀ x B ( x ) ⇒ ∀ x ( A ( x ) ∨ B ( x ) ) \forall xA(x)\lor\forall xB(x)\Rightarrow \forall x(A(x)\lor B(x)) ∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x)) 析取全称，整体取出来
    ∃ x ( A ( x ) ∧ B ( x ) ) ⇒ ∃ x A ( x ) ∧ ∃ x B ( x ) \exists x(A(x)\land B(x))\Rightarrow\exists xA(x)\land\exists xB(x) ∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x) 合取存在，整体展开
    ∀ x ( A ( x ) → B ( x ) ) ⇒ ∀ x A ( x ) → ∀ x B ( x ) \forall x(A(x)\rightarrow B(x))\Rightarrow\forall xA(x)\rightarrow\forall xB(x) ∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x) 蕴含全称，整体展开
    ∀ x ( A ( x ) → B ( x ) ) ⇒ ∃ x A ( x ) → ∃ x B ( x ) \forall x(A(x)\rightarrow B(x))\Rightarrow\exists xA(x)\rightarrow\exists xB(x) ∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x) 展开量词改变

  • 消去量词和引入量词的规则

    • 全称量词消去规则（ ∀ − \forall- ∀−）： ∀ ( F ( x ) → G ( x ) ) 通 过 ∀ − 可 以 得 出 F ( x ) → G ( x ) \forall(F(x)\rightarrow G(x))通过\forall-可以得出F(x)\rightarrow G(x) ∀(F(x)→G(x))通过∀−可以得出F(x)→G(x)
    • 全称量词引入规则（ ∀ + \forall+ ∀+）： F ( x ) → G ( x ) 通 过 ∀ + 可 以 得 出 ∀ ( F ( x ) → G ( x ) ) F(x)\rightarrow G(x)通过\forall+可以得出\forall(F(x)\rightarrow G(x)) F(x)→G(x)通过∀+可以得出∀(F(x)→G(x))
    • 存在量词消去规则（ ∃ − \exists- ∃−）： F ( x ) → ∃ x G ( x ) 和 ∃ x F ( x ) 通 过 ∃ − 可 以 得 出 ∃ x G ( x ) F(x)\rightarrow\exists xG(x)和\exists xF(x)通过\exists-可以得出\exists xG(x) F(x)→∃xG(x)和∃xF(x)通过∃−可以得出∃xG(x)
    • 存在量词引入规则（ ∃ + \exists+ ∃+）： F ( x ) → G ( x ) 通 过 ∃ + 可 以 得 出 F ( x ) → ∃ G ( x ) F(x)\rightarrow G(x)通过\exists+可以得出F(x)\rightarrow \exists G(x) F(x)→G(x)通过∃+可以得出F(x)→∃G(x)

第六章 集合代数

6.1 集合的基本概念

集合通常用大写的英文字母来标记

集合的表示方法：

  • 列元素法：A = {a,b,c,…,z}
  • 谓词表示法：B = {x|x∈R∧x-1=0}

集合的元素是彼此不同的；集合是无序的

元素和集合的关系：元素和集合是属于和不属于关系，使用 ∈ , ∉ \in,\notin ∈,∈/​

集合和集合的关系：集合和集合是包含和不包含关系，使用 ⊂ , ⊆ , ⊊ \subset,\subseteq,\subsetneq ⊂,⊆,⊊

空集的特殊性：空集是唯一的，是一切集合的子集

含有n个元素的集合简称为n元集合，它的含有m(m≤n)个元素的子集合称为它的m元子集。（一元子集为单自子集）

幂集的概念：A的全体子集构成的集合称为A的幂集，记作P(A)

全集的概念：在某一个具体问题中，如果所涉及的集合都是某个集合的子集，那么这个集合为全集记为E

6.2 集合的运算

集合的基本运算有并，交，相对补和对称差

相对补集的概念：B对A的相对补集A-B（简而言之：属于A并且不属于B）

对称差集的概念：A与B的对称差集A⊕B定义为A⊕B=(A-B)∪(B-A)（或A⊕B=(A∪B)-(A∩B)）（简而言之：两个集合的并集减去两个集合的交集）

绝对补集的概念：需要给定全集E即可，全集E中的补集

集合A的广义并的概念：就是所有元素的元素构成,记为∪A

集合A（A为非空集合）的广义交的概念：就是所有元素的公共元素构成，记为∩A；

注意：广义交和广义并操作后需要减去一层集合（就是要删去一个大括号）

规定:

  • 广义并，广义交，幂集，绝对补运算为一类运算
  • 并，交，相对补，对称差运算为二类运算
  • 一类运算优先于二类运算
  • 一类运算之间由右向左顺序进行
  • 二类运算之间由括号决定先后顺序

6.3 有穷集的计数

文氏图计算：会画图即可

包含排斥原理计算：考试一般都是三个计算，设未知数即可

6.4 集合恒等式（写过了，不会再来总结）

第七章 二元关系

7.1 有序对与笛卡尔积

有序对

又称序偶

表示形式：<x, y>；x是第一元素，y是第二元素

性质：

  • x ≠ y , < x , y > ≠ < y , x > x \ne y ,<x,y>\ne <y,x> x​=y,<x,y>​=<y,x>
  • 有序对相等必须要两个元素对应相等

笛卡尔积

表示形式： A × B = { < x , y > ∣ x ∈ A ∧ y ∈ B } A×B = \{<x,y>|x\in A \land y\in B\} A×B={<x,y>∣x∈A∧y∈B}

理解：前面元素来自前面的集合，后面的元素来自后面的集合

性质：

  • A × ∅ = ∅ ， ∅ × A = ∅ A × \varnothing = \varnothing，\varnothing × A = \varnothing A×∅=∅，∅×A=∅

  • A × B ≠ B × A ( A ≠ ∅ ∧ B ≠ ∅ ∧ A ≠ B ) A × B \ne B × A(A \ne \varnothing \land B \ne \varnothing \land A \ne B) A×B​=B×A(A​=∅∧B​=∅∧A​=B)

  • ( A × B ) × C ≠ A × ( B × C ) ( A ≠ ∅ ∧ B ≠ ∅ ∧ C ≠ ∅ ) (A×B)×C\ne A×(B×C)(A\ne\varnothing\land B\ne\varnothing \land C \ne\varnothing) (A×B)×C​=A×(B×C)(A​=∅∧B​=∅∧C​=∅)

  • A × ( B ∪ C ) = ( A × B ) ∪ ( A × C ) ( B ∪ C ) × A = ( B × A ) ∪ ( C × A ) A × ( B ∩ C ) = ( A × B ) ∩ ( A × C ) ( B ∩ C ) × A = ( B × A ) ∩ ( C × A ) A×(B\cup C) = (A×B)\cup (A×C)\\(B\cup C)×A = (B×A)\cup (C×A)\\A×(B\cap C) = (A×B)\cap (A×C)\\(B\cap C)×A = (B×A)\cap (C×A) A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)

    理解：笛卡尔积与交并没有先后关系

  • A ⊆ C ∧ B ⊆ D ⇒ A × B ⊆ C × D A\subseteq C \land B \subseteq D \Rightarrow A×B\subseteq C×D A⊆C∧B⊆D⇒A×B⊆C×D（从范围上去思考；逆命题考虑空集的分配即可讨论）

7.2 二元关系

二元关系

二元关系（简称关系）的集合都满足下面的条件之一：

  • 集合非空，且它的元素都是有序对
  • 集合是空集

表示形式： < x , y > ∈ R ⇒ x R y < x , y > ∉ R ⇒ x R ( R 上 有 条 斜 杠 ) y <x,y>\in R\Rightarrow xRy\\ <x,y>\notin R \Rightarrow xR(R上有条斜杠)y <x,y>∈R⇒xRy<x,y>∈/​R⇒xR(R上有条斜杠)y

一些特殊关系：

  • 从A到B的二元关系：A×B的任何子集所定义的二元关系（A=B时，称为 A上的二元关系）

  • 空关系：空集称为A上的空关系

  • 全域关系： E A = { < x , y > ∣ x ∈ A ∧ y ∈ A } = A × A E_A=\{<x,y>|x\in A \land y\in A\} = A×A EA​={<x,y>∣x∈A∧y∈A}=A×A

    理解：第一元素和第二元素都属于A的笛卡尔积

  • 恒等关系： I A = { < x , x > ∣ x ∈ A } I_A=\{<x,x>|x\in A\} IA​={<x,x>∣x∈A}

    理解：第一元素等于第二元素，并属于A集合

  • 小于等于关系： L A = { < x , y > ∣ x , y ∈ A , x ≤ y } L_A=\{<x,y>|x,y\in A,x\le y\} LA​={<x,y>∣x,y∈A,x≤y}

    理解：x，y都属于A，但第一元素小于等于第二元素

  • 整除关系： D A = { < x , y > ∣ x , y ∈ A , x ∣ y } D_A=\{<x,y>|x,y\in A,x|y\} DA​={<x,y>∣x,y∈A,x∣y}

    理解：由整除的概念可得，前面比后面小；写题时注意本身整除本身

    整除的概念：整数a除以非零整数b，商为整数，且余数为零， 我们就说a能被b整除（或说b能整除a），记作a/b（表示 b 整除 a，即 a 是 b 的倍数，b 是 a 的因数）

  • 包含关系： R ⊆ = { < x , y > ∣ x , y ∈ A , x ⊆ y } R_\subseteq=\{<x,y>|x,y\in A,x\subseteq y\} R⊆​={<x,y>∣x,y∈A,x⊆y}

    同上理解

表示关系的方法

  • 集合表达式

  • 关系矩阵（<i,j>对应（i，j）的位置）

    A={x1,x2,…,xn}，R是A上的关系，则
    r i j { 1 ,    x i R x j 0 , e l s e r_{ij} \begin{cases} 1, \;x_iRx_j\\ 0, else \end{cases} rij​{1,xi​Rxj​0,else​
    则：
    M R = ( r 11 r 12 ⋯ r 1 n r 21 r 22 ⋯ r 2 n ⋮ ⋮ ⋱ ⋮ r n 1 r n 2 ⋯ r n n ) M_R=\begin{pmatrix} r_{11}&r_{12}&\cdots&r_{1n}\\ r_{21}&r_{22}&\cdots&r_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ r_{n1}&r_{n2}&\cdots&r_{nn}\\ \end{pmatrix} MR​=⎝⎜⎜⎜⎛​r11​r21​⋮rn1​​r12​r22​⋮rn2​​⋯⋯⋱⋯​r1n​r2n​⋮rnn​​⎠⎟⎟⎟⎞​

  • 关系图

    < x i , x j > ∈ R <x_i,x_j>\in R <xi​,xj​>∈R 那么图中就有一条xi到xj的一条有向边

7.3 关系的运算

习惯：

  • 我习惯将右复合说成连接，下面注意分辨
  • 限制我是用 ∣ | ∣ 表示

定义域： d o m R = { x ∣ ∃ y ( < x , y > ∈ R ) } domR=\{x|\exists y(<x,y>\in R)\} domR={x∣∃y(<x,y>∈R)}

理解：R中所有第一元素组成的集合

值域： r a n R = { y ∣ ∃ x ( < x , y > ∈ R ) } ranR=\{y|\exists x(<x,y>\in R)\} ranR={y∣∃x(<x,y>∈R)}

理解：R中所有第二元素组成的集合

域： f l d R = d o m R ∪ r a n R fldR=domR\cup ranR fldR=domR∪ranR

理解：R中所有元素的集合

逆关系： R − 1 = { < x , y > ∣ < y , x > ∈ R } R^{-1} = \{<x,y>|<y,x>\in R\} R−1={<x,y>∣<y,x>∈R}

G对F的右复合： F o G = { < x , y > ∣ ∃ t ( < x , t > ∈ F ∧ < t , y > ∈ G ) } FoG=\{<x,y>|\exist t(<x,t>\in F \land <t,y>\in G)\} FoG={<x,y>∣∃t(<x,t>∈F∧<t,y>∈G)}

理解：以某个数为连接数，将两个关系连接起来

R在A上的限制： R ∣ A = { < x , y > ∣ x R y ∧ x ∈ A } R|A=\{<x,y>|xRy\land x\in A\} R∣A={<x,y>∣xRy∧x∈A}

理解：关系R在A的定义域中的集合

A在R下的像： R [ A ] = r a n ( R ∣ A ) R[A]=ran(R|A) R[A]=ran(R∣A)

理解：关系R在A的定义域下的集合的值域

R的n次幂： R 0 = { < x , x > ∣ x ∈ A } = I A ( R 为 A 的 关 系 ) R n + 1 = R n o R R^0 =\{<x,x>|x\in A\} =I_A(R为A的关系)\\ R^{n+1}=R^noR R0={<x,x>∣x∈A}=IA​(R为A的关系)Rn+1=RnoR

技巧：

  • 对于A的任何关系的0次幂都是 I A I_A IA​
  • 如果R是用集合表达式给出的，那么通过连接多次即可获得答案
  • 如果R是用关系矩阵得出的，那么R的幂就是n个矩阵M之积；但要注意这里相加是逻辑加（ 1 + 1 = 1 , 1 + 0 = 1 , 0 + 1 = 1 , 0 + 0 = 0 1 + 1 = 1,1+0=1,0+1=1,0+0=0 1+1=1,1+0=1,0+1=1,0+0=0 ）

注意：关系运算的逆运算优先于其他运算，所有关系运算都优先于集合运算

关系的基本运算

  • ( F − 1 ) − 1 = F (F^{-1})^{-1}=F (F−1)−1=F

    理解：逆的逆等于本身

  • d o m F − 1 = r a n F ,    r a n f − 1 = d o m F domF^{-1}=ranF,\;ranf^{-1}=domF domF−1=ranF,ranf−1=domF

    理解：逆的值域和定义域和原本相反

  • ( F o G ) o H = F ( G o H ) (FoG)oH=F(GoH) (FoG)oH=F(GoH)

    理解：都是连接性质的，中间做连接词

  • ( F o G ) − 1 = G − 1 o F − 1 (FoG)^{-1}=G^{-1}oF^{-1} (FoG)−1=G−1oF−1

    理解：连接的逆和逆的连接本质上是一样的（注意顺序）

  • R o I A = I A o R = R ( R 为 A 上 的 关 系 ) RoI_A=I_AoR=R(R为A上的关系) RoIA​=IA​oR=R(R为A上的关系)

    理解：与恒等关系做连接，最后的结果不变

  • F o ( G ∪ H ) = F o G ∪ F o H ( G ∪ H ) o F = G o F ∪ H o F F o ( G ∩ H ) = F o G ∩ F o H ( G ∩ H ) o F = G o F ∩ H o F Fo(G\cup H) = FoG\cup FoH\\ (G\cup H)oF=GoF\cup HoF\\Fo(G\cap H) = FoG\cap FoH\\ (G\cap H)oF=GoF\cap HoF Fo(G∪H)=FoG∪FoH(G∪H)oF=GoF∪HoFFo(G∩H)=FoG∩FoH(G∩H)oF=GoF∩HoF

    理解：先并（交）后并（交）对连接没有影响

  • F ∣ ( G ∪ H ) = F ∣ G ∪ F ∣ H ( G ∪ H ) ∣ F = G ∣ F ∪ H ∣ F F ∣ ( G ∩ H ) = F ∣ G ∩ F ∣ H ( G ∩ H ) ∣ F = G ∣ F ∩ H ∣ F F|(G\cup H) = F|G\cup F|H\\ (G\cup H)|F=G|F\cup H|F\\F|(G\cap H) = F|G\cap F|H\\ (G\cap H)|F=G|F\cap H|F F∣(G∪H)=F∣G∪F∣H(G∪H)∣F=G∣F∪H∣FF∣(G∩H)=F∣G∩F∣H(G∩H)∣F=G∣F∩H∣F

    理解：限制对于定义域有影响，但对先交（并）后交（并）没有影响

  • 存在自然数s和t，使 R s = R t R^s=R^t Rs=Rt

    理解： R k R^k Rk都是 E A E_A EA​的子集，但是 E A E_A EA​是有限个的，所以必当存在两个不同次幂相等

  • R m o R n = R m + n R^moR^n=R^{m+n} RmoRn=Rm+n

    理解：m次连接接着相互连接了n次

  • ( R m ) n = R n m (R^m)^n =R^{nm} (Rm)n=Rnm

    理解：经过n次的m次连接

  • R s + k = R t + k ( 当 R s = R t ) R^{s+k} = R^{t+k}(当R^s = R^t) Rs+k=Rt+k(当Rs=Rt)

    理解：从集合表达式的角度分析，相同的矩阵经过相同次数的连接R，结果应该是相同的

  • ( k , i ∈ N ) ∃ R s + k p + i = R s + i ( 当 R s = R t ) ⇒ p = t − s (k,i\in N)\exists R^{s+kp+i} = R^{s+i}(当R^s = R^t)\Rightarrow p=t-s (k,i∈N)∃Rs+kp+i=Rs+i(当Rs=Rt)⇒p=t−s

    理解：p代表的意义：一个矩阵经过连接p次会得到原来的矩阵

  • s < t ;    R s = R t S = { R 0 , r 1 , . . . , R t } ;    ∀ q ∈ N ⇒ R q ∈ S s<t;\;R^s=R^t\\S=\{R^0,r^1,...,R^t\};\;\forall q\in N\Rightarrow R^q\in S s<t;Rs=RtS={R0,r1,...,Rt};∀q∈N⇒Rq∈S

    理解：这种连接的过程是渐进的，出现重复代表开始新一轮的循环

7.4 关系的性质

自反性： ∀ x ( x ∈ A → < x , x > ∈ R ) \forall x(x\in A\rightarrow <x, x>\in R) ∀x(x∈A→<x,x>∈R)，R在A上是自反的

理解：所有A中的元素，在R中都有一二序列相等的有序对

理解（课本给出的，下面也提到，加深印象）：R包含 I A I_A IA​

反自反性： ∀ x ( x ∈ A → < x , x > ∉ R ) \forall x(x\in A\rightarrow <x,x>\notin R) ∀x(x∈A→<x,x>∈/​R)，R在A上是反自反的2

理解：所有的A中的元素，在R中都没有一二序列相等的有序对

对称性： ∀ x ∀ y ( x , y ∈ A ∧ < x , y > ∈ R → < y , x > ∈ R ) \forall x\forall y(x,y\in A\land<x,y>\in R\rightarrow <y,x>\in R) ∀x∀y(x,y∈A∧<x,y>∈R→<y,x>∈R)，R为A上对称的关系

理解：所有在R中一二序列元素属于A集合中的有序对的逆序对也存在R中

反对称性： ∀ x ∀ y ( x , y ∈ A ∧ < x , y > ∈ R ∧ < y , x > ∈ R → x = y ) \forall x\forall y(x,y\in A\land<x,y>\in R\land<y,x>\in R\rightarrow x=y) ∀x∀y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，R为A上的反对称

理解：R中不能存在一二元素都存在于A集合中的互逆有序对（要两个的那种）

传递性： ∀ x ∀ y ∀ z ( x , y , z ∈ A ∧ < x , y > ∈ R ∧ < y , z > ∈ R → < x , z > ∈ R ) \forall x\forall y\forall z(x,y,z\in A\land <x,y>\in R\land<y,z>\in R\rightarrow<x,z>\in R) ∀x∀y∀z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)，R在A上由传递关系

理解：所有一二序列的元素相等的两个有序对的其他一二序列元素（三个元素都要存在于A集合中）

组成的有序对存在R中

一些定理（充分别要条件的）

  • 自反性： I A ⊆ R I_A\subseteq R IA​⊆R

    理解：自反需要的是包含 I A I_A IA​

  • 反自反性： R ∩ I A = ∅ R\cap I_A=\varnothing R∩IA​=∅

    理解：刚好与上面相反

  • 对称性： R = R − 1 R=R^{-1} R=R−1

    理解：存在互逆有序对（反了一样是充分必要条件要注意区分）

  • 反对称性： R ∩ R − 1 ⊆ I A R\cap R^{-1}\subseteq I_A R∩R−1⊆IA​

    理解：R与其的逆的交集都是存在于 I A I_A IA​

  • 传递性： R o R ⊆ R RoR\subseteq R RoR⊆R

    理解：自身连接后的关系还是存在于自身的

表示 自反性 反自反性 对称性 反对称性 传递性
集合表达式 I A ⊆ R I_A\subseteq R IA​⊆R R ∩ I A = ∅ R\cap I_A=\varnothing R∩IA​=∅ R = R − 1 R=R^{-1} R=R−1 R ∩ R − 1 ⊆ I A R\cap R^{-1}\subseteq I_A R∩R−1⊆IA​ R o R ⊆ R RoR\subseteq R RoR⊆R
关系矩阵 主对角线全是1 主对角线全是0 对称矩阵 i = j → r i j = 0 i=j\rightarrow r_{ij}=0 i=j→rij​=0其他为1 M 2 M^2 M2中1所在的位置，M中相应的位置都是1
关系图 每个顶点都有环 每个顶点都没有环 如果连个顶点有边的话，一定要有两条相反方向的边 如果两个顶点有边的话，一定只能有一条单向边 如果 x i x_i xi​到 x j x_j xj​右边， x j x_j xj​到 x k x_k xk​也有边的话，那么 x i x_i xi​到 x k x_k xk​之间也有边

7.5 关系的闭包

自反闭包（对称，传递） R ’ R’ R’满足的条件：

  • R ′ R' R′是自反的（对称或传递）
  • R ⊆ R ′ R\subseteq R' R⊆R′
  • 对于A上任何包含R的自反（对称或传递）关系 R ′ ′ R'' R′′有 R ′ ⊆ R ′ ′ R'\subseteq R'' R′⊆R′′

理解：在R中添加最少数量的有序对使其变成自反的（对称或传递）

一些关系：

  • 自反闭包 r ( R ) = R ∪ R 0 r(R)=R\cup R^0 r(R)=R∪R0

  • 对称闭包 s ( R ) = R ∪ R − 1 s(R)=R\cup R^{-1} s(R)=R∪R−1

  • 传递闭包 t ( R ) = R ∪ R 2 ∪ R 3 . . . . t(R)=R\cup R^2\cup R^3.... t(R)=R∪R2∪R3....；推论：存在r使得 t ( R ) = R ∪ R 2 ∪ R 3 . . . ∪ R r t(R)=R\cup R^2\cup R^3...\cup R^r t(R)=R∪R2∪R3...∪Rr

    理解：在R的基础上，将必要的有序对加上；推论的理解：后面会重复循环，所以有特殊值；证明的过程，就证明定义的三个条件（不会）

  • R是自反的当且仅当 r ( R ) = R r(R)=R r(R)=R

  • R是对称的当且仅当 s ( R ) = R s(R)=R s(R)=R

  • R是传递的当且仅当 t ( R ) = R t(R)=R t(R)=R

  • 在 R 1 ⊆ R 2 R_1\subseteq R2 R1​⊆R2的情况下，

    • r ( R 1 ) ⊆ r ( R 2 ) r(R_1)\subseteq r(R_2) r(R1​)⊆r(R2​)

    • r ( R 1 ) ⊆ r ( R 2 ) r(R_1)\subseteq r(R_2) r(R1​)⊆r(R2​)

    • r ( R 1 ) ⊆ r ( R 2 ) r(R_1)\subseteq r(R_2) r(R1​)⊆r(R2​)

      理解：一开始的条件就已经确定了大小关系，后面只是添加一些大家都缺少的的东西而已

  • 若R是自反的，那么 s ( R ) s(R) s(R)和 t ( R ) t(R) t(R)也是自反的

    理解：自反只需要包含 I A I_A IA​即可

  • 若R是对称的，那么 r ( R ) r(R) r(R)和 t ( R ) t(R) t(R)也是对称的

    理解：理解点就是 t ( R ) t(R) t(R)这一块：因为对称的是两边互通的，所以要变成传递性，他也会两各方向都加一个的

  • 若R是传递的，那么 r ( R ) r(R) r(R)是传递的

    理解： r ( R ) r(R) r(R)只是在顶点上自身操作，不会影响传递性，但 s ( R ) s(R) s(R)会在顶点与顶点之间操作，会导致传递性出现问题（只有一个有序对的时候）

7.6 等价关系与划分

等价关系：R是自反的、对称的和传递的，则称R是A上的等价关系； < x , y > ∈ R <x,y>\in R <x,y>∈R称x等价于y，记作x~y

等价类：
[ x ] R = { y ∣ y ∈ A ∧ x R y } [x]_R=\{y|y\in A \land xRy\} [x]R​={y∣y∈A∧xRy}
[ x ] R [x]_R [x]R​为x关于R的等价类，简称x的等价类，简记 [ x ] [x] [x]或 x ‾ \overline x x

举例说明：

设 A = 1 , 2 , 3 , 4... , 8 A={1,2,3,4...,8} A=1,2,3,4...,8，其A上的关系R为：
R = { < x , y > ∣ x , y ∈ A ∧ x ≡ y ( m o d    3 ) } R=\{<x,y>|x,y\in A\land x\equiv y(mod\;3) \} R={<x,y>∣x,y∈A∧x≡y(mod3)}
注： x ≡ y ( m o d    3 ) x\equiv y(mod\;3) x≡y(mod3)称做x于y模3相等；就是x除以3的余数和y除以3的余数相等

通过下图可以看出R是A上的等价关系

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cYBxJ5OW-1624090702228)(img/等价关系.png)]

看关系图分成三部分，每一部分所有顶点被分为一个等价类

所以上图的等价类为：

[ 1 ] = [ 4 ] = [ 7 ] = { 1 , 4 , 7 } [ 2 ] = [ 5 ] = [ 8 ] = { 2 , 5 , 8 } [ 3 ] = [ 6 ] = { 3 , 6 } [1]=[4]=[7]=\{1,4,7\}\\ [2]=[5]=[8]=\{2,5,8\}\\ [3]=[6]=\{3,6\} [1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}

同理，在整数集上模n的等价关系类似

等价关系的性质：

  • ∀ x ∈ A , [ x ] \forall x\in A,[x] ∀x∈A,[x]是A的非空子集

    理解：一定是有一个集合的，最小也有一个元素

  • ∀ x , y ∈ A \forall x,y\in A ∀x,y∈A，如果xRy，那么[x]=[y]

    理解：只有相互之间有关系的才会在一个等价类中

  • ∀ x , y ∈ A \forall x,y\in A ∀x,y∈A，如果xR（有条斜线），则[x]与[y]不交

  • ∪ { [ x ] ∣ x ∈ A } = A \cup\{[x]|x\in A\}=A ∪{[x]∣x∈A}=A

    理解，所有等价类的并集就是A本身

商集：以所有等价类作为元素的集合，称为A关于R的商集
A / R = { [ x ] R ∣ x ∈ A } A/R=\{[x]_R|x\in A\} A/R={[x]R​∣x∈A}
集合的划分：一个 π \pi π（ π ⊆ P ( A ) \pi \subseteq P(A) π⊆P(A)）满足下面条件：

  • ∅ ∉ π \varnothing \notin \pi ∅∈/​π

  • ∀ x ∀ y ( x , y ∈ π ∧ x ≠ y → x ∩ y = ∅ ) \forall x\forall y(x,y\in \pi \land x\ne y\rightarrow x\cap y=\varnothing) ∀x∀y(x,y∈π∧x​=y→x∩y=∅)

    理解：两个集合不相等，那么他们之间一定不交

  • ∪ π = A \cup \pi = A ∪π=A

划分有很多种，商集只是其中一种

7.7 偏序关系

偏序关系：R是自反的，反对称的和传递的，称R为A上的偏序关系，记作 ≤ \le ≤，设 ≤ \le ≤为偏序关系，如果 < x , y > ∈ ≤ <x,y>\in\le <x,y>∈≤，记作 x ≤ y x\le y x≤y，读作：x小于等于y

这里的小于等于不是指数的关系，而是指在偏序关系中的顺序性

x小于等与y，表示依照这个序，x排在y的前面，或x就是y

设 ≤ \le ≤为非空集合A上的偏序关系，定义：

  • ∀ x , y ∈ A , x < y ⇔ x ≤ y ∧ x ≠ y \forall x,y\in A,x\lt y\Leftrightarrow x\le y \land x\ne y ∀x,y∈A,x<y⇔x≤y∧x​=y

  • ∀ x , y ∈ A , x 与 y 可 比 ⇔ x ≤ y ∨ y ≤ x \forall x,y\in A,x与y可比\Leftrightarrow x\le y\lor y\le x ∀x,y∈A,x与y可比⇔x≤y∨y≤x

    理解：可比就是两者之间要有互相包含的关系；如果全是可比的就称为全序关系（线性关系）

集合A和A上的偏序关系 ≤ \le ≤一起称作偏序集，记作 < A , ≤ > <A,\le> <A,≤>
利用偏序关系的性质可以简化一个偏序关系的关系图，得到偏序集的哈斯图

设 < A , ≤ > <A,\le> <A,≤>为偏序集， ∀ x , y ∈ A \forall x,y\in A ∀x,y∈A，如果 x < y x\lt y x<y且不存在 z ∈ A z\in A z∈A使得 x < z < y x\lt z\lt y x<z<y则称y覆盖x

理解：就是y只比x多一个元素

画哈斯图的步骤：

  • x < y x\lt y x<y—>将x画在y的下方
  • y覆盖x，就用一条线段连接

通过哈斯图得有序对：底下是第一序列往上写（下面可以跳的（传递性））

最小（大）元：只有一个（哈斯图的点没有下接）

极小（大）元：有多个（哈斯图的点没有上接）

上（下）界：在一个子集中，上界需要在子集中所有点的上（下）方（简而言之：就是某个点是连接该子集中的所有点，并且在上（下）面）

最大（小）下（上）界：最小（大）元或数值最大（小）的下（上）界；只有一个

附加

  • 证明一般都可以使用命题演算法（就是写出元素的属于关系）也可以使用归纳法
上一篇：Atcoder Regular Contest 072 C - Alice in linear land（思维题）


下一篇：WCF技术剖析之二十六:如何导出WCF服务的元数据(Metadata)[实现篇]