离散数学-第1章-命题逻辑省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,离散数学,授课教师：仝允战,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第一章 命题逻辑,（,Proposition Logic）,命题符号化及联结词,命题公式及分类,等值演算,联结词全功效集,对偶与范式,推理理论,1,2,3,4,5,6,1/81,介绍,逻辑学：,研究推理一门学科,数理逻辑：,用数学方法研究推理一门数学学科,一套符号体系+一组规则,2/81,2,介绍,数理逻辑内容：,古典数理逻辑：,命题逻辑、谓词逻辑,当代数理逻辑：,逻辑演算、公理化集合论、递归论、模型论、证实论,3/81,3,命题逻辑,命题(,Proposition),：,一个有确定真或假意义语句。,命题符号化及联结词,1,4/81,4,EXAMPLE 1,以下句子都是命题：,1.华盛顿是美国首都。,2.多伦多是加拿大首都。,3.1+1=2。,4.2+2=3。,命题1和3是真命题，2和4是假命题。,命题符号化及联结词,5/81,5,命题符号化及联结词,EXAMPLE 2,考虑以下句子：,1.现在几点了？,2.认真阅读一下。,3.,x+1=2.,4.x+y=z.,句子1和2不是命题，因为它们都不是陈说句。,句子3和4不是命题，因为,x，y,和,z,值不确定，使得它们真值都不唯一。,6/81,6,命题语句形式：,陈说句,非命题语句：,疑问句、命令句、感叹句、,非命题陈说句：悖论语句（真值不唯一）,命题符号化及联结词,7/81,7,命题符号表示：,大小写英文字母：,P、Q、R、,p、q、r,命题真值(,Truth Values),表示：,真：,T、1,假：,F、0,命题符号化及联结词,8/81,8,命题语句真值确定几点说明：,1、时间性,2、区域性,3、标准性,命题真值间关系表示：,真值表(,Truth Table),命题符号化及联结词,9/81,9,DEFINITION 1.,设,p,为任一命题，复合命题“非,p”（,或“,p,否定”）称为,p,否定式,。记作,p。,为,否定联结词,。真值表见,Table 1。,(,Let p be a proposition.The statement “It is not the case that p.”is another proposition,called the negation of p.The negation of p is denoted by,p.The proposition,p is read“not p.”,),p,否定,命题符号化及联结词,10/81,10,Table 1,Table1,否定命题真值表,p,p,1,0,0,1,命题符号化及联结词,11/81,11,EXAMPLE 3,设,p,表示“今天是星期五”，则,p,表示“今天不是星期五”。,显然，当,p,真值为0时，,p,真值为1。,命题符号化及联结词,12/81,12,命题符号化及联结词,设,p，q,为两命题，复合命题“,p,而且,q”（,或“,p,和,q”）,称作,p,与,q,合取式,。记作,pq。,为,合取联结词,。真值表见,Table 2。,(,Let,p and q be propositions.The proposition p and q,denoted by p,q,is the proposition that is true when both p and q are true and is false otherwise.The proposition p,q is called the conjunction of p and q.,),p,和,q,合取,DEFINITION 2.,13/81,13,命题符号化及联结词,Table 2,Table2,两个命题合取真值表,p q,p q,0 0,0 1,1 0,1 1,0,0,0,1,14/81,14,EXAMPLE 4,用,p,表示命题“今天是星期五”，,q,表示命题“今天下雨”，则命题,p,与,q,合取式是什么？,解答：,p,与,q,合取式,pq,是“今天是星期五，而且今天下雨。”假如是星期五，又下雨，则该命题为真；假如是除星期五外任意一天，或者虽是星期五但没下雨，则该命题为假。,命题符号化及联结词,15/81,15,命题符号化及联结词,设,p，q,为两命题，复合命题“,p,或,q”,称作,p,与,q,析取式,。记作,pq。,为,析取联结词,。真值表见,Table 3。,(,Let p and q be propositions.The proposition p or q,denoted by p,q,is the proposition that is false when p and q are both false and true otherwise.The proposition p,q is called the disjunction of p and q.,),p,和,q,析取,DEFINITION 3.,16/81,16,命题符号化及联结词,Table 3,Table3,两个命题析取真值表,p q,p q,0 0,0 1,1 0,1 1,0,1,1,1,17/81,17,还是以,Example 4,为例，命题,p,与,q,析取式是什么？,解答：,p,与,q,析取式,pq,是“今天是星期五或今天下雨。”只有今天既不是星期五，又没有下雨，则该命题为假；假如今天是星期五或者今天下雨了（包含下雨星期五），则该命题就为真。,EXAMPLE 5,命题符号化及联结词,18/81,18,命题符号化及联结词,设,p，q,为两命题，复合命题“假如,p，,则,q”,称作,p,与,q,蕴含式,。记作,pq。,称,p,为蕴含式,前件,(,hypothesis)，q,为蕴含式,后件,(,conclusion)。,称作,蕴含联结词,。真值表见,Table 4。,(,Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise.,),假如,p,，则,q,单条件，蕴涵,p：,前提,q：,结论,DEFINITION 4.,19/81,19,命题符号化及联结词,Table 4,Table4,蕴含式p q真值表,p q,p q,0 0,0 1,1 0,1 1,1,1,0,1,20/81,20,命题符号化及联结词,用,p,表示命题“天下雨”，用,q,表示命题“我骑自行车上班”，将以下命题符号化：,（1）只要不下雨，我就骑自行车上班。,（2）只有不下雨，我才骑自行车上班。,解答：,（1）中，,p,是,q,充分条件，因而符号化为,pq；（2）,中，,p,是,q,必要条件，因而符号化为,q p。,EXAMPLE 6,21/81,21,命题符号化及联结词,设,p，q,为两命题，复合命题“,p,当且仅当,q”,称作,p,与,q,等价式,。记作,p,q，,称作,等价联结词,。真值表见,Table 5。,(,Let p and q be propositions,The biconditional p,q is the proposition that is true when p and q have the same truth values and is false otherwise.,),p,当且仅当,q,双条件，等价,DEFINITION 5.,22/81,22,命题符号化及联结词,Table 5,Table5,等价式p q真值表,p q,p q,0 0,0 1,1 0,1 1,1,0,0,1,23/81,23,命题符号化及联结词,将下一命题符号化：,“,只有（仅当）,你是计算机科学系学生或者你不是新生，你才能够经过校园网上,Internet。”,解答：,a (cf),EXAMPLE 7,c,f,a,24/81,24,将下一命题符号化：,“假如你身高小于4英尺，你就不能乘坐过山车，除非你超出了16岁。”,解答：,(1)(,r s)q.,(2)s(r q).,EXAMPLE 8,r,q,s,假如你身高小于4英尺，而且你不超出16岁，那么你就不能乘坐过山车。,假如你不超出16岁，那么当你身高小于4英尺时，你就不能乘坐过山车。,命题符号化及联结词,25/81,25,命题符号化及联结词,“说离散数学是枯燥无味或毫无价值，那是不正确。”,p：,离散数学是有味道；,q：,离散数学是有价值；,EXAMPLE 9,符号化为：(,p q),26/81,26,命题逻辑,命题公式及分类,2,P、Q、R,称为,原子命题,(,Atomic Proposition)。,原子命题或加上逻辑联结词组成表示式成为,复合命题,(,Compositional Proposition)。,从,命题常量,到,命题变量,(,Propositional Variable),命题公式：,1.原子命题是命题公式；,2.设,P,是命题公式，则,P,也是命题公式；,3.设,P、Q,是命题公式，则(,PQ)、(PQ)、(PQ)、(P,Q),也是命题公式；,4.有限次地使用1、2、3所得到也是命题公式。,Proposition Formulas,Well-Formed Formulas(wff),27/81,27,命题公式及分类,命题公式运算规则：,逻辑联接词优先级：,、,命题公式表示式运算规律：,同代数表示式,命题公式运算方法：,全部公式中命题变量用指定命题（真值）代入（或指派），得到一个公式对应真值。,性质1：,假如一个命题公式有,n,个互异命题变量，则命题公式对应真值有2,n,种可能分布。,28/81,28,命题公式及分类,EXAMPLE 10,求以下命题公式真值表：,（1）,p (q r).,Table6,p(q r)真值表,p q r,r,q r,p (q r),0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,29/81,29,命题公式及分类,EXAMPLE 10,求以下命题公式真值表：,（2）(,p(pq)q.,Table7,(p(pq)q 真值表,p q,pq,p(pq),(,p(pq)q,0 0,0 1,1 0,1 1,1,1,0,1,0,0,0,1,1,1,1,1,30/81,30,命题公式及分类,EXAMPLE 10,求以下命题公式真值表：,（3）(,pq)q.,Table8,(pq)q 真值表,p q,pq,(,pq),(,pq)q,0 0,0 1,1 0,1 1,1,1,0,1,0,0,1,0,0,0,0,0,31/81,31,命题公式及分类,永真式,(,Tautology),：,公式中命题变量不论怎样代入，公式对应真值恒为1。,永假式,(,Contradiction),：,公式中命题变量不论怎样代入，公式对应真值恒为0。,可满足式,(,Satisfaction),：,公式中命题变量不论怎样代入，公式对应真值总有一个情况为1。,普通命题公式,(,Contingency),：,既不是永真公式也不是永假公式。,32/81,32,命题公式及分类,性质2：,（1）设,P,是永真命题公式，则,P,否定公式是永假命题公式；,（2）设,P,是永假命题公式，则,P,否定公式是永真命题公式；,（3）设,P、Q,是永真命题公式，则(,PQ)、(PQ)、(PQ)、(P,Q),也是永真命题公式。,33/81,33,命题公式及分类,小 结,1.命题概念：定义、逻辑值、符号化表示,2.从简单命题到复合命题：,逻辑联接词：运算方法、运算优先级,3.从命题常量到命题变量，,从复合命题到命题公式：,命题公式真值描述：真值表,4.命题公式分类：,永真公式、永假公式、可满足公式、普通公式,34/81,34,Propositional Equivalences,设,A，B,为两命题公式，若等价式,A,B,是重言式，则称,A,与,B,是,等值,。记作,A,B。,(,The propositions A and B are called logically equivalent if A,B is a tautology.The notation A,B denotes that A and B are logically equivalent.,),逻辑等值，或逻辑等价,DEFINITION 6.,命题逻辑,等值演算,3,35/81,35,证实(,pq),与,pq,是等值。,（这个等值关系是德摩根(,De Morgan),定律之一。德摩根是十九世纪中叶英国数学家。）,解答：真值表见,Table 9。,因为对于,p,和,q,全部可能组合，(,pq),和,pq,真值都相同，所以这两个命题是等值。,EXAMPLE 11,等值演算,36/81,36,Table 9,Table9,(pq)与pq真值表,p q,pq,(,pq),p,q,pq,0 0,0 1,1 0,1 1,0,1,1,1,1,0,0,0,1,1,0,0,1,0,1,0,1,0,0,0,等值演算,37/81,37,证实,pq,与,p q,是等值。,解答：真值表见,Table 10。,因为对于,p,和,q,全部可能组合，,pq,和,pq,真值都相同，所以这两个命题是等值。,EXAMPLE 12,等值演算,38/81,38,Table 10,Table10,pq与pq 真值表,p q,pq,p,pq,0 0,0 1,1 0,1 1,1,1,0,1,1,1,0,0,1,1,0,1,等值演算,39/81,39,证实,p(qr),与(,pq)(pr),是等值。,（分配律）,解答：真值表见,Table 11。,因为对于,p、q,和,r,全部可能组合，,p(qr),和(,pq)(pr),真值都相同，所以这两个命题是等值。,EXAMPLE 13,等值演算,40/81,40,Table 11,Table11,p(qr)与(pq)(pr)真值表,p q r,q r,p(qr),pq,pr,(,pq)(pr),0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,1,等值演算,41/81,41,下面给出,24个主要等值式,（祥见,P9）：,双重否定律、等幂律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。,依据已知等值式，推演出另外一些等值式过程称为,等值演算,。在进行等值演算时，往往用到,置换规则,。,等值演算,42/81,42,证实(,p(pq),与,pq,是等值。,EXAMPLE 14,0,0,等值演算,43/81,43,证实(,pq)(pq),是重言式。,EXAMPLE 15,1,1,1,等值演算,44/81,44,判断命题公式逻辑等价方法：,1.真值表,2.命题公式演算,基本等值定理；,公式代入不变性（置换规则）；,等值关系传递性。,等值演算,45/81,45,命题公式逻辑等价关系应用：,1、判定是否逻辑等价（等值）；,2、判断是否为永真公式或永假公式；,3、命题公式化简。,等值演算,46/81,46,设,p,q,为两命题，复合命题“,p,q,之中恰有一个成立”称为,p,与,q,排斥或,或,异或,。记作,p q，,称作,排斥或,或,异或联结词,。,真值表见,Table 12。,(,Let p and q be propositions.The exclusive or of p and q,denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwise.,),p,和,q,异或,DEFINITION 7.,命题逻辑,联结词全功效集,4,47/81,47,Table 12,联结词全功效集,0,1,1,0,0 0,0 1,1 0,1 1,p,q,p q,Table12,异或,p,q,真值表,p,q,(p q)(pq),48/81,48,设,p,q,为两命题，复合命题“,p,与,q,否定”称为,p,与,q,与非式,。记作,pq，,称作,与非联结词,。,真值表见,Table 13。,(,Let p and q be propositions.The and not of p and q,denoted by p,q,is the proposition that is false when p and q are both true and true otherwise.,),p,和,q,与非,DEFINITION 8.,联结词全功效集,49/81,49,Table 13,Table13,与非式pq真值表,p q,p,q,0 0,0 1,1 0,1 1,1,1,1,0,p,q,(pq),联结词全功效集,50/81,50,设,p,q,为两命题，复合命题“,p,或,q,否定”称为,p,与,q,或非式,。记作,pq，,称作,或非联结词,。,真值表见,Table 14。,(,Let p and q be propositions.The or not of p and q,denoted by p,q,is the proposition that is true when p and q are both false and false otherwise.,),p,和,q,或非,DEFINITION 9.,联结词全功效集,51/81,51,Table 14,Table14,与非式pq真值表,p q,p,q,0 0,0 1,1 0,1 1,1,0,0,0,p,q,(pq),联结词全功效集,52/81,52,逻辑联结词集是,功效完备集,(,Functionally Complete Set)：,任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来公式。,逻辑联结词集是,极小功效完备集,：,是功效完备集而且没有冗余联结词。,联结词全功效集,53/81,53,例1：,、,、,、,、,是功效完备，但不是,极小功效完备,。,例2：,、,、,是,极小功效完备,。,例3：,、,、,是,极小功效完备,。,联结词全功效集,54/81,54,DEFINITION 10.,命题公式,P,对偶公式,(,Dual),：,将,P,中,析取联结词换成合取联结词，,合取联结词换成析取联结词，,1换成0，0换成1（假如存在话）。,记为,P*.,命题逻辑,对偶与范式,5,55/81,55,对偶原理(,Duality Principle)：,设,P，Q,是两命题公式，假如,P,Q，,则,P*,Q*。,例：,A,：(P,Q)Q,B：P Q,这里，,A,B，,分析是否,A*,B*。,对偶与范式,56/81,56,命题公式标准化,范式,小项,(,small item)/,合取式,(,conjunctive form):,若干个原子命题或其否定合取。,大项,(,large item)/,析取式,(,disjunctive form):,若干个原子命题或其否定析取。,析取范式,(,disjunctive normal form)：,若干个小项析取。,合取范式,(,conjunctive normal form)：,若干个大项合取。,对偶与范式,57/81,57,定理证实思绪：,1、消去对,、,来说冗余联结词；,2、将否定联结词移到命题变量前面；,3、消除多出否定联结词；,4、利用分配律化成合取范式和析取范式。,定理1：任意一个命题公式都存在与之等价,合取范式和析取范式。,范式存在定理,对偶与范式,58/81,58,令,A(a,1,、a,2,、a,n,),是包含有,n,个变量公式，,极小项,(,extremal),:,小项中恰包含,n,个变量或其否定。,极大项,(,extremal),:,大项中恰包含,n,个变量或其否定。,主析取范式,(,Unique disjunctive normal form),:,若干个,极小项,析取。,主合取范式,(,Unique conjunctive normal form),:,若干个,极大项,合取。,对偶与范式,59/81,59,以三个命题变项,p,q,r,为例，可形成2,3,=8个,极小项,，每个,极小项,对应一个二进制数，也对应一个十进制数，二进制数是该极小项,成真赋值,，十进制数可做该极小项抽象表示法角码。对应情况以下：,pqr 0000，,记作,m,0,；,pqr 0011，,记作,m,1,；,pqr 0102，,记作,m,2,；,pqr 0113，,记作,m,3,；,pqr 1004，,记作,m,4,；,pqr 1015，,记作,m,5,；,pqr 1106，,记作,m,6,；,pqr 1117，,记作,m,7,。,主析取范式,：如,m,1,m,2,m,5,可用,(1,2,5),表示。,对偶与范式,60/81,60,以三个命题变项,p,q,r,为例，可形成2,3,=8个,极大项,，每个,极大项,对应一个二进制数，也对应一个十进制数，二进制数是该极大项,成假赋值,，十进制数可做该极大项抽象表示法角码。对应情况以下：,pqr 0000，,记作,M,0,；,pqr 0011，,记作,M,1,；,pqr 0102，,记作,M,2,；,pqr 0113，,记作,M,3,；,pqr 1004，,记作,M,4,；,pqr 1015，,记作,M,5,；,pqr 1106，,记作,M,6,；,pqr 1117，,记作,M,7,。,主合取范式,：如,M,0,M,3,M,6,可用,(0,3,6),表示。,对偶与范式,61/81,61,EXAMPLE 16,求,pqr,主析取范式和主合取范式：,解：(,pq)r,(p q),(r r),)(r,(p p),),(p q r)(p q r)(p r)(p r),(pqr)(pqr)(pr),(qq),)(pr),(qq),),(pqr)(pqr)(pqr)(pqr),(pqr)(pqr),(pqr)(pqr)(pqr)(pqr)(pqr),m,7,m,6,m,5,m,3,m,1,(1,3,5,6,7)（,主析取范式）,M,0,M,2,M,4,(0,2,4)（,主合取范式）,对偶与范式,62/81,62,例,6,张先生手中有代号为,A,、,B,、,C,、,D,、,E,五种股票，依据当前股市情况及张先生本人经济需求，需要有若干个股票抛出，但又必须满足以下复杂要求：,（,1,）若,A,抛出，则,B,也抛出；,（,2,）,B,和,C,要留一个股票且只能留一个；,（,3,）,C,和,D,要么全抛，要么都不抛；,（,4,）,D,和,E,两种股票中必定有一个或两种要抛出；,（,5,）若,E,抛出，则,A,、,B,也抛出。,上述五种条件全部满足，问有几个合理方案供张先生选择。,AB,C,D,DE,EA B,解答：留,ABE,或,CD（,将题意置换成主析取范式）。,对偶与范式,B,C,63/81,63,小 结,1、命题公式等价演算,2、命题公式标准化描述,表示、分类、判定、应用,对偶与范式,64/81,64,数理逻辑主要任务是借助于数学方法来研究,推理,逻辑。,推理,是从前题推出结论思维过程，,前提,是已知命题公式，,结论,是从前题出发应用推理规则推出命题公式。,命题逻辑,推理理论,6,65/81,65,DEFINITION 11.,若,A,1,A,2,A,k,B,为重言式，则称从,A,1,A,2,A,k,推出结论,B,推理正确,，记作,A,1,A,2,A,k,B。B,是,A,1,A,2,A,k,逻辑结论,或,有效结论,。,称,A,1,A,2,A,k,B,为推理,形式结构,。,推理理论,66/81,66,判断推理是否正确方法有以下几个：,（1）真值表法；,（2）等值演算法；,（3）主析取范式法。,（即判断,A,1,A,2,A,k,B,是否为重言式）,推理理论,67/81,67,EXAMPLE 17,判断以下推理是否正确：,假如天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。,解这类推理问题，应先将命题符号化，然后写出前提、结论和推理形式结构，最终进行判断。,在这里，设,p：,天气凉快；,q：,小王去游泳。,前提：,pq,p。,结论：,q。,推理形式结构：(,pq)p)q。,下面分别用三种方法来判断该蕴含式是否为重言式。,推理理论,68/81,68,Table 15（1）,真值表法,Table15,(pq)p)q (*)真值表,p q,q,pq,(,pq)p,(*),0 0,0 1,1 0,1 1,1,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,真值表最终一列全为1，因而（*）是重言式，所以推理正确。,推理理论,69/81,69,（2）等值演算法,(,pq)p)q,(,p,q),p),q,(,p,q),p),q,(,p,q),p,q,(,p,q),(,p,q),1,该蕴含式是重言式，所以推理正确。,推理理论,70/81,70,(,pq)p)q,(,p,q),p),q,(,p,q),p),q,(,p,q),p,q,(p,q),(,p,(q,q),),(,q,(p,p),),(p,q),(,p,q)(,p,q),(,q,p),(,q,p),(p,q),(,p,q)(,p,q),(p,q,),m3,m1m0m2,(0,1,2,3),（3）主析取范式法,该蕴含式主析取范式中含有4个极小项，因而是重言式。,推理理论,71/81,71,为了更加好地判断推理正确性，引入,结构证实,方法。,在数理逻辑中，,证实,是一个描述推理过程命题公式序列，其中每个命题公式或者是已知前提，或者是由一些前提应用,推理规则,得到结论。其中有些规则建立在,推理定律,（重言蕴含式）基础之上。,主要8条,推理定律,：,附加、化简、假言推理、拒取式、析取三段论、假言三段论、等价三段论、结构性二难。,除此之外，每个等值式均产生两条推理定律。,推理理论,72/81,72,推理规则：,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,9、,析取三段论,规则：,A,B,B,A,10、,结构性二难,规则：,A,B,C,D,A,C,B,D,11、,合取引入,规则：,A,B,A,B,推理理论,73/81,73,EXAMPLE 18,写出对应下面推理证实：,若数,a,是实数，则它不是有理数就是无理数。若,a,不能表示成份数，则它不是有理数。,a,是实数且它不能表示成份数。所以,a,是无理数。,解：将简单命题符号化：,p：a,是实数；,q：a,是有理数；,r：a,是无理数；,s：a,能表示成份数。,前提：,p(qr),sq,ps。,结论：,r。,推理理论,74/81,74,证实：,ps,前提引入,p ,化简,s,化简,p(qr),前提引入,qr,假言推理,sq,前提引入,q,假言推理,r ,析取三段论,推理理论,75/81,75,在使用,结构证实法,来进行推理时，经常采取一些技巧，下面介绍两种：,1、附加前提证实法,2、归谬法,推理理论,76/81,76,EXAMPLE 19,用附加前提证实法证实下面推理：,假如小张去看电影，则当小王去看电影时，小李也去。小赵不去看电影或小张去看电影。小王去看电影。所以当小赵去看电影时，小李也去。,解：将简单命题符号化：,p：,小张去看电影；,q：,小王去看电影；,r：,小李去看电影；,s：,小赵去看电影。,前提：,p(qr),sp,q。,结论：,sr。,推理理论,77/81,77,证实：,sp,前提引入,s,附加前提引入,p,析取三段论,p(qr),前提引入,qr,假言推理,q,前提引入,r,假言推理,推理理论,78/81,78,EXAMPLE 20,用归谬法结构下面推理证实：,前提：,p(rs)q),p,s。,结论：,q。,推理理论,79/81,79,证实：,p(rs)q),前提引入,p,前提引入,(,rs)q,假言推理,(,q),否定结论,引入,q,置换,rs,拒取式,s,化简,s,前提引入,s,s,合取,为矛盾式，依据归谬法说明推理正确。,推理理论,80/81,80,谢谢！,下一章,81/81,