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

2019/10/14计算机科学与工程系1离散数学习题课（二）2019/10/14计算机科学与工程系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)。2019/10/14计算机科学与工程系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)）。真2019/10/14计算机科学与工程系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)）。真)2)(2(22xxx)2)(2(22xxx)2)(2(22xxx2019/10/14计算机科学与工程系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)）2019/10/14计算机科学与工程系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))。2019/10/14计算机科学与工程系7第二章一阶逻辑（习题）6、将下列命题符号化，个体域为R，并指出其真值。1）对所有的X，都存在Y，使得X·Y=0。2）存在着X，对所有的Y，都有X·Y=0。3）对所有的X，都存在Y，使得Y=X+1。4）对所有的X，Y都有X·Y=Y·X。1）F（X，Y）：X·Y=0，ｘyF（X，Y）。真2）F（X，Y）：X·Y=0，ｘyF（X，Y）。真4）F（X，Y）：X·Y=Y·X，ｘyF（X，Y）。真3）F（X，Y）：Y=X+1，ｘyF（X，Y）。真2019/10/14计算机科学与工程系8第二章一阶逻辑（习题）7、将下列各公式翻译成自然语言，个体域为整数集，并判断各命题的真假。1）ｘyz(x-y=z)。2）ｘy(x·y=1)。3）ｘyz(x+y=z)。2）对任意的整数X，都存在整数Y，使得x·y=1。假3）存在整数X,对任意的整数Y和Z，都使得x+y=z。假1）对任意的整数X和Y，都存在整数Z，使得x-y=z。真2019/10/14计算机科学与工程系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。2019/10/14计算机科学与工程系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))。2019/10/14计算机科学与工程系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。假2019/10/14计算机科学与工程系12第二章一阶逻辑（习题）10、给定解释I如下：a）个体域D为自然数集合N。b）D中特定元素a=2。c）特定函数f(x,y)=x+y，g(x,y)=x·y。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zF(f(x,y),z)。4）ｘF(f(x,x),g(x,x))。2019/10/14计算机科学与工程系13第二章一阶逻辑（习题）解：1）ｘ（x·2=x)。任意的自然数X，都有x·2=x。假2）ｘY（（x+2=y)(y+2=x))。任意的自然数X和Y，如果x+2=y，则y+2=x。假3）ｘyz(x+y=z)。任意的自然数X和Y，都存在自然数z，使得x+y=z。真4）ｘ（x+x=x·x)。存在自然数X和Y，使得x+x=x·x。真2019/10/14计算机科学与工程系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)yxF(x,y)。5）ｘy(F(x,y)F(y,x))。6）（ｘF(x)yG(y)）∧yG(y)。2019/10/14计算机科学与工程系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，所以ｘ（F(x)F(x))1。因为y(G(y)∧G(y))0，所以ｘ（F(x)F(x))y(G(y)∧G(y))是永假式。2019/10/14计算机科学与工程系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)为真。综上，ｘyF(x,y)ｘyF(x,y)为可满足的。2019/10/14计算机科学与工程系17第二章一阶逻辑（习题）4）D:R,F(x,y):xy,ｘyF(x,y):存在实数x,对任意的实数y，使得xy。假yxF(x,y):对任意的实数y,存在实数x，使得xy。真所以，ｘyF(x,y)yxF(x,y)为真。D:N,F(x,y):xy,ｘyF(x,y):存在自然数x,对任意的自然数y，使得xy。真yxF(x,y):对任意的自然数y,存在自然数x，使得xy。假所以，ｘyF(x,y)yxF(x,y)为假。综上，ｘyF(x,y)yxF(x,y)是可满足的。2019/10/14计算机科学与工程系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))是可满足的。2019/10/14计算机科学与工程系19第二章一阶逻辑（习题）6）（PQ）∧Q（PQ）∧QP∧Q∧Q0，用ｘF(x)和yG(y)分别替换上式中的P，Q，可得（ｘF(x)yG(y)）∧yG(y)是永假的。2019/10/14计算机科学与工程系20第二章一阶逻辑（习题）12、证明下列各式既不是永真的也不是永假的：1）ｘ（F(x)y(G(y)∧H(x,y)))。2）ｘy（F(x)∧G(y)H(x,y))。2019/10/14计算机科学与工程系21第二章一阶逻辑（习题）1）D:N,F(x):x是偶数,G(x):x是奇数,H(x,y)：x≥y。ｘ（F(x)y(G(y)∧H(x,y))):对任意的自然数x，如果x是偶数，则存在奇数y，使得x≥y。假D:N,F(x):x是偶数,G(x):x是奇数,H(x,y)：x≠y。ｘ（F(x)y(G(y)∧H(x,y))):对任意的自然数x，如果x是偶数，则存在奇数y，使得x≠y。真综上，ｘ（F(x)y(G(y)∧H(x,y)))既不是永真的也不是永假的。2019/10/14计算机科学与工程系22第二章一阶逻辑（习题）2）D:N,F(x):x是偶数,G(x):x是奇数,H(x,y)：x≥y。ｘy（F(x)∧G(y)H(x,y)):对任意的自然数x和y，如果x是偶数，y是奇数，则x≥y。假D:N,F(x):x是偶数,G(x):x是奇数,H(x,y)：x≠y。ｘy（F(x)∧G(y)H(x,y)):对任意的自然数x和y，如果x是偶数，y是奇数，则x≠y。真综上，ｘy（F(x)∧G(y)H(x,y))既不是永真的也不是永假的。2019/10/14计算机科学与工程系23第二章一阶逻辑（习题）13、给出下列各式的一个成真解释和一个成假解释：1）ｘ（F(x)G(x))。2）ｘ（F(x)∧G(x)∧H(x))。3）ｘ（F(x)∧y(G(y)∧H(x,y)))。2019/10/14计算机科学与工程系24第二章一阶逻辑（习题）1）成真解释:D:N,F(x):X是偶数，G(x):X是奇数，ｘ（F(x)