《离散数学》总复习.ppt

若 x A, x x x ，则称运算为等幂的。
《离散数学》总复习
若 x A,e x x e x ，则称e为幺元。
若 x A, x x ，则称为零元。 13.设 S, 是一个代数系统，若满足（1）运算 封闭，（2）结合律成立 ，
（3） 有幺元 ， 则称 S , 是一个独异点。
(P Q R) (P Q R)
五. 已知论域E 1,2
a b f (1) f (2) P(1,1)
P(1, 2) P(2,1) P(2, 2)
12 2 1
T
T
F
F
求1. P(a, f (a)) P(b, f (b)) 2. (x)(y)(P( x, y) P( f ( x), f ( y)))
解. 知识点: 条件联结词P Q：当且仅当P为T ,Q也为T时, P Q为T,否则都为F。
3.设L( x)：x是运动员。S( x)：x是大学生。命题：“并非每个运动员 都是大学生”可表示为 (x)(L( x) S( x))。 解. 知识点: 带量词的谓词来表达命题，翻译时用全总个体域。而用
特性谓词来刻画个体域。全称量词此特性谓词常作条件
解. P Q R PQ PQR
TT T
T
T
TT F
T
F
TF T
F
T
TF F
F
T
FT T
F
T
FT
F
F
T
FF T
F
T
FF F
F
T
《离散数学》总复习
三. 证1.P (P Q) Q T。 证2.(P Q) （Q R) P P Q R。
证. 1.P (P Q) Q (P P) (P Q) Q
14. G , 是一个群， S , 是 G , 的平凡子群，则S e 或者
S G 。
15.群 G, 的运算表中每一行或每一列都是G中元素的 置换 。
1
16.n个结点的无向完全图Kn的边数 E
n (n 1) 2
。
17.一棵树有一个结点的度数为2，二个结点的度数为3，三个结点的
度数为4，则有
《离散数学》总复习
源自文库
四. 求合式公式Q ((P Q) R)的主析取、主合取范式。
解. Q ((P Q) R) Q ((P Q) R) Q （[ P Q) R] （P Q) （Q R) （P Q R) （P Q R) （P Q R) m111 m011 m010 M110 M101 M100 M001 M000 (P Q R) (P Q R) (P Q R)
M I N 1，则M U N 1,2,4 。
解. 知识点: 集合的交、并运算。-1 M 1 p q 0, -1 N 1 p 2q 0,
6.设A a1,a2,a3,a4,P( A)是A的密集，S9 P( A)，在二进制编码下，
S9
a1,a4
。
29 1 24 0
22 0
解. 知识点: 十进制与二进制的转换。 9=(1001)2
21 1 0
《离散数学》总复习
7.设A 0,1,则P( A) A
,0 , ,1 , 0,0 , 0,1 , 1,0 , 1,1 , 0,1,0 , 0,1,1 。
解. 知识点:幂集的概念与笛卡尔积
P( A)是由A的所有子集为元素构成的集合。 P(A) ，0，1，0，1。 X Y x, y x X y Y.
解. 知识点: 偏序关系 p 确定CovA x, y 元素y盖住元素x .
1
2
3
4
12.设 A, 是一个代数系统，A ，为定义在A上的二元运算。 若 x, y A, x y y x，则称运算为可交换的。 若 x, y, z A,( x y) Mz x ( y z) ，则称运算为可结合的。
10
个结点的度数为1。
解. 知识点: 树的基本概念及图的基本定理（握手定理）v
树T的边数e与结点数v的关系：e v 1. deg(vi ) 2e
设有x个结点的度数为1，则有x 1 1 2 2 3 3 4 i21（x 1 2 3 1)
《离散数学》总复习
二.求合式公式P Q R的真值表。
8.设X 1,2,3,X上的大于关系> 2,1 , 3,1 , 3,2
。
解. 知识点:关系的概念。若R X Y ,则称R为X到Y上的二元关系。
若R X X ,则称R为X上的二元关系。
9.设X上的二元关系R,若满足（1） 自反的 ，（2） 对称的 ，
（3） 传递的 ，则称R为X上的等价关系。
10.设X上的二元关系R,若满足（1） 自反的 （3） 传递的 ，则称R为X上的偏序关系。
，（2）反对称的 ，
《离散数学》总复习
11.设 p 1,1 , 2,2 , 3,3 , 4,4 , 3,1 , 4,1 , 4,2 , 4,3
是A 1，2，3，4上的偏序关系，则CovA 3,1 , 4,2 , 4,3 。
的前件,存在量词,此特性谓词常作合取项.
《离散数学》总复习
4.设A a1 ,a2 ,a3 ,a4,则A的所有真子集有 24 1 15 个。 解. 知识点: 若A a1,a2,L ,an,则A的全体子集共有2n个，其中唯一
的非真子集的子集是A本身。 5.设关于x的方程x2+px q 0和x2 px 2q 0的解集为M和N ,且
(P Q) Q (P Q) Q
(P Q) Q P (Q Q)
P T T
证. 2. (P Q) (Q R) P (P Q) (Q R) P
[(P P) (P Q)] (Q R) [F (P Q)] (Q R) (P Q) (Q R) (P Q Q) (P Q R) F (P Q R) P Q R
《离散数学》总复习
一.填空题
1.设P：若2 1 4，则雪是黑的。该命题真值为 T 。
解. 知识点: 条件联结词P Q：当且仅当前件为T,后件为F时, P Q为F。 特别是当前件P为F时，不管后件Q是T
还是F , P Q为T。
2.设P：我们划船。Q：我们跑步。命题“我们不能既划船又跑步” 可表示为 (P Q) 。