第一章 命题逻辑

1、离散数学及算法 课程名称：离散数学及算法 课 时：54 学 分：3 主讲教师：吕威 联系方式短号：663593 Email：教材及参考书教材: 离散数学与算法. 曹晓东，原旭等编著 .机械工业出版社. 2007.参考书: 离散数学及应用.（英文版.第4版）（美）KennethH.Rosen著 离散数学.陈莉编著.高等教育出版社,2000.学习方式 听课 （启发式、讨论式） 读书（预习、复习） 报告（综合练习）考试成绩 平时成绩 （书面作业、综合练习、大作业40%） 期末考试（60%）内容安排 数理逻辑包括命题逻辑和谓词逻辑（教材第一、二章） 集合论包括集合、关系和函数

2、（教材第三、四、五章） 代数系统包括代数系统的基本概念，几类典型的代数系统（第六章） 图论包括图的基本概念，几种特殊的图（第七章）第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.1引言 目标探索出一套完整的逻辑规则，这些规则给出数学语句的准确定义，按照这些规则可以确定任何特定的论证是否有效。 应用计算机电路设计计算机程序构造程序正确性证明第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴

3、含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.2命题与命题逻辑联结词 1.2.1命题 1.2.2逻辑联结词1.2.1命题一.定义：一个具有真假意义真假意义的陈述句陈述句被称为一个命题。 或真或假，不能既真又假。 例1:判断下面语句是否是命题 华盛顿是美国的首都。 多伦多是加拿大的首都。 1+101=110 几点了？ x+1=3 西安的小吃真多呀！1.2.1命题 理发师问题理发师给所有不给自己理发的人理发。1.2.1命题二、命题的真值及表示命题用大写的英文字母，如，来表示。 P：今天是星期二。如果一个命题的真值是真，则用1或(Ture)来表示；如果一个命题的真值是假，则

4、用0或（False）来表示。原子命题 一个命题不能再分解为更简单的命题，这个命题称为原子命题。 PQR1.2命题与命题逻辑联结词 1.2.1命题 1.2.2逻辑联结词1.2.2逻辑联结词复合命题，分子命题如果如果下周日下雪，那么那么我就去滑雪。如果下周日不不下雨并且并且没有考试，那么我去海边玩。这次演讲比赛，我们班将由赵明或者或者张强参加。5种逻辑联结词 否定词“并非” 合取词“并且” 析取词“或者” 蕴含词“如果，那么”（单向词） 双向蕴含词“当且仅当”（双向词）否定 定义：设 是一个命题，则 的否定是一个新的命题，记作“ ”，读作“非 ”。 例2：找出命题“所有的素数都是奇数”的否定。 “

5、并非所有的素数都是奇数。” “所有的素数都不是奇数。” 否定词“”的意义如下表：PPPPPPTFFTPP0110或真值表：利用运算对象真值的所有可能组合判断命题的真假。合取 定义： 表征意义两命题合取的真值表PQ（在命题 和 均为真时为真，否则为假。）PQPQPQ设 和 是命题，则用表示命题“ 并且 ”。PQPQPQPQFFFFTFTFFTTT000010100111或合取PQPQ命题 ： 今天是星期五。命题 ： 今天下雨。找出命题 和 的合取PQ解：表示“今天是星期五并且下雨”。这一命题在下雨的星期五成真，不下雨的星期五和不是星期五的日子都为假。析取 定义： 表征意义两命题析取的真值表PQ（

6、在命题 和 均为假时为假，否则为真。）PQPQPQ设 和 是命题，则用表示命题“ 或者 ”。PQPQPQPQFFFFTTTFTTTT000011101111或析取PQPQ例：命题 ： 李明在教室。命题 ： 张强是个好教练。找出命题 和 的析取PQ解：表示“李明在教室或张强是个好教练”。PQ例：命题 ： 李明在教室。命题 ： 李明在网球场。表示命题“李明在教室或在网球场”？异或 定义： 表征意义双条件 的真值表PQ（在 和 中恰有一个为真时为真，否则为假。）PQP QPQ设 和 是命题，则用表示命题“ 异或 ”。PQP QPQP QFFFFTTTFTTTF000101011110P Q或单条件

7、定义： 表征意义蕴含 的真值表PQ（在 为真而 为假时为假，否则为真。）PQPQPQ设 和 是命题，则用表示命题“如果 那么 ”。PQPQPQPQFFTFTTTFFTTT001100011111PQ或单条件 政治家竞选时许诺“如果我当选了，那么我将会减税”。 如果今天是星期五，那么2+2=4. 与程序设计中if p then S语句的区别。双条件 定义： 表征意义双条件 的真值表PQ（在 和 具有相同的真值时为真，否则为假。）PQPQPQ设 和 是命题，则用表示命题“ 等值于 ”。PQPQPQPQFFTFTFTFFTTT001100010111PQ或1.2.2逻辑联结词 注意：由逻辑联结词联结

