第01章-离散数学

高等学校21世纪教材电子教案离散数学人民邮电出版社1/2/20241第一章 命题逻辑命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的根底，而命题逻辑又是谓词逻辑的根底。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为根本单位构成的前提和结论之间的可推导关系。退出1.1命题与联结词1.2命题变元和合式公式1.3公式分类与等价公式1.4对偶式与蕴涵式1.5联结词的扩充与功能完全组1.6公式标准型——范式1.7公式的主范式1.8命题逻辑的推理理论1.1 命题与联结词

１.命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感慨句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值—真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的根本单位。命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R…及其带下标的Pi，Qi，Ri，…表示。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。２.命题联结词 设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否认式复合命题，lP读“非P〞。称l为否认联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否认联结词“l〞的定义可由表1.1.1表示之。 由于否认〞修改了命题，它是对单个命题进行操作，称它为一元联结词。 设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表示之。 设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q〞。称∨为析取联结词。当且仅当P和Q的真值同为假，P∨Q的真值为假；否那么，P∨Q的真值为真。析取联结词∨的定义由表1.1.3表示之。由定义可知，析取联结词表示“可兼和〞，“不可兼和〞另有别的联结词定义之。与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有关例子就不再给出了。定义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表示之。在条件命题P→Q中，命题P称为P→Q的前件或前提，命题Q称为P→Q的后件或结论。条件命题P→Q有多种方式陈述：“如果P，那么Q〞；“P仅当Q〞；“Q每当P〞；“P是Q的充分条件〞；“Q是P的必要条件〞等。在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如例1.1.4中的①，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不单是出于“善意推断〞，主要是因为前提与结论间有无因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。 令P、Q是两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的双条件式复合命题，简称双条件命题，PQ读做“P当且仅当Q〞，或“P等价Q〞。称为双条件联结词。当P和Q的真值相同时，PQ的真值为真；否那么，PQ的真值为假。双条件联结词的定义由表1.1.5表示之。在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。1.2命题变元和合式公式１.命题变元在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下： 以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。2. 合式公式通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规那么可循。由这种定义产生的公式称为合式公式。 单个命题变元和命题常元称为原子命题公式，简称原子公式。 合式公式是由以下规那么生成的公式：①单个原子公式是合式公式。②假设A是一个合式公式，那么(lA)也是一个合式公式。③假设A、B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：①规定联结词的优先级由高到低的次序为：l、∧、∨、→、②相同的联结词按从左至右次序计算时，圆括号可省略。③最外层的圆括号可以省略。为了方便计，合式公式也简称公式。３. 公式真值表 对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。定义1.2.5 如果B是公式A中的一局部，且B为公式，那么称B是公式A的子公式。用归纳法不难证明，对于含有n个命题变元的公式，有2n个真值指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：①命题变元按字典序排列。②对每个指派，以二进制数从小到大或从大到小顺序列出。③假设公式较复杂，可先列出各子公式的真值(假设有括号，那么应从里层向外层展开)，最后列出所求公式的真值。4. 命题的符号化把一个用文字表达的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意以下事项:①确定给定句子是否为命题。②句子中连词是否为命题联结词。③要正确地表示原子命题和适中选择命题联结词。命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。1.3公式分类与等价公式１.公式分类 设A为任意公式，那么①对应每一个指派，公式A均相应确定真值为真，称A为重言式，或永真式。②对应每一个指派，公式A均相应确定真值为假，称A为矛盾式，或永假式。③至少存在一个指派，公式A相应确定真值为真，称A为可满足式。由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：①重言式的否认是矛盾式，矛盾式的否认是重言式，这样只研究其一就可以了。②两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。③由重言式使用公认的规那么可以产生许多有用等价式和蕴涵式。判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。２. 等价公式 设A和B是两个命题公式，如果A、B在其任意指派下，其真值都是相同的，那么称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。显然，假设公式A和B的真值表是相同的，那么A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。在这里，请读者注意和的区别与联系。区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：可用下面定理说明之。 AB当且仅当AB是永真式。有时也称AB是永真双条件式。等价式有以下性质：①自反性，即对任意公式A，有AA。②对称性，即对任意公式A和B，假设AB，那么BA。③传递性，即对任意公式A、B和C，假设AB、BC，那么AC。３.根本等价式——命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为根本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：(1)双否认：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。(3)结合律：(A∧B)∧C

A∧(B∧C)，(A∨B)∨C

A∨(B∨C)，(A

B)

C

A

