离散数学第一章命题逻辑

1离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此充分描述了计算机科学离散性的特点。离散数学包括数理逻辑、集合论、代数系统、图论等方面内容。离散数学(DiscreteMathematics)2第一篇数理逻辑数理逻辑：是用数学的方法来研究推理的规律，即引入一套符号体系的办法，所以又叫符号逻辑。推理判断概念思维的形式结构形式逻辑辩证逻辑逻辑学3本篇将要介绍的就是数理逻辑的两个最基本的内容：命题逻辑和谓词逻辑。4第一章命题逻辑5第一章命题逻辑

1.1命题及其表示法命题：能判断真假的陈述句。命题是一个陈述句，不能是祈使句、疑问句和感叹句。该陈述句所表达的内容可判断真假，非真即假，非假即真，不能无所谓真假。真值：作为命题的陈述句所表达的判断结果，称为命题的真值。真值只有两种取值：真或假，分别用符号1(或T)和0(或F)表示。6例：判断下列句子中哪些是命题。(1)5是素数。(2)雪是黑的。(3)2+3=5.(4)明年10月1日是晴天。(5)充分大的偶数等于两个素数之和(哥德巴赫猜想)。(6)x>3.(7)你去图书馆吗？(8)请不要吸烟！(9)天气真好啊！(10)我正在说慌。7命题表示法：可用字母P，Q，R…或带下标的字母，如P1，Q4…表示命题。例：P：今天下雨。

Q：今天是晴天。

R：雪是黑的。命题标识符：表示命题的符号。如上例中的P，Q和R就是标识符。8命题分类简单命题：不能分解为更简单命题的命题，又称为原子命题。复合命题：由原子命题、联结词和标点符号复合构成的命题。例：(1)黄色和蓝色都是常用的颜色。(2)李冰选学英语或法语。(3)如果4是偶数，则5也是偶数。(4)小王虽然没上过大学，但他自学成才。符号逻辑下，联结词也要符号化。91.2联结词一、否定联结词

一个命题P加上否定词，就形成了一个新的命题，读作“非P”或“P的否定”，记作┐P，符号“┐”称为否定联结词，它是个一元联结词。规定：若命题P的真值为1，那么┐P的真值就为0；若P的真值为0，那么┐P的真值就为1。P与其否定┐P之间的关系,可用下面的表格来表示。10P┐P0110例：P：昨天张三去看球赛了。

┐P：昨天张三没有去看球赛。若昨天张三去看球赛了，命题P是真的，那么新命题┐P必然是假的。反之，若命题P是假的，那么┐P就是真的。11注意：否定词的含义是否定被否定命题的全部，而不是一部分。例：A：张明和李红都是三好学生。

┐A？

┐A：张明和李红不都是三好学生。12二、合取联结词

设P、Q是两命题，复合命题“P并且Q”或“P与Q”，称为P与Q的合取式，记作P∧Q，符号“∧”称作合取联结词，是个二元命题联结词。规定：只有P和Q同时为真时，P∧Q为真，其他情况下，P∧Q的真值都是假。P∧Q的真值与构成它的命题P、Q的真值间的关系，可由下表所示。

13PQP∧Q000010100111例：P：教室里有10名女同学。

Q：教室里有15名男同学。不难看出，命题“教室里有10名女同学与15名男同学”，便可由P∧Q来描述了。14例：A：雪是黑的。

B：小李是大学生。

A∧B：雪是黑的且小李是大学生。需要指出，我们现在只考虑命题与命题之间的形式关系，而不顾及语句的含义，正如我们在研究语法规则时，只考虑句子的形式，而不考虑句子的意义。

合取有日常自然用语里的“和”、“与”、“并且”等含义。但逻辑联结词是自然用语中联结词的抽象，两者并不是等同的。

15如：这台机器质量很好，但是很贵。这句话的含义是说同一台机器质量很好而且很贵。若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话的逻辑表示就是P∧Q，尽管这句话里出现的联结词是“但是”。自然语言中的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”等都可以符号化为∧。另外，不要见到“与”或“和”就认为是合取联结词。如：王兰和李辉是朋友。16三、析取联结词设P、Q是两命题，复合命题“P或Q”称为P与Q的析取式，记作P∨Q，符号“∨”称为析取联结词，是一个二元命题联结词。

