然来是这么样的

然来是这么样的第1页，课件共113页，创作于2023年2月第一章 命题逻辑命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。退出第2页，课件共113页，创作于2023年2月1.1命题与联结词1.2命题变元和合式公式1.3公式分类与等价公式1.4对偶式与蕴涵式1.5联结词的扩充与功能完全组1.6公式标准型——范式1.7公式的主范式1.8命题逻辑的推理理论第3页，课件共113页，创作于2023年2月1.1 命题与联结词１.命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值—真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。第4页，课件共113页，创作于2023年2月如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R…及其带下标的Pi，Qi，Ri，…表示。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。第5页，课件共113页，创作于2023年2月２.命题联结词定义1.1.1

设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题，lP读“非P”。称l为否定联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否定联结词“l”的定义可由表1.1.1表示之。第6页，课件共113页，创作于2023年2月第7页，课件共113页，创作于2023年2月 由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。第8页，课件共113页，创作于2023年2月定义1.1.2

设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。合取联结词∧的定义由表1.1.2表示之。第9页，课件共113页，创作于2023年2月第10页，课件共113页，创作于2023年2月定义1.1.3

设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q”。称∨为析取联结词。当且仅当P和Q的真值同为假，P∨Q的真值为假；否则，P∨Q的真值为真。析取联结词∨的定义由表1.1.3表示之。第11页，课件共113页，创作于2023年2月第12页，课件共113页，创作于2023年2月由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有关例子就不再给出了。第13页，课件共113页，创作于2023年2月定义1.1.4 设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q的条件式复合命题，简称条件命题。P→Q读做“P条件Q”或者“若P则Q”。称→为条件联结词。 当P的真值为真而Q的真值为假时，命题P→Q的真值为假；否则，P→Q的真值为真。条件联结词→的定义由表1.1.4表示之。第14页，课件共113页，创作于2023年2月第15页，课件共113页，创作于2023年2月在条件命题P→Q中，命题P称为P→Q的前件或前提，命题Q称为P→Q的后件或结论。条件命题P→Q有多种方式陈述：“如果P，那么Q”；“P仅当Q”；“Q每当P”；“P是Q的充分条件”；“Q是P的必要条件”等。第16页，课件共113页，创作于2023年2月在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如例1.1.4中的①，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不单是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。第17页，课件共113页，创作于2023年2月定义1.1.5

令P、Q是两个命题，由命题联结词把P和Q连接成P

Q，称P

Q为命题P和Q的双条件式复合命题，简称双条件命题，P

Q读做“P当且仅当Q”，或“P等价Q”。称为双条件联结词。当P和Q的真值相同时，P

Q的真值为真；否则，P

Q的真值为假。双条件联结词的定义由表1.1.5表示之。第18页，课件共113页，创作于2023年2月第19页，课件共113页，创作于2023年2月在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。第20页，课件共113页，创作于2023年2月1.2命题变元和合式公式１.命题变元在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。第21页，课件共113页，创作于2023年2月命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下： 定义1.2.1

以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。第22页，课件共113页，创作于2023年2月2. 合式公式通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。定义1.2.2

单个命题变元和命题常元称为原子命题公式，简称原子公式。第23页，课件共113页，创作于2023年2月定义1.2.3

合式公式是由下列规则生成的公式：①单个原子公式是合式公式。②若A是一个合式公式，则(lA)也是一个合式公式。③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(A

B)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。第24页，课件共113页，创作于2023年2月当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：①规定联结词的优先级由高到低的次序为：l、∧、∨、→、②相同的联结词按从左至右次序计算时，圆括号可省略。③最外层的圆括号可以省略。为了方便计，合式公式也简称公式。第25页，课件共113页，创作于2023年2月３. 公式真值表定义1.2.4

对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。定义1.2.5 如果B是公式A中的一部分，且B为公式，则称B是公式A的子公式。第26页，课件共113页，创作于2023年2月用归纳法不难证明，对于含有n个命题变元的公式，有2n个真值指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：①命题变元按字典序排列。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。第27页，课件共113页，创作于2023年2月4. 命题的符号化把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意下列事项:①确定给定句子是否为命题。②句子中连词是否为命题联结词。③要正确地表示原子命题和适当选择命题联结词。第28页，课件共113页，创作于2023年2月命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。第29页，课件共113页，创作于2023年2月1.3公式分类与等价公式１.公式分类定义1.3.1

设A为任意公式，则①对应每一个指派，公式A均相应确定真值为真，称A

