命题逻辑II 范式与推理理论

1、11.4 范式范式 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 2析取范式与合取范式析取范式与合取范式 文字文字: : 单个命题变元或其否定式单个命题变元或其否定式简单析取式简单析取式: :有限个文字构成的析取式有限个文字构成的析取式1.1.包含有限个包含有限个( (可以是一个可以是一个) )析取项析取项 2.2.每个析取项是一个文字每个析取项是一个文字如如 p, q, pq, p q r, 简单合取式简单合取式: :有限个文字构成的合取式有限个文字构成的合取式1.1.包含有限个包含有限个( (可以是一个可以是一个) )合取项合取项 2.2.每个合取项是

2、一个文字每个合取项是一个文字如如 p, q, pq, p q r, 析取范式析取范式: :由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式: :由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是简单析取式简单析取式3析取范式与合取范式析取范式与合取范式( (续续) )范式范式: :析取范式与合取范式的总称析取范式与合取范式的总称 公式公式A的析取范式的析取范式: 与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式: 与与A等值

3、的合取范式等值的合取范式说明：说明： 单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式pq r, p qr既是析取范式，又是合取范式既是析取范式，又是合取范式(为什么为什么?) 4命题公式的范式命题公式的范式 定理定理 任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式. .求公求公式式A的范式的步骤：的范式的步骤： (1) 消去消去A中的中的, （若存在）（若存在） (2) 否定联结词否定联结词 的内移或消去的内移或消去 (3) 使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（

