离散数学习题答案(耿素云屈婉玲)

离散数学习题答案

习题二及答案:(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 都没有补元,所以不是有补格,所以不是布尔格。


© 2024 实用范文网 | 联系我们: webmaster# 6400.net.cn