第二章命题逻辑等值演算

例：人不犯我，我不犯人；人若犯我，我必犯人。 解：令 P：人犯我。 Q：我犯人。 该命题符号化为： (PQ)∧(PQ) 或： PQ
2.1.2 命题公式及分类
本节主要讨论：
命题公式的定义 命题公式的层次 命题公式的真值表 命题公式的分类
一、命题公式的概念
命题常项：简单命题。 命题变项：真值可以变化的陈述句。
p∧q 的逻辑关系是 p与q同时为真
p∧q真值表如图所示：
P
Q
P∧ Q
0
0
0
0
1
0
1
0
0
1
1
1
(2) 合取联结词“∧” －－且
例如，p: 李军聪明 q: 李军用功 则命题 “李军既聪明又用功” 可描述为： p∧q
以下自然语言中的联结词等都可以抽象为“∧” 。 “并且”、“既…又…”、 “与”、“和”、“以及”、
一、命题公式的概念
例: (1) A = p ∨q，
则 A是2层公式。
(2) A = p ∧ q ∧ r ， 则 A是2层公式。
(3) A =(p ∧q) (r ∨s)， 则A为4层公式。
二、公式的赋值或解释
定义2.8 (P.44) －－公式的赋值或解释
设A 为含有命题变项 p1, p2,…, pn的命题公式, 给 p1, p2, …, pn 一组确定的真值, 称作对公式 A
举例：
令：p：天气好。
q：我去公园。
如果天气好，我就去公园。符号化为：pq
只要天气好，我就去公园。
pq
仅当天气好，我才去公园。
qp
只有天气好，我才去公园。
qp
我去公园玩，除非天气好。
qp
例2.5 将下列命题符号化，并求其真值。

保持等值性的两条规则
代入规则: 等值式模式的代换实例是等值式. 在蕴涵等值式 A B AB 中取 A 为 p, B 为 q 得
p q p q. 而取 A 为 p q r, B 为 p q 则得
(p q r) (p q) (p q r) (pq). †具体的等值式叫做等值式模式的代入实例.
101 1 1
011
110 1 1
110
111 1 1
111
离散数学(60). W&M.
§2.1 等值式

涉及联结词 , 的运算律有
蕴涵等值式: A B A B 等价等值式: (AB) (AB)(BA) 假言易位: A B B A 等价否定律: A B A B 以及: A (B C) (A∧B) C 等.
离散数学(60). W&M.
§2.1 等值式

第二章 命题逻辑等值演算
§2.1 等值式 §2.2 析取范式与合取范式 §2.3 联结词的完备集
离散数学(60). W&M.
§2.2 析取范式与合取范式

公式的标准形式
实数代数 R, +, * 中, 函数有不同的表达式, 其中多项 式和多因式是“标准形式”.
即 (pq) r (pq)r.
离散数学(60). W&M.
§2.1 等值式

例2 用等值演算法证明 (pq) q p q.
证 (p q) q
q (p q)
交换律
(q p) (q∨ q)
分配律
(q p) 1
排中律和替换规则
A = A1 A2 … As; 一个合取范式是重言式 它的每个简单析取式都 是重言式.

