习题(一阶逻辑)080923VIP

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

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

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

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

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

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

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

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

。真11/13/20248第二章一阶逻辑（习题）

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

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

。11/13/202410第二章一阶逻辑（习题）

解：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。假11/13/202411第二章一阶逻辑（习题）

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

解：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/13/202413第二章一阶逻辑（习题）

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

解：1）P(Q

P)

P

Q

P1，用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))是永假式。11/13/202415第二章一阶逻辑（习题）

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)为可满足旳。11/13/202416第二章一阶逻辑（习题）

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)是可满足旳。11/13/202417第二章一阶逻辑（习题）

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)

)是可满足旳。11/13/202418第二章一阶逻辑（习题）

6）

（P

Q）∧Q（

P

Q）∧QP∧Q∧Q0，用ｘF(x)

和

y

G(y)分别替代上式中旳P，Q，可得

（ｘF(x)

y

G(y)）∧

yG(y)是永假旳。11/13/202419第二章一阶逻辑（习题）

12、证明下列各式既不是永真旳也不是永假旳：1）ｘ（F(x)

y(G(y)∧H(x,y)))。2）ｘ

y（F(x)

∧

G(y)

H(x,y))。11/13/202420第二章一阶逻辑（习题）

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

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

13、给出下列各式旳一种成真解释和一种成假解释：1）ｘ（F(x)

G(x))。2）ｘ（F(x)

∧

G(x)∧

H(x))。3）ｘ（F(x)

∧

y(G(y)∧

H(x,y)))。11/13/202423第二章一阶逻辑（习题）

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

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

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

。11/13/202426第二章一阶逻辑（习题）

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

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

。11/13/202428第二章一阶逻辑（习题）

15、设个体域D={1,2}，请给出解释I1和I2，使得下面公式在I1下是真命题，在I2下是假命题：1）

ｘ（F(x)

∧G(x))。2）

ｘ(F(x)

G(x))。11/13/202429第二章一阶逻辑（习题）

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

16、给定公式A=

ｘF(x)

ｘF(x)，1）解释I1，D={a}，证明A在I1下旳真值为1。2）解释I2，D={a1,a2,…,an},n≥2,A在I2下旳真值还一定是1吗？为何？11/13/202431第二章一阶逻辑（习题）

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

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

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

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