01离散数学课件资料

1、2020/7/21,离散数学,1,参考教材：,1、离散数学、离散数学 理论.分析.题解 左孝凌、李为鑑、刘永才，上海科学技术文献出版社 2、离散数学（修订版） 耿素云、屈婉玲，高等教育出版社 3、离散数学（第三版） 耿素云、屈婉玲、张立昂，清华大学出版社 4、离散数学及其应用（原书第5版） （美）Kenneth H.Rosen著，袁崇义、屈婉玲、王悍贫、 刘田 译， 机械工业署版社,2020/7/21,离散数学,2,离散数学，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此充分描述了计算

2、机科学离散性的特点。 离散数学是随着计算机科学的发展而逐步建立的， 它形成于七十年代初，是一门新兴的工具性学科。,2020/7/21,离散数学,3,逻辑学:研究思维(或推理)的形式结构和规 律的学科。利用数学方法研究思维(或推理)的形式结构和规律的学科，称作数理逻辑。,数理逻辑,数理逻辑的基本内容：命题逻辑(演算)、谓词逻辑。它们对电子元件设计和性质分析，对逻辑程序设计语言的研制具有十分重要的意义。,2020/7/21,离散数学,4,第一章 命题逻辑 1.1 命题符号化与联结词 1.2 命题公式及其赋值 1.3 等值演算 1.4 联结词的完备集 1.5 对偶与范式 1.6 推理理论,2020/

3、7/21,离散数学,5,一、命题的概念,命题：能判断真假的陈述句。这种判断只有两种 可能，一种是正确的判断，一种是错误的 判断。,1.1 命题符号化及联结词,命题真值：判断为正确的命题称其命题真值为真(1) ； 判断为错误的命题称其命题真值为假(0) ； 命题是具有唯一真值的陈述句。,2020/7/21,离散数学,6,例1 判断下列句子中哪些是命题。,(1) 4是素数。 (2) 2 + 3 = 5。 (3) 雪是黑色的。 (4) 3能被2整除。 (5) 2050年元旦是晴天。 (6) 5x + 1 11。 (7) 这朵花真美丽呀！ (8) 明天下午开会吗？ (9) 我正在说假话。,(是),(是

4、),(是),(是),(是),(否),(否),(否),(否),2020/7/21,离散数学,7,解题思想：判断一个句子是否为命题，首先看它是否为陈述句，,其次看它的真值是否唯一。,2020/7/21,离散数学,8,二、与命题相关的几个概念,1、简单命题(或原子命题)： 命题为简单的陈述句，不能分解成更简单的句子。一般用小写的英文字母p, q, r, 表示。,2、命题常项(或命题常元)： 由于简单命题的真值确定，故又称之为命题常项 或命题常元。 如例1中的陈述句(1) (2) (3) (4) (5)。,2020/7/21,离散数学,9,二、与命题相关的几个概念（续）,3、命题变项(或命题变元)：

5、真值可以变化的简单陈述句，但它不是命题,也可以用p,q,r等表示。 如例1中的陈述句(6) (5x + 1 11)。,4、复合命题： 由简单命题用联结词联结而成的命题。 命题逻辑主要就是研究复合命题。,5、命题的符号化： 用符号来表示命题。,2020/7/21,离散数学,10,三、联结词,先看一个例子： 例2：判断下列命题是否为复合命题，说出其联结词。 (1) 3不是偶数。 (2) 2是偶素数。 (3) 2或4是素数。 (4) 如果2是素数，3也是素数。 (5) 2是素数当且仅当4也是素数。,(非),(且),(或),(如果,则),(当且仅当),2020/7/21,离散数学,11,三、联结词（续

