离散数学及其应用01-数理逻辑课件

1、第1篇数理逻辑数理逻辑逻辑学分为辨证逻辑与形式逻辑两种 。用数学方法来研究推理的规律称为数理逻辑 现代数理逻辑分为四论、两演算四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。两演算：命题演算、谓词演算 第 1 章 命题逻辑 1.1 命题及其表示1.2 逻辑联结词 第 1 章 命题逻辑1.1 命题及其表示 定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的真值，常用 1 （或大写字母 T ）表示真，用 0 （或大写字母 F ）表示假。凡是与事实相符的陈述句即真值为真的命题称为真命题，而与事实不符合的陈

2、述句即真值为假的命题称为假命题。从这个定义可以看出命题有两层含义： (1) 命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题； (2) 这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。 第 1 章 命题逻辑1.1 命题及其表示例1：判断下列语句是否为命题，若是并指出其真值。 （ 1 ）北京是中国的首都。 真命题（ 2 ）2是偶数且3也是偶数。 假命题（ 3 ）2+2=5 。 假命题（ 4 ）请勿吸烟! 不是命题（ 5 ）乌鸦是黑色的吗？ 不是命题（ 6 ）这个小男孩多勇敢啊！ 不是命题（ 7 ）地球外的星球上存在生物 。是命题，真假值客观存在 （

3、 8 ）1+101=110。二进制中为真命题，二进制中为假命题（ 9 ）x + y=5。不是命题（10 ）我正在说谎。悖论 ，不是命题第 1 章 命题逻辑1.1 命题及其表示定义1.1.2 不能被分解为更简单的陈述语句的命题称为原子命题(Simple Proposition )。由两个或两个以上原子命题通过联结词组合而成的命题称为复合命题(Compound Proposition )。例1.1.1中的命题(1)(3)(7)(8)为原子命题，而命题(2)是复合命题，是由“2是偶数。”与“3是偶数。”两个原子命题由联结词“且”组成的，该命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词

4、的意义。像这样的联结词称为逻辑联结词（logical connectives）。 约定用大写字母P，Q，R，S等表示原子命题（为了避免与真值T及F混淆，建议不用T及F表示原子命题）。例如，用P表示“北京是中国的首都”，Q表示“5可以被2整除”等。 第 1 章 命题逻辑1.1 命题及其表示定义1.1.3 表示原子命题的符号称为命题标识符(Identifier)。定义1.1.4用一个确定的命题代入一个命题标识符（如P），称为对P进行指派（赋值，或解释）。如果命题标识符P代表命题常元则意味它是某个具体原子命题的符号化，如果P代表命题变元则意味着它可指代任何具体原子命题。本书中如果没有特别指明，通常来

5、说命题标识符P等是指命题变元，即可指代任何原子命题。 第 1 章 命题逻辑1.2 逻辑联结词 定义1.2.1 设P表示一个命题，P的否定(Negation)是一个新的命题，记为P（读作非P）。规定若P为1，则P为0；若P为0，则P为1。 P的取值情况依赖于P的取值情况，真值情况见表1-1。表1-1联结词“”的定义PP1001第 1 章 命题逻辑1.2 逻辑联结词定义1.2.2 设P、Q为两个命题，P和Q的合取(Conjunction)是一个复合命题，记为PQ（读作P与Q），称为P与Q的合取式。规定P与Q同时为1时，PQ为1，其余情况下，PQ均为0。日常用语中的“与”、“和”、“也”、“并且”、

6、“而且”、“既，又”、“一面，一面”等可用合取词表示。 联结词“”的定义见表1-2。PQPQ000010100111第 1 章 命题逻辑1.2 逻辑联结词定义1.2.3 设P、Q为两个命题，P和Q的析取(Disjunction)是一个复合命题，记为PQ（读作P或Q），称为P与Q的析取式。规定当且仅当P与Q同时为0时，PQ为0，否则PQ均为1。日常用语中的“或”，“要么要么”等可用析取词表示。表1-3 联结词“”的定义PQPQ000011101111第 1 章 命题逻辑1.2 逻辑联结词定义1.2.4 设P、Q为两个命题，P和Q的条件(Conditional)命题是一个复合命题，记为PQ（读作若

7、P则Q），其中P称为条件的前件，Q称为条件的后件。规定当且仅当前件P为1， 后件Q为0时，PQ为0，否则PQ均为1。日常用语中的“若则”，“如果那么”，“只有才”等可用条件词表示。 表1-4 联结词“”的定义PQPQ001011100111第 1 章 命题逻辑1.2 逻辑联结词定义1.2.5 设P、Q为两个命题，其复合命题PQ称为双条件(Biconditional)命题，PQ读作P当且仅当Q。规定当且仅当P与 Q真值相同时，PQ为1，否则PQ均为0。 表1-5联结词“”的定义PQPQ001010100111第 1 章 命题逻辑1.3 命题公式与翻译定义1.3.1 命题公式归纳定义如下：（1）单

8、个命题变元是命题公式；（2）如果A是命题公式，则A也是命题公式；（3）如果A和B是命题公式，则(AB)，(AB)，(AB)，(AB)均是命题公式；（4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。 定义是以递归的形式给出的，其中（1）称为基础，（2）、（3）称为归纳，（4）称为界限。定义中的符号A,B不同于具体公式里的P、Q、R等符号（一般P、Q、R来表示原子命题标识符），它可以用来表示任意的命题公式。 第 1 章 命题逻辑1.3 命题公式与翻译命题公式是没有真假的,如果把公式中的命题变元代以确定的命题命题