规定：当P、Q中有一取值为真时，P∨Q便为真。仅当P、Q均取假时,P∨Q方为假。P∨Q的真值与构成它的命题P、Q的真值关系可由下表所示。17PQP∨Q000011101111例：P：今天刮风。

Q：今天下雨。

P∨Q：今天刮风或者下雨。18例：A：2小于3。

B：雪是黑的。

A∨B：2小于3或者雪是黑的。由于“2小于3”为真，所以A∨B取值必为真，尽管“雪是黑的”这命题为假。注意：在自然语言中的“或”具有二义性，有时表示的是相容性或，有时表示的是不相容性或（即排斥或）。这就是自然语言的意思不确定性。为避免歧义，在将命题进行形式化的时候，我们就需要格外注意。19如：R：张三或者李四考了90分。

S：第一节课上数学或者上英语。对于R，张三和李四可能都考了90分。张三和李四中只要有一个考了90分，则命题R为真，若张三和李四都考了90分，R当然也为真。而对于S，第一节课不能既上数学又上英语，因此，若P表示“第一节课上数学”，Q表示“第一节课上英语”，当两个命题都真，S就不真了。在将命题进行形式化的时候，我们不能简单的符号化为P∨Q，而应采用其他形式。如可以写为(P∧┐Q)∨(┐P∧Q)。20四、条件联结词(蕴涵联结词)

设P、Q是两命题，复合命题“如果P，那么Q”或“若P则Q”，称为P与Q的条件式，记作P→Q，符号“→”称为条件联结词，是一个二元命题联结词。其中，P为条件式的前件(前项、条件)，Q为条件式的后件(后项、结论)。

规定：只有当P为真而Q为假时,P→Q为假。而P为真、Q为真或P为假、Q任意时，P→Q均取值为真。条件词“→”的定义如下表所示。21PQP→Q001011100111例：如果我得到这本小说，那么我今晚就读完它。例：若某动物是哺乳动物，则它必胎生。上述例子均可用条件命题P→Q表达。22条件词→与自然用语“如果…那么…”有一致的一面，可表示因果关系。然而当条件词连接两个意义毫不相干的命题时，逻辑上允许讨论P→Q，只要前件和后件满足P→Q为真的定义所规定的条件，我们便可说“P→Q为真”。但有些在自然用语中是不大使用的。如：如果地球停止了转动，则大熊猫产在中国。23又如：如果月亮从西边出来，则太阳也从西边出来。由定义这是一个真命题，但这使人感到有点不自然，既然月亮不会从西边出来，我们完全可以认为这个命题毫无用处或毫无意义。但是，我们感兴趣的主要是(数学)推理和证明的方法，在这种情况下，命题P→Q真的意义在于我们能从P真推出Q真，而没有必要追求从P假能推出什么来。24使用P→Q能描述推理。即P→Q为真时,只要P为真必有Q真,而不能出现P真而Q假。至于P为假时,Q取真取假都可以，这可理解为“善意的推定”。条件运算PQ表示的逻辑关系是：Q是P的必要条件。自然语言中可用PQ式表述命题格式还有：“只要P，就Q”、“因为P，所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”、“除非Q，否则非P”等。联结词→，较┐、∨、∧难于理解，然而它在逻辑中用于表示因果关系时又是最有用的。25五、双条件联结词(等价联结词)

设P、Q是两命题，复合命题“P当且仅当Q”或“P等值Q”，称作P与Q的双条件式，记作PQ，符号“”也可以记作“iff”，称为双条件联结词，又常称为同或⊙，是一个二元命题联结词。规定：只有当两个命题P、Q的真值相同时,PQ的真值方为真。而当P、Q的真值不同时，复合命题PQ为假。这个新命题的真值与P、Q真值间的关系，见下表。26PQPQ001010100111例：P：△ABC是等腰三角形。

Q：△ABC中有两个角相等。命题PQ就是“△ABC是等腰三角形当且仅当△ABC中有两个角相等”。显然就这个例子而言PQ为1。27

以上5种最基本、最常用、最重要的联结词可以组成一个集合{┐，∧，∨，，}，成为一个联结词集，可规定其运算的优先级为：┐，∧，∨，，，对于同一级者，先出现者先运算。281.3命题公式与翻译

