离散数学样卷十二套(含答案)

一、证明下列各题

1、（10分）证明蕴涵式：P人（PfQ）nQ

2、（10分）证明：九g为1-1函数n/cig为1-1函数。

5、3、（10分）给定代数结构（Mx〉和«0」｝，x），其中N是自然数集合，x是数的

乘法。设｛0,1｝,定义为：

，/、1n=2k,n,k$N

f（n）=<

0否则

试证〈Mx〉三〈｛0，l｝，x]

4、（10分）给定代数结构（尺*〉，其中R是实数集合，对R中任意元。和"*定

义如下：a*b=a+b+axb

试证明:〈凡*〉是独异点。

二、求下列各题的解：

1、试求下列公式的主析取范式和主合取范式（15分）:

（「尸「Q）

2、（15分）设氏={〈0，1），〈0,2〉，〈0,3〉，。，2〉,（1,3）,〈2,3〉},试求

⑴、R*R，⑵、/{1},⑶、5},（4）、此例，（5）、上刖］

3、（15分给定无向图6=〈匕石），如图，试求:

FED

（1）从A到D的所有基本链；

（2）从A到D的所有简单链；

（3）长度分别是最小和最大的简单圈;

（4）长度分别是最小和最大的基本圈;

（5）从A到D的距离。

4、45分）给定二部图G=化，瓦匕），如图

V,

一、证明下列各题

1、（10分）证明蕴涵式：P—QnP-（PA°）

2、(10分)证明：AX(8—C)=(AXB)—(4XC)

3、(10分)给定群(°')，则伶')为Abel群

o(Wa)"b)(a,匕eGf(ab)2=a2b2)

4、（10分）给定代数结构（S，*），其中S中元为实数有序对，*定义为

[a,b）*（c,d）=（a+c,b+d+2bd）,试证｛S,*）是可交换独异点。

二、求下列各题的解：

1、试求下列公式的主析取范式和主合取范式（15分）:

Pv（「Pr（Qv（「Q-»R）））

2、（15分）设/?={3/但0〉«，叫，试求“幻，5（我）和川）。

3、（15分）给定有向图G—〈V'£），如图，试求:

（1）、各结点的出度、入度和度；

（2）、从W到v」的所有简单路和基本路；

（3）、所有简单回路和基本回路。

4、（15分）给定树G,试求对应二叉树

一、证明下列各题

1、（10分）证明蕴涵式：（/>一0）—。=/>丫。

2、（10分）证明：九g为1T函数n/Clg为1-1函数。

给定代数结构〈N，x〉和《｛0」｝，'），其中N是自然数集合，x是数的乘

3、（10分）

法。设广Nf｛0,1｝,定义为:

1n=2k,n,k&N

/（〃）=，

0否则

试证〈Mx〉三他1｝，X）。

4、(10分)给定代数结构@，*〉，其中S中元为实数有序对，*定义为

(a,by{c,d)=(a+c,b+d+2bd)f试证6*)是可交换独异点。

二、求下列各题的解：

1、试求下列公式的主析取范式和主合取范式(15分):

R)))

2、(15分)设夫={〈0，1〉，〈0,2〉，〈0,3〉，。，2〉,〈1,3〉,〈2,3〉},试求

⑴、R*R，(2)、"{1},⑶、KT{1},(4)、R[{1}],(5)、内刖]

3、(15分)给定有向图G=〈')，如图，试求:

V5V4吟

(1)、各结点的出度、入度和度；

(2)、从vi到V3的所有简单路和基本路；

(3)、所有简单回路和基本回路。

4、(15分)给定树G,试求对应二叉树

专业:信息与计算科学课程名称：离散数学学分：3试卷编号（D）

课程编号：4114600考试方式：闭卷考试时间：120分钟

拟卷入（签字）:拟卷日期:审核人（签字）:

得分统计表

N!题号—总分

救婚

得分

一、第一部分

1（10分）写出下列公式的真值表

A=（pvq）

得分

阅卷人

D|P：

料已

2（10分）用等值演算法判断下列公式的类型

q八一1Sfq）

3（10分）求主析取范式

4（10分）判断下面推理是否正确

若今天是1号，则明天是5号.今天是1号.所以明天是5号.

5（10分）用归缪法证明

前提：r->5,-is,p结论：

二、第二部分

1（10分）在一阶逻辑中将下面命题符号化

-------------------正数都大于负数

得分

阅卷人

