Loading [MathJax]/jax/output/HTML-CSS/jax.js

离散数学笔记(4)——谓词逻辑(续)和集合论

离散数学笔记(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) 为真。

作用:去掉存在量词。

要求

  1. c 不是 A(x) 中的符号。
  2. 用 ES 指定的客体 c 不应该是在此之前用 US 规则或者用 ES 规则所指定的个体 c
  3. 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) 为真。

作用:添加全称量词。

要求

  1. x 不是 A(c) 中的符号。
  2. 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) 为真,则 aA,否则 aA

特别说明

  1. 集合中的元素间次序是无关紧要的,但是必须是可以区分的。
  2. 对集合中的元素无任何限制。
  3. 常用的几个集合符号的约定:
    1. 自然数集合 N={0,1,2,3,}
    2. 整数集合 Z
    3. 实数集合 R
    4. 有理数集合 Q
  4. 集合中的元素也可以是集合。
  5. 对一个集合来说,任一事物或者是它的元素或者不是它的元素,二者必居其一而不可兼而有之,且结论是确定的。

集合间的关系

被包含关系(子集)

AB 是集合,如果 A 中元素都是 B 中元素,则称 B 包含 AA 包含于 B, 也称 AB 的子集。

记作 AB

谓词定义ABx(xAxB)

性质

  1. 自反性,AA
  2. 传递性,AB,BC,则 AC
  3. 反对称性,AB,BA,则 A=B

相等关系

AB 是集合,如果它们的元素完全相同,则称 AB 相等。

记作 A=B

谓词定义A=Bx(xAxB)

定理A=B 当且仅当 ABBA

性质

  1. 自反性,A=A
  2. 传递性,A=B,B=C,则 A=C
  3. 对称性,A=B,则 B=A

真被包含关系(真子集)

AB 是集合,如果 ABAB,则称 B 真包含 AA真包含于 B,也称 AB 的真子集。

记作 AB

谓词定义

21

性质

对任何集合 ABC,如果有 ABBC ,则 AC

特殊集合

全集:E

包含所讨论的所有集合的集合,称之为全集,记作 E

性质:对于任何集合 A,都有 AE

空集:

不含任何元素的集合,称之为空集,记作

性质

  1. 对于如何集合 A,都有 A。 因为 x(xxA)为永真式,所以 A
  2. 空集是唯一的。

集合的幂集

A 是集合,由 A 的所有子集构成的集 合,称之为 A 的幂集。记作 P(A)2A

P(A)={B|BA}

结论

对任意集合 A,因为 AAA,所以有 P(A),AP(A)

集合的运算

交运算

AB 是集合,由既属于 A,也属于 B 的元素构成的集合,称之为 AB 的交集,记作 AB

谓词定义

AB={x|xAxB}

xABxAxB

性质

  1. 幂等律,AA=A
  2. 交换律,AB=BA
  3. 结合律,(AB)C=A(BC)
  4. 同一律,AE=A
  5. 零律,A=
  6. ABAB=A

并运算

AB 是集合,由或属于 A,或属于 B 的元素构成的集合,称之为 AB 的并集,记作 AB

谓词定义

AB={x|xAxB}

xABxAxB

性质

  1. 幂等律,AA=A
  2. 交换律,AB=BA
  3. 结合律,(AB)C=A(BC)
  4. 同一律,A=A
  5. 零律,AE=E
  6. 分配率,A(BC)=(AB)(AC),A(BC)=(AB)(AC)
  7. 吸收律,A(AB)=A,A(AB)=A
  8. ABAB=B
  9. ABACBC,ACBC
  10. ABCDACBD,ACBD

差运算

AB 是集合,由属于 A,而不属于 B的元素构成的集合,称之为 AB 的差集,或 BA 的相对补集,记作 AB

谓词定义

AB={x|xAxB}

xABxAxB

性质

  1. A=A
  2. A=
  3. AA=
  4. ABA
  5. ABAB=
  6. AB=AAB=

