新版离散数学答案(尹宝林版)第二章习题解答课件.doc
第二章谓词逻辑
习题与解答
1. 将下列命题符号化：
(1) 所有的火车都比某些汽车快。
(2) 任何金属都可以溶解在某种液体中。
(3) 至少有一种金属可以溶解在所有液体中。
(4) 每个人都有自己喜欢的职业。
(5) 有些职业是所有的人都喜欢的。
解(1) 取论域为所有交通工具的集合。令
T(x):x是火车，C(x):x是汽车，F(x,y):x比y跑得快。
“所有的火车都比某些汽车快”可以符号化为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)同。“至少有一种金属可以溶解在所有液体中”可以符号化为
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)))。
2. 取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：
(1) 没有既是奇数，又是偶数的正整数。
(2) 任何两个正整数都有最小公倍数。
(3) 没有最大的素数。
(4) 并非所有的素数都不是偶数。
解先引进一些谓词如下：
D(x,y):x能被y整除，D(x,y)可表示为v(v y x)。
J(x):x是奇数，J(x)可表示为v(v2x)。
E(x):x是偶数，E(x)可表示为v(v2x)。
P(x):x是素数，P(x)可表示为(x1)u(v(v u x)u1u x)。
(1)“没有既是奇数，又是偶数的正整数”可表示为x(J(x)E(x))，
并可进一步符号化为x(v(v2x)v(v2x))。
(2)“任何两个正整数都有最小公倍数”可表示为
x y z(D(z,x)D(z,y)u(D(u,x)D(u,y)z u z u))，
并可进一步符号化为
x y z(v(v x z)v(v y z)u(v(v x u)v(v y u)z u z u)) (3)“没有最大的素数”可表示为x(P(x)y(P(y)y x y x))，
并可进一步符号化为
x((x1)u(v(v u x)u1u x)
y((y1)u(v(v u y)u1u y)y x y x))
(4)“并非所有的素数都不是偶数”可表示为x(P(x)E(x))，并可进一步符号化为
x((x1)u(v(v u x)u1u x)v(v2x))
3.取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：
(1)没有最大的实数。
(2)任何两个不同的实数之间必有另一实数。
(3)函数f(x)在点a处连续。
(4)函数f(x)恰有一个根。
(5)函数f(x)是严格单调递增函数。
解(1)“没有最大的实数”符号化为x y(y x y x)。
(2)“任何两个不同的实数之间必有另一实数”符号化为x y(x y z(x z z y))。
(3)“函数f(x)在点a处连续”的定义是：
任给0，总可以找到0，使得只要|x a|就有|f(x)f(a)|。
“函数f(x)在点a处连续”符号化为
(0(0x(a x x a f(a)f(x)f(x)f(a))))
(4) “函数 f (x) 恰有一个根”符号化为x( f (x) 0 y( f (y) 0 y x)) 。
(5) “函数 f (x) 是严格单调递增函数”符号化为x y(x y f (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 )))
(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 在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 ))) 中的头两次出现是自由出现，后两次出现是约束出现。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，则t x 是t ，x
t 是项。
t t
②若t是不同于x 的变元y，则t t x 仍是y，t t x 是项。
③若t是常元a，则t x 仍是a，x
t 是项。
t t
④若t 是f (t1, ,t n) ，则
x x x
t 是f (( t1)t , ,(t ) )，由归纳假设知
t n t
x x
(t1) , ,( ) 都是项，
t t
n t
所以x
t是项。
t
6.归纳证明：若t是项，A是公式，则A t x也是公式。
证明①若A是P(t1,,t n)，则x x
P x x，由上题知x
A是((1),,())
t t t t t
(t1),,()都是
t n t n t
项，所以x
A是公式。
t
②若A是B，则A x是B x，由归纳假设知B x是公式，所以x
A是公式。
t t t t
③若A是B C，则A x是B x，由归纳假设知B x和C x都是公式，所以x
x
t C A是公
t t t t t
式。
④若A是xB，则x
A仍是A，
t
x
A是公式。t
⑤若A是yB，其中y是不同于x的变元，则A x是yB x，由归纳假设知x
B是公式，
t t t
所以x
A是公式。
t
7.给定解释I和I中赋值v如下：
D，a I1，b I2，f I(1)2，f I(2)1
{1,2}
I
P I(P I，P I(2,1)P I(2,2)0，v(x)1，v(y)1
1,1)(1,2)1
计算下列公式在解释I和赋值I中v下的真值。
(1)P(a,f(x))P(x,f(b))P(f(y),x)
(2)x yP(y,x)
(3)x y(P(x,y)P(f(x),f(y)))
解(1)I(P(a,f(x))P(x,f(b))P(f(y),x))(v)
P I I I I I I I I
(a,f(v(x)))P(v(x),f(b))P(f(v(y)),v(x))
P I(f I P I f I P I f I
1,(1))(1,(2))(I
(f I P I f I P I f I
(1),1)
P I(P I P I
1,2)(1,1)I
(P I P I
(2,1)1100
(2)I(x yP(y,x))(v)
I(yP(y,x))(v[x/1])I(yP(y,x))(v[x/2])
(I(P(y,x))(v[x/1][y/1])I(P(y,x))(v[x/1][y/2]))
(I(P(y,x))(v[x/2][y/1])I(P(y,x))(v[x/2][y/2]))
(2,2))
(P I P I P I P I
(1,1)(2,1))((1,2)
(10)(10)1
(3)I(x y(P(x,y)P(f(x),f(y))))(v)
(P I P I f I f I P I P I f I f I
(2)))
(1,1)((1),(1)))((1,2)((1),
(2)))
(P I P I f I f I P I P I f I f I
(2,1)((2),(1)))((2,2)((2),
(1,1)) (P I P I P I P I P I P I P I P I (1,1)(2,2))((1,2)(2,1))((2,1)(1,2))((2,2)
(10)(10)(01)(01)00110
7.给定解释I如下：
I，P I(a,b)P I(b,a)0
I
D I{a b，P(a,a)P(b,b)1
,}
判断I是不是以下语句的模型。
(1)x yP(x,y)
(2)x yP(x,y)
(3)x yP(x,y)
(4)x y P(x,y)
(5)x y(P(x,y)P(y,x))
(6)xP(x,x)
解(1)I(x yP(x,y))
(10)(01)1
(P I a a P I a b P I b a P I b b
(,)(,))((,)(,))
(2)I(x yP(x,y))
10010
P I I I I
(a,a)P(a,b)P(b,a)P(b,b)
(3)I(x yP(x,y))
(P I a a P I a b P I b a P I b b
(10)(01)0
(,)(,))((,)(,))
(4)I(x y P(x,y))
P I I I I
(a,a)P(a,b)P(b,a)P(b,b)
01101
(5)I(x y(P(x,y)P(y,x)))
(P I a a P I a a P I a b P I b a
(,)(,))((,)(,))
(P I b a P I a b P I b b P I b b
(,)(,))((,)(,))
(11)(00)(00)(11)1
(6)I(xP(x,x))P I(a,a)P I(b,b)111
9.写出一个语句A，使得A有模型，并且A的每个模型的论域至少有三个元素。
解语句A为x P(x,x)P(a,b)P(b,c)P(c,a)。给定解释I如下。
D为自然数集合，P I(x,y)1当且仅当x y，a I1，b I2，c I3 I
则I是A的模型，A有模型。
任取满足语句A的解释I，则P I(a I,b I)P I(b I,c I)P I(c I,a I)1，又因为
I，所以a I，b I，c I是论域D I中三个不同元素，论域D I中至少有三个(x P(x,x))1
元素。
10.写出一个语句A，使得A有模型，并且A的每个模型的论域有无穷多个元素。
解语句A为x P(x,x)x y(P(x,y)P(y,z)P(x,z))x yP(x,y)。给定解释I如下。
D为自然数集合，P I(x,y)1当且仅当x y
I
则I是A的模型，A有模型。
任取满足语句A的解释I，取d1D I，因为I(x yP(x,y))1，所以有d2D I使得
P I，又因为I(x P(x,x))1，故(d1,d2
)1d1d。因为I(x yP(x,y))1，所以2
I
有d3D I使得P(d2,d3)1
，又因为I(x P(x,x))1，故d3d2。因为
I，故I((，所以P(d1,d3)1
(x y P(x,y)P y,z)P(x,z)))1d3d。因此，d1，
1
d，d3是论域中的三个不同元素。这个过程可以不断进行下去，得到d1,d2,d3,因此，2
论域D I中必然有无穷多个元素。
11.判断以下公式是不是永真式、永假式、可满足式，并说明理由。
(1)xP (x) xQ( x) x( P(x) Q( x))
(2)xP (x) xQ( x) x( P(x) Q( x))
(3)x(P( x) Q( x)) xP( x) xQ( x)
(4)xP(x, x) x yP( x, y)
(5)( xP( x) xQ ( x)) x( P( x) Q( x))
(6)( xP( x) xQ(x )) x( P(x) Q (x))
(7)x(P( x) Q(x)) ( xP( x) xQ( x))
解(1) xP( x) xQ( x) x( P(x) Q( x)) 是永真式。若解释I 使得
I ( xP( x) xQ (x)) 1 ，则I ( xP( x)) 1或I ( xQ( x)) 1。
①若I ( xP (x)) 1，则存在d D I 使得P I (d) 1，P I (d) Q I (d) 1。
②若I ( xQ(x )) 1，则存在d D I 使得Q I (d) 1，P I (d) Q I (d) 1。
因此，I ( x( P( x) Q( x))) 1。
(2) xP (x) xQ( x) x( P( x) Q(x)) 是非永真的可满足式。给定解释I 如下。
I ，Q I (d) 1
D I {d} ，P (d) 1
则I ( xP(x) xQ (x) x(P(x) Q (x))) 1。
给定解释I 如下。
D I ，P I (a) 1，P I (b) 0，Q I (a) 0，Q I (b) 1
{a,b}
则I ( xP( x) xQ( x) x(P( x) Q( x))) 0 。
(3) x( P(x) Q( x)) xP (x) xQ (x) 是非永真的可满足式。给定解释I 如下。
I ，Q I (d) 1
D I ，P (d) 1
{d}
则I ( x( P( x) Q( x)) xP (x) xQ(x )) 1。
给定解释I 如下。
D I ，P I (a) 1，P I (b) 0，Q I (a) 0，Q I (b) 1
{a,b}
则I ( x(P(x) Q( x)) xP (x) xQ ( x)) 0 。
(4) xP( x, x) x yP( x, y) 是非永真的可满足式。给定解释I 如下。
I
D I ，P (d, d) 1
{d}
则I ( xP( x, x) x yP( x, y)) 1。
给定解释I 如下。
I ，P I (a ,b) P I (b,a) 0
I
D I {a,b} ，P(a, a) P (b ,b) 1
则I ( xP( x, x) x yP( x, y)) 0 。
(5) ( xP( x) xQ( x)) x(P( x) Q( x)) 是非永真的可满足式。给定解释I 如下。
I ，Q I (d) 1
D I {d} ，P (d) 1
则I (( xP( x) xQ( x)) x(P( x) Q( x))) 1。
给定解释I 如下。
I ，P I (b) 0，Q I (a) 0，Q I (b) 1
{a,b}
D I ，P(a) 1
则I (( xP(x) xQ( x)) x( P( x) Q( x))) 0 。
(6) ( xP( x) xQ( x)) x( P( x) Q(x )) 是永真式。若解释I 使得
I I ，因此P I (d) 1且
( x(P(x Q x))) 0
I ) ( ，则存在 d D I 使得P (d) Q (d) 0
Q I ，I ( xP(x )) 1且I ( xQ( x)) 0，I (( xP (x) xQ( x))) 0。
(d) 0
(7) x(P( x) Q( x)) ( xP( x) xQ (x)) 是永真式。若解释I 使得
I ，则I ( xP( x)) 1 且I ( xQ( x)) 0 。存在d D I 使得(( xP( x) xQ (x))) 0
P I ，又因为I ( xQ( x)) 0 ，所以Q I (d) 0 ，P I (d) Q I (d) 0 。因此，
(d) 1
I ( x( P( x) Q (x))) 0。
12. 设A, B 是任意公式，证明以下公式是永真式。
(1) A x xA
t , 其中项t 对于A 中的x 是可代入的。
(2) xA x A
(3) xA x A
(4) x( A B) xA xB
(5) xA xB x(A B)
(6) x( A B) (A xB) ，其中x 不是A 的自由变元。
x x
解(1) 任取解释I 和I 中赋值v，若I(A t )(v) 1, 则I (A )( v) I (A)(v[ x / I (t)(v)] ) 1
t ，所以I ( xA)( v) 1。这表明A x xA
t 是永真式。
(2) 任取解释I 和I中赋值v，
( xA)( v) 1
I
当且仅当I ( xA)(v) 0
当且仅当存在d D I 使得I ( A)( v[ x/d]) 0
当且仅当存在d D I 使得I ( A)(v [ x/ d]) 1
当且仅当I ( x A)(v) 1
这表明xA x A 是永真式。
(3) 任取解释I 和I中赋值v，
I ( xA)(v) 0
当且仅当I ( xA)( v) 1
当且仅当存在d D I 使得I ( A)( v[ x/d]) 1
当且仅当存在d D I 使得I ( A)( v[ x/ d]) 0
当且仅当I ( x A)(v) 0
这表明xA x A 是永真式。
(4) 任取解释I 和I 中赋值v ，若I ( x(A B) ) v() 1 ，则存在d D I 使得
I ( A B)(v[ x / d ] ) 1 ，I ( A)(v [ x/d ])I ( B)(v[ x / d ] ) 1 ，I ( xA)( v) 1 且
I ( xB)( v) 1，I ( xA xB)( v)1。这表明x( A B) xA xB 是永真式。
(5) 任取解释I 和I 中赋值v，若I ( x( A B) )v() 0 ，则存在d D I 使得
I ( A B)(v [ x/ d ])0 ，I ( A)(v [x / d ] ) I (B)(v[ x / d ] ) 0 ，I ( xA xB)( v) 0 。这表明xA xB x( A B) 是永真式。
(6) 任取解释I和I 中赋值v，若I ( x( A B))( v) I ( A)( v) 1，则对于每个d D ，
I
I ( A B)(v[ x / d ])1，因为x不是A 的自由变元，所以I ( A)(v[ x/d])I ( A)( v) 1，
因此I ( B)(v[ x/ d ] ) 1 ，I ( xB )(v) 1。这表明x(A B) ( A xB)是永真式。13.设A1 是公式 A 的闭包，A2 是x1 x n A，其中Var ( A) { x1, , x n} 。证明：
(1) A 是永真式当且仅当A1是永真式；
(2) A 是可满足式当且仅当 A 是可满足式。
2
证
明(1) （）首先证明：若 A 是永真式，则x A 是永真式。设A是永真式。任取解
释
I和I 中赋值v，任取d D I ，因为v[ x/d]也是I 中赋值，所以I ( A)(v[ x / d ])1，
I ( xA v 。xA是永真式。若A 是永真式，则x n A 是永真式，?，x1 x n A是
)( ) 1
永真式。
（）因为x1 x n A A是永真式，所以若x1 x n A是永真式，则A是永真式。
(2) （）因为A x1 x n A是永真式，所以若解释I和I 中赋值v满足A，则I和v
满
足x x A
1 。
n
（）若解释I和I 中赋值v满足x x A
1 n ，则
有d1, ,d 使得
n D
I
I(A v[ x1 d1 x n d n ，I 和I 中赋值v[ x1 / d1, ,x n / d n]满足A。
)( / , , / ]) 1
14. 判断以下等值式是否成立，并说明理由。
(1) x( P(x) Q( x)) xP( x) xQ( x)
(2) x( P(x) Q( x)) xP( x) xQ( x)
(3) xP( x) P(x)
(4) x xP (x) xP( x)
(5) x( P(x) yQ( y)) xP( x) yQ( y)
(6) x( P(x) yQ( y)) xP (x) yQ( y)
解(1) 不成立。取解释I 如下。
I ，P I (b) 1，Q I (a) 1，Q I (b) 0
{a b
D I , } ，P (a) 0
则I ( x( P(x) Q( x))) 0 且I ( xP (x) xQ (x)) 1 。
(2) 不成立。取解释I 如下。
I
，P I (b) 1，Q I (a) 1，Q I (b) 0
D I ，P (a) 0
{a,b}
则I ( x( P(x) Q( x))) 0且I ( xP( x) xQ( x)) 1 。
(3) 不成立。取解释I 和I中赋值v 下。
I ，P I (b) 1，v( x) b
, }
D I {a b ，P (a) 0
则I ( xP( x))( v) 0 且I (P( x))( v) 1。
(4) 成立。任取解释I 和I 中赋值v，因为x 不是xP(x )中的自由变元，所以对于每个
d D ，I ( xP( x))( v[ x / d]) I ( xP( x))( v) 。
I
I ( x xP( x))( v) 1
当且仅当对于每个 d D I ，I ( xP( x))( v[ x/d]) 1
当且仅当I ( xP( x))( v) 1
(5) 不成立。取解释I 如下。
I
，P I (b) 1，Q I (a) 1，Q I (b) 0
D I {a,b ，P (a) 0
}
则I ( x( P( x) yQ ( y))) 0 且I ( xP( x) yQ( y)) 1。
(6) 不成立。取解释I 如下。
I ，P I (b) 0，Q I ( a) Q I (b) 1
{a, b}
D I ，P (a) 1
则I ( x( P( x) yQ ( y))) 0 且I ( xP (x) yQ( y)) 1 。
15. 设A, B 是任意公式，证明以下等值式。
(1) x
x A yA ，其中y 在A 中不出现。
y
(2) x( A B) x A x B
(3) x y(A B) xA yB ，其中x 不是B 的自由变元，y 不是A 的自由变元。
(4) x y(A B) x A yB ，其中x 不是B 的自由变元，y 不是A 的自由变元。
(5) x y(A B) x A yB ，其中x 不是B 的自由变元，y 不是A 的自由变元。
(6) x y A y x A
证明(1) x x
x A x A y A
y y A
y
(2) x( A B) x( A B) x A xB x A xB xA xB
(3) x y(A B) x( A yB )x A y B
(4) x y( A B) x(A yB) x A yB
(5) x y(A B) x(A yB) x A yB
(6) 任取解释I 和I中赋值v，
I ( x yA)( v)0
当且仅当有d D I 使得I ( yA)( v[ x /d]) 0
当且仅当有d, c D I 使得I ( A)( v[ x/d][ y / c]) 0
当且仅当有d, c D I 使得I ( A)( v[ y/c][ x/d]) 0
当且仅当有c D I 使得I ( xA)(v[ y/c]) 0
当且仅当I ( y xA)( v) 0
16. 判断以下逻辑推论关系是否成立，并说明理由。
(1) x( P(x) Q( x)) | xP( x) xQ( x)
(2) xP (x) xQ( x) | x( P(x) Q( x))
(3) x( P(x) xQ (x)) | x( P( x) Q( x))
(4) x( P(x) xQ (x)) | x( P( x) Q( x))
(5) x( P( x) Q(x)) , xP( x) | xQ (x)
(6) x yP( x, y) | xP( x, x)
解(1) 不成立。取解释I 如下。
I ，P I (b) 1，Q I (a) 1，Q I (b) 0
, }
D I {a b ，P (a) 0
则I ( x( P( x) Q( x))) 1 且I ( xP( x) xQ( x)) 0 。这表明
x( P( x) Q( x)) |/ xP(x) xQ( x) 。
(2) 不成立。取解释I 如下。
I
P I (b) 1，Q I (a) 1，Q I (b) 0
D I {a,b} ，P (a) 0 ，
则I ( xP(x) xQ(x )) 1 且I ( x(P(x) Q(x ))) 0 。这表明
xP( x) xQ(x) |/ x(P( x) Q( x)) 。
(3) 不成立。取解释I 如下。
I I
，Q I (a) 1，Q I (b) 0
D I {a,b} ，P (a) P (b) 0
则I ( x(P( x) xQ( x))) 1 且I ( x( P(x) Q( x))) 0 。这表明x(P(x) xQ( x)) |/ x( P( x) Q( x)) 。
，
I I
(4) 若解释I 使得I ( x( P(x) Q (x))) 0 ，则有d D I 使得P (d) Q (d) 0
P I 且Q I (d) 0 ，I ( xQ( x)) 0 ，I ( x(P( x) xQ( x))) 0 。这表明
(d) 1
x(P(x) xQ( x)) | x(P(x) Q(x)) 。
(5) 不成立。取解释I 如下。
I
，P I (b) 0，Q I (a) Q I (b) 0
D I {a,b} ，P (a) 1
则I ( x(P( x) Q( x))) I ( xP( x)) 1 且I ( xQ( x)) 0 ，这表明
x(P( x) Q(x)) , xP( x) | xQ( x)。
/
(6) 不成立。取解释I 如下。
I I I I
D I {a,b} ，P (a, b) 1
，P (a,a) P (b ,a) P (b ,b) 0
则I ( x yP( x, y)) 1，但I ( xP( x, x)) 0 。所以x yP( x, y) |/ xP( x, x) 。
17. 设A, B 是任意公式，证明以下结论。
(1) x( A B) |xA xB
(2) x( A B) , xA | xB
(3) xA y x yA
x | ，其中x 对于A 中的y 是可代入的。
(4) x A xB | x(A B)
证明(1) 若解释I 和I 中赋值v 使得I ( x( A B))( v) 1 ，则有d D I 使得
I ( A B )(v[ x/d]) 1 ，I ( A)(v[ x/d]) I ( B)(v[ x / d ]) 1 ，I ( xA)( v ) 1 且
I ( xB)( v) 1，I ( xA xB)( v)1。这表明x( A B) | xA xB 。
(2) 若解释I 和I 中赋值v 使得I ( x( A B))( v) I ( xA)( v) 1，则对于每个d D ，
I
I ( A B)(v[ x /d]) I ( A)(v[ x / d ]) 1 ，I (B)( v[ x / d ]) 1 ，I ( xB)( v) 1 。这表明x( A B), xA | xB 。
(3) 若解释I 和I 中赋值v 使得I ( xA y )(v) 1
y
x ，则有d D I 使得I(A)(v[ x/ y]) 1
x ，
因为I(A y)(v[x / d]) I ( A)(v[ x/d][ y/I ( x)(v[ x / d])]) I(A)(v[ x / d][ y / d])
x ，所以I ( A)(v[ x / d][ y/ d]) 1 ，I ( yA)( v[ x /d]) 1 ，I ( x yA)( v) 1 。这表明
x y
A x | x yA。
(4) 若解释I 和I 中赋值v 使得I ( x(A B))( v) 0 ，则对于每个d D I ，
I ( A B)(v[ x / d]) 0 ，I ( A)( v[ x/d]) 1 且I (B)(v[ x / d ]) 0 ，因此I ( xA)(v ) 1 且
I ( xB)( v) 0，I ( xA xB)( v) 0 。所以x A xB | x( A B) 。
18. 设变元x 既不是公式B 中的自由变元，也不是公式集中任何公式的自由变元， A 是公
式。若{ A}| B ，则{ x A} | B 。
证明设解释I 和I 中赋值v 满足{ x A} ，则I ( xA)( v) 1 ，有d D I 使得
I ( A v x d]) 1。因为x不是公式集中任何公式的自由变元，所以I和v[ x / d]也满足，
)( [ /
I 和v[ x / d]满足{ A} 。又因为{ A} | B ，所以I (B)(v[ x / d]) 1，因为x 不是B
中的自由变元，因此I ( B)(v) 1。这表明{ x A}| B 。
19. 设是公式集合，A 是公式，则| A 当且仅当{ A} 不可满足。
证明设{ A} 可满足，解释I 和I 中赋值v 满足{ A} ，则I 和v 满足且
I ( A)( v) 0 ，所以| / A 。
设|/A ，则有解释I 和I 中赋值v 满足且I ( A)( v) 0 ，所以I 和v 满足{ A} 。
因此，{ A} 可满足。
20. 判断以下公式集合是否可满足，并说明理由。
(1) { P(t) | t是项} { xP( x)}
(2) { x P(x, x), x y z( P( x, y) P( y, z) P(x, z)) , x yP( x, y)}
解(1) 可满足。取解释I 和I中赋值v如下。
I I
D {1, 2} ，P (1) 0，P (2) 1，
I
对每个常元a，a I 1；
I x x
对每个n 元函数符号f，f ( , , ) 1；
1 n
对每个变元x，v(x) 1。
可归纳证明：对每个项t，I (t)(v) 1。
I 和v满足{ P(t) | t是项} { xP(x)} 。
(2) 可满足。取解释I 和I 中赋值v 如下。
I
当且仅当x y
D 为自然数集，P (x, y) 1
I
则I和v满足{ x P( x, x) , x y z( P( x, y) P( y, z) P( x,z)) , x yP( x, y)} 。
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
离散数学复习题参考带答案
一、选择题：（每题2’） 1、下列语句中不是命题的有（ ）。 A ．离散数学是计算机专业的一门必修课。 B ．鸡有三只脚。 C ．太阳系以外的星球上有生物 。 D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（ ）。 A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的 C ． 当A 的真值为真时，B 的真值也为真 D ． A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（ ）。 A ． 010，100，101，110，111 B ． 010，100，101，111 C ． 全体赋值 D ． 不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为（ ）。 A ．2 B ．3 C ．5 D ．0 5、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 6、下述公式中是重言式的有（ ）。 A ．(P ∧Q) (P ∨Q) B ．(P Q) (( P Q)∧(Q P)) C ．(P Q)∧Q D ．P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0 B ．1 C ．2 D ．3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（ ）。 A ．m 001∧m 011∧m 110∧m 111 B ．M 000∧M 010∧M 100∧M 101 C ．M 001∧M 011∧M 110∧M 111 D ．m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是（ ）。 A ．(x)A(x) ( x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（ ）。 A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C ．x ( P(x) Q ) x P(x) Q D ． x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（ ）。 A ．x y （x·y=1） B ．x y （x·y=0） C ． x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（ ）S 。 A ．{{1,2}} B ．{1,2 } C ．{1} D ．{2} 13、下列是真命题的有（ ）。 A ．{a}{{a}} B ．{{}}{,{}} C ．{,{}} D ．{}{,{}}
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学 第2章 习题解答
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
离散数学习题三 含答案
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。
离散数学课后习题答案(左孝凌版)
离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：
离散数学课后习题答案_屈婉玲(高等教育出版社)
第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p)
离散数学课后习题答案第二章
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学 第2章 习题解答
习题 2.1 1．将下列命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)∧B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)∨B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A(a)∧A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，则2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a) 2．将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
离散数学复习题及标准答案
1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学部分答案
第十四章部分课后习题参考答案 5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=? 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ?， )(),(D D ++?δ,)(),(D D --?δ. 解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G 的度数之和为：1262=? 设2度点x 个，则1221513=+?+?x ，2=x ，该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设有3个4阶4条边的无向简单图G 1、G 2、G 3，证明它们至少有两个是同构的。 证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学答案第二章习题解答
习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
离散数学复习题参考带答案
. 一、选择题：（每题2’） 1、下列语句中不是命题的有（）。 A．离散数学是计算机专业的一门必修课。B．鸡有三只脚。 C．太阳系以外的星球上有生物。D．你打算考硕士研究生吗? 2、命题公式A与B是等价的，是指（）。 A．A与B有相同的原子变元B．A与B都是可满足的 C．当A的真值为真时，B的真值也为真D．A与B有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（）。 A．010，100，101，110，111 B．010，100，101，111 C．全体赋值D．不存在 4、合式公式?(P∧Q)→R的主析取范式中含极小项的个数为（）。 A．2 B．3 C．5 D．0 5、一个公式在等价意义下，下面哪个写法是唯一的（）。 A．析取范式B．合取范式C．主析取范式D．以上答案都不对 6、下述公式中是重言式的有（）。 A．(P∧Q) → (P∨Q) B．(P?Q) ? (( P→Q)∧(Q→P)) C．?(P →Q)∧Q D．P →(P∧Q) 7、命题公式(?P→Q) →(?Q∨P)中极小项的个数为（），成真赋值的个数为（）。 A．0 B．1 C．2 D．3 8、若公式(P∧Q)∨(?P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。 A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101 C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m101 9、下列公式中正确的等价式是（）。 A．?(?x)A(x) ? (?x)?A(x) B．(?x) (?y)A(x, y) ? (?y) (?x) A(x, y) C．?(?x)A(x) ? (?x)?A(x) D．(?x) (A(x) ∧B(x)) ? (?x) A(x) ∨(?x) B(x) 10、下列等价关系正确的是（）。 A．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) B．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) C．?x ( P(x) →Q ) ??x P(x) → Q D．?x ( P(x) →Q ) ??x P(x) → Q 11、设个体域为整数集，下列真值为真的公式是（）。 A．?x?y（x·y=1）B．?x?y（x·y=0）C．?x?y（x·y=y）D．?x?y（x+y=2y） 12、设S={?,{1},{1,2}}，则有（）?S。 A．{{1,2}} B．{1,2 } C．{1} D．{2} 13、下列是真命题的有（）。 A．{a}?{{a}} B．{{?}}∈{?,{?}} C．?∈{?,{?}} D．{?}∈{?,{?}} 14、设S={?,{1},{1,2}}，则2S有（）个元素。 A．3 B．6 C．7 D．8
离散数学答案(尹宝林版)第二章习题解答
第二章 谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。
《离散数学》试习题及答案
欢迎共阅 一、填空题 1设集合A,B ，其中A ＝{1,2,3},B={1,2},则A-B ＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a ,b },B={1,2},则从A 到B 的所有映射是_______________________________________,其中双射的是__________________________. 4.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题