2（10分）设偏序集＜4＜＞如下图所示，

求力的极小元、最小元、极大元、最大元.

设8={6,c,济，求5的下界、上界、下确界、上确界.

3（10分）伍办是12阶循环群，写出G的所有子群

4（10分）考虑110的正因子集合Si。关于gcd,1cm运算构成的布尔代数.

写出它所有的子布尔代数

5（10分）⑴对权1，4,9,16,25,36,49,64,81,100构造一棵最优二元树，并求权和。

⑵求下图的最小生成树，并求最小权和

专业:信息与计算科学课程名称：离散数学学分：3试卷编号（E）

课程编号：4114600考试方式：闭卷考试时间：120分钟

拟卷入（签字）：拟卷日期：审核人（签字）：

得分统计表

N!题号—总分

救婚

得分

一、第一部分

1（10分）写出下列公式的真值表

B=(q->p)八qip

得分

阅卷人

D|P：

料已

2（10分）用等值演算法判断下列公式的类型

3（10分）求主合取范式

4（10分）判断下面推理是否正确

若今天是1号，则明天是5号.明天是5号.所以今天是1号

5（10分）用附加前提证明法构造证明

前提：pvq,prr,r->-ns结论：slq

二、第二部分

1（10分）在一阶逻辑中将下面命题符号化

有的无理数大于有的有理数

得分

阅卷人

2（10分）已知偏序集＜4曲的哈斯图如下图所示,

试求出集合力和关系7?的表达式.。

3（10分）设作｛&a,b,d是Klein四元群.给出G的所有自同构.

4（10分）写出下图中£i,L?,£3的原子。

♦000

5（10分）写出下图所示树产生的前缀码

专业:信息与计算科学课程名称：离散数学学分：3试卷编号(F)

课程编号：4114600考试方式：闭卷考试时间：120分钟

拟卷入(签字)：拟卷日期：审核人(签字)：

得分统计表

题号—总分

得分

一、第一部分

1(10分)写出下列公式的真值表

得分

阅卷人

2(10分)用等值演算法判断下列公式的类型

((/?A<7)v(/?A-,g))Ar)

3(10分)用主析取范式判两个公式是否等值

(1)p->(q->r)与(pA<7)->r

(2)pf(qrr)与(p—><7)—>r

4（10分）证明｛J｝为联结词完备集

5（10分）直接证明法构造证明

前提：（pv<7）->r,r->s,-is结论：

二、第二部分

1（10分）在一阶逻辑中将下面命题符号化

（1）人都爱美（2）有人用左手写字

得分个体域分别为

（a）介“人类集合”=｛xx是人｝

阅卷人（6）〃为全总个体域

2（10分）分别画出下列各偏序集的哈斯图，再求出最大元、最小元、极大元和极小元

A=（a,b,c,d,e）<=（<a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>UIA

“、f^2x>3,、c

J（x）=<g（x）=x+2

3（10分）设f：RTR,g：RTRl-2*<3

求/bg,gQ/：如果/和g存在反函数，求出它们的反函数.

4（10分）下图中的人心,A和乙是否是有补格。

L.

5（10分）用Huffman算法产生最佳前缀码

在通信中，八进制数字出现的频率如下:

0：25%1：20%

2：15%3：10%

4：10%5：10%

6：5%7：5%

求传输它们的最佳前缀码，并求传输10000个按上述比例出现的八进制数字需要多少

个

二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？

专业:信息与计算科学课程名称：离散数学学分：3试卷编号（G）

课程编号：411461考试方式：阅去考试时间：100分钟

拟卷人（签字）：拟卷日期：审核人（签字）：

得分统表：

题号—三四总分

得分

得分阅卷人一、将下列命题符号化：（本题共4题，每题5分，满分20分.）

1.小明学习和体育都好.

2.只有努力才能成功.

3.存在函数连续但不可导（论域为全总个体域）.

4.凡有理数均可表示成分数（论域为全总个体域）.

得分阅卷人

计算题:（本题共3小题,满分34分.）

1.求公式（P—°）A（PA°）的主析取范式和主合取范式（12分）.

2设A={1,2,3},A上的一兀关系R={(1,2),(2,2),(2,3)}.求“R)、s(R)及t(R)(12

分).

3.设4={1，2,3}，问人上共有多少个不同的等价关系（10分）.

三、应用题：（本题共3小题，满分30分.）

