习题参考解答
习题1.1
1、（3）P：银行利率降低
Q：股价没有上升
P∧Q
（5）P：他今天乘火车去了
Q：他随旅行团去了九寨沟
Q
P?
（7）P：不识庐山真面目
Q：身在此山中
Q→P，或～P→～Q
（9）P：一个整数能被6整除
Q：一个整数能被3整除
R：一个整数能被2整除
T：一个整数的各位数字之和能被3整除
P→Q∧R ，Q→T
2、（1）T （2）F （3）F （4）T （5）F
（6）T （7）F （8）悖论
习题 1.3
1（3）
)
(
)
(
)
(
)
(
)
(
)
(
R
P
Q
P
R
P
Q
P
R
Q
P
R
Q
P
→
∨
→
?
∨
?
∨
∨
?
?
∨
∨
?
?
∨
→
（4）
()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右
2、不， 不， 能 习题 1.4
1(3) (())~((~))
(~)()~(~(~))(~~)(~)
P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取式
)
()()()()()()()()()()()()()())(())(()()(())
()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取式
(2) ()()(~)(~)
(~(~))(~(~))(~~)(~)(~~)
P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、
()~()
(~)(~)
(~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价
3、解：根据给定的条件有下述命题公式： （A →（C ?D ））∧～（B ∧C ）∧～（C ∧D ）
?（～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） ?（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨
（～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）
?（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（～C ∧D ∧～C ）） ∧（～C ∨～D ）
?（～A ∧～B ∧～C ）∨（C ∧～D ∧～B ∧～C ）∨（～C ∧D ∧～B ∧～C ）∨ （～A ∧～C ∧～C ）∨（～C ∧D ∧～C ∧～C ）∨（～A ∧～B ∧～D ）∨ （C ∧～D ∧～B ∧～D ）∨（～C ∧D ∧～B ∧～D ）∨（～A ∧～C ∧～D ）∨ （～C ∧D ∧～C ∧～D ）（由题意和矛盾律）
?（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ）∨（C ∧～D ∧～B ） ?（～C ∧D ∧～B ∧A ）∨ （～C ∧D ∧～B ∧～A ）∨ （～A ∧～C ∧B ）∨ （～A ∧～C ∧～B ）∨ （～C ∧D ∧A ）∨ （～C ∧D ∧～A ）∨ （C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ）
?（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～A ∧～C ∧B ∧～D ）∨ （～A ∧～C ∧～B ∧D ）∨ （～A ∧～C ∧～B ∧～D ）∨
（～C ∧D ∧A ∧B ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ）∨ （～C ∧D ∧～A ∧～B ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ） ?（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ） ∨（C ∧～D ∧～B ∧A ）
?（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨（C ∧～D ∧～B ∧A ） 三种方案：A 和D 、
B 和D 、
A 和C
习题 1.5
1、 （1）需证()(())P Q P P Q →→→∧为永真式
()(())~(~)(~())
~~(~)(()(~))
~(~)(~)()
P Q P P Q P Q P P Q P P
P Q P Q T
P Q P Q T P Q P P Q →→→∧=∨∨∨∧∨=∨∨∧∨=∨∨∨=∴→?→∧Q （3）需证S R P P →∧?∧为永真式
S
R P P T S F S R F S R P P ?∧?∧∴?→?→∧?→∧?∧Θ
3A B A B ?∴→Q 、为永真式。即~A B ∨永真
~~~~A B B A B A ∨?∨?→Q 永真
A B ∴?当且仅当~~B A ?
4、设： P ：珍宝藏在东厢房 Q ：藏宝的房子靠近池塘 R ：房子的前院栽有大柏树 S ：珍宝藏在花园正中地下 t ：后院栽有香樟树
m ：珍宝藏在附近（后院）
命题化后进行推理：
(~)()()()~()()()
~()()
()
Q p R P Q R S t m p R P R S t m R R S t m S t m →∧→∧∧∨∧→?∧→∧∨∧→?∧∨∧→?∧→ 即S 为真，珍宝藏在花园正中地下
5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1) 习题 1.6
1.（1）~,~~P Q R Q P R ∨→?→ 证：利用CP 规则
① P P (附加前提) ② ~P Q P ∨ ③ Q T ①②I ④ ~R Q
P →
⑤~R T③④I
⑥结论成立CP规则①⑤
（2）()(),()
∨→∧→?→
P Q R S SVE B P B
证：①P P(附加)
②P∨Q T①
③()()
∨→∧
P Q R S P
④R S T
∧②③
⑤S T④
⑥S∨E T⑤
⑦S∨E→B P
⑧B T⑥⑦
⑨P B CP
→(①⑧)
2. (2) P：无任何痕迹
Q：失窃时，小花在OK厅
R：失窃时，小英在OK厅
S：失窃时，小胖在附近
T：金刚是偷窃者
M：瘦子是偷窃者
命题可符号化为：
{M
→
?
→
R
∨,
,
,}
,
,
→
?
?
T
S
R
P
Q
S
Q
P→
R
证：①P P
②P
→P
S~
③S
~T①②
④R
~→P
S~
⑤R
~T③④
⑥R
Q∨P
⑦Q T⑤⑥
⑧T
Q→P
⑨T T⑦⑧
∴金刚是窃贼。
3. (1) 不相容
(2) 相容()0
R
Q
P
=
=S
=
,1=
（3）不相容
（4）不相容
4. (1)证：()()()P
∨
∧
→
∧
~
∧
~
(
→)
P
S
Q
→
S
Q
P∧
Q
R
()()()()P
∨
∧
∨
∧
~
∨
~
~
~
?~
R
Q
P
Q
S
S
∨
P∧
Q
∧
即{}P
~
,
~
~
~∨
∨
=
∨
∨
Φ
,
S
Q
P
Q
,
S
~
R
P,
Q
利用消解原理：
①P P
②Q
~∨P
P~
③Q
~①②
④Q
~P
P∨
⑤~P③④
⑥~F
∧□①⑤
P
P=
习题 2.1
1. (1)()x A ：x 是实数 ()x B ：x 是有理数
()()()()∧→?x A x B x ()()()∧→??x B x A x ()()()x B x A x ∧?
(2)()x A ：x 是直线
()y x F ,：x 与y 平行
()y x G ,：x 与y 相交
()()()()()[]b a G b a F b A a A b a ,,??→∧??
(3))(x A ：x 是会员
)(x C ：x 有意义
),(y x F ：x 参加y
a ：这个活动
()()()()a x F x A x a C ,→?→
或者
()()()a C a x F x A x ?→→??),(
（4） ()x A ：x 是正整数
)(x B ：x 是合数 )(x C ：x 是质数
()()()()x C x B x A x ?→?
（5） ()x A ：x 是人 B （x ）：x 存钱 a ：利息
P:存钱有利息 ()y x F ,：x 想有y
()()()()()()()[]x B x A P a x F x B x A x ?∧→?∧→∧?,
2.(1)()()()()()()()210210Q R R P P P ∨∨∧∧∧ (2)()()][()()]()()[[221100Q P Q P Q P →∧→∧→ 4.(1)
()()()[()]()()z y x R z t y Q y x P y x ,,,,?∨→??
习题 2.2
1.（1）D ：数 ()()xy y x f x x A ==,0
:
()()()()[]()()()1,11,+-?→-?∧∨→??x x f A x A y A x A y x f A y x
可满足式
(2)()x x A :是诚实的人
()x x B :讲实话
a ：小林
()()[]()()a B a A x B x A x ?→?∧→? 可满足式 (3) ()x x A :不便宜
()x x B :是好货
()x y x F :,买的y
a ：衣服
b ：小王
()()[]()()()a B a A b a F x B x A x →∧∧→?,
可满足式
（4）()x x A :是作家 ()x x B :懂得人性本质
()x x C :是诗人
()x x D :是真正的
()x x E :能刻画人们心世界
()x x F :很高明
()x y x P :,创作了y
a ：莎士比亚
b ：哈姆雷特
()()()()()()()[]()()[]
)(),()()()()()(,)(x D b x P x C x x E x B x A x b a P x D x E x C x F x B x A x →∧?∧∧?∧??∧∧?→?∧∧→∧?
2.(1) T
3.(1) F (2) T
4. 0:)( ,:),( :>=y y Q e y y x P D x 实数 习题 2.3
1.（1）()()][y Q x P y x →??
()[()]y Q x P y x ∨???~ ()[()]y yQ x P y x ?∨???~
())(~y yQ x P x ?∨??
())(~y yQ x xP ?∨??
()()())(y Q y x P Ax ?→?
2. 不成立
D={0,1,2} 1)
2(,0)1(,1)0( 0)2(,1)1(,0)0(Q Q Q P P P
3.(1)()()()()()y P y x P x ?→?~
()()()()()y P y x P x ?∨??~~ ()(()()()()y P y x P x ?∨??~~ ()()()()()y P y x P x ~?∧??
()()()()()y P x P y x ~∧??? ——skolem 式
(2)()()()()()()z y Q z y x P x ,~??→?
()()()()()()z y Q z y x P x ,~~??∨?? ()()()()()z y Q z y x P x ,~??∧??
()()()()()()z y Q x P z y x ,~∧???? ——前束式
()()()()()()y x f y Q x P y x ,,~∧??? ——skolem 式
1. （1）证：在某个解释下，()()()][)(y Q x P y x ∧??取值1，必有D b a ∈,,
()()b Q a P ∧，取值1，因此，D a ∈? ()a P 取值1。 ()()x P x ?∴取值1，由定义，蕴含关系成立。
（2）①()()()()()()()a Q x P x a Q x P x ~~~∨??∧?
()()()a Q x P x ~→??
(2) 证: 在某个解释下，()()()()a Q x P x ∧?~取值1 即()()()a Q x P x ∧?取值0，分二种情况：
i)()()0=?x P x ，则无论()a Q 为何值，()()()a Q x P x ~→?取值1。 ii) ()()()10
=?=x P x a Q ，则()()()a Q x P x ~→?取值1
由定义，蕴含关系成立。
1（2）（反证法）
①()()()][x Q x P x →?~ P ②()()()][x Q x P x →? T ①,E ③()(()()][x Q x P x ∨→?~~ T ②,I ④()()()()x Q x P x ~∧? T ③,I ⑤()()x Q x P ~∧ US ④ ⑥()x P T ⑤,I ⑦()()x P x ? UG ⑥ ⑧()()()()x Q x x P x ?→? P ⑨()()x Q x ? T ⑧,I ⑩()x Q ~ T ⑤,I ○
11()x Q US ⑨ ○12□ T ⑩○11I 2. (1) 错误，应换元，即
①()()()x Q x P x →?，
②()()x Q y P → （2） 正确
（3） 错误，a 、b 应是同一个常元
（4） 错误，因为在()()())]([x R x Q x x P ∧?∨ 中x 并不是自由出现 (5) 错误，因为在()()()x Q x P x →?中，前件是命题，
而后件不是命题
（6）错误，因为a、b并不是同一个常量
（7）错误，①②和③④的顺序不对
应先使用ES，再使用US
3(1)解：设F(x,y):x≥y; G(z):z≥0 ; f(x,y)=x-y 前提：
①?(x)?(y)（F(x,y)→G(f(x,y))
②?(x)?(y)（?F(x,y)→?G(f(x,y))
③?(x)?(y)(?G(f(x,y)→ G(f(y,x)))
结论：?(x)?(y)（G(f(x,y))∨G(f(y,x))）
证明（反证法）：
①??(x)?(y)（G(f(x,y))∨G(f(y,x))）
②（?ｘ）（?ｘ）?（G(f(x,y))∨G(f(y,x))）
③?G(f(a,b))∧?G(f(b,a))
④?(x)?(y)（F(x,y)→G(f(x,y))
⑤F(a,b)→G(f(a,b))
⑥?G(f(a,b))→?F(a,b)
⑦?(x)?(y)(?G(f(x,y)→ G(f(y,x)))
⑧? G(f(b,a))→G(f(a,b))
⑨?(x)?(y)（?F(x,y)→?G(f(x,y))
⑩?F(a,b)→?G(f(a,b))
⑾ G(f(a,b)) → F(a,b)
⑿?F(a,b) ∧ F(a,b)
4. （2）
证：首先，将结论否定否作为前提加入到原有前提中
()()()()()()()[[{]}()()()()∧?∧?∧→∨?→?x Q x x P x x R x Q x P x x P x
()()()()][x R x R y x ∧??~
()()()()()()[{()]}()()()()∧?∧?∧∨∨?∨??v Q v u P u x R x Q x P x x P x ~~ ()()()()][y R w R y w ∧??~
()()()()()()()()()()()()[]x R x Q x P x R x P y w v u x ∨∨∧∨??????~~~ ()()()()()]w R w R u R u P ~~∨∧∧∧
()()()()()()()()()()[()()]b Q a P x R x Q x P x R x P y w x ∧∧∨∨∧∨????~~~
()()()]y R w R ~~∨∧ Skolem 式
子句集为()()()()()()()()()}{y R w R b R a P x R x Q x P x R x P ~~,,,~~,~∨∨∨∨ ①()()x R x P ∨~ ②()a P
③()x R ①,②代换{a/x} ④()c R ③代换{c/x} ⑤()()y R w R ~~∨
⑥()y R ~ ④,⑤代换{c/w} ⑦()c R ~ ⑥代换{c/y} ⑧□
习题 3.4 3、
习题 5.2 2.
习题 5.3
2. （3）“?”R 是对称的，设
R y x ∈,则 R
x y ∈,1,-∈?R y x
R x y R y x R x y >∈?<>∈∴<>∈<-,,,1
Θ，即R R =-1
“?” R y x R R ∈?=-,1
，由1
-R
的定义，1,-∈R x y
R x y ∈∴,，即R 是对称的。
（5）“?”R 是传递的，对2,R z x >∈
B
A A A
B A B A A B
A B A x x x x x x x x x x x x x x x x 2222B A B A 22222B A 2 B A B A 2222)1(B B
B I I I I Y Y I I Y ∈?∈?∈??????∈∈?∈?=∈??????∈∈?∈，由于上述过程可逆”如“和和”）“（等号成立的条件为：或或φ
即R R ?2
“?”R ，R ?2，对R z y R y x >∈<>∈
的定义，
有R z x R
R z x >∈∴∈<,,2，即R 是可传递的。
4. 解：21R R R Y Θ=，且Φ=21R R I 212
1A A A R R R m m m Y Y ==∴
∴==∴,
21
5
231A A I R I R 需3|m ，5|m
15=?m ，即 16=n
R R R R R R ===2116
216116Y Y
故使n m
R R
=的最小正整数16,
1==n m
习题 5.4 2、解：
???
?
??????
??
?
?
?=00
01
100001000010000000000000 000000010000000000000000000101000010
R M ????????????
? ??=11
111111
11111111
100010001000100011110000
0000000
01000011101110111)(R t M
3. (3)证：2
)(1
)(121
1i
R U R t i
R U R t i i ∞
=∞
===Θ
i i R R U R R t )()(21121Y Y ∞
==
由归纳法可证：对i R R i
R i R N
i )(2
1 21Y Y ?∈?+
R z x R
z y R y x A y >∈∴<>∈<>∈
∈?,,,
)()()21
(21)()(2121111121R R t R R U i
R i R U i R U i R U R t R t i i i i i Y Y Y Y Y =?=???? ?????? ??=∴∞=∞=∞=∞= (4)证：①()
i i R U R t R R
R ∞
=+
+
+
+===1
)(Θ
()
()()()()j j R t U R t R ∞
=+
+
+==∴
1
由归纳法可证：()()()R t R t N j j =∈?+
()
()()()()()+∞
=∞
=+
+====∴
R R t R t U R t U R j j
j 1
1
③()R t I R R R R A Y Θο==*+
*
()()()R t R I R R t I R R R A A οY οY οο==∴* ()()+===R R t R t R R οY
习题 5.5
1. 证：(){}+∈=N b a b a A ,|,Θ
()()(){}bc ad d c b a R ==|,,,
①自反性 由A 的定义，N b a ba
ab ∈=,
()()()R b a b a ∈∴
,,,
②对称性 设()()()R d c b a ∈,,,，则bc ad = 即 ()()()R b a d c da
cb ∈∴
=,,,
③传递性 设()()()R d c b a ∈1111,,，则1111c b d a =
()()()R d c d c ∈2211,,，则2121c d d c =
2121211211211c b d a c d b d c b d d a =?==?
()()()R d c b a ∈∴
2211,,,
3. 解：{}{}{}{}3,4,2,1 ,,4,3,2,10==S A Θ
设{}{}3,4,3,2,121==A A
()()()()()()()()()(){}33442414422212412111，，，，，，，，，，，，，，，，，，R =∴
4. 解：∵每个集合的划分就可以确定一个等价关系
∴集合有多少个划分就可以确定多少个等价关系
154
1
424344=+++C C C C 种。 5. 解：
①21UR R 不是A 上的等价关系 ②21R R ?是A 上的等价关系 ③()21R R r - 是A 上的等价关系 ④21oR R 不是A 上的等价关系 习题 5.6 2. 解：{}c b a A ,,=
()()()()()()(){}c b a c b c a b a c b a A ,,,,,,,,,,,,2Φ=
3. 解：集合A 上的空关系Φ、恒等关系I A 都是等价关系和偏序关系。
6. 解：()d c b a A ,,,=
<2C
,?>
Φ
{b,c}
()()()()()()()()()()()()()()(){}
d c b a d c a d c b d b a c b a d c d b c b d a c a b a d c b a A ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2Φ=()()()()()()()()()()()()d b a c b a d c d b c b d a c a b a d c b a ,,,,,,,,,,≤≤≤≤≤≤≤≤≤≤≤≤Φ()()()d c b a d c b d c a ,,,,,,,≤≤≤
7. 证：i ）自反性，对()R b b A B b ∈∴
?∈?,,，（R 的自反性）
显然()()B B R b b B
B b b ?∈∴
?∈I
,,
ii)反对称性，对()()B B R a b B B R b a B b a ?∈?∈∈?I I ,,,,
,
即()()R a b R b a ∈∈,,,，由R 的反对称性，b a =?
iii)传递性，对B c b a ∈?,,，设()()B B R c b B B R b a ?∈?∈I I ,,,， 则()R b a ∈,，()R c b ∈,。
由R 的传递性，()R c a ∈,，显然()B B c a ?∈,
()B B R c a ?∈∴
I
,
习题6.2 4、证：
2121b b B b b 1≠∈?，、）对
221121,A a a b ),f(a b )f(a f(x)==?∈?∴、是满射，
Θ )
b (g a ),b (g a )b (g a ),b (g a )x (g 12212211??∈∈，且的定义，由 12211221 )b (g a ),b (g a b )f(a ,b )f(a ==∈∈，有否则，如
为单射即与函数的定义相矛盾，g(x)), g(b )g(b 21≠∴
不一定是满射
并不能保证为单射时，对）而)x (f ,
)b (g ,B b )(2∴≠∈?φx g
7、证：
习题6.4:
3．证明：非空有限集A 与可数集B 的笛卡尔积A ×B 也是可数集。 证明：设A={a 1,a 2,…,a n ｝ B={b 1,b 2,…,b n ,…}
令B i ={(a i ,b 1),(a i ,b 2),…,(a i ,b n ),…} (i≤n),则
为满射
即令对为满射
）（为单射矛盾与即反证法：设不是单射，）（g )( , )( ))(()x ( , g 2g )(g )g()g(g 1:,:22112121z y g B y B y x f z x f g f g A x C,z f f x f )f(x )f(x )f(x )f(x )f(x A,x x C B g B A f =?∈?∴∈===?∈?∈?∴====?∈≠?→→οοΘοοο
A ×B= , 因为
B 为可数集，所以B i 为可数集。A ×B 为有限个可数集的并集。下面用归纳法证明有限个(m 个)可数集的并集为可数集。 设
C m ={c m1,c m2, …,c mn , …} 当m=2时，
构造双射f:N →C 1∪C 2,
N 1 2 3 4 5 6 … n -1 n … f(N) c 11 c 21 c 12 c 22 c 13 c 23 … c 1(n/2) c 2(n/2) … 所以2个可数集的并集为可数集。
假设m=k-1(k ≥3)时结论成立，即k-1个可数集的并集为可数集，记为D 。
则m=k 时，可以构造类似的双射g:N →D ∪C k ,所以为可数集。因而有限个可数集的并集为可数集。所以A ×B 是可数集。 习题9.1
1．设G 是一个(n,m)简单图。证明：m ≤ ,等号成立当且仅当G
是完全图.
证明：由欧拉定理，2m= ，d(k)表示第k 个结点的度
因为G 是简单图，所以d(k) ≤n-1,等号成立当且仅当G 是完全图
2m= ≤ , 所以 2m ≤n(n-1)
即 m ≤ =
1
k
i
i B =U 2
n C 1()n
k d k =∑1
()n
k d k =∑1
1
n
k n =-∑(1)
2
n n -2
n C
离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论
离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；
7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}
习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ →
（4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）
习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.
（2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表：
第一章部分课后习题参考答案 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 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （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)
离散数学课后习题答案(左孝凌版) 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）解：
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命
题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q
离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值：
（4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q,
其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1.
(4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的.
离散数学习题详细答案
————————————————————————————————作者：————————————————————————————————日期：
离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值：
证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。
3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使
习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组> 1-1，1-2 （1）解： 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）解： a)不是合式公式，没有规定运算符次序（若 规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（括弧不配对） d)不是合式公式（R和S之间缺少联结词） e)是合式公式。 （2）解： 习题 1-5 （1）证明： a)(P∧(P→Q))→Q (P∧(┐P∨Q))→Q (P∧┐P)∨(P∧Q)→Q (P∧Q)→Q ┐(P∧Q)∨Q ┐P∨┐Q∨Q ┐P∨T T b)┐P→(P→Q) P∨(┐P∨Q) (P∨┐P)∨Q T∨Q T c)((P→Q)∧(Q→R))→(P→R) 因为(P→Q)∧(Q→R)(P→R) 所以(P→Q)∧(Q→R)为重言式。 d)((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a) 因为((a∧b)∨(b∧c)∨(c∧a)) ((a∨c)∧b)∨(c∧a) ((a∨c)∨(c∧a))∧(b∨(c∧a)) (a∨c)∧(b∨c)∧(b∨a) 所以((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)为重言式。 （2）证明： a)(P→Q)P→(P∧Q) 解法1： 设P→Q为T （1）若P为T，则Q为T，所以P∧Q为T，故P→(P∧Q)为T （2）若P为F，则Q为F，所以P∧Q为F，P→(P∧Q)为T 命题得证 解法2： 设P→(P∧Q)为F ，则P为T，(P∧Q)为F ，故必有P为T，Q为F ，所以P→Q为F。 解法3： (P→Q) →(P→(P∧Q)) ┐(┐P∨Q)∨(┐P∨(P∧Q)) ┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) T 所以(P→Q)P→(P∧Q) b)(P→Q)→Q P∨Q 设P∨Q为F，则P为F，且Q为F， 故P→Q为T，(P→Q)→Q为F， 所以(P→Q)→Q P∨Q。 c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q 设R→Q为F，则R为T，且Q为F，又P∧┐P为F 所以Q→(P∧┐P)为T，R→(P∧┐P)为F 所以R→(R→(P∧┐P))为F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q成立。 （3）解： a) P→Q表示命题“如果8是偶数，那么糖果是甜的”。 b)a)的逆换式Q→P表示命题“如果糖果是甜的，那么8是偶数”。 c)a)的反换式┐P→┐Q表示命题“如果8不是偶数，那么糖果不是甜的”。 d)a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的，那么8不是偶数”。（4）解： a)如果天下雨，我不去。 设P：天下雨。Q：我不去。P→Q 逆换式Q→P表示命题:如果我不去，则天下雨。 逆反式┐Q→┐P表示命题:如果我去，则天不下雨 b)仅当你走我将留下。 设S：你走了。R：我将留下。R→S 逆换式S→R表示命题：如果你走了则我将留下。 逆反式┐S→┐R表示命题：如果你不走，则我不留下。 c)如果我不能获得更多帮助，我不能完成个任务。 设E：我不能获得更多帮助。H：我不能完成这个任务。E→H 逆换式H→E表示命题：我不能完成这个任务，则我不能获得更多帮助。 逆反式┐H→┐E表示命题：我完成这个任务，则我能获得更多帮助（5）试证明P Q，Q逻辑蕴含P。 证明：解法1： 本题要求证明(P Q) ∧Q P, 设(P Q) ∧Q为T，则(P Q)为T，Q为T ，故由的定义，必有P为T。 所以(P Q) ∧Q P 解法2： 由体题可知，即证((P Q)∧Q)→P是永真式。 ((P Q)∧Q)→P (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P ((┐Q∨┐P) ∧T) ∨P ┐Q∨┐P∨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)在两个个体域中都解释为)(x ?，在（a）中为假命题， xF 在(b)中为真命题。 (2)在两个个体域中都解释为)(x ?，在（a）(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ ((y ( )) ( H ) x , ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y 快 命题符号化为: ))) x F x y y→ ?? ∧ ? H G ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 离散数学~ 习题1.1 1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以 。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：?p→?q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：p?q ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p?q。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：?p→q；该命题是真命题。 ⑶原命题符号化为：p→?q；该命题是假命题。 ⑷原命题符号化为：?p→?q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：p?q；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：p?q；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：p?q；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：p?q；该命题是真命题。离散数学课后习题答案
离散数学课后习题答案_(左孝凌版)
屈婉玲版离散数学课后习题答案
离散数学(左孝凌)课后习题解答(详细)
相关主题
文本预览