《习题（第二章一阶逻辑）ppt课件.ppt》由会员分享，可在线阅读，更多相关《习题（第二章一阶逻辑）ppt课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、2023/1/7,计算机科学与工程系,1,离散数学习题课（二）,主讲,姜虹,2023/1/7,计算机科学与工程系,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：3。F(a)F(b)。
2、,2023/1/7,计算机科学与工程系,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)）。真,2023/1/7,计算机科学与工程系,4,第二章 一阶逻辑（习题）,3、在一阶逻辑中将下列命题符号化，并讨论个体域为(a),(b)时命题的真值。1
3、）对任意的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)）。真,2023/1/7,计算机科学与工程系,5,第二章 一阶逻辑（习题）,4、在一阶逻辑中将下列命题符号化。1）在北京卖菜的人不全是外地人。2）乌鸦都是黑色的。3）有的人天天锻炼身体。,F(X):X是在北京卖菜的人，G(X)：X是外地人。（F(X)G(X)），（F(X)G(X)）,2）F(X)：X是乌鸦，G(X)：X是黑色的。（F
4、(X)G(X)），（F(X)G(X)）,3）F(X)：X是人，G(X)：X天天锻炼身体。（F(X)G(X)），（F(X)G(X)）,2023/1/7,计算机科学与工程系,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(X)G(Y)L(X,Y),4）G(X)：X是汽车。M（X，Y）：X比Y慢。(y（F(x)G(y)M(Y,X)。,3）
5、G(X)：X是汽车。（G(X)y(F(y)L(X,Y)。,2023/1/7,计算机科学与工程系,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）F（X，Y）：XY=YX，y F（X，Y）。真,3）F（X，Y）：Y=X+1，y F（X，Y）。真,2023/1/7,计算机科学与工程系,8,第二章 一阶逻辑（习题）
6、,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。真,2023/1/7,计算机科学与工程系,9,第二章 一阶逻辑（习题）,8、指出下列各公式中的指导变元，量词的辖域，各变元的自由出现和约束出现。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
7、(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。,2023/1/7,计算机科学与工程系,10,第二章 一阶逻辑（习题）,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(
8、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)。,2023/1/7,计算机科学与工程系,11,第二章 一阶逻辑（习题）,解：1）Y（xy)(x=y)。任意的实数X和Y，如果x小于y，则x不等于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。假,2023/1/7,计算机科学与工程系,12,第二章 一阶逻辑（习题）,
9、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)。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)。,2023/1/7,计算机科学与工程系,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)。
10、任意的自然数X和Y，都存在自然数z，使得x+y=z。真4）（x+x=xx)。存在自然数X和Y，使得x+x=xx。真,2023/1/7,计算机科学与工程系,14,第二章 一阶逻辑（习题）,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)。,2023/1/7,计算机科学与工程系,15,第二章 一阶逻辑（习题）,解：1）P(Q P)P Q P 1，用F(x,y)代替上式中的P，用代替上式中的Q，
11、得 F(x,y)(G(x,y)F(x,y)是永真的。2）因为 F(x)F(x)F(x)F(x)1，所以（F(x)F(x)1。因为y(G(y)G(y)0，所以（F(x)F(x)y(G(y)G(y)是永假式。,2023/1/7,计算机科学与工程系,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，使得
12、xy。假所以，yF(x,y)yF(x,y)为真。综上，yF(x,y)yF(x,y)为可满足的。,2023/1/7,计算机科学与工程系,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)是可满足的。,
13、2023/1/7,计算机科学与工程系,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)是可满足的。,2023/1/7,计算机科学与工程系,19,第二章 一阶逻辑（习题）,6）（PQ）Q（PQ）QPQQ 0，用F(x)和 y G(y)分别替换上式中的P，Q，可得（F(x)y G(y)）yG(y)是永假的。,2023/1/7,计算机科学与工程系,20,第二章
14、一阶逻辑（习题）,12、证明下列各式既不是永真的也不是永假的：1）（F(x)y(G(y)H(x,y)。2）y（F(x)G(y)H(x,y)。,2023/1/7,计算机科学与工程系,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。真综上，（F(x)y(G(y)H(x,y)既不是永真的也
15、不是永假的。,2023/1/7,计算机科学与工程系,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)既不是永真的也不是永假的。,2023/1/7,计算机科学与工程系,23,第二章 一阶逻辑（习题）,13、给出下列各式的一个成真解释和一个成假解释：1）（F(
16、x)G(x)。2）（F(x)G(x)H(x)。3）（F(x)y(G(y)H(x,y)。,2023/1/7,计算机科学与工程系,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。,2023/1/7,计算机科学与工程系,25,第二章 一阶逻辑（习题）,2）成真解释:D:N,F(x):X是偶数，G(x):X是素数，H(x):X整除所有偶数。（F(x)G(x)H(x)：存在自然数X，既是偶数，又是素
17、数，又能整除所有偶数。成假解释：D:N,F(x):X是偶数，G(x):X是素数，H(x):X是奇数。（F(x)G(x)H(x)：存在自然数X，既是偶数，又是素数，又是奇数。,2023/1/7,计算机科学与工程系,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。,2023/1/7,计算机科学与工程系,27,第二章 一阶逻辑（习题）,14、设个体域D=a,b,c，消去下列各式的量词：1）y（F(x)G(y)。2）y（F(x)G(y)。3）F(x)yG(y)
18、。4）(F(x)y G(y)。,2023/1/7,计算机科学与工程系,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)。,2023/1/7,计算机科学与工程系,29,第二章 一阶逻辑（习题）,15、设个体域D=1,2，请给出解释I1和I2，使得下面公式在I1下是真命题，在I2下是假命题：1）（F(x)G(x)
19、。2）(F(x)G(x)。,2023/1/7,计算机科学与工程系,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，既是偶数，又是奇数。2）(F(x)G(x)：对任意的X，如果X是偶数，则X是奇数。,2023/1/7,计算机科学与工程系,31,第二章 一阶逻辑（习题）,16、给定公式A=F(x)F(x)
20、，1）解释I1，D=a，证明A在I1下的真值为1。2）解释I2，D=a1,a2,an,n2,A在I2下的真值还一定是1吗？为什么？,2023/1/7,计算机科学与工程系,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)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
21、(4)(F(2)F(4)(1 1)(1 1)1。,2023/1/7,计算机科学与工程系,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(x,y)。2）xyF(x,y)。3）xy（F(x,y)F(f(x),f(y)。,2023/1/7,计算机科学与工程系,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
22、(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)(0 1)(1 0)0。,2023/1/7,计算机科学与工程系,35,第二章 一阶逻辑（习题）,3）xy（F(x,y)F(f(x),f(y)x(（F(x,3)F(f(x),f(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。,2023/1/7,计算机科学与工程系
23、,36,第二章 一阶逻辑（习题）,18、在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式。1）没有小于负数的正数。2）相等的两个角未必都是对顶角。,1）F(x)：X是正数，G(x)：X是负数，L(x,y)：xy。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)）。,2023/1/7,计算机科学与工程系,37,第二章 一阶逻辑（习题）,19、求下列各式的前束范式。1）xF(x)yG(x,y)。2）x（F(x,y)yG(x,y,z)。3）xF(x,y)xG(x,y)。,2023/1/7,计算机科学与工程系,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)。,