9、，则该公式便是一个命题，才有确定的真值。因此，对复合命题的研究可化为对公式的研究，今后我们将以公式为主要研究对象。为了减少命题公式中使用括号的数量，规定：（1）逻辑联结词的优先级别由高到低依次为、。（2）具有相同级别的联结词，按出现的先后次序进行计算，括号可以省略。（3）命题公式的最外层括号可以省去。例1.3.1 （PQ）R也可以写成PQR，（PQ）R也可写成PQR，（PQ）R）也可写成（PQ）R，而P（QR）中的括号不能省去。定义1.3.2 设B是命题公式A的一部分，且B也是命题公式，则称B为A的子公式。第 1 章 命题逻辑1.3 命题公式与翻译把一个文字描述的命题相应地写成由命题标识符、逻

10、辑联结词和圆括号表示的命题形式称为命题的符号化或翻译。命题符号化的一般步骤：（1）明确给定命题的含义；（2）找出命题中的各原子命题，分别符号化。（3）使用合适的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。把命题符号化，是不管具体内容而突出思维形式的一种方法。注意在命题符号化时，要正确地分析和理解自然语言命题，不能仅凭文字的字面意思进行翻译。第 1 章 命题逻辑1.3 命题公式与翻译例1.3.2 将下列用自然语言描述的命题符号化。（1）我和他既是弟兄又是同学。 解 令P：我和他是弟兄；Q：我和他是同学，则该语句可符号化为PQ。 （2）我和你之间至少有一个要去海南岛。 解 令P：

11、我去海南岛；Q：你去海南岛，则该语句可符号化为PQ。 （3）如果他没来见你，那么他或者是生病了，或者是不在本地。 解 令P：他来见你；Q：他生病；R：他在本地，则该语句可符号化为P(QR)。 （4）n是偶数当且仅当它能被2整除。 解 令P：n是偶数；Q：n能被2整除，则该语句可符号化为PQ。第 1 章 命题逻辑1.3 命题公式与翻译（5）只有你走，我才留下。解这个命题的意义也可以理解为：如果我留下了，那么你一定走了。令P：你走。Q：我留下。则该语句可符号化为：QP。与原命题类似的命题如：仅当你走我才留下。我留下仅当你走。当我留下你得走。（6）仅当天不下雨且我有时间，我才上街。解设P：天下雨。Q

12、：我有时间。R：我上街。该语句可符号化为：R（PQ）。第 1 章 命题逻辑1.3 命题公式与翻译（7）你将失败，除非你努力。解这个命题的意义可以理解为：如果你不努力，那么你将失败。令P：你努力。Q：你失败。则该语句可符号化为：PQ。含有“除非”的命题，“非”是充分条件，译成条件命题时，“非”是条件的前件。（8）A中没有元素，A就是空集。解令P：A中有元素。Q：A是空集。则该语句可符号化为：PQ。（9）张三与李四是表兄弟。解此命题是一个原子命题，“与是表兄弟。”表示两个对象之间的关系。“张三是表兄弟。”及“李四是表兄弟。”都不是命题。所以上述命题只能符号化为P的形式。其中P：张三与李四是表兄弟。