8、的命题之间不需要任何关系。 优先次序：()PQRPQR句子到逻辑表达式的翻译 步骤：确定给定的句子是否为命题；找出各原子命题并确定句子中的连词为对应的联结词；用正确的语法把原命题表示成由原子命题、联结词和圆括号组成的公式。句子到逻辑表达式的翻译 翻译下列命题：(1)他既聪明又用功。(2)他虽聪明但不用功。解：原子命题 P：他聪明。 Q：他用功。则有： (1)翻译成： P Q (2)翻译成： P Q句子到逻辑表达式的翻译 除非有时间，我才去看电影 A：我有时间。 B：我去看电影。翻译为： B A 我不承认你是对的，除非太阳从西边出来 A：我不承认你是对的。 B：太阳从西边出来。翻译为： B A句

9、子到逻辑表达式的翻译 如果你和他都不固执己见的话，那么不愉快的事情就不会发生了。 P：你固执己见。 Q：他固执己见。 R：不愉快的事情不会发生。翻译为： (PQ)R 如果你和他不都是固执己见的话，那么不愉快的事情就不会发生了。 (PQ)R逻辑难题 一个岛上居住着两类人骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们两个不是一类人”，请判断A、B到底是流氓还是骑士。 解：首先架设P: A是骑士；Q: B是骑士如果A是骑士如果A是流氓第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真

10、蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.3命题变元和合式的公式 命题变元用P表示一个抽象的命题，而不是一个具体的命题时，成它为命题变元命题变元可以表示任意命题，不能确定真值 合式的公式（1）单个命题变元是合式的公式。（2）如果A是合式的公式，那么 A是合式的公式。（3）如果A和B均是合式的公式，那么 ， , 和 都是合式的公式。（4）当且仅当有限次的应用(1)、(2)、(3)条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式的公式。()AB()AB()AB()AB1.3命题变元和合式的公式 判断下列字符串哪些是合式的公式，哪些不是？P， P，P Q()PP

