数理逻辑.ppt

第五篇 数理逻辑逻辑-是研究人的思是研究人的思维的科学。它包含：的科学。它包含：1.1.辩证逻辑：是研究人的思：是研究人的思维中的中的辩证法。是法。是研究思研究思维内在内在语义规律，属于哲学的范畴。律，属于哲学的范畴。例如：用全面的和例如：用全面的和发展的展的观点点观察事物；察事物；具体具体问题具体分析；具体分析；实践是践是检查事物正事物正误的唯一的唯一标准；等等。准；等等。2.2.形式形式逻辑：是研究人的思：是研究人的思维的形式和一般的形式和一般规律。是研究思律。是研究思维外部表外部表现的的规律。律。这里我里我们只关心形式只关心形式逻辑。1.数理逻辑形式形式逻辑主要是研究推理的主要是研究推理的。归纳推理：推理：由若干个由若干个别事事实推出一般推出一般结论。如：如：铜能能导电。铁能能导电。锡能能导电。铅能能导电。一切金属都一切金属都导电。演演绎推理：推理：由一般由一般规律推出个律推出个别事事实。形式形式逻辑主要是研究演主要是研究演绎推理的。推理的。例例1 1：如果天下雨，：如果天下雨，则路上有水。路上有水。(一般一般规律律)天下雨了。天下雨了。(个个别事事实)推出推出结论：路上有水。：路上有水。(个个别结论)2.数理逻辑数理数理逻辑是用是用数学的方法数学的方法研究形式研究形式逻辑。所所谓“数学方法数学方法”：是建立一套有：是建立一套有严格定格定义的的符号，即建立一套形式符号，即建立一套形式语言，来研究形式言，来研究形式逻辑。所以数理所以数理逻辑也称也称为“符号符号逻辑”。它与数学的其它分支、它与数学的其它分支、计算机科学、人工智能、算机科学、人工智能、语言学等学科均有密切言学等学科均有密切联系。系。这里只里只讨论“命命题逻辑”和和“谓词逻辑”。下面就前面两个例子，下面就前面两个例子，说明如何将推理符号化明如何将推理符号化的。的。3.数理逻辑使用使用计算机必算机必须首先学会首先学会编“程序程序”，那么什么，那么什么是程序？是程序？程序算法数据程序算法数据 算法算法逻辑控制控制 可可见“逻辑”对于于编程序是多么重要。要想程序是多么重要。要想学学好、使用好好、使用好计算机，必算机，必须学学习逻辑，此外，通，此外，通过学学习逻辑，掌握，掌握逻辑推理推理规律和律和证明方法明方法 ，会，会培培养同学养同学们的的逻辑思思维能力，提高能力，提高证明明问题的技巧。的技巧。4.数理逻辑 正如著名的正如著名的计算机算机软件大件大师戴克斯特拉戴克斯特拉 (E.W.Dijkstra)(E.W.Dijkstra)曾曾经说过：我：我现在年在年纪大了，搞了大了，搞了这么多年么多年软件，件，错误不知犯了多少，不知犯了多少，现在在觉悟了。我想，假如悟了。我想，假如我早在数理我早在数理逻辑上好好下点功夫的上好好下点功夫的话，我，我就不会犯就不会犯这么多么多错误。不少。不少东西西逻辑学家学家早就早就说过了，可是我不知道。要是我能年了，可是我不知道。要是我能年轻2020岁的的话，我就会回去学，我就会回去学逻辑。5.命题逻辑命命题是一个能确定是真的或是假的判断。（判断都是用是一个能确定是真的或是假的判断。（判断都是用陈述句表示）述句表示）例例1.1.判定下面判定下面这些句子哪些是命些句子哪些是命题。2 2是个素数。是个素数。雪是黑色的。雪是黑色的。20132013年人年人类将到达火星。将到达火星。如果如果 abab且且bcbc，则acac。x+y5 x+yb(ab、bcbc、ac)ac)构成的复合命构成的复合命题。8.命题逻辑联结词复合命复合命题的构成：是用的构成：是用“联结词”将原子命将原子命题联结起来构成的。起来构成的。归纳自然自然语言中的言中的联结词，定，定义了五个了五个逻辑联结词，分，分别是：是：(1)(1)否定否定“”(2)(2)并且并且“”(3)(3)或者或者“”(4)(4)蕴含含“”(5)(5)等价等价“”9.命题逻辑否定否定“”表示：表示：“不成立不成立”，“不不”，“非非”，“没有没有”，“无无”，“并非并非”，“并不并不”。用于用于:对一个命一个命题P P的否定的否定,写成写成 P,P,并并读成成“非非P P”。P P的真的真值：与：与P P真真值相反。相反。例例1 1中中 P P：2 2是素数。是素数。P P：2 2不是素数。不是素数。P PT FF T10.命题逻辑并且并且“”(合取合取)表示：表示：“并且并且”、“不但不但而且而且.”、“既既又又 .”“”“尽管尽管还 ”，“和和”，“与与”，“同同”，“以及以及”，“而且而且”。例如例如 P P：小王能唱歌。：小王能唱歌。Q Q：小王能跳舞。：小王能跳舞。PQPQ：小王能歌善舞。：小王能歌善舞。PQPQ读成成P P并且并且Q Q。PQPQ的真的真值为真真，当且，当且 仅当当P P和和Q Q的真的真值均均为真真。P Q PQF F FF T FT F FT T T11.命题逻辑或者或者“”（析取）（析取）表示表示“或者或者”，“或者或者”有有二二义性性，看下面，看下面两个例子：两个例子：例例1.1.灯泡灯泡或者或者线路有故障。路有故障。例例2.2.第一第一节课上数学上数学或者或者上英上英语。例例1 1中的中的或者或者是是可兼取的或可兼取的或。即。即或者或者“”例例2 2中的中的或者或者是是不可兼取的或不可兼取的或，也称之，也称之为异或异或、排斥或排斥或。即。即“”.12.命题逻辑P P：灯泡有故障。：灯泡有故障。Q Q：线路有故障。路有故障。例例1 1中的复合命中的复合命题可可 表示表示为：PQPQ，读 成成P P或者或者Q Q，PQPQ的的真真值为F F，当且，当且仅当当P P与与Q Q均均为F F。P Q PQF F FF T TT F TT T T13.命题逻辑P P：第一第一节上数学。上数学。Q Q：第一：第一节上英上英语。例例2 2中的复合命中的复合命题 可写成可写成P QP Q，读 成成P P异或异或Q Q。P QP Q的真的真值为F F，当且当且仅当当P P与与Q Q的的真真值相同相同。F F FF T TT F TT T FP Q P Q14.命题逻辑蕴含含(条件条件)“”表示表示“如果如果 则 ”，“当当.则.”,“若若.那么那么.”，“假如假如.那么那么.”例如：例如：P P表示：缺少水分。表示：缺少水分。Q Q表示：植物会死亡。表示：植物会死亡。P PQ Q：如果：如果缺少水分缺少水分，植物就会死亡植物就会死亡。P PQ Q：也称之：也称之为蕴含式，含式，读成成“如果如果P P则Q Q”。也也说成成P P是是P PQ Q 的前件，的前件，Q Q是是P PQ Q的后件。的后件。还可以可以说P P是是Q Q的充分条件，的充分条件，Q Q是是P P的必要条的必要条件。件。15.P PQ Q的真的真值为假，当且假，当且仅当当P P为真、真、Q Q为假假。在在这里，当前件里，当前件P P为假假时，则不不论后件是真后件是真还是假此是假此蕴含含式一定式一定为真。如真。如“如果明天天气晴朗如果明天天气晴朗则举行运行运动会。会。”此此蕴含式是含式是对“明天天气晴朗明天天气晴朗”条件成立而言，此条件成立而言，此时如如举行行运运动会会则为真，不真，不举行行则为假。但是如果明天天气不晴朗，假。但是如果明天天气不晴朗，此此蕴含式并没有考含式并没有考虑这种情况，种情况，则不管不管举行行还是不是不举行运行运动会都会都认为真。真。P Q PQ F F T F T T T F F T T T 16.命题逻辑充分条件充分条件：就是只要条件成立，：就是只要条件成立，结论就成立，就成立，则该条件就条件就是是充分条件充分条件。上例中，上例中，“缺少水分缺少水分”就是就是“植物会死亡植物会死亡”的充分条件。在自然的充分条件。在自然语言中表示充分条件的言中表示充分条件的词有有 ：如如果果 则 ，只要，只要 就就，若，若则 必要条件必要条件：就是如果：就是如果该条件不成立，那么条件不成立，那么结论就不成立就不成立,则该条件就是条件就是必要条件必要条件。上例中，上例中，“植物死亡植物死亡”就是就是“缺少水分缺少水分”的必要条件的必要条件(植植物未死亡，一定不缺少水分物未死亡，一定不缺少水分)。在自然在自然语言中表示必要条件的言中表示必要条件的词有有 ：只有只有 才才 ；仅当当，;,仅当当。17.命题逻辑等价等价“”表示表示“当且当且仅当当”、“充分且必要充分且必要”,相同相同，“相等相等”，“一一样”例如：例如：P P：ABCABC是等是等边三角形。三角形。Q Q：ABCABC是等角三角形。是等角三角形。P PQ Q ：ABCABC是等是等边三角形当且三角形当且仅当当 它是等角三角形。它是等角三角形。18.命题逻辑PQ的真值为真，当且仅当P与Q的真值相同。P Q PQ F F T F T F T F F T T T 19.命题逻辑常常值命命题与命与命题变元元常常值命命题：即是我：即是我们前面所前面所说的命的命题。它是有具体含。它是有具体含义 (真真值)的。的。例如：例如：“3 3是素数。是素数。”就是常就是常值命命题。命命题变元：用大写的英字母如元：用大写的英字母如P P、Q Q等表示任何命等表示任何命题。称。称这些字母些字母为命命题变元。元。对命命题变元作指派元作指派(给命命题变元一个解元一个解释)：将一个常：将一个常值命命题赋予命予命题变元的元的过程，或者是直接程，或者是直接赋给命命题变元真元真值“T T”或或“F F”的的过程。程。注意：注意：命命题变元本身不是命元本身不是命题，只有，只有给它一个解它一个解释，才，才变成命成命题。20.命题逻辑命命题公式公式定定义：单个命个命题变元是个命元是个命题公式。公式。若若A A是命是命题公式，公式，则 A A是命是命题公式。公式。若若A A和和B B是命是命题公式，公式，则(A(AB)B)，(A(AB)B)，(A (AB)B)和和(A(AB)B)都是命都是命题公式。公式。当且当且仅当有限次地当有限次地应用用，所得到所得到 的含有命的含有命题变元、元、联结词和括号的和括号的符号串符号串 是命是命题公式。公式。这里所里所谓的命的命题公式可以解公式可以解释为由命由命题变元元,命命题联接接词及及圆括号括号组成的符号。成的符号。21.命题逻辑下面的式子不是命下面的式子不是命题公式：公式：P PQQ，P PR R，（PQPQ）R R）下面的式子才是命下面的式子才是命题公式：公式：(P(PQ)Q)，(P PR)R)，(PQ)R)(PQ)R)按照按照合式公式定合式公式定义最外最外层括号必括号必须写。写。约定：定：为方便，最外方便，最外层括号可以不写，上括号可以不写，上面的命面的命题公式可以写成：公式可以写成：P PQQ，P PR R，(PQ)R(PQ)R22.命题逻辑命命题公式的真公式的真值表表 一个命一个命题公式不是命公式不是命题，所以它没有，所以它没有真真值，但是，但是给其中的所有命其中的所有命题变元作指派以元作指派以后它就有了真后它就有了真值。可以以表的形式反。可以以表的形式反应它的它的真真值情况，例如命情况，例如命题公式公式 (P PQ)Q)Q Q 的的真真值表如下所示：表如下所示：P Q P Q P P P PQ (Q (P PQ)Q)Q Q F F T F F F F T F F F T T T T F T T T T T F F T T T F F T T T T F T T T T F T T23.命题逻辑由于由于对每个命每个命题变元可以有两个真元可以有两个真值(T,F)(T,F)被指派，所以有被指派，所以有n n个命个命题变元的命元的命题公式公式 A A(P(P1 1,P,P2 2,P,Pn n)的真的真值表有表有2 2n n行，每个指派行，每个指派对应公式的一个确定的公式的一个确定的值。公式公式值的确定是按公式中的确定是按公式中联结词出出现的先的先后后顺序及括号序及括号顺序逐步序逐步应用命用命题联结词的的真真值表表规定而得到的。定而得到的。24.命题逻辑所所谓命命题符号化，就是用命符号化，就是用命题公式的符号串来表示公式的符号串来表示给定的命定的命题。命命题符号化的方法符号化的方法1.1.首先要明确首先要明确给定命定命题的含的含义。2.2.对于复合命于复合命题，找，找联结词，用，用联结词断句，分解出各个原断句，分解出各个原子命子命题。3.3.设原子命原子命题符号，并用符号，并用逻辑联结词联结原子命原子命题符号，构符号，构成成给定命定命题的符号表达式。的符号表达式。4.4.为了减少括号的使用，在此做下列了减少括号的使用，在此做下列规定：定：(1)5(1)5个个联接接词的的结合能力从合能力从强到弱到弱顺序序为：“否定否定”，“合合取取”，“析取析取”，“蕴含含”，“等价等价”。(2)(2)规定具有相同定具有相同结合能力的合能力的联接接词，按照出，按照出现的先后次序，的先后次序，先出先出现者先运算，凡符合此要求者，括号均可除去。者先运算，凡符合此要求者，括号均可除去。(3)(3)最外最外层括号可省去。括号可省去。25.命题逻辑例例1.1.说离散数学无用且枯燥无味是不离散数学无用且枯燥无味是不对的。的。P P：离散数学是有用的。：离散数学是有用的。Q Q：离散数学是枯燥无味的。：离散数学是枯燥无味的。该命命题可写成：可写成：(P PQ)Q)例例2.2.如果小如果小张与小王都不去，与小王都不去，则小李去。小李去。P P：小：小张去。去。Q Q：小王去。：小王去。R R：小李去。：小李去。该命命题可写成：可写成：(P P Q)Q)R R例例3.3.如果小如果小张与小王不都去，与小王不都去，则小李去。小李去。该命命题可写成：可写成：(P(PQ)Q)R R 也可以写成：也可以写成：(P P Q)Q)R R26.命题逻辑例例4.4.仅当天不下雨且我有当天不下雨且我有时间，才上街。，才上街。P P：天下雨。：天下雨。Q Q：我有：我有时间。R R：我上街。：我上街。分析：由于分析：由于“仅当当”是表示是表示“必要条件必要条件”的，既的，既“天不下雨且我有天不下雨且我有时间”，是，是“我上我上街街”的必要条件。所以的必要条件。所以 该命命题可写成：可写成：R R(P PQ)Q)例例5.5.人不犯我，我不犯人；人若犯我，我必人不犯我，我不犯人；人若犯我，我必犯人。犯人。P P：人犯我。：人犯我。Q Q：我犯人。：我犯人。该命命题可写成：可写成：(P PQ)Q)(P(PQ)Q)或写成：或写成：P PQ QP是Q的必要条件P是Q的充分条件P是Q的充分且必要条件27.命题逻辑重言式重言式(永真式永真式)与矛盾式与矛盾式(永假式永假式)例子：例子：P P P PP P P PPP F T F F T F T T F T T F 可可见不不论P P取什么真取什么真值 P PPP 的真的真值总是是为真，真，P PPP的真的真值总是是为假。故称假。故称 P PPP为重言式重言式(永真式永真式)，称，称 P PPP为矛盾式矛盾式(永永假式假式)。28.命题逻辑重言式重言式(矛盾式矛盾式)定定义 A(P A(P1 1,P,P2 2,P,Pn n)是含有命是含有命题变元元P P1 1,P,P2 2,P Pn n的命的命题公式，如不公式，如不论对P P1 1,P,P2 2,P Pn n作作任何指派，都使得任何指派，都使得A(PA(P1 1,P,P2 2,P Pn n)为真真(假假)，则称之称之为重言式重言式(矛盾式矛盾式),),也称之也称之为永永真式真式 (永假式永假式)。重言式的重言式的证明方法明方法 方法方法1 1：列真：列真值表。表。方法方法2 2：公式的等价：公式的等价变换，化，化简成成“T T”。方法方法3 3：用公式的主析取范式。：用公式的主析取范式。29.命题逻辑方法方法1.1.列真列真值表。表。例如，例如，证明明 (P P(P PQ)Q)Q Q 为重言式。重言式。P Q P Q P PQ Q P P(P PQ)Q)(P P(P PQ)Q)Q Q F F T F F F T F T T F T T F T T F F T T T F F F T F F F T T T T T T T T T T T T 永真式的真永真式的真值表的最后一列全是表的最后一列全是“T T”30.命题逻辑永真式的性永真式的性质 1).1).如果如果A A是永真式，是永真式，则 A A是永假式。是永假式。2).2).如果如果A A，B B是永真式，是永真式，则(A(AB)B)、(A(AB)B)、(A(AB)B)和和(A(AB)B)也都是永真式。也都是永真式。有些重言有些重言(永真永真)式，如式，如(P P(P PQ)Q)Q Q，公式中公式中间是是“”联结词，是很重要的，是很重要的，称之称之为重言重言蕴含式。含式。31.命题逻辑重言重言(永真永真)蕴含式含式定定义：如果公式：如果公式A AB B是重言式，是重言式，则称称A A重言重言(永真永真)蕴含含B B，记作作 A AB B。注意符号注意符号“”不是不是联结词，它是表示公式，它是表示公式间的的“永真永真蕴含含”关系，也可以看成是关系，也可以看成是“推推导”关系。即关系。即A AB B可以理解成由可以理解成由A A可推出可推出B B，即，即由由A A为真，可以推出真，可以推出B B也也为真真。32.命题逻辑性性质 1).1).有自反性：有自反性：对任何命任何命题公式公式A A，有，有A AA A 2).2).有有传递性：若性：若A AB B且且B BC C，则A AC C 3).3).若若A AB B 且且 A AC C，则A ABCBC 4).4).若若A AB B 且且 C CB B，则ACACB B我我们可以通可以通过列真列真值表表(即列永真式的真即列永真式的真值表表)来来证明重言明重言(永真永真)蕴含式含式。33.命题逻辑重要的重言重要的重言蕴含式含式(如教材第如教材第182182页所示所示)I I1 1.P.PQ QP IP I2 2.P.PQ QQ Q I I3 3.P.PP PQ IQ I4 4.Q.QP PQ Q I I5 5.P PP PQ IQ I6 6.Q.QP PQ Q I I7 7.(P PQ)Q)P IP I8 8.(P PQ)Q)Q Q I I9 9.P.P(Q(Q P PQ Q)I I1010.P P(P(PQ)Q)Q Q I I1111.P.P(P(PQ)Q)Q IQ I1212.Q Q(P(PQ)Q)P P I I1313.(P.(PQ)Q)(Q(QR)R)P PR R I I1414.(P.(PQ)Q)(P(PR)R)(Q(QR)R)R R I I1515.A.AB B(B BR)R)(A AR)R)I I1616.A.AB B(R(RB B)(A AR RB B)34.命题逻辑等价公式等价公式例子例子 看下面三个公式的真看下面三个公式的真值表表 P Q P P Q PQ Q P PQ Q Q QP P F F T T T F F T T T F T T T T F T T T T T F F F F T F F F F T T T T T T T T T T 从真从真值表可以看出，不表可以看出，不论对P P、Q Q作何指派，作何指派，都使得都使得P PQ Q、P PQ Q和和 Q QP P的真的真值相同，相同，表明它表明它们之之间彼此等价。彼此等价。35.命题逻辑定定义：A A、B B是含有命是含有命题变元元P P1 1,P,P2 2,P Pn n的命的命题公式，如不公式，如不论对P P1 1,P,P2 2,P Pn n作任何指派，作任何指派，都使得都使得A A和和B B的真的真值相同，相同，则称之称之为A A与与B B等价，等价，记作作A AB B,或者称或者称A A与与B B相等，相等，记作作A=B.A=B.显然然 P PQ Q=P PQ Q=Q QP P重要的等价公式（重要的等价公式（p178)p178)对合律合律 P P=P P 幂等律等律 P PP P=P PP PP P=P P 结合律合律 P P(Q QR)R)=(P PQ)Q)R R P P(Q QR)R)=(P PQ)Q)R R 交交换律律 P PQ Q=Q QP PP PQ Q=Q QP P36.命题逻辑分配律分配律 P P(Q QR)R)=(P PQ)Q)(P PR)R)P P(Q QR)R)=(P PQ)Q)(P PR)R)吸收律吸收律 P P(P PQ)Q)=P PP P(P PQ)Q)=P P德德-摩根定律摩根定律 (P PQ)Q)=P P Q Q (P PQ)Q)=P P Q Q 同一律同一律 P PF F=P PP PT T=P P 零律零律 P PT T=T PT PF F=F F 互互补律律 P P P P=T T P P P P=F F P PQ Q=P PQ Q P PQ Q=Q QP P P PQ Q=(P PQ)Q)(Q(QP)P)P PQ Q=(P PQ)Q)(P(P Q)Q)P PQ Q=(P PQ)Q)(P P Q)Q)37.命题逻辑为便于便于记忆，将等价公式，将等价公式(前前1010个个)与集合与集合论的公式比的公式比较，(书p7)p7)请看集合看集合公式：公式：对合律合律 A A A AA A表示表示A A的的绝对补集集 幂等律等律 A AA AA AA AA AA A 结合律合律 A A(B BC)C)(A AB)B)C C A A(B BC)C)(A AB)B)C C交交换律律 A AB BB BA AA AB BB BA A分配律分配律 A A(B BC)C)(A AB)B)(A AC)C)A A(B BC)C)(A AB)B)(A AC)C)吸收律吸收律 A A(A AB)B)A AA A(A AB)B)A A德德-摩根定律摩根定律 (A AB)B)A AB B (A AB)B)A AB B 同一律同一律 A AA AA AE EA EA E表示全集表示全集 零律零律 A AE EE AE A 否定律否定律 A AA AE E A AA A38.命题逻辑例例题1.1.求求证 (P PQ)(PQ)Q)(PQ)P P证明明 (P PQ)(PQ)Q)(PQ)(P PQ)(PQ)(Q)(PQ)(公式公式E E1111)(PP Q)(PQ)(Q)(PQ)(摩根定律摩根定律)(P(P Q)(PQ)(Q)(PQ)(对合律合律)P(P(QQ)(QQ)(分配律分配律)PT (PT (互互补律律)P (P (同一律）同一律）39.命题逻辑例例题2.2.化化简(PQ)(PQ)(P(P(PQ)PQ)解解 原公式原公式 (PQ)(PQ)(PP P)Q)(EP)Q)(E1111,结合合)(PQ)(PQ)(PQ)(PQ)(对合律，合律，幂等律等律)(PQ)(Q(PQ)(Q P)(P)(交交换律律)(PQ)(PQ)Q)Q)P (P (结合律合律)（Q Q(Q(QP)P)）P P （交（交换律）律）QQ P (P (吸收律吸收律)40.命题逻辑等价公式的等价公式的对偶性偶性从前面列出的等价公式看出，有很多是成从前面列出的等价公式看出，有很多是成对出出现的。的。对偶式：在一个只含有偶式：在一个只含有联结词 、的公式的公式A A中，将中，将换成成，换成成，T T换成成F F，F F换成成T T，其余部分不，其余部分不变，得到另一个公，得到另一个公式式A A*，称，称A A与与A A*互互为对偶式。偶式。例如例如:：A AA A*P P P P Q QR R Q QRR (P (PTT)Q Q (P(PFF)Q Q41.命题逻辑对偶原理：偶原理：令令A(PA(P1 1,P,P2 2,P,Pn n)、B(PB(P1 1,P,P2 2,P,Pn n)是只含有是只含有联结词、的命的命题公式，公式，则如果如果 A(PA(P1 1,P,P2 2,P,Pn n)B(PB(P1 1,P,P2 2,P,Pn n)则 A*(PA*(P1 1,P,P2 2,P,Pn n)B*(PB*(P1 1,P,P2 2,P Pn n)下面我下面我们验证一下一下对偶原理：偶原理：P P(Q QR)R)(P PQ)Q)(P PR)R)P P(Q QR)R)(P PQ)Q)(P PR)R)P PT TT T P PF FF F42.命题逻辑命命题逻辑推理推理推理推理就是根据一个或几个已知的判断得出一个就是根据一个或几个已知的判断得出一个新的判断的思新的判断的思维过程。称程。称这些已知的判断些已知的判断为前提前提。得到的新的判断。得到的新的判断为前提的前提的有效有效结论。实际上，推理的上，推理的过程就是程就是证明永真明永真蕴含式的含式的过程，即令程，即令H H1 1，H H2 2，H Hn n是已知的命是已知的命题公式公式(前提前提)，若有，若有 H H1 1HH2 2.H.Hn n C C 则称称C C是是H H1 1，H H2 2，H Hn n的有效的有效结论，简称称结论。记为H H1 1，H H2 2，.，H Hn n C C43.命题逻辑在推理在推理过程中，程中，还要要应用永真用永真蕴涵式涵式I I1 1-I-I1616和等价公式和等价公式E E1 1-E-E22 22(常用的公式要熟常用的公式要熟记)。下面主要介下面主要介绍推理方法：推理方法：直接推理直接推理，就是从前提直接推出，就是从前提直接推出结论。上面上面讲到推理的到推理的过程程实际上是上是证明永真明永真蕴含式的含式的过程。程。反反证法法的主要思想是：假的主要思想是：假设结论不成立，可不成立，可以推出矛盾的以推出矛盾的结论(矛盾式矛盾式)。44.命题逻辑范式就是命范式就是命题公式形式的公式形式的规范形式。分范形式。分为析取析取范式与合取范式范式与合取范式1.1.析取范式析取范式：公式公式A A如果写成如下形式：如果写成如下形式：A A1 1AA2 2.A.An n (n1)(n1)其中每个其中每个A Ai i(i=1,2.n)(i=1,2.n)是合取式，称是合取式，称A A的析取范的析取范式。式。2.2.合取范式：合取范式：公式公式A A如果写成如下形式：如果写成如下形式：A A1 1AA2 2.A.An n (n1)(n1)其中每个其中每个A Ai i(i=1,2.n)(i=1,2.n)是析取式，称是析取式，称A A的合取范的合取范式。式。45.命题逻辑可以看出可以看出:在析取范式与合取范式中只含有在析取范式与合取范式中只含有联结词,并且并且 在命在命题变元之前元之前例如，例如，P PQ Q 的的析取范式与合取范式：析取范式与合取范式：P PQ Q(P PQ)Q)(P P Q)-Q)-析取范式析取范式 P PQ Q(P PQ)Q)(P(P Q)-Q)-合取范式合取范式注注:P PP PP PP PP PP P P P是合是合(析析)取式取式.46.命题逻辑析取范式与合取范式的写法析取范式与合取范式的写法 先用相先用相应的公式去掉的公式去掉和和。公式公式E E16 16 P PQ QP PQ Q 公式公式E E2121 P PQ Q(P PQ)Q)(P P Q)Q)公式公式E E20 20 P PQ Q(P PQ)Q)(Q(QP)P)再用再用E E16 16 P PQ Q(P PQ)Q)(P(P Q)Q)用公式的否定公式或摩根定律将用公式的否定公式或摩根定律将 后移到命后移到命题变元之前。元之前。A(PA(P1 1,P,P2 2,P,Pn n)A*(A*(P P1 1,P P2 2,P Pn n)底底-摩根定律摩根定律 (P PQ)Q)P P Q Q (P PQ)Q)P P Q Q用分配律、用分配律、幂等律等公式等律等公式进行整理，使之成行整理，使之成为要求的形式。要求的形式。47.命题逻辑例如求例如求(P(PQ)Q)R R的的析取范式与合取范式析取范式与合取范式 (P(PQ)Q)R R (P PQ)Q)(P P Q)Q)R R (P(P Q)Q)(P PQ)Q)R -R -析取范式析取范式(P(PQ)Q)R R(P(PQ)Q)(P P Q)Q)R R(P P Q)Q)(P PQ)Q)R R(P P Q QR)R)(P PQ QR)-R)-合取范式合取范式48.命题逻辑主析取范式与主主析取范式与主合取范式合取范式 一个公式的一个公式的析取范式与合取范式的形式是不唯一的。下析取范式与合取范式的形式是不唯一的。下面定面定义形式唯一的形式唯一的主析取范式与主主析取范式与主合取范式。合取范式。主析取范式（特异析取范式）主析取范式（特异析取范式）1.1.小小项 定定义：是：是n n个命个命题变元的合取式，其中每个元的合取式，其中每个变元必出元必出现且且仅出出现一次，称一次，称这个合取式个合取式为小小项。例如，有两个例如，有两个变元的小元的小项：P PQ QP P Q Q、P PQ Q、P P Q Q小小项可可编码:用用1 1表表变元本身元本身,0,0表表变元的元的否定形式否定形式,则49.命题逻辑 m m0000 P P Q Q m m0101 P PQ Q m m1010P P Q Q m m1111P PQ Q(2)(2)小小项的性的性质 m m1111 m m1010 m m01 01 m m0000 P Q P P Q PQ PQ P Q Q P PQ Q P P Q Q 00 F F F F F T 00 F F F F F T 01 F T F F T F 01 F T F F T F 10 T F F T F F 10 T F F T F F 11 T T T F F F 11 T T T F F F a).a).有有n n个个变元，元，则有有2 2n n个小个小项。50.命题逻辑b).b).每个小每个小项当且当且仅当其真当其真值指派与指派与编码相同相同时,其真其真值为T;T;其余其余2 2n n-1-1组真真值指派均使指派均使该小小项的真的真值为F F。c).c).全体小全体小项的析取式的析取式为永真式永真式,记为:m mi i=m=m0 0 m m1 1 mm2 2n n-1-1 T T2.2.主析取范式定主析取范式定义若一个命若一个命题公式的公式的析取范式析取范式为A A1 1AA2 2.A.An,n,其中每个其中每个A Ai i(i=1,2.n)(i=1,2.n)都是小都是小项，则称之称之为该命命题公式的公式的主析取范式。主析取范式。51.命题逻辑例如求例如求 P PQ Q和和P PQ Q的的主析取范式主析取范式 P Q PP Q PQ Q P PQ Q F F T T F F T T F T T F F T T F T F F F T F F F T T T T T T T T P PQ Q m m0000m m0101m m1111 (P P Q)Q)(P PQ)Q)(P(PQ)Q)P PQ Qm m0000m m1111 (P P Q)Q)(P(PQ)Q)一公式的真一公式的真值表中，使其表中使其为T T的指派所的指派所对应的的小小项构成的析取范式构成的析取范式为主主析取范式。析取范式。52.命题逻辑主主合取范式合取范式（特异合取范式）（特异合取范式）大大项：是：是n n个命个命题变元的析取式，其中每个元的析取式，其中每个变元必出元必出现且且仅出出现一次。一次。例如，有两个例如，有两个变元的大元的大项及其真及其真值表：表：M M0 0 0 0 M M01 01 M M10 10 M M1111 P Q P P Q PQ PQ P Q Q P PQ Q P P Q Q00 F F F T T T 00 F F F T T T 01 F T T F T T01 F T T F T T10 T F T T F T10 T F T T F T11 T T T T T F11 T T T T T F53.命题逻辑可看出大可看出大项的的编码正好与小正好与小项相反相反:用用0 0表表变元本身元本身,1,1表表变元的否定形式。元的否定形式。M M0 00 0P PQ Q M M01 01 P P Q Q M M10 10 P PQ Q M M11 11 P P Q Q大大项的性的性质a).a).有有n n个个变元，元，则有有2 2n n个大个大项。b).b).每个大每个大项当且当且仅当其真当其真值指派与指派与编码相同相同时,其真其真值为F;F;其余其余2 2n n-1-1组真真值指派均使指派均使该大大项的真的真值为T T。c).c).全体大全体大项的合取式必的合取式必为永假式永假式 M Mi i=M M0 0 M M1 1M M2 2n n-1-1 F F54.命题逻辑主合取范式定主合取范式定义若一个命若一个命题公式的合公式的合取范式取范式 为A A1 1AA2 2.A.An,n,其中每个其中每个A Ai i(i=1,2.n)(i=1,2.n)都是大都是大项，则称之称之为该命命题公式的公式的主合取范式。主合取范式。例如求例如求 P PQ Q和和P PQ Q的的主合取范式主合取范式 P Q PP Q PQ Q P PQ Q F F T T F F T T F T T F F T T F T F F F T F F F T T T T T T T T P PQ Q M M1010 P PQ Q P PQ Q M M0101M M10 10 (P(P Q Q )(P PQ)Q)一公式真一公式真值表中使其表中使其为F F的指派所的指派所对应的大的大项的合取即的合取即为主合主合取范式。取范式。55.谓语逻辑问题的提出的提出：(即命题逻辑的局限性)在前一章,一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。请看下面的例子。例1.令：小张是大学生。：小李是大学生。从符号、中不能归纳出他们都是大学生的共性。我们希望从所使用的符号那里带给我们更多的信息，比如可以看出他们的共性。这种想法在前一章是无法实现的。56.谓语逻辑例2.令：所有自然数都是整数。：是自然数。：是整数。这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，由和可以推出结论。这个推理是有效的，但是这个推理在前一章也是无法实现的。所以就要另外考另外考虑表示命表示命题的方法的方法。57.谓语逻辑解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念。令S(x)表示x是大学生，a:小张，b:小李 命题P表示成S(a):小张是大学生。命题Q表示成S(b):小李是大学生。从符号S(a)、S(b)可看出小张和小李都是大学生的共性.令N(x):x是自然数。I(x):x是整数。表示所有的。A:x(N(x)I(x)B:N(8)C:I(8)58.谓语逻辑个体与个体个体与个体变元元定定义：能够独立存在的事物，称之为个体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、.表示。例如，小张、小李、8、a、沈阳、社会主义等等都是个体。定定义：用小写英文字母x、y、z.表示任何个体，则称这些字母为个体变元。59.谓语逻辑谓词定定义：一个大写英文字母后边有括号，括号内是若干个个体变元，用以表示个体的属性或者个体之间的关系，称之为谓词。如果括号内有n个个体变元，称该谓词为n元谓词。例如 S(x):表示x是大学生一元谓词 G(x,y)：表示 xy。二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词一般地 P(x1,x2,xn)是n元谓词。60.谓语逻辑命命题函数函数谓词本身并不是命题，只有谓词的括号内填入足够的客体，才变成命题。例如，a表示小张，b表示小李，则 S(a):小张是大学生。S(b):小李是大学生。(7,3)表示:。如果c表示锦州，d表示沈阳，e表示山海关，则B(c,d,e)表示：锦州在沈阳与山海关之间。这时S(a)、S(b)、G(7,3)、B(c,d,e)才是命题。61.谓语逻辑令谓词S(x):x是大学生，括号内填入不同的人名，就得到不同的命题，故谓词S(x)相当于一个函数，称之为