13、 第 1 章 命题逻辑1.4 真值表与命题公式分类 定义1.4.1 设P1，P2，Pn是出现在命题公式中的全部命题变元，给P1，P2，Pn各指定一个真值，称为对公式的一个赋值（或解释或真值指派）。若指定的一组值使公式的真值为1，则这组值称为公式的成真赋值。若指定的一组值使公式的真值为0，则这组值称为公式的成假赋值。定义1.4.2 设A是含有n个命题变元的命题公式，将命题公式A在所有赋值之下取值的情况汇列成表，称为命题公式A的真值表。为方便构造真值表，特约定如下： 命题变元按字典序排列。 对每组赋值，以二进制数从小到大或从大到小顺序列出。 若公式较复杂，可先列出各子公式的真值(若有括号，则应从里

14、层向外层展开)，最后列出所求公式的真值。 第 1 章 命题逻辑1.4 真值表与命题公式分类 例1.4.1 利用真值表求命题公式(P(QR)的成真赋值和成假赋值。 PQRQRP(QR) (P(QR)000011110011001101010101011101111111011100001000第 1 章 命题逻辑1.4 真值表与命题公式分类例1.4.2利用真值表求命题公式（PQ）Q的成真赋值和成假赋值。PQPQ（PQ）（PQ）Q00100011001001011100第 1 章 命题逻辑1.4 真值表与命题公式分类利用真值表求命题公式（PQ）（PQ）的成真赋值和成假赋值。 PQPQ（PQ）PQ（

15、PQ）（PQ）000111010111100111111001第 1 章 命题逻辑1.4 真值表与命题公式分类定义1.4.3 设A为任一命题公式。 （1）若对公式A的命题变元所有赋值均是成真指派，则公式A称为重言式或永真式； （2）若对公式A的命题变元所有赋值均是成假指派，则公式A称为矛盾式或永假式； （3）若公式A中至少有一个成真赋值，则公式A称为可满足式。 从定义不难看出以下几点： 1）重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假指派，则称A为非重言式的可满足式。 2）真值表可用来判断公式的类型： 若真值表最后一列全为1，则公式为重言式； 若真值表最后一

16、列全为0，则公式为矛盾式； 若真值表最后一列中至少有一个1，则公式为可满足式。 第 1 章 命题逻辑1.4 真值表与命题公式分类例1.4.4 判断下列公式的类型。（1）(PQ)Q重言式 （2）(QP) (PQ) 矛盾式 (3)(PQ)(PQR)可满足式 从以上的讨论可知，真值表不但能准确地给出公式的成真赋值和成假赋值，而且能判断公式的类型。但当命题变元较多时，计算量大，在后面的章节中还要介绍其他的方法。 第 1 章 命题逻辑1.5 等价公式与蕴含式 定义1.5.1 给定两个命题公式A和B，设P1，P2，Pn是出现在命题公式A和B中的全部命题变元，若对所有命题变元P1，P2，Pn任一组赋值，公式

17、A和B的真值都对应相同，则称公式A与B等价或逻辑相等(Equivalence)，记作式AB。 定理1.5.1 对命题公式A和B，AB当且仅当AB是重言式。证明 若AB是重言式，则在任一解释下，AB的真值都为真。依AB的定义知，当AB为真时，A和B必有相同的真值。于是，在任一解释下，A和B都有相同的真值，从而有AB。反过来，若AB，则在任一解释下A和B都有相同的真值，依AB的定义知，此时AB为真，从而AB是重言式。 第 1 章 命题逻辑1.5 等价公式与蕴含式需要注意的是，“”不是逻辑联结词，因而“AB”不是命题公式，只是表示两个命题公式之间的一种等价关系，即若AB，A和B没有本质上的区别，最多

18、只是A和B具有不同的形式而已。“”具有如下的性质：（1）自反性：AA。（2）对称性：若AB，则BA。（3）传递性：若AB，BC，则AC。给定n个命题变元，根据公式的形成规则，可以形成许多个形式各异的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等价的概念，其目的就是将复杂的公式简化。 第 1 章 命题逻辑1.5 等价公式与蕴含式下面介绍两种证明公式等价的方法。1真值表法由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。例1.5.1 证明PQ(PQ)(QP)证明 命题公式PQ与(PQ)(QP)的真值表见表1-12。由表1-12可知，在任意赋值下PQ与(PQ)(QP)两者

19、的真值均对应相同。因此 PQ(PQ)(QP)表1-12 PQ与(PQ)(QP)的真值表PQPQQP(PQ)(QP)PQ001111011000100100111111第 1 章 命题逻辑1.5 等价公式与蕴含式常用等价式（1）双重否定律： PP（2）结合律： (PQ)RP(QR)，(PQ)RP(QR)，(PQ)RP(QR)（3）交换律： PQQP，PQQP，PQQP（4）分配律： P(QR) (PQ) (PR)， P(QR) (PQ) (PR)（5）幂等律： PPP，PPP（6）吸收律： P(PQ)P，P(PQ)P（7）德.摩根律：(PQ)PQ，(PQ)PQ（8）同一律： P0P，P1P（9）

20、零律： P11，P00第 1 章 命题逻辑1.5 等价公式与蕴含式常用等价式（10）否定律： PP1，PP0（11）蕴含律： PQPQ（12）等价律： PQ( PQ)(QP) PQ（13）输出律：(PQ)RP(QR)（14）归谬律：(PQ)(PQ) P（15）逆反律：PQQP第 1 章 命题逻辑1.5 等价公式与蕴含式2等值演算法定理1.5.2（代入规则）在一个永真式A中，任何一个原子命题变元R出现的每一处用另一个公式代入，所得的公式B仍为永真式。证明：因为永真式对于任何指派，其真值都是1，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元R出现的每一处，所得到的命题公式的真

21、值仍为1。定理1.5.3（置换规则） 设X是命题公式A的一个子公式，若XY，如果将公式中的X用Y来置换，则所得到的公式B与公式A等价，即AB。证明：因为XY，所以在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下真值也必相同，因此AB。 第 1 章 命题逻辑1.5 等价公式与蕴含式有了上述的15组等价公式及代入规则和置换规则后，就可以推演出更多的等价式。由已知等价式推出另外一些等价式的过程称为等值演算(Equivalent Calculation)。 例1.5.3 证明下列公式等价。 （1）(PQ)RP(QR)（2）(PQ) (PQ) (PQ)(

22、PQ)证明 （1） (PQ)R PQRP(QR) P(QR)P (QR) （2） (PQ) (PQ) (PQ) P)( (PQ) Q) (PP)( QP)(PQ)( QQ) 1( P Q)(PQ)1 (PQ) ( P Q) (PQ) (PQ) 第 1 章 命题逻辑1.5 等价公式与蕴含式等值演算还可以用来解决常见的推理题。例1.5.4 某件事情是甲、乙、丙、丁4人中某一个人干的。询问4人后回答如下：（1）甲说是丙干的；（2）乙说我没干；（3）丙说甲讲的不符合事实；（4）丁说是甲干的。若其中3人说的是真话，一人说假话，问是谁干的？例1.5.5 A、B、C、D 4人进行百米竞赛，观众甲、乙、丙对比

23、赛的结果进行预测。甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙每个人的预测结果都各对一半。试问实际名次如何（假如无并列者）？第 1 章 命题逻辑1.5 等价公式与蕴含式蕴含式定义1.5.2 设A、B为两个命题公式，若AB为重言式，则称“A蕴含( Implication)B”，记作AB。 蕴含关系具有如下的性质：(1) A为重言式，AB，则B必为重言式；(2) 自反性 AA；(3) 反对称性 若AB且 BA 则AB；(4) 传递性 若AB且 BC 则AC； (5) 若A B且 A C 则A B C 。(6) 若AB且CB，故A CB。第 1 章 命题逻辑1

24、.5 等价公式与蕴含式定理1.5.4 AB的充分必要条件是AB且BA。证明：若AB，则AB为重言式，而AB(AB)( BA)，故AB且BA均为重言式，即AB且BA。反之，若AB且BA，则AB且BA均为重言式，于是(AB)( BA)为重言式，即AB为重言式，故AB。要证明AB，只需证明AB为重言式即可。因此，前面介绍的真值表法和等值演算法均可应用。 第 1 章 命题逻辑1.5 等价公式与蕴含式证明AB的各种方法 1真值表法2等值演算法3逻辑分析法逻辑分析法包括以下两种形式：（1）肯定前件法：假定前件A为真，推出后件B为真，则AB。（2）否定后件法：假定后件B为假，推出前件A为假，则AB。理由是：

25、对于条件式AB，根据条件联结词的运算规则可知： 只有前件A为真，后件B为假时AB为假，其余情况均为真。第 1 章 命题逻辑1.5 等价公式与蕴含式因此有（1）若从假设前件A为真时能推导出后件B一定也为真，说明无论前件A为真为假，AB都为真，即AB为重言式，也即AB。（2）若从假设后件B为假时能推导出前件A一定也为真，说明无论前件A为真为假，AB都为真，即AB为重言式，也即AB。 第 1 章 命题逻辑1.5 等价公式与蕴含式例1.5.8 逻辑证明下列蕴含式。（1）Q(PQ)P（2）P (PQ)Q证明 （1）假设前件Q(PQ)为真，则Q为真，PQ为真；由此有Q为假，P为真。因此Q(PQ)P。（2）

26、假设后件Q为假，若P为真，则PQ为假，有P (PQ)为假。若P为假，则PQ为真，有P (PQ)为假。综上，若后件Q为假，无论P为真还是假，前件P (PQ)均为假。因此P (PQ)Q。第 1 章 命题逻辑1.5 等价公式与蕴含式常用的蕴含式 (1) PQP，PQQ；(2) PPQ，QPQ；(3) P PQ；(4) QPQ；(5) (PQ)P；(PQ)Q；(6) P(PQ)Q； (7) Q(PQ)P；(8) P(PQ)Q ；(9) (PQ)(QR) PR；(10) (PQ)(PR) (QR) R；(11) (PQ) (RS)(PR)(QS)；(12) (PQ) (Q R) P R第 1 章 命题逻

27、辑1.7 对偶与范式 对偶式定义1.7.1 在只含有逻辑联结词，的命题公式A中，若把将换成，换成，如果A中有T（或1）或者F（或0）就分别换成F（或0）或T（或1），所得到的新公式A* 称为A的对偶式(Dualistic Formula)。显然A*与A互为对偶式。例1.7.1 写出下列公式的对偶式。(1) (PR)(PQRQ)；(2) (PQ)F；(3) P(QT)解 (1) 令A=(PR)(PQRQ)，则 A=(PR)(PQ)RQ)。故 A* =(PR)(PQ)RQ)。(2)，(3)中二式的对偶式分别为(PQ)T，P(QF)。第 1 章 命题逻辑1.7 对偶与范式对偶原理 定理1.7.1设P