6、）,常见的基本联结词： 1、否定联结词“ ”，读作“非”。 复合命题“非p ”称作p 的否定式，记作“ p ”。 p 为真当且仅当p 为假。,在命题“3不是偶数”中，设p 表示“3是偶数”，则 p 表示“3不是偶数”。显然，p 真值为0， p 真值 为1 。,2020/7/21,离散数学,12,三、联结词（续）,2、合取联结词“ ”，读作“合取”。 复合命题“ p并且q ”称作p 与q 的合取式，记“ p q ”。 p q 为真当且仅当p 与q 同时为真。,在命题“2是偶素数”中，设 p 表示“2是素数”， q 表示“2是偶数”，则 p q 表示“2是偶素数”。因为 p和q 的真值均为1， 所

7、以 p q 的真值为1 。,联结词“既又”，“不但而且”，“虽然但是”等，都可符号化为 。,2020/7/21,离散数学,13,三、联结词（续）,3、析取联结词“ ”，读作“析取”。 复合命题“ p或q ”称作 p与q 的析取式，记作“p q ”。 p q 为真当且仅当 p 与 q 中至少一个为真。,在命题“2或4是素数”中，设 p 表示“2是素数”， q 表示“4是素数”，则 p q 表示“2或4是素数”。,注意：“或”的二义性。如命题：派小王或小李中 的一人去开会，应符号化为( p q ) ( p q ), 这类“或”表达的是排斥或。,2020/7/21,离散数学,14,三、联结词（续）,

8、4、蕴涵联结词“ ”，读作“蕴涵”。 复合命题“ 如果 p，则 q ”称作p 与q 的蕴涵式，记作 “ p q ”。其中 p 称为蕴涵式的前件， q 称为蕴涵 式的后件。 p q 为假当且仅当 p 为真且 q 为假。,在命题“如果2是素数，3也是素数”中，设 p 表示“2是素数”，q 表示“3是素数”，则 p q 表示“如果2是素数，则3也是素数”。,联结词“只要 p 就 q ”，“ p 仅当 q ”，“只有q才p ”等，都表示q是p的必要条件,因此都可符号化为 p q 。,2020/7/21,离散数学,15,三、联结词（续）,5、等价联结词“ ”，读作“等价”。 复合命题“ p 当且仅当 q

9、 ”称作 p 与 q 的等价式，记 作“ p q ”。 p q 为真当且仅当 p 与 q 真值相同。,在命题“2是素数当且仅当4也是素数”中，设 p 表示“2是素数”，q 表示“4是素数”，则 p q 表示“2是素数当且仅当4是素数”,由于p、q的真值分别为1、0，所以p q的真值为0。,2020/7/21,离散数学,16,真值表,利用以上5种联结词，可将复合命题符号化，进 而正确分析出复合命题的真值。基本真值表如下：,p q, p,p q,p q,p q,p q,0 0,0 1,1 0,1 1,1 1 0 0,0 0 0 1,0 1 1 1,1 1 0 1,1 0 0 1,表1.1,2020

10、/7/21,离散数学,17,(1) 李平不是不聪明，而是不用功。 (2) 李文和李武是兄弟。 (3) 只有不下雨，我才骑自行车上班。 (4) 如果下雨，我就不骑自行车上班。 (5) 我去书店看看，除非我很累。,设p:我很累,q:我去书店看看,则符号化为 p q,例3 将下列命题符号化,设p:李文和李武是兄弟，则符号化为p,设p:天下雨,q:我骑自行车上班, p是q的必要条件则符号化为q p,设p:天下雨,q:我骑自行车上班,则符号化为p q,设p:李平聪明，q:李平用功,则符号化为 ( p) q,解题步骤: (1) 分析出各简单 命题，并符号化； (2) 使用合适的联 结词，把简单命题 逐个联

11、结起来，组 成一复合命题的符 号化形式。,2020/7/21,离散数学,18,例3 将下列命题符号化（续）,(6) 2 + 2 4，当且仅当3不是奇数。 (7)小王是游泳冠军或百米赛跑冠军。 (8) 小王现在在宿舍或在图书馆。 (9) 选小王或小李中的一人当副班长。,设p:2 + 2 = 4，q:3是奇数, 则符号化为 p q,设p:选小王当副班长，q:选小李当副班长,则符号化为(p q) ( p q),设p:小王在宿舍，q:小王在图书馆,符号化为p q,这里的“或”本来是排斥或，排斥或一般不能直接用“ ”联结，但两个命题不能同时为真时例外，因此,命题可符号化为p q ，其中p:小王在宿舍，q