(B

C)。(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∧A

A，A∨A

A。(7)同一律：A∧T

A，A∨F

A。(8)零律：A∧F

F，A∨T

T。(9)吸收律：A∧(A∨B)

A，A∨(A∧B)

A。(10)互补律：A∧

A

F，(矛盾律)A∨

A

T。(排中律)(11)条件式转化律：A→B

A∨B，A→B

B→

A。(12)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)输出律：(A∧B)→CA→(B→C)。(14)归谬律：(A→B)∧(A→B)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成局部，它们的正确性利用真值表是不难给出证明的。４.代入规那么和替换规那么在定义合成公式时，已看到了逻辑联结词能够从公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入〞和“替换〞，它们也有从公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容无视的。(1)代入规那么定理在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规那么。(2)替换规那么设A1是合式公式A的子公式，假设A1B1，并且将A中的A1用B1替换得到公式B，那么AB。称该定理为替换规那么。满足定理1.3.3条件的替换，称为等价替换。代入和替换有两点区别：①代入是对原子命题变元而言的，而替换可对命题公式实行。②代入必须是处处代入，替换那么可局部替换，亦可全部替换。1.4对偶式与蕴涵式１. 对偶式在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。在给定的仅使用联结词、∧和∨的命题公式A中，假设把∧和∨互换，F和T互换而得到一个命题公式A*，那么称A*为A的对偶式。显然，A也是A*的对偶式。可见A与A*互为对偶式。定理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的否认等价于其命题变元否认的对偶式；②说明，命题变元否认的公式等价于对偶式之否认。设A和B为两个命题公式，假设AB那么A*B*。有了等价式、代入规那么、替换规那么和对偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。２.蕴涵式设A和B是两个命题公式，假设A→B是永真式，那么称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。联系：AB成立，其充要条件A→B是永真式。蕴涵式有以下性质：①自反性，即对任意公式A，有AA。②传递性，即对任意公式A、B和C，假设AB，BC，那么AC。③对任意公式A、B和C，假设AB，AC，那么A(B∧C)。④对任意公式A、B和C，假设AC，BC，那么A∨BC。这些性质的正确性，请读者自己验证。下面给出等价式与蕴涵式之间的关系。设A和B是两命题公式，A

B的充要条件是A

B且B

A。３.蕴涵式证明方法除真值表外，还有两种方法：①前件真导后件真方法设公式的前件为真，假设能推导出后件也为真，那么条件式是永真式，故蕴涵式成立。因为欲证AB，即证AB是永真式。对于AB，除在A取真和B取假时，AB为假外，余下AB皆为真。所以，假设AB的前件A为真，由此可推出B亦为真，那么AB是永真式，即AB。②后件假导前件假方法设条件式后件为假，假设能推导出前件也为假，那么条件式是永真式，即蕴涵式成立。因为假设A→B的后件B取假，由此可推出A取假，即推证了：BA。又因A→BB→A，故AB成立。1.5联结词的扩充与功能完全组１.联结词的扩充设P和Q是任两个原子命题，①由合取非联结词↑和P，Q连接成P↑Q，称它为P和Q的合取非式复合命题，读作“P合取非Q〞。P↑Q的真值由命题P和Q的真值确定：当且仅当P和Q均为Ｔ时，P↑Q为Ｆ，否那么P↑Q为Ｔ。“合取非〞又常称为“与非〞。②由析取非联结词↓和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为Ｆ。④由双条件非联结词把P，Q连接成PQ，称它为P和Q的双条件非式复合命题，读作“P双条件非Q〞。PQ的真值由P和Q的真值确定：当且仅当P和Q的真值不同时，PQ为Ｔ，否那么PQ为Ｆ。“双条件非〞又常称为“异或〞，也常用符号表示之。上面4个联结词构成的复合命题，其真值表如下：由表可知，①P

Q

(P

Q) ②P

Q

(P

Q) ③P

Q

(P

Q) ④P

Q

(P

Q)２.与非、或非和异或的性质与非、或非以及异或在计算机科学中是经常使用的3个联结词，因此，掌握它们的性质是十分必要的。令P、Q和R是原子命题变元。①与非的性质(a)P↑Q

Q↑P(b)P↑P

P(c)(P↑Q)↑(P↑Q)

P∧Q(d)(P↑P)↑(Q↑Q)

P∨Q②或非的性质(a)P↓Q

Q↓P(b)P↓P

P(c)(P↓Q)↓(P↓Q)

P∨Q(d)(P↓P)↓(Q↓Q)

P∧Q从上述的性质可知，联结词

、

和

可分别用联结词

或者

取代，读者可以自行验证，

和

都不满足结合律。③异或的性质(a)PQQP(b)P(QR)(PQ)R(c)P∧(QR)(P∧Q)(P∧R)(d)PPF，FPP，TPP(e)假设PQR，那么QRP，PPQ，且PQRF。以上所有性质，用真值表或命题定律都是不难证明的。至此，已有了9个联结词，是否还需要扩充呢？事实上，两上命题变无P和Q，与9个联结词一共可构成 类命题公式，如下表示之：从列表可知，除命题常元F，T及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为