1.画出集合A={1'2'3'4,6，12}上整除关系的哈斯图，指出最大元、最小元、极

大元和极小元（12分）.

2.设〃=底,*）是半群，s={a,b,c,d},“*”运算定义如下表（10分）:

（1）.证明U是一个循环含幺半群，并给出它的生成元;

*abcd

aabcd（2）.把U中的每个元素均表示成生成元的疑.

bbcda

ccdab

ddabc

3.设（4,+,x）是一个代数系统，A=[x\x=a+b“，。、人均为有理数，其中

“+"、“X”为普通加法和普通乘法，问(A,+,x)是否为域？为什么？(8分)

得分阅卷人四、证明题：(本题共2小题，满分16分.)

1.给定代数系统0=(*，・)，丫=0»,卬=(2,*).设/是从。到"的同态，力是从V到

W的同态.证明：力。/是从U到W的同态.(8分)：

2.构造下列推理的证明(8分)：

前提:Vx(A(x)-「8(x)),Vx(B(x)vC(x)),「VxC(x).

结论：引「A(x).

料t

：3.存在函数连续且可导（论域为全总个体域）.

4.有的有理数能被2整除（论域为全总个体域）.

黑二、计算题：（本题共3小题，满分34分.）

1.化•阶逻辑公式（vxP（x）vW2（y））fVxR（x）为前束范式（12分）.

2设4={。也（:},4上的二元关系7?={（。,6）,3,3,（仇0）}求，也）、s（R）及t（R）

（12分）.

3.设A={1,2,3,4},问A上共有多少个不同的等价关系（10分）

三、应用题：（本题共3小题，满分30分.）

1.画出集合A={2,3,4,9,12}上整除关系的哈斯图，指出极大元和极小元（12

分）.

2.设U=3*）是半群，s={a，b,c},“*”运算定义如下表（10分）:

*abc

aabc（1）.证明U是一个循环含幺半群，并给出它的生成元；

bbca（2）.把U中的每个元素均表示成生成元的累.

ccab

A=x|』+码,以b均为有理数,其中

3.设（A+/）是一个代数系统，一

"+"、“x”为普通加法和普通乘法，问（A,+,x）是否为域？为什么？（8分）

得分阅卷人四、证明题：（本题共2小题，满分16分.）

1.设/、g分别是两代数系统（X，。），*，*）上的同态，其中（丫，*）可交换,令〃是从X到

丫的函数，对VxeX有：/7（x）=/（x）*g（x）.证明：人是从x到y的同态.（8分）：

2.构造下列推理的证明（8分）：

前提：P.{SAR）f-10）,P,—.

结论：「e

专业：信息与计算科学课程名称：离散数学学分：3试卷编号（I）

课程编号：4114600考试方式：闲典考试时间：100分钟

拟卷人（签字）：拟卷日期：审核人（签字）：

.­得分统表：

—.

W.题号—三四总分

姬

软

—

：得分

：

得分阅卷人一、将下列命题符号化：（本题共4题，每题5分，满分20分.）

1.只要努力过就不会后悔.

：2.我在城在.

D|P\

料日

3.所有孩子都崇拜某些偶像（论域为全总个体域）.

4.一切房子都不•样大（论域为全总个体域）.

得分阅卷人

黑计算题:（本题共3小题,满分34分.）

1.求公式（2八。）-R的主析取范式和主合取范式（12分）.

2.设4={1,2},4上的一兀关系7?={(1,2)}.求「也)、s(R)及t(R)(12分)

3.设4={1，2}，问A上共有多少个不同的等价关系（10分）.

得分阅卷人

三、应用题：（本题共3小题，满分30分.）

1.画出集合A={2'3,4,7,8,9}上整除关系的哈斯图，指出极大元和极小元（12

分）.

2『G={e,a,b,c}

,”为G上的二元运算,“*”运算定义如下表（10分）:

（1）.G是否能构成一个群？

*eabc

eeabc（2）.G有何性质？

aaecb

bbcea

ccbae

3.设（A，+d）是一个代数系统,a、6均为有理数，其中

+”、“x”为普通加法和普通乘法，问（A,+,x）是否为域？为什么？（8分）

得分阅卷人四、证明题：（本题共2小题，满分16分.）

1.设/：R-R，VxeR有/（x）=2x.证明：/是（尺+）上的自同构.（8分）:

2.构造下列推理的证明（8分）：

前提：Vx（P（x）f。（幻）,一（「。》））.

结论：主（iQ（x）△-1P（x））.

一、证明下列各题

得分

2：1、（10分）证明蕴涵式：P人（P-»Q）n。

阅卷人

2、（10分）证明：£g为IT函数n/Clg沏-1函数。

5、3、50分）给定代数结构MM和40,1},X）,其中N是自然数集合,

x是数的

乘法。设广Nr{0,1},定义为:

/（»）=':n-2k,n,keN

否则

试证〈Mx〉三〈{0,1}'X）。

4、（10分）给定代数结构〈&*〉，其中R是实数集合，对R中任意元。和〃，*定

义如下：a*b=a+b+axb

试证明:〈&*〉是独异点。

二、求下列各题的解：

得分

1、试求下列公式的主析取范式和主合取范式（15分）:

阅卷人（尸］。）

2、（15分）设尺={〈0，1〉，〈。，2〉，〈0,3〉，〈1，2〉,。,3〉,〈2,3）},试求

⑴、R*R，（2）、而傅，（3）、KT{1},⑷、RDM，（5）、内刖］

3、（15分给定无向图G=（V,£），如图，试求:

FED

（1）从A到D的所有基本链；

（2）从A到D的所有简单链；

（3）长度分别是最小和最大的简单圈;

（4）长度分别是最小利最大的基本圈;

（5）从A到D的距离。

4、（15分）给定二部图G=化，区匕），如图

匕

业：信息与计算科学课程名称：离散数学学分：二_试卷编号

（K）

课程编号：4114600考试方式：闭卷考试时间：JOT.分钟

拟卷人（签字）：_______拟卷日期：_________审核人（签字）：_______

得分统计表:

题号―■二总分

得分一、证明

得夕下列

阅卷人

1、（10分）证明蕴涵式:P—QnPf(PAQ)

2、(10分)证明：AX(8—C)=(AX8)—(4XC)

3、(10分)给定群〈G，〉，则(G，)

为Abel群

222

<=>(Va)(Vb)(〃,bGG—>(6fh)=ab)

4、(10分)给定代数结构C'*)，其中S中元为实数有序对，*定义为

(a,b)*(c,d)=(a+c,b+d+2bd)试证⑸*〉是可交换独异点。

得分二、求下列各题的解：

_i.______________1、试求下列公式的主析取范式和主合取范式(15分):

阅卷人Pv(~1P-v-R)))

