date: 2025-06-11T23:33:00 aliases:

• 离散数学笔记第二章

---

二、命题逻辑等值计算

等值式

类似于普通计算里的恒等式，这里给几个思考的角度

1. 按照与或非运算
2. 按照集合运算

双重否定律

$a \iff \neg \neg A$

幂等律律

$A \iff A \lor A$ $A \iff A \land A$

交换律

$A \lor B \iff B \lor A$ $A \land B \iff B \land A$

结合律

$(A \lor B) \lor C \iff A \lor (B \lor C)$ $(A \land B) \land C \iff A \land (B \land C)$

分配律

$(A \land B) \lor C \iff (A \lor C) \land (B \lor C)$ $(A \lor B) \land C \iff (A \land C) \lor (B \land C)$

==德摩根律==

$\neg (A \lor B) \iff \neg A \land \neg B$ $\neg (A \land B) \iff \neg A \lor \neg B$

==吸收律==

$A∨(A∧B)⟺A$ $A∧(A∨B)⟺A$

同一律

$A∨0⟺A$ $A∧1⟺A$

零律

$A∨1⟺1$ $A∧0⟺0$

排中律

$A∨¬A⟺1$

矛盾律

$A∧¬A⟺0$

蕴含等值式

$A⟹B⟺¬A∨B$

等价等值式

$A⟺B⟺(A⟹B)∧(B⟹A)$

假言易位

$A⟹B⟺¬B⟹¬A$

归谬论

$(A \implies B)\land(A \implies \neg B) \iff \neg A$

析取范式与合取范式

这两个记个形状

析取范式

$(X_1 \land X_2)\lor(X_3 \land X_4)\lor(X_5 \land X_6)$

合取范式

$(X_1 \lor X_2)\land(X_3 \lor X_4)\land(X_5 \lor X_6)$

极大项与极小项

极大项

与成假赋值相关，如果成假赋值为 00 ， 10 ，那么名称可以记作 $M_0 , M_2$ (角标数字来自成假赋值的二进制转十进制)

极小项

与成真赋值相关，如果成真赋值为 01 ， 11 ，那么名称可以记作 $m_1,m_3$ (角标数字来自成假赋值的二进制转十进制)

注意：极大项与极小项在所有可能赋值中是互补的

主析取范式与主合取范式

这个的概念与上面的区别就在于 $X_1$ 要写成极大项或极小项的形式 在写题的时候要知道如P、Q、R的顺序

主析取范式

如 $(p \land q) \lor (\neg p \land q)$ 是一个析取范式，无 $\neg$ 符号的为 1 ，有的为 0 可以写成主析取范式： $m_1 \lor m_3$

主合取范式

如 $(p \lor q) \land (\neg p \lor q)$ 是一个合取范式，无 $\neg$ 符号的为 0 ，有的为 1 可以写成主合取范式： $M_0 \land M_2$

注意主析取范式对应的是极小项，主合取范式为极大项

连结词的完备集

定义：设连结词集合 $S$ ，如果任一命题公式可以仅由 $S$ 中的连结词表示，则称 $S$ 是一个连结词完备集

奇技淫巧：长这样的如： $S=\{\neg, \lor , ...\}$ 或者 $S=\{\neg, \land ,...\}$ 就是一个连结词完备集