离散数学习题五.doc

1、习题五1.设个体域 D=a,b,c，在 D 中消去公式 的量词。甲乙用了()()xFyG不同的演算过程：甲的演算过程如下： ()()()()()()(xFyGabcbcFacabGc乙的演算过程如下： ()()()()xyGabcabc显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。2. 设个体域 D=a,b,c，消去下列各式的量词：(1)()23(4),)()xyFGy（解：（1） )()()()( cGbacFba（2）（3） )()()()( cc（4） , GbayFbyaF在

2、（1） （2） （4）中均将量词的辖域缩小，所以演算结果都比较简单3. 设个体域 D=1,2，请给出两种不同的解释 和 ，使得下面公式在 下都1I21I是真命题，而在 下都是假命题。2I（1） ()()xFGx（2） 解：解释 I1 为：个体为实数集合 R，F(x) ：x 为自然数，G(x)：x 为整数。在 I1 下， （1）为自然数都是整数， （2）为存在整数为自然数。他们都是真命题解释 I2 为：个体域仍为实数集 R，F(x) ：x 是无理数，G(x)：x 能表示成分数，在 I2 下，（1）为无理数都能表示成分数， （2）为存在能表示成分数的无理数，他们都是假命题4. 给定公式 ()()A

3、xF（1）在解释 中，个体域 =a，证明公式 A 在 下的真值为 1.1I1D1I（2）在解释 中，个体域 = ， ,A 在 下的真值还一定是222,na 221 吗？为什么？解：（1）在 I1 下， 1)()()()( aFaFxFx（2）在 I2 下 )()()()( 2121 nnaxF 为可满足式，设 F(x)：x 为奇数， ，此时，蕴涵式前件为真，后件2,1,ii为假，故蕴含式为假，若令 F(x)；x 为整数，则蕴含式前后件均为真，所以（2）中公式在I2 下为可满足式5. 给定解释 如下：I（a）个体域 D=3,4；（b） 为()fx34,()3;ff（c） 为,Fy,0,(4)(,

4、3)1.FF试求下列公式在 下的真值。I(1)(,)23,(),xyFfxy解：（1） 1)4,()3,()4,3(),(,FFxxy（2）0)4,()3,()4,()3,(FFxx（3） 1 )4(,)4,()3,4()3,()4(,3)4,()3,(),( fFfFffxxx6.甲使用量词辖域收缩与扩张等值式进行如下演算 ),()(yxGxF乙说甲错了，乙说的对吗？为什么？解：乙说的对，甲错了，全称量词 的指导变元 x，辖域为 ，其中 F(x),()(yxGF与 G(x,y)都是 x 的约束变元，因而不能讲量词的辖域变小7.请指出下面等值运算的两处错误 ),()(,)yxHyGxFy解：演

5、算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词 ，演算的第二步，在原错的基础上又用错了等值式和 不等值),()(yxx ),()(yxxF8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1）没有小于负数的正数（2）相等的两个角未必都是对顶角解：（1） 其中 F(x)：x 小于负数，G(x)：x 是正)()()( xFGxxF数（2） ),(),()(),(),()( yxLHyFyLyHy 其中 F(x)：x 是角，H(x,y)：x=y，L(x,y) ：x 和 y 是对顶角9.设个体域 D 为实数集合，命题“有的实数既是有理数又是无理数” ，这显然是个假命题。可是某人却

6、说这是真命题，其理由如下设 F(x)：x 是有理数，G(x）：x 是无理数。 都是真命题，于)(,xGxF是， )()()(xGF由于 是真命题，故 也是真命题，即有的实数是)()(xGxF)(xGFx有理数，也是无理数这个人的结论对吗？为什么？解：存在量词对 无分配律10.在求前束范式时有人说 已是前束范式，理由是量词已在),()(yxx公式的前面，他说的对吗？为什么？解：在前束范式中，否定联结词不能在量词前面出现11.有人说无法求公式 ),()(yxGxF的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？换名规则可以使两个指导变元不相同12.求下列各式的前束范式：(1)

7、 ),()(yxGxF(2) ,z(3) ),()(yxyx(4) ),()(322211 xLxHGF(5) ,)(),( 12xx解：（1） ),()(yzFy（2） ,txGtx（3） ),(),(),(),( 43214321 yxFGy（4） 322LHxyFy（5） ),()()(112,121 yx13.将下列命题符号化，要求符号化的公式权威前束范式：（1）有点火车比有的汽车跑的快（2）有的火车比所有的汽车跑的快（3）说有的火车比所有汽车跑得快是不对的（4）说有的飞机比有的汽车慢也是不对的解：（1） 其中 F(x)：x 是汽车 G(y):y 是 火车 ),()(yxHGxFyH(

8、x,y)：x 比 y 跑得快（2） 其中 F(x)：x 是火车 G(y):y 是 汽车 ),()(yxHGFH(x,y)：x 比 y 跑得快（3) 其中 F(x)：x 是火车 G(y):y 是 汽车),()(H(x,y)：x 比 y 跑得快（4） 其中 F(x)：x 是飞机 G(y):y 是 汽车 ),()(yxHGFH(x,y)：x 比 y 跑得慢14.在自然推理系统 F 中，指出下面各证明序列中的错误：（1） 前提引入)()(x EI 规则cG（2） 前提引入)()(yxF EI 规则ba（3） 前提引入)(yG EG 规则xFx（4） 前提引入)(ba EG 规则xGx（5） 前提引入)

