命题逻辑
命题逻辑啊命题逻辑，就是把我们讲的那些能分出真假的话给数学化和符号化的……艺术？
好吧应该不能这么说
要开始上强度了啊……
快乐的开始：命题
那什么是命题捏？
专家说自然语言中能够判断真假的陈述句就是命题，如果命题是真的那就是真命题，是假的就是假命题（废话
专家还说能判断真假的简单陈述句就是简单命题，简单命题被关联词复合连接起来就是复合命题，但是啥是关联词呢？唉，这就很计算机了
专家说逻辑联结词有下面几种
$\neg$ 叫做否定联结词（not），也就是“非”，表示某个命题的否定，比如 $\neg p$
$\land$ 叫做合取联结词（and），也就是“与”，当两个连接的命题都为真时它也是真的，比如 $p \land q$
$\lor$ 叫做析取联结词（or），也就是“或”，只要连接的其中一个命题为真那它就是真的，比如 $p \lor q$
但是生活中有一种情况是 $p$ 和 $q$ 最多只有一个为真，在这种情况下专家觉得只用 $p \lor q$ 表示就不太准确了，于是就拉出来长长一串 $(\neg p \land q) \lor (p \land \neg q)$ ，也就是说这两种情况只有一种能发生。专家把这玩意叫做“排他性或”
$\rightarrow$ 叫做蕴含联结词（in）， $p \rightarrow q$ 读作“若 $p$ ，则 $q$ ”，叫做 $p$ 和 $q$ 的蕴含式， $p$ 和 $q$ 分别叫它的前件和后件，只有 p=1 而 q=0 时 $p \rightarrow q$ 才为假
$\leftrightarrow$ 叫做等价联结词（==），只要 $p$ 和 $q$ 同时为真或假，那 $p \leftrightarrow q$ 就为真
通过这些关联词和简单命题就能组合出各种乱七八糟的命题公式了
但首先还是看看什么是简单命题吧
- 李强不是教师。
- 小王会法语和英语。
下班高峰时，交通真拥挤！- 如果明天不下雨，我就去书店。
- 1+3=4当且仅当今天是3号。
- 张宏不是学习委员，也不是三好学生。
- 等价关系是离散数学中的一个概念。
- 如果暑假没有生产实习，我就去西藏或海南旅游。
- 这朵花是红色的。
上面一堆句子里面，加粗的都是关联词，被划掉的则连命题都不是，所以里面 7 和 9 简单命题， 3 不是命题，别的都是复合命题
但是这样的句子一点也不符号化，一点也不数学！
于是专家想到可以用字母来表示命题，就像用字母来表示数字一样：专家通常用 $a,A,p,P,q,Q$ 这些符号表示特定含义的命题，那这些字母就叫命题常量或者命题常元；而 $x,X,y,Y,z,Z$ 更多用来表示某些未知的命题，那这些字母被叫做命题变量或者命题变元
命题的联结：命题公式
把命题变成各种符号之后，那些长长的奇奇怪怪的命题也就可以表示出来了。那些符号连起来组成的 东西叫做命题逻辑公式，简单点就叫命题公式
命题公式有这样的规则：
- 单个 $a$ 或 $x$ 那肯定是命题公式
- 如果 $A$ 是命题公式，那 $\neg A$ 肯定也是命题公式
- 如果 $A$ 和 $B$ 都是命题公式，那 $A \land B, A\lor B, A \rightarrow B, A \leftrightarrow B$ 肯定也都是命题公式
- 有限次重复 1 2 3 得到的东西当然也是命题公式
如果一个命题公式只有一个联结词，那它就叫基本命题公式，如果不止一个就叫复杂命题公式了
我们总有不明白的时候……
但是有的时候，我们可能看到的只是一串命题公式，只凭这些乱七八糟的符号我们是判断不出来它的真假的，尤其是里面还有命题变元的时候
所以很多时候，对于一个命题公式，我们需要一个赋值，或者说是解释，这个解释记作 $I$ 。
在这个解释下，如果命题里面未知量（命题变元）的某组值可以让这个命题为真，那这组值就叫做命题公式的成真赋值，反之就是成假赋值
专家还发明了一种展示命题所有可能图表，叫真值表，基本长得像下面那样（除了没有竖线
| $p$ | $q$ | $\neg p$ | $p \land q$ | $p \lor q$ | $p \rightarrow q$ | $p \leftrightarrow q$ |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
除了必要的列（最简单的那几个变元和结果），剩下的列写不写出来就看你自己觉得方不方便了
别沮丧，进行分类是可行的
有些命题公式比较特别，所以专家专门为它们起了名字
比如永远为真的叫做永真公式或重言式，永远为假的叫永假公式或矛盾式，可能为真也可能为假的叫可满足公式
然后就……没了？专家你写这点东西真的要单开一小节吗？
坐和放宽，要开始计算了
这么多字母不算一下真是可惜了，如果 $A \leftrightarrow B$ 是重言式，那这俩命题公式就叫逻辑等值的，或者叫命题公式的等值式，当然亦可简称为等值式，写成 $A \Leftrightarrow B$
用等值式把命题公式替换成别的样子叫做命题逻辑的等值演算，简称就是等值演算
专家总结出了下面一大串的基本等值式，就像加法交换律一样是要记住的（不过大概不需要记名字
- 交换律： $A \lor B \Leftrightarrow B \lor A, A \land B \Leftrightarrow B \land A$ （超级显然
- 结合律： $(A \lor B) \lor C \Leftrightarrow A (\lor B \lor C), (A \land B) \land C \Leftrightarrow A (\land B \land C)$ （也挺显然？
- 分配律： $(A \lor B) \land C \Leftrightarrow (A \land C) \lor (B \land C), (A \land B) \lor C \Leftrightarrow (A \lor C) \land (B \lor C)$ （没那么显然了
- 吸收律： $A \land (A \lor B) \Leftrightarrow A, A \lor (A \land B) \Leftrightarrow A$ （怎么这么像集合
- 幂等律： $A \lor A \Leftrightarrow A, A \land A \Leftrightarrow A$ （这个太显然了
- 同一律： $A \lor 0 \Leftrightarrow A, A \land 1 \Leftrightarrow A$
- 零律： $A \lor 1 \Leftrightarrow 1, A \land 0 \Leftrightarrow 0$
- 排中律： $A \lor \neg A \Leftrightarrow 1$
- 矛盾律： $A \land \neg A \Leftrightarrow 0$
- 双重否定律： $A \Leftrightarrow \neg \neg A$
- 德·摩根律： $\neg (A \lor B) \Leftrightarrow \neg A \land \neg B, \neg (A \land B) \Leftrightarrow \neg A \lor \neg B$ （这个不显然
- 蕴含等值式： $A \rightarrow B \Leftrightarrow \neg A \lor B$
- 等价等值式： $A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \land (B \rightarrow A)$
- 假言易位： $A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$
- 等价否定等价式： $A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$ （这个确实显然
- 归谬论： $A \rightarrow B \land (A \rightarrow \neg B) \Leftrightarrow \neg A$
这些式子全部都要记住，不然可能就写不出题力
你今天看起来很不错！范式
专家发现， 命题公式通过前面一节的各种等值演算，都可以变成一类标准的形式，这些标准形式叫做命题公式的范式，简称就是命题范式
专家把有限个变元或其否定的析取 $\lor$ 组成的式子叫简单析取式，也就是 $\lor$ 和 $\land$ 之中只有 $\lor$ 的式子，比如 $p \lor q, \neg p \lor q \lor r$ 都算简单析取式，同理也有简单合取式
用有限个简单合取式的析取得到的是析取范式，这种范式看起来都可以用分配律，比如 $(p \land q) \lor (r \land \neg p)$ 就是一个析取范式；合取范式亦是同理，这两种范式统称为范式（好废话）
专家还发现所有命题公式都有等价的析取范式和合取范式
有 $n$ 个不互为非的命题变元的简单合取式叫这些命题变元的极小项，长得像 $p \land q \land \neg r$ 这样，大概是因为所有极小项里面只有一个为真，所以叫做极小项；同理也有极大项，所有极大项里面只有一个为假，那为真的概率是超级高的
如果一个析取范式的每个简单合取式都是极小项的话，这个析取范式又被称为主析取范式，类似的还有主合取范式
每个命题公式的主析取范式和主合取范式是唯一的
命题的演进：推理
专家所想的推理与大多数人理解的并无二致，唯一的不同点是普通人用文字推理，专家用符号推理
确保那是正确的
专家规定：对于 $A_1,A_2,\cdots,A_n$ 与 $B$ 这些命题，如果在 $A_1,A_2,\cdots,A_n$ 都为真时 $B$ 也是真的，那从 $A_1,A_2,\cdots,A_n$ 到 $B$ 的推理是正确的或有效的， $A_1,A_2,\cdots,A_n$ 就叫做 $B$ 的前提， $B$ 是以 $A_1,A_2,\cdots,A_n$ 为前提的逻辑结果，或者叫有效结论，记作 $A_1,A_2,\cdots,A_n \models B$
如果 $A \rightarrow B$ 恒为真，那它叫永真蕴含式或重言蕴含式，记作 $A \Rightarrow B$
当 $A_1 \land A_2 \land \cdots \land A_n \Rightarrow B$ 时有 $A_1,A_2,\cdots,A_n \models B$ ，这叫命题逻辑推理的直接方法
或者当 $A_1 \land A_2 \land \cdots \land A_n \land \neg B$ 是矛盾式时有 $A_1,A_2,\cdots,A_n \models B$ ，这叫命题逻辑推理的间接方法或反证法
让我们开始吧
推理这东西说起来也是很复杂的，对 $A_1 \land A_2 \land \cdots \land A_n \Rightarrow B$ 和 $A_1 \land A_2 \land \cdots \land A_n \land \neg B$ 这两个命题的推理用前面的东西就能解决，这两类命题的推理叫简单证明推理
既然有简单的那一定也有难的，如果命题之间是一环套一环，这样的推理就叫做构造证明推理
于是下面又有一大堆名字又怪又要记的推理规则：
- 化简式： $A \land B \Rightarrow A, A \land B \Rightarrow B,\neg (A \rightarrow B) \Rightarrow A, \neg (A \rightarrow B) \Rightarrow \neg B$
- 合取引入： $A,B \models A \land B$
- 附加式： $A \Rightarrow A \lor B,\neg A \Rightarrow A \rightarrow B$
- 假言推论： $A \land (A \rightarrow B) \Rightarrow B$
- 拒取式： $\neg B \land (A \rightarrow B) \Rightarrow \neg A$
- 析取三段论： $\neg A \land (A \lor B) \Rightarrow B$
- 条件三段论： $(A \rightarrow B) \land (B \rightarrow C) \Rightarrow A \rightarrow C$
- 双条件三段论： $(A \leftrightarrow B) \land (B \leftrightarrow C) \Rightarrow A \leftrightarrow C$
- 合取构造二难： $(A \rightarrow B) \land (C \rightarrow D) \land (A \land C) \Rightarrow B \land D$
- 析取构造二难： $(A \rightarrow B) \land (C \rightarrow D) \land (A \lor C) \Rightarrow B \lor D$
- 二难推论： $(A \rightarrow B) \land (C \rightarrow B) \land (A \land C) \Rightarrow B, (A \rightarrow B) \land (C \rightarrow B) \land (A \lor C) \Rightarrow B$
- 前后件附加： $A \rightarrow B \Rightarrow (A \lor C) \rightarrow (B \lor C),A \rightarrow B \Rightarrow (A \land C) \rightarrow (B \land C)$
不过这些式子虽然看起来很多……但仔细想想应该也不太难理解吧？
下面是一个直接构造证明的栗子
\[\begin{align} &\text{用直接构造证明} p \rightarrow r,q \rightarrow s, p\lor q, s \rightarrow t, \neg t \models r \\ &\textbf{证明} \\ &(1)~ p \rightarrow r \tag*{前提引入} \\ &(2)~ q \rightarrow s \tag*{前提引入} \\ &(3)~ p \lor q \tag*{前提引入} \\ &(4)~ r \lor s \tag*{(1)(2)(3)析取构造二难} \\ &(5)~ s \rightarrow t \tag*{前提引入} \\ &(6)~ \neg t \tag*{前提引入} \\ &(7)~ \neg s \tag*{(5)(6)拒取式} \\ &(8)~ r \tag*{(4)(7)析取三段论} \end{align}\]而在间接构造证明中，我们可以把某些前件（原结论中的前件？）作为附加前提引入，看能不能得到新的结论（原结论中的后件！）
间接构造证明还有一种方法，就是大名鼎鼎的反证法，亦称归谬推理，其步骤是将结论的否定 $\neg B$ 作为附加前提引入，然后在 $A_1,A_2,\cdots,A_n$ 和 $\neg B$ 的有效结论里面找到矛盾式，就能反证了
如果在这些规则上再加上一条：
- 归结： $(A \lor B) \land (\neg A \lor C) \Rightarrow B \lor C, (A \lor B) \land \neg A \Rightarrow B,A \land (\neg A \lor C) \Rightarrow C$
然后把前提和结论都变成合取范式再进行推理，这个方法被专家叫做直接归结推理（看不懂啊看不懂
而采用反证法推理则叫间接归结推理
唉命题逻辑的东西证明那么多，之后还要迎接一波新内容追加，是真的累啊啊啊