2024年3月1日发(作者：数学试卷初中初三一模)
.
离散数学习题答案
习题二及答案：〔P38
5、求下列公式的主析取范式,并求成真赋值：
〔2(pq)(qr)
解：原式(pq)qrqr(pp)qr
(pqr)(pqr)m3m7,此即公式的主析取范式,
所以成真赋值为011,111。
6、求下列公式的主合取范式,并求成假赋值：
〔2(pq)(pr)
解：原式(ppr)(pqr)所以成假赋值为100。
7、求下列公式的主析取范式,再用主析取范式求主合取范式：
〔1(pq)r
解：原式(pqr)M4,此即公式的主合取范式,
pq(rr)((pp)(qq)r)
m1m3m5m6m7,此即主析取范式。
主析取范式中没出现的极小项为m0,m2,m4,所以主合取范式中含有三个极大项M0,M2,M4,故原式的主合取范式M0M2M4。
9、用真值表法求下面公式的主析取范式：
〔1(pq)(pr)
解：公式的真值表如下：
p
0
0
0
0
1
1
1
1
q
0
0
1
1
0
0
1
1
r
0
1
0
1
0
1
0
1
p
1
1
1
1
0
0
0
0
pq
0
0
1
1
1
1
1
1
pr
0
1
0
1
0
0
0
0
(pq)(pr)
0
1
1
1
1
1
1
1
由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式m1m2m3m4m5m6m7
1 / 7
.
习题三及答案：〔P52-54
11、填充下面推理证明中没有写出的推理规则。
前提：pq,qr,r结论：s
证明：
① p 前提引入
②pq前提引入
③ q ①②析取三段论
④qr前提引入
⑤ r ③④析取三段论
⑥rs,p
s前提引入
⑦ s ⑤⑥假言推理
15、在自然推理系统P中用附加前提法证明下面推理：
〔2前提：(pq)(rs),(st)u
结论：pu
证明：用附加前提证明法。
① p 附加前提引入
②pq①附加
③(pq)(rs)前提引入
④rs②③假言推理
⑤s④化简
⑥st⑤附加
⑦(st)u前提引入
⑧ u ⑥⑦假言推理
故推理正确。
16、在自然推理系统P中用归谬法证明下面推理：
〔1前提：pq,rq,rs
结论：p
证明：用归谬法
① p 结论的否定引入
pq 前提引入
③
q ①②假言推理
④
rq 前提引入
⑤
r ③④析取三段论
②⑥
rs 前提引入
⑦ r ⑥化简
⑧rr ⑤⑦合取
由于rr0,所以推理正确。
17、在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没离开,A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开,看门人会看见他。看门人没有看见他。所以,A是谋杀嫌犯。
2 / 7
.
解：设p：A到过受害者房间,q：A在11点以前离开,r：A是谋杀嫌犯,s：看门人看见过A。
则前提：(pq)r, 结论：r
证明：
①
②
③
④
⑤
⑥
⑦
p,qs,s
qs 前提引入
s 前提引入
q ①②拒取式
p 前提引入
pq ③④合取引入
(pq)r 前提引入
r ⑤⑥假言推理
习题五及答案：〔P80-81
15、在自然推理系统N中,构造下面推理的证明：
〔3前提：x(F(x)G(x)),xG(x)
结论：xF(x)
证明：
①
②
③
④
⑤
⑥
⑦
xG(x) 前提引入
xG(x) ①置换
G(c) ②UI规则
x(F(x)G(x)) 前提引入
F(c)G(c) ④UI规则
F(c) ③⑤析取三段论
xF(x) ⑥EG规则
22、在自然推理系统N中,构造下面推理的证明：
〔2凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。
解：设F
则前提：x(F(x)G(x)),G(c)
结论：F(c)
证明：
3 / 7
.
①
②
③
④
x(F(x)G(x)) 前提引入
F(c)G(c) ①UI规则
G(c) 前提引入
F(c) ②③拒取式
25、在自然推理系统N中,构造下面推理的证明：
每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者,并且是聪明的。所以,王大海在他的事业中将获得成功。〔个体域为人类集合
解：设F
则前提：x(F(x)G(x)),x(G(x)H(x)I(x)),F(c)H(c)
结论：I(c)
证明：
①F(c)H(c)前提引入
②F(c)①化简
③H(c)①化简
④x(F(x)G(x))前提引入
⑤F(c)G(c)④UI规则
⑥G(c) ②⑤假言推理
⑦G(c)H(c) ③⑥合取引入
⑧x(G(x)H(x)I(x)) 前提引入
⑨G(c)H(c)I(c) ⑧UI规则
⑩I(c) ⑦⑨假言推理
习题七及答案：〔P132-135
22、给定A1,2,3,4,A上的关系R1,3,1,4,2,3,2,4,3,4,试
〔1画出R的关系图；
〔2说明R的性质。
解：〔1
1 2
4 / 7
.
● ●
● ●
3 4
〔2R的关系图中每个顶点都没有自环,所以R是反自反的,不是自反的；
R的关系图中任意两个顶点如果有边的都是单向边,故R是反对称的,不是对称的；
R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边,但顶点x到顶点z没有边的情况,故R是传递的。
26 设A1,2,3,4,5,6,R为A上的关系,R的关系图如图7.13所示：
2〔1求R,R3的集合表达式；
〔2求r
解：〔1由R的关系图可得R所以R可得R21,5,2,5,3,1,3,3,4,5
RR3,1,3,3,3,5,R3R2R3,1,3,3,3,5,
n3,1,3,3,3,5,当n>=2；
IA1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6〔2r(R)=R,
46、分别画出下列各偏序集〔1RA,R的哈斯图,并找出A的极大元、极小元、最大元和最小元。
a,d,a,c,a,b,a,e,b,e,c,e,d,eIA
解：哈斯图如下：
e
b c d
a
A的极大元为e、极小元为a；
A的最大元为e、最小元为a。
48、设A,R和B,S为偏序集,在集合AB上定义关系T如下：
证明T为AB上的偏序关系。
证明：〔1自反性：
〔2反对称性：
〔3传递性：
综合〔1〔2〔3知T满足自反性、反对称性和传递性,故T为AB上的偏序关系。
5 / 7
.
习题九及答案：〔P179-180
8、
〔1运算在S上是否可交换、可结合？是否为幂等的？
〔2运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元。
解：〔1
〔2
11、
设S1，2，...,10，问下面的运算能否与S构成代数系统S，?如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。〔3xy=大于等于x和y的最小整数；
解：〔3由*运算的定义可知：xy=max(x,y),
16、
习题十一及答案：〔P218-219
1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由
解：〔a、〔c、〔f是格；因为任意两个元素构成的集合都有最小上界和最大下界；
〔b不是格,因为{d,e}的最大下界不存在；
〔d不是格,因为{b,c}的最小上界不存在；
〔e不是格,因为{a,b}的最大下界不存在。
2、下列各集合低于整除关系都构成偏序集,判断哪些偏序集是格。
〔1L={1,2,3,4,5}；
〔2L={1,2,3,6,12}；
解：画出哈斯图即可判断出：〔1不是格,〔2是格。
4、设L是格,求以下公式的对偶式：
〔2a(bc)(ab)(ac)
解：对偶式为：a(bc)(ab)(ac),参见P208页定义11.2。
9、针对图11.11中的每个格,如果格中的元素存在补元,则求出这些补元。
解：
〔a图：a,d互为补元,其中a为全下界,d为全上界,b和c都没有补元；
〔c图：a,f互为补元,其中a为全下界,f为全上界,c和d的补元都是b和e,b和e的补元都是c和d；
〔f图：a,f互为补元,其中a为全下界,f为全上界,b和e互为补元,c和d都没有补元。
10、说明图11.11中每个格是否为分配格、有补格和布尔格,并说明理由。
解：
〔a图：是一条链,所以是分配格,b和c都没有补元,所以不是有补格,所以不是布尔格；
〔c图：a,f互为补元,c和d的补元都是b和e,b和e的补元都是c和d,所以任何元素皆有补元,是有补格；c(bd)cac,(cb)(cd)fddc(bd)(cb)(cd),所以对运算不满足分配律,所以不是分配格,所以不是布尔格；
6 / 7
.
〔f图：经过分析知图〔f对应的格只有2个五元子格：L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格,根据分配格的充分必要条件〔见P213页的定理11.5得图〔f对应的格是分配格；c和d都没有补元,所以不是有补格,所以不是布尔格。
7 / 7
更多推荐
推理,运算,前提,没有,赋值
发布评论