奥鹏东北大学《离散数学》题库

PQ
P Q P (Q P) Q
FF
T
T
F
FT
T
T
T
TF
F
T
F
TT
F
F
T
从真值表看出，该命题公式的主合取范式含有大项 ( P∨Q)。于是此命题公式的主合取范式为： (Q P) Q (P ∨Q)∧ ( P∨Q)
M0 和 M2，即 (P∨ Q)和
五 . 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写 推理过程。
反对称的
传递的
R
S
T
M
N
解：
R S T M N
自反的 √ √ × × √
反自反的 × × √ √ ×
对称的 × √ × √ √
反对称的 √ × √ √ ×
传递的 √ √ × √ √
3. 上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是 A 上函数？
对等价关系，写出此等价关系的各个等价类。 对函数，指出它的类型。 解： S 和 N 是等价关系。 R 是偏序关系。
解： A={1,{1}}, B={1} ，
⑴ A ×P(B) ＝{1,{1}} × { Φ ,{1}}
＝{<1, Φ>,<1,{1}>,<{1}, Φ>,<{1},{1}>}
⑵ A ⊕B＝(A B)－(A B)
=({1,{1}}
{1}) － ({1,{1}}
{1}) ＝ {1,{1}} － {1} ＝{{1}} 。
九 . 令集合 A={1},B ＝{1,2}, P(A) 表示集合 A 的幂集。 （注意：要求要有计算过程，不能直接写出计算结果！ ）
1 ．计算 A 与 B 的对称差 A B。 解： A B＝ (A B)－ (A B)
＝({1} {1,2}) －({1} {1,2}) ＝ {1,2} －{1} ＝ {2} 2．计算 P(B) － P(A) 解： P(B) － P(A) ＝P({1,2}) －P({1})
1. 写出关系 R的矩阵；再画出上述各个关系的有向图。
解 ： 关系 R的矩阵如下：
111 M R 010
001
下面是几个关系的有向图：
1
1
。
。
。 2 。3
R
。2
。3
S
1
1
。
。
。2
。3
T
。2
。3
M
1
。
。2 。3
N
2. 判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
自反的
反自反的
对称的
六 . 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写
推理过程。
xC(x), x(A(x) B(x)), x(B(x) C(x))
xA(x)
解： ⑴ x(A(x) B(x)) P
⑵ A(a) B(a)
ES
⑴
⑶ xC(x)
P
⑷ C(a)
US
⑶
⑸ x(B(x) → C(x)) P
⑹ B(a) → C(a)
四 . 写出命题公式 (Q → P)→ Q 的主合取范式。（要求有解题过程）
解：
方法 1：等价变换
(Q P) Q
( Q∨ P) ∨Q (
去)
(Q ∧P) ∨Q
(
摩根定律 )
Q
(
吸收律 )
(P ∧ P) ∨Q
（互补、同一律 ）
(P ∨Q)∧( P∨Q)
( 分配律 )
方法 2：真值表法
先列 (Q P) Q的真值表如下：
离散数学复习题
一 . 有两个小题
1．分别说明联结词 、∧、∨、→和 的名称，再分别说明它们在自然语言中
表示什么含义。
解： (1) 叫做否定 。 (2) ∧ 叫做合取。 (3) ∨叫做析取。
(4)
叫做蕴涵。 (5)
叫做等价。
“ ”表示“ , 不成立”，“不 , ”。
“∧”表示“并且”、“不但 , 而且 ... ”、“既 , 又 ... ”等。 “∨”表示“或者”， 是可兼取的或。 “ ”表示 如果 , ， 则 , ； 只要 , ， 就 , ； 只有 , , 才, ； “ ”表示“当且仅当”、“充分且必要”。 2．分别列出 P、P Q、P Q、 P Q、 P Q的真值表 ( 填下表 ) 。
解： P(A) ＝{ Φ,{1},{{1}}, {1,{1}}
P(B) ＝{ Φ,{1}}
⑴：真值为 T；因为 A={1,{1}}, B={1}, B
是 A 中一个元素，所以 B∈A。
⑵：真值为 T；因为 P(B) ＝{ Φ,{1}} ， P(B) 中两个元素 Φ和 {1} 都属于 P(A), 所
以 P(B) P(A) 。
无向连通图 欧拉图 汉密尔顿图 树 根树 m叉树 完全 m叉树
解： 无向图结点 v 的度 :G 是个无向图 , v ∈ V(G), 结点 v 所关联边数 , 称之为结点 v 的度 . 记作 deg(v).( 或 d(v)). 有向图结点的出度和入度 : G=<V,E> 是有向图 ,v ∈ V
v 的出度 : 从结点 v 射出的边数 . v 的入度 : 射入结点 v 的边数 . 平行边 : 在两个结点之间关联的多条边，这些边是平行边 . 简单图 : 不含有环和平行边的图 . 无向完全图 Kn：G 是个简单图 , 如果每对不同结点之间都有边相连，则称 G 是 个无向完全图。如果 G有 n 个结点 , 则记作 Kn。 路 : 给定图 G=<V,E >，设 v0 ,v1,v2,,,,vn ∈V, e1,e2,,,,en ∈ E 其中 ei 是关联 vi-1 ,vi 的边 , 则称结点和边的交叉序列 v0 e1v1 e2v2,envn 是连接 v0 到 vn 的路 . 回路 : 如果一条路的起点和终点是一个结点 , 则称此路是一个回路 . 迹 ： 如果一条路中 , 所有边都不同 , 则称此路为迹 . 闭迹 ：如果一条回路中 , 所有边都不同 , 则称此回路为闭迹 . 通路 ：如果一条路中 , 所有结点都不同 , 则称此路为通路 . 圈 ： 如果一条回路中 , 除起点和终点外 , 其余结点都不同 , 则称此回路为圈 . 无向连通图 : 如果一个无向图 G只有一个连通分支 (W(G)=1), 则称 G是连通图 . 欧拉图 ：在无孤立结点的图 G 中, 若存在一条回路 , 它经过图中每条边一次且仅 一次 , 称此图为欧拉图。 汉密尔顿图 ：图中有通过每个结点恰好一次的回路。 ( 具有汉密尔顿回路 ) 的图 . 称之为汉密尔顿图。 树 ：一个连通无回路的无向图 T，称之为树。 根树 : 如果一棵有向树 , 恰有一个结点的入度为 0, 其余所有结点的入度均为 1, 则 称此树为根树 . m叉树 : 在根树中 , 如果每个结点的出度最大是 m, 则称此树是 m叉树 . 完全 m叉树 : 在根树中 , 如果每个结点的出度都是 m或者等于 0, 则称此树是完全 m叉树 .
⑶：真值为 T；因为集合 { Φ } 中只有一个元素 Φ，而 P(A) 中也有元素 Φ ，所以
{ Φ} P(A) 。
⑷：真值为 F。因为 {{1}} 不是 P(B) 中元素，故真值为 F。
2. 分别计算 : （注意：要求要有计算过程，不能直接写出计算结果！ ）
(1) A ×P(B)
(2) A ⊕B
(3) P(A) －P(B)
算。
1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，填下表：
+
－
×
max
min
|x-y|
有交换性
有结合性
有幂等性
有幺元
有零元
2. 分别指出 R对上面哪些运算是半群、独异点和群。
3. 如果有群，请说明它为什么是群。
解 :1.
+
－
×
max
min
|x-y|
有交换性
√
×
√
√
√
√
有结合性
√
×
√
⑶ P(A) －P(B) ＝{ Φ ,{1},{{1}}, {1,{1}}
－{ Φ,{1}}
＝{{{1}}, {1,{1}}}
八 . 令全集 E={1,2},A={1}, P(A) 表示集合 A 的幂集。
（注意：要求要有计算过程，不能直接写出计算结果！ ）
1. 指出 P(E) 和 P(A) 各有多少个元素。即求 |P(E)| 和 |P(A)|.
3. 证明结合性 ,
任取 a,b,c I,
(a*b)*c=(a ＋b＋ 4) ＋ c＋4=a＋ b＋ 4＋ c＋ 4 =a ＋ (b ＋c ＋4) ＋4=a*(b*c).
所以 * 满足结合性。
4. 证明 -4 是幺元 ,
任取 a I,
因为 (-4) I, 使得 a* (-4)=a ＋4＋ (-4)=a
解：因为 P(E) ＝{ Φ,{1},{2}, {1,2}}
所以 P(E) 有 4 个元素。即 |P(E)| ＝4。
P(A) ＝ { Φ,{1}} 所以 P(A) 有 2 个元素。即 |P(A)| ＝2。
2. 计算～ A E
解：因为～ A＝E－A={1,2}-{1}={2}
～A E＝ {2} {1,2} ＝({2} {1,2}) － ({2} {1,2}) ＝ {1,2} －{2} ＝ {1}
所以 <R,＋>是群。
十二 . 设 I 是整数集合，在 I 上定义二元运算 * 如下：
对于任何 a,b ∈I a*b=a+b ＋4
求证 <I,*> 是个交换群 .
解： 1. 证明封闭性 : 任取 a,b I 因 a＋b＋4 I , a*b
I. 所以 * 满足封闭性。