离散数学(数学教育)知识点.docx

（）：设P, Q是两个命题，，命题”若P,则Q”称为P蕴涵Q,记
作 P Q . 规定： P Q 是假的当且仅当 P 是真的而 Q 是假的 .
二．
1．设 A 是非空集合， R 是 A 上的二元关系， R 的 自反闭包 （对) ( G H ) ；
G G
G H
G （H
G （G
G （H
G 0
G 0
（G
2．基本蕴涵式：
P Q
2） P P
G,G G G；
H G,G H
S) (G H)
H) G,G (G
S) (G H) (G
G,G 1 G ；
0,G 1 1 ；
H) G H
P, P Q Q ；
Q,Q P Q ；
（等幂律）
H G；
S,G （H
H） G；
S）,G （H
（同一律）
（零一律）
（G H） G
（交换律）
S） （G H ） S ；
(吸收律)
S) (G H) (G
H . (De
（结合律）
S） ； （分配律）
Morgan 律)
P (P Q),Q (P Q) ； (因为 (P Q) ( P Q)
(4) (P Q) P, (P Q) Q ； (因为 (P Q) ( P Q) P Q .
3．注 1： G H 的充要条件是公式 G H 是恒真的 .
五．
． 等价关系： 设 R 是非空集合A 上的一个关系，若R 具有自反性、对称性和传
递性，则称R 是一个等价关系 .
例子：设 A={a, b, c} ， R={(a, a), (b, b), (c, c), (a, b), (b, a)} 是 A 上的等价关系 .
． 等价类： 设 A 是一个非空集合， 是 A 上的一个等价关系 .A 的一个非空集合
M 叫做一个等价类，如果
(1)若aM ,bM ,则 a b;
(2)若 aM , ab ，则 b M .
(即a,b属于同一个等价类当且仅当a b)
3．商集： 设 R 是非空集合A 上的一个等价关系， 以 R 的所有不同的等价类为元
素作成的集合称为 A 关于 R 的商集，简称A 的商集，记作A/ R.
4． 划分： 当 A 的子集簇 C 满足如下条件时，称C 为 A 的划分：
a) 若 B C ，则 B ；
(2) U B A ；
(3)对任意的B, B C ，且 B B ，则 BI B .
5．定理：设R 是非空集合A 上的一个等价关系，则 A 的商集构成 A 的一个划
分；反之，若C 是集合 A 的一个划分，令
Rc{(x,y)|x,y A, x, y属于C的同一个等价类},
则 RC 是 A 的一个等价关系 .
六． 幂集的定义 ：设 A 是集合， A 中所有子集为元素构成的集合称为 A 的幂集。
七． 主析取范式
.设P,R,L ,Pn是n个不同的原子，一个短语如果恰好包含所有这n个原子或其
否定，且其排列顺序与Pi，P2，L二的顺序一致,则称此短语为关于R,P2，L ,Pn的
一个极小项.
.共有2n个不同的极小项.
.例子：有3个不同的原子P,Q,R,则P Q R, P QR是极小项.
.:主析取范式的定义
.:对于命题公式G,都存在等价于它的主析取范式.
.主析取范式的求法及应用
例