0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
m0 m1 m2 m3 m4 m5 m6 m7
pqr p q r p q r p q r p q r p q r p q r p q r
0 0 0 0 1 1 1 1
(2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成
Bj Bj(pipi) (Bjpi)(Bjpi) 重复这个过程, 直到所有简单合取式都是长度为n的极
小项为止
(3) 消去重复出现的极小项, 即用mi代替mimi (4) 将极小项按下标从小到大排列
23
求公式主范式的步骤
(pq)r
0 1 0 1 1 1 0 1
4
结论: p(qr) 与 (pq) r 不等值
基本等值式
双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC)(AB)(AC), A(BC)(AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
M0 M1 M2 M3 M4 M5 M6 M7
21
mi与Mi的关系： mi Mi, Mi mi
主析取范式与主合取范式
主析取范式——由极小项构成的析取范式 主合取范式——由极大项构成的合取范式 例如，n=3, 命题变项为 p, q, r 时， (pqr)(pqr) m1m3 ——主析取范式 (pqr)(pqr) M1M7——主合取范式
第二章 命题逻辑等值演算
主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集 可满足性问题与消解法

定理 2.5.4 若A = B必有A*=B* 证明: 因为A = B等价于AB 永真等价 于AB永真。 依定理2.5.3, A = A*－, B = B*－ 于是 A*－ B*－ 永真 必有 A* B* 永真 故 A* = B*
2021/1/15
定理2.5.5 若AB永真, 必有B*A*永真 定理2.5.6 A与A－同永真, 同可满足
15.从取假来描述双条件词
PQ = (P∨Q)∧(P∨Q)
16. 从蕴涵词描述双条件词 PQ = (PQ)∧(QP)
2021/1/15
2.2.3 置换规则 (注意与代入规则p8的区别)
置换定义：对公式A的子公式, 用与之等值的 公式来代换便称置换。
置换规则：将公式A的子公式置换后，A化为 公式B, 必有A = B。
2021/1/15
2.4 联结词的完备集
问题的提出：对n 个命题变项P1…Pn来说, 共 可定义出多少个联结词? 在那么多联结词中有 多少是相互独立的? 介绍3个新型联结词： 异或 ∨: P∨Q =(P∧Q)∨(P∧Q) 与非 : P Q = (P∧Q) 或非 : P Q = (P∨Q)
2021/1/15
特别注意
✓如果一个联结词的集合是不完备的，那 么它的任何子集都是不完备的。因此， {∨,∧,, }的任何子集都是不完备的。 {, }的任何子集也是不完备的。 ✓由此可推知，集合3,4,5,6,7都是独立的 完备集。事实上，6,7是仅有的两个只有一 个联结词的完备集(不证). ✓{∨,∧}不是完备的(不证).
2.4.1 命题联结词的个数
• 要解决本节提出的第一个问题，首先要把n 个命题变项构造出的无限多个合式公式分 类。
• 将等值的公式视为同一类，从中选一个作 代表称之为真值函项。对一个真值函项， 或者说对于该类合式公式，就可定义一个 联结词与之对应。

9. Q (PQ) PBiblioteka 拒取式基本的推理公式
10. (PQ)(QR) PR 假言三段论 11.(PQ)(QR) P R 等价三段论 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 构造性二难 14. (PQ)(RS)( QS) (PR) 破坏性二难 15. (QR) ((PQ) (PR)) 16. (QR) ((PQ) (PR))
附加前提证明法 ——举例
例如：证明下列推理。 前提： P(QR)，S∨P, Q 结论： S R 证明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段论 (4) P (Q R) 前提 (5) Q R (3)(4) 假言推理 (6) Q 前提 (7) R (5)(6) 假言推理
((PQP Q
例：判断下面推理是否正确
（1）若天气凉快，小王就不去游泳。天气凉快，所 以小王没去游泳。 ③判断 ((PQ)P) Q是否为重言式 方法3：主析取范式法 ((PQ)P) Q = ((PQ)P)Q = (PQ) P Q = m11m0xmx0 = m11m00m01m00m10 = (0,1,2,3) = T ((PQP Q
(PQ(RS(PRQS 构造性二难
写出对应下面推理的证明
在大城市球赛中，如果北京队第三，那么如果上海队第 二，则天津队第四；沈阳队不是第一或北京队第三，上海队第 二。从而知：如果沈阳队第一，那么天津队第四。 解：设 (1) P (Q R) 前提 P：北京队第三 Q：上海队第二 (2) Q (P R) (1)置换 R：天津队第四 (3) Q 前提 S：沈阳队第一 (4) P R (2)(3)假言推理 前提：
P(QR)，S∨P, Q 结论： S R

1 2 k
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(4)构造证明法 构造证明法 当前提与结论中命题变项较多时，前几种方法 的工作量太大，不方便，而构造证明法较为方 便。构造证明法必须在给定的推理规则下进行。 常用的推理规则有以下11条： (1)前提引入规则：在证明的任何步骤上，都可 以引入前提。 (2)结论引入规则：在证明的任何步骤上，所得 中间结果都可以作为后继证明的前提。 (3)置换规则：在证明的任何步骤上的公式中的 子公式均可用与之等值的公式置换。
离散数学
Discrete Mathematics
Chen Guangxi
School of Mathematics and Computing Science
第二章 命题逻辑的推理理论
目标:
掌握推理形式结构 熟练运用构造推理方法 了解命题逻辑归结证明
学习建议:
与初中平面几何证明进行对比 勤做练习
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(8)假言三段论 ：
A→B B→C ∴A→C
(9)析取三段论规则： A∨ B A∨ B ¬A ¬B 或者 ∴B ∴A
Dr Chen Guangxi
第二章 命题逻辑的推理理论
(10)构造性二难推理规则：
A → B C → D A∨C ∴B∨ D
(11)合取引入规则：
A B ∴A∧ B
Dr Chen Guangxi
第二章 命题逻辑的推理理论
是重言式类似， 与用 A ⇔ B 表示 A ↔ B是重言式类似，用 A ⇒ B表示A → B 是重言式， 不是联结词 是重言式， ⇒ 符。 推出B的推理正确 的推理正确， 若 A , A ,⋯, A 推出 的推理正确，则记作 ( A1 ∧ A2 ∧ ⋯ ∧ Ak ) ⇒ B 为蕴涵式。 称A⇒B为蕴涵式。 ⇒ 为蕴涵式

6
程序解法：
#include "stdio.h" #include "conio.h" main() { int p,q,r,A1,A2,A3,B1,B2,B3,C1,C2,C3,E; for(p=0;p<=1;p++) for (q=0;q<=1;q++) for(r=0;r<=1;r++) { A1=!p&&q;A2=(!p&&!q)||(p&&q);A3=p&&!q; B1=p&&!q;B2=(p&&q)||(!p&&!q);B3=!p&&q; C1=!q&&r;C2=(q&&!r)||(!q&&r);C3=q&&r; E=(A1&&B2&&C3)||(A1&&B3&&C2)||(A2&&B1&&C3)||(A2&&B3&&C1)||(A3&&B1&&C2)||(A3 &&B2&&C1); if (E==1) printf("p=%d\tq=%d\tr=%d\n",p,q,r); } getch(); }
复合命题： E=(A1 ∧B2 ∧C3) ∨ (A1 ∧B3 ∧C2) ∨ (A2 ∧B1 ∧C3) ∨ (A2 ∧B3∧C1) ∨ (A3 ∧B1 ∧C2) ∨ (A3 ∧B2 ∧C1)
A1 ∧B2 ∧C3 = (p ∧q ) ∧ ((p ∧ q) ∨(p ∧ q) ) ∧(q ∧ r) 0 A1 ∧B3 ∧C2 = (p ∧q ) ∧ ( p ∧ q) ∧( (q ∧ r) ∨(q ∧ r ) ) p ∧q ∧ r A2 ∧B1 ∧C3 =A2 ∧B3∧C1 = A3 ∧B2 ∧C1 = 0 A3 ∧B1 ∧C2 p ∧ q ∧ r E (p ∧q ∧ r) ∨ (p ∧ q ∧ r) 所以王教授是上海人。