离散数学第一章 1

1、离散数学,主讲教师:刘志伟,离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。,离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。,数理逻辑简介,数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最

2、为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。,第一章命题逻辑,第一节 命题符号化及联结词,内容：命题，逻辑联结词，命题符号化,(1)掌握命题概念 (2)掌握联结词含义及真值表 (3)掌握命题符号化方法,重点：,一、命题的概念,命题：具有唯一真值的陈述句。,对事物有确切的肯定或否定的一种思维形式,判断:,例1、判断下列句子中哪些是命题。,(1) 北京是中国的首都。,(2) 雪是黑色的。,(4) 请把门关上！,(6) 地球外的星球上也有人。,例1、判断下列句子中哪些是命题。,(7) 明天有课吗？,(8) 本语句是假的。,(

3、9) 小明和小林都是三好生。,(10) 小明和小林是好朋友。,判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。,表示。,命题常项1,0，命题变项用,(11)我正在说谎,二、逻辑联结词。,真值表,真值表,(1) 李平既聪明又用功。,(2)李平虽然聪明，但不用功。,(3)李平不但聪明，而且用功。,(4)李平不是不聪明，而是不用功。,真值表,我在看电视或我在吃饭,我去图书馆或我去食堂,可兼或:,不可兼或:,真值表：,真值表：,6、逻辑联结词与自然语言中联结词的关系。,否定不是，没有，非，不。,合取并且，同时，和，既又，不但而且，虽然但是。,析取或者，或许，可能。,蕴涵若则，假如那么，

4、既然那就，倘若就。,等价当且仅当，充分必要，相同，一样。,7、运算顺序,例如：,三、命题分类。,按真值分:,按联结词联结情况:,真命题:真值为真 假命题:真值为假,简单命题:不能由其它联结词联结的 复合命题:可以由其它联结词联结的,(1)中国是世界上人口最多的国家,(2)木星上有水,(3)多么壮观的景色啊!,(4)2不是素数,四、命题符号化。,步骤：(1) 找出各简单命题，分别符号化。,(2) 找出各联结词，把简单命题逐个联结起来。,例6、将下列命题符号化。,(1) 小王是游泳冠军或百米赛跑冠军。,(2) 小王现在在宿舍或在图书馆。,例6、将下列命题符号化。,(3) 选小王或小李中的一人当班长

5、。,(4) 如果我上街，我就去书店看看，除非我很累。,(5) 小丽是计算机系的学生，她生于1982或1983年， 她是三好生。,(6) 3不是偶数,设 P:3 是偶数,(7) 李平不是不聪明,而是不用功,设 P:李平聪明 q:李平不用功,原语句化为:,原语句化为:,(8)若3+2=5则太阳从西边升起,(9)3+2=6的充分必要条件是有外星人存在,(10)如果7是3的倍数,或者5是素数,则老虎会飞同时人可以在月球上行走,(11)仅当我有时间且天不下雨,我将去镇上,(12)张刚总是在图书馆看书,除非图书馆不开门或张刚生病,第二节 命题公式及分类,内容：命题公式，重言式，矛盾式，可满足公式。,重点：

6、(1) 掌握命题公式的定义及公式的真值表。,(2) 掌握重言式和矛盾式的定义及使用真 值表进行判断。,一、命题公式,通俗地说，命题公式是由命题常项，命题变项， 联结词，括号等组成的字符串。,单个的命题变元和命题常元称原子公式,合式公式是如下定义的符号串: (1)原子公式是合式公式,(3)只有有限次应用(1)和(2)得到的符号串才是合式公式,例1、判断以下字符串中哪些是命题公式。,(1),(2),(3),(4),(5),(6),解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。,解：,2,真值表,例3、求下列命题公式的真值表。,(2),解：,二、重言式、矛盾式，可满足式。,2、判定方

