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

离散数学习题课（二）主讲姜虹第二章一阶逻辑（习题）

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):X>Y。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.在一阶逻辑中将下列命题符号化，并讨论个体域为(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)）。真第二章一阶逻辑（习题）

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)）。真第二章一阶逻辑（习题）

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)）第二章一阶逻辑（习题）

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.将下列命题符号化，个体域为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）。真第二章一阶逻辑（习题）

7、将下列各公式翻译成自然语言,个体域为整数集,并判断各命题的真假。1）ｘyz(x-y=z)。2）ｘy(x·y=1)。3）ｘyz(x+y=z)。2）对任意的整数X,都存在整数Y,使得x·y=1。假3）存在整数X,对任意的整数Y和Z,都使得x+y=z。假1）对任意的整数X和Y,都存在整数Z,使得x-y=z。真第二章一阶逻辑（习题）

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。第二章一阶逻辑（习题）

9、给定解释I如下:a）个体域D为实数集合R。b）D中特定元素a=0。c）特定函数f(x,y)=x-y。d）特定谓词F(x,y):x=y，G(x,y):x<y。说明下列公式在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))。第二章一阶逻辑（习题）

解:1）ｘY（（x<y)(x=y))。任意的实数X和Y，如果x小于y，则x不等于y。真2）ｘY（（x-y=0)(x<y))。任意的实数X和Y，如果x-y=0，则x<y。假3）ｘy((x<y)(x-y=0))。任意的实数X和Y，如果x小于y，则x-y不等于0。真4）ｘY（(x-y<0)(x=y))。任意的实数X和Y，如果x-y小于0，则x等于y。假第二章一阶逻辑（习题）

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）ｘyzF(f(x,y),z)。4）ｘF(f(x,x),g(x,x))。第二章一阶逻辑（习题）

解: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）ｘyz(x+y=z)。任意的自然数X和Y，都存在自然数z，使得x+y=z。真4）ｘ（x+x=x·x)。存在自然数X和Y，使得x+x=x·x。真第二章一阶逻辑（习题）

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)yG(y)）∧yG(y)。第二章一阶逻辑（习题）

解:1）P(QP)PQP1，用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))是永假式。第二章一阶逻辑（习题）

3）D:R,F(x,y):x>y,ｘyF(x,y):对任意的实数x,存在实数y,使得x>y。真ｘyF(x,y):存在实数x,对任意的实数y,使得x>y。假所以,ｘyF(x,y)ｘyF(x,y)为假。D:N,F(x,y):x>y,ｘyF(x,y):对任意的自然数x,存在自然数y,使得x>y。假ｘyF(x,y):存在自然数x,对任意的自然数y,使得x>y。假所以,ｘyF(x,y)ｘyF(x,y)为真。综上,ｘyF(x,y)ｘyF(x,y)为可满足的。第二章一阶逻辑（习题）

4）D:R,F(x,y):x>y,ｘyF(x,y):存在实数x,对任意的实数y,使得x>y。假yxF(x,y):对任意的实数y,存在实数x,使得x>y。真所以,ｘyF(x,y)yxF(x,y)为真。D:N,F(x,y):x<y,ｘ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)是可满足的。第二章一阶逻辑（习题）

5）D:R,F(x,y):x>y,ｘy(F(x,y)F(y,x)):对任意的实数x和y,如果x>y,则y>x。假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）（PQ）∧Q（PQ）∧QP∧Q∧Q0,用ｘF(x)和yG(y)分别替换上式中的P,Q,可得（ｘF(x)yG(y)）∧yG(y)是永假的。第二章一阶逻辑（习题）

12.证明下列各式既不是永真的也不是永假的：1）ｘ（F(x)y(G(y)∧H(x,y)))。2）ｘy（F(x)∧G(y)H(x,y))。第二章一阶逻辑（习题）

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)))既不是永真的也不是永假的。第二章一阶逻辑（习题）

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))既不是永真的也不是永假的。第二章一阶逻辑（习题）

13.给出下列各式的一个成真解释和一个成假解释：1）ｘ（F(x)G(x))。2）ｘ（F(x)∧G(x)∧H(x))。3）ｘ（F(x)∧y(G(y)∧H(x,y)))。第二章一阶逻辑（习题）

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。第二章一阶逻辑（习题）

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，既是偶数，又是素数，又是奇数。第二章一阶逻辑（习题）

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。成假解释: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。第二章一阶逻辑（习题）

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))。第二章一阶逻辑（习题）

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)))。第二章一阶逻辑（习题）

15.设个体域D={1,2}，请给出解释I1和I2，使得下面公式在I1下是真命题，在I2下是假命题：1）ｘ（F(x)∧G(x))。2）ｘ(F(x)G(x))。第二章一阶逻辑（习题）

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是奇数。第二章一阶逻辑（习题）

16.给定公式A=ｘF(x)ｘF(x)，1）解释I1，D={a}，证明A在I1下的真值为1。2）解释I2，D={a1,a2,…,an},n≥2,A在I2下的真值还一定是1吗？为什么？第二章一阶逻辑（习题）

1）解释I1，D={a}，A=ｘF(x)ｘF(x)F(a)F(a)1，2）解释I2，D={a1,a2,…,an},n≥2,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)(0∧1)0。又如:D={2，4}，F(x):X是偶数。A=ｘF(x)ｘF(x)(F(2)F(4))(F(2)∧F(4))(11)(1∧1)1。第二章一阶逻辑（习题）

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)))。第二章一阶逻辑（习题）

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。第二章一阶逻辑（习题）

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))