28、1，P2，P n 是公式A和A*中出现的原子命题变元，现采用函数记法分别为 A(P1，P2，P n )，A*(P1，P2，P n )，则A(P1，P2，P n ) A*(P1，P2，P n)，A(P1，P2，P n)A*(P1，P2，P n )。定理1.7.2（对偶原理）设A，B为合式命题公式，若AB，则A*B* 。证明：设P1，P2，P n 是出现在A，B中的原子命题变元。因A(P1，P2，P n ) B(P1，P2，P n )，故A(P1，P2，P n ) B(P1，P2，P n )是重言式。即：A（P1，P2，P n）B(P1，P2，P n)是重言式，故A(P1，P2，P n)B(P1，

29、P2，P n)。由定理1.7.1有 A(P1，P2，P n) A*(P1，P2，P n )，B(P1，P2，Pn)B*(P1，P2，Pn )，由合式公式的等价具有传递性，可得 A*（P1，P2，Pn ）B*(P1，P2，Pn )。从而A*B*。第 1 章 命题逻辑1.7 对偶与范式命题公式的范式 1简单析取式与简单合取式定义1.7.2 单个的命题变元及其否定形式称为文字。如P，Q等。定义1.7.3 仅由有限个文字组成的析取式称为简单析取式。仅由有限个文字组成的合取式称为简单合取式。例如P Q，PQ，PQ ，PQ，P，Q等都是简单析取式；P Q，PQ，PQ，PQ，P，Q等都是简单合取式。一个文字

30、既是简单析取式，又是简单合取式。定理1.7.3 简单析取式是重言式当且仅当它同时含有某个命题变元及其否定形式。 定理1.7.4 简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定形式。 第 1 章 命题逻辑1.7 对偶与范式2析取范式与合取范式定义1.7.4 由有限个简单合取式组成的析取式称为析取范式（Disjunctive Normal Form）。亦即该公式具有形式A1A2An，其中Ai(i=1,2,n)为简单合取式。由有限个简单析取式组成的合取式称为合取范式（Conjunctive Normal Form）。亦即该公式具有形式B1B2Bm，其中Bj(j=1,2,m)为简单析取式。析

