当前位置：文档之家› 离散数学样卷

离散数学样卷

1.设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当

我有时间时”符号化为（c）

A.P→Q

B.Q→P

C.P ?Q

D.?Q∨?P

2.设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑

步”符号化为（A）

A. ?p∧?Q

B. ?P∨?Q

C. ?(P?Q)

D.P??Q

3.下列语句中哪个是真命题？（D）

A.我正在说谎。

B.严禁吸烟。

C.如果1+2=3，那么雪是黑的。

D.如果1+2=5，那么雪是黑的。

4.下面哪个联结词运算不可交换？（B）

A.∧

B.→

C.∨

D.?

5.命题公式(P∧ (P→Q)) →Q是（）。

A.矛盾式

B.蕴含式

C.重言式

D.等值式

6.下列命题联结词集合中，哪一个是最小联结词组？（B）

A.{?,?}

B.{?,∨,∧}

C.{↑}

D.{∧,→}

7.已知A是B的充分条件，B是C的必要条件，D是B的必要

条件，则A是D的（）

A.充分条件

B.必要条件

C.充要条件

D.A、B、C都不对

(7) 重言式的否定式是（C）

A.重言式

B.矛盾式

C.可满足式

D.蕴含式

8.下面哪一个命题是假命题？（）

A.如果2是偶数，那么一个公式的析取范式惟一

B.如果2是偶数，那么一个公式的析取范式不惟一

C.如果2是奇数，那么一个公式的析取范式惟一

D.如果2是奇数，那么一个公式的析取范式不惟一

9.下面哪一组命题公式不是等值的？（）

A.?(A→B),A∧?B

B.?(A?B),(A∧?B)∨(?A∧B)

C.A→(B∨C),?A∧(B∨C)

D. A→(B∨C),(A∧?B)→C

A.8

B.3

C.5

D.0

10.命题公式?(P∧Q)→R的主析取范式中含极大项的个数为（）

A.0

B.3

C.5

D.8

11.命题公式?(P∧Q)→R的成真赋值为（）

A.000,001,110

B.001,011,101,110,111

C.全体赋值

D.无

1.设P：我生病，Q：我去学校

(1).命题“我虽然生病但我仍去学校”符号化为。

(2).命题“只有在生病的时候，我才不去学校”符号化

为。

2.设P：我有钱，Q：我去看电影。

命题“当且仅当我有钱时，我才去看电影”符号化为。

3.(P∧(P∨Q)) →R?。

4.P→(P→Q) 。

5.对于下列各式

(1).(?P∧Q)∨(?P∧?Q)可化简为。

(2).Q→(P∨(P∧Q)) 可化简为。

(3).(?P∨Q)?(?Q→?P)∧P可化简为。

6.命题公式P∨(Q∧?R)的成真赋值为，成假赋值

为。

9. 若且则称X是公式A的子公式。

10.写出表中各列所定义的命题联结词。

P Q P ①

Q P ②Q

1 1 1 0

1 0 0 1

0 1 0 1

11.命题公式?(P→Q)的主析取范式为①，主合取范

式的编码表示为②。

12.已知公式A(P,Q,R)的主合取范式为M0∧M3∧M5，它的主析取范

式为（写成编码形式）。

13.命题公式?(P?Q)的主析取范式为①，其编码表示

为②，主合取范式的编码表示为③。

三、综合题

1.给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下

列命题公式的真值：

(1).(?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S)

(2).(P∨(Q→(R∧?P)))?(Q∨?S)

2.命题联结词“↓”定义为P↓Q??(P∨Q)

(1).构造P↓Q的真值表；

(2).证明∨、∧、?可以用仅含联结词↓的等值公式表示。

3.化简下列命题公式：

(1).A∨(?A∨(B∧?B))