，

，

，

，

等。３.联结词功能完全组有9个联结词就够用了，能不能少呢？假设能少，说明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有以下等价式：PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ)可见，扩充的4个联结词，，和能由原有5个联结词分别替代之。又由命题定律：P

Q

(

P

Q)

(

Q

P)P

Q

P

QP

Q

(

P

Q)P

Q

(

P

Q)可知，原有5个联结词

，

，

，

和

又能由联结词组{

，

}或{

，

}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。称G为联结词功能完全组，如果G满足以下两条件：①由G中联结词构成的公式能等价表示任意命题公式；②G中的任一联结词不能用其余下联结词等价表示。可以证明，{，}，{，}，{，}，{}，{}都是联结词功能完全组；而{，}，{}，{}，{}，{，}都不是联结词功能完全组，但为了表示方便，仍经常使用联结词组{，，}。1.6公式标准型——范式１.简单合取式与简单析取式在一公式中，仅由命题变元及其否认构成的合取式，称该公式为简单合取式，其中每个命题变元或其否认，称为合取项。定义1.6.2在一公式中，仅由命题变元及其否认构成的析取式，称该公式为简单析取式，其中每个命题变元或其否认，称为析取项。例如，公式P，Q，PQ和PQP等都是简单合取式，而P，Q和P为相应的简单合取式的合取项；公式P，Q，PQ，PQP等都是简单析取式，而P，Q和P为相应简单析取式的析取项。注意，一个命题变元或其否认既可以是简单合取式，也可是简单析取式，如例中P，Q等。简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否认。简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否认。２.析取范式与合取范式一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取，即A

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

Ai；其中Ai为简单析取式，1≤i≤n。对于任何一命题公式，都存在与其等价的析取范式和合取范式。求范式算法：①使用命题定律，消去公式中除

、

和

以外公式中出现的所有联结词；②使用

(

P)

P和德·摩根律，将公式中出现的联结词

都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。３.范式的应用利用析取范式和合取范式可对公式进行判定。公式A为永假式的充要条件是A的析取范式中每个简单合取式至少包含一个命题变元及其否认。公式A为永真式的充要条件是A的合取范式中每个简单析取式至少包含一个命题变元及其否认。４.范式不唯一性1.7公式的主范式范式根本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。１.主析取范式(1)小项的概念和性质在含有n个命题变元的简单合取式中，假设每个命题变元与其否认不同时存在，而二者之一出现一次且仅出现一次，那么称该简单合取式为小项，或布尔积。例如，两个命题变元P和Q，其构成的小项有P

Q，P

Q，

P

Q和

P

Q；而三个命题变元P、Q和R，其构成的小项有P

Q

R，P

Q

R，P

Q

R，P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R。可以证明，n个命题变元共形成2n个小项。如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否认与0对应，那么可对2n个小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个小项的真值表，可明显地反映出小项的性质。表1.7.1和表1.7.2分别给出了2个命题变元P和Q、3个命题变元P、Q和R的小项真值表。从表1.7.1，表1.7.2可看出，小项有如下性质：(a)没有两个小项是等价的，即是说各小项的真值表都是不同的；(b)任意两个不同的小项的合取式是永假的：mi∧mj

Ｆ，i≠j。(c)所有小项之析取为永真：mi

Ｔ。(d)每个小项只有一个解释为真，且其真值1位于主对角线上。(2)主析取范式定义与存在定理在给定公式的析取范式中，假设其简单合取式都是小项，那么称该范式为主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式。(3)主析取范式的求法主析取范式求法有两种：真值表法和公式化归法。定理1.7.1的证明已给出了用真值表求主析取范式的方法，而公式化归法给出如下：(a)把给定公式化成析取范式；(b)删除析取范式中所有为永假的简单合取式；(c)用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如P∧PP。(d)用同一律补进简单合取式中未出现的所有命题变元，如Q，那么PP∧Q∨Q)，并用分配律展开之，将相同的简单合取式的屡次出现化为一次出现，这样得到了给定公式的主析取范式。(4)主析取范式的惟一性任意含n个命题变元的非永假命题公式，其主析取范式是惟一的。２.主合取范式(1)大项的概念和性质在n个命题变元的简单析取式中，假设每个命题变元与其否认不同时存在，而二者之一必出现一次且仅出现一次，那么称该简单析取式为大项，或布尔和。例如，由两个命题变元P和Q，构成大项有P

Q，P

Q，

P

Q，

P