为重言式，或永真式。②对应每一个指派，公式A均相应确定真值为假，称A

为矛盾式，或永假式。③至少存在一个指派，公式A相应确定真值为真，称A为可满足式。第30页，课件共113页，创作于2023年2月由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：①重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。②两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。③由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。第31页，课件共113页，创作于2023年2月判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。第32页，课件共113页，创作于2023年2月２. 等价公式定义1.3.2

设A和B是两个命题公式，如果A、B在其任意指派下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。显然，若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。第33页，课件共113页，创作于2023年2月在这里，请读者注意和的区别与联系。区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：可用下面定理表明之。第34页，课件共113页，创作于2023年2月定理1.3.1

A

B当且仅当AB是永真式。有时也称AB是永真双条件式。等价式有下列性质：①自反性，即对任意公式A，有A

A。②对称性，即对任意公式A和B，若A

B，则B

A。③传递性，即对任意公式A、B和C，若A

B、B

C，则A

C。第35页，课件共113页，创作于2023年2月３.基本等价式——命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。第36页，课件共113页，创作于2023年2月(3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等幂律：A∧AA，A∨AA。第37页，课件共113页，创作于2023年2月(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互补律：A∧AF，(矛盾律)A∨AT。(排中律)(11)条件式转化律：A→BA∨B，A→BB→A。第38页，课件共113页，创作于2023年2月(12)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)输出律：(A∧B)→CA→(B→C)。(14)归谬律：(A→B)∧(A→B)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。第39页，课件共113页，创作于2023年2月４.代入规则和替换规则在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。第40页，课件共113页，创作于2023年2月(1)代入规则定理1.3.2

在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。(2)替换规则定理1.3.3

设A1是合式公式A的子公式，若A1B1，并且将A中的A1用B1

替换得到公式B，则AB。称该定理为替换规则。满足定理1.3.3条件的替换，称为等价替换。第41页，课件共113页，创作于2023年2月代入和替换有两点区别：①代入是对原子命题变元而言的，而替换可对命题公式实行。②代入必须是处处代入，替换则可部分替换，亦可全部替换。第42页，课件共113页，创作于2023年2月1.4对偶式与蕴涵式１. 对偶式在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。第43页，课件共113页，创作于2023年2月定义1.4.1

在给定的仅使用联结词、∧和∨的命题公式A中，若把∧和∨互换，F和T互换而得到一个命题公式A*，则称A*为A的对偶式。显然，A也是A*的对偶式。可见A与A*互为对偶式。第44页，课件共113页，创作于2023年2月定理1.4.1(对偶定理)

设A和A*互为对偶式，P1，P2，…，Pn是出现A和A*

中的原子命题变元，则①A(P1，P2，…，Pn)A*(P1，P2，…，Pn)②A(P1，P2，…，Pn)A*(P1，P2，…，Pn)①表明，公式A的否定等价于其命题变元否定的对偶式；②表明，命题变元否定的公式等价于对偶式之否定。第45页，课件共113页，创作于2023年2月定理1.4.2

设A和B为两个命题公式，若AB则A*B*。有了等价式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。第46页，课件共113页，创作于2023年2月２.蕴涵式定义1.4.2

设A和B是两个命题公式，若A→B是永真式，则称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。联系：AB成立，其充要条件A→B是永真式。第47页，课件共113页，创作于2023年2月蕴涵式有下列性质：①自反性，即对任意公式A，有AA。②传递性，即对任意公式A、B和C，若AB，BC，则AC。③对任意公式A、B和C，若AB，AC，则A(B∧C)。④对任意公式A、B和C，若AC，BC，则A∨BC。第48页，课件共113页，创作于2023年2月这些性质的正确性，请读者自己验证。下面给出等价式与蕴涵式之间的关系。定理1.4.3

设A和B是两命题公式，AB的充要条件是AB且BA。第49页，课件共113页，创作于2023年2月３.蕴涵式证明方法除真值表外，还有两种方法：①前件真导后件真方法设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成立。因为欲证AB，即证AB是永真式。对于AB，除在A取真和B取假时，AB为假外，余下AB皆为真。所以，若AB的前件A为真，由此可推出B亦为真，则AB是永真式，即AB。第50页，课件共113页，创作于2023年2月②后件假导前件假方法设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。因为若A→B的后件B取假，由此可推出A取假，即推证了：BA。又因A→BB→A，故AB成立。第51页，课件共113页，创作于2023年2月1.5联结词的扩充与功能完全组１.联结词的扩充定义1.5.1

设P和Q是任两个原子命题，①由合取非联结词↑和P，Q连接成P↑Q，称它为P和Q的合取非式复合命题，读作“P合取非Q”。P↑Q的真值由命题P和Q的真值确定：当且仅当P和Q均为Ｔ时，P↑Q为Ｆ，否则P↑Q为Ｔ。“合取非”又常称为“与非”。第52页，课件共113页，创作于2023年2月②由析取非联结词↓和P，Q连接成P↓Q，称它为P和Q的析取非式复合命题，读作“P析取非Q”。P↓Q的真值由P和Q的真值确定：当且仅当P和Q均为Ｆ时，P↓Q为Ｔ，否则P↓Q为Ｆ。“析取非”又常称为“或非”。③由条件非联结词和P，Q连接成PQ，称它为P和Q的条件非式复合命题，读作“P条件非Q”。PQ的真值由P和Q的真值确定：当且仅当P为Ｔ而Q为Ｆ时，PQ为Ｔ；否则PQ为Ｆ。第53页，课件共113页，创作于2023年2月④由双条件非联结词把P，Q连接成PQ，称它为P和Q的双条件非式复合命题，读作“P双条件非Q”。PQ的真值由P和Q的真值确定：当且仅当P和Q的真值不同时，PQ为Ｔ，否则PQ为Ｆ。“双条件非”又常称为“异或”，也常用符号表示之。上面4个联结词构成的复合命题，其真值表如下：第54页，课件共113页，创作于2023年2月第55页，课件共113页，创作于2023年2月由表可知，①PQ(PQ) ②PQ(PQ) ③PQ(PQ) ④PQ(PQ)第56页，课件共113页，创作于2023年2月２.与非、或非和异或的性质与非、或非以及异或在计算机科学中是经常使用的3个联结词，因此，掌握它们的性质是十分必要的。令P、Q和R是原子命题变元。①与非的性质(a)P↑QQ↑P(b)P↑PP(c)(P↑Q)↑(P↑Q)P∧Q(d)(P↑P)↑(Q↑Q)P∨Q第57页，课件共113页，创作于2023年2月②或非的性质(a)P↓QQ↓P(b)P↓PP(c)(P↓Q)↓(P↓Q)P∨Q(d)(P↓P)↓(Q↓Q)P∧Q从上述的性质可知，联结词、和可分别用联结词或者取代，读者可以自行验证，和都不满足结合律。第58页，课件共113页，创作于2023年2月③异或的性质(a)PQQP(b)P(QR)(PQ)R(c)P∧(QR)(P∧Q)(P∧R)(d)PPF，FPP，TPP(e)若PQR，则QRP，PPQ，且PQRF。第59页，课件共113页，创作于2023年2月以上所有性质，用真值表或命题定律都是不难证明的。至此，已有了9个联结词，是否还需要扩充呢？事实上，两上命题变无P和Q，与9个联结词一共可构成 类命题公式，如下表示之：第60页，课件共113页，创作于2023年2月第61页，课件共113页，创作于2023年2月第62页，课件共113页，创作于2023年2月从列表可知，除命题常元F，T及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为，，，，等。第63页，课件共113页，创作于2023年2月３.联结词功能完全组已知有9个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有下列等价式：PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ)可见，扩充的4个联结词，，和能由原有5个联结词分别替代之。第64页，课件共113页，创作于2023年2月又由命题定律：PQ(PQ)(QP)PQPQPQ(PQ)PQ(PQ)可知，原有5个联结词，，，和又能由联结词组{，}或{，}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。第65页，课件共113页，创作于2023年2月定义1.5.2