12、:小王在图书馆,设p:小王是游泳冠军，q:小王是百米赛跑冠军,符号化为p q,2020/7/21,离散数学,19,例3 将下列命题符号化（续）,(10) 如果我上街，我就去书店看看，除非我很累。 (11)王一乐是计算机系的学生, 他生于1968年或1969 年, 他是三好学生。,设p：我上街，q：我去书店看看，r：我很累， r是（pq）的充分条件则符号化为r (p q),该命题也可叙述为“如果我不累并且我上街，则我就去书店看看。”，因此（10）也可符号化为( r p ) q,设p：王一乐是计算机系的学生，q：他生于1968年，r：他生于1969年，s：他是三好学生，则符号化为：p (q r)

13、s,2020/7/21,离散数学,20,合式公式：,一、命题公式的概念,1.2 命题公式及其赋值,(1) 单个命题常项或变项p, q, , 0, 1是合式公式；,(2) 若A是合式公式，则 A也是合式公式；,(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)是合式公式;,合式公式即称为命题公式。,(4) 只有有限次地应用(1) (3)组成的符号串才是 合式公式。,2020/7/21,离散数学,21,一个含有命题变项的命题公式的真值是不确定的，只有用指定的命题常项代替后真值才唯一确定。,二、命题公式的解释或赋值,设A为一命题公式，p1, p2, , pn为出现在

14、A中的所有的命题变项。给p1, p2, , pn指定一组真值，称为对A的一个赋值或解释。,若指定的一组真值使命题公式A的真值为1，则 称这组赋值为A的成真赋值；若使A的真值为0，则 称这组赋值为A的成假赋值。,将命题公式A在所有赋值下的取值情况列成表， 称为A的真值表。,2020/7/21,离散数学,22,(3)对应每个赋值，计算命题公式各层次的值，直到 最后计算出命题公式的值。,二、命题公式的解释或赋值（真值表）,构造真值表的步骤：,命题运算的优先级顺序：(1)先括号 (2) (3) , (4) (5) (6) 从左至右,(1)找出命题公式中所有命题变项：p1 , p2 , , pn , 列