命题常量：当命题标识符表示确定命题时。

命题变元：当命题标识符只表示任意命题的位置时。命题常量与命题变元都可以用P,Q,R…等表示，具体情况由上下文确定。命题变元不能确定真值，故不是命题。指派：当命题变元P用一个特定命题取代时，称为对P进行指派，这时才能确定其真值。原子变元：当命题变元表示原子命题时。29合式公式/命题公式：将命题变元用联结词和圆括号按一定的逻辑关系联结起来的符号串。

当使用联结词集{，∧，∨，，}时，合式公式（wff）定义如下：（1）单个命题变元是合式公式，并称为原子命题公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。（4）只有有限次地应用(1)~(3)形成的符号串才是合式公式。30合式公式也称为命题公式或命题形式，并简称为公式。例如，(PQ)，(P)等均为合式公式，而PQ∨R,(Pw)∧Q)等不是合式公式。为了减少使用括号的数量，约定最外层括号可以省略。所以，(R∧S)∨e，P等都是合式公式。如果规定了联结词运算的优先次序为：，∧，∨，，，则P∧QR也是合式公式。31上述归纳定义方式中的符号A，B不同于具体公式里面的P,Q,R等符号，可以用来表示任意的合式公式，属于元语言符号，而P,Q,R等属于对象语言符号。对象语言：用来描述研究对象的语言。元语言：用来描述对象语言的语言。32公式层次：（1）若公式A是单个的命题变项，则称A为0层合式公式。（2）称A是n+1(n≥0)层公式是指下列情况之一：

(A)A=B,B是n层公式；(B)A=B∧C,其中B,C分别为i层和j层公式,且n=mAx(i,j);(c)A=B∨C,其中B,C的层次及n同(B);(d)A=BC,其中B,C的层次及n同(B);(e)A=BC,其中B,C的层次及n同(B);（3）若公式A的层次为k，则称A是k层公式。33例:公式PPQ(P

Q)∧R((PQ)(QP))的层次分别为0、1、3、4341.4真值表与等价公式

赋值/指派：设P1，P2，…，Pn是出现在公式A中的全部命题变元，给P1，P2，…，Pn各指定一个真值，称为对公式A的一个赋值。若指定的一组值使A的真值为1，则称这组值为A的成真赋值/指派，若使A的真值为0，则称这组值为A的成假赋值/指派。真值表：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。35PQQP

Q0011010110111100例1：构造P

Q的真值表。36例2：给出(P∧Q)∧P的真值表。PQP∧QP(P∧Q)∧P0001001010100001110037例3：给出

(P∧Q)(P∨Q)PQP∧Q(P∧Q)PQP∨Q(P∧Q)(P∨Q)0001111101011011100101111110000138对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变元P1，P2，…，Pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。39由例2、例3可以看出，有一类公式不论命题变元作何种指派，其真值总为真（假），我们把这类公式记为1（0）。如(P∧Q)(P∨Q)为永真公式，可记为1，(P∧Q)∧P为永假公式，可记为0。40设A为任一命题公式，有如下分类重言式/永真公式：若无论对A的分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。矛盾式/永假公式：若无论对A的分量作怎样的指派，其对应的真值永为假，则称该命题为矛盾式或永假公式。可满足式：若A不是矛盾式，则称A为可满足式。A是可满足式的等价定义是：A至少存在一个成真赋值。41含有n个命题变元的公式，由合式公式的递归定义可以写出无穷多种形式。但含有n个命题变元的公式对应的真值表数量是不是也是无穷多呢？由真值表的构造方法可以计算，含有n个命题变元的公式对应的不同的真值表共有22n种。所以，有很多公式有着相同的真值表。42等价：给定两个命题公式A和B，设P1，P2，…，Pn为所有出现于A和B中的原子变元，若给P1，P2，…Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的，记作：AB。真值表法证明公式等价例１：证明P∨QP→Q（板书）43PQP→QQ→PPQ(P→Q)∧(Q→P)001111011000100100111111由表可知PQ与(P→Q)∧(Q→P)等价，命题得证。例２：证明PQ(P→Q)∧(Q→P)证明：列出真值表44例３：证明PQ(P∧Q)∨(P∧

Q)证明：列出真值表PQP∧