31、取范式与合取范式统称为范式。定理1.7.5（范式存在定理）任何一个命题公式都存在着与之等价的析取范式和合取范式。第 1 章 命题逻辑1.7 对偶与范式求任一公式的析取范式和合取范式的步骤：（1）利用蕴含等值式和等价等值式消去除，以外公式中出现的所有逻辑联结词。（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律、结合律将公式转化为合取范式或析取范式。例1.7.4求P(PQ)的合取和析取范式。解： P(PQ)P(PQ)P(P Q) （合析取范式）(PP)QTQ （合析取范式）TPP。 第 1 章 命题逻辑1.7 对偶与范式3范式的应用利用析取范式和合取范式可

32、以判定一个命题公式是重言式还是矛盾式。定理1.7.6 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。第 1 章 命题逻辑1.7 对偶与范式命题公式的主析取范式和主合取范式 1主析取范式定义1.7.5 在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，则称该简单合取式为极小项。第 1 章 命题逻辑1.7 对偶与范式表1-20 两个命题变元P和Q生成的4个极小项的真值表m（二进制）m00m01m

33、10m11PQPQPQPQPQ001000010100100010110001m（十进制）m0m1m2m3第 1 章 命题逻辑1.7 对偶与范式由真值表可得到极小项具有如下性质：（1）各极小项的真值表都不相同。（2）每个极小项当其真值指派与对应的二进制编码相同时，其真值为真，在其余2n-1种指派情况下，其真值均为假。（3）任意两个极小项的合取式是矛盾式。例如m0 m1(PQ) (PQ)0。（4）全体极小项的析取式为永真式。定义1.7.6 由若干个不同的极小项组成的析取式称为主析取范式(The Principal Disjunctive Normal Form )。与公式等价的主析取范式称为的主

34、析取范式。定理1.7.7 任意含n个命题变元的非永假式命题公式都存在着与之等价的主析取范式，并且其主析取范式是唯一的。 第 1 章 命题逻辑1.7 对偶与范式一个命题公式的主析取范式可通过两种方法求得，一是由公式的真值表得出，即真值表法；另一是由基本等价公式推出，即等值演算法。（1）真值表法定理1.7.8 在真值表中，命题公式A的真值为真的赋值所对应的极小项的析取即为命题公式A的主析取范式。 利用真值表法求主析取范式的基本步骤为：（1）列出公式的真值表。（2）将真值表中的最后一列中的1的赋值所对应的极小项写出。（3）将这些极小项进行析取。第 1 章 命题逻辑1.7 对偶与范式例1.7.8 利用

35、真值表法求（PQ）的主析取范式。解 （PQ）的真值表见表1-21。表1-21 （PQ）的真值表PQ（PQ）001011101110从表1-21中可以看出，该公式在其真值表的00行、01行、10行处取真值1，所以（PQ）m0 m1 m2（PQ）（PQ）（PQ）。第 1 章 命题逻辑1.7 对偶与范式例1.7.9用真值表法求 (PQ)R的主析取范式。解 (PQ)R的真值表见表1-22。表1-22(PQ)R的真值表PQRPQ(PQ)R0000000101010000110110000 101011101111111从表1-22中可以看出，该公式在其真值表的001行、011行、101行、110行和11

36、1行处取真值1，所以 (PQ)Rm1m3m5m6m7(PQR) (PQR) (PQR) (PQR) (PQR)。第 1 章 命题逻辑1.7 对偶与范式（2）等值演算法除了用真值表法来求一个命题公式的主析取范式外，还可以利用公式的等值演算方法来推导。具体的求解步骤如下：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为析取范式；（4）利用同一律消去矛盾的简单合取式； （5）利用等幂律消去相同的简单合取式以及简单合取式中相同的合取项；（6）利用同一律、分配律将不包含某一命题变元的简单合取

