充分性: 若蕴涵式(A1∧A2∧…∧Ak)→B为重言式，则对于任何赋 值此蕴涵式均为真，因而不会出现前件为真后件为假 的情况，即在任何赋值下，或者A1∧A2∧…∧Ak为假， 或者A1∧A2∧…∧Ak和B同时为真，这正符合定义3.1中 推理正确的定义。 由此定理知，推理形式： 前提：A1,A2,…,Ak 结论：B 是有效的当且仅当(A1∧A2∧…∧Ak)→B为重言式。
以引入前提。
（2） 结论引入规则：在证明的任何步骤上所得 到的结论都可以作为后继证明的前提。 （3） 置换规则：在证明的任何步骤上，命题公 式中的子公式都可以用与之等值的公式置换，得到 公式序列中的又一个公式。
（4） 假言推理规则
（5） 附加规则：
（6） 化简规则：
（7） 拒取式规则：
（8） 假言三段论规则：
A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，
或者A1∧A2 ∧…∧Ak为假，或者当A1∧A2 ∧…∧Ak为 真时，B也为真，则称由前提A1,A2,…,Ak推出B的推 理是有效的或正确的，并称B是有效结论。 其中，前提是一个有限的公式集合，记为Г。 将由Г推B的推理记为Г├ B。 若推理是正确的，则记为Г B，否则记为Г B。
（9） 析取三段论规则：
（10） 构造性二难推理：
（11） 破坏性二难推理规则：
（12） 合取引入规则：
P中的证明就是由一组P中公式作为前提，利用P 中的规则，推出结论。当然此结论也为P中公式。
例3.3 在自然推理系统P中构造下面推理的证明： (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) 证明： ① p→s ② ┐s 前提引入
结论的否定 前提引入 前提引入 ②③析取三段 前提引人 ④⑤拒取式 ⑥置换 前提引入 ⑦⑧析取三段
由于最后一步q∧┐q 0，即
(((p∧q)→r)∧(┐r∨s)∧┐s∧p)∧q 0，所以推理正
确。 思考：不用归谬法证明例3.6
这是著名物理学家爱因斯坦出过的一道题： 一个土耳其商人，想找一个十分聪明的助手协助他经 商，有两个人前来应聘。这个商人为了试一试哪一个聪 明些，就把两个人带进一间漆黑的屋子里，他打开电灯 后说：“这张桌子上有五顶帽子、两顶是红色的，三顶 是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄 乱，然后我们三个人每人摸一顶帽子戴在头上，在我开 灯后，请你们尽快地说出自己头上戴的帽子是什么颜色 的。”说完之后，商人将电灯关掉，然后三人都摸了一 顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来， 接着把电灯打开。这时，那两个应试者看到商人头上戴 的是一顶红帽子，过了一会儿，其中一个人便喊到： “我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的?
定理3.1
命题公式A1,A2,…,Ak推B的推理正确当且仅当 (A1∧A2∧…∧Ak )→B 为重言式。
证： 必要性。 若A1,A2,…,Ak推B的推理正确，则对于A1,A2,…,Ak ,B 中所含命题变项的任意一组赋值，不会出现 A1∧A2∧…∧Ak为真，而B为假的情况，因而在任何赋 值下，蕴涵式(A1∧A2∧…∧Ak )→B均为真，故它为重 言式。
3.2
自然推理系统P
将推理用更严谨的形式推理系统描述出来。
定义3.2 一个形式系统 I 由下面四个部分组成： （1） 非空的字符表集，记作A(I)。 （2） A(I)中符号构造的合式公式集，记作E(I)。 （4） 推理规则集，记作R(I)。 可以将I记为 <A(I) , E(I) , AX(I) , R(I)>
P是一个自然推理系统，因而没有公理。故P只有三 个部分。 定义3.3 自然推理系统P定义如下：
1．字母表
（1） 命题变项符号：p，q，r，…,pi，qi，ri，…
（2） 联结词符号：┐,∧,∨,→,
（3） 括号和逗号：( , )，，
2．合式公式 同定义1.6
3．推理规则 （1） 前提引入规则：在证明的任何步骤上都可
例3.4 在自然推理系统P中构造下面推理的证明： 若数a是实数，则它不是有理数就是无理数；若a 不能表示成分数，则它不是有理数；a是实数且它不 能表示成分数。所以a是无理数。 解 首先将简单命题符号化： 设 p：a是实数。 q：a是有理数。 r：a是无理数。 s：a能表示成分数。 前提：p→(q∨r), ┐s→┐q, p∧┐s 结论：r
证明： ① p∧┐s ②p ③ ┐s ④ p→(q∨r) ⑤ q∨r ⑥ ┐s→┐q ⑦ ┐q ⑧r
前提引入 ①化简 ①化简 前提引入 ②④假言推理 前提引入 ③⑥假言推理 ⑤⑦析取三段论
P中证明的两个常用技巧： 1．附加前提证明法 2．归谬法 1、附加前提法 若推理的形式结构具有如下形式 （A1∧A2∧…∧Ak)→(A→B) （3.5）
证明：用附加前提证明法。 ①s ② ┐s∨p ③p ④ (p∧q)→r 附加前提引入 前提引入 ①②析取三段论 前提引入
⑤q
⑥ p∧q ⑦r
前提引入
③⑤合取 ④⑥假言推理
思考？ 不用附加前提证明法构造例3.5的证明。
2、归谬法 在构造形式结构为 (A1∧A2∧…∧Ak)→B
的推理证明中，如果将┐B作为前提能推出矛盾 来，比如说得出(A∧┐A)，则说明推理正确。
析取三段论
假言三段论 等价三段论
8. (A→B)∧(C→D)∧(A∨C) (B∨D) (A→B)∧(┐A→B)∧(A∨┐A) B 9. (A→B)∧(C→D)∧(┐B∨┐D) (┐A∨┐C)
构造性二难
构造性二难 (特殊形式 破坏性二难
说明：1. 九条推理定律是一个模式，对应多种不同形式； 2. 若一 个推理的形式结构与某条推理定律对应 的蕴含式一致，就可直接判定推理正确； 3. 24个等值式中的每一个都派生出两条推理定律。
（3） E(I)中一些特殊的公式组(I)>是I的形式语言系统，<AX(I) , R(I)>为 I的形式演算系统。
形式系统一般分为两类: 一类是自然推理系统，它的特点是从任意给定的前
提出发，应用系统中的推理规则进行推理演算，得到
的最后命题公式是推理的结论（有时称为有效的结论， 它可能是重言式，也可能不是）。 另一类是公理推理系统，它只能从若干给定的公理 出发，应用系统中推理规则进行推理演算，得到的 结论是系统中的重言式，称为系统中的定理。
第三章 命题逻辑的推理理论 3.1 推理的形式结构
前提（多个）
推理
结论
推理：从前提出发推出结论的思维过程。 前提：已知命题公式集合。 结论：从前提出发应用推理规则推出的命题公式。
要研究推理就应该给出推理的形式结构，为此，首 先应该明确什么样的推理是有效的或正确的。
定义3.1 设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 故推理正确。
例3.6 在自然推理系统P中构造下面推理的证明。
如果小张守第一垒并且小李向B队投球，则A队 将取胜；或者A队未取胜，或者A队获得联赛第一名； A队没有获得联赛的第一名；小张守第一垒。因此， 小李没有向B队投球。
┐((p ∨ q)∧ ┐ p ) ∨ q
┐ (p ∨ q) ∨ p ∨ q
1 所以，推理正确
（2） 若下午气温超过30℃，则王小燕必去游泳，若 她去游泳，她就不去看电影了。所以，若王小燕没去 看电影，下午气温必超过了30 ℃。
解： 设 p:下午气温超过30℃ r:王小燕去看电影 q:王小燕去游泳
例3.5 在自然推理系统P中构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影；小赵 不去看电影或小张去看电影；小王去看电影。所以， 当小赵去看电影时，小李也去看电影。 解: 将简单命题符号化： 设 p:小张去看电影。 q:小王去看电影。 r:小李去看电影。 s:小赵去看电影。 前提：(p∧q)→r,┐s∨p,q 结论：s→r
解 先将简单命题符号化。 设 p:小张守第一垒。 前提：(p∧q)→r,┐r∨s,┐s ,p q:小李向B队投球。 结论：┐q r:A队取胜。 s:A队获得联赛第一名。
前提：(p∧q)→r,┐r∨s,┐s ,p 结论：┐q ① q 证明：用归谬法 引入 ② ┐r∨s ③ ┐s ④ ┐r 论 ⑤ (p∧q)→r ⑥ ┐(p∧q) ⑦ ┐p∨┐q ⑧p ⑨ ┐q 论
判断下列推理是否正确：
(1){p,p→q} ┝ q (2){p,q→p} ┝ q 解： 只要写出前提的合取式与结论的真值表，看是否 出现前提合取式为真，而推论为假的情况。
3.1
(1)
推理的形式结构
由表可知，没有出现前提合取式为真，而结论为 {p,p→q} q
假的情况，因而(1)中推理正确，即
(2)由表可知，在赋值为1 0情况下，出现了前提合取 式为真，而结论为假的情况，因而(2)推理不正确，即 {p,q→p} q
(A1∧A2∧…∧Ak)→B称为上述推理的形式结构。从而推 理的有效性等价于它的形式结构为重言式。 于是，推理正确 {A1,A2,…,Ak}╞ B 可记为 A1∧A2∧…∧AkB 判断是否为重言式有三个方法： 1． 真值表法 2． 等值演算法 3． 主析取范式法
例3.2 判断下面推理是否正确： (1)下午马芳或去看电影或去游泳。她没去看电影。 所以，她去游泳了。 解： 设 p:马芳下午去看电影 q:马芳下午去游泳 前提：p∨q， ┓ p 结论：q 推理的形式结构： （（p ∨ q）∧ ┓p ）→q ((p ∨ q)∧ ┐ p )→q
此证明的序列长 ①②拒取式 为8，最后一步为推 理的结论，所以推理 前提引入 正确，r∧(p∨q)是有 ③④析取三段论 效结论。
前提引入
③ ┐p
④ p∨q
