离散数学试卷及答案

离散数学试题与答案试卷一

一、填空 20% （每小题2分）

1．设 A?{x|(x?N)且(x?5)},B?{x|x?E且x?7}（N：自然数集，E+ 正偶

数） 则 A?B? 。 2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 。

3．设P，Q 的真值为0，R，S的真值为1，则

A B C ? ?(P?(Q?(R??P)))?(R??S)的真值= 。

4．公式(P?R)?(S?R)??P的主合取范式为 。

5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x) 在I下真值为 。

6．设A={1，2，3，4}，A上关系图为

则 R2 = 。

离散数学试题(A卷答案)

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P?(P∨Q∨R) 2)?(P?Q)∧Q 3)(P?Q)∧?R

解：1)重言式；2)矛盾式；3)可满足式

二、（10分）求命题公式(?P?Q)?(?Q∨P)的主析取范式，并求成真赋值。

解：(?P?Q)?(?Q∨P)?(P∨Q)?(?Q∨P)??(P∨Q)∨(?Q∨P)

?(?P∧?Q)∨?Q∨P??Q∨P?((P∨?P)∧?Q)∨(P∧?Q)∨(P∧

Q)

?(?P∧?Q)∨(P∧?Q)∨(P∧?Q)∨(P∧Q)? m0∨m2∨m3

成真赋值为：00、10、11。

三、（10分）证明下列命题的等值关系：(P∨Q)∧?(P∧Q)??(P?Q）

证明：(P∨Q)∧?(P∧Q)?(P∨Q)∧(?P∨?Q)?(P∧?Q)∨(Q∧?P)

??((?P∨Q)∧(?Q∨P))??((P?Q)∧

(Q?P))??(P?Q）

四、（10分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。 命题符号化为?x（F（x）?G（x）），F（a）?G（a）

一、 填空 10% （每小题 2分）

1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统，S是布尔格?A,??，中所有原子的集合，则

?A,?,?,?? ～ 。

2、 集合S={α，β，γ，δ}上的二元运算*为

* α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么，代数系统中的幺元是 , α的逆元是 。

3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：[i]?3[j]?[(i?j)mod3]，则+3的运算表为 ；是否构成群 。 4、 设G是n阶完全图，则G的边数m= 。

5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。

二、 选择 20% （每小题 2分）

1、 在有理数集Q上定义的二元运算*，?x,y?Q有

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选

项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路

2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14

3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c)

B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉

离散数学试卷（25）

166

一、填空题：（每空1分，本大题共15分）

1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2．命题公式)(Q P →?的主析取范式为 ，主合取范式的编

码表示为 。

3．设E 为全集， ，称为A 的绝对补，记作～A ，

且～（～A ）= ，～E = ，～Φ= 。

4．设},,{c b a A =考虑下列子集

}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =，}},,{{4c b a S = }}{},{},{{5c b a S =，}},{},{{6c a a S =

则A 的覆盖有 ，A 的划分有 。

5．设S 是非空有限集，代数系

离散数学试卷（十三）

一、 填空 10% （每小题 2分）

1、Z??{x|x?Z?x?0}，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算

的幺元是 ，零元是 。 2、代数系统中，|A|>1，如果e和?分别为的幺元和零元，

则e和?的关系为 。

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

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

5、一个图是平面图的充要条件是 。

二、 选择 10% （每小题 2分）

1、 下面各集合都是N的子集，（ ）集合在普通加法运算下是封闭的。 A、{x | x 的幂可以被16整除}； B、{x | x 与5互质}； C、{x | x是30的因子}； D、{x | x是30的倍数}。

2、 设G1??{0,

离散数学期末试题(B卷)

一、单项选择题（每小题1分，共15分。四选一）

1、设Φ是一个空集，则下列之一哪一个不成立（）。 ①、Φ∈Φ

②、Φ?Φ

③、Φ∈{Φ}

④、Φ?{Φ}

2、如果命题公式G=P∧Q，则下列之一哪一个成立（）。 ①、G=?(P→Q)

②、G=?(P→?Q)

③、G=?(?P→Q)

④、G=?(?P→?Q)

3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（）个二元关系。 ①、n

m

②、m

n

③、m×n ④、2

m×n

4、在有补分配格中，?a,b∈L，a≤b当切仅当下列（）成立。 ①、a?b＝b

②、a?b＝a

③、a＇?b＝0

④、a＇?b＝1

5、若是一个群，则运算“*”一定满足（）。 ①、交换律

②、消去律

③、幂等律

④、分配律

6、量词的约束范围称为量词的（）。 ①、定义域

②、个体域

③、辖域

④、值域

7、下列公式中，（）是析取范式。 ①、?(P∧Q)

②、?(P∨Q)

③、(P∨Q)

④、(P∧Q)

8、设G是一个12阶循环群，则该群一定有（）个不变子群。 ①、2

②、4

③、6

④、8

9、图的构成要素是（

试卷二试题与答案

一、填空 20% （每小题2分）

1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为

；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P

P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 。

3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系

R=

试卷二试题与答案

一、填空

1、 设P：你努力，Q：你失败。

2、 “除非你努力，否则你将失败”的符号化为； 3、 “虽然你努力了，但还是失败了”的符号化为 。 2、论域D={1，2}，指定谓词P

则公式 x yP(y,x)真值为 。

3设A={2，3，4，5，6}上的二元关系R { x,y |x y x是质数}，则

（列举法）。

R的关系矩阵MR=

。 4、 设A={1，2，3}，则

A上既不是对称的又不是反对称的关系R= ； A上既是对称的又是反对称的关系R= 。 5、设代数系统<A，*>，其中A={a，b，c},

则幺元是 ；是否有幂等 性 ；是否有对称性 。

6、4阶群必是 群或

群。

7、下面偏序格是分配格的是 。

8、n个结点的无向完全图Kn的边数为 。 二、选择

1、在下述公式中是重言式为（ ）

A．(P Q) (P Q)；B．(P Q) ((P Q) (Q P))；

C． (P Q) Q； D．P (P Q)。

2、命题公式 ( P Q) ( Q P) 中极小项的个数为（ ），成真赋值的个数为（

试卷二试题与答案

一、填空 20% （每小题2分）

1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为

；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P

P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 。

3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系

R=