15、出所有可能的赋值(2n个)。,2020/7/21,离散数学,23,二、命题公式的解释或赋值（真值表）,例4：求下列命题的真值表 (1) ( p) q (2) ( p ( p q ) q (3) ( p q ) q,2020/7/21,离散数学,24,二、命题公式的解释或赋值（真值表）,(1) ( p) q,2020/7/21,离散数学,25,二、命题公式的解释或赋值（真值表）,(2) (p ( p q ) q,表1.3,2020/7/21,离散数学,26,二、命题公式的解释或赋值（真值表）,(3) ( p q ) q,2020/7/21,离散数学,27,三、命题公式的类型,命题公式A在各种赋值

16、下取 值恒为真，则A为重言式。,命题公式A在各种赋值下取 值恒为假，则A为矛盾式。,命题公式A至少存在一组赋值是成真 赋值，则A为可满足式。,1、重言式(或永真式)： 2、矛盾式(或永假式)： 3、可满足式：,2020/7/21,离散数学,28,三、命题公式的类型,3、真值表可以用来判断公式的类型： （1）若真值表最后一列全为1，则公式为重言式；,1、可满足式至少存在一组成真赋值。,2、重言式一定是可满足式，反之不真。,从以上定义可以看出以下几点：,（2）若真值表最后一列全为0，则公式为矛盾式；,（3）若真值表最后一列至少有一个1，则公式为 可满足式。,2020/7/21,离散数学,29,一、

17、等值演算的概念,等值关系是自反的、对称的和传递的，因而为 等价关系。,等值演算：按一定方法寻找某个复合命题公式的等 值式的过程。,1.3 等值演算,等值公式：设A, B为两命题公式，若等价式A B 是重言式，称A与B等值。记作:A B,用真值表可以验证公式等值。,2020/7/21,离散数学,30,例5：判断命题是否等值 ( p q) 与 p q,不 等 值,一、等值演算的概念（续）,2020/7/21,离散数学,31,二、常用的重要等值公式表,1、A ( A),2、A A A,3、A A A,4、A B B A,5、A B B A,6、(A B) C A (B C),7、(A B) C A

18、(B C),双重否定律,结合律,交换律,等幂律,2020/7/21,离散数学,32,二、常用的重要等值公式表（续）,分配律,零律,吸收律,德摩根律,8、A (B C ) (A B) (A C),9、A (B C ) (A B) (A C),10、 (A B) A B,11、 (A B) A B,12、A (A B) A,13、A (A B) A,14、A 1 1,15、A 0 0,2020/7/21,离散数学,33,二、常用的重要等值公式表（续）,同一律,归谬论,蕴涵等值式,排中律,16、A 0 A,17、A 1 A,19、A A 0,20、A B A B,21、A B (A B) (B A

19、),22、A B B A,23、A B A B,24、(A B) (A B ) A,18、A A 1,矛盾律,等价否定等值式,等价等值式,假言易位,2020/7/21,离散数学,34,以上24个等值式必须熟记，并注意其中所含的 A, B, C可以是任意的一个命题公式，因而每个公式 是一个模式，可以代表无数多个同类型的命题公式。,利用24个基本等值式，不用真值表法也可以推 演出很多等值式。,二、常用的重要等值公式表（续）,2020/7/21,离散数学,35,设 (A)是含命题公式A的命题公式, (B)是用B置换了 (A)中的A之后得 到的命题公式。若A B, 则 (A) (B) 。,此外，在进行

20、等值演算时，常常用到：,置换定理,二、常用的重要等值公式表（续）,如： (A)： p (q r)， A： q r B： q r， (B)： p ( q r),由于： A B，故 (A) (B),2020/7/21,离散数学,36,例6：验证下列等值式 (1) p (q r) ( p q) r (2) p ( p q) ( p q),解题思想: 可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。,三、应用,2020/7/21,离散数学,37,例6：验证下列等值式 (1) p (q r) ( p q) r, p ( q r), ( p q) r,蕴涵等值式,蕴涵等值式,结合律,德摩根律

21、,蕴涵等值式,三、应用（续）,2020/7/21,离散数学,38,例6：验证下列等值式 (2) p ( p q) (p q), ( p q) ( p q),同一律,排中律,分配律,三、应用（续）,2020/7/21,离散数学,39,例7：判别下列公式的类型 (1) q ( p q ) p ) (2) ( p p ) (q q) r) (3) ( p q ) p,解题思想: 真值表法和等值演算都可以用来判别公式的类型，但等值演算更为简单快捷。,三、应用（续）,2020/7/21,离散数学,40,例7：判别下列公式的类型 (1) q ( p q ) p ),解： (1) q ( p p ) (q

22、p), q (0 (q p), q (q p), q ( q p), (q q) p, 1 p, 1,分配律,矛盾律,同一律,德摩根律,结合律,排中律,零律,重 言 式,三、应用（续）,2020/7/21,离散数学,41,例7：判别下列公式的类型 (2) ( p p) (q q) r), 1 (0 r), 1 0, 0,矛盾律,零律,排中律,矛 盾 式,三、应用（续）,解： (2) 1 (q q) r),2020/7/21,离散数学,42,例7：判别下列公式的类型 (3) ( p q) p,解： (3) ( p q) p, p,吸收律,蕴涵等值式,可 满 足 式,三、应用（续）,2020/7/

