习题(第二章一阶逻辑)080923演示教学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机科学与工程系,*,离散数学习题课（二）,主讲,姜虹,6/16/2025,1,计算机科学与工程系,第二章 一阶逻辑,（习题）,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(ab),F(a，c)。,F(X)：X是偶数。a：3。,F(a),F(X)：X是素数。a：2,，,b：3。,F(a),F(b)。,6/16/2025,2,计算机科学与工程系,第二章 一阶逻辑,（习题）,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是有理数,。,（,GX),F(X)）。真,6/16/2025,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)）。真,6/16/2025,4,计算机科学与工程系,第二章 一阶逻辑,（习题）,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(X),G(X)），,（,F(X),G(X)）,3）F(X)：X是,人,，,G(X)：X天天,锻炼身体。,（,F(X),G(X)），,（,F(X),G(X)）,6/16/2025,5,计算机科学与工程系,第二章 一阶逻辑,（习题）,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）G(X)：X是,汽车。,（,G(X,),y(,F(y),L(X,Y)。,6/16/2025,6,计算机科学与工程系,第二章 一阶逻辑,（习题）,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，,y,F（X，Y）。真,4）F（X，Y）：XY=YX，,y,F（X，Y）。真,3）F（X，Y）：Y=X+1，,y,F（X，Y）。真,6/16/2025,7,计算机科学与工程系,第二章 一阶逻辑,（习题）,7、将下列各公式翻译成自然,语言，个体域为整数集，并,判断各命题的真假。,1）,y,z(x-y=z)。,2）,y,(xy=1),。,3）,y,z(x+y=z),。,2）对任意的整数X，都存在整数Y，使得,xy=1。,假,3）存在整数X,对任意的整数Y和Z，都使得,x+y=z,。假,1）对任意的整数X和Y，都存在整数Z，使得,x-y=z,。真,6/16/2025,8,计算机科学与工程系,第二章 一阶逻辑,（习题）,8、指出下列各公式中的指导,变元，量词的辖域，各变元的,自由出现和约束出现。,1）,（,F(X),G(X,Y),。,2）,F,(X,Y),y,G(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。,6/16/2025,9,计算机科学与工程系,第二章 一阶逻辑,（习题）,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),。,6/16/2025,10,计算机科学与工程系,第二章 一阶逻辑,（习题）,解：,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-yy,y,F(,x,y,),:对任意的实数x,存在实数y，使得xy。真,yF(,x,y,),:存在实数x,对任意的实数y，使得xy。假,所以，,y,F(,x,y,),yF(,x,y,),为假。,D:N,F(,x,y,),:xy,y,F(,x,y,),:对任意的自然数x,存在自然数y，使得xy。假,yF(,x,y,),:存在自然数x,对任意的自然数y，使得xy。假,所以，,y,F(,x,y,),yF(,x,y,),为真。,综上，,y,F(,x,y,),yF(,x,y,),为可满足的。,6/16/2025,16,计算机科学与工程系,第二章 一阶逻辑,（习题）,4）,D:R,F(,x,y,),:xy,yF(,x,y,),:存在实数x,对任意的实数y，使得xy。假,yx,F(,x,y,),:对任意的实数y,存在实数x，使得xy。真,所以，,y,F(,x,y,),yx,F(,x,y,),为真。,D:N,F(,x,y,),:xy,yF(,x,y,),:存在自然数x,对任意的自然数y，使得,x y。真,yx,F(,x,y,),:对任意的自然数y,存在自然数x，使得,x y,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,),)是可满足的。,6/16/2025,18,计算机科学与工程系,第二章 一阶逻辑,（习题）,6）,（,P,Q,）,Q,（,P,Q）,Q,P,Q,Q 0，,用F,(,x),和,y,G,(,y)分别替换上式中的P，Q，可得,（,F,(,x),y,G,(,y),）,yG,(,y,)是永假的。,6/16/2025,19,计算机科学与工程系,第二章 一阶逻辑,（习题）,12、证明下列各式既不是永真的也不是永假的：,1）,（,F(,x,),y(G,(,y),H,(,x,y,),),。,2）,y（,F(,x,),G,(,y),H,(,x,y,)。,6/16/2025,20,计算机科学与工程系,第二章 一阶逻辑,习题）,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,),),既不是永真的,也不是永假的。,6/16/2025,21,计算机科学与工程系,第二章 一阶逻辑,（习题）,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,)既不是永真的,也不是永假的。,6/16/2025,22,计算机科学与工程系,第二章 一阶逻辑,（习题13、给出下列各式的一个成真解释和一个成假解释：,1）,（,F(,x,),G,(,x),),。,2）,（,F(,x,),G,(,x),H,(,x,)。,3）,（,F(,x,),y(G,(,y),H,(,x,y)。,6/16/2025,23,计算机科学与工程系,第二章 一阶逻辑,（习题）,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,。,6/16/2025,24,计算机科学与工程系,第二章 一阶逻辑,（习题）,2）,成真解释:,D:N,F(,x,):X是偶数，,G,(,x),:X是素数，,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，既是偶数，又,是,素数，又是奇数。,6/16/2025,25,计算机科学与工程系,第二章 一阶逻辑,（习题）,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。,（,F(,x,),y(G,(,y),H,(,x,y),：存在偶数X，对任意的奇,数y，使得,x y,。,6/16/2025,26,计算机科学与工程系,第二章 一阶逻辑,（习题）,14、设个体域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),。,6/16/2025,27,计算机科学与工程系,第二章 一阶逻辑,（习题）,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,),Gc,),),),。,6/16/2025,28,计算机科学与工程系,第二章 一阶逻辑,（习题）,15、设个体域D=1,2，请给出解释I1和I2，使,得下面公式在I1下是真命题，在I2下是假命题：,1）,（,F(,x,),G,(x,),),。,2）,(,F(,x,),G,(x,),。,6/16/2025,29,计算机科学与工程系,第二章 一阶逻辑,（习题）,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是奇数,。,6/16/2025,30,计算机科学与工程系,第二章 一阶逻辑,（习题）,16、给定公式A=,F(,x,),F(,x,)，,1）解释I1，D=a，证明A在I1下的真值为1。,2）解释I2，D=a1,a2,an,n2,A在I2下的真,值还一定是1吗？为什么？,6/16/2025,31,计算机科学与工程系,第二章 一阶逻辑,（习题）,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(4,),),(F(2,),F(4,),),(1,1,),(1,1),1。,6/16/2025,32,计算机科学与工程系,第二章 一阶逻辑,（习题）,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）,xy,F(,x,y,)。,2）,xy,F(,x,y,)。,3）,xy（,F(,x,y,),F(f(,x),f(y),)。,6/16/2025,33,计算机科学与工程系,第二章 一阶逻辑,（习题）,1）,xy,F(,x,y,),x,(,F(,x,3,),F(,x4,),(,F(,3,3,),F(,3,4,),(,F(,4,3,),F(,4,4,),(,0,1,),(,1,0,),1。,2）,xy,F(,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。,6/16/2025,34,计算机科学与工程系,第二章 一阶逻辑,（习题）,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),f3),),（,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。,6/16/2025,35,计算机科学与工程系,第二章 一阶逻辑,（习题）,18、在一阶逻辑中将下列命题符号化，要求用两种不,同的等值形式。,1）没有小于负数的正数。,2）相等的两个角未必都是对顶角。,1）,F(,x,)：X是正数，G,(,x,)：X是负数，L,(,xy,)：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,)）。,6/16/2025,36,计算机科学与工程系,第二章 一阶逻辑,（习题）,19、求下列各式的前束范式。,1）,x,F(,x,),y,G,(,x,y,)。,2）,x（,F(,x,y,),yG,(,x,y,z,)。,3）,x,F(,x,y,),xG,(,x,y,)。,6/16/2025,37,计算机科学与工程系,第二章 一阶逻辑,（习题）,1）,x,F(,x,),y,G,(,x,y,),x,F(,x,),y,G,(,u,y,),x,F(,x,),y,G,(,u,y,),x(,F(,x,),y,G,(,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,)。,6/16/2025,38,计算机科学与工程系,