离散数学（一）知识梳理•逻辑和证明部分o命题逻辑题型▪命题符号化问题将自然语言转为符号化逻辑命题▪用命题变量来表示原子命题▪用命题联结词来表示连词▪命题公式的类型判断判断命题公式是否是永真式、矛盾式、可能式▪利用真值表判断▪利用已知的公式进行推理判断▪利用主析取和合取范式判断▪定理：A为含有n个命题变元的命题公式，若A的主析取范式含有2^n个极小项，则A为重言式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为矛盾式；若A的主合取范式含有2^n个极大项，则A为矛盾式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为重言式▪翻译：一个命题公式化成主范式后，若所有项都分布在主析取范式中（主合取范式为1）则为重言式；若所有项都分布在主合取范式中（主析取范式为0）则为矛盾式；若均有分布，则为可满足式。
【思想来源：真值表法求主范式】▪一个质析取式是重言式的充要条件是其同时含有某个命题变元及其否定式；一个质合取式是矛盾式的充要条件是其同时含有某个命题变元及其否定式▪一个析取范式是矛盾式当且仅当它的每项都是矛盾式；一个合取范式是重言式当且仅当它的每项都是重言式▪求（主）析取或合取范式▪等值演算法▪ 1. 利用条件恒等式消除条件（蕴含和双条件）联结词，化简得到一个范式▪ 2. 在缺项的质项中不改变真值地添加所缺项，化简得到一个主范式▪ 3. 找出包含所有命题变元排列中剩余项，凑出另一个主范式（思想上类似于真值表法）▪真值表法▪ 1. 画出命题公式真值表▪ 2. 根据真值表结果求出主范式▪主析取范式：真值为1的所有项，每一项按对应01构成极小项▪主合取范式：真值为0的所有项，每一项按对应01构成极大项▪形式证明与命题推理利用推理规则构造一个命题公式的序列，证明结论▪形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。
注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。
也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。
选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。
如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。
关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。
当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。
蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。