绝对补集

A 是集合,由不属于 A 的元素构成的集合,称之为 A 的绝对补集,记作 A。实际上 A=EA

谓词定义

A=EA={x|xExA}={x|xA}

x∈∼AxA

性质

  1. E=
  2. =E
  3. (A)=A
  4. AA=
  5. AA=E
  6. AB=AB
  7. (AB)=∼AB
  8. (AB)=∼AB

对称差

AB 是集合,由属于 A 而不属于 B,或者属于 B 而不属于 A 的元素构成的集合,称之为 AB 的对称差,记作 AB

谓词定义

AB=(AB)(BA)={x|(xAxB)(xBxA)}

AB=(AB)(AB)

性质

  1. 交换律,AB=BA
  2. 结合律,(AB)C=A(BC)
  3. 同一律,A=A
  4. AA=

序偶与集合的笛卡尔积

序偶与有序 n 元组

由两个对象 xy 组成的序列称为有序二元组,也称之为序偶,记作 x,y;称 xy 分别为序偶 x,y 的第一,第二元素。

注意,序偶 x,y 与集合 {x,y}不同:

序偶 x,y:元素 xy 有次序;

集合 {x,y}:元素 xy 的次序是无关紧要的。

x,yu,v 是两个序偶,如果 x=uy=v,则称 x,yu,v 相等, 记作 x,y=u,v

有序 n 元组是一个序偶,其第一个元素本身是个有序 n1 元组,记作 $\langle \langle x_1 , x_2 ,\cdots, x_{n-1}, x_n \rangle$。

x1,x2,,xn=y1,y2,,yn(x1=y1)(x2=y2)(xn=yn)

集合的笛卡尔积

AB 是集合,由 A 的元素为第一元素,B 的元素为第二元素组成序偶的集合,称为 AB 的笛卡尔积,记作 A×B,即 A×B={x,y|xAyB}

性质

  1. 如果 AB 都是有限集,且 |A|=m,|B|=n, 则 |A×B|=mn.
  2. A×=×B=
  3. 分配律:
    1. A×(BC)=(A×B)(A×C)
    2. A×(BC)=(A×B)(A×C)
    3. (AB)×C=(A×C)(B×C)
    4. (AB)×C=(A×C)(B×C)
  4. CAB(A×CB×C)(C×AC×B)
  5. ABCD 为非空集合,则 A×BC×DACBD

优先权

22

关系及其表示法

关系

AB 是集合,如果 RA×B,则称 R 是一 个从 AB 的二元关系。

如果 RA×A,则称 RA 上的二元关系。

二元关系简称为关系。

任何序偶的集合,都称之为一个二元关系。

列举法和描述法。

xRy 表示有关系 R

xy 表示无关系 R

关系的定义域与值域

定义域:设 RA×B,称集合 domR={x|y(x,yR)}R 的定义域。

值域:设 RA×B,称集合 ranR={y|x(x,yR)}R 的值域。

关系的域fidR=domRranR

结论domRA,ranRB

关系的另两种表示法

  1. 有向图法:

    RA×BAB 非空、有限),用两组小圆圈(称为结点)分别表示 AB 的元素,当 x,yR 时,从 xy 引一条有向弧(边)(由 x 指向 y)。这样得到的图形称为 R 的关系图。 如 RA×A,即 R 是集合 A 中关系时,用一组小圆圈表示 A 中的元素,若 x,xR,则从 xx 画一条有向环(自回路)。

  2. 矩阵表示法:

    非空有限集合之间的关系也可以用矩阵来表示,这种表示法便于用计算机来处理关系。

    A={a1,a2,,am}B={b1,b2,,bn} 是个有限集,RA×B,定义 Rm×n 阶矩阵 MR=(rij)m×n,其中:

    rij={1ai,bjR0ai,bjR(1im,1jn)


    MR 为关系 R 的关系矩阵。

 

点赞 0

No Comments

Add your comment

你是我最真模样,从来不曾遗忘。