下载文档原格式
离散数学（一）知识梳理•逻辑和证明部分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构成极大项▪形式证明与命题推理利用推理规则构造一个命题公式的序列，证明结论▪形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。
离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。
A1:我是一名大学生.[10]：我是一名大学生。
R：我是一名大学生。
1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。
1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。
1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
离散数学（1）复习笔记Ch1 命题逻辑的基本概念1.1 命题命题：能判断真假且⾮真即假的陈述句。
命题的真值，真命题，假命题。
* 真值待定 *简单命题 | 原⼦命题，复合命题。
1.2 常⽤的5个命题联结词否定，合取，析取，蕴涵，双蕴涵。
* 异或 | 排斥或 | 不可兼或 * 注意语义判断。
* p→q = ﹁ p∨q ** 必要条件 * 只有……才……；仅当……，……；……，仅当……。
注意命题符号化的蕴涵⽅向。
* domain * A horse is white. （×）联结词集，⼀元联结词，⼆元联结词。
* 优先顺序 * （），﹁，∧，∨，→，↔1.3 合式公式及其赋值命题常项 | 命题常元（值是确定的），命题变项 | 命题变元（真值可以变化的陈述句）。
合式公式 | 命题公式 | 命题形式 | 公式（wff）（well formed formulas），原⼦命题公式（单个命题变项），⼦公式。
* 单个命题变项是合式公式，没说命题常项。
*赋值 | 解释，成真赋值，成假赋值。
真值表。
* 真值表要点：赋值从00…0开始，按照⼆进制加法，直到11…1为⽌；按照运算的优先次序写出各⼦公式。
*命题公式的分类：重⾔式 | 永真式，⽭盾式 | 永假式，可满⾜式。
1.4 重⾔式与代⼊规则代⼊规则。
* 1. 公式中被代换的只能是命题变项（原⼦命题），⽽不能是复合命题。
2.对公式中某命题变项施以代⼊，必须对该公式中出现的所有同⼀命题变项施以相同的代换。
* 1.5 命题形式化命题形式化 | 符号化。
* 注意充分条件和必要条件的区别 ** 注意语义是否考虑完整 *1.6 波兰表达式中置式 | 中缀式，前置式 | 前缀式 | 波兰式，后置式 | 后缀式 | 逆波兰式。
Ch2 命题逻辑的等值和推理演算2.1 等值定理等值 | 等价，等值定理：设A，B为两个命题公式，A = B的充分必要条件是 A↔B为⼀个重⾔式。