37、式置换为包含这一命题变元的简单合取式，直到每一简单合取式成为极小项为止。例如P QP Q (RR) ( PQR) ( PQR)。并将极小项按顺序排列。第 1 章 命题逻辑1.7 对偶与范式例1.7.11 求（PQ）Q的主析取范式。解 （PQ）Q （PQ）Q（PQ） Q（PQ） (PP) Q )（PQ） (P Q) (P Q)（PQ） (P Q)m1 m3 第 1 章 命题逻辑1.7 对偶与范式例1.7.12 求A=(PQ)(QR)(PR)的主析取范式。解 A=(PQ)(QR)(PR) (PQ)Q)( (PQ)R) (PR) （结合律，分配律）(Q (PR) (QR) (PR) （吸收律，分配律

38、）(Q (PR) (PR) （吸收律，交换律）(Q(PR) (PR) (PR) （分配律）(QP) ( QR) ( PR(PR) （分配律，结合律）(QP) ( QR) ( PRP) ( PRR) （分配律）(QP) ( QR) ( PR) （吸收律）(PQ(RR) (PP)QR) ( P(QQ)R) (交换律，同一律)(PQR) ( PQR) (PQR) (PQR) (PQR) (PQR)(PQR) ( PQR) (PQR) (PQR)m2 m3 m5 m7第 1 章 命题逻辑1.7 对偶与范式2主合取范式定义1.7.7 在含有n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而

39、二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左算起的第i位上(若命题变元无下标,则按字典顺序排序)，则称该简单析取式为极大项。 第 1 章 命题逻辑1.7 对偶与范式表1-24 两个命题变元P和Q生成的4个极大项的真值表M（二进制）M00M01M10M11P Q P QPQPQPQ0 001110 110111 011011 11110M（十进制）M0M1M2M3第 1 章 命题逻辑1.7 对偶与范式由真值表可得到极大项具有如下性质：1）各极大项的真值表都不相同。2）每个极大项当其真值指派与对应的二进制编码相同时，其真值为假，在其余2n-1种指派情况下，其真值均为真。3）任意两

40、个不同极大项的析取式是永真式。例如M0 M2(PQ) (PQ)1。4）全体极大项的合取式必为永假式。定义1.7.8 由若干个不同的极大项组成的合取式称为主合取范式(The Principal Conjunctive Normal Form)。与公式等价的主合取范式称为的主合取范式。定理1.7.9 任意含n个命题变元的非永真式命题公式都存在着与之等价的主合取范式，并且其主合取范式是唯一的。 第 1 章 命题逻辑1.7 对偶与范式与主析取范式的求解方法相类似，主合取范式同样可通过真值表法或等值演算法求得。（1）真值表法定理1.7.10 在真值表中，命题公式A的真值为假的赋值所对应的极大项的合取即为

41、命题公式A的主合取范式。证明方法与定理1.7.8的证明相类似。利用真值表法求主合取范式的基本步骤为：（1）列出公式的真值表。（2）将真值表中的最后一列中的0的赋值所对应的极大项写出。（3）将这些极大项进行合取。第 1 章 命题逻辑1.7 对偶与范式（2）等值演算法 具体的求解步骤如下：（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为合取范式；（4）利用同一律消去矛盾的简单析取式； （5）利用等幂律消去相同的简单析取式以及简单析取式中相同的析取项；（6）利用同一律、分配律将不包含某一

42、命题变元的简单析取式置换为包含这一命题变元的简单析取式，直到每一简单析取式成为极大项为止。例如P QPQ (RR) ( PQR) ( PQR)。将极大项按顺序排列。 第 1 章 命题逻辑1.7 对偶与范式3主析取范式和主合取范式关系设Z为命题公式A的主析取范式中所有极小项的足标集合，R为命题公式A的主合取范式中所有极大项的足标集合，则有 R0,1,2, ,2n-1Z或 Z0,1,2, ,2n-1R。故已知命题公式A的主析取范式，可求得其主合取范式；反之亦然。事实上，注意到极小项mi与极大项Mi满足mi Mi ， mi Mi。（例：m5：PQR，M5：PQR）。如例1.7.14 中的主合取范式为

43、M0M2M4M5已求出，则主析取范式为m1m3m6m7，然后写出相应的极小项即可。 第 1 章 命题逻辑1.7 对偶与范式4主范式的应用（1）命题公式等价性的判定由于每个命题公式都存在着与之等价的唯一的主析取范式和主合取范式，因此，如果两个命题公式等价，则相应的主范式也对应相同。( 2) 命题公式类型的判定定理1.7.11 设A是含n个命题变元的命题公式，则1）A为永真式当且仅当A的主析取范式中含有全部2n个极小项。2）A为矛盾式当且仅当A的主合取范式中含有全部2n个极大项。3）若A的主析取范式中至少含有一个极小项，则A是可满足式。第 1 章 命题逻辑1.7 对偶与范式（3） 解决实际问题例1

44、.7.18某科研所要从名科研骨干A,B,C中挑选12名出国进修。由于工作原因，选派时要满足以下条件：（）若A去，则C同去。（）若B去，则C不能去。（）若C不去，则A或B可以去。问应如何选派他们去？第 1 章 命题逻辑1.8 命题逻辑的推理理论 数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理就是由已知的命题得到新命题的思维过程。任何一个推理都是由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发应用推理规则推出的新命题。定义1.8.1设H1，H2，Hn，C都是命题公式。若(H1H2Hn)C是重言式，则称由前提H1，H2，Hn推出C的推理是有效的或正确的，并称C是H1

45、，H2，Hn的有效结论或逻辑结果，记为H1，H2，HnC或H1H2HnC，记号H1H2HnC也称为重言蕴含或推理形式。 第 1 章 命题逻辑1.8 命题逻辑的推理理论 说明：（1）由前提H1，H2，Hn推结论C的推理是否正确与各前提的排列次序无关，因而前提中的公式不一定是序列，而是一个有限公式集合。若推理是正确的，则记为H1H2HnC，否则记为H1H2HnC。（2）符号与是两个完全不同的符号，它们的区别与联系类似于和的关系。不是命题联结词而是公式间的关系符号，而是命题联结词。这两者之间有密切的联系，即AB的充要条件是公式AB为重言式。第 1 章 命题逻辑1.8 命题逻辑的推理理论1.8.1推理

46、规则在数理逻辑中，要想进行正确的推理，就必须构造一个逻辑结构严谨的形式证明，这需要使用一些推理规则。下面就介绍人们在推理过程中常用到的几条推理规则。1前提引入规则(P) 在推理过程中，可以随时引入已知的前提。2结论引用规则(T)在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。第 1 章 命题逻辑1.8 命题逻辑的推理理论3置换规则(R)在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明的公式序列的另一公式。(在1.5节介绍的常用等价式作为命题推理定律，在后面的推理演算中以大写字母E加以引用)4代入规则(S)在推理过程中，重言式中的任一命题变元都可以用一命题公

47、式代入，得到的仍是重言式。 第 1 章 命题逻辑1.8 命题逻辑的推理理论1.8.2推理定律（1）化简律 ABA，ABB（2）附加律 AA B，BA B（3）假言推理（又称分离规则） A ( AB) B （4）假言三段论 (AB) ( BC) ( AC)（5）等价三段论 (AB) ( BC) ( AC)（6）析取三段论 (A B) A A第 1 章 命题逻辑1.8 命题逻辑的推理理论1.8.2推理定律（7）拒取式 B ( AB) A （8）二难推理 (AC) ( BC) ( A B) C（9）合取引入 A，B AB（10）A AB，B AB（11） (AB) A， (AB) （12）(AB)

48、( BA) ( AB)（13）AB (AC) (BC)，AB (AC) (BC)（14）AB AB，AB BA 第 1 章 命题逻辑1.8 命题逻辑的推理理论1.8.3推理方法在命题逻辑中，常用的推理方法有三种：真值表法、直接证法和间接证法，下面分别介绍。1真值表法设P1,P2,Pn是出现于前提H1,H2,Hn和结论C中的全部命题变元，对P1,P2,Pn的所有情况作完全指派，这样能对应地确定H1,H2,Hn和C的所有真值，列出这个真值表，即可判断如下推理形式是否成立： H1H2HnC或H1，H2，HnC若从真值表上找出H1，H2，Hn均为1的行，C对应的行也为1，则上式成立。或者，若C为0的行

49、，对应的行中H1，H2，Hn至少有一个0，则上式也成立。 第 1 章 命题逻辑1.8 命题逻辑的推理理论2直接证法利用前面的四条推理规则，根据已知的命题等价公式（1.5节中的15组公式）和推理定律，推演而得到有效的结论。例1.8.2 证明 (PQ)(PR)(QS)SR证明 （1）PQ P （2）PQ R,E,(1) （3）QS P （4）PS T,I,(2)(3) （5）SP R,E,(4) （6）PR P （7）SR T,I,(5)(6) （8）SR R,E,(7) 证毕。第 1 章 命题逻辑1.8 命题逻辑的推理理论说明：上述推理过程中，最左边的一列（1），（2）等代表推理的步骤，也是推导

50、出来的命题公式的编号，最右边的一列是说明每一步的依据。如P表示前提引入规则；R,E,(1)表示依据置换规则和命题定律中的命题等价公式，由（1）得到（2）；T,I,(2)(3)表示依据结论引用规则和推理定律，由（2），（3）两式推得（4）。 第 1 章 命题逻辑1.8 命题逻辑的推理理论例1.8.3 证明 WR V，VCS，SU，CUW证明 （1）CU P（2） U T,I,(1)（3）SU P（4）S T,I,(2)(3)（5）C T,I,(1)（6）CS T,I,(4)(5)（7）(CS) R,E,(6)（8）WRV P（9）VCS P（10）WR CS T,I,(8)(9)（11）(WR)

51、 T,I,(7)(10)（12）WR R,E,(11)（13）W T,I,(12) 第 1 章 命题逻辑1.8 命题逻辑的推理理论例1.8.4 “如果下雨，春游就改期，如果没有球赛，春游就不改期。结果没有球赛，所以没有下雨”，证明这是有效的论断。证明： 令A：天下雨 B：春游改期 C：没有球赛。 符号化推理中各命题得： AB，C B，C A。(1) AB P(2) CB P(3) BC R,E,(2)(4) AC T,I,(1)(3)(5) CA R,E,(4)(6) C P(7) A T,I,(5)(6)第 1 章 命题逻辑1.8 命题逻辑的推理理论3间接证法间接证法主要有两种，一种称之为C

52、P规则，还有一种是常用的反证法（也叫归谬法）。（1）附加前提证明法（CP规则）由公式的等价性知H1H2Hn（AB） （H1H2HnA）B，所以要证明H1H2Hn（AB），只需证明（H1H2HnA）B即可，这种方法称为CP规则。 第 1 章 命题逻辑1.8 命题逻辑的推理理论例1.8.6证明RS是 P(QS)，RP，Q 的逻辑结果。证明(1) RP P(2) R P ( 附 加 前 提)(3) P T,I, (1)(2)(4) P(QS) P(5) QS T ,I, (3)(4)(6) Q P(7) S T, I, (5)(6) (8) RS CP (2)(7)第 1 章 命题逻辑1.8 命题逻

53、辑的推理理论例1.8.7 如果学生学习努力，他们的父亲或母亲就高兴，若母亲高兴，学生就不努力学习，若老师只表扬学生，学生的父亲就不高兴，故如果学生学习努力，老师就不是只表扬学生。试证这是有效的结论。证明: 令A：学生学习努力；B：学生的父亲高兴；C：学生的母亲高兴；D：老师只表扬学生。符号化推理中各命题得：第 1 章 命题逻辑1.8 命题逻辑的推理理论ABC，C A，DBAD(1) DB P(2) BD R,E,(1)(3) CA P (4) AC R,E,(3)(5) A(BC) P(6) A(CB) R,E,(5)(7) A P(附加前提)(8) C T,I,(4)(7)(9) CB T,

54、I,(6)(7)(10) B T,I,(8)(9)(11) D T,I,(2)(10)(12) AD CP所以这是有效的结论。 第 1 章 命题逻辑1.8 命题逻辑的推理理论（2）归谬法归谬法（反证法）是经常使用的一种间接证明方法，是将结论的否定形式作为附加前提与给定的前提条件一起推证来导出矛盾。定义1.8.2 设P1，P2 ，P n 是A1，A2 ，A m 中出现的原子命题变元，若对P1，P2 ，P3 ，Pn 的一些真值指派，A1 A2 Am 取值为1，则称A1，A2，A m 是相容的，若对P1，P2，P3 ，Pn 的任何指派，A1 A2 Am 取值为0，则称A1，A2 ，A m 是不相容的

55、（矛盾的）。定理1.8.1 A1 A2 A m B 当且仅当A1，A2 ，Am ，B是不相容的。第 1 章 命题逻辑1.8 命题逻辑的推理理论证明: A1 A2 A m B 当且仅当A1 A2 A m B T（重言式），当且仅当(A1 A2 A m )BT，当且仅当A1 A2 Am BF(矛盾式)，当且仅当A1，A2 ，A n，B是不相容的。 第 1 章 命题逻辑1.8 命题逻辑的推理理论例1.8.8用归谬法证明例1.8.2。证明 (1) (SR) P（附加前提） (2) SR R,E,(1) (3) PQ P (4) PQ R,E,(3)(5) QS P(6) PS T,I,(4)(5)(7

56、) SP R,E,(6)(8) SRRP T,I,(7)(9) RP T,I,(2)(8)(10) PR P(11) PR R,E,(10)(12) (PR） R,E,(11)(13) (PR)(PR)F T,I,(9)(12)由（13）得出了矛盾，根据归谬法说明原推理正确。本章小结命题逻辑是研究数理逻辑的基础，它是数理逻辑的一部分。其主要内容包括：命题符号化及联结词，命题公式及分类，等值演算，最小联接词全功能集，对偶与范式，推理理论。通过本章学习，主要熟悉命题的概念；熟悉命题公式演算；掌握命题的公式符号化应用；熟悉真值表及其应用；领会推理理论及其规则。第 2 章 谓词逻辑命题逻辑不仅无法刻画

57、世界上事物之间的复杂的逻辑关系，甚至无法证明一些简单而又常见的推理。例如，著名的苏格拉底三段论：“所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”根据常识，我们知道上述推理是正确的，然而利用命题逻辑是无法推证的。因为，在命题逻辑中，令P、Q、R分别表示上述三个原子命题，则该推理可符号化为PQR，即证明PQR是永真式。然而，在命题逻辑中这是不可能的，如何能推证这个原子命题间的蕴涵关系呢？关键在于命题符号R与P，Q间的内在关系未能表示出来，受到了原子命题的限制。因此，需要对原子命题再进行剖析，去掉命题逻辑不能很好推理的局限性。因此从推理的角度看，也有必要扩充命题逻辑。第 2 章 谓词逻辑

58、2.1个体、谓词和量词 2.1.1个体和谓词定义2.1.1 在原子命题中，所陈述的对象称之为个体，它可以是独立存在的具体事物，也可以是一个抽象的概念。如王平，李明，计算机，离散数学，精神等都可以作为个体。定义2.1.2 将表示具体的或确定的个体称为个体常元，而将表示抽象的或泛指的（或者说取值不确定的）个体称为个体变元。个体常元一般用小写英文字母a,b,c或带下标的ai,bi,ci表示，个体变元一般用小写英文字母x,y,z或带下标的xi,yi,zi表示。第 2 章 谓词逻辑2.1个体、谓词和量词 定义2.1.3 用以描述单个个体所具有的性质或多个个体之间关系的词称为谓词。 定义2.1.4 表示具

59、体性质或关系的谓词称为谓词常元，表示抽象的或泛指的性质或关系的谓词称为谓词变元。无论是谓词常元或变元都用大写英文字母P,Q,R或带下标的Pi , Qi , Ri 表示，要根据上下文区分。 第 2 章 谓词逻辑2.1个体、谓词和量词定义2.1.5 一个原子命题用一个谓词(如P)和n个有次序的个体常元(如a1，a2，an)表示成P(a1，a2，an)，称它为该原子命题的谓词形式或命题的谓词形式。 定义2.1.6 由一个谓词(如P)和n个个体变元(如x1，x2，xn)组成的P(x1，x2，xn)，称它为n元原子谓词或n元命题函数，简称n元谓词。例如令P表示谓词“是大学生”，则用P(x)表示“x是大学

60、生”；令G表示谓词“比大”，则用G(x，y)可表示“x比y大”。当n=1时，称一元谓词；当n=2时，称为二元谓词，。一元谓词表达了个体的性质，而元谓词表达了个个体之间的关系。特别地，当n=0，称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看成特殊的谓词。 第 2 章 谓词逻辑2.1个体、谓词和量词例2.1.1分析下列命题的个体和谓词（1）2是质数。（2）上课认真听讲是好习惯。（3）李强比王飞高。（4）5大于3。（5）x与y具有关系R。解：(1) “2”是个体常元，“是质数”是谓词，记为P。这里的谓词是一元谓词，属于谓词常元，是描述个体的性