QP

QP∧

QPQ(P∧Q)∨(P∧

Q)00011111010100001000100011100011由表可知PQ与(P∧Q)∨(P∧

Q)等价，命题得证。45例４：证明(PQ)(P∧

Q)∨(P∧Q)

需要记忆的16组重要的等价公式（命题定律）1.双重否定律

A¬¬A2.幂等律

A∧AA，A∨AA3.交换律

A∨BB∨A，A∧BB∧A

A↔BB↔A4.结合律 (A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)5.分配律

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

A∨(B∧C)(A∨B)∧(A∨C)466.德摩根律¬(A∨B)¬A∧¬B

¬(A∧B)¬A∨¬B7.吸收律

A∨(A∧B)A，A∧(A∨B)A8.零律

A∨11，A∧009.同一律A∨0A，A∧1A10.排中律

A∨¬A111.矛盾律

A∧¬A012.条件式转化律

A→B¬A∨B

13.双条件等价式

A↔B(A→B)∧(B→A)

(A∧B)∨(A∧

B)14.假言易位

A→B¬B→¬A4715.双条件否定等价式A↔B¬A↔¬B16.归谬论(A→B)∧(A→¬B)¬A48例５：验证分配律、吸收律。证明公式等值法一：真值表法法二：等价演算等价演算：由已知的等值式和置换规则推演出其他等值式的过程。49如果Ｘ是合式公式A的一部分，且Ｘ本身也是一个合式公式，则称Ｘ为公式A的子公式。Th1(置换/替换规则)

设Ｘ是合式公式A的子公式，若ＸY，如果将A中的X用Y来置换，所得到的公式B与公式A等值，即AB。证：因为在相应变元的任一种指派下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应变元的指派情况下，其真值亦必相同，故AB。满足Th1的置换称为等值置换/等值代换。50Th2(代入规则)一个重言式，对同一分量都用同一合式公式代入，其结果仍为一个重言式。证：由于重言式的真值与分量的指派无关，故对同一分量以任何公式代入后，重言式的真值仍永为Ｔ。51例：验证P(QR)(P∧Q)R证：右边(P∧Q)∨R(条件式转化律)

P∨Q∨R(德摩根律、置换规则)

P∨(Q∨R)(结合律)

P∨(QR)(条件式转化律、置换规则)

P(QR)(条件式转化律)52Th2

设A、B为两个命题公式，AB当且仅当AB为一个重言式。证：若AB，则A、B在任一组真值指派下，真值都相同，那A、B有相同真值，所以AB永为1。

若AB为重言式，则AB永为1，故A、B的真值相同，即AB。Th3

设A,B,C是命题公式，如果AB且BC，则AC。531.5对偶式与蕴涵式

对偶式：设A为命题公式，A中仅有联接词¬，∧，∨。在A中将∧和∨互换，若有F和T也互换，所得新公式A*称为原公式A的对偶式。例：书上第16页。54Th1(对偶定理)

设公式A(P1，P2，...，Pn)的对偶式为A*(P1，P2，...，Pn)，其中P1，P2，...，Pn

是A中不同的变元，n是正整数。则A(P1，P2，...，Pn)

A*(P1,P2,...,Pn)

A(P1,P2,...,Pn)

A*(P1，P2，...，Pn)

证明：由德·摩根定律P∧Q(

P∨Q)，P∨Q(

P∧Q)故A(P1，P2，...，Pn)

A*(P1,P2,...,Pn)

同理，A(P1,P2,...,Pn)

A*(P1，P2，...，Pn)55Th2(对偶定理)设A*,B*分别是命题公式A,B的对偶式，如果AB，则A*

B*。证明：因为AB，即A(P1,P2,...,Pn)B(P1,P2,...,Pn)是一个重言式，故

A(P1,P2,...,Pn)B(P1,P2,...,Pn)也是一个重言式。即A(P1,P2,...,Pn)B(P1,P2,...,Pn)。由Th1，得A*(P1,P2,...,Pn)

B*(P1,P2,...,Pn)，因此A*

B*.56蕴含：当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作PQ。对于P→Q来说，Q→P称作它的逆换式，P→Q称为它的反换式，

Q→