(2).((A→B)?(?B→?A)∨C

4.用真值表判断下列各式是否为重言式：

(1).((?P∨Q)∧(Q→R))→?(P∧?R)

5.设命题公式A的真值表如表所示，试求出A的主析取范式和

：

P Q A

1 1 1

1 0 1

0 1 0

0 0 1

6.用等值演算法证明P∧(P→Q) →Q是重言式。

7.证明下列命题的等值关系：

(1).(P→Q)∧(R→Q)?(P∨R)→Q

(2).(P∨Q)∧?(P∧Q)??(P?Q)

8.设计一种简单的表决器，表决者每人座位旁边有一按钮，若同

意则按下按钮，否则不按按钮，当表决结果超过半数时，会场

电铃就会响，否则铃不响。试以表决人数为3人的情况设计表

决器电路的逻辑关系。

9.观察下列推理过程，是否正确，结论是否有效，说明理由。

(1).①P∧Q→R P

(2).②P→R T①I

(3).③P P

(4).④R T②③I

所以P∧Q→R，P?R。

10.用推理规则证明下列推理的正确性：如果A努力工作，那么B

或C感到愉快；如果B愉快，那么A不努力工作；如果D愉

快那么C不愉快。所以，如果A努力工作，则D不愉快。

谓词逻辑

一、选择题

1.若个体域为整体域，下列公式中哪个值为真？（）

A.?x?y(x+y=0)

B.?y?x(x+y=0)

C.?x?y(x+y=0)

D.??x?y(x+y=0)

2.设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”

符号化为（）

A.?x(A(x)∧B(x))

B.??x(A(x)→?B(x))

C.??x(A(x)∧B(x))

D.??x(A(x)∧?B(x))

3.设个体域A={a,b}，公式?xP(x)∧?xS(x)在A中消去量词后应

为（）

A.P(x)∧S(x)

B.P(a)∧P(b)∧(S(a)∨S(b))

C.P(a)∧S(b)

D.P(a)∧P(b)∧S(a)∧S(b)

4.下列各式哪个不正确？（）

A.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)

B.?x(P(x)∧Q(x))??xP(x)∧?xQ(x)

C.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)

D.?xP(x)∧Q)??xP(x)∧Q

二、填空题

1.令R(x)：x是实数，Q(x)：x是有理数。

(1)命题“虽然有些实数是有理数，但并非一切实数都是有理

数”。则其符号化可表示为。

2.设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，

则命题“并非所有智能工作都能由计算机来做”符号化

为。

3.取个体域为整数集，给定下列公式：

(1).?x?y(x·y=0) (2).?x?y(x·y=1)

(3)?x?y(x·y=2) (4)?x?y?z(x-y=z)

(5).x-y=-y+x (5).?x?y(x·y=y)

(7)?x(x·y=x) (8).?x?y(x+y=2y)

上面公式中，真命题的有①，假命题的有

②。

4.?x(P(x)∨Q(x))，其中P(x):x=1，Q(x):x=2，当论域为{1,2}时，

其真值为

①，当论域为{0,1,2}时，其真值为②。

5.谓词公式?x(P(x)→Q(x,y)∨?zR(y,z))→S(x)的前束范式

为。

三、综合题

1.令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“x

其中个体域为自然数集，用以上符号表示下列命题：

(1).没有x<0，且若x>0当且仅当有这样的y，使得x≥y。

(2).并非对一切x，都存在y，使得x≤y。

(3).对任意的x，若x+y=x，当且仅当y=0。

2. 假设论域为自然数集N={1,2,3,……}，a为2，P为命题“2>1”；

A(x)表示“x>1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值：

?x(A(x)→(A(a)→B(x))→((P→?xA(x))→B(a))

3.求下面谓词公式

?x(X(x)∧?y(X(y)→((Y(x,z)∧Y(y,z)∧p)→?t(X(t)→(Y(x,t)→Y(y,t

))))))

在赋值(z;p;X(x);Y(x,y))=(2;1;x是自然数;x

4.改正下面证明中的错误：

前提：?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z)))；