称G为联结词功能完全组，如果G满足下列两条件：①由G中联结词构成的公式能等价表示任意命题公式；②G

中的任一联结词不能用其余下联结词等价表示。可以证明，{，}，{，}，{，}，{}，{}都是联结词功能完全组；而{，}，{}，{}，{}，{，}都不是联结词功能完全组，但为了表示方便，仍经常使用联结词组{，，}。第66页，课件共113页，创作于2023年2月1.6公式标准型——范式１.简单合取式与简单析取式定义1.6.1

在一公式中，仅由命题变元及其否定构成的合取式，称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。定义1.6.2在一公式中，仅由命题变元及其否定构成的析取式，称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。第67页，课件共113页，创作于2023年2月例如，公式P，Q，PQ和PQP等都是简单合取式，而P，Q和P为相应的简单合取式的合取项；公式P，Q，PQ，PQP等都是简单析取式，而P，Q和P为相应简单析取式的析取项。注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例中P，Q等。第68页，课件共113页，创作于2023年2月定理1.6.1

简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。定理1.6.2

简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。第69页，课件共113页，创作于2023年2月２.析取范式与合取范式定义1.6.3

一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取，即AAi；其中Ai为简单合取式，i=1，2，…，n。定义1.6.4

一个命题公式A称为合取范式，当且仅当A可表为简单析取式的合取，即AAi；其中Ai为简单析取式，1≤i≤n。第70页，课件共113页，创作于2023年2月定理1.6.3

