命题逻辑
命题
具有确定真值的陈述句。如果命题为真， 其真值为真(T)， 否则真值为假(F)。
例子：
命题：李自成起义那天，杭州下雨。
已无法查明它的真值， 但它是或真或假的， 将它归属于命题。
非命题：
- x = 3
- 真好啊！
x=3是断言，但不是命题， 因为它的真值取决于x的值。 “真好啊！”不是断言， 所以不是命题。
原子命题
不能分解为更简单的陈述句。
例子：
别的星球上有生物。
思考： 这不应该是悖论？
复合命题
由联结词、标点符号和原子命题复合构成的命题。
例子：
如果地球是方的，那么恐龙现在还活着。
悖论
断言事实上不能指定它的真假， 所以不是命题。 这种断言叫悖论。
例子：
一个人说： “我正在说谎”。
他是在说谎还是在说真话呢? 如果他讲真话, 那么他所 说的是真, 也就是他在说谎。我们得出结论如果他讲真话, 那么他是在说谎。另一方面, 如果他是说谎, 那么他说的是 假; 因为他承认他是说谎, 所以他实际上是在说真话, 我们 得出结论如果他是说谎, 那么他是讲真话
从以上分析, 我们得出他必须既非说谎也不是讲真话。
命题联结词
否定词
否定词$\lnot$：类似于 非
合取词
合取词$\land$：类似于 交
析取词
析取词$\lor$：类似于 并
条件词
条件词$\rightarrow$：条件命题是一个复合命题，读作若P则Q， P为前件， Q为后件
条件式P →Q可以用多种形式描述：
- “若P, 则Q”
- “P是Q的充分条件”
- “Q是P的必要条件”
- “Q(每)当P”; ”只要P，就Q” ；”因为P，所以Q”
- “P仅当Q” ；”只有Q，才P” ；”除非Q，否则﹁P” 等。
真值表：
| $P$ | $Q$ | $P \rightarrow Q$ |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
双条件词
双条件词$\leftrightarrow$：双条件命题是一个复合命题， 读作 P双条件Q。 当P和Q的真值相同时， $P \leftrightarrow Q$的真值为T， 否则为F。
真值表：
| $P$ | $Q$ | $P \leftrightarrow Q$ |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
命题公式
命题公式（合式公式）的递归定义：
- 单个原子命题是一个命题公式。
- 如果 A 和 B 是命题公式，那么(﹁ A)，(A∧B)，(A∨B)，(A→B) 和（A B）都是命题公式。
- 当且仅当能够有限次地应用 ⑴、⑵所得到的包含命题变元，联结词和括号的字符串是命题公式。
运算符的优先级：$\lnot, \land, \lor, \rightarrow, \leftrightarrow$
命题常量和命题变元
命题常量：一个命题标识符如果表示确定的命题。 命题变元：一个命题标识符如果表示任意的命题。
翻译
使用命题公式，将自然语言中的命题，翻译成数理逻辑中的符号形式。
例子：设P：明天下雨， Q：明天下雪， R：我去学校。 则：
（i）“如果明天不是雨夹雪则我去学校”可写成：
\[(\lnot P \lor \lnot Q) \rightarrow R\]或者：
\[\lnot(P \land Q) \rightarrow R\]（ii）“如果明天不下雨并且不下雪则我去学校”可写成：
\[(\lnot P \land \lnot Q) \rightarrow R\]（iii）“如果明天下雨或下雪则我不去学校”可写成：
\[(P \lor Q) \rightarrow R\]（iv）”明天，我将风雪无阻一定去学校”可写成：
\[(P \land Q \land R) \lor (\lnot P \land Q \land R) \land (P \land \lnot Q \land R) \land (\lnot P \land \lnot Q \land R)\]考虑几种情况：
- $P \land Q$
- $\lnot P \land Q$
- $P \land \lnot Q$
- $\lnot P \land \lnot Q$
这几种情况都会去上学， 即$\rightarrow R$
（v）“当且仅当明天不下雪并且不下雨时我才去学校”可写成：
\[(\lnot P \land \lnot Q) \leftrightarrow R\]等值演算
重要！！！
真值表法
重点：
\[p \rightarrow q \Leftrightarrow \lnot p \lor q\]等价演算法
- 双重否定率：
- 交换律：
- 结合律：
- 分配律：
- 德摩根律：
- 幂等律：
- 吸收律：
- 零律：
- 同一律：
- 排中律：
- 矛盾律：
- 等价条件式：
- 双条件等价式：
- 假言易位式：
- 双条件否定等价式
例子：
【证明题】用等价演算法证明： $p \leftrightarrow q \Leftrightarrow (p \land q) \lor (\lnot p \land \lnot q)$
证明：
\[p \leftrightarrow q \Leftrightarrow (p \rightarrow q) \land (q \rightarrow p) \\ \Leftrightarrow (\lnot p \lor q) \land (\lnot q \land p) \\ \Leftrightarrow ((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land p) \\ \Leftrightarrow ((\lnot p \land \lnot q) \lor (q \land \lnot q)) \lor ((\lnot p \land p) \lor (q \land p)) \\ \Leftrightarrow (\lnot p \land \lnot q) \lor (q \land p)\]永真式和蕴涵式
- 若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式
- 若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式
- 若A不是矛盾式。则称命题公式A为可满足的
设A、B为两个命题公式， $A \Leftrightarrow B$当且仅当$A \leftrightarrow B$是永真式
设A和B是命题公式， 若$A \rightarrow B$是永真式， 则称A蕴涵B， 记为$A \Rightarrow B$
证明蕴涵的方法：
- 真值表法
- 等价演算法
- 对A指定真值T， 若推出B的真值为T
- 对B指定真值F，若推出A的真值为F
例子：
【证明题】证明$\lnot p \land (p \lor q) \Rightarrow q$
证： \(\lnot p \land (p \lor q) \rightarrow q \Leftrightarrow \lnot (\lnot p \land (p \lor q)) \lor q \\ \Leftrightarrow (p \lor \lnot (p \lor q)) \lor q \\ \Leftrightarrow (p \lor (\lnot p \land \lnot q)) \lor q \\ \Leftrightarrow ((p \lor \lnot p) \land (p \lor \lnot q)) \lor q \\ \Leftrightarrow (p \lor \lnot q) \lor q \Leftrightarrow p \lor (\lnot q \lor q) = 1\)
常用的推理定律：
- 附加律： $A \Rightarrow (A \lor B)$
- 化简律：$(A \land B) \Rightarrow A$
- 假言推理：$((A \rightarrow B) \land A) \Rightarrow B$ (含义是 A可以推出B， A成立了，B一定成立)
- 据取式：$((A \rightarrow B) \land \lnot B) \Rightarrow \lnot A$（A可以推出B，B不成立，A一定不成立）
- 条件（假言）三段论：$((A \rightarrow B) \land (B \rightarrow C)) \Rightarrow (A \rightarrow C)$
- 析取三段论：$(A \lor B) \land \lnot B \Rightarrow A$
- 合取引入规则：$A， B \Rightarrow (A \land B)$
设A，B为任意两个命题公式， 则$A \Leftrightarrow B$的充分必要条件是$A \Rightarrow B$且$B \Rightarrow A$
设A， B， C为合式公式
- $A \Rightarrow A$（即蕴涵是自反的）
- 若$A \Rightarrow B$且A为重言式， 则B为重言式 （为什么？）
- 若$A \Rightarrow B$且$B \Rightarrow C$， 则$A \Rightarrow C$（即蕴涵是传递的）
- 若$A \Rightarrow B$且$A \Rightarrow C$， 则$A \Rightarrow B \land C$
- 若$A \Rightarrow B$且$C \Rightarrow B$，则$A \lor C \Rightarrow B$
- 若$A \Rightarrow B$, C是任意公式， 则$A \land C \Rightarrow B \land C$
推理规则
- P规则 前提引入 可以在任何步骤上引入
- T规则 结论引入 可以引入前面已经得出的结论
-
CP规则 附加前提引入 如果要推导的结论是 R→C 可以把R加入前提 推出C
- UI或US规则 全称量词消去规则
- UG 全称量词推广规则
- EG 存在量词推广规则
- EI或ES 存在量词消去规则
联结词完备集
设S是一个联结词集合，如果任何$n(n \geq 1)$个变元组成的公式，都可以由S中的联结词来表示， 则称S是联结词完备集
- $S_1 = {\lnot, \land, \lor, \rightarrow, \leftrightarrow}$
- $S_2 = {\lnot, \land, \lor, \rightarrow}$
- $S_3 = {\lnot, \land, \lor}$
- $S_4 = {\lnot, \rightarrow}$
最小联结词完备集：
- $S_5 = {\lnot, \land}$
- $S_6 = {\lnot, \lor}$
范式
简单析取式和简单合取式
简单析取式：由命题变元或其否定构成的析取式
简单合取式：由命题变元或其否定构成的合取式
析取范式和合取范式
析取范式：由简单合取式构成的公式叫做析取范式，外析取内合取
合取范式：由简单析取式构成的公式叫做合取范式， 外合取内析取
主析取范式和主合取范式
在简单合取式中，每个变元及其否定不同时存在， 但两者之一必须出现且进出现一次， 这样的简单合取式叫做布尔合取也叫小项或极小项。
小项的性质：
- 每个小项当与其真值指派与编码相同时， 其真值为T， 在其余情况下均为F
- 任意两个不同小项的合取式永假
- 全体小项的析取式永真
主析取范式：首先是一个 析取式， 如果它有一个等价公式，仅有最小项组成，称为该公式的主析取范式。
在真值表中，一个公式的成真指派所对应的小项的析取，即为该公式的主析取范式， 即为该公式的主析取范式。