11、Q()()PQQ (PQ()()()PQQRST1.3命题变元和合式的公式命题公式合式的公式命题公式 vs 命题真值表 设P是一个命题公式， P1， P2， Pn是出现在P中的所有命题变元，对于这些命题变元真值指派的每一种可能的组合，都能唯一的确定P的真值。将这些真值列成一个表，称为命题公式P的真值表。 给出命题公式 的真值表 ()PQPPQPQ()PQP()PQP 00001011011011011110应用 系统规范性说明在说明硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师从自然语言中提取需求，生成精确、无二义的规范说明，这些说明可以作为系统开发的基

12、础。应用 确定下列系统规范性说明是否一致“诊断消息存放在缓冲区中或是被重传”“诊断消息没有存储在缓冲区中”“如果诊断消息存储在缓冲区中，那么它被重传” 解： P：诊断消息存储在缓冲区中 Q：诊断消息被重传三个命题分别是 P Q， P, PQPPQP Q P PQ000110 01 11 11 11 11010011100公式的等价性 定义：设A、B是两个命题公式，P1，P2，Pn 是出现在A和B中的所有命题变元。如果对于P1，P2，Pn的2n 个真值指派的每一组，公式A和B的真值相同，则称A和B等价。记作AB。 显然，要判断两个公式是否等价，用真值表法即可以实现。但是当命题变元多时这种方法是不

13、方便的。例如两个公式若含有4个变元，则真值表要列出24行。所以，我们一般不采用这种方法，而是采用等价变换的方法。下面列出的是常用的一组等价变换公式。真值表判定公式等价性 利用真值表证明公式等价性证明 与 是相互等价的。PQPQPQPQPQPQPQ0011010010001111第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.4重言式和永真蕴含式 1.4.1有关重言式的讨论 1.4.2重言式与恒等式 1.4.3永真蕴含式的定义和常用永真蕴含式 1.4.4代

14、入规则和替换规则1.4.1有关重言式的讨论 一个命题公式若含有N个变元，则应有2n种组合，所以证明两个命题公式的等价，当命题变元多时使用真值表法是不现实的，只能采用上面的等价变换的方法。有两种特殊的命题公式值得一提，即不依赖变元的真值指派总是取值为T的公式（称为永真式），不依赖变元的真值指派总是取值为F的公式（称为永假式），其余则情况则为可满足的式子。1.4重言式和永真蕴含式 1.4.1有关重言式的讨论 1.4.2重言式与恒等式 1.4.3永真蕴含式的定义和常用永真蕴含式 1.4.4代入规则和替换规则1.4.2重言式与恒等式 重言式给定一个命题公式，若无论对其中的命题变元作何种真值指派，其对应

15、的真值永为T，则称该命题公式为重言式或永真式。 永假式给定一个命题公式，若无论对其中的命题变元作何种真值指派，其对应的真值永为F，则称该命题公式为永假式或矛盾。 至少存在一组真值指派使命题公式取值为的命题公式，称为可满足的。 1.4.2重言式与恒等式 对命题公式 ， ， 做出真值表PP PPPQPPP PPPQPQ001011100111(1)重言式的否定是一个矛盾式，一个矛盾式的否定是重言式，所以只研究其中之一就可以了。(2)重言式的析取，合取，单条件，双条件都是重言式。于是可由简单的重言式推出复杂的重言式。(3)由重言式可以产生许多有用的恒等式。基本的等价公式12345678 ()() (

16、)() ()() ()()() EPQQPEPQQPEPQQPEPQRPQREPQRPQREPQRPQREPQRPQPRE交换律结合律9 ()()() ()()()PQRPQPRE PQRPQPR分配律基本的等价公式101112131415161718192023 () ( ( EPPEPQPQEPQPQEPQP QEPQQPEPQPQEPPPEPPPEPPFEPPTEPTPE 双重否定律德 摩根律逆反律等幂律)否定律 PFP同一律基本的等价公式212224252627282930 ()()()() () () ()EPFFEPTTEPTPEPFPEPQPQQPPQPQEPQPQEPQRPQR

17、EPPQPEPPQP 输出律吸收律零律1.4重言式和永真蕴含式 1.4.1有关重言式的讨论 1.4.2重言式与恒等式 1.4.3永真蕴含式的定义和常用永真蕴含式 1.4.4代入规则和替换规则永真蕴含式 定义：当且仅当AB是一个永真式时，称A永真蕴含B ，记作 要证明A永真蕴含B ，只需要证明AB是一个永真式假定前件A是真，若能推出后件B必为真，则AB永真，于是 .假定后件B是假，若能推出前件A必为假，则AB永真，于是 . ABABAB永真蕴含式()()1()()(),(1)(2)()()2PQQRPRPQQRTPQTQRTPTQTRTPRTPFRTFPRTPQQRTPRTPRFPT试证明证明：

18、 假定的真值为 ，那么为 并且()为分两种情况讨论：若 为 ，则 必然为 ，因而 为 ，于是有()为 ；若 为 ，则此时无论 为 或 ，都有()为 。综上所述，假定前提的真值为 ，推出结论的真值为 ，蕴含式成立。证明 ： 假定的真值为 ，那么由定义可知 为 ，,(1)()()(2)()()()()()RFQTQRFPQQRFQFPQFPQQRFPRFPQQRF并且 为分两种情况讨论：若 为 ，则(为 ，于是有为 ；若 为 ，则为 ，于是有为 。综上所述，假定结论的真值为 ，推出前提的真值为 ，蕴含式成立。常用永真蕴含式1234567891011 () () , , , IPQPIPQQIPPQ

19、IQPQIPPQIQPQIPQPIPQQIP PQQIP PQQIQ PQP 化简式附加式析取三段论假言推论1213141516 , ,IPQ QRPRIPQ PR QRRIPQRPRQIPQRPRQIP QPQ拒取式假言三段论二难推论,等价式和蕴含式的关系 设P和Q是命题公式， 的充分必要条件是 并且 设A、B、C是公式且有 ， ，则 设A,B,C是公式，若有 ， ，则PQPQQPBCABACABACABC蕴含式 定义：假设H1, Hm ,Q是命题公式。如果是命题公式。如果（H1 Hm ） Q，则称则称H1, Hm 共同蕴涵Q，并记作H1, Hm Q 定理：如果定理：如果H1 Hm P Q，

20、则则H1, Hm P Q 定理是显然的：定理是显然的： H1 Hm P 为真，为真，保证了保证了P为真，为真， H1 Hm P Q，保保证了证了Q为真，于是有为真，于是有P Q为真，得证。为真，得证。1.4重言式和永真蕴含式 1.4.1有关重言式的讨论 1.4.2重言式与恒等式 1.4.3永真蕴含式的定义和常用永真蕴含式 1.4.4代入规则和替换规则1.4.4代入规则和替换规则 下面我们给出子公式，及关于公式等价的一个定理。 定义： 设A是一个公式，A是A的一部分，且A也是一个命题公式，则称A是A的子公式。 替换规则替换规则：设A是公式A的子公式，B 是一命题公式且AB，将A中的A用B来取代，

21、则所得到的是一个新公式， 记为B，且A B。 例1（P(QR) (P Q R) P 证明：左边(P(QR) (P (Q R) P (QR) (Q R) P T P.重言式和永假式 P P T, P P F 永真式与永假式取决于公式本身的结构，不依赖变元的真值指派。 例如(P Q R) (P Q R)就是一个永真式 (P Q R) (P Q R)就是一个永假式 永真式的性质：若公式A是永真式，并且P1，P2，Pn是出现于A中的变元，若用公式B代换A中的原子变元Pi(i=1,2, ,n),所得到的公式设为A，则A也是永真式。（注意代换过程从左向右要进行到底）。对非永真式，这条性质不一定成立。 带入

22、规则 带入规则在一个重言式中，某个命题变元出现的每一处均代以同一个公式后，所得到的新的公式仍是重言式，这条规则称之为带入规则。 应用代入规则和替换规则及已有的重言式可以证明新的重言式 是重言式，那么用 代P得到的式子仍然是重言式。 E11： ，用 代P， 代Q PPFRQ()()RQRQF()PQPQ ABAB()()()()ABABABAB 1.4.4代入规则和替换规则PQQPQ例：试证明181920 ()() () PQQQPQEQPQQEQPTEPQE和替换规则证明：1.4.4代入规则和替换规则()() PQQRPQR例：试证明2727124()()()() ()() ()() () (

23、)() PQQRPQQREPQQREPQQREPQQREPQQQRPQ 和替换规则和替换规则证明： 1.4-4-1(a)R例和替换规则1.4.4代入规则和替换规则 将语句“情况并非如此，如果他不来，那么我也不去”化简。 P：他来。 Q：我去。符号化为：化简：化简后最终意思：我去了，他没来。()PQ ()() 27() 10 10, 12 PQPQEPQEPQEE 全功能联结词集合 前面我们已经学习了6个逻辑联结词： 是不是这些逻辑联结词都是必不可少的呢？在前面介绍的等价公式中我们已经发现，有些逻辑联结词是可以被其它逻辑联结词代替的： 例如：P Q P Q P Q （P Q） （P Q） P Q

24、 (P Q) P Q ( P Q) 从上面的讨论我们可以看出逻辑联结词集合， 是全功能的，但不是最小的。逻辑联结词全功能最小完备集是指用该集合中的逻辑联结词能表示所有的命题公式，并且删除一个至少有一个公式不能被表示。例如： ，和， 均是最小功能完备集。 例如：在，中删除，至少存在公式P仅用逻辑联结词不能表示，同样若删除，则至少存在公式P Q 不能仅用来表示。第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.5对偶原理 定义： 注意:求对偶式并不要求将“非”

25、变原，而且对偶式是相互的。 举例：求 的对偶式求 的对偶式*, , , , ,ATFAT FF TAAA 设有公式 ，其中仅含有逻辑联结词和逻辑常值和 。在 中将分别换以，得公式，则称为 的对偶式。()PQR()PQRPFPT对偶原理 定理1.5-1 ： 证明：由德摩根律 可知，对公式A求否定，直到深入到命题变元之前位置，在这个过程中，所有的变， 变 ，T变F，F变T。得证1。*12*1212*1212,( ,)(,)(1)(,)( ,)(2)nnnAAP PPAAA P PPAPPPAPPPA P PP 设 和互为对偶式，是出现于 和 中的所有命题变元，于是有：()PQPQ ()PQPQ 对

26、偶原理 定理1.5-2: 证明： 意味着 永真于是有 永真由定理1.5-1知，下式也永真利用带入规则，以 取代 Pi ，得 永真即12*, ,.nABABP PPAB 若，且 、 为命题变元及联结词构成的公式，则AB1212(,)(,)nnA P PPB P PP1212( ,)( ,)nnA P PPB P PP 1212(,)(,)nnAPPPBPPP (1,2, )iP in1212( ,)( ,)nnA P PPBP PPAB对偶原理例：()()()()PQPPQPQPQPPQPQ 若，试证明证明：设()()APQPPQBPQ 则*()()APQPPQBPQ 由于，因此，AB*AB对偶

27、原理 试证明：(1) ()()(2) ()()PQPQTPQPQF 2726111281719171916()()()()()()()()()(),()()()()()()()(),PQPQPQPQEPQPQPQEPQPQPQEEPQPQPQPQEPQPQPQPQPTQTEETTEETE 证明：对偶原理 试证明：(1) ()()(2) ()()PQPQTPQPQF 261112()()()()()()()()()(),()()()()()()PQPQPQPQPQEPQPQPQPQPQEEPQPQPQPQTFPQPQF 证明：由知和互为对偶式由于 的对偶式是 ，因此由定理1.5-1知对偶原理 定

28、理1.5-3: 证明： 意味着 永真由逆反律得 永真根据定理1.5-1 永真利用带入规则，以 取代 ，得 永真即12*, ,.nABABP PPBA 若，且 、 为命题变元及联结词构成的公式，则AB1212(,)(,)nnA P PPB P PP1212( ,)( ,)nnB P PPA P PP1212(,)(,)nnBPPPAPPP (1,2, )iP iniP1212( ,)( ,)nnBP PPA P PPBA第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的

29、推理理论1.6范式和判定问题 公式的标准形式范式 用来判定公式永真、 永假、 可满足1.6范式和判定问题 1.6.1析取范式和合取范式 1.6.2主析取范式和主合取范式1.6.1析取范式和合取范式 定义： 若一个命题公式是一些命题变元及其否定的积，则称之为基本积基本积；若这个命题公式是一些变元及其否定之和，称为基本和基本和。 一个由组成的公式，如果与给定的公式A等价，则称它是A的析取范式析取范式。 一个由组成的公式，如果与给定的命题公式A等价，则称它是A的合取范式合取范式。,P QPQPQ PQPPQPQPP QQ PQ PQPP 基本积：基本和：，,()()P QPQPQ PQPQ 析取范式

30、：,()()PP QQ PQ PQPP 合取范式：1.6.1析取范式和合取范式 定理定理1.6-1： 一个基本积是永假式，当且仅当它含有 形式的两个因子。 证明：（充分性）由于 是永假式，而 ，所以含有 和 形式的两个因子时基本积是永假式。 （必要性）用反证法。设基本积为假但不含 和 形式的因子，于是给这个基本积中的命题变元指派真值T，给带有否定的命题变元指派真值F，得基本积的真值是T，与假设矛盾。证毕。 ,PPPPQFFPPPP1.6.1析取范式和合取范式 定理定理1.6-2 : 一个基本和是永真式，当且仅当它含有 形式的两个因子。,PP1.6.1析取范式和合取范式例：求命题公式P （Q R

31、）的析取范式解： P （Q R） P （ Q R） /*这是一个合取范式*/ （ P Q） （ P R）/*使用与对或的分配律，化成析取范式*/1.6.1析取范式与合取范式例：求命题公式(P Q) (PQ)的合取范式解：(P Q) (PQ) (PQ)(PQ)(PQ) (PQ) /*消*/ (PQ)(P Q)(P Q) (P Q) /*消 并且否定深入到单个变元前*/ (P Q) (P Q) /*析取范式*/ (P Q)P) (P Q)Q) (PQ) (P Q) /*使用或对与的分配律及补余律，现在是合取范式的形式*/1.6.1析取范式和合取范式()()PQPQ例：求的析取范式。()()()()

32、( ()()()()()()()()()()()()()PQPQPQPQPQPQPQPQPQPQFPQPQPQPQPQPPQQPPPQPQQQFPQPQFPQPQ 解：1.6.1析取范式和合取范式()()PQPQ例：求的合取范式。()()( ()()( ()()( ( ()()()()()()()()APQPQAPQPQPQPQPQPQPQPQPQPQPQPQAAPQPQAPQPQ 解：令，那么由于所以1.6范式和判定问题 1.6.1析取范式和合取范式 1.6.2主析取范式和主合取范式1.6.2主析取范式和主合取范式 定义定义1.6-4： 在含n个变元的基本积中，若每个变元与其否定不同时存在，

33、而二者之一必出现且仅出现一次，则称这种基本积为。 例：两个命题变元P、Q的极小项为 n个变元，极小项个数2n,PQ PQPQPQ ，主析取范式 假定有P、Q、R三个变元PQRPQRPQRPQRPQRPQRPQRPQR000 0001 1010 2011 3100 4101 5110 6111 701234567mmmmmmmm主析取范式每个极小项只有一个真值指派任何两个极小项的合取必为假（因为在2n种真值指派中，只有一个极小项取值为真）所有极小项的析取必为真主析取范式 定义定义1.6-5：一个由极小项的和组成的公式，如果与命题公式A等价，则称它是公式A的主析取范式。 对任何命题公式(永假式除外

34、)都可求得与其等价的主析取范式，而且主析取范式的形式唯一。 主析取范式 求主析取范式的方法：先化成与其等价的析取范式；若析取范式的基本积中同一命题变元出现多次，则将其化成只出现一次；去掉析取范式中所有为永假式的基本积，即去掉基本积中含有形如PP的子公式的那些基本积；若析取范式中缺少某一命题变元如P，则可用公式 将命题变元P补充进去，并利用分配律展开，然后合并相同的基本积PPQQ（）主析取范式()()()()()()()()()()()()()()()()()()()()()()()APQRPQRRPPRPQRPQRPRPRPQRPQRPRQQPRQQPQRPQRPQRPQRPQRPQRPQRP

35、QRPQRPQRPQR 76531(1,3,5,6,7)mmmmm 主析取范式 主析取范式和真值表的关系： 右图为 对应的真值表：PQRPQRPQRPQRPQRPQRPQRPQRPQRPQR极小项00000011010001111000101111011111APQR主合取范式 定义定义1.6-6： 在含n个变元的基本和中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本和为。 例：两个命题变元P、Q的极大项为 n个变元，极大项个数2n,PQ PQPQPQ ，主合取范式 假定有P、Q、R三个变元PQRPQRPQRPQRPQRPQRPQRPQR 000 0001 1010

36、 2011 3100 4101 5110 6111 701234567MMMMMMMM每个极大项只有一组真值指派使其为F任何两个极大项的析取必为真（因为在2n种真值指派中，只有一个极大项取值为假）所有极大项的合取必为假。主合取范式 定义定义1.6-7：一个由极大项的积组成的公式，如果与命题公式A等价，则称它是公式A的主合取范式。 对任何命题公式(永真式除外 )都可求得与其等价的主合取范式，而且主合取范式的形式唯一。 主合取范式024()()()()()()()()()()()()()(0,2,4)APQRPRQRPRQQQRPPPQRPQRPQRPQRPQRPQRPQRMMM 主合取范式 主合

37、取范式和真值表的关系： 右图为 对应的真值表：PQRPQRPQR PQRPQRPQRPQRPQRPQRPQR极大项00000011010001111000101111011111APQR极小项和极大项的关系 极小项 和极大项 有下列的关系 ：imiMiiMm iimM 由合取（析取）范式求主析取（合取）范式 二者可以互相转化 已知公式A的主合取范式为： 求主析取范式。 解： A的主合取范式为M1M3，可知A的主析取范式为于是可直接写出A的主析取范式()()PQRPQR0,2,4,5,6,7（）()()()()()()PQRPQRPQRPQRPQRPQR 主析取范式和主合取范式 一个命题公式是永

38、真式，它的命题变元的所有极小项均出现在其主析取范式中，不存在与其等价的主合取范式 ； 一个命题公式是永假式，它的命题变元的所有极大项均出现在其主合取范式中，不存在与其等价的主析取范式； 一个命题公式是可满足的，它既有与其等价的主析取范式，也有与其等价的主合取范式 主析取范式和主合取范式例:求下列公式的主范式：（PQ)R解：（PQ)R (P Q )R (PQ)R (P R) (Q R) (PR(QQ)(Q R (PP) (PQR)(PQ R)(PQR)(PQR )M1,3,5 /*其中表示求合取*/m0,2,4,6,7 /*即该公式是可满足的，应存在与其等价的主析取范式*/主析取范式和主合取范式

39、例：求下列命题公式的主范式：（P Q R）（ P Q S）解： （P Q R）（ P Q S） （PQRS）（PQRS） （PQRS）（PQRS） m11,10,6,4/*这里代表析取*/ M0，1，2，3，5，7，8，9，10，12，13，14，15从上面的解题过程中我们可以看出，如果与一个命题公式等价的一种主范式一经求出，另一种形式立刻可以得出，除非是永真（或永假）式。第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论1.7命题演算的推理理论数理逻辑的一个

40、主要任务就是提供一套推理规则，给定一些前提，利用所提供的推理规则，推导出一些结论来，这个过程称为演绎或证明。 生活中：倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推理规则，则认为此结论是真的，并且认为这个论证过程是。 数理逻辑中：不关心前提的真实真值，把注意力集中于推理规则的研究，依据这些推理规则推导出的任何结论，称为，而这种论证则被称为。 有效结论定义:设A和B是两个命题公式，当且仅当AB是个永真式，即AB，则说B是A的有效结论，或B由A可逻辑的推出。可把该定义推广到有n个前提的情况。有效结论 定义： 例： H1：今天周一或者今天下雨。 H2：今天不是周一。 C：今天下雨。1212

41、12,mmmH HHCHHHCCH HH设是一些命题公式，当且仅当则称 是前提集合的有效结论。证明有效结论的方法 1，真值表法思路:“证明使前提集合取值为真的那些组真值证明使前提集合取值为真的那些组真值指派，也一定使结论取值为真指派，也一定使结论取值为真”。例:考察结论C是否是下列前提H1，H2,H3的结论。(1) H1：PQ，H2：P，C：QPQH1H2CH1 H2C001001011011100101111111真值表法 (2) 真值表构造如下：1:HPQ 2:()HQR3:HR:CP P Q RPQ ()QRRP0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1

42、 111110011 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0真值表法 (3)1:HP2:HPQ:C PQ P QPPQPQ 0 0 0 1 1 0 1 1110001110001例：一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解：设P:一份统计表格的错误是由于材料不可靠。 Q:一份统计表格的错误是由于计算有错误。于是问题可符号化为：(PQ)PQ其真值表如下页所示，使前提集合取值为真的真值指派只有一组，这组真值指派使结论Q也取值为真。真值表法真值表法真

43、值表法 P Q (PQ)P Q 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1证明有效结论的方法 2，直接证法在命题变元较多的情况下，真值表法显得不方便，我们采用直接证明发法，为此先给出如下的定义定义：设S是一个命题公式的集合，从S推出命题公式C的推理过程是命题公式的一个有限序列：C1，C2，Cn。其中，Ci或者属于S，或者是某些Cj(ji)的有效结论，并且Cn就是C。如何构造这个推理序列以得出结论C呢？只要遵循下面的推理规则，使用列出的等价式或永真蕴涵式，就能构造出满足要求的公式序列。为了帮助大家记忆，我们把常用的等价式和永真蕴涵式再次列出来。常用永真蕴含式I1：PQP, I

44、2: PPQ, I3: PPQI4: QPQ,I5: (PQ)P, I6: (PQ)QI7：P,Q PQ,I8：P,PQQ, I9：P, PQ QI10：Q,PQP, I11：PQ,QRPRI12： PQ,PR,QRR公式中“,”代表“”,公式不必死记硬背，其证明均可从“”的定义出发。例如对I11前件为真时保证PQ和QR都必为真，PQ为真，则保证P为真时Q一定为真，而Q为真和QR为真则保证了R必为真，P为真，R为真自然保证了PR为真，问题得证。常用等价式E E1 1: : P PP, EP, E2 2: P: P Q QQ Q P, EP, E3 3: P: P Q QQ Q P PE E4

45、4: (P: (P Q)Q) R RP P (Q(Q R )R )E E5 5: (P: (P Q)Q) R RP P (Q(Q R )R )E E6 6: (P: (P Q)Q) R R(P (P R) R) (Q (Q R) R)E E7 7: (P: (P Q)Q) R R(P (P R) R) (Q (Q R) R)E E8 8: : (P(P Q)Q)P PQ QE E9 9: : (P(P Q)Q)P PQ QE E1010:P:P P PP EP E1111:P:P P PP P常用等价式E E1212:R:R (P(PP)P)R ER E1313:R:R (P(PP)P)R R

46、E E1414:R:R (P(PP)P)T ET E1515:R:R (P(PP)P)F FE E1616:P:PQ QP P Q EQ E1717: : (P(PQ)Q)P PQ QE E1818:P:PQ QQ QP PE E1919:P:P(Q(QR)R)(P(P Q)Q)R RE E2020: : (P(PQ)Q)P P Q QE E2121:P:PQ Q(P(PQ)Q) (Q(QP)P)E E2222:P:PQ Q(P(P Q)Q) ( ( P PQ)Q)直接证法直接证明法：使用推理规则和给定的等价式及永真蕴涵式进行推导证明。 推理规则：规则P：在推导过程中，任何时候都可以引入前提。

47、引入一个前提称为使用一次P规则。规则T：在推导中，如果前面有一个或多个公式永真蕴含公式S，则可以把公式S引进推导过程中。换句话说，引进前面推导过程中的推理结果称为使用T规则。直接证法()PPQQRR例：证明是，的有效结论。解: 1 (1) (P Q) P规则 1 (2) P Q T规则 (1)和E11 1 (3) PQ T规则 (2)和E27 4 (4) Q R P规则 4 (5) QR T规则 (4)和E27 1,4 (6) PR T , (3), (5)和I12 7 (7) R P规则 1,4,7(8) P T,(6),(7)和I12直接证法例：证明公式例：证明公式S S R可由公式P Q

48、 Q，P PR，Q S S推出推出解：问题即证解：问题即证P Q Q，P PR，Q S S S S R1、 P Q PQ P规则规则2 2、 P PQ TQ T规则和规则和1 13 3、 Q S PS P规则规则4 4、 QS TS T规则和规则和3 35 5、 P PS TS T规则及规则及2 2和和4 46 6、 S SP P T T规则和规则和5 57 7、 P PR P P规则规则8 8、（、（P PR R） （R RP P）T T规则和规则和7 79 9、 P PR TR T规则和规则和8 81010、 S SR TR T规则及规则及6 6和和9 9； 1111、S S R T T规

49、则和规则和9 9 得证。得证。直接证法例：例： (P(PQ) (R(R S),(QS),(QP)R,RR,R P PQ Q1 1、R PR P规则规则2 2、(Q(QP)R PR P规则规则3 3、 Q QP T T规则及规则及1 1和和2 24 4、 R R S TS T规则及规则及1 15 5、 (P(PQ) (R(R S) PS) P规则规则6 6、 P PQ T T规则及规则及4 4和和5 57 7、( (P PQ) (Q(QP) T T规则及规则及3 3和和6 68 8、P PQ TQ T规则和规则和7 7直接证法 推理规则： CP规则：如果能从R和前提集合中推导出S来，则就能够从前

50、提集合中推导出RS。换句话说，当结论是RS的形式的时候，可以把结论的前件当作一个附加前提使用，并且它和前提一起若能推出结论的后件，则问题得证实际上恒等式E28就可以推出CP规则： （ P Q ） R （ P Q ） R （ P Q ） R P （ Q R ） P （Q R）直接证法 解：1 (1) R P规则（附加前提） 2 (2) R P P规则 1,2 (3) P T规则,(1),(2)和I9 4 (4) P(QS) P规则 1,2,4(5) QS T规则,(3),(4)和I10 6 (6) Q P规则 1,2,4,6(7) S T规则,(5),(6)和I10 1,2,4,6(8) R S

51、 CP规则,(1),(7),()RSPQSQRP 例：证明是， ，的有效结论。例：证明例：证明R RS S是前提是前提P P(Q(QS),S), R R (P(P Q)Q)的有效结论的有效结论解：原证明即证解：原证明即证:P:P(Q(QS), S), R R (P(P Q)Q)R RS S1 1、 R P R P规则（附加前提）规则（附加前提）2 2、 R R (P(P Q) PQ) P规则规则3 3、 P P Q TQ T规则及规则及1 1和和2 24 4、 P TP T规则和规则和3 35 5、 P P(Q(QS) PS) P规则规则6 6、 Q QS TS T规则及规则及4 4和和5 5

52、7 7、 Q TQ T规则和规则和3 38 8、 S TS T规则及规则及6 6和和7 79 9、R RS CPS CP规则及规则及1 1和和8 8直接证法 例：证明例：证明P P(Q(QR),Q,PR),Q,PS S S SR R解：解：1 1、 S PS P规则（附加前提）规则（附加前提） 2 2、 P PS PS P规则规则 3 3、 P TP T规则及规则及1 1和和2 2 4 4、 P P(Q(QR) PR) P规则规则 5 5、 Q QR TR T规则及规则及3 3和和4 4 6 6、 Q PQ P规则规则 7 7、 R T R T规则及规则及5 5和和6 6 8 8、 S SR

53、CPR CP规则及规则及1 1和和7 7直接证法证明有效结论的方法 3，间接证明法（反证法）定义：设公式H1,H2,Hm中的原子变元是P1, P2 ,Pn。如果给各原子变元P1, P2 ,Pn指派某一个真值集合，能使H1H2 Hm具有真值T，则命题公式集合H1,H2,Hm称为；对于各原子变元的每一个真值指派，如果命题公式H1,H2,Hm中至少有一个是假，从而使得H1H2 Hm是假，则称命题公式集合是。例如：令H1=P， H2 = P，则H1H2 = PP是矛盾式，所以P，P是不相容的。反证法 定理：若存在一个公式R，使得H1H2 Hm R R 则公式H1，H2，,Hm是不相容的。 证明：设，

54、H1H2 Hm R R则意味着（ H1H2 Hm ）（RR）是重言式，而RR是矛盾式，所以前件 H1H2 Hm必永假。因此， H1，H2，,Hm是不相容的。反证法 定理：设命题公式集合H1，H2，Hm是一致的，于是从前提集合出发可以逻辑的推出公式C的充要条件是从前提集合H1，H2，Hm，C出发，可以逻辑地推出一个矛盾（永假）式。 证明：必要性：由于H1 H2 Hm C，即H1 H2 Hm C为永真式，因而使H1 H2 Hm 为真的真值指派一定使C为真，C为假，从而使H1 H2 Hm C为假。必要性证完。反证法证充分性：由于证充分性：由于 H H1 1 H H2 2 H Hm m CC可以逻辑可以逻辑地推出一个矛盾，即地推出一个矛盾，即H H1 1 H H2 2 H Hm m C C F F即即H H1 1 H H2 2