7、法:真值表法。,1、定义,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,解：列出各题真值表如下(步骤简略),(1)、(2)、(5)、(6)、(9)为重言式； (3)、(8)为矛盾式； (4)、(7)、(10)及以上的重言式均为可满足式。,第三节 等值演算,内容：等值关系，24个重要等值式，等值演算。,重点：(1) 掌握两公式等值的定义。,(2) 掌握24个重要等值式，并能利用其进行等值演算。,一、两命题公式间的等值关系。,2、判定 。,(1) ，,解：作真值表如下：,解：作真值表如下：,(

8、2) ，,二、重要等值式。,二、重要等值式。,二、重要等值式。,10、双重否定律,二、重要等值式。,11、蕴涵等值式,12、等价等值式,13、假言易位,14、等价否定等值式,15、归谬论,三、等值演算。,公式置换:设公式B是A子公式,C是公式,在公式A中B出现的一次或者是多次用C来代替得到新的公式D,从A到D这个过程称公式的置换.,例2、验证下列等值式。,当B和C等值,称这为等值置换,如果是等值置换,A和D也是等值的,例2、验证下列等值式。,(1),解：,蕴涵等值式,蕴涵等值式,结合律,德摩根律,蕴涵等值式,例2、验证下列等值式。,(2),解：,交换律,分配律,排中律,同一律,(3),解：,分

9、配律,矛盾律,同一律,德摩根律,结合律,排中律,零律,(1),(2),练:,(1),考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。,判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法和等值演算法。,例3,判定下列公式类型,(1),(2),(3),(4),例4、用两种方法证明:,证法一 用真值表法,由最后两列真值完全相同，于是命题成立。,例4、用两种方法证明:,证法二 用等值式法,蕴涵等值式,双重否定律,交换律,结合律,吸收律,第四节 联结词的全功能集,内容：联结词的全功能集，极小功能集。,了解：全功能集，极小功能集。,一、全

10、功能集，极小功能集。,全功能集：若干个联结词的集合，其余的联结词均可由它们表示。,最小全功能集：不含冗余联结词的全功能集。,等都是极小全功能集。,冗余联结词:在联结词集合中,如果一个联结词可以由其它的联结词来表示,否则是独立联结词,第五节 对偶与范式,内容：对偶原理，命题公式的范式。,重点：(1) 掌握对偶式，对偶原理。,(2) 掌握析取范式和合取范式的定义和求法步骤。,(3) 掌握极小项，极大项的概念及主范式的求法。,一、对偶原理。,1、对偶式。,与,2、对偶原理。,所以可得：,二、范式。,1、简单析取式，简单合取式。,结论:(1)一个简单合取式是永假式当且仅当同时含 某个命题变元及它的否定

11、. (2)一个简单析取式是永真式当且仅当同时含某个便是变元及它的否定.,2、析取范式，合取范式。,为合取范式。,2、析取范式，合取范式。,为析取范式。,结论:(1)一个析取范式为永假式当且仅当每一个简单合取式为永假式. (2)一个合取范式是永真式,当且仅当每一个简单析取式为永真式,解：原式,消去,内移,消去,上式即析取范式,解：原式,消去,内移,消去,上式即合取范式,求范式步骤：,(2) 否定消去或内移。,(3) 利用分配律。,(1) 消去联结词,2、析取范式，合取范式。,三、主范式。,1、极小项，极大项。,都是极小项，,都是极大项，,极小项的特点: (1)N个变元全部出现. (2)N个变元顺

12、序不能颠倒. (3)P的肯定式和否定式只能出现一次. (4)有n-1个联结词.,极小项真值表的特点: (1)每一个极小项只有一个成真赋值. (2)每一组赋值下面只有一个极小项为真. (3)任意两个极小项的合取式为永假式. (4)全体极小项的析取式为永真式. (5)二进制数写出对应惟一成真赋值极小项.,例,极大项真值表的特点: (1)每一个极大项只有一个成假赋值. (2)每一组赋值下面只有一个极大项为假. (3)任意两个极大项的析取式为永真式. (4)全体极大项的合取式为永假式. (5)二进制数写出对应惟一成假赋值极大项.,例,2、主析取范式，主合取范式。,两种求法，等值式法和真值表法。,定理：

13、任何命题公式的主析取范式、主合取范式 都存在且都是唯一的。,步骤：,解：(1) 列真值表,解：(2) 的成真赋值有010，100，101，110，111,(3) 对应的十进制数为2，4，5，6，7,所以的主析取范式为,步骤：,(3) 消去重复的及永假项。,解：由例1的析取范式为,解：由例1的析取范式为,步骤：,(3) 消去重复的及永真项；,解：由例1，,合取范式,解：由例1，,由例3、例5知：,(2) 写出与(1)中极小项角码相同的极大项，,3、主范式的用途。,(1) 判断两命题公式是否等值。,(2) 判断命题公式的类型。,3、主范式的用途。,(2) 判断命题公式的类型。,(3) 求成真(假)

