吉林大学离散数学期末考试

厦门大学《离散数学》课程试卷

软件学院2008年级

主考教师：金贤安 试卷类型：（A卷）

一、 选择题（共10题，每题3分，共30分）CDDAC DCADD

1、下列语句为命题的是（ ）。

A．勿踏草地；。

B．你去图书馆吗？； C．月球上有水； D．本命题为假。

2．下列推理中，（ ）是错误的。

A. 如果x是有理数，则它为整数。1/2是有理数。所以1/2是整数。

B. 若周末气温超过30度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。 C. 下午小明或者去看电影，或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。 D. 若a能被4整除，则a能被2整除。a能被2整除。因此a能被4整除。 3．谓词公式?x(P(x)??yR(y))?Q(x)中的x( )。 A．只是约束变元 B．只是自由变元

C．既非约束变元又非自由变元 D．既是约束变元又是自由变元

4. 下列关系中，（ ）不是等价关系。 A. 非空集合的幂集的元素间包含关系； B. 集合之间的等势关系； C. 公式之间的等值关系； D. 图之间的同构关系。

5. 下面等值式中，（ ）是不正确的。 A. ?x(A(x)?B(x))??xA(x)??x

离散数学试题(B卷答案1）

一、证明题（10分）

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

证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)

?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R

2) ?x (A(x)?B(x))? ?xA(x)??xB(x)

证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))

??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)??xB(x)

二、求命题公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）。

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

?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

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

(P∧Q∧R)

?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6

三、推理证明题（10分）

1） C∨D， (C∨D)? ?E，

2014-2015学年第二学期期末《离散数学》大作业

一、简要回答下列问题：（每小题3分，共30分）

1．请给出集合运算的等幂率。 答：等幂律 A?A=A，A?A=A

2．请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。 答：设A={1,2,3}, R={（1，1），（2，2），（3，3）} 既对称又反对称。

3．设A={1，2，3}，问全域关系是否具有自反性，对称性 ？ 答：是，全域关系具有自反性、对称性

4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={4,3}，求M的上界，下界。 答：上界 无 下界 1

5．关于P，Q，R请给出使极小项m1，m7为真的解释。

答：P=0,Q=0,R=1, ?P∧?Q∧R，记为m1 取1值，为真； P=1,Q=1,R=1，P∧Q∧R 记为m7 取1值，为真。

6．什么是图中的回路，请举一例。

设G=(P,L)是图，(v0 ,v1, …, vn)是G中从v0 到vn的路，称此路为简单路，如果 （1） v0 , …, vn-1互不相同 （2） v1 , …, vn互不相同

显然，一条简单路(v0 ,v1, …, vn)，除v0与 vn可以相同外，其他任意

广东技术师范学院

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 120 分钟

系别、班级： 姓名： 学号：

一．填空题（每小题2分，共10分）

1. 谓词公式 xP(x) xQ(x)的前束范式是__ x y¬P(x)∨Q(y) __________。 2. 设全集E 1,2,3,4,5 ,A 1,2,3 ,B 2,5 ,则A∩ _{4,5}____，

3. 设A a,b,c ,B a,b ，则 (A) (B) __ {{c},{a,c},{b,c},{a,b,c}} __________，

(B) (A) _____Φ_______。

4. 在代数系统（N，+）中，其单位元是0，仅有 5．如果连通平面图G有n个顶点，e条边，则G有___e+2-n____个面。

二．选择题（每小题2分，共10分）

1. 与命题公式P (Q R)等价的公式是（ ）

（A）(P Q) R （B）(P Q) R （C）P (Q R) （D）P (Q R) 2. 设集合A a,b,c ,A上的二元关系R a,a , b,b 不具备关系( )

离散试卷及答案 离散数学试题(A卷及答案）

一、证明题（10分）

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

证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R)

?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R

2)?x(A(x)?B(x))? ?xA(x)??xB(x)

证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)??xB(x) 二、求命题公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）

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

?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6

三、推理证明题（10分）

