自考离散数学期末复习

《离散数学》复习题一、填空题1、若P ，Q 为二命题，Q P ↔真值为1，当且仅当 。

2、对公式),()),(),((y x xR z x zQ y x yP ∀∨∃∧∀中自由变元进行代入的公式为 。

3、))(()(x xG x xF ∃⌝∧∀的前束范式为 。

4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则 被称为全称量词消去规则，记为US 。

5、与非门的逻辑网络为 。

6、}0|{>∧∈=+x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元是 ，零元是 。

7、代数系统<A,*>中，|A|>1，如果θ和e 分别为<A,*>的幺元和零元， 则θ和e 的关系为 。

8、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是 。

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

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

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

A 、R Q P ⌝∧∧)(；B 、)()((S R Q P ∧→→；C 、R Q P ∧∨∨；D 、S R Q P ∨∧∨⌝))((。

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

A 、2是素数；B 、x+5 > 6；C 、地球外的星球上也有人；D 、这朵花多好看呀！。

3、下列公式是重言式的有（ ）。

A 、)(Q P ↔⌝；B 、Q Q P →∧)(；C 、P P Q ∧→⌝)(；D 、P Q P ↔→)(4、下列问题成立的有（ ）。

若C B C A ∨⇔∨，则B A ⇔； B 、若C B C A ∧⇔∧，则B A ⇔； C 、若B A ⌝⇔⌝，则B A ⇔； D 、若B A ⇔，则B A ⌝⇔⌝。

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

A 、在推演过程中可随便使用前提；B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；D 、设)(A Φ是含公式A 的命题公式，A B ⇔，则可用B 替换)(A Φ中的A 。

离散数学一、选择题1△O Y C3A^Q un ㊉iv1.设：P：张三可以作这件事，Q：李四可以作这件事，命题“张三或李四都可以做这件事”的符号化为()A、PVQB、PVi QC、P—QD、-P V -Q2.谓词公式V x(P(x)V m yR(y))fQ(x)中量词V x的作用域是()A. V x(P(x) V3yR(y))B.P(x)C. (P(x) V3yR(y)) D,P(x), Q(x)3.若个体域为整体域，下列公式中哪个值为真？()A. V x 3y(x+y=0)B. 3y V x(x+y=0)C. V x V y(x+y=0)D. n 3x 3y(x+y=0)4.空集①的幂集P (①)的基数是()A. 1B.2C.3D.45.设R、S是集合A上的任意关系，则下面命题是真命题的是()。

A.若R、S是自反的，则R・S是自反的B.若R、S是反自反的，则R・S是反自反的C.若R、S是对称的，则R・S是对称的D.若R、S是传递的，则R・S是传递的6.集合 A={1, 2,…，10}上的关系 R={(x, y)|x+y=10 且x, y£A},则 R 的性质为()A.自反的B.对称的C.传递的，对称的口.非自反的，传递的7.含有5个结点，3条边的不同构的简单图有()A.2个B.3个C.4个D.5个8.设G (n, m),且G中每个结点的度数不是K就是K+1,则G中度数为K的结点数()A.2/nB.n(n+1)C.nkD.n(k+1)-2m9.设谓词P(x) :x是奇数，Q(x):x是偶数，谓词公式m(x) (P(x) AQ(x))在下面哪个论域中是可满足的。

()A自然数集 B整数集 C实数集 D以上均不成立10.设C(x)： x是运动员，G(x)： x是强壮的。

命题“没有一个运动员不是强壮的”可符号化为()A. n V x(C(x) A n G(x))B. iV xOx) — G(x))C. _|m x(C(x)A_|G(x))D. im x(C(x) - 1 G(x))11.设集合 M={x|f (x) =0}, N={x|g (x) =0},则方程 f (x)・g (x) =0 的解集是()A.MANB.MUNC.M ㊉ ND.M-N12.设A=/"a}},下列选项错误的是()A. {a} e p(A)B. {a}U p(A)C. {{a}} e p(A)D. {{a}} e p(A)13.设A={1,2,3,4,5},p{<i,j>|i<j,i,j £ A}则 p 逆的性质是()A.对称的B.自反的C.反对称的D.反自反，反对称，传递的14.设R和S是集合A上的等级关系，则RUS的对称性()A. 一定成立B.一定不成立C.不一定成立D.不可能成立15. K4中含有3条边的不同构生成子图有()A.1个B.3个C.4个D.2个16.设G=<V,E>为无向图，u,v £V，若u,v连通，则()A.d(u,v)>0B.d(u,v)=0C.d(u,v)<0D.d(u,v)三0二、填空题1.命题公式I(P-Q)的主析取范式为()，主合取式的编码表示为().2.设Q(x)： x是奇数，Z(x)： x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为()。

复习知识点： 第1章1． 命题、真命题、假命题 2． 命题符号化〔连接词〕设P ：天下大雨，Q ：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为〔 D 〕A ．Q P ∧⌝B ．Q P →⌝C ．Q P ⌝→⌝D ．Q P ⌝→设P ：只有你通过了大学英语六级考试，Q ：你是英语专业的学生，R ：你可以选修这门课程。

命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课程”( B )A ．R Q)(P →∧B ．R Q)(P →⌝∧C ．R Q)(P ↔⌝∧D ．R Q)(P ↔∧3． 什么是命题公式 4． 命题公式的等价式5． 利用逻辑等价关系证明下面的等价关系 Q P Q)(P P))(Q Q)((P ∨⇔∧→→∧→证明：6． 用真值表法求命题公式的主析取范式和主合取范式 7． 符号化以下语句，并推证结论的有效性。

有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。

解：设论述域为全总个体域，S(x)：x 是学生，T(x)：x 是老师，P(x)：x 是骗子，L(x,y)：x 相信y 。

将前提和结论符号化为P(x))x(T(x)y)))L(x,y(P(y)x(S (x)y))),L(x,y(T(y)x(S (x)⌝→∀⇒⌝→∀→∀→∀∧∃〔1〕y)))L(x,y(T(y)x(S (x)→∀∧∃ P 〔2〕y))L(a,y(T(y)S (a)→∀∧T1，ESQ)(P TQ)(P Q)Q (Q)(P Q Q)(P T)(Q Q)(P P))P ((Q Q)(P Q)(P P)(Q Q)(P Q)(P P)Q (Q)P (Q)(P P))Q (Q)P ((Q)(P P)Q (Q)P (Q)(P P))(Q Q)((P ∨⇔∧∨⇔∨⌝∧∨⇔∨⌝∧⇔∧∨⌝∧⇔∨⌝∧∨⌝∧⇔∧∨⌝∧∨⌝∧⇔∧∨∨⌝⌝∨∨⌝⌝⇔∧∨∨⌝∧∨⌝⌝⇔∧→∨⌝∧∨⌝⇔∧→→∧→〔3〕S(a) T2，I 〔4〕y))L(a,y(T(y)→∀ T2，I 〔5〕b)L(a,T(b)→T4，US 〔6〕y)))L(x,y(P(y)x(S (x)⌝→∀→∀ P 〔7〕y))L(a,y(P(y)S (a)⌝→∀→ T6，US 〔8〕y))L(a,y(P(y)⌝→∀ T3,7，I 〔9〕b)L(a,P(b)⌝→ T8，US 〔10〕P(b)b)L(a,⌝→ T9，E 〔11〕P(b)T(b)⌝→T5,10，I 〔12〕P(x))x(T(x)⌝→∀T11，UG侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实： （1） 是营业员甲或营业员乙作案。

总复习题（一）一．单选题1 (C)。

一连通的平面图，5个顶点3个面，则边数为（）。

、4 、5 、6 、72、 (A)。

如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。

、1 、2 、3 、43、 (D)。

为无环有向图，为的关联矩阵，则（）。

、是的终点、与不关联、与关联、是的始点4、 (B)。

一连通的平面图，8个顶点4个面，则边数为。

、9 、10 、11 、125、 (D)。

如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。

、1 、2 、3 、46、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。

、13 、12 、11 、107、 (D)。

有向图的通路包括。

、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路8、 (D)。

一连通的平面图，9个顶点5个面，则边数为。

、9 、10 、11 、12A B C D G G ≅G A B C D E ,V D =[]m n ij m ⨯D 1m ij =A i v j e B i v j e C i v j e D i v j e A B C D G G ≅G A B C D A B C D A B C D A B C D9、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。

、13 、12 、11 、1010、 (D)。

有向图的通路包括。

、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路11、 (D)。

一连通的平面图，9个顶点5个面，则边数为。

、9 、10 、11 、1212、 (B)。

为有向图，为的邻接矩阵，则。

、邻接到的边的条数是５、接到的长度为４的通路数是５、长度为４的通路总数是５、长度为４的回路总数是５13、 (C)。

在无向完全图中有个结点，则该图的边数为（）。

A 、B 、C 、D 、14、 (C)。

任意平面图最多是（）色的。

A 、3B 、4C 、5D 、615、 (A)。

对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。

1.证明永真公式Q14,Q15,Q16,Q17和Q18。

2.证明P(x)∧任意xQ(x)==>存在x(P(x)∧Q(x))3.设论述域是{a1,a2,a3,…an},试证明下列关系式。

(a) 任意xA(x)∧P<==>任意x(A(x)∧P)(b) 任意x(A(x)∧B(x))<==>任意xA(x)∧任意xB(x)(c) 存在x(A(x)∧B(x))<==>存在xA(x)∧存在xB(x)4.证明下列关系式(a) 任意x任意y(P(x)∨P(y))<==>任意xP(x)∨任意yP(y)(b) 存在x存在y(P(x)∧Q(y))==>存在xP(x)(c) 任意x任意y(P(x)∧Q(y))<==>任意xP(x)∧任意yQ(y)(d) 存在x存在y(P(x)－＞P(y)) <==>任意xP(x)－＞存在yP(y)(e) 任意x任意y(P(x) －＞Q(y)) <==>(存在xP(x)－＞任意yQ(y))5.写出limf(x)=k的定义的符号形式，并用形成定理两边的否定的方法，找出limf(x)不等x->c x->c于k的条件。

6.给定自然数集合N的下列子集：A={1,2,7,8}B={i|i平方<50}C={i|i可被30整除}D={i|i=2的k次方∧k∈I∧0≤k≤6}求下列集合(a)A∪(B∪(C∪D))(b)A∩(B∩(C∩D))(c)B-(A∪C)(d)(非A∩B) ∪D7.假定A≠空集和A∪B=A∪C，证明这不能得出B=C，假设中增加A∩B=A∩C，你能得出B=C吗？8．(a)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A-B≠B-A。

(b)A-B=B-A可能吗？刻划上式出现的全部条件。

(c)“相对补”是一个可结合的运算马？证明你的断言。

9.证明下列恒等式(a)A∪(A∩B)=A(b)A∩(A∪B)=A(c)A-B=A∩非B(d)A∪(非A∩B)=A∪B(e)A∩(非A∪B)=A∩B10.设Sn={a0,a1,…,an}和Sn+1={a0,a1, …,an,an+1},试用p(Sn)和an+1表达出p(Sn+1)。

《离散数学》期末复习大纲（完整版）（含例题和考试说明）一、命题逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。

5、掌握命题逻辑的推理理论。

[疑难解析]1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。

具体方法有两种，一是真值表法，二是等值演算法。

2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。

关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。

3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。

例1.试求下列公式的主析取范式：（1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨（))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解 Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()())(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝=)()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝=)))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解)()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨=)()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨）2．用真值表判断下列公式是恒真？恒假？可满足？（1）（P ∧⌝P ）↔Q（2）⌝（P →Q ）∧Q（3）（（P →Q ）∧（Q →R ））→（P →R ）解：（1） 真值表因此公式（1）为可满足。