Q；三个命题变元P，Q和R，构成P

Q

R，P

Q

R，P

Q

R，P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R。能够证明，n个命题变元共有2n个大项。如果将n个命题变元排序，并且把命题变元与０对应，命题变元的否认与１对应，那么可对2n个大项按二进制数编码，记为Mi，其下标i是由二进制数化成的十进制数。用这种编码所求的2n个大项的真值表，能直接反映出大项的性质。表1.7.3给出了2个命题变元P和Ｑ构成所有大项的真值表。类似可给出３个命题变元Ｐ、Ｑ和Ｒ的所有大项的真值表，留给读者完成。从表1.7.3可看出大项的性质：(a)没有两个大项是等价的。(b)任何两个不同大项之析取是永真的，即Mi∨Mj

Ｔ，i≠j。(c)所有大项之合取为永假，即Mi

Ｆ。(d)每个大项只有一个解释为假，且其真值0位于主对角线上。(2)主合取范式的定义与其存在定理在给定公式的合取范式中，假设其所有简单析取式都是大项，称该范式为主合取范式。任意含有n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。任意含n个命题变元的非永真命题公式A，其主合取范式是唯一的。上述两定理的证明，类似于定理1.7.1和定理1.7.2。主合取范式的求法也有两种，类似于主析取范式的求法。３.主析取范式与主合取范式之间的关系由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有以下关系：miMiMimi因此，主析取范式和主合取范式有着“互补〞关系，即是由给定公式的主析取范式可以求出其主命取范式。设命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项 ， ，…，，那么A的主析取范式中必含有2n-k个小项，不妨含为，，…，，即A∨∨…∨。于是AA( ∨∨…∨ ) ∧∧…∧ ∧∧…∧由此可知，从A的主析取范式求其主合取范式的步骤为：(a)求出A的主析取范式中设有包含的小项。(b)求出与(a)中小项的下标相同的大项。(c)做(b)中大项之合取，即为A的主合取范式。例如，(PQ)Qm1m3，那么(PQ)QM0M2。４.主范式的应用利用主范式可以求解判问题或者证明等价式成立。〔1〕判定问题根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按以下条件判定之：(a)假设AＴ，或A可化为与其等价的、含2n个小项的主析取范式，那么A为永真式。(b)假设AＦ，或A可化为与其等价的、含2n个大项的主合取范式，那么A为永假式。(c)假设A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，那么A为可满足的。〔2〕证明等价式成立由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，假设主范式相同，那么给定两公式是等价的。1.8命题逻辑的推理理论在逻辑学中，把从前题〔又叫公理或假设〕出发，依据公认的推理规那么，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，那么有效结论也应该真而绝非假。在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规那么和论证原理，与这些规那么有关的理论称为推理理论。提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的符合逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。１.推理的根本概念和推理形式推理也称论证，它是指由命题得到新的命题的思维过程，其中命题称为推理的前提或假设，推得的新命题称为推理的结论。在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,···,HnC，其中符号表示推出···。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。如果存在H1，H2，…，Hn，C的一个指派，使得每个Hi(1≤i≤n)为真而C为假推理形式H1，H2，…，HnC是无效的；否那么，推理是有效的，此时称C是H1，H2，…，Hn的有效结论，或称C是从前提H1，H2，…，Hn逻辑推出的结论。推理形式H1，H2，…，HnC是有效的，当且仅当命题公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)C。２.推理规那么在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规那么，它们是：①Ｐ规那么(也称前提引入规那么)：在推导过程中，前提可视需要引入使用。②Ｔ规那么(也称结论引入规那么)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。此外，在从前提推出的结论为条件式时，还需要下面规那么：③ＣＰ规那么(也称条件证明引入规那么)：假设推出有效结论为条件式R→C时，只需将其前件R参加到前提中作为附加前提且再去推出后件C即可。ＣＰ规那么的正确性可由下面定理得到保证：假设H1，H2，…，Hn，RC，那么H1，H2，…，HnR→C。３.推理定律在推理过程中，除使用推理规那么后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴涵式及运用定理1.8.1而得到。下面只给出了由蕴涵式得出的推理定律，它们是：(1)P，QP(2)P，QQ(3)PP∨Q(4)PP→Q(5)Q

P→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)(P

Q)，(Q

R)

P

R(13)(P→Q)，(R→S)，(P∧R)

Q∧S(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)此外，每个命题定律也可应得出两个推理定律，这些请读者补全。由于推理定律是确定有效结论的不可缺少的重要根据，因此要牢记并熟练运用它们。４.判断有效结论的常用方法判断有效结论的常用方法有真值表法，演绎法和间接证法。下面分别讨论之。(1)真值表法根据给定前提H1，H2，…，