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

蕴涵():设P, Q是两个命题,,命题“若P,则Q”称为P蕴涵 Q,记作. 规定:是假的当且仅当P是真的而 Q是假的.
,R是A上的二元关系,R的自反闭包(对称闭包、传递闭包)满足如下条件:
(1)是自反的(对称的,传递的);
(2);
(3)对A上任意包含R的自反的(对称的,传递的)关系,都有.
、对称闭包和传递闭包分别记为,他们分别是包含R的最小(是指元素个数最小)的自反关系、对称关系和传递关系.
:设R是集合A上的关系,则
(1);
(2);
(3).
:
集合A上的关系R称为自反的(反身的),如果对于每个,都有
对于自反性,有3个命题是等价的:(1)R是自反的;(2); (3)是自反的.
集合A上的关系R称为对称的,如果xRy,则有yRx,其中.
对于对称性,有2个命题是等价的:(1)R是对称的;(2).
集合A上的关系R称为传递的,如果xRy, yRz,则有xRz, 其中.
集合A上的关系R称为反对称的,如果xRy, yRx,则必有x=y, 其中.
对于反对称性,有2个命题是等价的:(1)R是反对称的;(2).(注意这里若,也有,即若,也称R是反对称的).
集合A上的关系R称为反自反的,如果对于每个, 均不成立.
对于反自反性,有2个命题是等价的:(1)R是反自反的;(2).
注:逆关系:设R是集合A上的一个关系,令,称关系为关系R的逆关系.

基本的等价式如下:
(1);
(2);
(3); (等幂律)
(4); (交换律)
(5); (结合律)
(6); (吸收律)
(7); (分配律)
(8); (同一律)
(9); (零一律)
(10). (De Morgan 律)
:
(1);
(2);
(3);(因为
(4);(因为.
:的充要条件是公式是恒真的.
五.
:设R是非空集合A上的一个关系,若R具有自反性、对称性和传递性,则称 R是一个等价关系.
例子:设A={a, b, c},R={(a, a), (b, b), (c, c), (a, b), (b, a)}是A上的等价关系.
等价类:设A是一个非空集合,,如果
若,则;
若,则.
(即a,b属于同一个等价类当且仅当)
商集:设R是非空集合A上的一个等价关系,以R的所有不同的等价类为元素作成的集合称为A关于R的商集,简称A的商集,记作.
划分:当A的子集簇C满足如下条件时,称C为A的划分:
若,则;
(2);
(3)对任意的,且,则.
定理:设R是非空集合A上的一个等价关系,则A的商集构成A的一个划分;反之,若C是集合A的一个划分,令
,
则是A的一个等价关系.
:设A是集合,A中所有子集为元素构成的集合称为A的幂集。

设是n个不同的原子,一个短语如果恰好包含所有这n个原子或其否定,且其排列顺序与的顺序一致,则称此短语为关于的一个极小项.
共有个不同的极小项.
例子:有3个不同的原子P,Q,R,则是极小项.
书本定义2