23、21,离散数学,43,除了前面我们介绍的5种基本联结词，这里再给 出逻辑设计中常用的3种：,1.4 联结词的完备集,2020/7/21,离散数学,44,2、与非：复合命题“ p与q 的否定”称作p 与q 的与非 式，记作“ p q ”。 p q为真当且仅当 p, q不同时为真。,等值关系：p q ( p q),3、或非：复合命题“ p或q 的否定”称作p 与q 的或非 式，记作“ p q ”。 p q为真当且仅当 p, q同时为假。,等值关系：p q ( p q),2020/7/21,离散数学,45,真值表,2020/7/21,离散数学,46,冗余联结词和独立联结词：在联结词集合中, 如果 一

24、个联结词可以由集合中其它的联结词来 定义，则称此联结词为冗余联结词，否则 称为独立联结词。 例如: , ， 中的 或是冗余联结词.,全功能集：如果任一真值函数(公式)，都可以仅用某一联 结词集合中的联结词的命题公式表示，则称该集合为全功能集。例如: , ， ， , ， , ， ,不含冗余联结词的全功能集称为极小全功能集。,2020/7/21,离散数学,47,常见的全功能集（也是极小全功能集）: , , , , , , , ,2020/7/21,离散数学,48,又： (p q) 0 的对偶式： (p q) 1,如： p (q r)的对偶式是 p (q r),一、对偶式的概念,在常见的基本等值式中

25、，多数公式是成对出现的，它们相互构成对偶式。,对偶式：在仅含有联结词 , , 的命题公式A中， 将 换成 ， 换成 ，0换成1，1换成0， 所得命题公式称为A的对偶式。记作：A*,显然，对偶式是相互的，即(A*)*= A,1.5 对偶与范式,2020/7/21,离散数学,49,设A与A*互为对偶式，P1, P2, , Pn是出现 在A和A*中的所有命题变元，如果用n元函 数的形式表达，则有 (1) A (P1 , P2 , , Pn ) A*( P1 , P2 , , Pn ) (2) A ( P1 , P2 , , Pn) A*( P1 , P2 , , Pn ),二、关于对偶式的两个定理,

26、定理,2020/7/21,离散数学,50,如：设A (p, q, r) p (q r),二、关于对偶式的两个定理（续）,则 A (p, q, r) ( p (q r) ) p ( q r) A*(p, q, r) p (q r) A*( p, q, r) p ( q r),于是有 A (p, q, r) A*( p, q, r),又 A ( p, q, r) p ( q r)， A*(p, q, r) ( p (q r) ) p ( q r)，,于是有 A ( p, q, r) A*( p, q, r),2020/7/21,离散数学,51,设A与B为两命题公式，如果A B， 则A* B*。,二

27、、关于对偶式的两个定理（续）,由此可知： A*为重言式 A为矛盾式 A*为矛盾式 A为重言式 A*为可满足式 A为可满足式 “两公式等值” “两公式的对偶式等值”,对偶定理,2020/7/21,离散数学,52,仅由有限个命题变元或其否定构成的 析取式，如 p q， p q。,三、范式的概念,显然：简单析取式是重言式，当且仅当它同时含有 一个命题变项及其否定； 简单合取式是矛盾式，当且仅当它同时含有 一个命题变项及其否定。,仅由有限个命题变元或其否定构成的 合取式，如 p q。,简单析取式： 简单合取式：,2020/7/21,离散数学,53,仅由有限个简单合取式构成的析取式。 如A=A1 A2

28、An , Ai (i =1, 2, , n)为简单合取式。,三、范式的概念（续）,由对偶的定义知：析取范式的对偶式为合取范式，合取范式的对偶式为析取范式。,性质：析取范式为矛盾式，当且仅当构成它的每一个简单合取式都是矛盾式；合取范式为重言式，当且仅当构成它的每一个简单析取式都是重言式。,仅由有限个简单析取式构成的合取式。 如A=A1 A2 An , Ai (i =1, 2, , n)为简单析取式。,析取范式： 合取范式：,2020/7/21,离散数学,54,任一命题公式都存在着与之等值 的析取范式和合取范式。,求范式的步骤：,(2) 的消去或内移。利用德摩根律或双重否定律,三、范式的概念（续）