对于任何一命题公式，都存在与其等价的析取范式和合取范式。求范式算法：①使用命题定律，消去公式中除、和以外公式中出现的所有联结词；②使用(P)P和德·摩根律，将公式中出现的联结词都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。第71页，课件共113页，创作于2023年2月３.范式的应用利用析取范式和合取范式可对公式进行判定。定理1.6.4

公式A为永假式的充要条件是A

的析取范式中每个简单合取式至少包含一个命题变元及其否定。定理1.6.5

公式A为永真式的充要条件是A

的合取范式中每个简单析取式至少包含一个命题变元及其否定。第72页，课件共113页，创作于2023年2月４.范式不唯一性第73页，课件共113页，创作于2023年2月1.7公式的主范式范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。第74页，课件共113页，创作于2023年2月１.主析取范式(1)小项的概念和性质定义1.7.1

在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。第75页，课件共113页，创作于2023年2月例如，两个命题变元P和Q，其构成的小项有PQ，PQ，PQ和PQ；而三个命题变元P、Q和R，其构成的小项有PQR，PQR，PQR，PQR，PQR

，PQR，PQR，PQR。可以证明，n个命题变元共形成2n个小项。第76页，课件共113页，创作于2023年2月如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个小项的真值表，可明显地反映出小项的性质。表1.7.1和表1.7.2分别给出了2个命题变元P和Q、3个命题变元P、Q和R的小项真值表。第77页，课件共113页，创作于2023年2月第78页，课件共113页，创作于2023年2月第79页，课件共113页，创作于2023年2月第80页，课件共113页，创作于2023年2月从表1.7.1，表1.7.2可看出，小项有如下性质：(a)没有两个小项是等价的，即是说各小项的真值表都是不同的；(b)任意两个不同的小项的合取式是永假的：mi∧mjＦ，i≠j。(c)所有小项之析取为永真：miＴ。(d)每个小项只有一个解释为真，且其真值1位于主对角线上。第81页，课件共113页，创作于2023年2月(2)主析取范式定义与存在定理定义1.7.2

在给定公式的析取范式中，若其简单合取式都是小项，则称该范式为主析取范式。定理1.7.1

任意含n个命题变元的非永假命题公式A

都存在与其等价的主析取范式。第82页，课件共113页，创作于2023年2月(3)主析取范式的求法主析取范式求法有两种：真值表法和公式化归法。定理1.7.1的证明已给出了用真值表求主析取范式的方法，而公式化归法给出如下：(a)把给定公式化成析取范式；(b)删除析取范式中所有为永假的简单合取式；第83页，课件共113页，创作于2023年2月(c)用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如P∧PP。(d)用同一律补进简单合取式中未出现的所有命题变元，如Q，则PP∧Q∨Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取范式。第84页，课件共113页，创作于2023年2月(4)主析取范式的惟一性定理1.7.2

任意含n个命题变元的非永假命题公式，其主析取范式是惟一的。第85页，课件共113页，创作于2023年2月２.主合取范式(1)大项的概念和性质定义1.7.3

在n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为大项，或布尔和。第86页，课件共113页，创作于2023年2月例如，由两个命题变元P和Q，构成大项有PQ，PQ，PQ，PQ；三个命题变元P，Q和R，构成PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。能够证明，n个命题变元共有2n个大项。第87页，课件共113页，创作于2023年2月如果将n个命题变元排序，并且把命题变元与０对应，命题变元的否定与１对应，则可对2n个大项按二进制数编码，记为Mi，其下标i是由二进制数化成的十进制数。用这种编码所求的2n个大项的真值表，能直接反映出大项的性质。表1.7.3给出了2个命题变元P和Ｑ构成所有大项的真值表。第88页，课件共113页，创作于2023年2月第89页，课件共113页，创作于2023年2月类似可给出３个命题变元Ｐ、Ｑ和Ｒ的所有大项的真值表，留给读者完成。从表1.7.3可看出大项的性质：(a)没有两个大项是等价的。(b)任何两个不同大项之析取是永真的，即Mi∨MjＴ，i≠j。(c)所有大项之合取为永假，即MiＦ。(d)每个大项只有一个解释为假，且其真值0位于主对角线上。第90页，课件共113页，创作于2023年2月(2)主合取范式的定义与其存在定理定义1.7.4