P称为它的逆反式。由真值表，易得(P→Q)(Q→

P)

(Q→P)(P→

Q)57证明PQ的方法法一：用真值表法或推导法证明P→Q为重言式，即P→QT。法二：用分析法，有两种分析方法：1)假设前件P为Ｔ时，推出后件Q也为Ｔ，则PQ;2)假设后件Q为Ｆ时，推出前件P也为Ｆ，则PQ。因为对于P→Q来说，只有一种真值指派，即P取Ｔ、Q取Ｆ时，P→Q为Ｆ。其余情况下P→Q均为Ｔ。58例：试证

Q∧(P∨Q)P。证法１：设前件

Q∧(P∨Q)为T，则

Q和(P∨Q)为T，由

Q为T，知Q为F，P∨Q为T，知P为T，即后件为T。证法２：设后件P为F，则P∨QQ，则Q∧(P∨Q)Q∧QF，即前件为F。16个重要的蕴含式，参见课本第18，19页。59正如和→有关系

PQ(P→Q)∧(Q→P)

一样，和也有类似的关系。Th4

设P、Q为任意两个公式，PQ的充分必要条件是PQ且QP。(该定理也可作为等价的定义)证：若PQ，则PQ为重言式，又由PQ(P→Q)∧(Q→P)，故(P→Q)∧(Q→P)要为T，故(P→Q)为T且(Q→P)为T，即PQ且QP。若PQ且QP，则(P→Q)为T且(Q→P)为T，即(P→Q)∧(Q→P)为T，故PQ为T，即PQ。60蕴含的5条常用性质设A、B、C为合式公式，若AB且A是重言式，则Ｂ必是重言式。自反性，即对任意公式A，有A

A传递性，即若AB，BC，则AC，蕴含关系是传递的。若AB，且AC，那么A(B∧C)。若AB且CB，则A∨CB。61Def1合取非，与非（）：由定义可知PQ(P∧Q)PQPQ0010111011101.6其他联结词

62Def2析取非，或非（）：PQ

(P∨Q)PQPQ00101010011063

cDef3

条件非，条件否定（）：PQcPQ000010101110c由定义可知PQ(PQ)64PQ

____PVQ000011101110

c

_____Def4双条件非，异或⊕，不可兼析取Ｖ：—------P∨Q(PQ)

—------P∨Q(P∧

Q)∨(P∧Q)

65性质：第20,21页Th1

设P、Q、R为命题公式。如果———————————————————P∨QR，则P∨RQ，Q∨RP，且—————————————P∨Q∨R为一矛盾式。证明（板书）66我们一共学了九个联结词{，∧，∨，

—

c，，∨，，，}。两个命题变元可构成２４个不等价的命题公式。它们可用命题常量T或F、命题变元本身及命题联结词表示如下。67PQFP∧Q

CPQP000000010000100011110101表１68PQ

CQPQ

—P∨QP∨Q000000011111100011110101表２69PQPQPQQQP001111010000100011110101表３70PQPPQPQT001111011111100011110101表４71联结词的完备集：设S是一个联结词集合，如果任何命题公式都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理

S={，∧，∨}是联结词的完备集。推论

以下联结词集都是完备集：（1）S1={，∧，∨，，}（2）S2={，∧，∨，}（3）S3={，∧}（4）S4={，∨}（5）S5={，}72最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换，而比这些联结词再少的命题公式不能对给定的公式作等价代换，这样的联结词组就是最小联结词组。

—

c{∨，，，，，∧，∨，，}中，{，∧}或{，∨}或{}或{}均是最小联结词组。证明731.7析取范式与合取范式——含n个命题变元的公式两种规范表示方法简单合取式/基本积：由命题变元或命题变元的否定组成的合取式P1

∧P2∧...∧Pn，其中Pi指Pi或者

Pi。如：P，Q，P∧Q，P∧Q∧R简单析取式/基本和：由命题变元或命题变元的否定组成的析取式P1∨P2∨...∨Pn，其中Pi指Pi或者

