离散数学知识点.docx

说明：
定义 ：红色表示。
定理性质： 橙色表示。
公式： 蓝色表示 。
算法 : 绿色表示
页码 ：灰色 表示 数理逻辑：
命题公式： 命题， 联结词 （ ，，，，），合式公式，子公式
公式的真值： 赋值，求值函数，真值表，的赋值下所取真值的表，称为
{1
A
0｝是一个真值赋值。
【】
的真值表。【】
重言式（永真式）
矛盾式（永假式）
等值式：若等价式
:任意赋值v
:任意赋值v
v A
有v^ A【】
A B是重言式，则称 A与B等值，记作
B。【】
基本等值式
双重否定律
募等律 交换律 结合律 分配律 德摩根律 吸收律
零律 A
同一律 排中律 矛盾律
A A A, A A A
A B B A, A B B A
(A B) C A (B C) (A B) A (A B) ,A
A, A A
A (B C),
(A
A
A,
B)
B
(A
(A
(A B) C A (B C),A (B C) (A (A B) A B B) A
C)
B)
(A C)
蕴涵等值式A B A B
等价等值式A
B (A B) (B A)
假言易位A B B A
等价否定等值式A B A B
归谬论 (A B) (A B)
置换规则：设X是公式 A的子公式
Y。将A中的X (可以是全部或部分X)用Y来置换,
所得到的公式B,则A B
文字 : 设 A (命题变元集)
则 A 和 A 都称为命题符号 A 的文字，其中前者称为正文字，
后者称为负文字。 【定义 】
析取范式：形如Ai A2…An(n 1)的公式称为析取范式，其中A(i=1,…,n)是由文字组成的合
取范式。
合取范式：形为Ai A2…An(n 1)的公式称为合取范式，其中Ai,…,AtB是由文字组成的析
取式。 【定义 】
极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。
极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。
】
主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。
主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。
【定义 】
公式的真值表中真值为 F 的指派所对应的极大项的合取，即为此公式的主合取范式。
真值函数： 称 F:{0,1}n{0,1} 为 n 元真值函数.【】
联结词的完备集： 设 C 是联结词的集合， 若对于任意一个合式公式均存在一个与之等价的公式，
而后者只含有C 中的联结词，则称C 是联结词的完备集。 【定义 】
{ ，，，，} ， {，，} , {，} ， {，} ， { ，}是联结词的完备集。 【定理
】
异或 P Q ： (P Q)
c
条件否定 P c Q： (P Q)
与非P Q ：(PQ)
或非P Q ：(PQ) 【】
{ },{ J}都是联结词的完备集【】
重言蕴含式： 当且仅当 P Q 是一个重言式时，称P 重言蕴含 Q ，记为 P Q 。
有效结论： 设 A 、 C 是两个命题公式，若 A C ，称 C 是 A 的有效结论。 【定义 】 推理定律——重言蕴涵式
A (A B) 附加律
(A B) A 化简律
(A B) A B 假言推理
(A B) B A 拒取式
(A B) B A 析取三段论
(AB)(BC)(AC) 假言三段论
(AB)(BC)(AC) 等价三段论
(A B) (C D) (A C) (B D) 构造性二难
(A B) ( A B) B 构造性二难 ( 特殊形式 )
(A B) (C D) ( B D) ( A C) 破坏性二难
形式系统 : 一个形式系统I 由下面四个部分组成：
(1)非空的字母表，记作 A(I).
A(I)中符号构造的合式公式集，记作EJ).
EJ)中一些特殊的公式组成的公理集，记作Ax(I).
(4)推理规则集，记作R(I).
记 I=< A(I),E(I),Ax(I),R(I)>,其中 <A(I),E(I)>是 I 的形式语言系统，<Ax(I),R(I)> 是 I 的形式演 算系统.
自然