29、,范式存在定理,(1) 消去对 , , 来说冗余的联结词。 , , 是全功能集，其他联结词都可用基本等值式消去,(3) 利用分配律。求析取范式，可利用 对 的分配 律；求合取范式，可利用 对 的分配律。,2020/7/21,离散数学,55,三、范式的概念（续）,2020/7/21,离散数学,56,例8：求命题公式( ( p q ) r ) p 的合取范式和 析取范式。,解：(1) 求析取范式 ( ( p q ) r ) p, ( p q ) r ) p, ( p r ) ( q r ) p, p ( q r ),四、应用, ( p q ) r ) p, ( p q ) r ) p,2020/7

30、/21,离散数学,57,例8：求命题公式( ( p q ) r ) p 的合取范式和 析取范式。,四、应用（续）,解： (2) 求合取范式 ( ( p q ) r ) p, ( p q ) r ) p, ( p q p ) ( r p ), ( p q) ( r p ),2020/7/21,离散数学,58,值得注意的是，任何命题公式的析取范式或合取 范式不唯一，因而不能作为命题公式的标准型。为 此，我们进一步引入“主析取范式”、“主合取范式” 的概念。它们是用极小项、极大项来定义的。,2020/7/21,离散数学,59,注1：其中 指pi或pi，1 i n 注2：极小项、极大项中必含有n-1个

31、联结词 注3： 一定位于第i个位置，顺序不能乱,五、主析取范式与主合取范式,极小项： 极大项：,2020/7/21,离散数学,60,五、主析取范式与主合取范式（续）,pqr pqr pqr pqr pqr pqr pqr pqr,成 真 赋 值,极小项的表示（以3个命题变项为例）：,000 - 0，记作m0 001 - 1，记作m1 010 - 2，记作m2 011 - 3，记作m3 100 - 4，记作m4 101 - 5，记作m5 110 - 6，记作m6 111 - 7，记作m7,2020/7/21,离散数学,61,五、主析取范式与主合取范式（续）,极小项的性质（以3个命题变项为例）：,

32、（1）每一个极小项当其真值指派与编码相同时，其真值为1，在其余7(2n-1)种指派情况下均为0。,（2）任意两个不同的极小项的合取式永假。如： m0m3 = (pqr) (pqr) 0,（3）全体极小项的析取式永真,m0 m1 m2n-1 1,2020/7/21,离散数学,62,五、主析取范式与主合取范式（续）,成 假 赋 值,极大项的表示（以3个命题变项为例）：,000 - 0，记作M0 001 - 1，记作M1 010 - 2，记作M2 011 - 3，记作M3 100 - 4，记作M4 101 - 5，记作M5 110 - 6，记作M6 111 - 7，记作M7,pqr pqr pqr

33、pqr pqr pqr pqr pqr,2020/7/21,离散数学,63,五、主析取范式与主合取范式（续）,极大项的性质（以3个命题变项为例）：,（1）每个极大项当其真值指派与编码相同时，其 真值为0，在其余7(2n-1)种指派情况下均为1。,（2）任意两个不同的极大项的析取式永真。如： M0 M3 = (pqr) (pqr) 1,（3）全体极大项的合取式永假。,M0 M1 M2n-1 0,2020/7/21,离散数学,64,五、主析取范式与主合取范式（续）,任何命题公式的主析取范式和主合取范式 一定存在，并且唯一。,定理,主析取范式： 主合取范式：,命题公式A的析取范式中的简单合取式 全是

34、极小项。特别地约定，矛盾式的 主析取范式为0。,命题公式A的合取范式中的简单析取式 全是极大项。特别地约定，重言式的主合取范式为1。,2020/7/21,离散数学,65,(4) 将极小项按从小到大的顺序排列，并用表示 如m1 m4 m5 (1, 4, 5),给定命题公式A的主析取范式的求解步骤:,五、主析取范式与主合取范式（续）,(1) 求A的析取范式A,(2) 若A的某简单合取式B中不含命题变项pi 或 pi， 则展开B如下： BB 1 B (pi pi)(B pi) (B pi),(3) 消去重复出现的命题变项、极小项和矛盾式。,2020/7/21,离散数学,66,(4) 将极大项按从小到