2、(15分)设夫={@"〉，〈仇。，《⑷「试求”⑻屈幻和^氏)。

3、（15分）给定有向图G=（V，E），如图，试求:

（1）、各结点的出度、入度和度；

（2）、从vi到V3的所有简单路和基本路；

（3）、所有简单回路和基本回路。

4、（15分）给定树G,试求对应二叉树

一、证明下列各题

1、（10分）证明蕴涵式:(PTQ'TQOPTQ

2、（10分）证明：£g为1T函数n/Clg为1-1函数。

3、（10分）给定代数结构〈Mx）和（{0』}，x）,其中N是自然数集合,

X是数的乘

法。设广Nf{0,1},定义为：

一、1，1=2k，〃,keN

八〃）=0否则

试证〈Mx〉三（{0,1},X）。

4、（10分）给定代数结构〈S，*〉，其中S中元为实数有序对，*定义为

（a,by（c,d）={a+c,b+d+2bd）f试证但*）是可交换独异点。

二、求下列各题的解：

得分

1、试求下列公式的主析取范式和主合取范式（15分）:

阅卷人Pv（「P->（Qv（「Q->R）））

2、（15分）设—={〈0，1〉，〈0,2），〈0,3〉，。，2〉,。,3）,〈2,3»,试求

⑴、R*R，⑵、RT。},（3）、R"T{I},（4）、网{吐（5）、穴IP}]

3、（15分）给定有向图G—〈V'£），如图，试求:

（1）、各结点的出度、入度和度；

（2）、从W到v」的所有简单路和基本路；

（3）、所有简单回路和基本回路。

4、（15分）给定树G,试求对应二叉树

答案:

一、1、

(「△(PfQ))fQ=「(P«PvQ))v。……2'o］Pv(Pv「Q)v。……2，

o「Pv(P△」Q)vQ......2'o(「PvP)人v」Q)vQ.......2'ov」Q)vQ

O「Pv(「QvQ)=T.......2'

或用推理方法，或用真值表方法(略)。

Clgy人VClgz。加人xgy△破人xgz

2、=xfy人对z=y=z......5分

“(/fig)—%△”(/Cig尸w<=>uf~'v/\ug~'v/\uf~'w/\ug~'w

=>uf~'v/\uf~］w=>v=w......5分

3、任给相，"GN,有三种情况：

(1)存在占水2cN,使机=2勺，〃=2%成立；......1分

(2)存在船％2GM使机=2自成立而不存在使〃=2与成立；或者反之；……1

分

(3)不存在配&eN,使机=2"〃=2"成立。……1分

对于(1),显然有了(〃?x〃)=/(2e)=lJ(〃?)x/(〃)=/(2"x/(2*2)=lxl=l,即

/(mxn)=/(/M)x/(/i).……3分

对于(2)(3),均有/(加'")=/(加”/(〃)。……丁分

因为f(mx〃)=0,加x〃#2*'f(m)xf(n)=0,m=2lc',n^2*2或％/2*'和〃=2*2

或加工2例和刀#2*2。……2分

综上所述，/("zx〃)=/(加)x/(n),故〈N,x)，{0,l},x)。

4、首先证明*满足结合律，任给x，y，zeR,因为

(x*y)*z=(x+y+xxy)*z=x+y+xxy+z+(x+y+xxy)xz

=/+y+z+xxy+xxz+yxz+xxyxz,

x*(y*z)=x*(y+z+yxz)=x+y+z+yxz+xx(y+z+yxz)

+y+z+yxz+xxy+xxz+xxyxz.

故a*y)*z=x*(y*z),因此，*满足结合律。……5分

其次证明*有幺元0,任给xeR,有：°*x=0+x+°xx=x,x*°=x+0+xx°=x,

故0是*的幺元。……5分

综上所述，依*〉是独异点。

(「PV」。)-(P］。)=」(「PV「。)v((P-「Q)A(~,QTP))•―2'

=(尸△。)v((「尸v［。)A(QvP))•••••♦2'

=(Pv((「Pv「。)A(PvQ)))A(2V((「Pv「。)A(PV。)))……2'

«(Pv-1Pv-n2)A(PvPve)A(ev^Pv-ne)A(PvPv2).......3'

二、］、o(PvQ)o%……3'

主析取范式为叫……3分

2、⑴、R*R={@2}，〈0,3〉,〈L3)}……3分

⑵、而{1}={〈1,2)43〉}……3分

⑶、内={(叫}……3分

(4)、网{1}]={2,3}……3分

⑸、/?-'{1!={0}……3分

3、(1)、从1至U〃的所有基本链共有10条，即：ABD,ABED,ABCD,ABCED,ABECD,AFED,

AFECD,AFEBD,AFEBCD,AFECBD.....3分

(2)、从月到〃的所有简单链共有14条，即除(1)的10条外，还有ABCEBD,ABECBD,

AFEBCED,AFECBED....3分

(3)、长度最小的简单圈共4个，即BCDB,BCEB,BDEB,CDEC,长度最大的简单.圈

共2个,即ABCEBDEFA,AFEBCEDBA....3分

(4)、长度最小的基本圈共4个，即同(3)；长度最大的基本圈有2个，为ABDCEFA；

ABCDEFA...3分；

⑸、。(人。)=2。......3分

4、乂到匕的最大匹配有多个，如{〈匕，％)，〈匕，％〉，〈匕，丫6〉，。5，口9〉},得分情况根据具体解

