命题逻辑

命题与连结词

可兼或
- 例：张明正在睡觉或游泳：此处的或者是可兼或（不可以即在睡觉又在游泳）
- 令P：张明在睡觉，Q：张明在有用，转化为 $(P\and\lnot Q)\or(\lnot P\and Q)$
“除非”是必要条件
- 例：除非天气好，我才骑自行车上班
- 令P：天气好，Q：骑自行车上班，转化为 $Q\rightarrow P$

命题定律（部分）
- 吸收律： $A\and(A\or B)\Leftrightarrow A,\enspace A\or(A\and B)\Leftrightarrow A$
- 归谬率： $(A\rightarrow B)\and(A\rightarrow\lnot B)\Leftrightarrow\lnot A$
代入规则：在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。

对偶式：在给定的仅使用连结词 $\lnot,\and,\or$ 的命题公式A中，若把 $\and$ 和 $\or$ 互换，F和T互换得到一个命题公式 $A^*$ ，则称 $A^*$ 是 $A$ 的对偶式。
对偶定理：设 $A^*$ 和 $A$ 互为对偶式， $P_1,\dots,P_n$ 是出现在 $A^*$ 和 $A$ 的原子命题变元，则：
- $\lnot A(P_1,P_2,\dots,P_n)\Leftrightarrow A^*(\lnot P_1,\dots,\lnot P_n)$
- $A(\lnot P_1,\dots,\lnot P_n)\Leftrightarrow\lnot A^*(P_1,\dots,P_n)$
设A和B为两个命题公式，若 $A\Leftrightarrow B$ 则 $A^*\Leftrightarrow B^*$
蕴涵式：设A和B是两个命题公式，若 $A\rightarrow B$ 是永真式，则称A蕴涵B，记作 $A\Rightarrow B$ ，称 $A\Rightarrow B$ 为蕴涵式或永真条件式
蕴涵式证明方法：
1. 前件真推导后件真方法
2. 后件假推导前件假方法
基本蕴含式

待补充

主析取范式
1. 小项：在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。
2. 在给定公式的析取范式中，若其简单合取式都是小项，则称该范式为主析取范式。
3. 任意含n个命题变元的非永假命题公式A，都存在与其等价的主析取范式。
4. 任意含n个命题变元的非永假命题公式A，主析取范式惟一。
主合取范式
1. 大项：在含有n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为大项，或布尔和。
2. 在给定公式的合取范式中，若其简单合取式都是大项，则称该范式为主合取范式。
3. 任意含n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。
4. 任意含n个命题变元的非永真命题公式A，主析取范式惟一。
关系
1. $\lnot m_i\Leftrightarrow M_i$
2. $\lnot(m_{j1}\or m_{j2}\or\dots\or m_{j_{2^n-1}})\Leftrightarrow(M_{j1}\and M_{j2}\and\dots\and M_{j_{2^n-1}})$
3. 如一个命题的主析取范式为 $m_1,m_2,m_4$ ，那么它的主合取范式为 $m_3,m_5$

欲证明 $A_1,A_2,\dots,A_n\vdash C$ ，可采用如下步骤：