自考离散数学第二章答案

习题答案

(从本章起，习题答案由jhju提供，晓津补充。如有问题或不同意见，欢迎到分课论坛发表)

1、用谓词表达式写出下列命题

a)小张不是研究生；

解：设A(x)：x是研究生；

a:小张；

|A(a)。

b)他是跳高或篮球运动员；

解：

设A(x):x是跳高运动员；

B(x):x是篮球运动员；

a: 他；

A(a)∨B(a) 。

c)晓莉非常聪明和能干；

解：设 A(x):x非常聪明 ；

B(x):x能干 ；

l: 晓莉 ；

A(l)∧B(l)

d)若m是奇数则2m是偶数

解：设 A(x): x是奇数

B(y):y是偶数

m:某数

A(m)→ B(2m)

2、将下列命题符号化并要分析到个体词及谓词

a)长江流经四川省；

解：B(x,y):x流经y；

a:长江 b:四川省

B(a,b)。

个体词：长江、四川省 谓词：流经

b)这架新式歼击机击沉了那艘老式快艇

解：设A(x,y):x击沉了y

a:新式歼击机 b:老式快艇

A(a,b).

个体词：歼击机、快艇 谓词：击沉

3、用谓词表达式符号化下列命题。

那位戴眼镜穿西服的大学生在看一本英文杂志。

解：设：

A(x): x戴眼镜；

B(x): x穿西服；

C(x): x在看英文杂志；

a: 那位大学生

A(a)∧B(a)∧C(a)

这个表达式的含义就是一个陈述句：

那位大学生戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。

个体词是：那位大学生。谓词有：戴眼镜、穿西服、在看英文杂志。

习题答案

(从本章起，习题答案由jhju提供，晓津补充。如有问题或不同意见，欢迎到分课论坛发表)

题号：1 2 3 4 5 6

1、对下列公式指出约束变元和自由变元，并指明量词的辖域。

a,(x)(P(x)—→Q(x))∧(x)R(x,y)；

(x)的指导变元是x,其辖域是(P(x)—→Q(x))

(x)的指导变元是x,其辖域是R(x,y)

对于(x)来说，x是约束出现，y则是自由出现。

b,(x)(y)(P(x)∨Q(y))—→(x)(R(x)∧S(z))；

(x)和(y)的指导变元是x,y,其辖域是(P(x)∨Q(y))

(x)的指导变元是x,其辖域是(R(x)∧S(z))

x,y在辖域是约束出现，z则是自由出现

(注，教材中本题原来是多一个括号的(或者说少一个)，现在jhju将它改成这个样子，请大家仔细在书中找BUG)

c,(x)(y)(P(x,y)∧Q(z))

(x)(y)的指导变元是x,y,自由变元是z,其辖域是P(x,y)∧Q(z)

2、在下列公式中，对约束变元进行换名，对自由变量进行代入。

a,(x)(y)(P(x,z)—→Q(y))←→S(x,y)

约束变元的换名，用t替换x,用g替换y

(t)(g)(P(t,z)—→Q(g))←→S(x,y)

将自由变元z换为e

(x)(y)(P(x,e)—→Q(y))←→S(x,y)

b,(x)(P(x)—→Q(x))—→(x)(k(x))∧S(x));

对约束变元x改名为z

(z)(P(z)—→Q(z))—→(z)(k(z))∧S(z))

c,(x)(P(x)—→(Q(x)∨R(x)))∧(x)(R(x)—→(y)S(x,y));

对前件的约束变元x改名为z

(z)(P(z)—→(Q(z)∨R(z)))∧(z)(R(z)—→(y)S(z,y))

用g来代替自由变元y

(z)(P(z)—→(Q(z)∨R(z)))∧(z)(R(z)—→(g)S(z,g))

d,(x)P(x,y)∧(x)(Q(x,z)—→(z)(x)R(x,y,z));

用g换名约束变元x

(g)P(g,y)∧(g)(Q(g,z)—→(z)(g)R(g,y,z))

对自由变元y进行替换d

(x)P(x,d)∧(x)(Q(x,z)—→(z)(x)R(x,d,z))

e,(x)(P(x,y)—→(z)Q(x,z));

对约束变元x进行替换g

(g)(P(g,y)—→(z)Q(x,z))

对自由变元 x代为g y代为d

(x)(P(x,d)—→(z)Q(g,z))