题过程考虑。

(P->Q)f(Pf(P人Q))o(「PvQ)-(「尸V(FA2))••••••2'

」(「尸v。)v(」Pv(P△Q))=(P人］。)v(「尸v(尸人Q))•―2'

=((P△vv((P人［。)v(P人Q))

=((PA「尸)A(「Pv」Q))v(((P△vP)人((PA［。))vQ))……2'

=(「P△「Q)v(尸△((Pv。)人(［。v2)))

=(「PA「。)V(PA((PvQ))=「PvvP........2'

一、1....2'

(x,y)GAx(5-C)<=>xGAAyG(5-C)....2'

C)....2'<^>(xGAAyeB)A(xeAAy^C)....2'

o(x,y〉EAx8A〈x,y)任AxC...2'=(x,y)£(4x5)_(AxC)....2'

乙、

3、充分性：因为〈G')是群，又对任意a/eG,有

(abY=a2b2=>(ab)(ab)=(aa)(bb)

=>a(ba)b=a(ab)b=>(ba)b=(ab)b

=>ha=ah....5'

可见，是可交换的，故(°')为Abel.

必要性：@)为Abel群，自然〈°，)是群；又对任意a/wG,有

(ab)2=(ah)(ab)=a(ba)h=a(ab)h

=(aa)(bb)=a2b2....5'

4、首先证明*是可结合的，任给SM，〈c,d〉,〈eJ)eS,有：

《a,b)*©d》*〈e,f)=ggb+d+2bd〉*&f〉

