离散数学I.ppt

离散数学 I,引言,课程简介 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，它研究的对象是有限个或可数的离散量。充分描述了计算机科学离散性的特征。 离散数学是传统的逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。 离散数学是随着计算机科学的发展而逐步建立起来的一门新兴的工具性学科，形成于七十年代。,引言,课程意义 离散数学是计算机科学的数学基础，其基本概念、理论、方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中，是这些课程的基础课程。 离散数学学习十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高，能够培养提高学生的数学思维能力和对实际问题的求解能力。 教学内容 数理逻辑、集合论、代数结构、图论,引言,教学内容 第一部分 数理逻辑 第一章 命题逻辑 第二章 谓词逻辑 第二部分 集合论 第三章 集合代数 第四章 二元关系,引言,教学内容 第二部分 集合论 第五章 函数 第六章 集合的基数 第三部分 代数结构 第七章 代数系统 第八章 群论,引言,教学内容 第三部分 代数结构 第九章 环与域 第十章 格与布尔代数,第一部分 数理逻辑,逻辑学 是一门研究思维形式和规律的科学。分为辩证逻辑和形式逻辑两种。思维的形式结构包括了概念判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，就是判断。由一个或几个判断推出另一判断的思维形式就是推理。 数理逻辑 用数学方法研究推理的规律称为数理逻辑。所谓数学方法就是引用一套符号体系的方法，所以数理逻辑又称作符号逻辑。,第一部分 数理逻辑,现代数理逻辑 逻辑演算、逻辑演绎、模型论、证明论、递归函数论、公理化集合论等。 我们要介绍的是数理逻辑中最基本的内容：命题逻辑和谓词逻辑。即一般所谓的古典逻辑。 德国数学家莱布尼茨Leibniz（现代逻辑的首席创始人）；布尔Boole （奠基人，逻辑的数学分析）；弗雷格（数论的基础）,第一章 命题逻辑,命题逻辑也称命题演算或语句逻辑。它研究以“命题”为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表示命题？怎样由一组前提推导一些结论。,概念,判断,推理,1.1 命题与命题联结词,1.1.1命题 定义1.1：具有确切真值的陈述句(或断言)称为命题(Proposition)。 命题的取值称为真值。真值只有“真”和“假”两种，分别用“T”或“1”和“F”或“0”表示。 注意：命题的真值非真即假，只有两种取值，这样的系统为二值逻辑系统。,1.1 命题与命题联结词,例1-1：命题示例。 (a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数 (d):陈胜起义那天，杭州下雨 (e):较大的偶数都可表为两个质数之和 (f):x+y4 (g):真好啊! (h):x=3 (i):你去哪里？ (j):我正在说谎。 注意：由定义知，一切没有判断内容的句子如命令，感叹句，疑问句，祈使句，二义性的陈述句等都不能作为命题。,1.1 命题与命题联结词,例1-2：下列句子哪些是命题，判断命题的真假。 (1):2是素数 (2):北京是中国的首都 (3):这个语句是假的 (4):x+y0 (5):我喜欢踢足球 (6):地球外的星球上也有人 (7):明年国庆节是晴天 (8):把门关上 (9):你要出去吗？ (10):今天天气真好啊！,注意 命题一定是通过陈述句来表达；反之，并非一切的陈述句都一定是命题。 命题的真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定的。,1.1 命题与命题联结词,1.1 命题与命题联结词,命题可分为两种类型： 简单命题：若一个命题已不能分解成更简单的命题，则该命题叫原子命题或本原命题或简单命题（Simple Proposition） 复合命题（Compound Proposition）：可以分解为简单命题的命题，而且这些简单命题之间是通过关联词（如“或者”,“并且”,“不”，“如果 则”,“当且仅当”等）和标点符号复合而构成一个复合命题。 例，合肥是安徽的省会当且仅当鸟会飞。 注意： 命题通常用大写英文字母（可带下标）来表示。,1.1.2 命题联结词 命题通常可以通过一些联结词复合而构成新的命题，这些联结词被称为逻辑联结词。用数学方法研究命题之间的逻辑关系时（也就是在命题演算中），这些联结词可以看作是运算符，因此也叫作逻辑运算符。 常用的联结词有以下5个： 定义1.2：设P是任一命题，复合命题“非P”（或“P的否定”）称为P的否定式（Negation），记作¬P，“¬”为否定联结词。 ¬P为真当且仅当P为假。 如：P：2是素数，则¬P：2不是素数。,1.1 命题与命题联结词,1.1 命题与命题联结词,定义1.3：设P Q是任意两个命题，复合命题“P并且Q”（或“P和Q”）称为P与Q的合取式（Conjunction），记作P Q，“ ”为合取联结词。 P Q为真当且仅当P，Q同为真。 例，P：2是素数，Q：2是偶数。则P Q：2是素数并且是偶数。,1.1 命题与命题联结词,定义1.4：设P Q是任意两个命题，复合命题“P或Q” 称为P与Q的析取式（Disjunction），记作P Q，“ ”为析取联结词。 P Q为真当且仅当P，Q至少一个为真。 例，P：2是素数，Q：2是奇数。则P Q：2是素数或是奇数。,1.1 命题与命题联结词,定义1.5：设P Q是任意两个命题，复合命题“如果P则Q” 称为P与Q的蕴含式（Implication），记作PQ，“”为 蕴含联结词，P称为蕴含式的前提，假设或前件，而Q称为结论式后件。PQ为假当且仅当P为真Q为假。 例，P：G是正方形，Q：G的四边相等，则PQ：如果G是正方形，则G的四边相等。 蕴含式PQ可以用多种方式陈述： “若P，则Q”; “P是Q的充分条件”; “Q是P的必要条件”; “Q每当P”; “P仅当Q”等。,1.1 命题与命题联结词,给定命题PQ，我们把QP，PQ， QP分别叫作命题PQ的逆命题，反命题和逆反命题。 定义1.6：设P，Q是任意两个命题，复合命题“P当且仅当Q”称为P与Q的等价式(Equivalence)，记作PQ，“”为等价联结词。 PQ为真当且仅当P，Q同为真假。 例如，P：合肥是安徽省会，Q：鸟会飞，则PQ：合肥是安徽省会当且仅当鸟会飞。 如果PQ是真，则PQ和QP是真，反之亦然，因此PQ也读作“P是Q的充要条件”或“P当且仅当Q”。,1.1 命题与命题联结词,五个联结词的真值表,1.1 命题与命题联结词,一般约定： a)：运算符(联结词)结合力强弱顺序为：¬， ，；凡符合此顺序的，括号可省略。 b)：相同的运算符，从左到右次序计算时，括号可省去。 c)：最外层括号可省。 如，(¬(P ¬Q) R) (R P)Q) ¬(P ¬QR) R PQ,例1.3：符号化下列命题。 a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校 ii. 如果明天不下雨并且不下雪，则我去学校 iii. 如果明天下雨或下雪则我不去学校 iv. 明天我将风雨无阻一定去学校 v. 当且仅当明天不下雪并且不下雨时我才去 学校,1.1 命题与命题联结词,1.1 命题与命题联结词,c)：说小学生编不了程序，或说小学生用不了个人计算机，那是不对的。 d)：若不是他生病了或出差了，我是不会同意他不参加学习的。 e)：如果我上街了，我就去书店看看，除非我很累。,1.1 命题与命题联结词,注意： ¬是自然语言中的“非”“不” 和“没有”等的逻辑抽象 是自然语言中的“并且” “既 又” “且” “和”等的逻辑抽象 是自然语言中的“或”和“或者”等的逻辑抽象；但“或”有“可兼或” “不可兼或” “近似或”三种 PQ是自然语言中的“只要P，就Q” “因为P，所以Q” “P仅当Q”等的逻辑抽象,(5) 是自然语言中的“充分必要条件”和“当且仅当”等的逻辑抽象 (6)联结词连接的是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题 的真值只取决于构成他们的各原子命题的真 值 (7) ，具有对称性，而¬，没有 (8) ， ¬与计算机中的与门，或门，非门电路是相对应的 看P6-7 例1.4-1.5，P9 例1.7,1.1 命题与命题联结词,符号化下列命题 a)：1. 张晓静爱唱歌或爱听音乐 2. 张晓静是江西人或安徽人 b)：a是给定的一个正整数， 1. 只要a能被4整除，则a一定能被2整除 2. a能被4整除，仅当a能被2整除 3. 除非a能被2整除，a才能被4整除 4. 除非a能被2整除，否则a不能被4整除 5. 只有a能被2整除，a才能被4整除,1.1 命题与命题联结词,1.2.1：命题公式 就像在代数学里引入变量一样，为了更广泛的应用命题演算，在数理逻辑中也引入了命题变量。使得在研究时，只需考虑命题的真值，而不知晓命题的具体含义。 定义1.7：一个特定的命题是一个常值命题(Constant Proposition)，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元、命题变项)(Proposition Variable)。命题变量无具体的真值，它的值域是集合T，F(或1，0)。,1.2 公式的解释与真值表,原子命题在不指派真值时称为命题变元，而复合命题由原子命题和联结词构成，可以看作是命题变元的函数，且该函数的值仍为“真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原子命题和联结词的一个随便的组合都可以为命题公式，我们用递归的方法来定义命题公式。,1.2 公式的解释与真值表,1.2 公式的解释与真值表,定义1.8：命题公式 (1).命题变元本身是一个公式； (2).如果P是公式，则¬P也是公式； (3).如果P，Q是公式，则PQ PQ PQ PQ也是公式； (4).命题公式(Prepositional Formula)是仅由有限步使用规则(1)(3)后产生的结果。公式常用符号GH等表示。 例，(¬ PQ)，(P(¬P Q) ，(PQ) (R Q) (P R)是命题公式 (P Q )¬ Q)， (P Q， (¬ PQ (R， PQ 不是命题公式,注意： 如果G是含有n个命题变元 P1, P2, ,Pn的公式，通常记为G（P1, ,Pn）或简记为G。 原子命题变元是最简单的（合式）公式，也叫原子（合式）公式。 合成公式没有真值，只有对其变元进行指派后才有真值。 合成公式无限多。,1.2 公式的解释与真值表,1.2 公式的解释与真值表,合成公式的层次： (1).若公式A是一单个的命题变项，则称A为0层公式； (2).称A是n+1(n0)层公式只需满足下列情况只一： a). A=¬B，B是n层公式； b). A=BC，其中B，C分别为i层和j层公式,且n=max(i, j)； c). A=BC，其中B，C的层次同b； d). A=BC，其中B，C的层次同b； e). A=BC，其中B，C的层次同b； 从图论的观点来看每个多层公式可以用一个“树”来表示。,1.2 公式的解释与真值表,1.2.2：公式的解释与真值表 公式本身没有真值，只有在对其所有命题变元指定真值后才变成一个具有真值的命题。 定义1.9：设命题变元P1, P2, ,Pn是出现在公式G中的所有命题变元，指定P1, P2, ,Pn一组真值，则这组这组称为G的一个解释(Explanation),并记作I。 一般来说，若有n个命题变元，则应有2n个不同的解释。 定义1.10：公式G在其所有可能的解释下所取真值的表，称作G的真值表(Truth)。,1.2 公式的解释与真值表,例1.4：5个联结词的真值表(T：1，F：0),1.2 公式的解释与真值表,例1.5：设公式G= (PQ) R )(PQ)，其中P，Q，R是G的命题变元，则其真值表如下：,1.2 公式的解释与真值表,1.2.3：一些特殊的公式 例1.6：考虑：G1= ¬(PQ) P； G2=(PQ) P； G3= ¬(P ¬ Q) ¬ (PQ) 公式G1对所有可能的解释都具有“真”值，G3对所有解释都具有“假”值，公式G2则具有“真”和“假”值。,1.2 公式的解释与真值表,1.重言式： 定义1.11： (1). 公式G称为永真公式（重言式），如果在它的所有解释下都为“真”； (2). 公式G称为可满足的，如果它不是永假的； (3). 公式G称为永假公式（矛盾式）, 如果在它的所有解释下都为“假”;有时也称永假公式为不可满足公式。 注意： (1). 重言式的否定是矛盾式，矛盾式的否定是重言式，所以研究其一就可以了；,1.2 公式的解释与真值表,(2). 重言式的合取，析取，蕴含，等值等都是重言式； (3). 重言式中有许多非常有用的恒等式叫永真蕴含式。 对任意的公式，判定其是否为永真公式，永假公式，可满足公式的问题称为给定公式的判定问题。由于一个命题公式的解释的数目是有穷的，所以命题逻辑的判定问题是可解的，即命题的永真，永假性是可判定的。其判定方法有真值表法和公式推演法。,1.2 公式的解释与真值表,例1.7： 判定公式： (1).(PQ) (¬ PQ); (2). (PQ)P) Q； (3). P(Q R)。 2.恒等式： 定义1.12：公式G，H，如果在其任意解释下，其真值相同，则称G是H的等价式(Equivalent)或称G恒等于H，记作GH。,1.2 公式的解释与真值表,定理1.1：对于公式G和H， GH的充分必要条件是公式G H是重言式。 证明： 必要性：假定GH，则G和H在其任意解释I下，或同为真或同为假，由“”的意义知， G H在任意解释I下，其真值为真，即G H为重言式； 充分性：假设公式G H是重言式，I是它的任意解释，在I下， G H为真，因此，G，H或同为真或同为假，由于I的任意性，故有GH。,1.2 公式的解释与真值表,注意与不同： (1). ：逻辑等价关系， G H不是命题公式； (2). ：逻辑联结词， G H是命题公式； (3).计算机不能判断G，H是否逻辑等价，而可计算G H是否为重言式。,1.2 公式的解释与真值表,常用逻辑恒等式（P，Q，R为任意命题，T为真命题，F为假命题）：,1.2 公式的解释与真值表,1.2 公式的解释与真值表,3.永真蕴含式： 定义1.13：若AB是一永真式，那么称为永真蕴含式，记为AB，读作A永真蕴含B 常用的永真蕴含式,1.2 公式的解释与真值表,4.恒等式和永真蕴含式的两个性质： (1).若AB， BC，则AC；若A=B， B=C，则A=C. (即逻辑恒等和永真蕴含都是可传递的) 证明：AB， BC，即AB， BC为重言式，对任意的解释I，A和B，B和C的真值相同，则A和C的真值相同。 A C为重言式，即AC； A=B， B=C，即AB， BC为真； (AB)(BC)为真，由公式I6： AC为重言式，即A=C。,1.2 公式的解释与真值表,(2).若A=B， A=C，则A=BC. 证明：A为真时，B，C都为真，则BC也为真，即ABC为真；A为假时，则不管BC是真还是假时，ABC均为真，因此A=BC。,1.2 公式的解释与真值表,1.2.4：代入规则和替换规则 当一个公式是永真式或永假式时，其公式的真值完全跟随其命题变元的真值的变化而变化，因此，当用其他公式来取代公式中的命题变元时，不会改变公式的永真性和永假性 定理1.2(代入定理) ：设G(P1, ,Pn)是一个命题公式，其中P1, ,Pn是命题变元，G1(P1, ,Pn), Gn(P1, ,Pn)为任意的命题公式，此时若G是永真公式或永假公式，则用G1取代P1,Gn取代Pn后，得到的新的命题公式G(G1,Gn) G(P1, ,Pn)也是一个永真公式或永假公式。,1.2 公式的解释与真值表,例1.8：设G(P, Q) = ¬(PQ) P；用H(P, Q) =(P Q)；S(P, Q) =(P Q)代入G验证代入定理。 定理1.3(替换定理) ：设G1是G的子公式，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到的新的命题公式H，若G1H1，则GH。 例1.9：简化开关电路：,S,S,R,Q,P,P,1.2 公式的解释与真值表,例1.10：将下面程序语言进行化简： if A then if B then X else Y else if B then X else Y 例1.11：简化逻辑电路：,R,Q,P,1.2 公式的解释与真值表,例1.12：求证： (1).P¬(P¬Q)Q)是永真公式； (2).P(QR)(PQ)R; (3).(P(QR)(P¬Q ¬R)P; (4).(¬P(¬QR)(QR)(PR)R;,1.2 公式的解释与真值表,1.2.5：对偶原理 定义1.14：设公式A，其中仅有联结词， ，¬。在A中将，T，F分别换以，F，T得到公式A*，则A*称为A的对偶公式。 对A*采取同样的替换，又得到A，所以A也是A*的对偶，即对偶是相互的。 例，¬P(QR)和¬P(QR)互为对偶；PF和PT互为对偶。 定理1.4：设A和A*是对偶式，P1,P2, ,Pn是出现于A和A*中所有命题变元，于是 ¬A(P1,P2, ,Pn)A*(¬P1, ¬P2, , ¬Pn) 公式(1),1.2 公式的解释与真值表,定理1.5：若AB，且A，B为命题变元P1,P2, ,Pn及联结词，¬构成的公式，则A*B* (对偶原理) 例，若(PQ)(¬P(¬PQ) ¬PQ，则由对偶原理，得 (PQ)(¬P(¬P Q) ¬PQ 定理1.6：如果A=B，且A，B为命题变元P1,P2, ,Pn及联结词，¬构成的公式，则B*=A*,1.3 联结词的完备集,我们知道，命题公式通过等价公式的转换，可以以不同的形式表示出来。我们前面介绍了5个联结词，是否够用呢？ 1.3.1 联结词的扩充 1. 一元运算： 我们来看一个命题变元在一个一元运算的作用下可能的真值表。,1.3 联结词的完备集,因此，最多只能定义4种运算，但除了否定之外，永假，永真，恒等作为运算意义不大，所以一般不再定义其它一元运算。 2.二元运算： 考虑两个变元在一个二元运算作用下可能的真值表。,1.3 联结词的完备集,：已定义；：意义不大；：可再定义 f1=P¬P=F，f2= ¬(PQ)，f3= ¬(PQ)， f4= ¬(QP)， f5 =PQ， f6 = ¬P， f7 = ¬Q， f8=(PQ)， f9 = ¬(PQ) f10=Q， f11=P， f12 = ¬(PQ)， f13 =PQ， f14 = PQ， f15 = QP， f16 =P¬P=T， 其中：f2，f3(或f4)，f9，f12都是两个联结词的组合，为了叙述方便，可以引进下列几个联结词：,1.3 联结词的完备集,P Q¬(PQ) ，P Q¬(PQ) ， PQ¬(PQ) ， PQ¬(PQ) ， 这9个联结词构成命题演算中的所有联结词。,1.3 联结词的完备集,1.3.2 与非，或非，异或的性质 1.与非的性质： PQQP，PP ¬P， (PQ)(PQ)PQ， (PP)(QQ)PQ 2.或非的性质： PQ QP，PP ¬P， (PQ)(PQ)PQ， (PP)(QQ)PQ 3.异或的性质： P0，0 PP， 1 P¬P,1.3 联结词的完备集,1.3.3：全功能联结词 定义1.15：设S是联结词的集合，(1)用S中的联结词表示的公式，可以等价地表示任何命题公式，则称S是一个联结词完备集 (或全功能集合) (Adequate Set of Connectives)，(2)S是一个联结词的完备集，且S中无冗余的联结词(即集合中不存在可以被其中的其它联结词所定义的联结词)，则称S为极小联结词完备集。 由前面1.3.1的分析知，¬,是一个联结词完备集，而AB¬AB， AB(AB)(BA)，所以，是冗余的，故¬,也是一个联结词完备集,而AB¬(¬A¬B)，所以也是冗余的, ¬,也是一个联结词完备集，进一步地,可知¬,是一个极小联结词完备集。,1.3 联结词的完备集,证明联结词完备集¬,是一个极小的。 同理，¬,，¬, ，¬, 也是极小完备集，此外由1.3.2中，的性质可知 ，也是极小完备集； , 及其子集不是完备集； 实际应用中经常采取的联结词集合为¬,。 例1.13：试将公式(P(Q¬R)(¬PQ)用仅含¬ ，的公式等价地表示出来。,1.4：范式,1.4.1：范式 对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍，此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此，有必要使命题公式规范化，为此，引入了范式的概念。,1.4：范式,定义1.16： (1)：命题变元或命题变元的否定称为文字； (2)：有限个文字的析取式称为简单析取式(基本和)，有限个文字的合取式称为简单合取式(基本积)； (3)：由有限个简单合取式构成的析取式称为析取范式(Disjunctive Normal From)，由有限个简单析取式构成的合取式称为合取范式(Conjunctive Normal From)。,1.4：范式,例如， ：P，¬P ；：PQ ¬R； ：¬PQR；：(PQ)(¬PQ)； ：(PQ)(¬PQ)； 性质： (1)：一个文字既是一个析取范式又是一个合取范式； (2)：一个析取范式为矛盾式，当且仅当它的每个简单合取式是矛盾式； (3)一个合取范式为重言式，当且仅当它的每个简单析取式是重言式。,1.4：范式,定理1.7：任一命题公式都存在着与之等值的析取范式和合取范式。 例1.14：求公式(P¬Q) (PR)的析取范式和合取范式。,1.4：范式,1.4.2：主析取范式和主合取范式 范式虽然为命题公式提供了一种统一的表达形式，但这种表达形式却并不是唯一的。如公式(PQ)(PR)与之等价的公式有：P(QR)，(PP)(QR) ，P(Q¬Q)(QR)，P(PR)(QR),等，这种不唯一的表达形式给研究问题带来了不便，因此有必要引进更为标准的范式。 定义1.17：(1)包含A中所有命题变元或其否定一次仅一次的简单合取式，称为极小项；(2)包含A中所有命题变元或其否定一次仅一次的简单析取式，称为极大项；(3)由有限个极小项组成的析取范式称为主析取范式； (4)由有限个极大项组成的合取范式称为主合取范式。,1.4：范式,1.极小项和极大项的性质 对于两个命题变元P，Q来说，由于每个P，Q可以取命题变元自身和其否定，所以其对应的极小项和极大项分别有四项：PQ， ¬PQ，P¬Q，¬P¬Q；PQ， ¬PQ, P¬Q， ¬P¬Q。其真值表如下： 一般来说，对于n个命题变元，则应有 个不同的极小项和 个不同的极大项。,1.4：范式,性质： (1)：没有两个不同的极小项是等价的，且每个极小项只有一组真值指派使该极小项的真值为真，因此可给极小项编码，使极小项为“T”和那组真值指派为对应的极小项编码；如极小项¬P¬Q¬R只有在P，Q，R分别取真值0，0，0时才为真，所以有时又可用 ( )来表示，又如¬PQ¬R也可用 ( )来表示。 (2)：没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假。因此可给极大项编码，使极大项为“F”的那组真值指派为对应的极大项的编码，如极大项¬P¬Q¬R只有在P，Q，R分别取真值1，1，1时才为假，所以有时又可用 来表示。,1.4：范式,三个命题变元的真值取值与极小项和极大项的对应对位关系表：,1.4：范式,(3)：任意两极小项的合取必假，任意两个极大项的析取必为真。极大项的否定是极小项，极小项的否定是极大项，即 (4)：所有极小项的析取为永真公式，所有极大项的合取是永假公式，即,1.4：范式,2.主析取范式和主合取范式的存在性和唯一性 定理1.8：任何命题公式的主析取范式和主合取范式存在且唯一，即任何命题公式都有且仅有一个与之等价的主合取范式和主析取范式。 真值表技术 例1.15：求命题公式(PQ)R)(PQ)的主析取范式。 例1.16：求命题公式(PQ)R的主合取范式。,1.4：范式,利用真值表技术求主析取范式和主合取范式的方法： ：选出公式的真值结果为真的所有行，在这样的行中，找到其每一个解释所对应的极小项，将这些极小项析取即可得到相应的主析取范式； ：选出公式的真值结果为假的所有行，在这样的行中，找到其每一个解释所对应的极大项，将这些极大项合取即可得到相应的主合取范式。,1.4：范式,公式转换法 唯一性： 设任一命题公式A有两个主析取范式B和C，则因为AB， AC，所以BC，若B，C是A的(在不计极小项的顺序的情况下)不同的主析取范式，则必有在存在极小项mi，mi只存在于B，C之一中，不妨设mi在B中,而不在C中，因此i之二进制表示B的一个真值解释，而对于C则为真值为假的解释，这与BC矛盾，所以B和C相同，同理主合取范式也是唯一的。 例1.17：利用公式的等价求G=(PQ)R的主析取范式和主合取范式,1.4：范式,3：主合取范式和主析取范式之间的转换 真值表技术和公式转换方式在求主析取范式和主合取范式各有其优点，在公式中的命题变元较少时时，利用真值表技术更为简单。当命题变元较多时，一般采用公式转换法，而在公式转换中，有时求主析取范式更为方便，而有时求主合取范式更为方便。但两者之间必然有相应的关系。下面介绍一种两者之间的转换方法。,1.4：范式,(1)：已知公式G的主析取范式求公式G的主合取范式的步骤如下： a：求¬G的主析取范式，即G的主析取范式中没有出现过的极小项的析取 b：G¬(¬G)即是G的主合取范式 即：若 为G的主析取范式，则 为¬G的主析取范式，其中 后剩下的极小项。则 为G的主合取范式。,1.4：范式,(2)：已知公式G的主合取范式，求G的主析取范式的步骤如下： a：求¬G的主合取范式，即G的主合取范式中没有出现过的极大项的合取 b： G¬(¬G)即是G的主析取范式， 即，若 为G的主合取范式，则 为¬G的主合取范式。其中 后剩下的极大项。 则 为G的主析取范式,1.4：范式,例1.18：设G=(PQ)(¬PR)(¬Q¬R),求其对应的主析取范式和主合取范式 性质： (1)：如果命题公式是永真公式它的主析取范式包含所有极小项，此时主合取范式不含有任何极大项，为空，记1或T (2)：如果命题公式是永假公式它的主合取范式包含所有极大项，此时主析取范式不含有任何极小项，为空，记0或F (3)：两个命题公式A，B，AB当且仅当A与B有相同的真值表，又当且仅当A与B有相同的主析取范式(主合取范式)。(真值表和主范式是描述命题公式标准形式的两种不同的等价形式)。,1.4：范式,5.主范式的应用 (1).求公式的成真或成假赋值。 如：p qm0m1m3=m00m01m11 00，01，11是成真赋值，10是成假赋值 (2).判定问题。 根据主范式的定义和性质，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式A，其次按下列条件判定之：,1.4：范式,若AT，或A可化为与其等价的含 个极小项的主析取范式，则A为永真式； 若AF，或A可化为与其等价的含 个极大项的主合取范式，则A为永假式； 若A不与T或F等价，且又不含 个极小项或极大项，则A为可满足的。 例，判定公式：(1).(PQ)Q； (2). (PQ) (¬ PQ)。,1.4：范式,(3).证明等价性。 由于任何一公式的主范式是唯一的，所以求给定两公式的主范式，若主范式相同，则给定两公式是等价的。 例，求证(PQ) (PR)P (QR). (4).解决实际问题。 例，某科研所要从3名科研骨干A，B，C中挑选1-2名出国进修，由于工作需要，选派时要满足以下条件： 若A去，则C同去；若B去，则C不能去；若C不去，则A或B可以去。,1.5：命题逻辑的推理理论,1.5.1：推理的基本概念和推理形式 推理也称论证，它是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题形式。 定义1.18：设G1，G2，Gn，H是命题公式，若对于G1，G2，Gn，H中出现的命题变元的任意一组赋值，或者G1G2Gn为假，或者当G1G2Gn为真，H也为真，则称H是G1，G2，Gn的有效结论(Efficacious Conclusion)或逻辑结果(Logic Conclusion)。 G1，G2，Gn仍为一组前提(Premise)。,1.5：命题逻辑的推理理论,定理1.9：命题公式G1，G2，Gn推出结论H的推理正确或公式H是前提条件G1，G2，Gn的逻辑结果，当且仅当(G1G2Gn) H为重言式。 =：逻辑蕴含关系， G=H不是命题公式，计算机判断G=H办不到； ：蕴含联结词，G H是命题公式，计算机可判断G H为永真公式。 因此我们可以用蕴含式来描述推理。 我们将由G1，G2，Gn推理H，用蕴含式表示为： (G1G2Gn) H 将由G1，G2，Gn正确推理出H，用蕴含式表示为： G1G2Gn =H,1.5：命题逻辑的推理理论,推理的形式结构为：G1G2Gn H，书写为： 前提： G1，G2，Gn 结论：H 推理的有效性判断，即判断推理是否正确，也就是判断G1G2GnH是否为重言式。 1.5.2：判断结论有效的方法 1.真值表法；2.等值演算法；3.主析取范式法,1.5：命题逻辑的推理理论,1.真值表法 设P1，P2，Pn是出现在前提G1，G2， ，Gn和结论H中的一切命题变元，如果将P1，P2，Pn中所有可能的介绍及G1，G2， ，Gn，H的对应真值结果都在一个表中，根据“”的定义，则有如下判断方法： (1)对所有G1，G2， ，Gn都具有真值T的行(表示前提为真的行)，如果在每个这样的行中，H也具有真值T，则H是G1，G2， ，Gn的逻辑结果； (2)对所有H具有真值为F的行(表示结论为假的行)，如果在每一个这样的行中， G1，G2， ，Gn中至少有一个公式的真值为F(前提也为假)。则H是G1，G2， ，Gn的逻辑结果。,1.5：命题逻辑的推理理论,例1.18：判断下列H是否为前提G1，G2的逻辑结果。 (1). H：Q; G1：P，G2：PQ； (2). H：¬P; G1：PQ ，G2：¬Q； (3). H：Q; G1： ¬P，G2：PQ； 2.等值演算法 直接用等值演算来判断推理的形式结构是否是重言式。 例1.19：下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。,1.5：命题逻辑的推理理论,3.主析取范式法 将推理的形式结构转化为主析取范式，但仍判断其是否为重言式。 例1.20：若下午气温超过30，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温超过了30 。 以上方法，当形式结构比较复杂，特别是所含的命题变元较多时，一般很不方便，下面介绍构造证明法。,1.5：命题逻辑的推理理论,1.5.3：构造证明法 构造证明法是依据一些公认的推理规则，从前提出发，推导结论，它可以看作公式的序列，其中每个公式都是按照事先规定的规则得到的，且可将所用的规则在公式后写明，该系列最后一个公式是所要证明的结论。 (1)推理规则： 前提引入规则：在推理的任何步骤上都可以引入前提； 结论引入规则：在推理的任何步骤上所得到的结论都可以做为后续证明的前提； 置换规则：在推理的任何步骤上，命题公式的子公式都可以用与之等价的公式置换，得到公式序列中又一个公式。,1.5：命题逻辑的推理理论,(2)推理定理：(一些重要的永真蕴含式) 1.A=(AB) 附加律 2.AB=A 化简律 3.(AB) A =B 假言真理 4 .(AB) ¬B =¬A 拒取式 5.(AB) ¬B =A 析取三段论 6 .(AB) (BC) =AC 假言三段论 7 .(AB) (BC) =AC 等价三段论 8 .(AB)(CD)(AC) =(BD) 构造性二难 (AB)(¬AB)(A¬A) =B构造性二难(特殊形式) 9 .(AB)(CD)(¬B¬D) =(¬A¬C)破坏性二难,1.5：命题逻辑的推理理论,由着9个定律中的8个可以得到8个推理规则： 附加规则：A|=(AB) 化简规则：(AB)|=A 假言推理规则：(AB) ，A |=B 拒取式规则：(AB)，¬B|=¬A 假言三段论规则：(AB)，(BC)|=(AC) 析取三段论规则：(A B)，¬B|=A 构造性二难规则：(AB)，(CD)，(AC) |=(BD) 破坏性二难规则：(AB)，(CD)，(¬B¬D) |=(¬A¬C) 合取引入规则：A，B|=(AB),1.5：命题逻辑的推理理论,例1.21：构造下列推理的证明： 前提：p q，p ¬r，s t，¬s r，¬t 结论：q 例1.22：分析下列事实：“早饭我吃面包或蛋糕；如果我吃面包，那么我还要喝牛奶；如果我吃蛋糕，那么我还要喝咖啡；但我没有喝咖啡，所以早饭我吃的是牛奶和面包。”写出前提和有效结论并证明之。 例1.23：用构造法证明，找出下列推理的有效结论。 如果我考试通过了，那么我很快乐；如果我快乐，那么阳光灿烂；现在是晚上11点，天很暗。,1.5：命题逻辑的推理理论,(3)P1P2Pn (P Q)形式命题的证明。 附加前提证明法(CP规则) 若P1，P2，Pn ，P|= Q，则P1，P2，Pn |= PQ 附加前提证明法的意义在于：当推理的结论是蕴含式时，可以将其前件作为附加前提引用，只要能推理出其后件，则原推理成立。 例1.24：如果A参加球赛，则B