结论：??zP(z)→?x?y(S(x,y)→?M(y))。

证明过程：

①?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z)))；P

②?y(S(b,y)∧M(y))→?z(P(z)∧R(b,z)) ①US

③??zP(z) P(附加前提)

④?z(?P(z)) ③T,E

⑤?P(a) ④US

⑥?P(a)∨?R(b,a) T,⑤I

⑦?z(?P(z)∨?R(b,z)) ⑥UG

⑧??z(P(z)∧R(b,z)) ⑦T,E

⑨??y(S(b,y)∧M(y)) ②,⑧T,L

⑩?y(?S(b,y)∨?M(y)) ⑨T,E

⑾?y(S(b,y)→?M(y)) ⑩T,E

⑿?x?y(S(x,y)→?M(y)) ⑾UG

⒀??zP(z)→?x?y(S(x,y)→?M(y)) CP

集合论

1设A={?}，B=P(P(A))，以下正确的式子是（）

A．{?,{?}}∈B B．{{?,?}}∈B

C．{{?},{{?}}}∈B D．{?,{{?}}}∈B

2．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（）

A．(X-Y)-Z=X-(Y∩Z)

B ．(X-Y)-Z=(X-Z)-Y

C ．(X-Y)-Z=(X-Z)-(Y-Z)

D ．(X-Y)-Z=X-(Y ∪Z)

3.某集合A={1，2，3，4}上的二元关系R={<1,1>,<2,2>,<3,3>,<3,4>,<4,3>}则R 具哪些性质，其关系矩阵是什么？。

4.用列元素法表示以下集合。