Pi。如：P，Q，P∨Q，P∨Q∨R74为方便起见，有时用Ai表示一个简单析取式或简单合取式。如设Ai为：P∨Q∨R∨S∨P或设Ai为：P∧Q∧R∧S∧PTh1一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定。一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定。75析取范式：由有限个简单合取式构成的析取式。如：P∨Q，(P∧Q)∨(P∧Q∧Q)合取范式：由有限个简单析取式构成的合取式。如：P∧Q，(P∨Q)∧(P∨Q∨R)范式：析取范式与合取范式统称为范式。76Th2(范式存在定理)任一个命题公式都存在着与之等值的析取范式与合取范式。化归过程：将公式中的联结词都化归成，∧，∨。利用德·摩根律将直接移到各个命题变元以前。利用分配律、结合律将公式归约为合取范式或析取范式。77说明：1)消去对{，∧，∨}来说冗余的联结词，即{，}。利用下列等值式：AB(A∨B)；AB(A∨B)∧(A∨B)2)否定词的消去或内移。利用下列等值式：AA；

(A∨B)A∧B；

(A∧B)

A∨B3)利用分配律：C∧(A∨B)(C∧A)∨(C∧B)；C∨(A∧B)(C∨A)∧(C∨B)78例1：求(PQ)R的析取/合取范式。解：原式((PQ)R)∧(R(PQ))((PQ)∨R)∧(R∨(PQ))((P∨Q)∨R)∧(R∨P∨Q)((P∧Q)∨R)∧(R∨P∨Q)(P∨R)∧(Q∨R)∧(R∨P∨Q)(合取范式)((P∧Q)∧(R∨P∨Q))∨(R∧(R∨P∨Q))(P∧Q∧R)∨(R∧P)∨(R∧Q)(析取范式)79例２：求(PQ)∧(PR)的析取/合取范式。解：原式(P∨Q)∧(P∨R)(合取范式)

((P∨Q)∧P)∨((P∨Q)∧R)

((P∧P)∨(Q∧P))∨((P∧R)∨(Q∧R))

(Q∧P)∨(P∧R)∨(Q∧R)(析取范式)例３：求(PQ)∨(P∧R)的析取/合取范式。解：原式

(P∨Q)∨(P∧R)

P∨Q∨(P∧R)(析取范式)(P∨Q∨P)∧(P∨Q∨R)(合取范式)(1∨Q)∧(P∨Q∨R)

(P∨Q∨R)(析取范式、合取范式)80极小项：在含有n个命题变元的简单合取式中，若每一个变元与其否定不同时存在，且每一个变元或其否定必出现且仅出现一次，则称该简单合取式为极小项。

极大项：在含有n个命题变元的简单析取式中，若每一个变元与其否定不同时存在，且每一个变元或其否定必出现且仅出现一次，则称该简单析取式为极大项。考虑：n个命题变元可产生多少个极小项或极大项？（２n）81观察真值表，可知对于每个极小项，如P1∧P2∧P3∧…∧Pn，有且仅有一种真值指派，使该小项真值为1，该极小项记作mi，其中i为成真指派对应的二进制数，或对应的十进制数。如：m00=P∧Q，m01=P∧Q，m10=P∧Q，m11=P∧Q，m010=P∧Q∧R=m2，m101=P∧Q∧R=m5，m111=P∧Q∧R=m7PQP∧QP∧QP∧QP∧Q00100001010010001011000182PQP∨QP∨QP∨QP∨Q001110011101101011110111观察下表，可知，对于每个极大项P1∨P2∨P3∨…∨Pn，有且仅有一种真值指派，使该极大项真值为0，该极大项记作Mi，其中i为成假指派对应的二进制数，或对应的十进制数。83如：M11=P∨Q，M10=P∨Q，M01=P∨Q，M00=P∨Q，M101=P∨Q∨R=M5，M010=P∨Q∨R=M2，M000=P∨Q∨R=M0Th3(极小项与极大项关系)

设mi和Mi是命题变元P1,P2,…,Pn形成的极小项和极大项，则

mi

Mi

，

Mi

miPQP∨QP∨QP∨QP∨Q00111001110110101111011184主析取范式：一个由极小项的析取组成的析取范式，如果与给定公式A等价，则把它叫做是公式A的主析取范式。主合取范式：一个由极大项的合取组成的合取范式，如果与给定公式A等价，则把它叫做是公式A的主合取范式。Th4任何命题公式都存在着与之等值的主析取范式和主合取范式，并且它们是唯一的。85命题公式向主析取范式的化归过程：化归为析取范式。除去析取范式中所有永假的简单合取式。将析取式中重复出现的简单合取式和相同的变元合并。对简单合取式补入没有出现的命题变元，即添加(P∨P)式，然后应用分配律展开公式，再去除相同的极小项。关键之处：