=<〃+c+e,》+d+/+2bd+2(/?+d+2bd»

=<〃+c+e,Z?+d+/+2hd+2bf+2df+4bdf)

伍b)*《c,cT)*(eQ)=(a,b)*〈c+d,d+f+2df)

=(a+c+e,b+e+/+2df+2b(d+/+

而=<〃+c+e,b+d+/+2hd+2hf+2df+4bdf),

故满足结合律，6*)是半群。……5分

其次证明*有幺元〈.°)，任给("MeS,有

〈0,0)*〈。/)=(0+。,0+/?+2x0x6)=〈〃力)，

(a,b〉*〈0,0〉=〈a+0,b+0+2xbx0)=«/〉.因此，〈0，°〉是幺元。……?分

最后，证明*满足交换律，任给〈"S)，(c,d)eS,有

{a,b)*{c,d)=(a+c,b+d+2hd)=(c,d)^{a,b)故*满足见换律。......3分

综上可知，⑸*)是可交换独异点。

Pv(「P-(Qv(「QT/?)))0Pv(Pv(Qv(Qv/?)))……5，

二、］oPvQvRoM。.......5'

2r(R)={a，b),(b,c),(c,a),〈a,a)，8,0〉,〈c,c)}......5分

s(R)={〈a/〉，8，c),(c,a)，a，a〉,〈c,0〉,(a,c)}......5分

t(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}...5分

+VV+VV+VV

£/(I)=2,(/"(1)=1;J(2)=1,6/-(2)=2;J(3)=1,J-(3)=1;

++

d(y4)=2,J-(v4)=2;d(vs)=1,J-(v5)=1.

3、(1)、1(%)=3,1(岭)=3,1(匕)=2,1(%)=4,1(以)=2.……§分

(2)、V>到匕的所有简单路共4条，它们是V"4V3,叩235叩4匕#"3#"5叩2叩3.

匕到匕的所有基本路共2条，它们是：匕丫2V4匕，匕匕匕・……5分

(3)、所有基本回路共3条，它们是:叩4M，岭14吁2”所有简单回路除上3

个基本回路外，还有1个,它是4%匕岭V4V5%……5分

4、根据解题过程分步给分。

((PfQ)->Q)->(PVQ)oT*Pv2)v2)v(PvQ)……1

=」((PA「Q)VQ)V(PVQ)=((「PVQ)AQ)V(PVQ)••-2'

((「PA「。)V(QA［。))v(Pv。)o((「PA「。)v(FvQ)……2'

一、1=(「PvPvQ)/\(「QvPvQ).......2'OTAT=T2'

或用真值表方法(略)。

xfr\gy^xfC\gz^xfy/\xgy/\xfz^xgz

2、=>^AVz=>y=z.......5'

w(/fig)/Ag)-1vvouf~lv/\ug~[v/\uf~]w/\ug~｛w

=>uf~xv/\uf~xw^>v=w....5r

3、任给如〃EM有三种情况：

(1)存在配火2wN,使用=2*〃=2人成立；……1分

(2)存在船&eN,使,〃=2自成立而不存在使〃=2和成立；或者反之；……1

分

(3)不存在占#2,使“=2",,〃=2八成立。1分

