《（推荐）习题(第二章一阶逻辑).ppt》由会员分享，可在线阅读，更多相关《（推荐）习题(第二章一阶逻辑).ppt（38页珍藏版）》请在三一文库上搜索。
1、06.05.2021,1,离散数学习题课（二）,主讲,姜虹,06.05.2021,2,第二章 一阶逻辑（习题）,1、将下列命题用0元谓词符号化： 1）小王学过英语和法语。 2）除非李健是东北人， 否则他一定怕冷。 3）2大于3仅当2大于4。 4）3不是偶数。 5）2或3是素数。,F(X) ：小王学过X。 a：英语， b：法语。 F(a) F(b) 。,F(X) ：X是东北人。 G(X) ：X一定怕冷。a：李健。 F(a) G(a ) 。,F(X，Y)：XY。 a：2，b：3， c：4。 F(a，b) F(a，c)。,F(X) ：X是偶数。 a：3。 F(a),F(X) ：X是素数。 a：2，b
2、：3 。 F(a) F(b)。,06.05.2021,3,第二章 一阶逻辑（习题）,2、在一阶逻辑中将下列命题 符号化，并讨论个体域为(a), (b)时命题的真值。 1）凡有理数都能被2整除。 2）有的有理数都能被2整除。 其中， (a)个体域为有理数集合。 (b)个体域为实数集合。,1-a）F(X) ：X能被2整除。 ()。假,1-b）G(X) ：X是有理数。 （G(X) F(X)）。假,2-a）F(X) ：X能被2整除。 ()。真,2-b）G(X) ：X是有理数。 （G(X) F(X)）。真,06.05.2021,4,第二章 一阶逻辑（习题）,3、在一阶逻辑中将下列命题 符号化，并讨论个体
3、域为(a), (b)时命题的真值。 1）对任意的x，均有 。 2）存在x，使得x+5=9。 其中， (a)个体域为自然数集合。 (b)个体域为实数集合。,1-a）F(X) ： ()。真,1-b）G(X) ：X是自然数。 （G(X) F(X)）。真,2-a）F(X) ： ()。真,2-b）G(X) ：X是自然数。 （G(X) F(X)）。真,06.05.2021,5,第二章 一阶逻辑（习题）,4、在一阶逻辑中将下列命题 符号化。 1）在北京卖菜的人不全是外 地人。 2）乌鸦都是黑色的。 3）有的人天天锻炼身体 。,F(X):X是在北京卖菜的人， G(X) ：X是外地人。 （F(X) G(X)），
4、 （F(X) G(X)）,2）F(X)：X是乌鸦， G(X) ：X是黑色的。 （F(X) G(X)）， （F(X) G(X)）,3）F(X)：X是人， G(X) ：X天天锻炼身体 。 （F(X) G(X)）， （F(X) G(X)）,06.05.2021,6,第二章 一阶逻辑（习题）,5、在一阶逻辑中将下列命题 符号化。 1）火车都比轮船快。 2）有的火车比有的轮船快。 3）不存在比所有火车都快的 汽车 。 4）凡是汽车就比火车慢是不对的。,1）F(X):X是火车， G(X) ：X是轮船人， L（X，Y）：X比Y快。 y（F(X) G(Y) L(X,Y)。,2）G(X) ：X是汽车。 y（ F
5、(X) G(Y) L(X,Y),4）G(X) ：X是汽车。 M（X，Y）：X比Y慢。 (y（ F(x) G(y) M(Y, X)。,3）G(X) ：X是汽车。 （ G(X ) y( F(y) L(X,Y)。,06.05.2021,7,第二章 一阶逻辑（习题）,6、将下列命题符号化，个体域 为R，并指出其真值。 1）对所有的X，都存在Y，使得 XY=0。 2）存在着X，对所有的Y，都有 XY=0。 3）对所有的X，都存在Y，使得 Y = X +1。 4）对所有的X， Y都有XY= YX。,1）F（X，Y）： XY=0， y F（X，Y）。真,2）F（X，Y）： XY=0， yF（X，Y）。真,4
6、）F（X，Y）： XY = YX ， y F（X，Y）。真,3）F（X，Y）： Y = X +1 ， y F（X，Y）。真,06.05.2021,8,第二章 一阶逻辑（习题）,7、将下列各公式翻译成自然 语言，个体域为整数集，并 判断各命题的真假。 1） yz(x-y=z)。 2） y(xy=1) 。 3） yz(x+y=z) 。,2）对任意的整数X，都存在整数Y，使得xy=1。 假,3）存在整数X,对任意的整数Y和Z，都使得x+y=z 。假,1）对任意的整数X和Y，都存在整数Z，使得 x-y=z 。真,06.05.2021,9,第二章 一阶逻辑（习题）,8、指出下列各公式中的指导 变元，量词
7、的辖域，各变元的 自由出现和约束出现。 1） （F(X) G(X,Y) 。 2） F(X,Y) yG(X,Y) 。 3） y(F(X,Y) G(Y,Z) X H(X,Y,Z) 。,2）指导变元:X,Y， 辖域: （）：F(X,Y), （ y ）：G(X,Y)， 自由出现:X，Y, 约束出现:X，Y。,3）指导变元:X，Y，Z， 辖域: （）：F(X,Y)G(Y,Z) （ y ）： F(X,Y)G(Y,Z) （X）： H(X,Y,Z) 自由出现:Y，Z 约束出现:X，Y。,1）指导变元:X, 辖域: F(X) G(X,Y), 自由出现:Y,约束出现:X。,06.05.2021,10,第二章 一阶
8、逻辑（习题）,9、给定解释I如下： a） 个体域D为实数集合R 。 b） D中特定元素a=0 。 c） 特定函数f(x,y)=x-y。 d） 特定谓词F(x,y)：x=y，G(x,y)：xy。 说明下列公式在I下的含义，并指出各公式的真值。 1） Y（G(X,Y) F(X，Y) ) 。 2） Y（F(f(x,y) , a ) G(X,Y) 。 3） y(G(X,Y) F (f(x,y) , a ) 4） Y（G(f(x,y) , a ) F(X,Y) 。,06.05.2021,11,第二章 一阶逻辑（习题）,解： 1） Y（xy) (x=y) ) 。 任意的实数X和Y，如果x小于y，则x不等于
9、y。真 2） Y（x-y=0) (xy) 。 任意的实数X和Y，如果x-y=0 ，则xy 。假 3） y(xy) (x-y=0)。 任意的实数X和Y，如果x小于y，则x-y不等于0。真 4） Y（(x-y0)(x=y) 。 任意的实数X和Y，如果x-y小于0，则x等于y。假,06.05.2021,12,第二章 一阶逻辑（习题）,10、给定解释I如下： a） 个体域D为自然数集合N 。 b） D中特定元素a=2 。 c） 特定函数f(x,y)=x+y， g(x,y)=xy 。 d） 特定谓词F(x,y)：x=y。 说明下列公式在I下的含义，并指出各公式的真值。 1） F(g(x,a) ，x) )
10、 。 2） Y（F(f(x,a) , y ) F(f(y,a) , x ) 。 3） y z F(f(x,y) , z ) 。 4） F(f(x,x) , g(x,x) ) 。,06.05.2021,13,第二章 一阶逻辑（习题）,解： 1） （x2=x ) 。 任意的自然数X，都有x2=x 。假 2） Y（x+2=y) (y+2=x) 。 任意的自然数X和Y，如果x+2=y ，则y+2=x 。假 3） yz(x+y=z) 。 任意的自然数X和Y，都存在自然数z，使得x+y=z 。真 4） （x+x= xx) 。 存在自然数X和Y，使得x+x= xx。真,06.05.2021,14,第二章 一
11、阶逻辑（习题）,11、判断下列各式的类型： 1） F(x,y) (G(x,y) F(x,y) )。 2） （F(x) F(x) y(G(y)G(y) 。 3） yF(x,y) yF(x,y) 。 4） yF(x,y) yxF(x,y)。 5） y(F(x,y) F(y,x) )。 6） （F(x) y G(y) ） yG(y)。,06.05.2021,15,第二章 一阶逻辑（习题）,解： 1） P (Q P) P Q P 1 ， 用F(x,y) 代替上式中的P，用代替上式中的Q，得 F(x,y) (G(x,y) F(x,y) ) 是永真的。 2）因为 F(x) F(x) F(x) F(x) 1
12、 ， 所以（F(x) F(x) 1 。 因为y(G(y)G(y) 0， 所以（F(x) F(x) y(G(y)G(y) 是永假式。,06.05.2021,16,第二章 一阶逻辑（习题）,3） D:R,F(x,y) :xy, yF(x,y) :对任意的实数x,存在实数y，使得xy。真 yF(x,y) :存在实数x,对任意的实数y，使得xy。假 所以， yF(x,y) yF(x,y) 为假。 D:N,F(x,y) :xy, yF(x,y) :对任意的自然数x,存在自然数y，使得xy。假 yF(x,y) :存在自然数x,对任意的自然数y，使得xy。假 所以， yF(x,y) yF(x,y) 为真。
13、综上， yF(x,y) yF(x,y) 为可满足的。,06.05.2021,17,第二章 一阶逻辑（习题）,4） D:R,F(x,y) :xy, yF(x,y) :存在实数x,对任意的实数y，使得xy。假 yxF(x,y) :对任意的实数y,存在实数x，使得xy。真 所以， yF(x,y) yxF(x,y) 为真。 D:N,F(x,y) :xy, yF(x,y) :存在自然数x,对任意的自然数y，使得 x y。真 yxF(x,y) :对任意的自然数y,存在自然数x，使得 x y。假 所以， yF(x,y) yxF(x,y) 为假。 综上， yF(x,y) yxF(x,y)是可满足的。,06.0
14、5.2021,18,第二章 一阶逻辑（习题）,5） D:R,F(x,y) :xy, y(F(x,y) F(y,x) ):对任意的实数x和 y，如果 xy ，则yx。假 D:R,F(x,y) :x+y=2, y(F(x,y) F(y,x) ):对任意的实数x和 y，如果 x+y=2 ，则 y + x=2 。真 综上，y(F(x,y) F(y,x) )是可满足的。,06.05.2021,19,第二章 一阶逻辑（习题）,6）（PQ）Q（PQ）QPQQ 0， 用F(x) 和 y G(y)分别替换上式中的P，Q，可得 （F(x) y G(y) ） yG(y)是永假的。,06.05.2021,20,第二章
15、 一阶逻辑（习题）,12、证明下列各式既不是永真的也不是永假的： 1） （F(x) y(G(y)H(x,y) )。 2） y（F(x) G(y) H(x,y)。,06.05.2021,21,第二章 一阶逻辑（习题）,1） D:N,F(x) :x是偶数, G(x) :x是奇数, H(x,y)：xy。 （F(x) y(G(y)H(x,y) ):对任意的自然数x，如 果x是偶数，则存在奇数 y，使得xy。假 D:N,F(x) :x是偶数, G(x) :x是奇数, H(x,y)：xy。 （F(x) y(G(y)H(x,y) ):对任意的自然数x，如 果x是偶数，则存在奇数 y，使得x y。真 综上，
16、（F(x) y(G(y)H(x,y) )既不是永真的 也不是永假的。,06.05.2021,22,第二章 一阶逻辑（习题）,2） D:N,F(x) :x是偶数, G(x) :x是奇数, H(x,y)：xy。 y（F(x) G(y) H(x,y):对任意的自然数x和y ， 如果x是偶数， y是奇数，则xy。假 D:N,F(x) :x是偶数, G(x) :x是奇数, H(x,y)：xy。 y（F(x) G(y) H(x,y):对任意的自然数x和y ， 如果x是偶数， y是奇数，则x y。真 综上， y（F(x) G(y) H(x,y)既不是永真的 也不是永假的。,06.05.2021,23,第二章
17、 一阶逻辑（习题）,13、给出下列各式的一个成真解释和一个成假解释： 1） （F(x) G(x)。 2） （F(x) G(x) H(x)。 3） （F(x) y(G(y) H(x,y)。,06.05.2021,24,第二章 一阶逻辑（习题）,1）成真解释:D:N, F(x):X是偶数，G(x) :X是奇数， （F(x) G(x)：任意的自然数X，或是偶数， 或是奇数。 成假解释：D:N, F(x):X是3，G(x) :X是4， （F(x) G(x)：任意的自然数X，或是3，或是4。,06.05.2021,25,第二章 一阶逻辑（习题）,2）成真解释:D:N, F(x):X是偶数，G(x) :X
18、是素数， H(x) :X 整除所有偶数。 （F(x) G(x) H(x)：存在自然数X，既是偶数，又是 素数，又能整除所有偶数。 成假解释：D:N, F(x):X是偶数，G(x) :X是素数，H(x) :X 是奇数。 （F(x) G(x) H(x)：存在自然数X，既是偶数，又是 素数，又是奇数。,06.05.2021,26,第二章 一阶逻辑（习题）,3）成真解释:D:N, F(x):X是偶数，G(x) :X是奇数， H(x，y) :x y。 （F(x) y(G(y) H(x,y)：存在偶数X，对任意的奇 数y，使得x y 。,06.05.2021,27,第二章 一阶逻辑（习题）,14、设个体域
19、D=a,b,c，消去下列各式的量词： 1） y（F(x) G(y)。 2） y（F(x) G( y)。 3 ） F(x) yG(y)。 4 ） (F(x) y G(y)。,06.05.2021,28,第二章 一阶逻辑（习题）,14、设个体域D=a,b,c，消去下列各式的量词： 1） y（F(x) G(y) (（F(x)G(a)(（F(x)G(b) （F(x) G(c) ) (（F(a)G(a)(（F(a)G(b) （F(a) G(c) (（F(b)G(a)(（F(b)G(b) （F(b) G(c) ) (（F(c)G(a)(（F(c)G(b) （F(c) G(c) ) 。,06.05.2021
20、,29,第二章 一阶逻辑（习题）,15、设个体域D=1,2，请给出解释I1和I2，使 得下面公式在I1下是真命题，在I2下是假命题： 1） （F(x) G(x)。 2） (F(x) G(x)。,06.05.2021,30,第二章 一阶逻辑（习题）,15、 I1:D=1,2， F(x):X是有理数，G(x)：X是实数； I2:D=1,2， F(x):X是偶数，G(x)：X是奇数 。 在I1下，为真命题： 1） （F(x) G(x)：存在X，既是有理数，又是实数。 2） (F(x) G(x)：对任意的X，如果X是有理数，则 X是实数。 在I2下，为假命题： 1） （F(x) G(x)：存在X，既是
21、偶数，又是奇数。 2） (F(x) G(x)：对任意的X，如果X是偶数，则 X是奇数。,06.05.2021,31,第二章 一阶逻辑（习题）,16、给定公式A= F(x) F(x)， 1）解释I1，D=a，证明A在I1下的真值为1。 2）解释I2，D=a1,a2,an,n2,A在I2下的真 值还一定是1吗？为什么？,06.05.2021,32,第二章 一阶逻辑（习题）,1）解释I1，D=a， A= F(x) F(x) F(a) F(a) 1 ， 2）解释I2，D=a1,a2,an,n2, A= F(x) F(x) (F(1) F(2) F(an) ) (F(a1) F(a2) F(an) )
22、A在I2下的真值不一定 是1。如：D =1,2， F(x) ：X是偶数。 A= F(x) F(x) (F(1) F(2) ) (F(1) F(2) (0 1 ) (0 1) 0。 又如：D =2，4， F(x) ：X是偶数。 A= F(x) F(x) (F(2) F(4) ) (F(2) F(4) (1 1 ) (1 1) 1。,06.05.2021,33,第二章 一阶逻辑（习题）,17、给定解释I如下： a) 个体域D=3，4， b) f(3)=4,f(4)=3, c ) F(3,3) =F(4,4) =0, F(3,4) = F(4,3) = 1， 求下列公式在I下的真值。 1） xyF(
23、x,y)。 2） xyF(x,y)。 3） xy（F(x,y) F(f(x),f(y) 。,06.05.2021,34,第二章 一阶逻辑（习题）,1）xyF(x,y) x (F(x,3) F(x,4) (F(3,3) F(3,4) (F(4,3) F(4,4) (0 1) (1 0) 1。 2）xyF(x,y) x(F(x,3) F(x,4) ) (F(3,3) F(3,4) ) (F(4,3) F(4,4) ) ) (0 1 ) (1 0 ) ) 0。,06.05.2021,35,第二章 一阶逻辑（习题）,3） xy（F(x,y) F(f(x),f(y) x(（F(x,3) F(f(x),f
24、(3) （F(x,4) F(f(x),f(4) (（F(3,3) F(f(3),f(3) （F(3,4) F(f(3),f(4) (（F(4,3) F(f(4),f(3) （F(4,4) F(f(4),f(4) (（0 F(4,4) （1 F(4,3) (（1 F(3,4) （0 F(3,3) (（0 0) （1 1) (（1 1) （0 0) 1。,06.05.2021,36,第二章 一阶逻辑（习题）,18、在一阶逻辑中将下列命题符号化，要求用两种不 同的等值形式。 1） 没有小于负数的正数。 2）相等的两个角未必都是对顶角。,1）F(x)：X是正数， G(x)：X是负数，L (x,y)：x
25、y。 x（F(x) G(y) L (x,y) x（F(x) G(y) L (x,y) 。 2）F(x,y)： x=y ， G(x,y)： x,y是对顶角。 xy（F(x,y) G(x,y)） xy （F(x,y) G(x,y)）。,06.05.2021,37,第二章 一阶逻辑（习题）,19、求下列各式的前束范式。 1） xF(x) yG(x,y) 。 2） x（F(x,y) yG(x,y,z)。 3） xF(x,y) xG(x,y) 。,06.05.2021,38,第二章 一阶逻辑（习题）,1） xF(x) yG(x,y) xF(x) yG(u,y) xF(x) yG(u,y) x(F(x) yG(u,y) x y(F(x) G(u,y) xy(F(x) G(u,y) 。 2）x（F(x,y) yG(x,y,z) x（ F(x,u) yG(x,y,z) x y（ F(x,u) yG(x,y,z) x y（F(x,u) yG(x,y,z) 。,