AiAi∧1Ai∧(Pj∨Pj)(Ai∧Pj)∨(Ai∧Pj)86命题公式向主合取范式的化归过程：化归为合取范式。除去合取范式中所有永真的简单析取式。将合取式中重复出现的析取项和相同的变元合并。对简单析取式补入没有出现的命题变元，即添加(P∧P)式，然后应用分配律展开公式，再除去相同的极大项。关键之处：

Ai

Ai∨0

Ai∨(Pj∧Pj)(Ai∨Pj)∧(Ai∨Pj)87例４：求(PQ)R的主析取/主合取范式。解：(接例１)原式(P∧Q∧R)∨(R∧P)∨(R∧Q)(析取范式)(P∧Q∧R)∨(R∧P∧(Q∨Q))∨(R∧Q∧(P∨P))(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)(主析取范式)m1∨m3∨m4∨m7(主析取范式)88(接例１)原式(P∨R)∧(Q∨R)∧(R∨P∨Q)(合取范式)((P∨R)∨(Q∧Q))∧((Q∨R)∨(P∧P))

∧(R∨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)(主合取范式)M0∧M2∧M5∧M6(主合取范式)89例５：(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)∨(P∧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)∨(P∧Q∧R)

∨(P∧Q∧R)m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7

(主析取范式，成真指派：000、001、010、011、100、101、110、111)90(接上)(P∧(Q∨R))∨(P∨Q∨R)(P∨(P∨Q∨R))∧((Q∨R)∨(P∨Q∨R))(P∨P∨Q∨R)∧(Q∨R∨P∨Q∨R)1∧11(没有真值指派能使极大项为0，主合取范式记为1)91求任一公式的主析（合）取范式，除了用基本等价式推导出外，还可用真值表的方法予以写出。Th5

在真值表中，一个公式的真值为1的指派所对应的小项的析取，即为此公式的主析取范式。Th6

在真值表中，一个公式的真值为0的指派所对应的大项的合取，即为此公式的主合取范式。例：92设公式A中含有n个命题变元，则：（1）A为重言式A的主析取范式含全部2n个极小项。

A的主合取范式不含任何极大项，记A的主合取范式为1。（2）A为矛盾式

A的主合取范式含全部2n个极大项。

A的主析取范式不含任何极小项，记A的主析取范式为0。（3）A为可满足式

A的主析取范式至少含一个极小项。

A的主合取范式中极大项的个数一定小于2n。93若公式A中含有n个命题变元，且A的主析取范式含S个极小项，则A有S个成真指派/成真赋值，有2n-S个成假赋值。A的主析取范式含S个极小项，即Ami1∨mi2∨…∨miS，0≤ik≤2n-1，k=1,2,…,S。AMj1∧Mj2∧…∧MjT，0≤jk≤2n-1，k=1,2,…,T，T=2n-S。没出现的极小项为mj1

,

mj2

,…,mjT

,它们的下标的二进制表示为A的成真赋值，因而A的主析取范式为A=mj1∨mj2∨…∨mjT。94A

A

(mj1∨mj2∨…∨mjT)

mj1∧

mj2∧

…

∧

mjT

Mj1∧Mj2∧…∧MjT重申：

AB当且仅当A、B有相同的真值表或A、B有相同的主析(合)取范式。951.8推理理论

数理逻辑的主要任务是用数学的方法研究数学中的推理。推理：指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的。96有效推理：设H1，H2，…，Hn和C是命题公式，H1，H2，…，Hn是n个前提，C是结论，对于它们中出现的命题变项的任一组赋值，前提和结论的取值有以下四种情况：①H1∧H2∧…∧Hn为0，C为0。√②H1∧H2∧…∧Hn为0，C为1。√③H1∧H2∧…∧Hn为1，C为0。×④H1∧H2∧…∧Hn为1，C为1。√若或者H1∧H2∧…∧Hn为假，或者当H1∧H2∧…∧Hn为真时，C也为真，这时称由前提H1，H2，…，Hn推出C的推理是有效的或是正确的，记作H1∧H2∧…∧HnC，称C是这组前提H1，H2，…，Hn的有效结论，或称C可由H1，H2，…，Hn

