习题(第二章一阶逻辑)080923PPT课件

08.05.2020,.,1,离散数学习题课（二）,主讲,姜虹,08.05.2020,.,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)。,08.05.2020,.,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)）。真,08.05.2020,.,4,第二章一阶逻辑（习题）,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)）。真,08.05.2020,.,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(X)G(X)），（F(X)G(X)）,3）F(X)：X是人，G(X)：X天天锻炼身体。（F(X)G(X)），（F(X)G(X)）,08.05.2020,.,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）G(X)：X是汽车。（G(X)y(F(y)L(X,Y)。,08.05.2020,.,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，yF（X，Y）。真,2）F（X，Y）：XY=0，yF（X，Y）。真,4）F（X，Y）：XY=YX，yF（X，Y）。真,3）F（X，Y）：Y=X+1，yF（X，Y）。真,08.05.2020,.,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。真,08.05.2020,.,9,第二章一阶逻辑（习题）,8、指出下列各公式中的指导变元，量词的辖域，各变元的自由出现和约束出现。1）（F(X)G(X,Y)。2）F(X,Y)yG(X,Y)。3）y(F(X,Y)G(Y,Z)XH(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。,08.05.2020,.,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(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)。,08.05.2020,.,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。真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)为真。综上，yF(x,y)yF(x,y)为可满足的。,08.05.2020,.,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，使得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)是可满足的。,08.05.2020,.,19,第二章一阶逻辑（习题）,6）（PQ）Q（PQ）QPQQ0，用F(x)和yG(y)分别替换上式中的P，Q，可得（F(x)yG(y)）yG(y)是永假的。,08.05.2020,.,20,第二章一阶逻辑（习题）,12、证明下列各式既不是永真的也不是永假的：1）（F(x)y(G(y)H(x,y)。2）y（F(x)G(y)H(x,y)。,08.05.2020,.,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，使得xy。真综上，（F(x)y(G(y)H(x,y)既不是永真的也不是永假的。,08.05.2020,.,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是奇数，则xy。真综上，y（F(x)G(y)H(x,y)既不是永真的也不是永假的。,08.05.2020,.,23,第二章一阶逻辑（习题）,13、给出下列各式的一个成真解释和一个成假解释：1）（F(x)G(x)。2）（F(x)G(x)H(x)。3）（F(x)y(G(y)H(x,y)。,08.05.2020,.,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。,08.05.2020,.,25,第二章一阶逻辑（习题）,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，既是偶数，又是素数，又是奇数。,08.05.2020,.,26,第二章一阶逻辑（习题）,3）成真解释:D:N,F(x):X是偶数，G(x):X是奇数，H(x，y):xy。（F(x)y(G(y)H(x,y)：存在偶数X，对任意的奇数y，使得xy。,08.05.2020,.,27,第二章一阶逻辑（习题）,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)yG(y)。,08.05.2020,.,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)。,08.05.2020,.,29,第二章一阶逻辑（习题）,15、设个体域D=1,2，请给出解释I1和I2，使得下面公式在I1下是真命题，在I2下是假命题：1）（F(x)G(x)。2）(F(x)G(x)。,08.05.2020,.,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是奇数。,08.05.2020,.,31,第二章一阶逻辑（习题）,16、给定公式A=F(x)F(x)，1）解释I1，D=a，证明A在I1下的真值为1。2）解释I2，D=a1,a2,an,n2,A在I2下的真值还一定是1吗？为什么？,08.05.2020,.,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)(01)(01)0。又如：D=2，4，F(x)：X是偶数。A=F(x)F(x)(F(2)F(4)(F(2)F(4)(11)(11)1。,08.05.2020,.,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)。,08.05.2020,.,34,第二章一阶逻辑（习题）,1）xyF(x,y)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)1。2）xyF(x,y)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)0。,08.05.2020,.,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)(（0F(4,4)（1F(4,3)(（1F(3,4)（0F(3,3)(（00)（11)(（11)（00)1。,08.05.2020,.,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