9、(cF UG 规则xx解：（1）对 不能使用 EI 规则，它不是前束范式，首先化成前)()(G束范式 ，因为量词辖域 中，除)(xyFxxF)(xGyF了 x 还有自由出现的 y 所以不能用 EI 规则（2）对 也应该先化成前束范式才能消去量词，其前束范)()(式为 ，要消去量词，既要用 UI 规则，又要用 EI 规则Gy（3）这里 A(y)=F(y) G(y)满足要求（4）这里，使 F(a)为真的 a 不一定使 G(a)为真，同样的，使 G(b)为真的b 不一定使 F(b)为真（5）这里，c 为个体常项，不能对 F(c) G(c)引入全称量词15.在自然推理系统 F 中，构造下面推理的证明：

10、（1）前提： )(),()()( xFyRGyx结论： R（2）前提： )(),()( xaxF结论： （3）前提： )(),(xGx结论： )F（4）前提： )(),(),( xRxxx 结论： )（1）证明：1 前提引入(xF2 前提引入)()(R(y)yG3 1 2 假言推理(4 1 EI)Fc5 3 UI(R(c)G6 4 附加)c7 5 6 假言推理(8 7EG)xR（2）证明：1 前提引入(F2 ),x()(aG,aIyH()xHF(x)(GaR(x)F前提引入3 1 EI(c)F4 2 UIGaR(c)5 3 4 假言推理G(a)Rc6 5 化简7 3 6 合取(c)F8 7EG

11、xR)（3）证明：1 前提引入(2 1 置换)F3 2UI(c4 前提引入x)(Gx5 4UIF(c6 3 5 析取三段论)7 6EG(x(4)证明：1 前提引入)FG2 1 UI(y3 前提引入x)()RX4 3 UIG(y5 前提引入)x6 5UI(R7 4 6 析取三段论)Gy8 27 析取三段论(F9 UGx)16.找一个解释 I，在 I 下，使得 为真，而使得()()xFGx为假，从而说明 。()()xFGx()()FxG解：取个体域为自然数集合 N，F(x):x 为奇数，G(x):x 为偶数。显然在以上解释下为真而 为假。xF()G(x)(Fx)G()17.给定推理如下：前提： (

12、)(),()Hx结论： 。xHFx有些人给出的证明如下：证明： 附加前提引入()x UIHy 前提引入()()xGx UIy 假言推理() 前提引入()xFGx UI()y 拒取式 UG()xF并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。解：根据 16 题可知两公式并不等价。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法） 。证明：1 前提引入x(F)G(x)2 前提引入H3 1 UI(y)()4 2UIG5 3 置换()()yF6 4 5 假言三段论H7 6 UG(x)()19.在自然推理系统 F 中，构造下列推理的证明：前提： ()()xGx结论：证明

13、：1 前提引入()()xF2 换名规则xy3 化简()()xG4 3 EIF20.在自然推理系统 F 中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提： ()()xGx结论：（2）前提： ()(xFx结论： )G证明：（1）. 1 附加前提引入(x2 1 UI)Fy3 前提引入()xx4 3UI)yG5 2 3 假言推理(6 )x（2）1 附加前提引入(F2 置换原则)x3 2EI(c4 前提引入)(xFGx5 UI()FcG6 3 5 析取三段论7 EG()x21.在自然推理系统中，构造下面推理的证明：没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。设 F(x):x 是乌鸦，G(x) ：x 是北京鸭， H(x):x 是白色的。前提 (F)H(,G()x)结论 x证明：1 前提引入()(x2 置换原则FH3 置换原则x()()4 x5 4UI(y)()HF6 前提引入Gx7 5UI()8 5 7 假言三段论y()F9 8UGGx22.在自然推理系统 F 中，构造下面推理的证明：(1)偶数都能被 2 整除。6 是偶数。所以 6 能被 2 整除。(2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。（1）设 F(x):x 为偶数，G(x)：x 能被 2 整除前提 ()G(),结论 G(6)证明：1 前提引入(x)()F2 1UI63 前提引入()