14、赋值。,(4) 求真值表。,的成假赋值有010，011，100，101。,解：真值表,第六节 推理规则,内容：,重点：,(1) 理解推理的概念；,(2) 掌握8条推理定律；,(3) 掌握推理规则；,(4) 掌握构造证明法。,了解：,附加前提证明法和归谬法。,一、推理的形式结构。,例1、判断下面各推理是否正确。,结论：,推理形式结构为：,判断此蕴涵式是否为重言式。,方法一 用等值式法。,所以推理正确。,方法二 用真值表法。,其真值表中最后一列全为1，,所以推理正确。,前提：,结论：,推理的形式结构为：,方法一,方法二,蕴涵等值式,吸收律,方法三,二、基本蕴涵关系式,(1) 附加,(2) 化简,(

15、3) 假言推理,(4) 拒取式,(5) 析取三段论,二、构造证明法。,(6) 假言三段论,(7) 等价三段论,(8) 构造性二难,1、自符表。,2、公式。,三，自然推理,3、推理规则。,（一）、自然推理的三个组成部分。,(1) 前提引入规则 蕴（P规则）,(3) 置换规则（E规则）,（二）、自然推理的规范化形式。,(2) 结论引入规则（T规则）,(4) 永真蕴涵规则（I规则）,例2、构造下列推理的证明。,证明：,前提引入,前提引入,前提引入,构造性二难,例2、构造下列推理的证明。,证明：,前提引入,前提引入,拒取式,前提引入,假言推理,例2、构造下列推理的证明。,证明：,前提引入,拒取式,前提

16、引入,析取三段论,例3、写出对应下面推理的证明。,解：,前提：,结论：,（一）直接法,四，推理的证明方法,证明：,前提引入,前提引入,假言推理,前提引入,前提引入,假言推理,析取三段论,前提：,结论：,解：,前提：,结论：,证明：,前提引入,置换规则,前提引入,假言推理,前提引入,拒取式,前提：,结论：,解：,前提：,结论：,解：,前提：,结论：,附加前提证明法和归谬法。,(1) 附加前提证明法。,（二）间接法（CP规则）,例如：例3 (3),前提：,结论：,用附加前提证明：,附加前提引入,前提引入,拒取式,例如：例3 (3),前提：,结论：,用附加前提证明：,前提引入,假言推理,化简,由附加

17、前提证明法知推理正确。,(2) 归谬法。,因为,例如：例3 (2),前提：,结论：,用归谬法证明：,否定结论引入,前提引入,假言推理,前提引入,例如：例3 (2),前提：,结论：,用归谬法证明：,析取三段论,前提引入,合取,由归谬法知推理正确。,第一章 小结与例题,一、命题与联结词。,1、基本概念。,2、应用。,(1) 选择适当的联结词将命题符号化。,(2) 判断命题(简单或复合)的真假。,二、命题公式及分类。,1、基本概念。,2、应用。,(2) 用真值表判断给定公式的类型。,三、等值演算。,1、基本概念。,两个公式等值的含义；等值演算。,2、应用。,(1) 灵活运用24个重要等值式。,四、联

18、结词的全功能集。,基本概念,联结词的全功能集，极小全功能集。,五、对偶与范式。,1、基本概念。,五、对偶与范式。,2、应用。,(1) 求给定公式的主析取范式和主合取范式。,(4) 用主析取范式或主合取范式判断公式的类型。,六、推理理论。,1、基本概念。,推理，推理规则，推理定律；构造证明法。,2、应用。,(2) 用8条推理定律构造推理的证明。,(2) 2是素数或是合数，,(4) 只有4是奇数，5才能被3整除。,(5) 明年5月1日是晴天。,解：命题有(2)(5)，,(1),解：我将进城去当且仅当我有空且天不下雪。,(2),解：虽然天正在下雪，但我将进城去。,(3),解：我进城当且仅当我有空。,(4),解：天不下雪且我没空。,(1),解：,(2),解：,(3),解：,(4),解：,例4、简化下列命题公式。,(1),解：,例4、简化下列命题公式。,(2),解：,例4、简化下列命题公式。,(3),解：,例4、简化下列命题公式。,(4),解：,(1),(2),(3),(2)为重言式，(3)为矛盾式，(1)，(2)均为可满足式。,解：先求主析取范式,解：先求主析取范式,故主合取范式为,例7、设,解：,例7、设,解：,例7、设,解