导图社区 离散数学第三章节命题逻辑
- 392
- 13
- 2
- 举报
离散数学第三章节命题逻辑
离散数学第四版邓文辉，将A 的所有可能的真值指派以及在每一个真值指派下的取值列为一个表，就得到命题公式 A 的真值表（truth table）。
编辑于2022-03-24 20:09:36- 离散数学
- 相似推荐
- 大纲
命题逻辑
命题的有关概念
什么是命题
命题是能判断出真假的语句
命题必须是一个完整的句子
命题的真值
命题的真值就是命题的逻辑取值
真值：1，假值：0
原子命题和复合命题
若一个命题不包含有更小的命题，则称其为原子命题或简单命题，否则称为复合命题
原子命题是命题逻辑研究的基本单位，区分原子命题在后 面命题的符号化时很重要
通常用小写英文字母 p, q, r, · · · 或带下标的 p1, p2, p3, · · · 表 示原子命题，
逻辑常量与逻辑变量
把 1 和 0 称为逻辑常量
在逻辑表达式中出现的 p, q, r, · · · 或 p1, p2, p3, · · · 称为命题 变元或逻辑变量
命题变元可以代表任意命题，从取值的角度看，命题变元 既可以取 1 又可以取 0。
逻辑联结词
否定联结词 ¬p
设 p 表示一个命题，¬p 是对命题 p 的否定（negation, not），读 作“非 p”。
子主题
合取联结词 p ∧ q
命题 p 与 q 的合取（conjunction，and）记为“p ∧ q”。合取联结 词 ∧ 相当于自然语言中的“并且”，“和”，“与”，“以及”等意思。
析取联结词 p ∨ q
命题 p 与 q 的析取（disjunction，or）记为“p ∨ q”。析取联结词 ∨ 相当于自然语言中的“或”，“或者”。
异或联结词 p ⊕ q
即“要么……要么……”，它表示两者 不能同时为真，换句话说，两者同时为真是假命题。这就 需要异或联结词。
条件联结词 p → q
条件命题 p → q 读作“p 条件 q”（conditional）。条件联结词 → 相当于自然语言中的“如果……那么……”，“若……则……”。在 p → q 中，p 称为前件（antecedent），q 称为后件（consequent）。
双条件联结词 p ↔ q
双条件命题 p ↔ q 读作“p 双条件 q”（biconditional）或“p 等价 q”（equivalence）。双条件联结词 → 相当于自然语言中的“当且 仅当”，“充分必要条件是”。
与非联结词 p ↑ q
与非命题 p ↑ q 读作“p 与非 q”（NOT AND），等于¬(p∧q)，先与 后非。与非联结词↑箭头的方向与合取联结词 ∧的尖方向一致。
或非联结词 p ↓ q
或非命题 p ↓ q 读作“p 或非 q”（NOT OR），等于¬(p ∨ q)，先或 后非。或非联结词↓箭头的方向与析取联结词∨的尖方向一致。
条件否定联结词 p 7→ q
条件否定命题 p 7→ q 读作“p 条件否定 q”（NOT IF · · · THEN）， 等于¬(p → q)，先条件后否定。
命题公式及其真值表
命题公式的定义
命题公式就是逻辑函数或逻辑表达式，其取值只可能为 1 或 0。
命题公式是由命题常量（逻辑常量 1 和 0）、命题变元（逻 辑变量）、逻辑联结词以及圆括号构成的有意义的符号串。
命题公式一般用 A, B, C, · · · 表示。若命题公式 A 中恰含有 n 个 命题变元 p1, p2, · · · , pn，则可以将 A 记为： A (p1, p2, . . . , pn) 显然，命题公式 A 就是命题变元 p1, p2, · · · , pn 的函数。
在形成最终的命题公式时，所有的中间过程得到的命题公式， 包含其本身，都称为该命题公式的子公式
9 个联结词运算的优先顺序依次为： ¬, ∧, ∨, ⊕, →, ↔, ↑, ↓, 7→ . 符合本约定的有些括号可以不写。同级运算从左至右依次进行
命题的符号化
命题的符号化就是使用符号——命题变元、逻辑联结词和括号 将所给出的命题表示出来。
命题的符号化的步骤： （1）找出所给命题的所有原子命题，并用小写英文字母或带下标 的小写英文字母表示； （2）确定应使用的联结词，进而将原命题用符号表示出来。
子主题
命题公式的真值表
对于命题公式 A，若对 A 中出现的每个命题变元都指定一个 真值 1 或者 0，就对命题公式 A 进行了一种真值指派 （assignment）或一个解释（interpretation），而在该指派下会求出 公式 A 的一个真值表。
将A 的所有可能的真值指派以及在每一个真值指派下的取值 列为一个表，就得到命题公式 A 的真值表（truth table）。
含 n 个命题变元的命题公式的不同的真值指派有 2n （2的n次方）种。
子主题
命题公式的类型
在任何指派下均取真的命题公式称为永真式、重言式 （tautology）或有效式（valid）；
在任何指派下均取假的命题公式 称为永假式或矛盾式（contradiction）；
至少有一种指派使其为真 的命题公式称为可满足式（satisfactable formula）；
至少有一种指 派使其为真，同时至少有一种指派使其为假的命题公式称为中 性式或偶然式（contingency）。
取值法证明永真式
证明 A → B 永真，可以通过由 A = 1 推出 B = 1或者由 B = 0 推出 A = 0 即可。
利用取值的方法得出一个命题公式的类型，这种方法可以 称为取值法。
取值法本质上是真值表法。
永真式代入定理
设命题公式 A(p1, p2, . . . , pn) 为永真式，则分别用命题公式 B1, B2, . . . , Bn 全部代换 A 中的命题变元 p1, p2, . . . , pn 所得到的 命题公式是永真式。其中，B1, B2, . . . , Bn 称为 A 的代入实例
永真式代入定理的使用方法
A 和 B 分别替换 p 和 q 代入永真的命题公式；
(p → q) ↔ (¬p ∨ q) 永真 ⇒ (A → B) ↔ (¬A ∨ B) 永真。
子主题
逻辑等值的命题公式
逻辑等值的定义
给定两个命题公式 A 和 B，若在任何真值指派下 A 和 B 的真值 都相同，则称命题公式 A 和 B逻辑等值（logically equal）或逻辑 相等（logically equivalent），简称为等值或相等，记为 A = B。
“=”表示两个命题公式之间的一种关系，逻辑等值
也可以记为 A ↔ B。
设 A 和 B 是命题公式，则 A = B 的充要条件是 A ↔ B 为永真 式。
命题公式间的等值关系是等价关系，即对任意命题公式 A, B, C，有
自反性：A = A.
对称性：若 A = B，则 B = A.
传递性：若 A = B 且 B = C，则 A = C
子主题
子主题
基本等值式
设 A, B, C 是任意的命题公式，则命题的 ¬, ∧, ∨ 运算有下列 重要的性质：
对合律：¬(¬A) = A.
幂等律：A ∨ A = A, A ∧ A = A.
交换律：A ∨ B = B ∨ A, A ∧ B = B ∧ A.
结合律：(A ∨ B) ∨ C = A ∨ (B ∨ C),(A ∧ B) ∧ C = A ∧ (B ∧ C)
吸收律：A ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A
分配律：A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
互补律：A ∨ ¬A = 1, A ∧ ¬A = 0（A 的补元为 ¬A）
德·摩根律：¬(A ∨ B) = ¬A ∧ ¬B, ¬(A ∧ B) = ¬A ∨ ¬B
幺元律：A ∨ 0 = 0 ∨ A = A, A ∧ 1 = 1 ∧ A = A
零元律：A ∨ 1 = 1 ∨ A = 1, A ∧ 0 = 0 ∧ A = 0
设 A, B 是任意的命题公式，则
异或等值式：A ⊕ B = ¬(A ↔ B) = (A ∧ ¬B) ∨ (¬A ∧ B)
条件等值式：A → B = ¬A ∨ B = ¬B → ¬A
双条件等值式：A ↔ B = (A → B) ∧ (B → A)
与非等值式：A ↑ B = ¬(A ∧ B).
或非等值式：A ↓ B = ¬(A ∨ B).
条件否定等值式：A 7→ B = ¬(A → B) = A ∧ ¬B
等值演算法
等值置换定理
设 C 是命题公式 A 的子公式且 C = D，则将 A 中的 C 部分或 全部替换成 D 所得到的命题公式与 A 等值。
利用基本等值式以及等值置换定理求解问题的方法称为等值演 算法
命题公式的化简是指将其化为一个与其等值的满足条件的含联 结词最少的命题公式。
子主题
对偶原理
子主题
设命题公式 A 中至多含有 3 个逻辑联结词 ¬, ∧, ∨ 将 A 中的 ∧ 换成 ∨，A 中的 ∨ 换成 ∧，A 中的 1 换成 0，A 中的 0 换成 1， 所得到的命题公式称为 A 的对偶式(dual formula)，记为A∗.
设 A 和 B 是命题公式，若 A = B，则 A∗ = B∗
∵ ¬(p ∧ q) = ¬p ∨ ¬q ∴ ¬(p ∨ q) = ¬p ∧ ¬q
命题逻辑中的推理
推理形式有效性的定义
逻辑学研究的主要内容是推理，推理是从一些前提推出结 论的思维过程
数理逻辑主要是用数学的方法研究逻辑中的推理，它关心 的是推理形式的有效性问题
所谓推理形式的有效性是指，如果前提全为真，那么所得结论 必然为真，而不考虑前提和结论的真实含义。
设 H1,H2, · · · ,Hn 和 C 是命题公式，若 H1,H2, · · · ,Hn 全为真， 可得出 C 必然真的结论，则称由 H1,H2, · · · ,Hn 得出 C 的推理 形式是有效的（valid argument form），记为H1,H2, · · · ,Hn ⇒ C， 其中H1,H2, · · · ,Hn 称为前提（antecedent, premise, hypothesis）， C 称为结论
H1,H2, · · · ,Hn ⇒ C 可读为H1,H2, · · · ,Hn 逻辑推出（logical follows）或逻辑蕴涵（logically implies）C，⇒ 是推断符号， H1,H2, · · · ,Hn ⇒ C 称为推理规则
H1,H2, · · · ,Hn 全为真可得出 C 必然真的充要条 件是H1 ∧ H2 ∧ · · · ∧ Hn → C 为永真式
设 H1,H2, · · · ,Hn 和 C 是命题公式，则 H1,H2, · · · ,Hn ⇒ C 的充 要条件是 H1 ∧ H2 ∧ · · · ∧ Hn → C 是永真式
又称 H1,H2, · · · ,Hn ⇒ C 是永真蕴涵式或逻辑蕴涵式。因此，⇒ 是“永真蕴涵”或“逻辑蕴涵”符号，它与蕴涵联结词 → 是不同 的。
⇒ 是关系符号，A ⇒ B 是逻辑蕴涵式
→ 是运算符号，A → B 是命题公式
通常所说的蕴涵指逻辑蕴涵
设 A 和 B 是命题公式，则 A ⇔ B 的充要条件是 A ⇒ B 且 B ⇒ A。 证 A ↔ B = (A → B) ∧ (B → A).
设 A, B, C 是命题公式，下述结论成立。 1. 自反性：A ⇒ A. 2. 反对称性：若 A ⇒ B 且 B ⇒ A，则 A = B。 3. 传递性：若 A ⇒ B 且 B ⇒ C，则 A ⇒ C。
设 A, B, C 是命题公式，下述结论成立。 (1) 若 A ⇒ C 且 B ⇒ C，则 A ∨ B ⇒ C. (2) 若 C ⇒ A 且 C ⇒ B，则 C ⇒ A ∧ B.
子主题
设 A, B 是命题公式，则对于命题公式间的永真蕴涵关系 ⇒，有 (1)sup {A, B} = A ∨ B. (2)inf {A, B} = A ∧ B.
设 A, B, C 是命题公式，则下列结论成立。 (1) A ∧ B ⇒ A, A ∧ B ⇒ B. (2) A ⇒ A ∨ B, B ⇒ A ∨ B. (3) A, B ⇒ A ∧ B. (4) A ∨ B, ¬A ⇒ B.
设 A, B, C 是命题公式，则下列结论成立。 (5) A → B, A ⇒ B. (6) A → B, ¬B ⇒ ¬A. (7) A → B, B → C ⇒ A → C. (8) A ∨ B, A → C, B → C ⇒ C.
子主题
基本推理规则
. 基本推理规则：真值表法，取值法，等值演算法，主范式 法；定理
命题逻辑的自然推理系统
命题公式的范式
命题公式的等值式很多，为其规定一种标准形式或规范形式， 就是其范式
命题公式的析取范式及合取范式
设 A 是命题公式，若 A = A1 ∨ A2 ∨ · · · ∨ An (n ≥ 1)，其中 Ai (1 ≤ i ≤ n) 是由命题变元或其否定组成的合取式，则称 A1 ∨ A2 ∨ . . . ∨ An 为 A 的析取范式
析取范式
Ai(1 ≤ i ≤ n) 是由命题变元或其否定组成的合取式
在每个 Ai 中，命题变元及其否定不同时出现
在每个 Ai 中，命题变元及其否定按字典顺序出现或按 下标从小到大顺序出现。
相同的合取式不同时出现（幂等律）
. A 的析取范式 A = A1 ∨ A2 ∨ · · · ∨ An 中，n 可以为 1。 n = 1 时，例如 A = ¬p ∧ ¬q ∧ r，则(¬p ∧ ¬q ∧ r) 是 A 的析 取范式。
合取范式
子主题
设 A 是命题公式，若 A = A1 ∧ A2 ∧ . . . ∧An(n ≥ 1)，其中 Ai(1 ≤ i ≤ n) 是由命题变元或其否定组成的析取式，则称 A1 ∧ A2 ∧ . . . ∧ An 为 A 的合取范式
Ai(1 ≤ i ≤ n) 是由命题变元或其否定组成的析取式。
(1) 在每个 Ai 中，命题变元及其否定不同时出现。 (2) 在每个 Ai 中，命题变元及其否定按字典顺序出现或按下标从小到大顺序出现。
相同的析取式不同时出现。
析取范式及合取范式主要的计算步骤
使用等值式，将命题公式中的联结词归约为 ¬, ∧, ∨
利用德·摩根律将 ¬ 移到命题变元的前面；
根据分配律得到命题公式的析取范式及合取范式
求析取范式用 A ∧ (B ∨ C) = (A ∧ B)∨(A ∧ C)
求合取范式用 A ∨ (B ∧ C) = (A ∨ B)∧(A ∨ C).
命题公式的主析取范式及主合取范式
一般来说，一个命题公式的析取范式及合取范式不是唯一 的。如 A = (p ∧ q) ∨ (p ∧ ¬q) = p 都是 A 的析取范式。
给定命题公式的唯一的标准形式：主析取范式以及主合取 范式
先定义 A 中命题变元产生的极小项和极大项，再据此给出 主析取范式以及主合取范式的定义
主析取范式
极小元
对于给定的命题变元，若由命题变元或其否定组成的合取式满 足以下两个条件：
每个命题变元或其否定两者之一只出现一次
按字典顺序或按下标从小到大顺序出现。
子主题
两个命题变元 p 和 q 产生的极小项有 p ∧ q, p ∧ ¬q, ¬p ∧ q, ¬p ∧ ¬q
三个命题变元 p, q, r 产生的极小项有 p∧q∧r, p∧q∧ ¬r, p∧ ¬q∧ r, p ∧ ¬q ∧ ¬r, ¬p ∧ q ∧ r, ¬p ∧ q ∧ ¬r, ¬p ∧ ¬q ∧ r, ¬p ∧ ¬q ∧ ¬r.
对于每一个极小项只有一种指派使其取 1
根据这个结论对极小项编码。极小项用 mi 表示，其下标 i 是 由成真指派得到的二进制数或对应的十进制数。
子主题
对于命题公式 A，若 A 等值于由A 中所有命题变元产生的若干 个极小项的析取，则把后者称为 A 的主析取范式
含 n 个命题变元的命题公式，“若干个”最大为 2n，最小为 0。
所有极小项的析取为永真式 1，而 0 个极小项的析取意味着 A 为永假式 0，这时 A 的主析取范式不存在。其他情况下，A 均为中性式。
求命题公式 A 的主析取范式方法
等值演算法，
1. 求出 A 的析取范式
2. 利用分配律补充缺少的命题变元
真值表法
写出命题公式 A 的真值表
对于使 A 取 1 的指派，写出对应的极小项，使该极小项在 该指派下也为 1。
(可以证明)A 等值于所有这样写出的极小项的析取.
主合取范式
极大项
对于给定的命题变元, 若由命题变元或其否定组成的析取式满足
每个命题变元或其否定二者之一只出现一次
按字典顺序或按下标从小到大顺序出现。
两个命题变元 p 和 q 产生的极大项有 p ∨ q, p ∨ ¬q, ¬p ∨ q, ¬p ∨ ¬q.
三个命题变元 p, q, r 产生的极大项有 p∨q∨r, p∨q∨ ¬r, p∨ ¬q∨ r, p ∨ ¬q ∨ ¬r, ¬p ∨ q ∨ r, ¬p ∨ q ∨ ¬r, ¬p ∨ ¬q ∨ r, ¬p ∨ ¬q ∨ ¬r
根据这个结论对极大项编码。极大项用 Mi 表示，其下标 i 是 由成假指派得到的二进制数或对应的十进制数
子主题
对于命题公式 A，若 A 等值于由A 中所有命题变元产生的若干 个极大项的合取，则把后者称为 A 的主合取范式
含 n 个命题变元的命题公式，“若干个”最大为 2n，最小为 0。
所有极大项的合取为永假式 0，而 0 个极大项的合取意味着 A 为永真式 1，这时 A 的主合取范式不存在。其他情况下，A 均为中性式
求命题公式 A 的主合取范式的方法
子主题
等值演算法，
求出 A 的合取范式。
. 利用分配律补充缺少的命题变元
真值表法
写出命题公式 A 的真值表
对于使 A 取 0 的指派，写出对应的极大项，使该极大项在 该真值指派下也为 0
(可以证明)A 等值于所有这样写出的极大项的合取
子主题
子主题
任意非永假命题公式都存在唯一的主析取范式； 任意非永真命题公式都存在唯一的主合取范式。
命题公式的主析取范式和主合取范式是等值的
主析取范式中所含的极小项个数加上主合取范式中所含的 极大项个数等于该命题公式的真值指派数目。
可以从主析取范式求出主合取范式，反过来亦然。
利用命题公式的主析取范式及主合取范式可以判定命题公式 的类型
利用命题公式的主析取范式及主合取范式可以判断两个命题 公式是否等值
一般原则是，若 A 取 1 的个数小于取 0 的个数，求主析取 范式；若 A 取 0 的个数小于取 1 的个数，求主合取范式
同一个命题公式的主析取范式与其主合取范式是等值的
子主题