2023年离散数学形成性考核作业离散数学综合练习书面作业

离散数学形成性考核作业4

姓名：

号.

学

得分：____________

离散数学综合练习书面作业

规定：学生提交作业有如下三种方式可供选择：

1.可将本次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有

解答过程，完毕作业后交给辅导教师批阅.

2.在线提交word文档.

3.自备答题纸张，将答题过程手工书写，并拍照上传.

一、公式翻译题

1.请将语句“小王去上课，小李也去上课."翻译成命题公式.

设P：小王去上课

Q:小李去上课

则：命题公式PAQ

2.请将语句“他去旅游，仅当他有时间.”翻译成命题公式.

设P：他去旅游

Q：他有时间

则命题公式为P-Q

3.请将语句“有人不去工作”翻译成谓词公式.

设A(x):x是人

B(x)：去工作

则谓词公式为3x(A(x)A-B(x))

4.请将语句“所有人都努力学习.”翻译成谓词公式.

设A(x):x是人

B(x):努力学习

则谓词公式为Vx(A(x)AB(x))

二、计算题

1.设4={{1},{2},1,2},5={1,2,{1,2}),试计算

(1)(A-B)；(2)(AA5)；(3)AxB.

解:

(I)(A-B)={{1},{2})

(2)(APB)={1,2}

(3)AxB=

{<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1,

2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>}

2.设4={1,2,3,4,5},R={<x,y>\x&A,yeA且x+yV4},S={<x,y>\x&A,

yeA且x+y<0},试求R,S,R・S,S・R,Ri,S-i,r(S),s(R).

解：

R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}

S=空集

R・S=空集

S・R=空集

7?-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>}

空集

r(5)={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}

s(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}

3.设A={1,2,3,4,5,6,7,8},R是A上日勺整除关系，B=[2,4,6).

(1)写出关系R日勺表达式；(2)画出关系R日勺哈斯图;

(3)求出集合5日勺最大元、最小元.

答：(1)R=|<1,1><1,2x1,3x1,4x1,5x1,6x1,7x1,8>

<2,2x2,4x2,6x2,8x3,3x3,6x4.4?<4,8x5,5x6,6x7,7><8,8>}

(2次的哈斯图为

{3)集合B没有最大元，最小元是2

4.设G=<V,E>,V=[V],v2,v3,v4,v5},E={(vpv3),(v2,v3),(v2,v4),(v3,v4),

(v3,v5),(v4,v5)},试

(1)给出G日勺图形表达；(2)写出其邻接矩阵；

(3)求出每个结点日勺度数；(4)画出其补图日勺图形.

答：⑴

(2)

-00100-

00110

.4(D)=11011

01101

00110

(3)

deg(vl)=l,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2

(4)

VL

5.图G=<V,E>,其中V={a,b,c,d,e},E={(a,b\(a,c),(a,e),(b,d),(b,e),

(c,e),(c,d),(d,e)},对应边日勺权值依次为2、1、2、3、6、1、4及5,试

(1)画出G日勺图形;(2)写出G日勺邻接矩阵;

(3)求出G权最小日勺生成树及其权值.

解:

(1)

(2)

011o1

1001

A(D)=10011

01101

11110

(3)

其中权值是：7

6.设有一组权为2,3,5,7,17,31,试画出对应日勺最优二叉树，计算该最优

二叉树日勺权.

解:

48

31

权值：65

7.求PfQvR日勺析取范式，合取范式、主析取范式，主合取范式.

解:

PTQVKCrPvQvR（析取超式）

oJPvQvR）（合取范式）

真值表；

pQR-Ip原式极小项及大项

00011-IPA—IPA—»P

00111-,PA->QAR

01011-IPAQA-IR

0111I—IPAQAR

10000PvQvR

10101PA-»QAR

11001PAQA-iR

11101PAQAR

主析菽应:if(->PA-,PA-,P)v(-,PA-,QAR)V(-,PAQA-.R)V

(-.PAQAR)v(PA-,QAR)V(PAQA->R)V(PAQAR)

主合取范式JPvQvR)

8.设谓词公式(土)(尸0,丁)—(以)。(丫,羽名))人(»)氏0,2).

(1)试写出量词日勺辖域；

(2)指出该公式日勺自由变元和约束变元.

答：(1)的辖域为P(x.y)T\/zQ(x,y,z)

Vz的辖域为Q(x,y,z)

Vy的辖域为R(y,z)

(2)约束变元为

P<x,y)->VzQ(x,y.z)中的x

Q(x,y,z)中的z

R(y,z)中的y

自由委无为

P(x,y)->DzQ(x,y,z)中的y

R(y,z)中的z

9.设个体域为。={%,%}，求谓词公式(Vy)0x)P(x,y)消去量词后日勺等值式;

捽：谓词公式消去用词后的等值式为

(R(a.a)AR(a,b))v(R(b,a)AR(b,b))

三、证明题

1.对任意三个集合A,B和C,试证明：<Ax5=AxC,且Aw0,则B=C.

证明：设x£A,yFB,JH1]<x,y>FAxB

由于AxB=AxC,故vx,y>£AxC,则有y^C

因此BcC

设xGA,z@C,则<x,z>GAxC

由于AxB=AxC,故<x,z>CAxB,则有z@B

因此CcB

故得A=B

2.试证明：若R与S是集合A上口勺自反关系，则ACS也是集合A上日勺自

反关系.

证明：

R和S是自反口勺，VxGA,<x,x>GR,<x,x>cS

则<x,x>eRnS

因此RcS是自反日勺

3.设连通图G有左个奇数度日勺结点，证明在图G中至少要添加：条边才能

使其成为欧拉图.

证明：由定理推论知：在任何图中，度数为奇数的结点必是偈数个，则k是

偎数，又由欧拉图的充要条件是图G