4、合取范式）公式的范式存在，但不惟一公式的范式存在，但不惟一5求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) A=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）6求公式的范式举例求公式的范式举例( (续续) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r

5、（消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德德 摩根律）摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成） 7极小项与极大项极小项与极大项 定义定义 在含有在含有n个命题变元的简单合取式个命题变元的简单合取式( (简单析取式简单析取式) )中，中，若每个命题变元均以文字的形式出现且仅出现一次，称这若每个命题变元均以文字的形式出现且仅出现一次，称这样的简单合取式样的简单合

6、取式( (简单析取式简单析取式) )为为极小项极小项( (极大项）极大项）.说明：说明： n个命题变元产生个命题变元产生2n个极小项和个极小项和2n个极大项个极大项 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值 在极小项和极大项中文字均按下标或字母顺序排列在极小项和极大项中文字均按下标或字母顺序排列 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十是该极小项成真赋值的十 进制表示进制表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成是该极大项成 假赋值的十进制表示假赋值的十进制表示, mi( (Mi) )称为极小项称为极小项( (

7、极大项极大项) )的名称的名称. mi与与Mi的关系的关系: : mi Mi , Mi mi 8极小项与极大项极小项与极大项( (续续) )由由p, q两个命题变元形成的极小项与极大项两个命题变元形成的极小项与极大项 公式公式 成真赋值成真赋值名称名称 公式公式 成假赋值成假赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项极小项 极大项极大项 9 由由p, q, r三个命题变元形成的极小项与极大项三个命题变元形成的极小项与极大项 极小项极小项 极大项极大项 公式

8、公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 10主析取范式与主合取范式主析取范式与主合取范式 主析取范式主析取范式: : 由极小项构成的析取范式由极小项构成的析取范式主

9、合取范式主合取范式: : 由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变元为命题变元为p, q, r时，时， ( pq r) ( p q r) m1 m3 是是主析取范式主析取范式 (p qr) ( p qr) M1 M5 是是主合取范式主合取范式 A的主析取范式的主析取范式: 与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 与与A等值的主合取范式等值的主合取范式. 11主析取范式与主合取范式主析取范式与主合取范式( (续续) )定理定理 任何命题公式都存在着与之等值的主析取范任何命题公式都存在着与之等值的主析取范式和主合取范式式和主合取范式

10、, 并且是唯一的并且是唯一的. . 用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤： (1) 先求析取范式（合取范式）先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等. (3) 极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按角标从小到大顺序排序按

11、角标从小到大顺序排序. 12求公式的主范式求公式的主范式例例 求公式求公式 A=(pq)r的主析取范式与主合的主析取范式与主合 取范式取范式. . (1) 求主析取范式求主析取范式 (pq)r (p q) r , （析取范式）（析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 13求公式的主范式求公式的主范式( (续续) ) r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入并排序，得代入并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式）主析取范式）

12、14求公式的主范式求公式的主范式( (续续) ) (2) 求求A的主合取范式的主合取范式 (pq)r (p r) (q r) , （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 15求公式的主范式求公式的主范式( (续续) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得代入并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式） 16主范式的用途主范式的用途与真值表相同与真值表相同 (1) 求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值 例如例如 (pq)r m1 m3 m5 m

13、6 m7， 其成真赋值为其成真赋值为001, 011, 101, 110, 111， 其余的赋值其余的赋值 000, 010, 100为为成假赋值成假赋值. 类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值. 17主范式的用途主范式的用途( (续续) ) (2) 判断公式的类型判断公式的类型 设设A含含n个命题变元，则个命题变元，则 A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合取范式含的主合取范式含2n个极大项个极大项A

14、为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项 18主范式的用途主范式的用途( (续续) )例例 用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值： p(qr) 与与 (p q)r p(qr) 与与 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7故中的两公式等值，而的不等值故中的两公

15、式等值，而的不等值. (3) 判断两个公式是否等值判断两个公式是否等值说明：说明： 由公式由公式A的主析取范式确定它的主合取范式，反之亦然的主析取范式确定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.19主范式的用途主范式的用途( (续续) )例例 某公司要从赵、钱、孙、李、周五名新毕业某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习的大学生中选派一些人出国学习. 选派必须满足选派必须满足以下条件：以下条件： (1)(1)若赵去，钱也去；若赵去，钱也去； (2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去； (3)(3)钱、孙两

16、人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人； (4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去； (5)(5)若周去，则赵、钱也去若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出国？试用主析取范式法分析该公司如何选派他们出国？20例例 (续续)解此类问题的步骤为：解此类问题的步骤为： 将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由中复合命题组成的合取式写出由中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 21例例 (续续)解解 设设p：派赵去，：派赵去，q：派钱去，：派钱去，r：派孙去，：派孙去， s：派李

17、去，：派李去，u：派周去：派周去. . (1) (pq) (2) (s u) (3) (qr) ( q r) (4) (r s) ( rs) (5) (u(p q) (1) (5)构成的合取式为构成的合取式为 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)22例例 (续续) A ( pq r su) (p qrs u)结论：由可知，结论：由可知，A的成真赋值为的成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）. . A的演算过程如下的演算过程

18、如下: : A ( p q) (qr) ( q r) (s u) ( u (p q) (r s) ( rs) （交换律（交换律) )B1= ( p q) (qr) ( q r) ( p qr) ( pq r) (qr) （分配律）（分配律）23例例 (续续) B2= (s u) ( u (p q) (su) (p q s) (p q u) （分配律）（分配律） B1 B2 ( p qr su) ( pq r su) (qr su) (p qr s) (p qr u)再令再令 B3 = (r s) ( rs)得得 A B1 B2 B3 ( pq r su) (p qrs u)注意：在以上演算中多

19、次用矛盾律注意：在以上演算中多次用矛盾律要求：自己演算一遍要求：自己演算一遍 241.5 联结词完备集定义定义 设设S是一个联结词集合是一个联结词集合, 如果任何如果任何n(n 1) 元真值元真值函数都可以由仅含函数都可以由仅含S中的联结词构成的公式表示中的联结词构成的公式表示, ,则称则称S是是联结词完备集联结词完备集定理定理 下述联结词集合都是完备集下述联结词集合都是完备集:(1) S1= , , , , (2) S2= , , , (3) S3= , , (4) S4= , (5) S5= , (6) S6= , AB (AB) (BA)AB A BA B (A B) ( AB)A B

20、( AB)A B ( A) B AB251.6 推理理论推理理论 推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法推理定律与推理规则推理定律与推理规则构造证明构造证明 直接证明法直接证明法, 附加前提证明法附加前提证明法, 归缪法归缪法 26推理的形式结构推理的形式结构问题的引入问题的引入 蕴涵命题构成了一个推理关系蕴涵命题构成了一个推理关系: (1) 若学习委员是甲和乙中的某个而且乙不是学习若学习委员是甲和乙中的某个而且乙不是学习委员，则甲是学习委员委员，则甲是学习委员. (2) 若若A C B D，则，则A B或或C D.上面上面(1)是正确的推理，而是正确的推理，

21、而(2)是错误的推理是错误的推理. 推理推理: 从前提出发推出结论的思维过程从前提出发推出结论的思维过程证明证明: 具体给出推理的步骤，通过每一步的正确性具体给出推理的步骤，通过每一步的正确性（以推理定律为依据）说明整个推理是正确的（以推理定律为依据）说明整个推理是正确的. 27从命题符号化到推理符号化从命题符号化到推理符号化推理的形式结构推理的形式结构: A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 结论：结论： B 若推理正确，则记作：若推理正确，则记作：A1 A2 AkB.28推理的正确性推理的正确性定义定义 若对于每组赋值，若对于每组赋值， A1 A2 AkB均为真

22、均为真, 则则称由称由A1,A2, , Ak到到B的的推理正确推理正确, 否则否则推理不正确推理不正确（错误）（错误）.“A1, A2, , Ak 推推B” 的推理正确的推理正确 当且仅当当且仅当 A1 A2 AkB为重言式，即为重言式，即A1 A2 AkB. 需要注意的是：需要注意的是：1.当当A1 A2 Ak永假时，上述推理总是正确的。永假时，上述推理总是正确的。2.正确的推理具体化以后，会出现某些正确的推理具体化以后，会出现某些“蕴涵怪蕴涵怪论论”，例如，例如(p(q r) ( (pq)(pr) , ,令令p表示表示“火车行驶在沪杭线上火车行驶在沪杭线上”，q表示表示“火车驶往上火车驶往

23、上海海”，而，而r表示表示“火车驶往杭州火车驶往杭州”，所得推理在自，所得推理在自然语言中很怪异然语言中很怪异( (前提是对的，而结论的析取式，前提是对的，而结论的析取式，两个析取项都不对两个析取项都不对) )。其实并不奇怪，这都是因为命题逻辑对因果联系进行其实并不奇怪，这都是因为命题逻辑对因果联系进行真值抽象，并使用由此得到的蕴涵联系，只需注意真值抽象，并使用由此得到的蕴涵联系，只需注意 对于对于1 1，应慎用从假前提开始的推理，注意其应用，应慎用从假前提开始的推理，注意其应用中的意义，不进行那些没有意义的推理。中的意义，不进行那些没有意义的推理。 对于对于2 2，要注意抽象研究的结论返回具

24、体问题时，要注意抽象研究的结论返回具体问题时，要按照当初抽象的方式进行应用。要按照当初抽象的方式进行应用。对推理正确性定义的补充说明对推理正确性定义的补充说明30判断推理是否正确的方法判断推理是否正确的方法真值表法真值表法等值演算法等值演算法 判断推理是否正确判断推理是否正确主析取范式法主析取范式法构造证明法构造证明法 证明推理正确证明推理正确 说明：用前说明：用前3 3个方法时采用个方法时采用形式结构形式结构 “ A1 A2 AkB” . 用构造证明时用构造证明时, 采用采用 “前提前提: A1, A2, , Ak, 结论结论: B”. 31实例实例例例 判断下面推理是否正确判断下面推理是否

25、正确 (1) 若今天是若今天是1号，则明天是号，则明天是5号号. 今天是今天是1号号. 所所 以明天是以明天是5号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. 推理的形式结构为推理的形式结构为: (pq) pq证明（用等值演算法）证明（用等值演算法） (pq) pq ( p q) p) q pq q 1得证推理正确得证推理正确 32实例实例 (续续)(2) 若今天是若今天是1号，则明天是号，则明天是5号号. 明天是明天是5号号. 所以今天是所以今天是1号号. 解解 设设p：今天是：今天是1号，号，q：明天是：明天是5号号. 推理的形式结构为推理的形式结构为: (pq

26、) qp 证明（用主析取范式法）证明（用主析取范式法） (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 结果不含结果不含m1, 故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确. 33推理正确性的证明：推理定律推理正确性的证明：推理定律重要的推理定律重要的推理定律重言蕴涵式重言蕴涵式 A (A B) 附加律附加律 (A B) A 化简律化简律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段论析取三段论 (AB) (BC) (AC) 假言三段论假言三段论 (

27、AB) (BC) (AC) 等价三段论等价三段论 (AB) (CD) (A C) (B D) 构造性二难构造性二难 34推理定律推理定律 (续续)(AB) ( AB) B 构造性二难（特殊形式）构造性二难（特殊形式）(AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难证明证明: :描述推理过程的命题公式序列，其中每个命描述推理过程的命题公式序列，其中每个命题公式或者是已知的前提，或者是由前面的命题题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论公式应用推理规则得到的结论. .35推理规则推理规则 (1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(

28、3) 置换规则置换规则(4) 假言推理规则假言推理规则 AB A B(5) 附加规则附加规则 A A B (6) 化简规则化简规则 A B A (7) 拒取式规则拒取式规则 AB B A(8) 假言三段论规则假言三段论规则 AB BC AC 36推理规则推理规则( (续续) ) (11) 破坏性二难推理破坏性二难推理规则规则 AB CD BD AC(12) 合取引入规则合取引入规则 A B A B (9) 析取三段论规则析取三段论规则 A B B A (10)构造性二难推理构造性二难推理规则规则 AB CD A C B D37构造证明之一构造证明之一直接证明法直接证明法例例 构造下面推理的证明

29、：构造下面推理的证明： 若明天是星期一或星期三，我就有课若明天是星期一或星期三，我就有课. 若有课，若有课，今天必备课今天必备课. 我今天没备课我今天没备课. 所以，所以， 明天不是星期一和星期三明天不是星期一和星期三. 解解 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我明天有课，：我明天有课，s：我今天备课：我今天备课推理的形式结构为推理的形式结构为 前提：前提：(p q)r, rs, s 结论：结论： pq 证明：证明： 如果我明天有课，今天一定备课如果我明天有课，今天一定备课 今天我没有备课今天我没有备课 我明天没课我明天没课 若明天是星期一或星期三，我就有课若明天是星期一或星期三，我就有课 并非明天是星期一或星期三并非明天是星期一或星期三 明天不是周一，明天也不是周三明天不是周一，明天也不是周三 推理过程及其符号化：自然语言推理过程推理过程及其符号化：自然语言推理过程 39推理过程及其符号化：形式证明推理过程及其符号化：形式证明证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置换置换40构造证明之二构造证