35、大的顺序排列，并用表示 如M1 M4 M5 (1, 4, 5),给定命题公式A的主合取范式的求解步骤:,五、主析取范式与主合取范式（续）,(1) 求A的合取范式A,(2) 若A的某简单析取式B中不含命题变项pi 或 pi， 则展开B如下： BB 0 B (pi pi)(B pi) (B pi),(3) 消去重复出现的命题变项、极大项和重言式。,2020/7/21,离散数学,67,例9：求公式( p r) q) (q p)的主析取范式和 主合取范式。,六、应用,解： (1) 求主析取范式 ( p r) q) (q p), ( p r) q) ( q p), ( p r) ( q p) (q (

36、q p),2020/7/21,离散数学,68,六、应用（续）, ( p q) (r q) (r p) (q 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), m0 m1 m5 m6 m7,(0, 1, 5, 6, 7),2020/7/21,离散数学,69,六、应用（续）,(2) 求主合取范式 (p r) q) (q p), ( p r) q) ( q p), ( p r q) ( q p), ( p q r) (p q r ) (p q r), M4 M3 M2,(2, 3, 4),2020

37、/7/21,离散数学,70,五、主析取范式与主合取范式（续）,在真值表中，一个公式的真值为1的指派（成真赋值）所对应的极小项的析取式，即为公式的主析取范式。,在真值表中，一个公式的真值为0的指派（成假赋值）所对应的极大项的合取式，即为公式的主合取范式。,定理,定理,真值表法求公式的主析取范式和主合取范式。,2020/7/21,离散数学,71,五、主析取范式与主合取范式（续）,例10. 试用真值表法求命题公式(p r) q) (q p) 的成真赋值、成假赋值、主析取范式、主合取范式。,p r (p r) q q p (p r) q) (q p),1 1 1 1 0 1 0 1,1 1 1 1 0

38、 1 1 1,1 1 0 0 1 1 1 1,1 1 0 0 0 1 1 1,2020/7/21,离散数学,72,五、主析取范式与主合取范式（续）,解：由真值表可知，公式A的成真赋值为000、001、 101、110、111，其对应的极小项分别为m0、m1、 m5、 m6、m7， 因此公式A的主析取范式为： A m0 m1 m5 m6 m7,由真值表可知，公式A的成假赋值为010、011、100， 其对应的极大项分别为M2 、 M3、 M4， 因此公式A的主合取范式为： A M2 M3 M4,2020/7/21,离散数学,73,A为重言式，当且仅当A的主析取范式含所有极小项 A为矛盾式，当且仅

39、当A的主析取范式不含任何极小项 A为可满足式，当A的主析取范式中至少含一个极小项,A为重言式，当且仅当A的主合取范式不含任何极大项 A为矛盾式，当且仅当A的主合取范式含所有极大项 A为可满足式，当A的主合取范式中至多含七个极大项,六、应用（续）,主析取范式（主合取范式）的用途：,(2) 判断两命题公式是否等值。通过判断两命题公式 的主析取范式（主合取范式）是否相等,(3) 判断命题公式的类型。,(1) 求命题公式的成真和成假赋值。,2020/7/21,离散数学,74,例11：判断下列命题公式的类型 (1) ( p q) q (2) ( p q) p) q,六、应用（续）,解：(1) ( p q

40、) q, ( p q) q, p q q, 0,矛 盾 式,2020/7/21,离散数学,75,例11：判断下列命题公式的类型 (1) ( p q) q (2) ( p q) p) q,六、应用（续）, ( p q) p) q,解：(2) ( p q) p) q, ( p q) p q, ( p q) ( p q) ( p q) ( p q),重 言 式, m2 m1 m0 m3,(0, 1, 2, 3),2020/7/21,离散数学,76,六、应用（续）,设命题公式含n个命题变项，其主析取范式中含k个极小项 ，不含极小项 ， 则主合取范式中含极大项 ,如：A中含3个命题变项， A m0 m1