1） C∨D, (C∨D)? ?E, ?

一、简答题（共50分）

1. （4分）设集合G={a,b,c}，试定义G上的“· ”运算，使得(G，·)构成一个群（给出运算表）。并指出(G，·)中的单位元和每个元素的逆元素。 2. （2分）n（n>1）元有限群中，一共存在多少个幂等元？

3. （2分）设?=(1 3 2 4)，?=(1 3 4)，请把??写成若干对换乘积的形式。 4. （2分）设G是3次对称群，H={I, (2 3)}是G的子群，求H的所有左陪集。 5. （2分）在4次对称群中，请写出由（1 3 4）生成的子群。

6. （2分）设S={1, 2, 3, 4, 5,6},?是模7乘法运算，请指出群(S, ?)中每个元素的逆元素。

7. （2分）设群G中的元素a的周期为8，则a6的周期是多少？ 8. （2分）写出模12剩余环中所有的零因子。

9. （2分）在整数环Z中，包含主理想（21）的极大理想有哪些？ 10. （2分）若子群H在群G中指数是2，则H一定是G的正规子群吗？ 11. （2分）在12元循环群(a)中，求子群（a3）的所有陪集。

12. （2分）设G是由a生成的6元循环群，设σ（n）=an是整数加法群（Z，+）到G内的映射，则σ是同态映射吗？如果是，求出σ的同态核。

第二章 命题逻辑

§2.2 主要解题方法

2.2.1 证明命题公式恒真或恒假

主要有如下方法：

方法一. 真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

18

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1 说明 G= (P?Q?R)?(P?Q)?(P?R)是恒真、恒假还是可满足。

解：该公式的真值表如下：

P Q R P?QP?(P?QP?R G ?R Q ?R)?(P?Q) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 表2.2.1

由于表2.2.1中对应公式G所在列的每一取值全为1，故

19

1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 G恒真。

方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。

例2.2.2

离散数学期末复习

一、选择题 1、

下列各选项错误的是

A、? ? ? B、? ? ? C、? ?{ ?} D、? ? {? }

2、命题公式 (p∧q) →p 是 A、矛盾式 B、重言式 C、可满足式 D、等值式

3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是

A、等价关系 B、偏序关系 C、全序关系 D、都不是

4、下列句子中那个是假命题？ A、

是无理数.

B、2 + 5 ＝8.

C、x + 5 ＞ 3 D、请不要讲话！ 5、下列各选项错误的是？ A、? ? ? B、? ? {? } C、? ?{ ?} D、{? } ? ?

6、命题公式 p→（p?q?r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式

7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是

8、设D=,则V={a,b,c,d,e,f},R={ ,,,,},有向图D为 A、强连通 B、单向连通 C、弱连通

D、不连通的

9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1 ?R2 B、R1-1 C、R1 ?R2 D、R1 -R2

10、连通平面图G有4个

离散数学

一、填空20%（每空2分）：

1．若对命题P赋值1，Q赋值0，则命题P?Q的真值为 。 2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 3．公式?(P?Q)?(P??(Q??S))的对偶公式为

4．图 的对偶图为

5．若关系R是等价关系，则R满足 性质。 6．关系R的传递闭包t (R) = 。 7．代数系统?A,??是群，则它满足 8．设?A,?,??和?B,?,??是两代数系统，f是从?A,?,??到?B,?,??的同态映射，则f具有 性质。

一、填空

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 (B⊕C)-A

A C 4．公式(P?R)?(S?R)??P的主合取范式为 (?P?S?R)?(?P??S?R) 。 5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x) 在I下真值为 1 。 6．设A={1，2，3，4}，A上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。

?1??0???0?0?010??

101?000??000?? //备注：

?0??1R???0?0?100? ?010?001??000??

R2

7．设A={a，b，c，d}，其上偏序关系R的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。

//备注：偏序满足自反性，反对称性，传递性

8．图的补图为 。

//补图:给定一个图G,又G中所有结点和所有能使G成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a，b，c，d} ，A上二元运算如下