当前位置：文档之家 › 离散数学复习

离散数学复习

  • 格式：doc
  • 大小：203.00 KB
  • 文档页数：4

1. 设},{b a A =，},,{z y x B =，则=⨯B A
2. 集合},{b a A =的幂集为
3. 等价关系具有的三个性质是
3. 设集合}5,4,3,2,1{=A ，R 是A 上的模3同余关系，则此等价关系所对应的划分为
4. 设}6,4,2{=A ，S R ,是A 上的两个二元关系，且x y x R ),{(=能整除y }，x y x s ),{(=小于y }，则=S R
5. 集合},,,{d c b a A =，)},(),,(),,(),,(),,{(d a b c c b b a a a R =，则R 的自反闭包为
6. 若p 和r 取真，q 取假，则命题)(r q p ∨∧⌝的真值为
7. 设}9,8,7,6,5,4,3,2,1{=A ,})4(mod ),{(b a A A b a R ≡⨯∈=，则商集R A /为
8. 设}5,4,3,2,1{=A ，运算*定义为),max (b a b a =*，则),(*A 中的幺元是
9. 在谓词推理过程中，由)()(x P x ∀得到P (a )，其中a 为论域的某个个体，用的是________规则，记为________规则。

10. 命题公式()P Q P →∨的真值是
11. 设P ：他生病了，Q ：他出差了，R ：我同意他不参加学习．则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 ．
12. 设集合A=｛a,b,c ｝，A 上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则二元关系R 具有的性质是 ．
13. 设S(x)：x 是大学生；K(x)：x 是运动员。

则命题：“有些运动员不是大学生”的符号化表示为： .
14. A ，B 为集合，如果|A | = m, |B | = n, 则 |A ×B | =
15. 已知f(x) = 4x - 2, g(x) = x 2 + 5, 则
(x) =
1. 下列语句不为命题的是（ ）
（A ）5是无理数； （B ）2与3都是偶数；
（C ）你去图书馆么？ （D ）刘红和魏新是同学.
2. 下列哪个公式是永真式（ ）
（A ）)()(P Q Q P →∧→； （B ）P Q P →∧)(；
（C ）))(()(Q P Q P ⌝∧⌝⌝∧∨⌝； （D ）)(Q P ∨⌝.
3. 若集合A ＝{2，a ，{ a }，4}，则下列表述正确的是( )．
A ．{a ，{ a }}∈A
B ．{a}⊆A
C ．{2}∈A
D ．∅∈A
4. 设R c b a A },,,{=是A 上的二元关系,具有传递性的有 ( )
（A ）)},(),,(),,(,,{a b b a a c c a R ）（=； （B ）)},(),,{(a c c a R =；
（C ）)},(),,)(,(),,{(c b a b c c b a R =； （D ） )},{(a a R =.
5. 命题公式r q p ↔→)(的成真赋值为 ( )
（A ）全部； （B ）000，010，101，110；
（C ）001，011，100，111； （D ）无.
6. 设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b >⎢a , b ∈A , 且a +b = 8}，则R 具有的性质为（
）．
A ．自反的
B ．对称的
C ．对称和传递的
D ．反自反和传递的
7. 命题公式)(Q P →⌝的主析取范式是（ ）．
A ．Q P ⌝∧
B ．Q P ∧⌝
C ．Q P ∨⌝
D ．Q P ⌝∨ 8. 表达式))(),(())(),((z zQ y x R y z Q y x P x ∀→∃∧∨∀中x ∀的辖域是（ ）．
A ．P(x, y)
B ．P(x, y)∨Q(z)
C ．R(x, y)
D ．P(x, y)∧R(x, y) 9. 下列关系矩阵所对应的关系具有反自反性的是( )
A.⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101
B. ⎥⎥
⎥⎦
⎤
⎢⎢⎢
⎣⎡101110001
C. ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100
D. ⎥⎥⎥⎦
⎤
⎢⎢⎢
⎣⎡001010101
10. 设A 是整数集，下列说法正确的是( )
A.<A ，+>有零元
B.<A ，÷>有零元
C.<A ，+>有幺元
D.<A ，÷>有幺元
三．简答题
1. 画出下列偏序集),(≤R A 的哈斯图，并找出A 的极大元，极小元，最大元和最小元，其中},,,,{e d c b a A =，),,(),,{(c a d a R =
.)},(),,(),,(),,(),,(A I e d e c e b e a b a
2. 设I 是整数集合,运算*定义为,ab b a b a ++=*问),(*I 是半群吗?为什么?
3. 证明推理：.)(,,,S S P R R Q Q P ⌝⇒∧⌝⌝⌝∨⌝→
4. 用列真值表的方法求命题公式R
→)
(的主析取范式．
P→
Q
5. 设集合A＝{a, b, c, d}上的二元关系R的关系图如图所示．
（1）写出R的表达式；
（2）写出R的关系矩阵；
（3）求出R2．。

合集下载

离散数学期末复习

离散数学期末复习

离散数学内容总结大纲第一篇 数理逻辑第1章 命题逻辑求命题公式的主析取范式及主合取范式例 求()()p r q p ∨⌝∧∨的主析取范式及主合取范式。

例 求(P →Q)∧R 的主析取范式及主合取范式。

例 求命题公式R Q P ∨∧)(的主析取范式和主合取范式。

例 求公式A =(p →⌝q )→r 的主析取范式与主合取范式。

例 求()r q p →→的主析取范式。

判断公式类型例 用等值演算法判断公式q ∧⌝ (p →q )的类型例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。

(1)(2)证明例 证明：()()()r q r p r q p →∧→⇔→∨ 例 证明：r q p r q p →∧⇔→→)()( 例 推证：⌝Q ∧(P →Q)⇒⌝P例 前提：q p s q r p ∨→→,,，结论：s r ∨。

该结论是否有效？请说明原因。

在命题逻辑中构造下面推理的证明：例 如果小张守第一垒并且小李向B 队投球，则A 队获胜。

或者A 队未获胜，或者A 队成为联赛的第一名。

小张守第一垒。

A 队没有成为联赛的第一名。

因此小李没有向B 队投球。

解：先将简单命题符号化。

P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A 队成为联赛第一名。

前提：(P∧Q)→R，R∨S，P，S结论：Q证明：(1) R∨S 前提引入(2) S 前提引入(3) R (1)(2)析取三段论(4) (P∧Q)→R 前提引入(5) (P∧Q) (3)(4)拒取式(6) P∨Q (5)置换(7) P 前提引入(8) Q (6)(7)析取三段论例一个公安人员审查一件盗窃案，已知下列事实：（1）甲或乙盗窃了录像机；（2）若甲盗窃了录像机，则作案时间不能发生在午夜前；（3）若乙的证词正确，则午夜时屋里灯光未灭；（4）若乙的证词不正确，则作案时间发生在午夜前；（5）午夜时屋里灯光灭了。

根据以上事实，推断谁是盗窃犯。

（在命题逻辑中构造推理证明。

离散数学复习知识点

离散数学复习知识点

复习知识点： 第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、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。

其它疑问句、祈使句、感叹句、悖论等皆不是。

详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。

特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。

B设出原子命题写出符号化公式。

详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。

详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。

②对每个指派，以二进制数从小到大或从大到小顺序列出。

③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。

详见P8。

6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。

主要等价式：(1)双否定：⎤⎤A⇔A。

(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。

3)结合律：(A∧B)∧C⇔A∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。

(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。

(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。

(6) 等幂律：A∧A⇔A，A∨A⇔A。

(7) 同一律：A∧T⇔A，A∨F⇔A。

(8) 零律：A∧F⇔F，A∨T⇔T。

(9) 吸收律：A∧(A∨B)⇔A，A ∨(A∧B)⇔A。

(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。