在给定公式的合取范式中，若其所有简单析取式都是大项，称该范式为主合取范式。定理1.7.3

任意含有n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。定理1.7.4

任意含n个命题变元的非永真命题公式A，其主合取范式是唯一的。上述两定理的证明，类似于定理1.7.1和定理1.7.2。第91页，课件共113页，创作于2023年2月主合取范式的求法也有两种，类似于主析取范式的求法。３.主析取范式与主合取范式之间的关系由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系：miMi

Mimi因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主命取范式。第92页，课件共113页，创作于2023年2月设命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项 ， ，…，，则A的主析取范式中必含有2n-k个小项，不妨含为，，…，，即A∨∨…∨。于是AA( ∨∨…∨ ) ∧∧…∧

∧∧…∧第93页，课件共113页，创作于2023年2月由此可知，从A的主析取范式求其主合取范式的步骤为：(a)求出A的主析取范式中设有包含的小项。(b)求出与(a)中小项的下标相同的大项。(c)做(b)中大项之合取，即为A的主合取范式。例如，(PQ)Qm1m3，则(PQ)QM0M2。第94页，课件共113页，创作于2023年2月４.主范式的应用利用主范式可以求解判问题或者证明等价式成立。（1）判定问题根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之：(a)若AＴ，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。第95页，课件共113页，创作于2023年2月(b)若AＦ，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。(c)若A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，则A为可满足的。（2）证明等价式成立由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。第96页，课件共113页，创作于2023年2月1.8命题逻辑的推理理论在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。第97页，课件共113页，创作于2023年2月在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。第98页，课件共113页，创作于2023年2月可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。第99页，课件共113页，创作于2023年2月１.推理的基本概念和推理形式推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,···,HnC，其中符号表示推出···。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。第100页，课件共113页，创作于2023年2月定义1.8.1

如果存在H1，H2，…，Hn，C的一个指派，使得每个Hi(1≤i≤n)为真而C为假推理形式H1，H2，…，HnC是无效的；否则，推理是有效的，此时称C是H1，H2，…，Hn的有效结论，或称C是从前提H1，H2，…，Hn逻辑推出的结论。定理1.8.1

推理形式H1，H2，…，HnC是有效的，当且仅当命题公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)C。第101页，课件共113页，创作于2023年2月２.推理规则在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，它们是：①Ｐ规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。②Ｔ规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。第102页，课件共113页，创作于2023年2月此外，在从前提推出的结论为条件式时，还需要下面规则：③ＣＰ规则(也称条件证明引入规则)：若推出有效结论为条件式R→C时，只需将其前件R加入到前提中作为附加前提且再去推出后件C即可。ＣＰ规则的正确性可由下面定理得到保证：定理1.8.2

若H1，H2，…，Hn，RC，则H1，H2，…，HnR→C。第103页，课件共113页，创作于2023年2月３.推理定律在推理过程中，除使用推理规则后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴涵式及运用定理1.8.1而得到。下面只给出了由蕴涵式得出的推理定律，它们是：(1)P，QP(2)P，QQ(3)PP∨Q(4)PP→Q第104页，课件共113页，创作于2023年2月(5)QP→Q(6)(P→Q)P(7)(P→Q)Q(8)P，(P→Q)Q(9)Q，(P→Q)P(10)P，(P∨Q)Q(11)(P→Q)，(Q→R)P→R(12)(PQ)，(QR)PR(13)(P→Q)，(R→S)，(P∧R)Q∧S第105页，课件共113页，创作于2023年2月(14)(P→Q)，(R→S)∧(P∨R)Q∨S特别当Q=S时，有(P→Q)，(R→Q)，(P∧R)Q(P→Q)，(R→S)，(P∨R)Q(15)P→Q(P∨R)→(Q∨R)P→Q(P∧R)→(Q∧R)此外，每个命题定律也可应得出两个推理定律，这些请读者补全。由于推理定律是确定有效结论的不可缺少的重要根据，因此要牢记并熟练运用它们。第106页，课件共1