离散数学习题五
习题五
1.设个体域D={a,b,c}，在D 中消去公式(()())x F x yG y ?∧?的量词。甲乙用了不同的演算过程：
甲的演算过程如下： (()())
(()(()()()))(()(()()()))(()(()()()))(()(()()()))
(()()())(()()())x F x yG y x F x G a G b G c F a G a G b G c F b G a G b G c F c G a G b G c F a F b F c G a G b G c ?∧???∧∨∨?∧∨∨∧∧∨∨∧∧∨∨?∧∧∧∨∨
乙的演算过程如下：
(()())()()
(()()())(()()())
x F x yG y xF x yG y F a F b F c G a G b G c ?∧???∧??∧∧∧∨∨
显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。
解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的
辖域缩小，因而演算简单。
2. 设个体域D={a,b,c}，消去下列各式的量词：
(1)(()())(2)(()())(3)()()(4)(,)())
x y F x G y x y F x G y xF x yG y x F x y yG y ??∧??∨?→??→?（
解：
（1）))()()(())()()((c G b G a G c F b F a F ∨∨∧∧∧ （2）))()()(())()()((c G b G a G c F b F a F ∧∧∨∧∧ （3）))()()(())()()((c G b G a G c F b F a F ∧∧→∧∧ （4）))()()(()),(),(),((c G b G a G y c F y b F y a F ∨∨→∨∨ 在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单
3. 设个体域D={1,2}，请给出两种不同的解释1I 和2I ，使得下面公式在1I 下都是真命题，而在2I 下都是假命题。 （1）(()())x F x G x ?→ （2）(()())x F x G x ?∧
解：
解释I1为：个体为实数集合R ，F(x)：x 为自然数，G(x)：x 为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题
解释I2为：个体域仍为实数集R ，F(x)：x 是无理数，G(x)：x 能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题
4. 给定公式()()A xF x xF x =?→?
（1）在解释1I 中，个体域1D ={a}，证明公式A 在1I 下的真值为1.
（2）在解释2I 中，个体域2D ={12,,,n a a a }，2n ≥,A 在2I 下的真值还一定是1吗？为什么？ 解：
（1）在I1下，1)()()()()()(?∨??→??→?a F a F a F a F x xF x xF （2）在I2下
))()()(())()()(()()(2121n n a F a F a F a F a F a F x xF x xF ∧∧∧→∨∨∨??→?
为可满足式，设F(x)：x 为奇数，2,,2,1,≥==n n i i a i ，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x 为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式
5. 给定解释I 如下： （a ）个体域D={3,4}； （b ）()f x 为(3)4,(4)3;f f ==
（c ）(,)F x y 为(3,3)(4,4)0,(3,4)(4,3) 1.F F F F ==== 试求下列公式在I 下的真值。
(1)(,)(2)(,)
(3)(,)((),()))
x yF x y x yF x y x yF x y F f x f y ??????→
解：
（1）
1
11))4,4()3,4(())4,3()3,3(())
4,()3,(()
,(?∧?∨∧∨?∨????F F F F x F x F x y x yF x
（2）
)4,4()3,4(())4,3()3,3(())
4,()3,((?∧∨∧?∧??F F F F x F x F x （3）
1
))))4(),4(()4,4(()))3(),4(()3,4(((())))4(),3(()4,3(()))3(),3(()3,3(((())))
4(),(()4,(()))3(),(()3,(((?→∧→∧→∧→?→∧→??f f F F f f F F f f F F f f F F f x f F x F f x f F x F x
6.甲使用量词辖域收缩与扩张等值式进行如下演算
)
,()()),()((y x G x xF y x G x F x →??→?
乙说甲错了，乙说的对吗？为什么？
解：乙说的对，甲错了，全称量词?的指导变元x ，辖域为)),()((y x G x F →，其中F(x)
与G(x,y)都是x 的约束变元，因而不能讲量词的辖域变小
7.请指出下面等值运算的两处错误
))
,())()((()),()(()(()),()(()((y x H y G x F y x y x H y G x F y x y x H y G x F y x →∧???→∧???→∧???
解：
演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词?，演算的第二步，在原错的基础上又用错了等值式
)),()()((y x H y G x F →∧和)),()()((y x H y G x F →∧不等值
8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式 （1）没有小于负数的正数
（2）相等的两个角未必都是对顶角 解：
（1）))()(())()((x F x G x x G x F x ?→??∧?? 其中F(x)：x 小于负数，G(x)：x 是正数
（2）)),(),()()((),(),()()((y x L y x H y F x F y x y x L y x H y F x F y x ?∧∧∧???→∧∧???其中F(x)：x 是角，H(x,y)：x=y ，L(x,y)：x 和y 是对顶角
9.设个体域D 为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下
设F(x)：x 是有理数，G(x ）：x 是无理数。)(),(x xG x xF ??都是真命题，于是，
))()(()()(x G x F x x xG x xF ∧???∧?
由于)()(x xG x xF ?∧?是真命题，故))()((x G x F x ∧?也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？ 解：存在量词对∧无分配律
10.在求前束范式时有人说)),()((y x G x F x ∧??已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？
解：在前束范式中，否定联结词不能在量词前面出现 11.有人说无法求公式
),())()((y x xG x G x F x ?→→?
的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？ 换名规则可以使两个指导变元不相同 12.求下列各式的前束范式： (1)),()(y x yG x xF ?→? (2))),,(),((z y x yG y x F x ?→? (3)),(),(y x xG y x xF ???
(4))),()(()),()((323222111x x L x x H x x x G x F x ?→?→→? (5))),()((),(2121211x x G x x F x x F x ??→→? 解：
（1）)),()((y z G x F y x →?? （2）)),,(),((z t x G t x F t x →??
（3）))),(),(()),(),(((43214321y x F y x G y x G y x F x x x x →∧→???? （4）))),()(()),()(((322211321y x L y H x y G y F y y y →→→??? （5）))),()(()((2112,121y x G x F x y F y y ?→→??
13.将下列命题符号化，要求符号化的公式权威前束范式： （1）有点火车比有的汽车跑的快 （2）有的火车比所有的汽车跑的快
（3）说有的火车比所有汽车跑得快是不对的 （4）说有的飞机比有的汽车慢也是不对的 解：
（1）)),()()((y x H y G x F y x ∧∧?? 其中F(x)：x 是汽车 G(y):y 是 火车 H(x,y)：x 比y 跑得快
（2）)))
x
G
y
F
∧
?其中F(x)：x是火车 G(y):y是汽车
?
H
x→
y
(
)
(
(
,
(y
(
)
x
H(x,y)：x比y跑得快
（3)))
y
F
x
x?
∧
G
?其中F(x)：x是火车 G(y):y是汽车?
∧
(
,
)
(
)
(
H
x
(y
y
H(x,y)：x比y跑得快
（4）))
y
F
x
x?
∧
y
?其中F(x)：x是飞机 G(y):y是汽车?
→
G
(
(
,
)
)
x
H
(y
(
H(x,y)：x比y跑得慢
14.在自然推理系统F中，指出下面各证明序列中的错误：
（1）①)
F?
x
→前提引入
(
)
(x
xG
②)
c
F→①EI规则
G
(
)
(c
（2）①)
→
?前提引入
(
x
xF?
)
(y
yG
②)
F
F→①EI规则
a
(b
(
)
（3）①)
y
F→前提引入
G
(
)
(y
②))
F
x→
?①EG规则
x
(
G
(
)
(x
（4）①)
a
F
F∧前提引入
(b
)
(
②))
F
x∧
?①EG规则
x
G
(
(
)
(x
（5）①)
c
G
F→前提引入
(c
)
(
②))
F
x→
?①UG规则
x
(
G
(
)
(x
解：（1）对)
F?
x
→不能使用EI规则，它不是前束范式，首先化成前束
(
)
(x
xG
范式))
?
→，因为量词辖域)
?
?
F→
(
)
x
y
G
(x
(
F→中，除了x
(
)
xG
(
)
(
)
(
x
(x
F
x
y
G
还有自由出现的y所以不能用EI规则
（2）对)
xF?
→
?也应该先化成前束范式才能消去量词，其前束范式x
(
)
(y
yG
为))
F
y
x→
?
?，要消去量词，既要用UI规则，又要用EI规则
G
x
)
(
(y
(
（3）这里A(y)=F(y)→G(y)满足要求
（4）这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b 不一定使F(b)为真
（5）这里，c为个体常项，不能对F(c)→G(c)引入全称量词
15.在自然推理系统F 中，构造下面推理的证明： （1）前提：)()),())()((()(x xF y R y G y F y x xF ?→∨?→? 结论：)(x xR ?
（2）前提：)())),()(()((x xF x R a G x F x ?∧→?
结论：))()((x R x F x ∧? （3）前提：)()),()((x xG x G x F x ??∨?
结论：)(x xF ?
（4）前提：)()),()(()),()((x xR x R x G x x G x F x ??∨??∨?
结论：)(x xF ?
（1）证明：1 ()xF x ? 前提引入
2 ()((()())R(y))xF x y F y G y ?→?∨→ 前提引入
3 ((()())R(y)y F y G y ?∨→ 1 2假言推理
4 ()F c 1 EI
5 (()())R(c)F c G c ∨→ 3 UI
6 ()()F c G c ∨ 4 附加
7 R(c) 5 6假言推理
8 ()xR x ? 7EG （2）证明：1 ()xF x ? 前提引入
2 ((x)),x (x)
(F(a)G(a))),G(a)I(y)H(a)(G(a)H(a)I(a))
x H F x x ?∨???→→?∧∨?∧→((x)(G(a)R(x)))x F ?→∧
前提引入
3 (c)F 1 EI
4 (c)(G(a)R(c))F →∧ 2 UI
5 G(a)R(c)∧ 3 4假言推理
6 R(c) 5化简
7 (c)R(c)F ∧ 3 6合取
8 ((x)R(x))x F ?∧ 7EG （3）证明：1 (x)xF ?? 前提引入 2 x (x)F ?? 1置换 3 F(c)? 2UI 4 x((x)())F G x ?∨ 前提引入 5 F(c)()G c ∨ 4UI
6F(c) 3 5析取三段论 7 (x)xF ? 6EG
(4)证明：1 x((x)())F G x ?∨ 前提引入 2 (y)()F G y ∨ 1 UI 3 x(G(x)())R X ??∨? 前提引入 4 G(y)()R y ?∨? 3 UI 5 (x)xR ? 前提引入 6 (y)R 5UI
7 ()G y ? 4 6析取三段论 8(y)F 27析取三段论 9 xF(x)? UG
16.找一个解释I ，在I 下，使得()()xF x xG x ?→?为真，而使得(()())x F x G x ?→?为假，从而说明()()(()())xF x xG x x F x G x ?→?≠?→?。
解：取个体域为自然数集合N ，F(x):x 为奇数，G(x):x 为偶数。显然在以上解释下
xF(x)xG(x)?→?为真而x(F(x)G(x))?→为假。
17.给定推理如下：
前提：(()()),(()())x F x G x x H x G x ?→??→ 结论：(()())x H x F x ?→?。 有些人给出的证明如下： 证明：
①()xH x ? 附加前提引入 ②()H y
①UI ③(()())x H x G x ?→ 前提引入 ④()()H y G y → ③UI ⑤()G y
②⑤假言推理 ⑥(()())x F x G x ?→? 前提引入 ⑦()()F y G y →? ⑥UI ⑧()F y ? ⑤⑦拒取式 ⑨()x F x ??
⑧UG
并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。 解：根据16题可知两公式并不等价。
18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。
证明：1 x(F(x)G(x))?→? 前提引入 2 x(H(x)G(x))?→ 前提引入 3 (y)()F G y →? 1 UI 4 H(y)G(y)→ 2UI 5 ()(y)G y F →? 3置换 6 H(y)F(y)→? 4 5假言三段论 7 (H(x)F(x))x ?→? 6 UG
19.在自然推理系统F 中，构造下列推理的证明： 前提：()()xF x xG x ?→? 结论：(()())x F x G x ?→
证明：1()(x)xF x xG ?→? 前提引入
2 ()(x)yF y xG ?→? 换名规则
3 y ((x)(x))x F G ??→ 化简
4 ((x)(x))x F G ?→ 3 EI
20.在自然推理系统F 中，构造下列推理的证明（可以使用附加前提证明法）： （1）前提：(()())x F x G x ?→
结论：()()xF x xG x ?→? （2）前提：(()())x F x G x ?∨ 结论：()()xF x xG x ??→?
证明：（1）. 1()xF x ? 附加前提引入 2 ()F y 1 UI
3 (()())x F x G x ?→ 前提引入
4 ()()F y G y → 3UI
5 ()G y 2 3假言推理
6 ()xG x ?
（2）1 ()xF x ?? 附加前提引入 2 ()x F x ?? 置换原则 3 ()F c ? 2EI 4 (()())x F x G x ?∨ 前提引入
5 ()()F c G c ∨ UI
6 ()G c 3 5析取三段论
7 ()xG x ? EG
21.在自然推理系统中，构造下面推理的证明：
没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。
设F(x):x 是乌鸦，G(x)：x 是北京鸭，H(x):x 是白色的。 前提 x(F(x)H(x)),(G(x)(x))x H ??∧?→ 结论 (G(x)F(x))x ?→?
证明：1 (F(x)(x))x H ??∧ 前提引入 2 x (F(x)(x))H ??∧ 置换原则 3 x(F(x)(x))H ??∨? 置换原则 4 x((x)(x))H F ??→? 5 (y)(y)H F →? 4UI 6 (G(x)(x))x H ?→ 前提引入 7 G(y)(y)H → 5UI
8 G(y)(y)F →? 5 7假言三段论 9 (G(x)(x))x F ?→? 8UG
22.在自然推理系统F 中，构造下面推理的证明：
(1)偶数都能被2整除。6是偶数。所以6能被2整除。
(2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。
（1）设F(x):x 为偶数，G(x)：x 能被2整除 前提 (F(x)G(x)),F(6)x ?→ 结论 G(6)
证明：1 ((x)G(x))x F ?→ 前提引入 2 (6)G(6)F → 1UI 3 (6)F 前提引入
4 G(6) 2 3假言推理
(2) 设F(x):x 是大学生，G(x)：x 是勤奋的，a 王晓山 前提 (F(x)G(x)),G(a)x ?→?， 结论 F(a)?
证明：1 ((x)G(x))x F ?→ 前提引入 2 (a)G(a)F → 1UI 3 G(a)? 前提引入 4 (a)F ? 2 3 据取式
23.在自然推理系统F 中，证明下面推理：
（1）每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9 （2）有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。
（1）设F(x):x 是有理数，G(x)：x 实数，H(x):x 是整数 前提 (F(x)G(x))x ?→，x(F(x)H(x))?∧ 结论 x(G(x)H(x))?∧
(2) 设F(x):x 是有理数，G(x)：x 是无理数，H(x):x 是实数，I(x):x 是虚数 前提 ((F(x)G(x))(x)),x H ?∨→(()(x))x I x H ?→? 结论 (()((x)G(x)))x I x F ?→?∧
证明：1 (()(x))x I x H ?→? 前提引入 2 I(y)H(y)→? 1 UI 3 ((F(x)G(x))(x)),x H ?∨→ 前提引入 4 (F(y)G(y))H(y)∨→ 3 UI 5 H(y)(F(y)G(y))?→?∧? 置换
6 ()(F(y)G(y))I y →?∧? 2 5假言三段论
7 x(()(F(x)G(x))I x ?→?∧? UG
24.在自然推理系统F 中，构造下面推理的证明：
每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）
设F(x):x 喜欢步行，G(x)：x 喜欢骑自行车，H(x):x 喜欢乘汽车 前提 (F(x)G(x)x ?→，(G(x)(x)),x (x)x H H ?∨?? 结论 xF(x)??
证明：1 xH(x)?? 前提引入 2 H(c)? 1 UI 3 (G(x)(x))x H ∨ 前提引入 4 G(c)H(c)∨ 3 UI
5 G(c) 2 4析取三段论
6 (F(x)G(x))x ?→? 前提引入
7 F(c)G(c)→? 6 UI
8 F(c)? 57拒取式
9 x (x)F ?? 8UG
25.在自然推理系统F 中，构造下列推理的证明（个体域为人类集合）： 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。
设F(x):x 是科学工作者，G(x)：x 是刻苦钻研的，H(x):x 是聪明的，I(x):x 在事业中获得成功
前提 (F(x)G(x))x ?→，(G(x)H(x)I(x))x ?∧→，a:王大海，F(a),H(a) 结论 I(a)
证明：1 F(a) 前提引入 2 (F(x)G(x))x ?→ 前提引入 3 F(a)G(a)→ 2UI 4 G(a) 1 3假言推论 5 H(a) 前提引入
6 (G(x)H(x)I(x))x ?∧→ 前提引入
7 G(a)H(a)I(a)∧→ 6UI
8 G(a)H(a)∧ 4 5合取
9 I(a) 7 8假言推论
离散数学(第五版)清华大学出版社第2章习题解答
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
离散数学习题(耿素云屈婉玲)
离散数学习题答案 习题二及答案：（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、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入 ④ r s ∧ ②③假言推理 ⑤ s ④化简 ⑥ s t ∨ ⑤附加 ⑦ ()s t u ∨→ 前提引入 ⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P 中用归谬法证明下面推理： （1）前提： p q →?，r q ?∨，r s ∧? 结论：p ?
离散数学第五章
第五章函数Function 函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。函数的思想、概念和应用无处不在，无时不在。 它主要是研究变量之间的关系和规律。函数的划分有很多种。有线性与非线性之分、连续与离散之分。例
如， x12345… y357911… 5.1 函数 假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。 函数也叫映射mappings或变换transformations（错误） a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。 例1. A＝{1,2,3,4}, B={a,b,c,d}, ，
则f是一个函数。 也可以简单记为， f={(1,a), (2,a), (3,d), (4,c)} 另外, g={(1,a), (1,b), (2,a), (4,c)} 因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。 例2． f：Z→Z， f(a)= f是函数。 例3．恒等函数1A(a)=a是函数。 正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。关系的特征函数为 或者简记为 因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。 例如，f：A→B, g：A→B, 函数的复合 设f：A→B，g：B→C，是函数，则g?f：A→C，是函数。 g?f（a）＝g(f(a))
离散数学习题解答
习题一 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年”既可以化 答:列出两种符号化的真值表：
离散数学第五版 模拟试题 及答案
《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
自考离散数学教材课后题第五章答案
习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致)
离散数学习题解答(第五章)格与布尔代数
离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 1 6 3 1 2 4 8 63 1 2 4 1 1
倒例如：46=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31
离散数学第5章作业答案
第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C)
离散数学(第五版)清华大学出版社第1章习题解答
离散数学（第五版）清华大学出版社第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→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （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为真命题。
离散数学 第5章 习题解答
第5章 习题解答 5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数 S S ?2n .这样的函数有个.因此上的二元运算有个. S S S f →?:2n n },{b a 162 =n n 下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律. ,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元. ,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素. θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的, 321,,f f f
离散数学习题解答(第五章)格与布尔代数教学文案
离散数学习题解答(第五章)格与布尔代数
仅供学习与交流，如有侵权请联系网站删除 谢谢2 离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 6 3 1 6 3 1 1
仅供学习与交流，如有侵权请联系网站删除 谢谢3 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 倒例如：4⊕6=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是 〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈ B ∧(?x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1(B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(?x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f 7 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
屈婉玲版离散数学课后习题答案
第四章部分课后习题参考答案 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→ ( ( )) ( H ) x ((y , (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x F x y G ∧ ? H ?? y→ ) ( , 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 第一章部分课后习题参考答案 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∧10. （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是无理数，则也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数0 r: 是无理数 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∨r1 所以公式类型为永真式 (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) (p q)(q p) (p q)(q p) (p q)(q p)(q p)(p q)(p q) (p q)(p q)(p q) ∑(0,2,3) 主合取范式： (p→q)→(q p) (p q)(q p) 离散数学习题答案 习题一及答案：（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、用真值表法求下面公式的主析取范式： 离散数学（第五版）清华大学出版社第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的真值是确定的（客观存在的），只是现在不知道而已。 离散数学课后习题答案(左孝凌版) 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）解： 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（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、求下列公式的成真赋值：离散数学第一章部分课后习题参考答案
最新离散数学习题答案
离散数学(第五版)清华大学出版社第
离散数学课后习题答案(左孝凌版)
离散数学习题详细答案