离散数学例题

1、.量词的辖域定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。 例：XP(X)Q(X) X的辖域是P(X) $X(P(X,Y)Q(X，Y) ) P(Y,Z) $X的辖域是P(X，Y)Q(X，Y)有限个体域上消去量词例15: 个体域D=a,b,c, 则消去下面公式中的量词$xyF(x,y) $x (F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c) (F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c)例16：设个体域D=a,b，消去下面各公式中的量词： (1) xy(F(x) G(y) x(F(x

2、) yG(y) xF(x) yG(y) (F(a)F(b) (G(a)G(b)(2) xy(F(x,y) G(x,y) x(F(x,a) G(x,a)(F(x,b)G(x,b) (F(a,a) G(a,a)(F(a,b)G(a,b) (F(b,a) G(b,a)(F(b,b)G(b,b)注：(1)中量词辖域可以缩小，先缩小量词辖域，再消量词，演算简单；但在(2)中，因为全称量词和存在量词均约束F与G中个体变量，因而它们的辖域不能缩小，消去量词后的公式也不易化的更简单。例17 将下面命题用两种形式符号化, 并证明两者等值: (1) 没有不犯错误的人解 令F(x)：x是人，G(x)：x犯错误. $

3、x(F(x)G(x) 或 x(F(x)G(x$x(F(x)G(x) x(F(x)G(x) 量词否定等值式 x(F(x)G(x) 置换 x(F(x)G(x) 置换(2) 不是所有的人都爱看电影解 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) 或 $x(F(x)G(x)x(F(x)G(x) $x(F(x)G(x) 量词否定等值式 $x(F(x)G(x) 置换 $x(F(x)G(x) 置换例18 求下列公式的前束范式 (1) $x(M(x)F(x)解 $x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 后两步结果都是前束范式，说明公式的前束范式不

4、惟一.(2) xF(x)$xG(x)解 xF(x)$xG(x) xF(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式）或 xF(x)$xG(x) xF(x)xG(x) 量词否定等值式 xF(x)yG(y) 换名规则 xy(F(x)G(y) 辖域收缩扩张规则(3) xF(x)$y(G(x,y)H(y)解 xF(x)$y(G(x,y)H(y) zF(z)$y(G(x,y)H(y) 换名规则 $z$y(F(z)(G(x,y)H(y) 辖域收缩扩张规则或 xF(x)$y(G(z,y)H(y) 代替规则 $x$y(F(x)(G(z,y)H(y) 推理定理第一组 命题逻辑推理定

5、理的代换实例 如, xF(x)$yG(y) xF(x) 第二组 基本等值式生成的推理定理 如, xF(x) xF(x), xF(x) xF(x) xF(x)$xF(x), $xF(x) xF(x) 第三组 其他常用推理定律 (1) xA(x)xB(x) x(A(x)B(x) (2) $x(A(x)B(x)$xA(x)$xB(x) (3) x(A(x)B(x) xA(x)xB(x) (4) $x(A(x)B(x) $xA(x)$xB(x) 一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。定义 设A为一个一阶逻辑公式，若A具有如下

6、形式 Q1x1Q2x2QkxkB 则称A为前束范式，其中Qi (1 i k)为或$，B为不含量词的公式. 例如， x(F(x)G(x) x$y(F(x)(G(y)H(x,y) 是前束范式而 $x(F(x)G(x) x(F(x)$y(G(y)H(x,y) 不是前束范式 注: 任何公式的前束范式都是存在的，但一般说来并不是唯一的。四条重要的推理规则 A.全称量词消去规则，简记为UI B.存在量词消去规则，简记为EI C.存在量词引入规则，简记为EG D.全称量词引入规则，简记为UG1. 全称量词消去规则UI 或含义：如果个体域的所有元素都具有性质A，则个体域中的任一元素具有性质A。 (1) x是A

7、(x)中自由出现的个体变项。(2) y为任意的不在A(x)约束出现的个体变项。(3) c为论域中任意的个体常项。例如 (1) x(F(x)G(x) 前提引入 (2) F(a)G(a) (1)UI 2. 全称量词引入规则UG(1) y在A(y)中自由出现，且y取何值A(y)均为真。(2) 取代y的x不能在A(y)中约束出现。例： y$xF(x,y) 个体域为实数集R,F(x,y):xy 设A(y)= $xF(x,y), y在A(x)中是自由出现的,满足条件(1). 若取x代替y 得 xA(x) x$xF(x,x)结论为“x$x(xx)”,是假命题。原因违背条件(2).2. 存在量词消去规则EI该

8、式成立的条件是：(1)c是使A为真的特定的个体常项。 (2)c不在A(x)中出现。 (3)若A(x)中除自由出现的x外，还有其它自由出现的个体变项，此规则不能使用。 4. 存在量词引入消去规则($+) 其中x,y是个体变项符号, c是个体常项符号, 且在A中y和c不在x和$x的辖域内自由出现.要特别注意使用-、+、$-、$+规则的条件.反例1. 对A=x$yF(x,y)使用-规则, 推得B=$yF(y,y). 取解释I: 个体域为R, 在I下A被解释为x$y(xy), 真; 而B被解释为$y(yy), 假 原因: 在A中x自由出现在$y的辖域F(x,y)内反例2. 前提: P(x)Q(x),

9、P(x) 结论: xQ(x) 取解释I: 个体域为Z, , 在I下前提为真, 结论为假, 从而推理不正确“证明”: P(x)Q(x) 前提引入 P(x) 前提引入 Q(x) 假言推理 xQ(x) +错误原因: 在使用+规则, 而x在前提的公式中自由出现.例19在自然推理系统NL 中构造下面推理的证明, 取个体域R: 任何自然数都是整数. 存在自然数. 所以, 存在整数.解 设F(x):x是自然数, G(x):x是整数.前提: x(F(x)G(x), $xF(x)结论: $xG(x)证明: x(F(x)G(x) 前提引入 F(x)G(x) - F(x)$xG(x) $+ $xF(x)$xG(x)

10、 $- $xF(x) 前提引入 $xG(x) 假言推理 例20在自然推理系统NL 中构造下面推理的证明, 取个体域R: 不存在能表示成分数的无理数. 有理数都能表示成分数. 所以, 有理数都不是无理数.解 设F(x):x是无理数, G(x):x是有理数, H(x):x能表示成分数.前提: $x(F(x)H(x), x(G(x)H(x)结论: x(G(x)F(x) 证明: $x(F(x)H(x) 前提引入 x(F(x)H(x) 置换 x(F(x)H(x) 置换 F(x)H(x) - x(G(x)H(x) 前提引入 G(x)H(x) - H(x)F(x) 置换 G(x)F(x) 假言三段论 x(G

11、(x)F(x) +笛卡儿积定义2 设A,B为集合，A与B的笛卡儿积记作AB，且 AB = | xAyB.例 20 A=1,2,3, B=a,b,c 求笛卡儿积AB,BA AB =, BA =, (1) 不适合交换律 AB BA (AB, A, B)(2) 不适合结合律 (AB)C A(BC) (A, B, C)(3) 对于并或交运算满足分配律 A(BC) = (AB)(AC) (BC)A = (BA)(CA) A(BC) = (AB)(AC) (BC)A = (BA)(CA) (4) 若 A 或 B 中有一个为空集，则 AB 就是空集. A = B = (5) 若 |A| = m, |B| =

12、 n, 则 |AB| = | B A | =mn 例 21 (1) 证明A=B,C=D AC=BD (2) AC = BD是否推出 A=B,C=D? 为什么？解 (1) 任取 AC xAyC xByD BD (2) 不一定.反例如下： A=1，B=2, C = D = , 则AC = BD但是A B.例22：设A， C， B， D为任意集合，判断以下命题是否为真，并说明理由。(1) AB= AC =B= C(2) A-(BC)=( A-B)(A-C)(3) 存在集合A,使得A A A.解：(1) 不一定为真。反例A= , B、C为任意不相 等的非空集合。(2) 不一定为真。反例A= 1, B=

13、2, C=3.(3) 为真。当 A= 时成立。 定义3 如果一个集合符合以下条件之一：(1) 集合非空，且它的元素都是有序对(2) 集合是空集则称该集合为一个二元关系，记作R，简称为关系。 对于二元关系R，若 R,可记作xRy;如果 R,则记作xRy。 例23：R1=,R2=5,6,7 aR1b, 1R12, 5R16 定义5 设 A 为集合, (1) 是A上的关系，称为空关系 (2) 全域关系 EA = | xAyA = AA 恒等关系 IA = | xA 小于等于关系 LA 整除关系 DB 包含关系 R 例如, A=1, 2, 则 EA = , IA = , 例如 A = 1, 2, 3,

14、 则 LA=, DA=,关系的定义域、值域与域分别定义为 domR = x | $y (R) ranR = y | $x (R) fldR = domR ranR 例 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 关系的表示: 关系图例24： 例 A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下： 设R是一个X到Y的关系， S是一个Y到Z的关系 , 则R与S的合成关系 ( 或复合关系 ) : R S 为： R S =| $z(xSzzRy 例 25 R = , , , S = , , , , RS = , , SR = , , ,

15、 利用图示（不是关系图）方法求合成 RS =, , SR =, , , 设 R 为A上的关系, R 的性质主要有以下 5 种(1) R 在 A 上是自反的：x(xAR) 该定义表明在自反的关系R中，除其他有序对外，必须包括有全部由每个xA所组成的元素相同的有序对。在关系矩阵中，反映为主对角线元素均为1； 在关系图中，反映为每结点都有自回路。例如：设A=1, 2, 3, R 是 A 上的关系， R=, , 则 R 是自反的全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA都是自反关系(2) R 在 A 上是反自反：x(x A R) 该定义表明了，一个反自反的关系R中，不应包括有任何

16、相同元素的有序对。在关系矩阵中，反映为主对角线元素均为0；在关系图中，反映为每结点都没有自回路。 例：设A=1,2,3， R=,， R 是 A 上的关系，R是反自反的。 再如实数集上的小于关系、幂集上的真包含关系也是反自反关系。 (3) 若xy( x,yARR), 则称 R 为 A上对称的关系.该定义表明在表示对称的关系R的有序对集合中，若有有序对，则必定还会有有序对。在关系矩阵中，反映为是对称矩阵；在关系图中，反映为若有a到b的边则必有b到a的边。 例如：设A=1,2,3,R是A上的关系， R=, , 则R 是对称的(4) 若xy( x,yARRx=y), 则称 R 为A上的反对称关系.在关

17、系矩阵中，反映为若aij=1,则aji=0 (注：若aij=0,不一定有aji=1) 在关系图上，反映为若存在a到b的边，则不存在b到a的边。例如：设A=1,2,3, R=, 是A上的关系，则 R是反对称的 (5)设R为A上的关系，若xyz(x,y,zARRR)则称R在A上是传递的关系。例如：设A=1,2,3，R1,R2,和R3是A上的关系，其中R1=, R2=, R3=说明R1， R2 和R3是否为A上的传递关系解：R1和R3是A上的传递关系，R2不是A上的传递关系集合例 26 判断下列命题是否为真 (1) （1） (2) （0） (3) (1) (4) （1） (5) a, b a, b,

18、 c, a, b, c （1） (6) a, b a, b, c, a, b (1) (7) a, b a, b, a, b (1) (8) a, b a, b, a,b (0)解 (1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.例 27 判断以下命题的真假，并说明理由. （1）A-B = A B= （2）A-(BC) = (A-B)(A-C) （3）AA = A （4）如果AB = B，则A = E. （5）A = xx，则 xA且x A. 解(1) B=是A-B=A的充分条件，但不是必要条件. 当B不空但是与A不交时也有A-B=A. (2) 这是DM律，命题为真.(3) 不符

19、合算律，反例如下： A=1，AA=，但是A.(4) 命题不为真. AB=B的充分必要条件是 BA，不是A=E. (5) 命题为真，因为 x 既是 A 的元素，也是 A 的子集 例 28设A,B为集合，试确定下列各式成立的充分必要条件：(1) A-B=B (2) A-B=B-A (3) AB=AB (4) AB=A解(1) A-B=B A=B=. 求解过程如下： 由A-B=B得 (AB)B = BB 化简得B=. 再将这个结果代入原来的等式得A= . 从而得到必要条件A=B=.再验证充分性. 如果A=B=成立，则A-B=B也成立.(2) A-B=B-A A=B. 求解过程如下：充分性是显然的，下面验证必要性. 由A-B=B-A得 (A-B)A=(B-A)A 从而有A=AB, 即AB. 同理可证BA.商集 定义 设 R 为非空集合A上的等价关系, 以 R 的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA实例 设 A=1,2,8，A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6A关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/EA = 1,2,8例28 .Aa, b