离散数学知识点.docx

内容及范围主要来自ppt，标签对应书本
可能有错，仅供参考
离散数学知识点
说明：
定义：红色表示。
定理性质：橙色表示。
公式：蓝色表示。
算法: 绿色表示
页码：灰色表示
数理逻辑：
命题公式：命题， 真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【】
重言式〔永真式〕:任意赋值v， v A
矛盾式〔永假式〕:任意赋值v， 有v A【】
等值式：假设等价式A«B是重言式，那么称A与B等值，记作AÛB。【】
根本等值式
双重否认律 ØØAÛA
幂等律 AÚAÛA, AÙAÛA
交换律 AÚBÛBÚA, AÙBÛBÙA
结合律 (AÚB)ÚCÛAÚ(BÚC), (AÙB)ÙCÛAÙ(BÙC)
分配律 AÚ(BÙC)Û(AÚB)Ù(AÚC), AÙ(BÚC)Û(AÙB)Ú(AÙC)
德摩根律 Ø(AÚB)ÛØAÙØB ,Ø(AÙB)ÛØAÚØB
^
^
吸收律 AÚ(AÙB)ÛA, AÙ(AÚB)ÛA
^
零律 AÚ Û , AÙ^Û^
^
同一律 AÚ^ÛA, AÙ ÛA
内容及范围主要来自ppt，标签对应书本
可能有错，仅供参考
离散数学知识点
排中律 AÚØA Û
矛盾律 AÙØAÛ ^
蕴涵等值式 A®BÛØAÚB
等价等值式 A«BÛ(A®B)Ù(B®A)
假言易位 A®BÛØB®ØA
等价否认等值式A«BÛØA«ØB
归谬论 (A®B)Ù(A®ØB) ÛØA
置换规那么： 设Ｘ是公式A的子公式, ＸÛ Y。将A中的Ｘ〔可以是全部或局部X〕用Y来置换，所得到的公式B，那么 AÛB。
文字: 设AÎå〔命题变元集〕, 那么A和 Ø A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【】
析取范式：形如A1 Ú A2 Ú …Ú An (n³1) 的公式称为析取范式，其中Ai(i=1,…,n)是由文字组成的合取范式。
合取范式：形为A1Ù A2 Ù …ÙAn (n³ 1) 的公式称为合取范式，其中A1,…,An都是由文字组成的析取式。【】
极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。
极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【】
主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。
主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。
【】
公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。
真值函数： 称F:{0,1}n® {0,1} 为n元真值函数.【】
联结词的完备集：设C是联结词的集合，假设对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，那么称C是联结词的完备集。【】
{Ø，Ù，Ú，®，«}，{ Ø，Ù，Ú } , {Ø， Ù}， {Ø， Ú}，{^ ，®}是联结词的完备集。【】
c
异或PÅQ ： Û Ø (P « Q)
条件否认P®Q： Û Ø (P ® Q)
与非P­Q： Û Ø (P Ù Q)
或非P¯Q： Û Ø (P Ú Q)【】
{­},{↓}都是联结词的完备集【】
重言蕴含式：当且仅当P®Q是一个重言式时，称P重言蕴含Q，记为PÞQ。
有效结论：设A、C是两个命题公式，假设A Þ C，称C是A的有效结论。【】
推理定律——重言蕴涵式
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. (A«B)Ù(B«C) Þ (A«C) 等价三段论
8. (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 构造性二难
(A®B)Ù(ØA®B) Þ B 构造性二难(特殊形式)
内容及范围主要来自ppt，标签对应书本
可能有错，仅供参考
离散数学知识点
9. (A®B)Ù(C®