逻辑的推出。97定理

前题H1，H2，…，Hn推出C的推理是有效的，即H1∧H2∧…∧HnC，当且仅当(H1∧H2∧…∧Hn)C为重言式。例：前提：P，PQ结论：Q(P∧(PQ))Q只需证明条件式(P∧(PQ))Q为重言式。论证的三种方法：真值表法等价演算法主析取范式法98真值表法例1：判断下列推理是否正确。今天小李或去网吧或去教室。他没去教室，所以他去网吧了。设P：小李去网吧。Q：小李去教室。则，前提：P∨Q，Q结论：P推理的形式结构：((P∨Q)∧Q)P990100(P∨Q)∧Q1110P∨Q1100P110((P∨Q)∧Q)PQQ101110101由真值表知((P∨Q)∧Q)P为重言式，所以((P∨Q)∧Q)P等价演算法((P∨Q)∧Q)P((P∨Q)∧Q)∨P(P∨Q)∨Q∨P(P∨Q)∨(P∨Q)110010组重要的蕴涵式(推理定律)，见课本35页。1.附加律AA∨B2.化简律A∧BA3.假言推理A∧(A→B)B4.拒取式¬B∧(A→B)¬A5.析取三段论¬A∧(A∨B)B6.假言三段论(A→B)∧(B→C)(A→C)7.等价三段论(A↔B)∧(B↔C)(A↔C)8.构造性二难(A∨C)∧(A→B)∧(C→D)B∨D

特殊形式(A∨¬A)∧(A→B)∧(¬A→B)B9.破坏性二难

(¬B∨¬D)∧(A→B)∧(C→D)(¬A∨¬C)10.合取A,BA∧B101判断推理是否正确的以上各方法，当推理中包含的命题变元较多时，演算量太大，给推理带来了困难。为此引入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或最终结论)。它有两种方法：直接推理和间接推理。1021.直接推理直接推理是由一组前提出发，利用一些公认的推理规则，根据已知的等价式或蕴含式，推演得到有效结论的方法。

P规则(前提引入规则)：前提在推导过程中的任何时候都可以引入使用。T规则(结论引入规则)：在推导中的任何步骤上所得的中间结论都可以引入推导过程中。置换规则：利用已知等价公式(命题定律)进行等价置换。与已知的蕴涵式(推理定律)相关的各规则。103例2：在自然推理系统中构造下列推理的证明。前提：P∨Q，QR，PS，S结论：R∧(Q∨P)证明：(1)PSP(2)SP(3)PT(1)，(2)I拒取式(4)P∨QP(5)QT(3)，(4)I析取三段论(6)Q

RP(7)RT(5)，(6)I假言推理(8)Q∨PT(4)E(9)R∧(Q∨P)T(7)，(8)I合取104例3：前提：QP,Q

S,ST,T∧R

结论：P∧Q证明：(1)T∧RP(2)TT(1)I化简(3)STP(4)(ST)∧(TS)T(3)E(5)TST(4)I化简(6)ST(2)，(5)I假言推理(7)Q

SP(8)(SQ)∧(QS)T(7)E(9)SQT(8)I化简(10)QT(6)，(9)I假言推理(11)QPP(12)PT(10)，(11)I假言推理(13)P∧QT(12)，(10)I合取105间接证法归谬法适用于此类蕴含式的证明：H1∧H2∧…∧HnC

(*)欲证明(*)式，只需将C作为前提，能推出矛盾来即可。因为：

(*)

(H1∧H2∧…∧Hn)

C为重言式

(H1∧H2∧…∧Hn)∨C为重言式

(H1∧H2∧…∧Hn∧

C)为重言式

H1∧H2∧…∧Hn∧

C为矛盾式(注：表示当且仅当)106例4：前提：PQ，R∨Q，R∧S结论：P证明：(1)

P结论的否定引入(2)PQP(3)QT(1)，(2)I假言推理(4)R∨QP(5)RT(3)，(4)I析取三段论(6)