41、 m6 m7 (0, 1, 6, 7),主析取范式和主合取范式的关系：,则A M2 M3 M4 M5 (2, 3, 4, 5),2020/7/21,离散数学,77,一、推理的概念,推理：从前提推出结论的思维过程。,前提指已知的命题公式，结论是从前提出发按照一定的推理规则推出的命题公式。,逻辑结论（有效结论）：若( A1 A2 An ) B 为重言式，,则称A1, A2, , An推结论B的推理正确， B是A1, A2, , An的逻辑结论或有效结论。,并记之为(A1 A2 An ) B,1.6 推理理论,2020/7/21,离散数学,78,例12：判断下面各推理是否正确 (1) 如果天气凉快，

42、小王就不去游泳。天气凉快, 所以小王没去游泳。 (2) 如果我上街，我一定去新华书店。我没上街， 所以我没去新华书店。,二、应用,解题思想: (1) 将命题符号化； (2) 写出前提、结论和推理的形式结构； (3) 用真值表法、等值演算或主析取范式法进行判断。,2020/7/21,离散数学,79,(1) 如果天气凉快，小王就不去游泳。天气凉快, 所以小王没去游泳。,二、应用（续）,解：设p：天气凉快，q：小王去游泳,前提： p q , p 结论： q,推理的形式结构为 ( p q) p) q (*),2020/7/21,离散数学,80,下面判断(*)式是否为重言式,二、应用（续）,( p q)

43、 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), m3 m1 m0 m2,推 理 正 确, (0, 1, 2, 3),2020/7/21,离散数学,81,(2) 如果我上街，我一定去新华书店。我没上街， 所以我没去新华书店。,二、应用（续）,解：设p：我上街，q：我去新华书店,前提： p q , p 结论： q,推理的形式结构为 (p q) p) q (*),2020/7/21,离散数学,82,下面判断(*)式是否为重言式,二、应用（续）,(p q) p) q, (

44、p q) p) q, ( p q) p) q, ( ( p q) p) q, ( p q) p q, ( p q) ( p q) ( p q), m2 m3 m0,推 理 不 正 确, (0, 2, 3),2020/7/21,离散数学,83,三、构造证明法,推理规则：在推理过程中，构造证明必须在给定的规则下进行，常用的推理如下：,(1) 前提引入规则: 证明的任何步骤上，都可引入前提；,证明：描述推理过程的命题公式序列。,(2) 结论引入规则：证明的任何步骤上，所证明的结论都 可作为后续证明的前提；,(3) 置换规则：证明的任何步骤上，命题公式中的任何子 命题公式都可以用与之等值的命题公式置换

45、；,2020/7/21,离散数学,84,(4) 假言推理规则：A B, A |= B,三、构造证明法（续）,(5) 附加规则： A |= A B,(8) 假言三段论规则： A B, B C |= A C,(11) 合取引入规则： A, B |= A B,(6) 化简规则： A B |= B,(7) 拒取式规则： A B, B |= A,(10) 构造性二难规则： A B, C D, A C |= B D,(9) 析取三段论规则： A B, B |= A,2020/7/21,离散数学,85,例13：构造下列推理的证明 (1) 前提：p r, q s, p q 结论：r s (2) 前提：p q, p r, s t, s r, t 结论：q,四、应用,2020/7/21,离散数学,86,(1) 前提：p r, q s, p q 结论：r s,四、应用（续）,证明： p r, q s, p q, r s,前提引入,前提引入,前提引入,构造性二难,2020/7/21,离散数学,87,(2) 前提：p q, p r, s t, s r, t 结论：q,四、应用（续）,证明： t, s t, s, s r,前提引入,前提引入,拒取式,析取三段论, r, p r, p, p q, q,前提引入,拒取式,前提引入,前提引入,假言