对于(1),显然有“〃?*〃)=/(2收)=1j(⑼xf(n)=f(2k')xf(2坛)=1x1=1,即

f(mxn)=f(m)xf(n);...3分

对于(2)(3),均有/(加x")=/0〃)x/(〃)。……2分

因为了("[X")=o,加X"#2g/(rn)X/(〃)=0,加=2占，"#2*?或加/2&和〃=2坛

或7nH2*和九二2检。...2分

综上所述,/(加x〃)=/("z)x/(〃)，故〈Mx〉/。/”)。

4、首先证明*满足结合律，任给％y，zeR,因为

(x*y)*z=(x+y+xxy)*z=x+y+xxy+z+(x+y+xxy)xz

=x+y+z+%xy+xxz+yxz+xxyxz,

x*(y*z)=x*(y+z+yxz)=x+y+z+yxz+xx(y+z+yxz)

同=x+y+z+yxz+xxy+xxz+冗xyxz.

故(x*y)*z=X*(y*Z),因此，*满足结合律。……5分，其次证明*有幺元0,任给XeR,

有：0*x=0+x+0xx=x,x*0=x+0+xx0=x,故。是*的幺元。……5分

综上所述，(民*〉是独异点。

Pv(「Pf(Qv(「Qf??)))=Pv(Pv(Qv(QvR)))……5，

二、1、=PvQvR....5'<=>M0主合取范式，

主析取范式为：叫v吗vm3V外vm5Vs.v叫。……5分

2、⑴、R*R=｛〈。，2〉，〈0,3〉,〈1,3))……3分

⑵、祈｛1｝=｛〈1,2〉,〈1,3)｝……3分⑶、k=｛〈L。〉｝……3分

⑷、即｛1｝]=｛2,3｝……3分⑸、内｛1｝=｛。｝……3分

，(“)=2,J-(v()=1；，(彩)=1,"一(彩)=2；△(匕)=1/一(也)=1；

++

d(v4)=2,J-(v4)=2；d(v5)=l,J-(v5)=l.

V3

3、⑴、^(I)=，^(V2)=3,J(V3)=2,J(V4)=4,J(V5)=2....5分

(2)、匕至-3的所有简单路共4条，它们是斗2”3,叩2叩5叩4匕，叩必用4匕呼2“3.

匕到匕的所有基本路共2条，它们是：丫必丫4V3，W43……5分

(3)、所有基本回路共3条，它们是：匕匕以％匕，匕丫4丫5匕#2V4V3%。所有简单回路除上3

个基本回路外,还有1个，它是“MV3V2彩……5分

4、根据解题过程分步给分。

专业：信息与计算科课程名称：离散数学学分：上_试卷编号（D）

字______

一.、第一部分

I（10分）写出下列公式的真值表

A=（内。）—

pQrmq—ir(w)

000011

001001

010111

011100

100111

101100

110111

111100

每错一处扣1分，扣到10分为止

2（10分）用等值演算法判断下列公式的类型

QA->

（2，）

=QA-iJp/q)（蕴涵等值式）

（2，）

0q八(pA-)q)（德摩根律）

（2，）

=IQ)（交换律，结合律）

(2，)

<=>/?A0（矛盾律）

（2，）

00（零律）

由最后一步可知，为矛盾式.

3（10分）求主析取范式

hTr

=(PAQ)V_T（析取范式）①

（0AQ）

=(7?AQ)/\(TV_r)

O(PA(?A—ir)v{p/\q/\r)

(3')

<=>gnh②

O(―,/A/jt?)A(—Ar

=(-1PA-iQA7)V(~yp/\(J/\r)V(pA-iQAr)V(°AQAr)

=ZZ7|VZ?iVZ%VZ^③

②，③代入①并排序，得

(»■>->(?)frO^v/zhvz^v小7砥(主析取范式)*J

4(10分)判断下面推理是否正确

若今天是1号，则明天是5号.今天是1号.所以明天是5号.

解设R今天是1号，q：明天是5号.O')

(用等值演算法)

O-I((-I/A//7)A/?)v(zG)

o-i/A/-i(?vq°)

o1(2')

推理正确

5(10分)用归缪法证明

前提：-i(pAQ)vr,r—s、->s,0结论：-yq

证明(用归缪法)

(1')

①Q结论否定引入

②is前提引入。')

(1‘)

③「5前提引入

(1')

④-17②③拒取式

(1')

⑤->(PAQ)vr前提引入

(1')

⑥-1(PA<7)④⑤析取三段论

(19

⑦->内-1。⑥置换

(19

⑧~»P①⑦析取三段论

(0

⑨P前提引入

(1')

10—10A/7⑧⑨合取

-、第i部分

1(10分)在一阶逻辑中将下面命题符号化

正数都大于负数

令夕(x)：x为正数，C(y)：y为负数0)

L(x,负:x>yG)

Vx(P(x)fVy(6(y)->£(x,y)))U)

u>X/处y(Fd)八G5)负)

2(10分)设偏序集<4w>如下图所示，

求力的极小元、最小元、极大元、最大元.

设6={“c,M,求6的下界、上界、下确界、上确界.

解极小元：a,b,