离散数学运算法则及例题
第一章 命题逻辑
1,否定
1) 幂等律 p ∧ p p
2) 交换律 p ∧ q q ∧ p
3) 结合律 （ p ∧q）∧ r p ∧ (q ∧ r )
4) 零律 p ∧ F F
5) 同一律 p ∧ T p
6) 否定律 p ∧ ¬ p
F
3,析取(+)
1) 幂等律
2) 交换律
3) 结合律
4) 同一律
5) 零律
6) 否定律
7) 吸收律
8) 分配律
9) 德、摩根律
4,蕴含
P→ Q读作“P蕴含Q”，“如果P则Q”，“当P，则Q”，“P是Q的充分条
是Q的充要条件”。
1. 1) 交换律
2. 2) 结合律
3. 说明：1)是逻辑联结词，而 是公式关系符。A、B是命题，A B仍是命题，而A B不是命题。(2) P、Q两命题，没有内在联系 P Q仍有意义。例：2+2=5的充要条件是太阳从西边升起。 该命题为真 几个重要定理
1.若A B， B C，则A C.传递性
2. A B的充要条件是A B且B A(逻辑等价的另一种定义） 其他的连接词符号
或非词符号
定理: A↓B等价于¬(AVB)
定理:{↓}是功能完备集
与非词符号
定理:A↑B等价于¬(A∧B)
定理:{↑}是功能完备集
异或词符号
举例说明:周末,我或者在北京或者在上海
定理:A异或B等价于¬(AB)
第二章谓词逻辑
谓词演算的推理规则
US 全称指定规则（消去量词）
UG 全称推广规则 对命题量化（添加量词）
ES 存在指定规则（消去量词）
EG 存在推广规则（添加量词）
第三章 集合
第四章关系
（R ◦ S）
（R·S）2=（R·S）·（R·S） = R·（S·R）·S
R-1
逆运算的性质
R和S均是A到B的关系，则
（1）（R-1）-1=R，
（2）（R∪S）-1=R-1∪S-1，
（3）（R∩S）-1= R-1∩S-1，
（4）（R-S）-1=R-1-S-1，
（5）（~R）-1=~(R-1),（A×B）-1=B×A
（6）ФA-1=ФA，EA -1 =EA, IA -1 = IA
（7）R=S iff R-1=S-1。
(8)（R-S）-1=（R∩S）-1=R-1∩（S）-1=R-1∩S-1=R-1-S-1 EG:
如|A|=n， A上自反关系共有?个 |A×A|=n2 ,其中n个有序对对应自回路， 故A上自反关系共有 2n(n-1)个。
例|A|=3，A上关系共有29个，而自反关系共有26个。