离散数学公式

2024年3月22日发(作者：怎么制作线上数学试卷图片)

基本等值式

1.双重否定律 A ┐┐A

2.幂等律

3.交换律

4.结合律

A A∨A, A A∧A

A∧B B∧A

(A∧B)∧C A∧(B∧C)

A∨B B∨A，

(A∨B)∨C A∨(B∨C)

5.分配律 A∨(B∧C) (A∨B)∧(A∨C) （∨对∧的分配律）

A∧(B∨C) (A∧B)∨(A∧C) （∧对∨的分配律）

A∨(A∧B) A，A∧(A∨B) A

A∨1 1,A∧0 0

A∨0 A，A∧1 A

A∨┐A 1

A∧┐A 0

A→B ┐A∨B

AB (A→B)∧(B→A)

A→B ┐B→┐A

(A→B)∧(A→┐B) ┐A

6.德·摩根律 ┐(A∨B) ┐A∧┐B ┐(A∧B) ┐A∨┐B

7.吸收律

8.零律

9.同一律

10.排中律

11.矛盾律

12.蕴涵等值式

13.等价等值式

14.假言易位

16.归谬论

15.等价否定等值式AB ┐A┐B

求给定公式范式的步骤

(1)消去联结词→、(若存在)。

(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。

(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。

推理定律--重言蕴含式

(1) A (A∨B)

附加律

假言推理

拒取式

假言三段论

析取三段论

等价三段论

(2) (A∧B) A

(3)(A→B)∧A B

化简律

(4) (A→B)∧┐B ┐A

(5) (A∨B)∧┐B A

(6)(A→B) ∧ (B→C) (A→C)

(7)(AB) ∧ (BC) (A C)

(8)(A→B)∧(C→D)∧(A∨C) (B∨D) 构造性二难

(A→B)∧(┐A→B)∧(A∨┐A) B 构造性二难(特殊形式)

(9)(A→B)∧(C→D)∧(┐B∨┐D) (┐A∨┐C) 破坏性二难

设个体域为有限集D={a1,a2,…,an},则有

（1）xA(x) A(a1)∧A(a2)∧…∧A(an)

（2）xA(x) A(a1)∨A(a2)∨…∨A(an)

设A(x)是任意的含自由出现个体变项x的公式，则

（1）┐xA(x) x┐A(x)

（2）┐xA(x) x┐A(x)

设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则

（1） x(A(x)∨B) xA(x)∨B

x(A(x)∧B) xA(x)∧B

x(A(x)→B) xA(x)→B

x(B→A(x)) B→xA(x)

x(A(x)∧B) xA(x)∧B

x(A(x)→B) xA(x)→B

x(B→A(x)) B→xA(x)

（2） x(A(x)∨B) xA(x)∨B

设A(x)，B(x)是任意的含自由出现个体变项x的公式，则

（1）x(A(x)∧B(x)) xA(x)∧xB(x)

（2）x(A(x)∨B(x)) xA(x)∨ xB(x)

全称量词“”对“∨”无分配律。

存在量词“”对“∧”无分配律。

xA(x)xA(x)

或

UG规则。

A(y)A(c)

A(y)

EG规则。

A(c)

xA(x)

EI规则。

xA(x)

xA(x)

A∪B＝{x|x∈A∨x∈ 、



B }

A(c)

UI规则。

A∩B＝{x|x∈A∧x∈B }

A－B＝{x|x∈A∧xB }

幂集 P(A)＝{x | xA}

对称差集 AB＝(A－B)∪(B－A)

AB＝(A∪B)－(A∩B)

绝对补集 ～A＝{x|x A }

广义并 ∪A＝{x | z(z∈A∧x∈z)} 广义交 ∩A＝{x | z(z∈A→x∈z)}

设 A＝{{a,b,c},{a,c,d},{a,e,f}} B＝{{a}} C＝{a,{c,d}}

则 ∪A＝{a,b,c,d,e,f}

∪B＝{a}

∪C＝a∪{c,d}

∪＝

∩A＝{a}

∩B＝{a}

∩C＝a∩{c,d}

A∪A＝A A∩A＝A

A∩B＝B∩A

A∩E＝A

集合恒等式

幂等律

交换律

分配律

同一律

零律

排中律

矛盾律

吸收律

结合律 (A∪B)∪C＝A∪(B∪C)

A∪B＝B∪A

A∪＝A

A∪E＝E

A∪～A＝E

A∪(A∩B)＝A

(A∩B)∩C＝A∩(B∩C)

A∪(B∩C)＝(A∪B)∩(A∪C)

A∩(B∪C)＝(A∩B)∪(A∩C)

A∩＝

A∩(A∪B)＝A

A∩～A＝

德摩根律 A－(B∪C)＝(A－B)∩(A－C) A－(B∩C)＝(A－B)∪(A－C)

～(B∪C)＝～B∩～C ～(B∩C)＝～B∪～C