3、谓词公式 (x)(P(x)∨(y)R(y))—→Q(x)中量词(x)的辖域是：

a,(x)(P(x)∨(y)R(y))

b,P(x);

c,(P(x)∨(y)R(y))

d,P(x),Q(x)

答案：[c]

4、谓词公式 (x)(P(x)∨(y)R(y))—→Q(x)中变元x是答案[ ]。

a,自由变元

b,约束变元

c,既不是自由变元，也不是约束变元

d,既是自由变元又是约束变元；

答案是[d]

(请注意，教材中又少一括号，如果按上面红色括号的位置添入，则答案为d,若加在最后，则答案为b,当然，括号还可以加在P(x)后面，则此时答案又变成d)

5、设论域为整数集，下列公式中哪个值为真。

a,(x)(y)(x+y=0);

b,(y)(x)(x+y=0);

c,(x)(y)(x+y=0);

d,|(x)(|y)(x+y=0);

答案[ ]

(jhju的答案是c,

注意题中的|y，晓津觉得个体变元前面不应该加否定，前面三个答案是不对的，但是也不能说最后一个答案是对的，除非把"|"改成""，大家说呢

后来有学友指出本题中答案a是正确的，其解释是对于任意x存在y，有x+y=0,这是真的。所以本题的答案应当是a)

6、取个体域为整数集，给定下列公式,指出下面公式中哪些是真命题，哪些是假命题：

a, xy =0); e, x-y=-y+x ;

b, xy =1); f, xy=y);

c, yx =2); g, x=x);

d, xyx (x-y=z); h,

xy (x+y=2y)。

答：a , e , f,h 为真

b ,c , g 为假

d 是否出错

(以上是jhju答案，晓津认为：只有a,c,e是真命题，其他的都为假。至于d,我也觉得有个BUG，大约x应改为z吧。)

习题参考答案

(本章习题答案由jhju提供，晓津补充。如有问题或不同意见，欢迎到分课论坛发表)

题号：1 2 3 4 5 6 7 8

1、设解释I如下： D={2,3}, f(2)=3,f(3)=2,F(2,2)=0,F(2,3)=0,F(3,2)=1,F(3,3)=1 。

试求出下列公式在I下的真值。

a) F(2,f(2))∧F(3,f(3));

解：a) F(2,f(2))∧F(3,f(3))

F(2,3)∧F(3,2)

0∧1

0

由于离散数学中 0与F对应故该式为假

b) xyF(y,x);

b)参照P33页例2 c

F(2,2)∨F(3,2)∧F(2,3)∨F(3,3)

0∨1∧0∨1

1 该式为真

(晓津观点：原式

〈＝〉(F(2,2)∨F(3，2))∧(F(2，3)∨F(3，3))

〈＝〉(0∨1)∧(0∨1)

〈＝〉1∧1〈＝〉T

我认为有些括号不能省略，虽然此题中结果相同)

c) xy(F(x,y)→F(f(x),f(y)));

解：c) 原式

〈＝〉(F(x,y)→F(f(x),f(y))∧

(F(x,y)→F(f(x),f(y))∧

(F(x,y)→F(f(x),f(y))∧

(F(x,y)→F(f(x),f(y))

〈＝〉(F(2,2)→F(f(2),f(2))∧

(F(2,3)→F(f(2),f(3))∧

(F(3,2)→F(f(3),f(2))∧

(F(3,3)→F(f(3),f(3))

〈＝〉(0→1)∧(0→1)∧(1→0)∧(1→0) 〈＝〉 0

该式为假

(晓津认为红色部分应舍去，在消去量词后，个体变元就应该赋值代入了,且红色部分的表达式似无意义，每一行都是相同的。)

2、给定解释N如下：

a) 个体域为自然数

DN；

b) DN上特定元素 a=0;

c) DN上特定函数 f(x,y)=x+y ,g(x,y)= ;

d) DN上特定谓词 F（x,y) 为 x=y 。

在解释N下，哪些公式为真，哪些公式为假。

a) xF(g(x,a),x);

b) xyF(f(x,a),y)→F(f(y,a),x));

c) xyzF(f(x,y),z);

d) xyF(f(x,y),g(x,y));

e) F(f(x,y),f(y,z))。

解：

a,为假，如果 a=1时，该式子便会成立的。

b, 为假，如果 a=1时，该式子也不会成立。

c, 为假