离散数学例题2

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, 则消去下面公式中的量词$x"yF(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,

2、b，消去下面各公式中的量词： (1) xy(F(x) ®G(y) Û x(F(x) ®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)中量词辖域可以缩小，先缩小量词

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

4、(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(

5、M(x)ÙF(x)解 Ø$x(M(x)ÙF(x) Û "x(ØM(x)ÚØF(x) （量词否定等值式） Û "x(M(x)®ØF(x) 后两步结果都是前束范式，说明公式的前束范式不惟一.(2) "xF(x)ÙØ$xG(x)解 "xF(x)ÙØ$xG(x) Û "xF(x)Ù"xØG(x) （量词否定等值式） Û "x(F(x)ÙØ

6、;G(x) （量词分配等值式）或 "xF(x)ÙØ$xG(x) Û "xF(x)Ù"xØG(x) 量词否定等值式 Û "xF(x)Ù"yØG(y) 换名规则 Û "x"y(F(x)ÙØG(y) 辖域收缩扩张规则(3) "xF(x)®$y(G(x,y)ÙØH(y)解 "xF(x)®$y(G(x,y)ÙØH(y) Û "z

7、F(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) 推理定理第一组 命题逻辑推理定理的代换实例 如, "xF(x)Ù$yG(y) Þ "xF(x) 第二组 基本等值式生成的推理定理 如, "xF(x) &#

8、222;ØØ"xF(x), ØØ"xF(x) Þ"xF(x) Ø"xF(x)Þ$xØF(x), $xØF(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) Þ

9、; "xA(x)®"xB(x) (4) $x(A(x)®B(x) Þ $xA(x)®$xB(x) 一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。定义 设A为一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2QkxkB 则称A为前束范式，其中Qi (1£ i £k)为"或$，B为不含量词的公式. 例如， "xØ(F(x)ÙG(x) "x$y(F(x)®(G(y)ÙH(x,y)

10、是前束范式而 Ø$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(x)中自由出现的个体变项。(2) y为任意的不在A(x)约束出现的个体变项。(3) c为论域中任意的个体常项。例如

11、 (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(x>x)”,是假命题。原因违背条件(2).2. 存在量词消去规则EI该式成立的条件是： (1)c

12、是使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(x>y), 真; 而B被解释为$y(y>y), 假 原因: 在A中x自由出现

13、在$y的辖域F(x,y)内反例2. 前提: P(x)®Q(x), 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)®

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

15、174;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(x)®ØF

16、(x) "+笛卡儿积定义2 设A,B为集合，A与B的笛卡儿积记作A´B，且 A´B = <x,y>| xÎAÙyÎB.例 20 A=1,2,3, B=a,b,c 求笛卡儿积A´B,B´A A´B =<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c> B´A =<a,1>,<b,1>,<c,1&

17、gt;,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3> (1) 不适合交换律 A´B ¹ B´A (A¹B, A¹Æ, B¹Æ)(2) 不适合结合律 (A´B)´C ¹ A´(B´C) (A¹Æ, B¹Æ, C¹Æ)(3) 对于并或交运算满足分配律 A´(BÈC) = (A´B)&#

18、200;(A´C) (BÈC)´A = (B´A)È(C´A) A´(BÇC) = (A´B)Ç(A´C) (BÇC)´A = (B´A)Ç(C´A) (4) 若 A 或 B 中有一个为空集，则 A´B 就是空集. A´Æ = Æ´B = Æ (5) 若 |A| = m, |B| = n, 则 |A´B| = | B ´ A | =mn 例 21 (1) 证

19、明A=B,C=D Þ A´C=B´D (2) A´C = B´D是否推出 A=B,C=D? 为什么？解 (1) 任取<x,y> <x,y>ÎA´C Û xÎAÙyÎC Û xÎBÙyÎD Û <x,y>ÎB´D (2) 不一定.反例如下： A=1，B=2, C = D = Æ, 则A´C = B´D但是A ¹ B.例22：设A， C， B，

20、D为任意集合，判断以下命题是否为真，并说明理由。(1) A×B= A×C =>B= C(2) A-(B×C)=( A-B)×(A-C)(3) 存在集合A,使得A Í A × A.解：(1) 不一定为真。反例A= , B、C为任意不相 等的非空集合。(2) 不一定为真。反例A= 1, B=2, C=3.(3) 为真。当 A= 时成立。 定义3 如果一个集合符合以下条件之一：(1) 集合非空，且它的元素都是有序对(2) 集合是空集则称该集合为一个二元关系，记作R，简称为关系。 对于二元关系R，若<x,y> R,可记作xR

21、y;如果<x,y> ÏR,则记作xRy。 例23：R1=<1,2>,<a,b>,R2=5,6,7 aR1b, 1R12, 5R16 定义5 设 A 为集合, (1) Æ是A上的关系，称为空关系 (2) 全域关系 EA = <x,y>| xAyA = A×A 恒等关系 IA = <x,x>| xA 小于等于关系 LA 整除关系 DB 包含关系 RÍ 例如, A=1, 2, 则 EA = <1,1>,<1,2>,<2,1>,<2,2> IA = <

22、;1,1>,<2,2> 例如 A = 1, 2, 3, 则 LA=<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3> DA=<1,1>,<1,2>,<1,3>,<2,2>,<3,3>关系的定义域、值域与域分别定义为 domR = x | $y (<x,y>ÎR) ranR = y | $x (<x,y>ÎR) fldR = domR È ranR 例 R=<1,2&g

23、t;,<1,3>,<2,4>,<4,3>, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 关系的表示: 关系图例24： 例 A=1,2,3,4, R=<1,1>,<1,2>,<2,3>,<2,4>,<4,2>, R的关系矩阵MR和关系图GR如下： 设R是一个X到Y的关系， S是一个Y到Z的关系 , 则R与S的合成关系 ( 或复合关系 ) : R ° S 为： R ° S =<x,y>| $z(xSzzRy 例 25 R = &

24、lt;1,2>, <2,3>, <1,4>, <2,2> S = <1,1>, <1,3>, <2,3>, <3,2>, <3,3> R°S = <1,3>, <2,2>, <2,3> S°R = <1,2>, <1,4>, <3,2>, <3,3>利用图示（不是关系图）方法求合成 R°S =<1,3>, <2,2>, <2,3> S°

25、R =<1,2>, <1,4>, <3,2>, <3,3>设 R 为A上的关系, R 的性质主要有以下 5 种(1) R 在 A 上是自反的："x(xA<x,x>ÎR) 该定义表明在自反的关系R中，除其他有序对外，必须包括有全部由每个xÎA所组成的元素相同的有序对。在关系矩阵中，反映为主对角线元素均为1； 在关系图中，反映为每结点都有自回路。例如：设A=1, 2, 3, R 是 A 上的关系， R=<1,1>,<2,2>, <3,3>, <1,2> 则 R

26、是自反的全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA都是自反关系(2) R 在 A 上是反自反："x(x A ®<x,x> R) 该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。在关系矩阵中，反映为主对角线元素均为0；在关系图中，反映为每结点都没有自回路。 例：设A=1,2,3， R=<2,3>,<3,2>， R 是 A 上的关系，R是反自反的。 再如实数集上的小于关系、幂集上的真包含关系也是反自反关系。 (3) 若"x"y( x,yA<x,y>R<y,x>

27、;R), 则称 R 为 A上对称的关系.该定义表明在表示对称的关系R的有序对集合中，若有有序对<x, y>，则必定还会有有序对<y, x>。在关系矩阵中，反映为是对称矩阵；在关系图中，反映为若有a到b的边则必有b到a的边。 例如：设A=1,2,3,R是A上的关系， R=<1,2>,<2,1> ,<3,3> 则R 是对称的(4) 若"x"y( x,yA<x,y>R<y,x>Rx=y), 则称 R 为A上的反对称关系.在关系矩阵中，反映为若aij=1,则aji=0 (注：若aij=0,不一定有a

28、ji=1) 在关系图上，反映为若存在a到b的边，则不存在b到a的边。例如：设A=1,2,3, R=<1,2>,<1,3> 是A上的关系，则 R是反对称的 (5)设R为A上的关系，若"x"y"z(x,y,zA<x,y>R<y,z>R®<x,z>R)则称R在A上是传递的关系。例如：设A=1,2,3，R1,R2,和R3是A上的关系，其中R1=<1,1>,<2,2> R2=<1,2>,<2,3> R3=<1,3>说明R1， R2 和R3是否为A

29、上的传递关系解：R1和R3是A上的传递关系，R2不是A上的传递关系集合例 26 判断下列命题是否为真 (1) ÆÍÆ （1） (2) ÆÎÆ （0） (3) ÆÍÆ (1) (4) ÆÎÆ （1） (5) a, b Í a, b, 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)、

30、(4)、(5)、(6)、(7)为真，其余为假.例 27 判断以下命题的真假，并说明理由. （1）A-B = A Û B=Æ （2）A-(BÈC) = (A-B)Ç(A-C) （3）AÅA = A （4）如果AÇB = B，则A = E. （5）A = xÈx，则 xÎA且x Í A. 解(1) B=Æ是A-B=A的充分条件，但不是必要条件. 当B不空但是与A不交时也有A-B=A. (2) 这是DM律，命题为真.(3) 不符合算律，反例如下： A=1，AÅA=Æ，但是A

31、5;Æ.(4) 命题不为真. AÇB=B的充分必要条件是 BÍA，不是A=E. (5) 命题为真，因为 x 既是 A 的元素，也是 A 的子集 例 28设A,B为集合，试确定下列各式成立的充分必要条件：(1) A-B=B (2) A-B=B-A (3) AÇB=AÈB (4) AÅB=A解(1) A-B=B Û A=B=Æ. 求解过程如下： 由A-B=B得 (AÇB)ÇB = BÇB 化简得B=Æ. 再将这个结果代入原来的等式得A= Æ. 从而得到必要条件A=B=Æ.再验证充分性. 如果A=B=