《离散数学及其应用》第一章·逻辑和证明 学习笔记
一、先导概念
- 命题:是一个陈述句,或真或假,但不能既真又假。
接下来我们字母表示命题变元,例如 p,q,r,s 等。后文所述真值可理解为命题的真假性,命题为真记作 T,命题为假记作 F。
- p的否定/逆命题:$\lnot p$ 或 $\overline{p}$ ,读作 “非 p”
p | $\lnot p$ |
---|---|
T | F |
F | T |
从真值表中可以看出,命题 p 和 命题 p 的否定真值相反。
- p,q 的合取命题(AND):$p \bigwedge q$,读作 “p 并且 q”
p | q | output |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
从真值表可以看出,当且仅当合取的两命题均为真时,结果为真。
- p,q 的析取命题(OR):$p \bigvee q$,读作 “p 或 q”
p | q | output |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
从真值表可以看出,只要两个合取的两命题有一个为真时,结果为真。
- p,q 的异或命题(XOR):$p \bigoplus q$,读作 “p 异或 q”
p | q | output |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
从真值表可以看出,当异或的两个命题中恰好只有一个为真(两命题的真值不同),结果为真。
- 条件语句:$p \rightarrow q$,读作 “如果 p,则 q”。我们通常将 p 称为 (前提)前件,将 q 称为(结论)后件。
p | q | output |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
相比之前的概念,这个真值表可能较难理解,在此举一个例子:设 p 为命题 “天下雨”,命题 q 为 “我不去打球”。则条件语句 “$p \rightarrow q$” 可以翻译为 “如果天下雨,我就不去打球”。将不同的真值带入:
p 的真值 | 命题 | q 的真值 | 命题 | output |
---|---|---|---|---|
T | 天下雨 | T | 我不去打球 | T |
T | 天下雨 | F | 我去打球 | F |
F | 天不下雨 | T | 我去打球 | T |
F | 天不下雨 | F | 我不去打球 | T |
可以发现,只有当 p(前提) 的真值为 T ,q(结论) 的真值为 F,条件语句才为 F。
- 逆命题:$p \rightarrow q$ 和 $q \rightarrow p$ 互为逆命题,也就是交换前提和结论。
- 逆否命题: $p \rightarrow q$ 和 $\lnot q \rightarrow \lnot p$ 互为逆命题,也就是交换前提和结论,并且取条件和结论的逆命题。
- 反命题:$p \rightarrow q$ 和 $\lnot p \rightarrow \lnot q$ 互为反命题,也就是取条件和结论的逆命题。
以下为有关逆命题、逆否命题、反命题的一些结论:
- 原命题和逆否命题的真值相同
- 逆命题和反命题都不具有相同的真值
一般地,我们称两个总具有相同真值的复合命题为等价命题。同时,为表达命题的等价,我们同样也可以运用双条件语句。
- 双条件语句:$p \leftarrow\rightarrow q$,读作 “p 当且仅当 q”,也称 p 为 q 的充分必要条件。等价于 $(p \rightarrow q) \bigwedge (q \rightarrow p)$
p | q | output |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
较为容易理解,因为双条件语句的定义是 p 和 q 等价,所以只有当 p 和 q 的真值相同时结果才为 T 。
至此我们介绍了部分逻辑运算符,我们希望你可以了解一下逻辑运算符的优先级:
运算符 | 优先级 |
---|---|
$\lnot$ | 1 |
$\bigwedge$ | 2 |
$\bigvee$ | 3 |
$\rightarrow$ | 4 |
$\leftarrow \rightarrow$ | 5 |
二、一些逻辑恒等式
等价式 | 解释 | 名称 |
---|---|---|
$p \bigwedge T \equiv p$ $p \bigvee F \equiv p$ |
恒等律 | |
$p \bigvee T \equiv T$ $p \bigwedge F \equiv F$ |
支配律 | |
$p \bigvee p \equiv p$ $p \bigwedge p \equiv p$ |
对于合取与析取的幂运算,结果仍为论元本身 | 幂等律 |
$\lnot (\lnot p) \equiv p$ | 双重否定律 | |
$p \bigvee q \equiv q \bigvee p$ $p \bigwedge q \equiv q \bigwedge p$ |
合取与析取满足交换律 | 交换律 |
$(p \bigvee q) \bigvee r \equiv p \bigvee (q \bigvee r)$ $(p \bigwedge q) \bigwedge r \equiv p \bigwedge (q \bigwedge r)$ |
合取与析取满足结合律 | 结合律 |
$(p \bigvee q) \bigwedge r \equiv (p \bigvee r) \bigwedge (q \bigvee r)$ $(p \bigwedge q) \bigvee r \equiv (p \bigwedge r) \bigvee (q \bigwedge r)$ |
合取与析取满足分配律 | 分配律 |
$\lnot (p \bigwedge q) \equiv \lnot p \bigvee \lnot q$ $\lnot (p \bigvee q) \equiv \lnot p \bigwedge \lnot q$ |
将 $\lnot$ 分配到每个论元,合取与析取互换 | 德·摩根律 |
$p \bigvee \lnot p \equiv T$ $p \bigwedge \lnot p \equiv F$ |
否定律 | |
$p \bigvee (p \bigwedge q) \equiv p$ $p \bigwedge (p \bigvee q) \equiv p$ |
p 并 (p和q的交集)还是 p p 交 (p和q的并集)还是 p |
吸收律 |
$p \rightarrow q \equiv \lnot p \bigvee q$ $p \rightarrow q \equiv \lnot q \rightarrow \lnot p$ $p \bigvee q \equiv \lnot p \rightarrow q$ $p \bigwedge q \equiv \lnot (p \rightarrow \lnot q)$ $\lnot(p \rightarrow q) \equiv p \bigwedge \lnot q$ $(p\rightarrow q) \bigwedge (p \rightarrow r) \equiv p \rightarrow (q \bigwedge r)$ $(p \rightarrow r) \bigwedge (q \rightarrow r) \equiv (p \bigvee q) \rightarrow r$ $(p \rightarrow q) \bigvee (p \rightarrow r) \equiv p \rightarrow (q \bigvee r)$ $(p \rightarrow r) \bigvee (q \rightarrow r) \equiv (p \bigwedge q) \rightarrow r$ |
$\rightarrow$ 可以理解为 $\lnot \bigvee$ 第三个和第四个需要牢记 |
条件命题的逻辑等价式 |
$p \leftarrow \rightarrow q \equiv (p \rightarrow q) \bigwedge (q \rightarrow p)$ $p \leftarrow \rightarrow q \equiv \lnot p \leftarrow \rightarrow \lnot q$ $p \leftarrow \rightarrow q \equiv (p \bigwedge q) \bigvee (\lnot p \bigwedge \lnot q)$ $\lnot (p \leftarrow \rightarrow q) \equiv p \leftarrow \rightarrow \lnot q$ |
$\lnot$ 可以挪到双条件表达式的后项 | 双条件命题的逻辑等价式 |
三、谓词、量词
- 谓词
一般地,涉及 n 个变量 $x_1$,$x_2$,…,$x_n$ 的语句可以表示为 $P(x_1,x_2,…,x_n)$ ,我们将其称为命题函数 P 在 n 元组 ( $x_1$,$x_2$,…,$x_n$) 的值,P 也称为 n 元谓词。
量词:量词比命题演算中所有逻辑运算符的优先级都更高
- 全称量词:全体域均可使命题成立。用符号 $\forall$ 表示。
- 存在量词:存在一个个体使命题成立。用符号 $\exists$ 表示。
量化表达式的否定:$\forall x P(x) \equiv \exists x \lnot P(x)$
嵌套量词:一个量词出现在另一个量词的作用域中,例如 $\forall x \forall y (x + y = y + x)$
量词的顺序:量词的顺序十分重要,除非所有的量词均为全称量词或者存在量词。(言下之意:如果只有全称量词或存在量词,则可前后交换顺序)
嵌套量词的否定
$\lnot (\forall x \exists y (xy = 1)) = \exists x \lnot \exists y (xy = 1)$ (将否定词移入所有量词之中)
= $\exists x \forall y \lnot (xy = 1)$ = $\exists x \forall y \lnot (xy \not= 1)$
四、推理
- 推理规则:
名称 | 永真式 | 理解 |
---|---|---|
假言推理 | $p \bigwedge ( p \rightarrow q)) \rightarrow q$ | 已知 p ,$p \rightarrow q$,可以推得 q |
取拒式 | $(\lnot q \bigwedge (p \rightarrow q)) \rightarrow \lnot p$ | 已知 $\lnot q$,$p \rightarrow q$,可以推得 $\lnot p$ |
假言三段论 | $((p \rightarrow q) \bigwedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ | 已知 $p \rightarrow q$,$q \rightarrow r$,可以推得 $p \rightarrow r$ |
析取三段论 | $((p \bigvee q) \bigwedge \lnot p) \rightarrow q$ | 已知 $p \bigvee q$,$\lnot p$,可以推得 q |
附加律 | $p \rightarrow (p \bigvee q)$ | 已知 p,可以推得 $p \bigvee q$ |
化简律 | $(p \bigwedge q) \rightarrow p$ | 已知 $p \bigwedge q$,可以推得 p |
合取律 | $((p) \bigwedge (q)) \rightarrow (p \bigwedge q)$ | 已知 p,q,可以推得 $p \bigwedge q$ |
消解律 | $((p \bigvee q) \bigwedge (\lnot p \bigwedge r)) \rightarrow (q \bigvee r)$ | 已知 $p \bigvee q$,$\lnot p \bigvee r$,可以推得 $q \bigvee r$ |
- 量化命题的推理规则:
- 全称实例:由 $\forall x P(x)$ 得出 $P(c)$
- 全称引入:由 论域中所有元素 c 都存在$P(c)$,得出 $\forall x P(x)$
- 存在实例:由 $\exists x P(x)$,得出 $P(c)$。但是 c 不知道确切的值,仅知道存在。
- 存在引入:由 $P(c)$,得出 $\exists x P(x)$
五、证明
直接证明法:($p \rightarrow q$)
第一步:假设 p 为真;第二步:用推理规则构造;第三步:推导出 q 为真。
反证法:($p \rightarrow q$ 等价于 $\lnot q \rightarrow \lnot p$)
第一步:假设 $\lnot q$;第二步:用推理规则构造;第三步:推导出 $\lnot p$ 为真。
空证明:如果能证明 p 为假,则我们就有了一个 $p \rightarrow q$ 的证明方法
平凡证明:如果能证明 p 为真,则我们也可以很快证明出 $p \rightarrow q$
归谬证明:如果我们能证明对于某个命题 r,$\lnot p \rightarrow (r \bigwedge \lnot r)$为真,则可以得出:p 是真的
等价证明法:为了证明双命题条件 $p \leftarrow \rightarrow q$,则需要证明 $p \rightarrow q$ 和 $q \rightarrow p$
唯一性证明:(存在性:P(c))&&(唯一性:如果 $b \not= c$,则 P(b) 不成立)
参考书籍:《离散数学及其应用》Kenneth H. Rosen 著