（1）}7|{2≤∧∈=x N x x A 。

（2）}33||{<-∧∈=x N x x A 。

（3）}0)1(|{2≤+∧∈=x R x x A 。

5. 计算B A B A B A B A ⊕-,,, 。

（1）},{},},,{{d c B c b a A ==。

（2）}2|{},3|{≥∧∈=<∧∈=x N x x B x N x x A

（3）}2|{},0|{≥∧∈=<∧∈=x Z x x B x Z x x A 。

6. 设}4,3,2,1{=S ，R 为S 上的关系，其关系矩阵是：

?????

???????0001

100000011001，则求（1）R 的关系表达式。（2）=domR ； =ranR ；

（3）R R

（4）1-R 的关系图

7. 设}6,,2,1{ =S ，下面各式定义的R 都是S 上的关系，分别列出R 的元素。

（1）}.)(,,{2S y x S y x y x R ∈-Λ∈><=

（2）}./,,{是素数y x S y x y x R Λ∈><=

离散数学第五版模拟试题及答案

《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化，其真值为。二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}，则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的主析取范式和主合取范式，并写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0

离散数学期末试题

离散数学考试试题（A 卷及答案）一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有：甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。

离散数学全部试卷

离散数学试题与答案试卷一一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数）则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为。 6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。 8．图的补图为。二、选择 20% （每小题 2分） 1、下列是真命题的有（） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（） A B C

?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = ； C．f : R→I , f (x) = [x] ；D．f :I→N, f (x) = | x | 。（注：I—整数集，E—偶数集，N—自然数集，R—实数集） 8、图中从v1到v3长度为3 的通路有（）条。 A．0；B．1；C．2；D．3。 9、下图中既不是Eular图，也不是Hamilton图的图是（） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4 度结点。 A．1；B．2；C．3；D．4 。

(完整版)离散数学试卷及答案

离散数学试题（A卷答案）一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，，，，，，}， (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系，为什么？解 (1) R 的关系矩阵为： ??? ??? ? ? ? ?=100001100010100 10110 11111 )(R M (2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；ij r ＋ji r ≤1，故R 是反对称的；可计算对应的关系矩阵为：

离散数学试卷及答案一

一、单项选择题(本大题共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},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x

离散数学试题(2006)_A(答案)

一、填空题（每小题3分，共15分） 1.设F(x)：x是苹果，H(x，y)：x与y完全相同，L(x，y)：x=y，则命题“没有完全相同的苹果”的符号化（利用全称量词）为?x?y(F(x)∧F(y)∧?L(x，y)→?H(x，y))． 2.命题“设L是有补格，在L中求补元运算‘′’是L中的一元运算”的真值是0． 3.设G={e，a，b，c}是Klein四元群，H=?a?是G的子群，则商群G/H={?a?，{b，c}}={{e，a}，{b，c}}． 4.设群G=?P({a，b，c})，⊕?，其中⊕为集合的对称差运算，则由集合{a，b}生成的子群?{a，b}? ={?，{a，b}}． 5.已知n阶无向简单图G有m条边，则G的补图有n(n-1)/2-m 条边．二、选择题（每小题3分，共15分） 1.命题“只要别人有困难(p)，小王就会帮助他(q)，除非困难已经解决了(r)”的符号化为【B】A．?(p∧r)→q．B．(?r∧p)→q． C．?r→(p∧q)．D．?r→(q→ p)． 2.设N为自然数集合，“≤”为通常意义上的小于等于关系，则偏序集?N，≤?是【C】 A．有界格．B．有补格． C．分配格．D．布尔代数． 3.设n (n≥3) 阶无向图G=?V，E?是哈密尔顿图，则下列结论中不成立的是【D】A．?V1?V，p(G-V1)≤|V1|．B．|E|≥n． C．无1度顶点．D．δ(G)≥n/2． 4.设A={a，b，c}，在A上可以定义个二元运算，其中有个是可交换的，有个是幂等的．【A】A．39，36，36．B．39，36，33． C．36，36，33．D．39，36，39． 5.下列图中是欧拉图的有【C】 A．K4，3．B．K6． C．K5．D．K3，3．三、计算与简答题（每小题8分，共40分） 1.利用等值演算方法求命题公式(p∨q) → (q→p)的主合取范式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值． (p∨q) → (q→p) ??(p∨q)∨(?q∨p) ?(?p∧?q)∨(?q∨p) ?(?p∨?q∨p)∧(?q∨?q∨p) ??q∨p?p∨?q ?M1 此为公式的主合取范式．该公式的主析取范式是m0∨m2∨m3．公式的成真赋值为00，10，11．公式的成假赋值为01．哈尔滨工程大学试卷考试科目：离散数学（041121，041131-32）考试时间：14:00-16:30 1

离散数学试卷及答案(2)

一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为。 2、设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是。 3、设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是；是否有幂等性；是否有对称性。 7、4阶群必是群或群。 8、下面偏序格是分配格的是。

9、n 个结点的无向完全图K n 的边数为，欧拉图的充要条件是。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为。二、选择 20% （每小题2分） 1、在下述公式中是重言式为（） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（），成真赋值的个数为（）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有（）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为

离散数学期末试题及答案完整版

离散数学期末试题及答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).

离散数学及答案

全国2010年7月自学考试离散数学试题课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（） A ．???? ? ?????001110101 B ．???? ? ?????101110001

自考离散数学试题及答案

一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（） A ．一定是等价关系 B ．一定是相容关系

离散数学期末试卷A卷及答案

《离散数学》试卷（A 卷）一、选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.

2、公式)(Q P Q ?∨∧的主合取范式为。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。（ F ） 2、“张刚和小强是同桌。”是复合命题。（ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。（ T ） 4、)(T S R T R S R ??????。（ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。（ T ） 6、若f 、g 分别是单射,则g f ?是单射。（ T ） 7、若g f ?是满射，则g 是满射。（ F ） 8、若A B ?，则)()(A P B P ?。（ T ） 9、若R 具有自反性，则1-R 也具有自反性。（ T ） 10、B A ∈并且B A ?不可以同时成立。（F ）四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问（１）三门课程都不选的学生有多少？（２）只选修计算机课程的学生有多少？