命题逻辑

命题

具有确定真值的陈述句。如果命题为真，其真值为真(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\]

等价演算法

双重否定率：

\[A \Leftrightarrow \lnot \lnot A\]

交换律：

\[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 \land (B \land C) \Leftrightarrow (A \land B) \lor (A \land C) \\ A \lor (B \lor C) \Leftrightarrow (A \lor B) \land (A \lor C)\]

德摩根律：

\[\lnot (A \lor B) \Leftrightarrow \lnot A \land \lnot B \\ \lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B\]

幂等律：

\[A \land A \Leftrightarrow A \\ A \lor A \Leftrightarrow A\]

吸收律：

\[A \lor (A \land B) \Leftrightarrow A \\ A \land (A \lor B) \Leftrightarrow A\]

零律：

\[A \lor 1 \Leftrightarrow 1 \\ A \land 0 \Leftrightarrow 0\]

同一律：

\[A \lor 0 \Leftrightarrow A \\ A \land 1 \Leftrightarrow A\]

排中律：

\[A \lor \lnot A \Leftrightarrow 1\]

矛盾律：

\[A \land \lnot A \Leftrightarrow 0\]

等价条件式：

\[A \rightarrow B \Leftrightarrow \lnot A \lor B\]

双条件等价式：

\[A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \land (B \rightarrow A)\]

假言易位式：

\[A \rightarrow B \Leftrightarrow \lnot B \rightarrow \lnot A\]

双条件否定等价式

\[A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B\]

例子：

【证明题】用等价演算法证明： $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
任意两个不同小项的合取式永假
全体小项的析取式永真

主析取范式：首先是一个析取式，如果它有一个等价公式，仅有最小项组成，称为该公式的主析取范式。

在真值表中，一个公式的成真指派所对应的小项的析取，即为该公式的主析取范式，即为该公式的主析取范式。

Reference

离散数学笔记

On this page