离散数学课件第二章(第2讲)

We denote the Inverse relation of B to A by S R-1.
R1 {(b, a) | (a, b) R, a A, b B}
2024/11/24
§5.1 Relations and their properties (7)
Exam:集合A={a, b, c}，B={1, 2, 3, 4, 5}，R是A 上的关系，S是A到B的关系。 R={<a, a>, <a, c>, <b, b>, <c, b>, <c, c>}， S={<a, 1>, <a, 4>, <b, 2>, <c, 4>, <c, 5>} 求：S·R，(S·R)-1，R–1，S–1，R–1·S–1
2024/11/24
§5.1 Relations and their properties (7) 5.1.4 Properties of relations
特殊关系 空关系 全域关系EA 恒等关系IA P(A)上的包含关系 三角形的相似关系
自反性 ⅹ
√ √ √ √
反自反性
√
ⅹ ⅹ ⅹ ⅹ
对称性
√ √ √
ab(a A b A (a,b) R (b,a) R a b)
ab(a A b A aRb a b bR a)
2024/11/24
§5.1 Relations and their properties (6)
5.1.4 Properties of relations
We denote the composite of R and S by SR.
S R {(a, c) | a A, c C, b B such that (a, b) R, (b, c) S}

量词的作用域即是找出位于该量词之后的相邻子公式，分为以下两种
情况：
（1）若量词后有括号，则括号内的子公式是该量词的作用域。
（2）若量词后无括号，则与量词邻接的子公式为该量词的作用域。
判断公式A中个体变元是自由变元还是约束变元，主要观察它在公 式中是自由出现还是约束出现，自由变元是不受约束的变元，虽然它 有时也在量词的作用域中出现，但它不受相应量词中指导变元的约束。
2.2 谓词公式与翻译
2.2.1 谓词公式 2.2.2 谓词公式的翻译
An Introduction to Database Systenm
2.2.2 谓词公式的翻译
对于含有谓词的命题，在符号化时应注意： （1）区分命题中表示性质和关系的谓词，分别符号化为一元和多元 谓词。 （2）根据命题的实际意义选用全称量词或存在量词。当命题有多个 量词时，注意它们的顺序不能随意调换。 例如：考虑个体的取值范围为实数域，P(x, y)表示x-y=5，则命题 “对于任意x都存在y，使得x-y=5”的符号化形式( 为x)： (y)P(x,y) 。该命题 为真命题。若改变量词的出现顺序，得谓词公(y式) (x)P(x,y) ，表示命 题“存在y，对任意x，使得x-y=5”，显然该命题为假命题。 （3）有些命题的符号化形式可能不止一种。 例如：这张红色的餐桌摆满了那些可口的中餐。若令F(x, y)表示“x 摆满了y”，R(x)表示“x是红色的餐桌”，B(x)表示“可口的中餐”，a表 示“这张”，b表示“那些”，则命题符号化为R(a)∧B(b)∧F(a, b)。若将 个体描述性质的谓词划分得更细些，则翻译成不同的谓词公式。若令F(x, y)表示“x摆满了y”，A(x)表示“x是餐桌”，B(x)表示“x是红色的”， C(x)表示“x是中餐”，D(x)表示“x是可口的”，a表示“这张”，b表示 “那些”，则命题符号化为： A(a)∧B(a)∧C(b)∧D(b)∧F(a, b)。

23

注意：
有些关系既不是对称的也不是反对称的；
0 1 0 1 0 1 0 0 0
可以是既是对称的，也是反对称的

如相等关系
24
定义2.10：在集合X上的关系R，如果有：
x, y R且 y, z R ，则必有 x, z R ，
即非对角线上的1， 对称位置必须是0； 而非对角线上的0 不做要求
判断方法：
1. 如果如果存在a到b的有向边，就不存在b到a的有向边。 （逆命题不成立，即可以两条有向边都不存在）； 2. 关系矩阵中，如果 a j ,i 1则ai , j 0，这里i j
(注意：a j ,i 0不一定ai , j 1)
n个
容易证明： n m nm m n i: R R R , R R mn ，m,n均为正整数 0 ii: R 是相等关系，即： R0 ={(x,x)|x∈A} 1 iii: R R
13

逆关系
由于关系中的元素是有序偶，则如果将该有序偶的顺
序颠倒，会得到一个新的关系，称之为逆关系。
~ ~ ~
~
补集的逆关系
~ ~ ~
(5) R S R S , R S R S
注意，这个跟德· 摩根律不一样
(6) R S R S
~
~
~
18
关系的重要性质

定义2.6：在集合X上的关系R，如果对任意 x X ， 有 x, x R ，则称R是自反的。
如：整数集合上的相等关系、" " 关系等；

如果 miq mqj 1 即mij 0 ，则 miq mqj 1 即 ai , aq R且 aq , a j R 由传递性的定义可知，如果R为传递的， 必有 ai , a j R ，即应有 mij 1 2 即：当R是A上的传递关系时，如果 M R 中的元素 bij 0 ， 则必须有 mij 1 ，反之亦然

定义2.1设A,B是两个命题公式，若A，B构成的等价 式AB为重言式，则称A与B等值，记为AB。
20
例2.1判断下面两个公式是否等值： (pq), pq 例2.2判断下面各组公式是否等值： （1）p(qr) 与 (pq)r （2） ( pq)r与 (pq)r
21
置换规则 ： 设（A）是含公式A的命题公式， （B） 是用公式B置换了（A）中所有的A以后得到的命题公式， 若BA，则（B） （A）。
定义1.2 设p，q为两命题，复合命题“p并且q”称为p与 q的合取式，记作“pq”。 pq为真当且仅当 p， q同 时为真。
定义1.3 设p，q为两命题，复合命题“p或q”称为p与q的 析取式，记作“pq”。 p q为假当且仅当 p， q同时为 假。
7
例1.3将下列命题符号化 （1）吴影既用功又聪明。 （2）吴影不仅用功而且聪明。 （3）吴影虽然聪明，但不用功。 （4）张辉与王丽都是三好学生。 （5）张辉与王丽是同学
16
例1.8求下列公式的真值表，并求成真赋值。 (1) (pq)r (2) (pp)(qq) (3) (p q) q r
定义1.10设A为一命题公式 （1）若A在它的各种赋值下取值均为真，则称A是重 言式或永真式。 （2）若A在它的各种赋值下取值均为假，则称A是矛 盾式或永假式。 （3）若A不是矛盾式，则称A是可满足式。
离散数学
1
离散数学课件
离散数学是计算机科学的核心理论课程， 是计算机专业的专业基础课。
第一部分 数理逻辑 第二部分 集合与关系代数 第三部分 图论
2
第一部分数理逻辑
第一章 命题逻辑基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑推理理论 第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理