
离散数学笔记(4)——谓词逻辑(续)和集合论
谓词演算的推理理论
推理方法
直接推理、条件论证、反证法
所用公式
等价式、蕴含式
推理规则
P,T,CP,US,ES,EG,UG
全称特质规则 US
形式:∀xA(x)⇒A(c)(其中 c 是论域内指定个体)
含义:如果 ∀xA(x) 为真,则在论域内任何指定个体 c,都使得 A(c) 为真。
作用:去掉全称量词。
要求:c 不是 A(x) 中的符号。
存在特制规则 ES
形式:∃xA(x)⇒A(c)(其中 c 是论域内指定个体)
含义:如果 ∃xA(x) 为真,则在论域内指定个体 c,都使得 A(c) 为真。
作用:去掉存在量词。
要求:
- c 不是 A(x) 中的符号。
- 用 ES 指定的客体 c 不应该是在此之前用 US 规则或者用 ES 规则所指定的个体 c。
- A(x) 中除 x 外还有其他自由出现的个体变元时,不能用此规则。
存在推广规则 EG
形式:A(c)⇒∃xA(x)(其中 c 是论域内指定个体)
含义:如果在论域内指定个体 c 使得 A(c) 为真,则 ∃xA(x) 为真。
作用:添加存在量词。
要求:x 不是 A(c) 中的符号。
全程推广规则 UG
形式:A(c)⇒∀xA(x)(其中 c 是论域内任何指定个体)
含义:如果在论域内任何指定个体 c 使得 A(c) 为真,则 ∀xA(x) 为真。
作用:添加全称量词。
要求:
- x 不是 A(c) 中的符号。
- c 一定是任意的个体,否则不可全称推广。
量词有关的重要等价式与蕴含式
\langle img src=”https://wzf2000.top/wp-content/uploads/————/——————/19-1.png” alt=”19″ style=”zoom: 67%;” / \rangle
\langle img src=”https://wzf2000.top/wp-content/uploads/2019/10/————/20.png” alt=”20″ style=”zoom: 50%;” / \rangle
注意点
- 使用 US、UG、ES、EG 规则应对前束范式。
在推理过程中,谓词公式只能应用前面给出的蕴含式与等价式。
在含有多个量词的谓词推理中,使用指定规则应该按照从左到右的顺序,而推广规则的使用应该按照从右到左的顺序。
集合论
基本定义
集合
是一些确定的、可以区分的事物汇集在一起组成的一个整体。用大写的英文字母表示。
元素
集合中的每个事物,称之为元素。用小写英文字母表示 ∈ 表示元素与集合的属于关系。
有限集合与无限集合
有限集合:元素是有限个的集合。
如果A是有限集合,用 |A| 表示 A 中元素个数。
无限集合:元素是无限个的集合
集合的表示方法
列举法(外延表示法)
将集合中的元素一一列出,写在大括号内。
描述法(谓词法)
用句子(或谓词公式)描述元素的属性。
A={x|P(x)},其中 P(x) 是谓词公式,如果论域内个体 a 使得 P(a) 为真,则 a∈A,否则 a∉A。
特别说明
- 集合中的元素间次序是无关紧要的,但是必须是可以区分的。
- 对集合中的元素无任何限制。
- 常用的几个集合符号的约定:
- 自然数集合 N={0,1,2,3,……}。
- 整数集合 Z。
- 实数集合 R。
- 有理数集合 Q。
- 集合中的元素也可以是集合。
- 对一个集合来说,任一事物或者是它的元素或者不是它的元素,二者必居其一而不可兼而有之,且结论是确定的。
集合间的关系
被包含关系(子集)
A、B 是集合,如果 A 中元素都是 B 中元素,则称 B 包含 A,A 包含于 B, 也称 A 是 B 的子集。
记作 A⊆B。
谓词定义:A⊆B⇔∀x(x∈A→x∈B)
性质:
- 自反性,A⊆A
- 传递性,A⊆B,B⊆C,则 A⊆C
- 反对称性,A⊆B,B⊆A,则 A=B
相等关系
A、B 是集合,如果它们的元素完全相同,则称 A 与 B 相等。
记作 A=B。
谓词定义:A=B⇔∀x(x∈A↔x∈B)
定理:A=B 当且仅当 A⊆B 且 B⊆A
性质:
- 自反性,A=A
- 传递性,A=B,B=C,则 A=C
- 对称性,A=B,则 B=A
真被包含关系(真子集)
A、B 是集合,如果 A⊆B 且 A≠B,则称 B 真包含 A,A真包含于 B,也称 A 是 B 的真子集。
记作 A⊂B。
谓词定义:
性质:
对任何集合 A、B、C,如果有 A⊂B 且 B⊂C ,则 A⊂C。
特殊集合
全集:E
包含所讨论的所有集合的集合,称之为全集,记作 E。
性质:对于任何集合 A,都有 A⊆E。
空集:∅
不含任何元素的集合,称之为空集,记作 ∅。
性质:
- 对于如何集合 A,都有 ∅⊆A。 因为 ∀x(x∈∅→x∈A)为永真式,所以 ∅⊆A。
- 空集是唯一的。
集合的幂集
A 是集合,由 A 的所有子集构成的集 合,称之为 A 的幂集。记作 P(A) 或 2A。
P(A)={B|B⊆A}
结论:
对任意集合 A,因为 ∅⊆A,A⊆A,所以有 ∅∈P(A),A∈P(A) 。
集合的运算
交运算 ∩
A、B 是集合,由既属于 A,也属于 B 的元素构成的集合,称之为 A 与 B 的交集,记作 A∩B。
谓词定义:
A∩B={x|x∈A∧x∈B}
x∈A∩B⇔x∈A∧x∈B
性质:
- 幂等律,A∩A=A
- 交换律,A∩B=B∩A
- 结合律,(A∩B)∩C=A∩(B∩C)
- 同一律,A∩E=A
- 零律,A∩∅=∅
- A⊆B⇔A∩B=A
并运算 ∪
A、B 是集合,由或属于 A,或属于 B 的元素构成的集合,称之为 A 与 B 的并集,记作 A∪B。
谓词定义:
A∪B={x|x∈A∨x∈B}
x∈A∪B⇔x∈A∨x∈B
性质:
- 幂等律,A∪A=A
- 交换律,A∪B=B∪A
- 结合律,(A∪B)∪C=A∪(B∪C)
- 同一律,A∪∅=A
- 零律,A∪E=E
- 分配率,A∩(B∪C)=(A∩B)∪(A∩C),A∪(B∩C)=(A∪B)∩(A∪C)
- 吸收律,A∪(A∩B)=A,A∩(A∪B)=A
- A⊆B⇔A∪B=B
- A⊆B⇒A∪C⊆B∪C,A∩C⊆B∩C
- A⊆B∧C⊆D⇒A∪C⊆B∪D,A∩C⊆B∩D
差运算 −
A、B 是集合,由属于 A,而不属于 B的元素构成的集合,称之为 A 与 B 的差集,或 B 对 A 的相对补集,记作 A−B。
谓词定义:
A–B={x|x∈A∧x∉B}
x∈A–B⇔x∈A∧x∉B
性质:
- A–∅=A
- ∅–A=∅
- A–A=∅
- A–B⊆A
- A⊆B⇔A–B=∅
- A–B=A⇔A∩B=∅
绝对补集 ∼
A 是集合,由不属于 A 的元素构成的集合,称之为 A 的绝对补集,记作 ∼A。实际上 ∼A=E–A。
谓词定义:
∼A=E–A={x|x∈E∧x∉A}={x|x∉A}
x∈∼A⇔x∉A
性质:
- ∼E=∅
- ∼∅=E
- ∼(∼A)=A
- A∩∼A=∅
- A∪∼A=E
- A–B=A∩∼B
- ∼(A∩B)=∼A∪∼B
- ∼(A∪B)=∼A∩∼B
对称差 ⊕
A、B 是集合,由属于 A 而不属于 B,或者属于 B 而不属于 A 的元素构成的集合,称之为 A 与 B 的对称差,记作 A⊕B。
谓词定义:
A⊕B=(A–B)∪(B–A)={x|(x∈A∧x∉B)∨(x∈B∧x∉A)}
A⊕B=(A∪B)–(A∩B)
性质:
- 交换律,A⊕B=B⊕A
- 结合律,(A⊕B)⊕C=A⊕(B⊕C)
- 同一律,A⊕∅=A
- A⊕A=∅
序偶与集合的笛卡尔积
序偶与有序 n 元组
由两个对象 x、y 组成的序列称为有序二元组,也称之为序偶,记作 ⟨x,y⟩;称 x、y 分别为序偶 ⟨x,y⟩ 的第一,第二元素。
注意,序偶 ⟨x,y⟩ 与集合 {x,y}不同:
序偶 ⟨x,y⟩:元素 x 和 y 有次序;
集合 {x,y}:元素 x 和 y 的次序是无关紧要的。
设 ⟨x,y⟩,⟨u,v⟩ 是两个序偶,如果 x=u 和 y=v,则称 ⟨x,y⟩ 和 ⟨u,v⟩ 相等, 记作 ⟨x,y⟩=⟨u,v⟩。
有序 n 元组是一个序偶,其第一个元素本身是个有序 n−1 元组,记作 $\langle
⟨x1,x2,⋯,xn⟩=⟨y1,y2,⋯,yn⟩⇔(x1=y1)∧(x2=y2)∧⋯∧(xn=yn)
集合的笛卡尔积
设 A、B 是集合,由 A 的元素为第一元素,B 的元素为第二元素组成序偶的集合,称为 A 和 B 的笛卡尔积,记作 A×B,即 A×B={⟨x,y⟩|x∈A∧y∈B}
性质:
- 如果 A、B 都是有限集,且 |A|=m,|B|=n, 则 |A×B|=mn.
- A×∅=∅×B=∅
- 分配律:
- A×(B∪C)=(A×B)∪(A×C)
- A×(B∩C)=(A×B)∩(A×C)
- (A∪B)×C=(A×C)∪(B×C)
- (A∩B)×C=(A×C)∩(B×C)
- 若 C≠∅,A⊆B⇔(A×C⊆B×C)⇔(C×A⊆C×B)
- 设 A、B、C、D 为非空集合,则 A×B⊆C×D⇔A⊆C∧B⊆D
优先权
关系及其表示法
关系
设 A、B 是集合,如果 R⊆A×B,则称 R 是一 个从 A 到 B 的二元关系。
如果 R⊆A×A,则称 R 是 A 上的二元关系。
二元关系简称为关系。
任何序偶的集合,都称之为一个二元关系。
列举法和描述法。
xRy 表示有关系 R。
xR̸y 表示无关系 R。
关系的定义域与值域
定义域:设 R⊆A×B,称集合 domR={x|∃y(⟨x,y⟩∈R)} 为 R 的定义域。
值域:设 R⊆A×B,称集合 ranR={y|∃x(⟨x,y⟩∈R)} 为 R 的值域。
关系的域:fidR=domR∪ranR
结论:domR⊆A,ranR⊆B
关系的另两种表示法
- 有向图法:
R⊆A×B(A、B 非空、有限),用两组小圆圈(称为结点)分别表示 A 和 B 的元素,当 ⟨x,y⟩∈R 时,从 x 到 y 引一条有向弧(边)(由 x 指向 y)。这样得到的图形称为 R 的关系图。 如 R⊆A×A,即 R 是集合 A 中关系时,用一组小圆圈表示 A 中的元素,若 ⟨x,x⟩∈R,则从 x 到 x 画一条有向环(自回路)。
矩阵表示法:
非空有限集合之间的关系也可以用矩阵来表示,这种表示法便于用计算机来处理关系。
设 A={a1,a2,⋯,am},B={b1,b2,⋯,bn} 是个有限集,R⊆A×B,定义 R 的 m×n 阶矩阵 MR=(rij)m×n,其中:
rij={1⟨ai,bj⟩∈R0⟨ai,bj⟩∉R(1≤i≤m,1≤j≤n)
称 MR 为关系 R 的关系矩阵。
No Comments