离散数学期末考试复习题及参考答案-专升本

一、填空题

1、若P，Q为二命题，当且仅当 。 PQ真值为1，2、对公式(yP(x,y)zQ(x,z))xR(x,y)中自由变元进行代入的公式为 。 3、xF(x)(xG(x))的前束范式为 。 4、设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则 被称为全称量词消去规则，记为US。 5、与非门的逻辑网络为 。

Z6、{x|xZx0}，*表示求两数的最小公倍数的运算（Z表示整数集合），

对于*运算的幺元是 ，零元是 。 7、代数系统中，|A|>1，如果e和分别为的幺元和零元， 则e和的关系为 。

8、设是一个群，是阿贝尔群的充要条件是 。

9、图的完全关联矩阵为 。

10、一个图是平面图的充要条件是 。 二、选择题

1、下列各符号串，不是合式公式的有（ ）。

A、(PQ)R； B、((PQ)(RS)； C、PQR； D、((PQ)R)S。

2、下列语句是命题的有（ ）。

A、2是素数；B、x+5 > 6；C、地球外的星球上也有人；D、这朵花多好看呀！。 3、下列公式是重言式的有（ ）。

A、(PQ)；B、(PQ)Q；C、(QP)P；D、(PQ)P

4、下列问题成立的有（ ）。

若ACBC，则AB； B、若ACBC，则AB； C、若AB，则AB； D、若AB，则AB。

5、命题逻辑演绎的CP规则为（ ）。

A、在推演过程中可随便使用前提；

B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C、如果要演绎出的公式为BC形式，那么将B作为前提，设法演绎出C；

D、设(A)是含公式A的命题公式，则可用B替换(A)中的A。 BA，

6、命题“有的人喜欢所有的花”的逻辑符号化为（ ）。

设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y A、B、x(M(x)y(F(y)H(x,y)))；x(M(x)y(F(y)H(x,y)))； C、x(M(x)y(F(y)H(x,y)))；D、x(M(x)y(F(y)H(x,y)))。 7、公式xy(P(x,y)Q(y,z))xP(x,y)换名（ ）。

A、B、 xu(P(x,u)Q(u,z))xP(x,y)；xy(P(x,u)Q(u,z))xP(x,u)；C、D、 xy(P(x,y)Q(y,z))xP(x,u)；uy(P(u,y)Q(y,z))uP(u,y)。8、给定公式xP(x)xP(x)，当D={a,b}时，解释（ ）使该公式真值为0。

A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1 9、下面蕴涵关系成立的是（ ）。

A、xP(x)xQ(x)x(P(x)Q(x))； B、xP(x)xQ(x)x(P(x)Q(x))； C、xP(x)xQ(x)x(P(x)Q(x))； D、xyA(x,y)yxA(x,y)。 10、下列推理步骤错在（ ）。

①yyF(x,y)

P

②yF(z,y) ③F(z,c) ④xF(x,c) ⑤yxF(x,y)

US① ES② UG③ EG④

A、①→②；B、②→③；C、③→④；D、④→⑤。

11、下面各集合都是N的子集，（ ）集合在普通加法运算下是封闭的。

A、{x | x 的幂可以被16整除}； B、{x | x 与5互质}； C、{x | x是30的因子}； D、{x | x是30的倍数}。 12、设G1{0,1,2},，G2{0,1},*，其中表示模3加法，*表示模2乘法，则积代数G1G2的幺元是（ ）。

A、<0,0>； B、<0,1>； C、<1,0>； D、<1,1> 。

13、设集合S={1,2,3,6}，“≤”为整除关系，则代数系统< S , ≤ >是（ ）。

A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统。

14、设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=（ ）。

A、n·k； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。

15、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有（ ）个4度结点。 三、逻辑判断题

1、下列命题相容吗？AB, (BC), A

2、用范式方法判断公式 (PQ)(PR),PQR 是否等价。 3、（10分）下列前提下结论是否有效？

今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。 判断题

4、（ ）设S={1,2}，则S在普通加法和乘法运算下都不封闭。

5、（ ）在布尔格中，对A中任意原子a，和另一非零元b，在ab或ab中有且仅有一个成立。

6、（ ）设S{x|xZx0}N，+,·为普通加法和乘法，则是域。

7、（ ）一条回路和任何一棵生成树至少有一条公共边。

8、（ ）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i = t-1。 四、计算题

1、给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：(QR)(PR)的真值。

2、给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式yxL(x,y)的真值。 证明题

3、对代数系统，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）中的每个元素在右逆元必定也是左逆元。

（2）每个元素的逆元是唯一的。

4、设A , ,,是一个布尔代数，如果在A上定义二元运算☆，为

a☆b(ab)(ab)，则是一阿贝尔群。

5、证明任一环的同态象也是一环。 6、（8分）若GV,E的连通平面图，则e五、逻辑推理题

1、所有有理数是实数，某些有理数是整数，因此某些实数是整数。

2、符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。

3、某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间

(Vv,Ee)是每一个面至少由k(k≥3)条边围成

k(v2) 。 k2有边（其图如右），问至少需几天？

4、用washall方法求图并判断图的连通性。

的可达矩阵，

5、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？

6、用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。

若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。

参考答案

一、填空题

1、P，Q的真值相同；2、3、(yP(u,y)zQ(u,z))xR(x,v)；x(F(x)G(x))；4、xA(x)A(y)；5、

。

6、1，不存在；7、e；8、a,bG有(a*b)*(a*b)(a*a)*(b*b)； 9、

e1 1 -1 0 0 e2 1 0 -1 0 e3 e4 0 0 1 -1 e5 v1 v2 v31 0 0 -1 0 1 -1 0 v4 二、选择题

题目 1 10、它不包含与K3, 3或K5在2度结点内同构的子图。

2 3 B 13 C 4 C、D 14 D 5 C 15 A 6 D 7 A 8 9 10 C 答案 B、C A、C 题目 答案 11 A，D 12 B B、C B、D 三、逻辑判断

1、

①AB ②A ③B ④(BC) ⑤BC ⑥B ⑦F

P P T①②I P T④E T⑤I T③⑥I

所以AB, (BC), A不相容。

2、

(PQ)(PR)(PQ)(PR)((PQ)(RR))((PR)(QQ))(PQR)(PQR)(PQR)M100M101M110PQRP(QR)(PQ)(PR) ((PQ)(RR))((PR)(QQ))(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)M100M101M110所以两式等价。

3、设P：今天天晴，Q：今天下雨，R：我不看书，S：我看电影

符号化为：PQ , PS,①PS ②SR ③PR ④RP ⑤PQ ⑥PQ ⑦RQ 结论有效。

题目 答案 4 Y 5 Y 6 N 7 N 8 N P P T①②I T③I P T⑤E T④⑥I

SRRQ

四、计算题

1、解：P，Q是真命题，R是假命题。

(QR)(PR)(10)(11)010

2、

yxL(x,y)y(L(2,y)L(3,y))(L(2,2)L(3,2))(L(2,3)L(3,3))(10)(01)000

3、证明

（1）设a,b,cA，b是a的右逆元，c是b的右逆元，由于b*(a*b)b*eb，

eb*cb*(a*b)*c(b*a)*(b*c)(b*a)*eb*a

所以b是a的左逆元。

（2）设元素a有两个逆元b、c，那么

bb*eb*(a*c)(b*a)*ce*cc

a的逆元是唯一的。 4、证明：

[乘]，，在A上封闭，  运算☆在A上也封闭。 [群] a,b,cA

(a☆b)☆c((ab)(ab))☆c(((ab)(ab))c)((ab)(ab)c)(abc)(abc)((ab)(ab)c)(abc)(abc)(((ab)(ab))c)(abc)(abc)(abc)(abc)同理可得:a☆(b☆c)(abc)(abc)(abc)(abc)

(a☆b)☆ca☆(b☆c) 即☆满足结合性。

[幺] aA,a☆00☆a(0a)(0a)0(1a)0aa 故全下界0是A中关于运算☆的幺元。

[逆] aA,(a☆a)(aa)(aa)000 即A中的每一个元素以其自身为逆元。

[交] a☆b(ab)(ab)(ba)(ba)b☆a 即运算☆具有可交换性。 所以是Abel群。 5、证明:

设A,,•是一环,且f(A),,是关于同态映射f的同态象。 由A,是Abel群，易证f(A),也是Abel群。

A,•是半群，易证f(A),也是半群。

现只需证：对是可分配的。

b1,b2,b3f(A),则必有相应的a1,a2,a3使得:f(ai)bi,i1,2,3 于是

b1(b2b3)f(a1)(f(a2)f(a3))f(a1)(f(a2a3))f(a1(a2a3))f((a1a2)(a1a3))f(a1a2)f(a1a3)(f(a1)f(a2))(f(a1)f(a3))(b1b2)(b1b3)

同理可证(b2b3)b1(b2b1)(b3b1) 因此f(A),,也是环。 6、证明：

设G有r个面，

deg(ri)2e,而deg(ri)ki1r(1ir)2ekr即r2e k而ver2,故ve2rk(v2) 。 2即ekk2五、逻辑推理题

1、解：设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数 符号化：前提：x(Q(x)R(x))，x(Q(x)I(x))结论：x(R(x)I(x)) ①x(Q(x)I(x)) ②Q(c)I(c) ③x(Q(x)R(x)) ④Q(c)R(c) ⑤Q(c) ⑥R(c) ⑦I(c) ⑧R(c)I(c)

P ES① P US③ T②I T④⑤I T②I T⑥⑦I

⑨x(R(x)I(x)) EG⑧

2、解：F(x)：x是病人，G(x)：x是医生，H(x)：x是骗子，L(x,y)：x相信y 符号化：前提：x(F(x)y(G(y)L(x,y)))x(F(x)y(H(y)L(x,y))) 结论：x(G(x)H(x)) ⑴x(F(x)y(G(y)L(x,y))) ⑵F(a)y(G(y)L(a,y)) ⑶F(a)

⑷y(G(y)L(a,y))

⑸x(F(x)y(H(y)L(x,y))) ⑹F(a)y(H(y)L(a,y)) ⑺y(H(y)L(a,y)) ⑻y(L(a,y)H(y)) ⑼G(z)L(a,z) ⑽L(a,z)H(z) ⑾G(z)H(z) ⑿x(G(x)H(x)) 3、

解：(G)即为最少考试天数。

用Welch-Powell方法对G着色：v9v3v7v1v2v4v5v8v6 第一种颜色的点 v9v1v4v6，剩余点v3v7v2v5v8 第二种颜色的点 v3v7v5，剩余点v2v8 第三种颜色的点 v2v8 所以(G)≤3

P ES⑴ T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾

任v2v3v9构成一圈，所以(G)≥3 故(G)=3

所以三天下午即可考完全部九门课程。 4、

01解：A(G)00011010 001100

011：A[2，1]=1，Ai

00000111001011A； 2： A[4，2]=1，i0110011011 001111011011 00111101A3： A[1，3]=A[2，3]=A[4，3]=1，i0111i4： A[k，4]=1，k=1，2，3，4，A11111111

111111p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。 5、

解：用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为 此图中的Hamilton回路即是圆桌安排座位的顺序。 Hamilton回路为a b d f g e c a。 6、 解：(1)

W(T)24345392728283

（1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输

e

传输它们的最优前缀码为{0000，0001，001，01，10，11} 。