第三次课(范式与推理).ppt
第三次课第三次课(范式与推理范式与推理)Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 n 个命题变项所能组成的具有不同真值的命题公式仅有个命题变项所能组成的具有不同真值的命题公式仅有 2 个个,然而与任何一个命题公式等值而形式不同的命题公式可以然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。有无穷多个。这样，这样，首先就要问凡与命题公式首先就要问凡与命题公式A等值的公式能等值的公式能否都可以化为某一个统一的标准形式希望这种标准形能为我们否都可以化为某一个统一的标准形式希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值。借助于标准形容易判断任一公公式，可判断它们的是否等值。借助于标准形容易判断任一公式是否为重言式或矛盾式。式是否为重言式或矛盾式。第一章第一章 -数理逻辑数理逻辑n10/15/20222Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 标准形或范式这类术语数学上是常见的，标准形或范式这类术语数学上是常见的，如几何学中如几何学中，分别是圆和椭圆的范式。分别是圆和椭圆的范式。第一章第一章 -数理逻辑数理逻辑10/15/20223Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 合取称为积合取称为积,析取称为和。析取称为和。由一些简单命题或其否定的合取组成的公式称为基本积。由一些简单命题或其否定的合取组成的公式称为基本积。由一些简单命题或其否定的析取组成的公式称基本和。由一些简单命题或其否定的析取组成的公式称基本和。如如 P,P,PQ,P Q P都是合取式，都是合取式，而而 P,P,PQ,PQ Q都是析取式。都是析取式。第一章第一章 -数理逻辑数理逻辑10/15/20224Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 范式存在定理范式存在定理任一命题公式都存在有与之等值的合取范任一命题公式都存在有与之等值的合取范式和析取范式。式和析取范式。第一章第一章 -数理逻辑数理逻辑10/15/20225Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 求范式的步骤求范式的步骤 对一个已给的公式对一个已给的公式,可按下述步骤求得该公式的合取范式和析取范式。可按下述步骤求得该公式的合取范式和析取范式。(1)消去已给公式中的联结词消去已给公式中的联结词和和 。(2)重复使用摩根律和双重否定律重复使用摩根律和双重否定律,把否定词内移到直接作用于把否定词内移到直接作用于命题变项上。命题变项上。(3)重复使用分配律。重复使用分配律。第一章第一章 -数理逻辑数理逻辑10/15/20226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 求求 (PQ)(PQ)的析取范式。的析取范式。解：解：(PQ)(PQ)=(PQ)(P Q)(PQ)(PQ)=(P QPQ)(PQ)(P Q)(摩根律、双重否定摩根律、双重否定)=(P QPQ)(P P)(P Q)(Q P)(Q Q)(分配律分配律)这已是析取范式了。又因这已是析取范式了。又因P P,Q Q,P QPQ都是矛盾式都是矛盾式,从而利用从而利用2.2.1的同一律的同一律PF=P,还可简化为还可简化为(P Q)(PQ)可见一公式的范式不是唯一的。可见一公式的范式不是唯一的。第一章第一章 -数理逻辑数理逻辑10/15/20227Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 求求 (PQ)(PQ)的合取范式的合取范式解解:(PQ)(PQ)=(PQ)(PQ)(PQ)(PQ)=(PQ)(PQ)(P Q)(P Q)(摩根律、双重否定摩根律、双重否定)=(PQ)(P Q)(吸收律吸收律)第一章第一章 -数理逻辑数理逻辑10/15/20228Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 对对n个命题变项个命题变项P1,P n来说来说,所组成的公式所组成的公式(基本积基本积)Q1Q2 Q n 其中其中 Q i=P i 或或 Pi(i=1,n),则称则称Q1Q n为极为极小项小项,并以并以 mi 表示。表示。极小项必须含有极小项必须含有Q1,Q n全部全部n个文字。个文字。第一章第一章 -数理逻辑数理逻辑10/15/20229Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 由两个命题变项由两个命题变项P1,P2可构成四个极小项：可构成四个极小项：P1 P2,P1P2,P1 P2和和P1P2。若将。若将Pi与与1对应对应,而而 Pi与与0对应对应,进而将极小项进而将极小项 P1 P2与与00对应对应,简记为简记为m0。P1P2与与01对应，简记为对应，简记为m1。P1 P1与与10对应对应,简记为简记为m2。P1P2与与11对应对应,简记为简记为m3。n个命题变项个命题变项P1,P n可组成可组成 个极小项。每个极小项也个极小项。每个极小项也可以可以mi表示表示。每个极小项中。每个极小项中Q1,Q m全部出现。全部出现。第一章第一章 -数理逻辑数理逻辑10/15/202210Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 定义：仅由极小项构成的析取式为主析取范式。定义：仅由极小项构成的析取式为主析取范式。定理：任一含有定理：任一含有n个命题变项的公式，都有唯一的个命题变项的公式，都有唯一的一个与之等值的恰仅含这一个与之等值的恰仅含这n个命题变项的主析取范式。个命题变项的主析取范式。第一章第一章 -数理逻辑数理逻辑10/15/202211Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 用真值表法将用真值表法将P Q化成主析取范式。化成主析取范式。由由P,Q到到P Q的真值表的真值表(从从T即选取使该式真值为即选取使该式真值为T的真值指派项的的真值指派项的析取析取)列写列写P Q,便得便得P Q=(P Q)(PQ)=m0m3 并简记为并简记为0,3。这便是。这便是P Q的主析取范式。的主析取范式。又因为等值公式都有相同的真值表又因为等值公式都有相同的真值表,从而可知所有等值公式从而可知所有等值公式(变项均为变项均为n)的主析取范式是相同的，或说一个公式的主析取范式是唯一的。的主析取范式是相同的，或说一个公式的主析取范式是唯一的。第一章第一章 -数理逻辑数理逻辑10/15/202212Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 用填满命题变项法用填满命题变项法,将将PQ的析取范式化成主析取范式。的析取范式化成主析取范式。PQ=PQ已是已是PQ的析取范式。现将这范式中的合取式的析取范式。现将这范式中的合取式 P添加变项添加变项Q,合取式合取式Q添加添加P,即填满变项即填满变项P、Q,以构成极小项。以构成极小项。P=P(Q Q)=(PQ)(P Q)Q=Q(P P)=(QP)(Q P)第一章第一章 -数理逻辑数理逻辑10/15/202213Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 从而从而PQ=PQ=(PQ)(P Q)(PQ)(PQ)=(P Q)(PQ)(PQ)=m0m1m3 =0,1,3 这便是这便是PQ的主析取范式。当然也可以用真值表法来得到此主析取范式的主析取范式。当然也可以用真值表法来得到此主析取范式.第一章第一章 -数理逻辑数理逻辑10/15/202214Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 某班级要从某班级要从3名学生名学生A，B，C中挑选中挑选12名搬花。由于名搬花。由于工作需要，选派时要满足以下条件：工作需要，选派时要满足以下条件：（1）若若A去，则去，则C同去；同去；（2）若若B去，则去，则C不能去；不能去；（3）若若C不去，则不去，则A或或B可以去。可以去。问班里应如何选派他们？问班里应如何选派他们？第一章第一章 -数理逻辑数理逻辑10/15/202215Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 解：设解：设P：派：派A去去 Q：派：派B去去 R：派：派C去去由已知条件可得公式由已知条件可得公式 (PR)(Q R)(R(PQ)经过演算可得经过演算可得(PR)(Q R)(R(PQ)=m1m2m5第一章第一章 -数理逻辑数理逻辑10/15/202216Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 由于由于m1=P QR,m2=PQ R,m5=P QR可知，选派方案有三种：可知，选派方案有三种：（a）C去，而去，而A，B都不去；都不去；（b）B去，而去，而A，C都不去；都不去；（c）A，C同去，而同去，而B不去。不去。第一章第一章 -数理逻辑数理逻辑10/15/202217Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 极小项的性质极小项的性质(1)对一个含有对一个含有n个变项的公式来说个变项的公式来说,所有可能的极小项个所有可能的极小项个数和该公式的解释个数一样多数和该公式的解释个数一样多,都是都是i 。(2)每个极小项只在一个解释下为真。每个极小项只在一个解释下为真。(3)极小项两两不等值极小项两两不等值,而且而且 m i m j=F(i j)。第一章第一章 -数理逻辑数理逻辑10/15/202218Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 由由n个命题变项个命题变项P1,P n 所组成的公式所组成的公式(基本和基本和)Q1Q2Q n其中其中Q i=Pi或或 Pi(i=1,n),则称则称 Q iQ n 为极大项为极大项,以以Mi表示。表示。极大项必须含有极大项必须含有Q1,Q n 全部全部n个文字。个文字。由两个命题变项由两个命题变项P1,P2可构成四个极大项：可构成四个极大项：P1 P2,P1P2,P1 P2和和P1P2,并分别以并分别以M3,M2,M1和和M0表示。表示。n个命题变项个命题变项P1,P n 可组成可组成 个极大项。每个极大项也可以个极大项。每个极大项也可以 Mi 来表示。来表示。每个极大项中每个极大项中Q1,Q n 全部出现。全部出现。第一章第一章 -数理逻辑数理逻辑10/15/202219Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 定义：仅由极大项构成的合取式为主合取范式。定义：仅由极大项构成的合取式为主合取范式。定理：任一含有定理：任一含有n个命题变项的公式，都有唯一的一个个命题变项的公式，都有唯一的一个与之等值的恰仅含这与之等值的恰仅含这n个命题变项的主合取范式。个命题变项的主合取范式。同样使用真值表列写公式的方法，以及将合取范式中的同样使用真值表列写公式的方法，以及将合取范式中的析取式填满命题变项的方法都可得到一个公式的唯一的主合析取式填满命题变项的方法都可得到一个公式的唯一的主合取范式。取范式。第一章第一章 -数理逻辑数理逻辑10/15/202220Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 用真值表法将用真值表法将P Q化成主合取范式。化成主合取范式。依由依由P、Q到到P Q的真值表的真值表,从从F(即选取使该式真值为即选取使该式真值为F的反真值指的反真值指派项的合取派项的合取)列写列写P Q,便得便得P Q=(P Q)(PQ)=M1M2 并简记为并简记为1,2。这便是。这便是P Q的主合取范式。的主合取范式。第一章第一章 -数理逻辑数理逻辑10/15/202221Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 用填满命题变项法用填满命题变项法,将已为合取范式的将已为合取范式的PQ化为主合取范式。化为主合取范式。PQ=(P(Q Q)(Q(P P)=(PQ)(P Q)(QP)(Q P)=(PQ)(P Q)(PQ)=M2M1M0=0,1,2第一章第一章 -数理逻辑数理逻辑10/15/202222Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 极大项的性质极大项的性质(1)对一个含有对一个含有n个变项的公式来说个变项的公式来说,所有可能的极大项个所有可能的极大项个数和该公式的解释个数一样多数和该公式的解释个数一样多,都是都是i。(2)每个极大项只在一个解释下为假。每个极大项只在一个解释下为假。(3)极大项两两不等值极大项两两不等值,而且而且 Mi M j=T (i j)。第一章第一章 -数理逻辑数理逻辑10/15/202223Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 推推 理理第一章第一章 -数理逻辑数理逻辑10/15/202224Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 如果今天我病了如果今天我病了,那么我没来上课。那么我没来上课。今天我病了。今天我病了。所以今天我没来上课。所以今天我没来上课。这是自然语句给出的三个命题，有前提有结论，表示了一种推理关系。这是自然语句给出的三个命题，有前提有结论，表示了一种推理关系。引入符号，以引入符号，以P表示表示今天我病了今天我病了,Q表示表示我没来上课我没来上课(则第一个自然语句则第一个自然语句表示为表示为PQ)。便可将这推理关系以条件式。便可将这推理关系以条件式(PQ)P)Q来表示。来表示。第一章第一章 -数理逻辑数理逻辑10/15/202225Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 也可以用图式表示也可以用图式表示:图示图示 这个条件式或图式就是一推理形式。说明如果这个条件式或图式就是一推理形式。说明如果P真真,PQ真真,就可就可推得推得Q真真,这里的这里的P、Q可表任意命题可表任意命题,从而推理形式从而推理形式(PQ)P)Q反映了一类推理关系。反映了一类推理关系。第一章第一章 -数理逻辑数理逻辑10/15/202226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 推理一般分为两类：推理一般分为两类：演绎推理和归纳推理。演绎推理和归纳推理。凡前提和结论存在必然联系的推理属于演绎推理，否则凡前提和结论存在必然联系的推理属于演绎推理，否则属于归纳推理。属于归纳推理。古典的数理逻辑主要研究演绎推理古典的数理逻辑主要研究演绎推理.第一章第一章 -数理逻辑数理逻辑10/15/202227Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 我们可以给出关于推理的如下定义：我们可以给出关于推理的如下定义：设设1，2，n，都是命题形式，称推理都是命题形式，称推理1，2，n推出推出是有效的，如果对是有效的，如果对1，2，n，中出现的命题变项的任一指派，中出现的命题变项的任一指派，若若1，2，n都真，则都真，则亦真，否则，称亦真，否则，称由由1，2，n推出推出是无效的或不合理的。是无效的或不合理的。另外，在推理形式中，推理形式的有效与否与前提中命题形式的排另外，在推理形式中，推理形式的有效与否与前提中命题形式的排列次序无关。列次序无关。第一章第一章 -数理逻辑数理逻辑10/15/202228Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 命题公式命题公式A1，A2，An推推B的推理正确当且仅当的推理正确当且仅当(A1A2A n)B 为重言式。为重言式。课本课本 P24 定义定义1.4-1常用的推理规则：（课本上常用的推理规则：（课本上 P25）第一章第一章 -数理逻辑数理逻辑10/15/202229Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 证明方法：证明方法：1.无义证明法。无义证明法。P假，假，P Q为真。为真。2.平凡证明法。平凡证明法。Q真，真，P Q为真。为真。3.直接证明法。直接证明法。假设假设P真真 Q真，真，P Q为真。为真。4.间接证明法。反证法。间接证明法。反证法。第一章第一章 -数理逻辑数理逻辑10/15/202230Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 构造下面推理的证明：如果小张追小李并且小李对小张有意思，则他们能构造下面推理的证明：如果小张追小李并且小李对小张有意思，则他们能成为朋友。或者他们不成为朋友，或者他们成为一对恋人。他们没有成为一对恋成为朋友。或者他们不成为朋友，或者他们成为一对恋人。他们没有成为一对恋人。小张追小李。因此，小李对小张没有意思。人。小张追小李。因此，小李对小张没有意思。解：先将简单命题符号化。解：先将简单命题符号化。P：小张追小李；：小张追小李；Q：小李对小张有意思；：小李对小张有意思；R：他们成为朋友；：他们成为朋友；S：他们成为一对恋人。：他们成为一对恋人。前提：前提：(PQ)R，RS，S，P 结论：结论：Q第一章第一章 -数理逻辑数理逻辑10/15/202231Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 证明：用归谬法证明：用归谬法 (1)Q 结论的否定引入结论的否定引入(2)RS 前提引入前提引入(3)S 前提引入前提引入(4)R (2)(3)析取三段论析取三段论(5)(PQ)R 前提引入前提引入(6)(PQ)(4)(5)拒取式拒取式 (7)P Q (6)置换置换(8)P 前提引入前提引入(9)Q (7)(8)析取三段论析取三段论(10)Q Q (1)(9)合合取取由于最后一步由于最后一步Q Q=F，即，即(PQ)R)(RS)SP)Q=F，所以推理正确。所以推理正确。第一章第一章 -数理逻辑数理逻辑10/15/202232Hongzhi Qiao,Xidian Univ.
