离散数学习题答案(耿素云屈婉玲)
离散数学习题答案
习题二及答案:(P38)
5、求下列公式的主析取范式,并求成真赋值: (2)(⌝p →q ) ∧(q ∧r ) 解:原式⇔(p ∨q ) ∧q ∧r
⇔q ∧r ⇔(⌝p ∨p ) ∧q ∧r
⇔(⌝p ∧q ∧r ) ∨(p ∧q ∧r ) ⇔m 3∨m 7,此即公式的主析取范式,
所以成真赋值为011,111。
6、求下列公式的主合取范式,并求成假赋值: (2)(p ∧q ) ∨(⌝p ∨r )
解:原式⇔(p ∨⌝p ∨r ) ∧(⌝p ∨q ∨r ) 所以成假赋值为100。
7、求下列公式的主析取范式,再用主析取范式求主合取范式: (1)(p ∧q ) ∨r 解:原式⇔
⇔(⌝p ∨q ∨r ) ⇔M 4,此即公式的主合取范式,
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 )
⇔m 1∨m 3∨m 5∨m 6∨m 7,此即主析取范式。
主析取范式中没出现的极小项为m 0,m 2,m 4,所以主合取范式中含有三个极大项M 0,M 2,M 4,故原式的主合取范式⇔M 0
9、用真值表法求下面公式的主析取范式: (1)(p ∨q ) ∨(⌝p ∧r ) 解:公式的真值表如下:
∧M 2∧M 4。
由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式
⇔m 1∨m 2∨m 3∨m 4∨m 5∨m 6∨m 7
习题三及答案:(P52-54)
11、填充下面推理证明中没有写出的推理规则。 前提:⌝p ∨q , ⌝q ∨r , r 结论:s 证明:
① p 前提引入 ② ④
→s , p
⌝p ∨q 前提引入 ⌝q ∨r 前提引入
③ q ①②析取三段论 ⑤ r ③④析取三段论 ⑥
15、在自然推理系统P 中用附加前提法证明下面推理: (2)前提:(p ∨q ) →(r ∧s ),(s ∨t ) →u 结论:
r →s 前提引入
⑦ s ⑤⑥假言推理
p →u
证明:用附加前提证明法。 ① p 附加前提引入 ② ③ ④ ⑥ ⑦
p ∨q ①附加
(p ∨q ) →(r ∧s ) 前提引入
r ∧s ②③假言推理
⑤ s ④化简
s ∨t ⑤附加
(s ∨t ) →u 前提引入
⑧ u ⑥⑦假言推理 故推理正确。
16、在自然推理系统P 中用归谬法证明下面推理:
p →⌝q ,⌝r ∨q ,r ∧⌝s 结论:⌝p
(1)前提:
证明:用归谬法
① p 结论的否定引入 ② ③ ④ ⑤ ⑥
p →⌝q 前提引入 ⌝q ①②假言推理 ⌝r ∨q 前提引入
⌝r ③④析取三段论 r ∧⌝s 前提引入
⑦ r ⑥化简 ⑧r ∧⌝r ⑤⑦合取 由于r ∧⌝r
⇒0,所以推理正确。
17、在自然推理系统P 中构造下面推理的证明:
只要A 曾到过受害者房间并且11点以前没离开,A 就是谋杀嫌犯。A 曾到过受害者房间。如果A 在11点以前离开,看门人会看见他。看门人没有看见他。所以,A 是谋杀嫌犯。
解:设p :A 到过受害者房间,q :A 在11点以前离开,r :A 是谋杀嫌犯,s :看门人看见过A 。 则前提:(p ∧⌝q ) →r , 结论:r 证明: ① ② ③ ④ ⑤ ⑥ ⑦
习题五及答案:(P80-81)
15、在自然推理系统N ξ中,构造下面推理的证明: (3)前提:∀x (F (x ) ∨G (x )) ,⌝∃xG (x ) 结论:∃xF (x ) 证明: ① ② ③ ④
p ,q →s ,⌝s
q →s 前提引入
⌝s 前提引入
⌝q ①②拒取式
p 前提引入
p ∧⌝q ③④合取引入
(p ∧⌝q ) →r 前提引入
r ⑤⑥假言推理
⌝∃xG (x ) 前提引入 ∀x ⌝G (x ) ①置换 ⌝G (c ) ②UI 规则 ∀x (F (x ) ∨G (x )) 前提引入
⑤ ⑥ ⑦
F (c ) ∨G (c ) ④UI 规则 F (c ) ③⑤析取三段论
∃xF (x ) ⑥EG 规则
22、在自然推理系统N ξ中,构造下面推理的证明:
(2)凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解:设F(x):x 为大学生,G(x):想是勤奋的,c :王晓山 则前提:∀x (F (x ) →G (x )) ,⌝G (c ) 结论:⌝F (c ) 证明: ① ② ③ ④
∀x (F (x ) →G (x )) 前提引入 F (c ) →G (c ) ①UI 规则 ⌝G (c ) 前提引入 ⌝F (c ) ②③拒取式
25、在自然推理系统N ξ中,构造下面推理的证明:
每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者,并且是聪明的。所以,王大海在他的事业中将获得成功。(个体域为人类集合)
解:设F(x):x 是科学工作者,G(x):x 是刻苦钻研的,H(x):x 是聪明的,I(x):x 在他的事业中获得成功,c :王大海 则前提:∀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、给定
A ={1,2,3,4},A 上的关系R ={, 4, 2,3, 2, 4, 3, 4},试
(1)画出R 的关系图; (2)说明R 的性质。 解:(1)
(2)R R 是反自反的,不是自反的;
R 的关系图中任意两个顶点如果有边的都是单向边,故R 是反对称的,不是对称的;
R 的关系图中没有发生顶点x 到顶点y 有边、顶点y 到顶点z 有边,但顶点x 到顶点z 没有边的情况,故R 是
传递的。 26 设
A ={1,2,3,4,5,6},R 为A 上的关系,R 的关系图如图7.13所示:
2
(1)求R
, R 3的集合表达式;
={, 2,5, , , 4,5
(2)求r(R), s(R), t(R)的集合表达式。 解:(1)由R 的关系图可得R 所以R 可得R
2
,
=R ︒R ={, 3,3, 3,5,R
3
=R 2︒R ={, 3,3, 3,5
n
={, 3,3, 3,5, 当n>=2;
={, 2,5, 3,1, 3,3, 4,5, , 2, 2, 4, 4, , 6,6
(2)r(R)=R I A
,
s (R ) =R R -1={, 5,1, 2,5, 5, 2, 3,1, , 3,3, 4,5, 5, 4
t (R ) =R R 2 R 3 ... =R R 2={, 2,5, , , 4,5, 46、分别画出下列各偏序集(1)R ≤
A , R ≤
的哈斯图,并找出A 的极大元、极小元、最大元和最小元。
={a , d , a , c , a , b , a , e , b , e , c , e , d , e } I A
解:哈斯图如下:
A 的极大元为e 、极小元为a ; A 的最大元为e 、最小元为a 。 48、设
A , R 和为偏序集,在集合A ⨯B 上定义关系T 如下:
∀a 1, b 1, a 2, b 2∈A ⨯B, a 1, b 1T a 2, b 2⇔a 1Ra 2∧b 1Sb 2
证明T 为A ⨯B 上的偏序关系。 证明:(1)自反性:
任取a 1, b 1∈A ⨯B ,则:
R 为偏序关系,具有自反性,∴a 1R a 1 S 为偏序关系,具有自反性,∴b 1Sb 1∴a 1R a 1∧b 1Sb 1
又a 1, b 1T a 2, b 2⇔a 1Ra 2∧b 1Sb 2,∴a 1, b 1T a 1, b 1,故T 满足自反性
(2)反对称性:
任取a 1, b 1, a 2, b 2∈A ⨯B ,若a 1, b 1T a 2, b 2且a 2, b 2T a 1, b 1,则有:a 1Ra 2∧b 1Sb 2a 2Ra 1∧b 2Sb 1
(1)(2)
∴a 1Ra 2∧a 2Ra 1,又R 为偏序关系,具有反对称性,所以a 1=a 2∴b 1Sb 2∧b 2Sb 1,又S 为偏序关系,具有反对称性,所以b 1=b 2∴a 1, b 1=a 2, b 2,故T 满足反对称性
(3)传递性:
任取a 1, b 1, a 2, b 2a 3, b 3∈A ⨯B ,若a 1, b 1T a 2, b 2且a 2, b 2T a 3, b 3,则有:a 1, b 1T a 2, b 2⇔a 1Ra 2∧b 1Sb 2a 2, b 2T a 3, b 3⇔a 2Ra 3∧b 2Sb 3
∴a 1Ra 2∧a 2Ra 3, 又R 为偏序关系,具有传递性,所以a 1Ra 3∴b 1Sb 2∧b 2Sb 3, 又S 为偏序关系,具有传递性,所以b 1Sb 3∴a 1Ra 3∧b 1Sb 3⇒a 1, b 1T a 3, b 3,故T 满足传递性。
综合(1)(2)(3)知T 满足自反性、反对称性和传递性,故T 为A ⨯B 上的偏序关系。
习题九及答案:(P179-180) 8、
S=Q⨯Q,Q 为有理数集,为*S 上的二元运算,∀a,b , x,y ∈S 有
a,b *x,y =ax,ay+b
(1)*运算在S 上是否可交换、可结合?是否为幂等的?
(2)*运算是否有单位元、零元?如果有,请指出,并求出S 中所有可逆元素的逆元。 解:(1)
x , y *a,b =xa,xb+y=ax,bx+y≠a,b *x , y ∴*运算不具有交换律
(x , y *a,b )*c,d
=ax,bx+y*c,d =acx,adx+bx+y而x , y *(a,b *c,d =x , y *ac,ad+b
=xac,xad+xb+y=acx,adx+bx+y=(x , y *a,b )*c,d ∴*运算有结合律
)
任取a,b ∈s ,则有:a,b *a,b =a 2, ad +b ≠a,b ∴*运算无幂等律
(2)
令a,b *x , y =a,b 对∀a,b ∈s 均成立ax,ay+b=a,b 对∀a,b ∈s 均成立⎧⎧a (x -1)=0⎪ax =a ∴⎨⇒⎨对∀(a,b )成立ay +b =b ay =0⎪⎩⎩
⎧x -1=0⎧x =1
∴必定有⎨⇒⎨
⎩y =0⎩y =0∴*运算的单位元为0
∴*运算的右单位元为0,可验证0也为*运算的左单位元,
令a,b *x , y =x , y ,若存在x , y 使得对∀a,b ∈s 上述等式均成立,则存在零元,否则不存在零元。由a,b *x , y =x , y ⇒ax,ay+b=x , y
⎧⎧⎪ax =x ⎪(a -1)x =0⇒⎨⎨
ay +b =y ⎪(a -1)y+b=0⎪⎩⎩
由于(a -1)y+b=0不可能对∀a,b ∈s 均成立,
故a,b *x , y =x , y 不可能对∀a,b ∈s 均成立,故不存在零元;
设元素a,b 的逆元为x , y ,则令a,b *x , y =e =01⎧
x =⎪⎧ax =1⎪a
⇒⎨⇒⎨(当a ≠0)
ay +b =0b ⎩⎪y =-
⎪a ⎩
∴当a =0a,b 的逆元不存在;
当a ≠0a,b 的逆元是
11
1b
, -a a
、
设S ={1,2,...,10},问下面的运算能否与S 构成代数系统S *?
如果能构成代数系统则说明*运算是否满足交换律、结合律,并求*运算的单位元和零元。
(3)x *y =大于等于x 和y 的最小整数; 解:(3)由*运算的定义可知:x *y=max(x,y),
x,y ∈S, 有x *y ∈S ,故*运算在S 上满足封闭性,所以*运算与非空集合S 能构成代数系统; 任取x,y ∈S, 有x *y=max(x,y)=max(y,x)=y*x , 所以*运算满足交换律;
任取x,y,z ∈S, 有(x *y) *z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x*(y*z), 所以*运算满足结合律;
任取x ∈S ,有x *1=max(x,1)=x=max(1,x)=1*x, 所以*运算的单位元是1; 任取x ∈S ,有x *10=max(x,10)=10=max(10,x)=10*x, 所以*运算的零元是10;16、
设V 1=1, 2,3}, ︒,1, 其中x ︒y 表示取x 和y 之中较大的数。V 2=5,6}, *,6,其中x *y 表示取x 和y 之中较小的数。求出V 1和V 2的所有的子代数。指出哪些是平凡的子代数,哪些是真子代数。
解:(1)V 11, 2,3}, ︒,1, 1}, ︒,1, 1, 2}, ︒,1, {1,3}, ︒,1;
V 1{1, 2,3}, ︒,1, 1}, ︒,1;V 1{1}, ︒,1, {1, 2}, ︒,1, 1,3}, ︒,1;
(2)V 25,6}, *,6{6}, *,6;
V 2 5,6}, *,66}, *,6;V 26}, *,6。
习题十一及答案:(P218-219)
1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由 解:(a )、(c )、(f )是格;因为任意两个元素构成的集合都有最小上界和最大下界; (b )不是格,因为{d,e}的最大下界不存在; (d )不是格,因为{b,c}的最小上界不存在; (e )不是格,因为{a,b}的最大下界不存在。
2、下列各集合低于整除关系都构成偏序集,判断哪些偏序集是格。 (1)L={1,2,3,4,5}; (2)L={1,2,3,6,12};
解:画出哈斯图即可判断出:(1)不是格,(2)是格。 4、设L 是格,求以下公式的对偶式: (2)a ∨(b ∧c ) ≤(a ∨b ) ∧(a ∨c )
解:对偶式为:a ∧(b ∨c ) ≥(a ∧b ) ∨(a ∧c ) ,参见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 ∨(b ∧d ) =c ∨a =c , (c ∨b ) ∧(c ∨d ) =f ∧d =d ∴c ∨(b ∧d ) ≠(c ∨b ) ∧(c ∨d ) ,所以∨对∧运算
不满足分配律,所以不是分配格,所以不是布尔格;
(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 都没有补元,所以不是有补格,所以不是布尔格。
相关文章
- 离散数学-第二章命题逻辑等值演算习题及答案
- 离散数学 第二章练习题答案
- 电大离散数学集合论部分期末复习题
- 标准差与方差教学设计
- 信号与系统习题
- 国外通信类经典书籍介绍
- 教材推荐|高等数学,线性代数,概率论与数理统计
- 统计学习题 第四章_数据分布特征的描述习题答案
- 统计学练习题与答案(西南财大出版社)
第二章作业 评分要求: 1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分 2. 给出每小题得分(注意: 写出扣分理由) 3. 总得分在采分点1处正确设置. 一. 证明下面等值式(真值表法, 解逻辑方程法, ...
一. 选择题 1.下列四个公式正确的是 ①∀x (A (x ) ∧B (x )) ⇒∀xA (x ) ∧∀xB (x ) ②∀x (A (x ) ∨B (x )) ⇒∀xA (x ) ∨∀xB (x ) ③∃x (A (x ) ∨B (x ...
一.单项选择题 1.若集合A ={ a,{a },{1,2}},则下列表述正确的是( ) . A .{a ,{a }}∈A B .{1,2}∉A C .{a }⊆A D .∅∈A 正确答案:C 2.若集合A ={1,2},B ={1,2,{ ...
<方差与标准差>教学设计 教学内容:方差与标准差 教学班级:高一(1)班 教学时间:2012年3月13日 教者:韩彦斌 一.教学目标 (一)知识与技能目标 1.正确理解样本数据标准差的概念和作用,学会计算样本数据的标准差: 2. ...
信号处理原理作业(2004下) 部分习题解答 第1章 1.判断题 1)⎰ ∞-∞ Sa (t ) dt =π/2 错误 ∞ 2)e(t)与h(t)的卷积是⎰e (τ) h (t -τ) d τ. 正确 -∞ 4)反因果信号只在时间零点之后有 ...
国外通信类经典书籍 1.<Linear Systems and Signals>--B.P.Lathi 这本书个人觉得很不错,是一本线性系统和信号的入门好书.可以适用于通信.电路.控制等专业. 虽说是入门的好书,但是本书的编排是 ...
这是一个,让你学好高数的头条号 工欲善其事,必先利其器!要想学好高等数学,线性代数,概率论与数理统计这三个大块头,没有合适的书怎么行?今天小编就为大家整理了一些不错的书! 高等数学书籍推荐 同济大学出版<高等数学> 结构严谨,逻 ...
第四章 数据分布特征的描述习题 一.填空题 1.数据分布集中趋势的测度值(指标)主要有 众数 . 中位数 和 均值 .其中 众数 和 中位数 用于测度品质数据集中趋势的分布特征, 均值 用于测度数值型数据集中趋势的分布特征. 2.标准差是反 ...
第一章.总论 一.单项选择题(在每小题的四个备选答案中,选出一个正确答案) 1. 在下列叙述中,不正确的是( ). A ."statistics "可以表示统计学 B."statistics "可以表 ...