命题

• 陈述句

• 确定性（真值唯一）

• 非悖论

• 拉塞尔悖论：涉及集合论中关于“所有不包含自身的集合的集合是否包含自身”的悖论。

• 撒谎者悖论：如“这句话是假的”，该语句如果是真的，那么它就是假的；如果它是假的，那么它就是真的。

• 祖父悖论：与时间旅行相关，假设你回到过去杀死了祖父，那么你将无法出生，从而无法回去杀死祖父。

• 芝诺悖论：如“阿基里斯与龟”的悖论，认为快速的阿基里斯永远无法追上慢速的乌龟，因为他必须先到达乌龟曾经所在的位置，而乌龟在此期间也会前进。

简单命题（原子命题）

• 由简单陈述句组成

• 不能分解为更简单的句子

复合命题

• 由简单命题与联结词按一定规则复合的命题

命题符号

蕴含

• 如果p，则q

• 先充分后必要

• “如果””只有””若”均为充分条件

• “除非”为必要条件

• 性质

命题分类

• 重言式：公式所有取值为1

• 矛盾式：公式所有取值为0

• 可满足式：公式取值有0有1

• 个命题变项最多有个真值不同的命题公式

置换定理

等值演算

等值

等值式

零元，同一元

• 零元（串并联上决定结果的因素）

• 同一元（串并联上不改变结果的元素）

利用等值式解决问题

1. 用事件表示条件（善用下标作为二维条件，通常下标相等会引发矛盾）， 1

2. 将各式依次在一起（）

3. 利用分配律和约束条件化简（化简为析取范式，即最简与或表达式）

4. 得出最终式，提取结果

范式

• 简单析取式：或表达式

• 简单合取式：与表达式

• 析取范式：与或表达式

• 合取范式：或与表达式
例

• 简单析取式为只有一项的合取范式

• 简单合取式为只有一项的析取范式

• 对偶式：与或表达式和或与表达式之间转换，符号全部取反

对偶式

对偶定理

主析取（合取）范式

参考数字电路的最大项和最小项，即用二进制编码将成真的排列列举出来再合并。

解题步骤

例题

成真（成假）赋值

例

联结词与全功能集

与非/或非

定义式

真值表

性质

全功能集

• 命题公式的集合。

• 任一真值函数都可以用仅含该集合中的命题公式表示。

组合电路

步骤

1. 构造输入输出表(问题的真值函数，真值表)

2. 写出主析取范式

3. 化简

最简展开式

奎因-莫可拉斯基方法

• 先用01数码表示，尽量把1个数相同的放在一起，升序排列

• 寻找1数量相邻的项，且两项只差一位数

• 合并，不同的项合并为-，合并过的项打上标记

• 重复前两个操作，无法合并时，所有没有打标记的项合起来就是最简展开式

例题

推理理论

判断推理是否正确的方法

• 真值表法

等值演算法

主析取范式法

• 构造证明法
• 直接证明法
• 附加前提证明法
• 归谬法

直接证明法

• 层层引入后利用推理规则化简，最后得出结论

例子

附加前提证明法

例子

归谬法

例子