新版离散数学答案(尹宝林版)第二章习题解答课件.doc
- 格式：doc
- 大小：3.86 MB
- 文档页数：19
现是约束出现。x的唯一出现的辖域是P(z,g(x,y))，y的唯一出现的辖域是
P(f(x,y),x)xP(z,g(x,y))。
(5)变元x在x(P(x)Q(x)xR(x))R(x)中的头五次出现是约束出现，第六次出现
是自由出现。x的唯一出现的辖域是P(x)Q(x)xR(x)，x的唯一出现的辖域是R(x)。
5.归纳证明：若t，t是项，则
x
t也是项。
t
证明①若t是x，则tx是t，x
t是项。
tt
②若t是不同于x的变元y，则ttx仍是y，ttx是项。
③若t是常元a，则tx仍是a，x
t是项。
tt
④若t是f(t1,,tn)，则
xxx
t是f ((t1)t,,(t))，由归纳假设知
tnt
xx
(t1),,()都是项，
(5)“函数f(x)是严格单调递增函数”符号化为xy(xyf(x)f(y))。
4.指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。
(1)x(P(y,x)P(x,a))
(2)xP(x)zQ(x,y)
(3)x(P(x)R(x))xP(x)Q(x)
(4)y(P(f(x,y),x)xP(z,g(x,y)))
x(M(x)y(L(y)D(x,y)))。
(4)取论域为所有事物的集合。令
M(x):x是人，J(x):x是职业，L(x,y):x喜欢y。
“每个人都有自己喜欢的职业”可以符号化为x(M(x)y(J(y)L(x,y)))
(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为
x(J(x)y(M(y)L(y,x)))。
E(x):x是偶数，E(x)可表示为v(v2x)。
P(x):x是素数，P(x)可表示为(x1)u(v(vux)u1ux)。
(1)“没有既是奇数，又是偶数的正整数”可表示为x(J(x)E(x))，
并可进一步符号化为x(v(v2x)v(v2x))。
(2)“任何两个正整数都有最小公倍数”可表示为
xyz(D(z,x)D(z,y)u(D(u,x)D(u,y)zuzu))，
“所有的火车都比某些汽车快”可以符号化为x(T(x)y(C(y)F(x,y)))。
(2)取论域为所有物质的集合。令
M(x):x是金属，L(x):x是液体，D(x,y):x可以溶解在y中。
“任何金属都可以溶解在某种液体中”可以符号化为x(M(x)y(L(y)D(x,y)))。
(3)论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为
第二章谓词逻辑
习题与解答
1.将下列命题符号化：
(1)所有的火车都比某些汽车快。
(2)任何金属都可以溶解在某种液体中。
(3)至少有一种金属可以溶解在所有液体中。
(4)每个人都有自己喜欢的职业。
(5)有些职业是所有的人都喜欢的。
解(1)取论域为所有交通工具的集合。令
T(x):x是火车，C(x):x是汽车，F(x,y):x比y跑得快。
2.取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：
(1)没有既是奇数，又是偶数的正整数。
(2)任何两个正整数都有最小公倍数。
(3)没有最大的素数。
(4)并非所有的素数都不是偶数。
解先引进一些谓词如下：
D(x,y):x能被y整除，D(x,y)可表示为v(vyx)。
J(x):x是奇数，J(x)可表示为v(v2x)。
并可进一步符号化为
xyz(v(vxz)v(vyz)u(v(vxu)v(vyu)zuzu))
(3)“没有最大的素数”可表示为x(P(x)y(P(y)yxyx))，
并可进一步符号化为
x((x1)u(v(vux)u1ux)
y((y1)u(v(vuy)u1uy)yxyx))
(4)“并非所有的素数都不是偶数”可表示为x(P(x)E(x))，并可进一步符号化为
x
tCA是公ttttt
式。
④若A是xB，则x
A仍是A，
t
x
A是公式。
t
⑤若A是yB，其中y是不同于x的变元，则Ax是yBx，由归纳假设知x
B是公式，
ttt
所以
x
A是公式。
t
7.给定解释I和I中赋值v如下：
D，aI1，bI2，fI(1)2，fI(2)1
{1,2}I
PI(PI，PI(2,1)PI(2,2)0，v(x)1，v(y)1
xP(x)zQ(x,y)中的唯一出现是约束出现。x的唯一出现的辖域是P(x)，z的唯
一出现的辖域是Q(x,y)。
(3)变元x在x(P(x)R(x))xP(x)Q(x)中的头五次出现是约束出现，第六次出
现是自由出现。x的第一次出现的辖域是P(x)R(x)，第二次出现的辖域是P(x)。
(4)变元x在y(P(f(x,y),x)xP(z,g(x,y)))中的头两次出现是自由出现，后两次出
(5)x(P(x)Q(x)xR(x))R(x)
解(1)变元x在x(P(y,x)P(x,a))中三次出现都是约束出现，x的唯一出现的辖
域是P(y,x)P(x,a)。
(2)变元x在xP(x)zQ(x,y)中的头两次出现是约束出现，第三次出现是自由出现。
变元y在xP(x)zQ(x,y)中的唯一出现是自由出现。变元z在
(2)“任何两个不同的实数之间必有另一实数”符号化为xy(xyz(xzzy))。
(3)“函数f(x)在点a处连续”的定义是：
任给0，总可以找到0，使得只要|xa|就有|f(x)f(a)|。
“函数f(x)在点a处连续”符号化为
(0(0x(axxaf(a)f(x)f(x)f(a))))
(4)“函数f(x)恰有一个根”符号化为x(f(x)0y(f(y)0yx))。
tt
nt
所以
x
t是项。
t
6.归纳证明：若t是项，A是公式，则Atx也是公式。
证明①若A是P(t1,,tn)，则
xx
Pxx，由上题知x
A是((1),,())
ttttt
(t1),,()都是
tntnt
项，所以
A是公式。
t
②若A是B，则Ax是Bx，由归纳假设知Bx是公式，所以x
A是公式。
tttt
③若A是BC，则Ax是Bx，由归纳假设知Bx和Cx都是公式，所以x
x((x1)u(v(vux)u1ux)v(v2x))
3.取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：
(1)没有最大的实数。
(2)任何两个不同的实数之间必有另一实数。
(3)函数f(x)在点a处连续。
(4)函数f(x)恰有一个根。
(5)函数f(x)是严格单调递增函数。
解(1)“没有最大的实数”符号化为xy(yxyx)。
P(f(x,y),x)xP(z,g(x,y))。
(5)变元x在x(P(x)Q(x)xR(x))R(x)中的头五次出现是约束出现，第六次出现
是自由出现。x的唯一出现的辖域是P(x)Q(x)xR(x)，x的唯一出现的辖域是R(x)。
5.归纳证明：若t，t是项，则
x
t也是项。
t
证明①若t是x，则tx是t，x
t是项。
tt
②若t是不同于x的变元y，则ttx仍是y，ttx是项。
③若t是常元a，则tx仍是a，x
t是项。
tt
④若t是f(t1,,tn)，则
xxx
t是f ((t1)t,,(t))，由归纳假设知
tnt
xx
(t1),,()都是项，
(5)“函数f(x)是严格单调递增函数”符号化为xy(xyf(x)f(y))。
4.指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。
(1)x(P(y,x)P(x,a))
(2)xP(x)zQ(x,y)
(3)x(P(x)R(x))xP(x)Q(x)
(4)y(P(f(x,y),x)xP(z,g(x,y)))
x(M(x)y(L(y)D(x,y)))。
(4)取论域为所有事物的集合。令
M(x):x是人，J(x):x是职业，L(x,y):x喜欢y。
“每个人都有自己喜欢的职业”可以符号化为x(M(x)y(J(y)L(x,y)))
(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为
x(J(x)y(M(y)L(y,x)))。
E(x):x是偶数，E(x)可表示为v(v2x)。
P(x):x是素数，P(x)可表示为(x1)u(v(vux)u1ux)。
(1)“没有既是奇数，又是偶数的正整数”可表示为x(J(x)E(x))，
并可进一步符号化为x(v(v2x)v(v2x))。
(2)“任何两个正整数都有最小公倍数”可表示为
xyz(D(z,x)D(z,y)u(D(u,x)D(u,y)zuzu))，
“所有的火车都比某些汽车快”可以符号化为x(T(x)y(C(y)F(x,y)))。
(2)取论域为所有物质的集合。令
M(x):x是金属，L(x):x是液体，D(x,y):x可以溶解在y中。
“任何金属都可以溶解在某种液体中”可以符号化为x(M(x)y(L(y)D(x,y)))。
(3)论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为
第二章谓词逻辑
习题与解答
1.将下列命题符号化：
(1)所有的火车都比某些汽车快。
(2)任何金属都可以溶解在某种液体中。
(3)至少有一种金属可以溶解在所有液体中。
(4)每个人都有自己喜欢的职业。
(5)有些职业是所有的人都喜欢的。
解(1)取论域为所有交通工具的集合。令
T(x):x是火车，C(x):x是汽车，F(x,y):x比y跑得快。
2.取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：
(1)没有既是奇数，又是偶数的正整数。
(2)任何两个正整数都有最小公倍数。
(3)没有最大的素数。
(4)并非所有的素数都不是偶数。
解先引进一些谓词如下：
D(x,y):x能被y整除，D(x,y)可表示为v(vyx)。
J(x):x是奇数，J(x)可表示为v(v2x)。
并可进一步符号化为
xyz(v(vxz)v(vyz)u(v(vxu)v(vyu)zuzu))
(3)“没有最大的素数”可表示为x(P(x)y(P(y)yxyx))，
并可进一步符号化为
x((x1)u(v(vux)u1ux)
y((y1)u(v(vuy)u1uy)yxyx))
(4)“并非所有的素数都不是偶数”可表示为x(P(x)E(x))，并可进一步符号化为
x
tCA是公ttttt
式。
④若A是xB，则x
A仍是A，
t
x
A是公式。
t
⑤若A是yB，其中y是不同于x的变元，则Ax是yBx，由归纳假设知x
B是公式，
ttt
所以
x
A是公式。
t
7.给定解释I和I中赋值v如下：
D，aI1，bI2，fI(1)2，fI(2)1
{1,2}I
PI(PI，PI(2,1)PI(2,2)0，v(x)1，v(y)1
xP(x)zQ(x,y)中的唯一出现是约束出现。x的唯一出现的辖域是P(x)，z的唯
一出现的辖域是Q(x,y)。
(3)变元x在x(P(x)R(x))xP(x)Q(x)中的头五次出现是约束出现，第六次出
现是自由出现。x的第一次出现的辖域是P(x)R(x)，第二次出现的辖域是P(x)。
(4)变元x在y(P(f(x,y),x)xP(z,g(x,y)))中的头两次出现是自由出现，后两次出
(5)x(P(x)Q(x)xR(x))R(x)
解(1)变元x在x(P(y,x)P(x,a))中三次出现都是约束出现，x的唯一出现的辖
域是P(y,x)P(x,a)。
(2)变元x在xP(x)zQ(x,y)中的头两次出现是约束出现，第三次出现是自由出现。
变元y在xP(x)zQ(x,y)中的唯一出现是自由出现。变元z在
(2)“任何两个不同的实数之间必有另一实数”符号化为xy(xyz(xzzy))。
(3)“函数f(x)在点a处连续”的定义是：
任给0，总可以找到0，使得只要|xa|就有|f(x)f(a)|。
“函数f(x)在点a处连续”符号化为
(0(0x(axxaf(a)f(x)f(x)f(a))))
(4)“函数f(x)恰有一个根”符号化为x(f(x)0y(f(y)0yx))。
tt
nt
所以
x
t是项。
t
6.归纳证明：若t是项，A是公式，则Atx也是公式。
证明①若A是P(t1,,tn)，则
xx
Pxx，由上题知x
A是((1),,())
ttttt
(t1),,()都是
tntnt
项，所以
A是公式。
t
②若A是B，则Ax是Bx，由归纳假设知Bx是公式，所以x
A是公式。
tttt
③若A是BC，则Ax是Bx，由归纳假设知Bx和Cx都是公式，所以x
x((x1)u(v(vux)u1ux)v(v2x))
3.取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：
(1)没有最大的实数。
(2)任何两个不同的实数之间必有另一实数。
(3)函数f(x)在点a处连续。
(4)函数f(x)恰有一个根。
(5)函数f(x)是严格单调递增函数。
解(1)“没有最大的实数”符号化为xy(yxyx)。
