1
1.6 命题逻辑的推理理论
?推理的形式结构
?判断推理是否正确的方法
?推理定律与推理规则
?构造证明法
2
推理的形式结构 — 问题的引入
推理举例,
(1) 正项级数收敛当且仅当部分和上有界,
(2) 若 A?C?B?D,则 A?B且 C?D,
推理, 从前提出发推出结论的思维过程
上面 (1)是正确的推理, 而 (2)是错误的推理,
证明, 描述推理正确或错误的过程,
3
推理的形式结构
定义 若对于每组赋值, A1?A2?… ? Ak 均为假, 或
当 A1?A2?… ?Ak为真时,B也为真,则称由 A1,A2,…,Ak
推 B的 推理正确,否则 推理不正确 （ 错误 ）,
“A1,A2,…,Ak 推 B” 的推理正确
当且仅当 A1?A2?… ?Ak?B为重言式,
推理的形式结构, A1?A2?… ?Ak?B 或
前提,A1,A2,…,Ak
结论,B
若推理正确，则记作,A1?A2?… ?Ak?B,
4
判断推理是否正确的方法
?真值表法
?等值演算法
?主析取范式法
?构造证明法
说明：当命题变项比较少时，用前 3个方法比较方
便,此时采用 形式结构,A1?A2?… ?Ak?B”, 而在
构
造证明时,采用,前提, A1,A2,…,Ak,结论, B”,
5
实例
例 判断下面推理是否正确
(1) 若今天是 1号, 则明天是 5号, 今天是 1号, 所
以明天是 5号,
解 设 p：今天是 1号, q：明天是 5号,
证明的形式结构为, (p?q)?p?q
证明 （ 用等值演算法 ）
(p?q)?p?q
? ?((?p?q)?p)?q
? ?p??q?q ? 1
得证推理正确
6
实例 (续 )
(2) 若今天是 1号, 则明天是 5号, 明天是 5号, 所以今天是 1号,
解 设 p：今天是 1号, q：明天是 5号,
证明的形式结构为, (p?q)?q?p
证明 （ 用主析取范式法 ）
(p?q)?q?p
? (?p?q)?q?p
? ? ((?p?q)?q)?p
? ?q?p
? (?p??q)?(p??q)? (p??q)?(p?q)
? m0?m2?m3
结果不含 m1,故 01是成假赋值，所以推理不正确,
7
推理定律 —— 重言蕴涵式
重要的推理定律
A ? (A?B) 附加律
(A?B) ? A 化简律
(A?B)?A ? B 假言推理
(A?B)??B ? ?A 拒取式
(A?B)??B ? A 析取三段论
(A?B)?(B?C) ? (A?C) 假言三段论
(A?B)?(B?C) ? (A?C) 等价三段论
(A?B)?(C?D)?(A?C) ? (B?D) 构造性二难
8
推理定律 (续 )
(A?B)?(?A?B)?(A??A) ? B
构造性二难 （ 特殊形式 ）
(A?B)?(C?D)?( ?B??D) ? (?A??C)
破坏性二难
说明,
A,B,C为元语言符号
若某推理符合某条推理定律, 则它自然是正确的
A?B产生两条推理定律, A ? B,B ? A
9
推理规则
(1) 前提引入规则
(2) 结论引入规则
(3) 置换规则
(4) 假言推理规则
A?B
A
\ B
(5) 附加规则
A
\A?B
(6) 化简规则
A?B
\A
(7) 拒取式规则
A?B
?B
\?A
(8) 假言三段论规则
A?B
B?C
\A?C
10
推理规则 (续 )
(11) 破坏性二难推理
规则
A?B
C?D
?B??D
\?A??C
(12) 合取引入规则
A
B
\A?B
(9) 析取三段论规则
A?B
?B
\A
(10)构造性二难推理
规则
A?B
C?D
A?C
\B?D
11
构造证明 —— 直接证明法
例 构造下面推理的证明,
若明天是星期一或星期三，我就有课, 若有课，
今天必备课, 我今天下午没备课, 所以,
明天不是星期一和星期三,
解 设 p：明天是星期一, q：明天是星期三,
r：我有课, s：我备课
形式结构为
前提,(p?q)?r,r?s,?s
结论,?p??q
12
直接证明法 (续 )
证明
① r?s 前提引入
② ?s 前提引入
③ ?r ①② 拒取式
④ (p?q)?r 前提引入
⑤ ?(p?q) ③④ 拒取式
⑥ ?p??q ⑤ 置换
13
构造证明 —— 附加前提证明法
欲证明
前提,A1,A2,…,Ak
结论,C?B
等价地证明
前提,A1,A2,…,Ak,C
结论,B
理由,(A1?A2?… ?Ak)?(C?B)
? ?( A1?A2?… ?Ak)?(?C?B)
? ?( A1?A2?… ?Ak?C)?B
? (A1?A2?… ?Ak?C)?B
14
附加前提证明法 (续 )
2
2
2
例 构造下面推理的证明,
2是素数或合数, 若 2是素数, 则 是无理数,
若 是无理数, 则 4不是素数, 所以, 如果 4是
素数, 则 2是合数,
用附加前提证明法构造证明
解 设 p,2是素数, q,2是合数,
r,是无理数, s,4是素数
形式结构
前提,p?q,p?r,r??s
结论,s?q
15
附加前提证明法 (续 )
证明
① s 附加前提引入
② p?r 前提引入
③ r??s 前提引入
④ p??s ②③ 假言三段论
⑤ ?p ①④ 拒取式
⑥ p?q 前提引入
⑦ q ⑤⑥ 析取三段论
请用直接证明法证明之
16
构造证明 —— 归谬法（反证法）
欲证明
前提,A1,A2,…,Ak
结论,B
将 ?B加入前提, 若推出矛盾, 则得证推理正确,
理由,
A1?A2?… ?Ak?B
? ?(A1?A2?… ?Ak)?B
? ?(A1?A2?… ?Ak??B)
括号内部为矛盾式当且仅当 (A1?A2?… ?Ak?B)为
重言式
17
归谬法 (续 )
例 构造下面推理的证明
前提,?(p?q)?r,r?s,?s,p
结论,?q
证明 （ 用归缪法 ）
① q 结论否定引入
② r?s 前提引入
③ ?s 前提引入
④ ?r ②③ 拒取式
18
归谬法 (续 )
⑤ ?(p?q)?r 前提引入
⑥ ?(p?q) ④⑤ 析取三段论
⑦ ?p??q ⑥ 置换
⑧ ?p ①⑦ 析取三段论
⑨ p 前提引入
⑩ ?p?p ⑧⑨ 合取
请用直接证明法证明之
1.6 命题逻辑的推理理论
?推理的形式结构
?判断推理是否正确的方法
?推理定律与推理规则
?构造证明法
2
推理的形式结构 — 问题的引入
推理举例,
(1) 正项级数收敛当且仅当部分和上有界,
(2) 若 A?C?B?D,则 A?B且 C?D,
推理, 从前提出发推出结论的思维过程
上面 (1)是正确的推理, 而 (2)是错误的推理,
证明, 描述推理正确或错误的过程,
3
推理的形式结构
定义 若对于每组赋值, A1?A2?… ? Ak 均为假, 或
当 A1?A2?… ?Ak为真时,B也为真,则称由 A1,A2,…,Ak
推 B的 推理正确,否则 推理不正确 （ 错误 ）,
“A1,A2,…,Ak 推 B” 的推理正确
当且仅当 A1?A2?… ?Ak?B为重言式,
推理的形式结构, A1?A2?… ?Ak?B 或
前提,A1,A2,…,Ak
结论,B
若推理正确，则记作,A1?A2?… ?Ak?B,
4
判断推理是否正确的方法
?真值表法
?等值演算法
?主析取范式法
?构造证明法
说明：当命题变项比较少时，用前 3个方法比较方
便,此时采用 形式结构,A1?A2?… ?Ak?B”, 而在
构
造证明时,采用,前提, A1,A2,…,Ak,结论, B”,
5
实例
例 判断下面推理是否正确
(1) 若今天是 1号, 则明天是 5号, 今天是 1号, 所
以明天是 5号,
解 设 p：今天是 1号, q：明天是 5号,
证明的形式结构为, (p?q)?p?q
证明 （ 用等值演算法 ）
(p?q)?p?q
? ?((?p?q)?p)?q
? ?p??q?q ? 1
得证推理正确
6
实例 (续 )
(2) 若今天是 1号, 则明天是 5号, 明天是 5号, 所以今天是 1号,
解 设 p：今天是 1号, q：明天是 5号,
证明的形式结构为, (p?q)?q?p
证明 （ 用主析取范式法 ）
(p?q)?q?p
? (?p?q)?q?p
? ? ((?p?q)?q)?p
? ?q?p
? (?p??q)?(p??q)? (p??q)?(p?q)
? m0?m2?m3
结果不含 m1,故 01是成假赋值，所以推理不正确,
7
推理定律 —— 重言蕴涵式
重要的推理定律
A ? (A?B) 附加律
(A?B) ? A 化简律
(A?B)?A ? B 假言推理
(A?B)??B ? ?A 拒取式
(A?B)??B ? A 析取三段论
(A?B)?(B?C) ? (A?C) 假言三段论
(A?B)?(B?C) ? (A?C) 等价三段论
(A?B)?(C?D)?(A?C) ? (B?D) 构造性二难
8
推理定律 (续 )
(A?B)?(?A?B)?(A??A) ? B
构造性二难 （ 特殊形式 ）
(A?B)?(C?D)?( ?B??D) ? (?A??C)
破坏性二难
说明,
A,B,C为元语言符号
若某推理符合某条推理定律, 则它自然是正确的
A?B产生两条推理定律, A ? B,B ? A
9
推理规则
(1) 前提引入规则
(2) 结论引入规则
(3) 置换规则
(4) 假言推理规则
A?B
A
\ B
(5) 附加规则
A
\A?B
(6) 化简规则
A?B
\A
(7) 拒取式规则
A?B
?B
\?A
(8) 假言三段论规则
A?B
B?C
\A?C
10
推理规则 (续 )
(11) 破坏性二难推理
规则
A?B
C?D
?B??D
\?A??C
(12) 合取引入规则
A
B
\A?B
(9) 析取三段论规则
A?B
?B
\A
(10)构造性二难推理
规则
A?B
C?D
A?C
\B?D
11
构造证明 —— 直接证明法
例 构造下面推理的证明,
若明天是星期一或星期三，我就有课, 若有课，
今天必备课, 我今天下午没备课, 所以,
明天不是星期一和星期三,
解 设 p：明天是星期一, q：明天是星期三,
r：我有课, s：我备课
形式结构为
前提,(p?q)?r,r?s,?s
结论,?p??q
12
直接证明法 (续 )
证明
① r?s 前提引入
② ?s 前提引入
③ ?r ①② 拒取式
④ (p?q)?r 前提引入
⑤ ?(p?q) ③④ 拒取式
⑥ ?p??q ⑤ 置换
13
构造证明 —— 附加前提证明法
欲证明
前提,A1,A2,…,Ak
结论,C?B
等价地证明
前提,A1,A2,…,Ak,C
结论,B
理由,(A1?A2?… ?Ak)?(C?B)
? ?( A1?A2?… ?Ak)?(?C?B)
? ?( A1?A2?… ?Ak?C)?B
? (A1?A2?… ?Ak?C)?B
14
附加前提证明法 (续 )
2
2
2
例 构造下面推理的证明,
2是素数或合数, 若 2是素数, 则 是无理数,
若 是无理数, 则 4不是素数, 所以, 如果 4是
素数, 则 2是合数,
用附加前提证明法构造证明
解 设 p,2是素数, q,2是合数,
r,是无理数, s,4是素数
形式结构
前提,p?q,p?r,r??s
结论,s?q
15
附加前提证明法 (续 )
证明
① s 附加前提引入
② p?r 前提引入
③ r??s 前提引入
④ p??s ②③ 假言三段论
⑤ ?p ①④ 拒取式
⑥ p?q 前提引入
⑦ q ⑤⑥ 析取三段论
请用直接证明法证明之
16
构造证明 —— 归谬法（反证法）
欲证明
前提,A1,A2,…,Ak
结论,B
将 ?B加入前提, 若推出矛盾, 则得证推理正确,
理由,
A1?A2?… ?Ak?B
? ?(A1?A2?… ?Ak)?B
? ?(A1?A2?… ?Ak??B)
括号内部为矛盾式当且仅当 (A1?A2?… ?Ak?B)为
重言式
17
归谬法 (续 )
例 构造下面推理的证明
前提,?(p?q)?r,r?s,?s,p
结论,?q
证明 （ 用归缪法 ）
① q 结论否定引入
② r?s 前提引入
③ ?s 前提引入
④ ?r ②③ 拒取式
18
归谬法 (续 )
⑤ ?(p?q)?r 前提引入
⑥ ?(p?q) ④⑤ 析取三段论
⑦ ?p??q ⑥ 置换
⑧ ?p ①⑦ 析取三段论
⑨ p 前提引入
⑩ ?p?p ⑧⑨ 合取
请用直接证明法证明之
