离散数学课件全套教学教程整套电子讲义幻灯片.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 命题逻辑,离散数学有何用？:,1计算机的基础是0-1组成的2进制.,0-false,1-true 2进制-布尔代数即命题逻辑,George Boole,19世纪 英国数学老师，它首次将,数学,与,逻辑,联系起来。,1938,香农,在其,硕士论文,中用布尔代数实现开关电路，布尔代数(命题逻辑)成为,数字电路,基础,由于所有内容(整数，实数，字符，汉字，图片，声音，视频，网页，)进入电脑后，全是,01组成的字符串,，从而都可以用,布尔运算,即,逻辑运算,实现，命题逻辑成为,计算机,的基础。,命题逻辑,将,数学,由,连续,变到,离散,，由,高数,进入,离散,。,Google采用逻辑运算进行搜索：,数字之美 吴军,杨圣洪 000100010001110000 两者对应位置,与,运算。,离散数学 100100000000100001,000,1,00000000,1,00000 逻辑运算 1秒10亿,离散数学有何用？:哥尼斯堡 康德老家,2七桥问题，可用于网络爬虫去搜索下载网页.,图中ABCD看成网站，桥就是“超链接”。,图论是离散数学非常重要的内容。,Euler,通过互联网或图书馆,查看离散数学与计算机哪些课程相关，数字电路设计，计算理论，数据库，编译原理，操作系统，体系结构，所有计算机专业。,目的:,1掌握离散数学,五大核心,内容（集合论、数理逻辑、代数结构、图论、组合数学）的基本概念、基本理论、基本方法，训练提高学生的概括抽象能力、逻辑思维能力、归纳构造能力，培养学生严谨、完整、规范的科学态度和学习思维习惯。,2通过,课程实验,的训练，应用所学理论锻炼学生在数学建模、设计算法、编写程序和调试方面的能力。,学习方法:,1勤查资料掌握每章的发展历史，与其他课程的横向联系，想明白为什么要学这些内容，在整个 计算机学科中处于什么位置用途？,2、提高听堂效率，课后立马看懂例题，争取当日做完习题，不过23点，越拖越学不下去。,3、勤于用程序解题，解能解之题！写程序是将你的算法，告诉计算机，让电脑解放人脑，你会发现电脑真的好蠢！人脑想办法让脑聪明起来。,4、多交流，同一道较难的题，往往有多种解法，有这本书的，其那本书的，有我的，有你的，有他的。,考核方法:,总评成绩=25%*期中考试+35%*,（程序设计*40+小班讨论*20%+20%*作业+20%*课堂测试）,+,40%*期末考试。,小班课实为习题讲解课。,小班课上课前交作业，小班讨论由老师抽查作业决定哪位同学上来讲，在讲的过程中老师予以打分。,程序设计在课后完成，实验课期间，助教与任课老师验收程序，学生直接讲解程序如何设计及当面改动程序。,实验课时间：,跟助教商定,引言,逻辑学,是推理的基础，在,社会学,、,自然科学,尤其计算机学科中得到普遍应用。,数理逻辑,是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在,程序设计,、,数字电路,设计、,计算机,原理、,人工智能,等计算机课程得到了广泛应用。,命题逻辑,是,数理逻辑,的基础部分，,但究竟什么是,命题,？,如何,表示,命题？,如何,构造,出复杂的命题？,在本章将,讨论,这些问题。,1.1 命题及联结词,对错,确定,的,陈述语句,称为命题,。如：,(1),湖南大学是985学校。,(2),命题逻辑是计算机科学的基础课程。,(3,)命题逻辑是数字电路的基础。,(4),4是素数。,(5),湖南大学坐落于湘江以东。,(6)地铁4号线,湖南大学站2018年建成。,其中(1)、(2)、(3)与事实相符，是对的、正确的，称为,真命题,，或者称命题的值为“真”，简记为T或数字1。,而(4)、(5)明显与事实不相符，是错的、不正确，称为,假命题,，或称命题的值为“假”，简记为F或数字0。,陈述句(6)的正确性，到2018年12月时能确定的，若届时建成了则它是对的、为真命题，否为假命题。,1.1 命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(7),x与y之和为100，其中x为整数，y为整数,(8),1加1等于10,(7)的对错,不确定,。当x为50、y为50时是对的，当x为51、y为52时是错的。,(8)的对错是,不确定,的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句,不是命题,。,(9)青枫峡,的红叶真美呀！,(10),动作快点！,(11),你是杨老师吗？,这三个语句,不是陈述语句,，因此不是命题。,1.1 命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(12),我在说假话。,(13),派出所说:必须先房子再能上户口,单位后勤说:必须先有户口才能分房,你能上到户口与要到房子吗?,这些是,悖论,，其真值不能确定，故不是命题。,左右为难,！,1.1 命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(12),我在说假话。,(13),派出所说:必须先房子再能上户口,单位后勤说:必须先有户口才能分房,你能上到户口与要到房子吗?,某市仅一位理发师，“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”,有一天理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，能给他自己刮脸呢？,若不刮自己，属于“不给自己刮脸的人”，他就要给自己刮脸，,真给自己刮脸呢？根据其所订规矩，不给自己刮。,1.1 命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(13),我既要学程序设计，又要学离散数学。,(14),我们早餐在公寓食堂或外面早点摊上吃。,(15),我不是数学院的学生,这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。,其中(13)与(14)可分解为另外二句话的组合，,而(15)是对“我是数学院学生”的否定，这些语句称为“,复合命题,”，不能再分解的语句称为“,简单命题,”或“,原子命题,”，为了便于推理与书写，常用,小写字母,表示,简单命题,或,原子命题,。,1.1 命题及联结词,简单命题,组合成,复杂命题,时所使用的辅助词称为“,联结词,”。,命题逻辑中的联结词归纳为以下5种。,合取,：C语言中&and 并且,析取,：C语言中|or 或,否定,：C语言中!not 非,不是,否定,条件式,：C语言中 if()如果那么 若p则q,双条件式,：若p则q且若q则p,当且仅当,1.1 命题及联结词,定义1.1合取,：当,p、q都对,，即取值为真(,T或1,)时，“p,合取,q”的值为,真,.,1.1 命题及联结词,定义1.1合取,：当,p、q,都,对,，都为,真,(,T,或,1,)时，“p,合取,q”的值为,真,，其他情况为,假,。,逻辑运算符,“合取”，,与汉语中,“并且、而且、同时”,含义相当,1.1 命题及联结词,定义1.2析取,：当,p、q,都,不对,，都为,假,(,F,或,0,)时，“p,析取,q”的值为,假,，其他情况为,真,。,逻辑运算符,“析取”，,与汉语中,“或”,含义相当，但有细微的区别,1.1 命题及联结词,运算符“析取”与汉语的“或”几乎一致但有区别：,哪些老师讲离散数学,？有人回答如下：,(16)“,讲离散数学的老师是杨老师或吴老师,”，,分解为,“,讲离散数学的老师是杨老师,”或,“,讲离散数学的老师是吴老师,”，,这两个原子命题有可能,都是对,的，,这种“或”称为“,可同时为真的或,”，,或简称为“,可兼或,”。,这种“或”表示可表 示为“,析取,”,1.1 命题及联结词,运算符“析取”与汉语的“或”几乎一致但有区别：,(17)“周一,的,离散数学教室是A201或301,”，,分解为“周一,的,离散数学教室是A201,”或,“周,一的,离散数学教室是A301,”，,因为这两个原子命题,一个对时另一个错,，,只能这二种情况之一，这种“,或,”称为,“,不可同时为真的或,”，或简称为,“,不可兼或,”、“,排斥或,”.,这种“或”表示,不能简单,表 示为“析取”，,1.1 命题及联结词,定义1.3否定,:当,p是1,，p的否定,p,即为0。,逻辑运算符,“否定”，,与汉语中,“否定”,含义相当.,“,我不是数学院的学生,”可表示为“,我是数学院的学生,”,“,离散数学的教室是202或204,”,表示,离散数学的教室是202不是204,或,“,离散数学的教室不是202是204,p:,离散数学的教室是202,q:,离散数学的教室是204,上面的语句表示:(p,q)(pq),1.1 命题及联结词,定义1.4条件,:当,p是1,q是0时,pq,为0,即,10,为,0,其他情况为,1,。,逻辑运算符,“如果那么”，,如老妈说：“,如果期终考了年级前10名，那么奖励1000元,”。,p:期终考了年级前10名,q:奖励1000元,则上面的语句表示为pq。,先考虑,值为0即假,的情况：,当p为1即“,期终考了年级前10,”，,且q为0即“,没有奖励1000元,”,这时老妈的话是,假话空话,，,故,pq,为,0,1.1 命题及联结词,定义1.4条件式,当,p是1,q是,0,时,pq,为0,即,10,为,0,其他,情况为,1,。p称为前件,q称为后件,(1),当p为,1,即“,我期终考了年级前10,”,q为,0,即“,我老妈没有奖励1000元,”,这时老妈,的话为假,，即pq为,0,(2)当p为,1,即“,我期终考了年级前10,”,q为,1,即“,我老妈奖励1000元,”,这时妈妈的话就对了，即pq为1,(3)至于p为,0,即“,我期终考了年级不是前10,”时,无论,q为1或为0，即无论我老妈,奖励,1000元或,不奖励,，都,不能说,老妈的话是,假的,，故,善意,的认为pq为1,均为1,1.1 命题及联结词,定义1.5双条件,:当,p与,q值,相同,时,pq,为1,不同为0。称p当且仅当q,“普通老师,赚了100万当且仅当他中了100万的彩票,”，,普通老师,赚了100万,普通老师,买彩票中了100万大奖,这个例题有点不正点！,“,郎才当且仅当女貌,”，,可以表示为“,郎才,女貌,”,1.2命题公式,对错明确的陈述语句称为,命题，其真值t/f 0/1,C运算,：加+、减-、乘x、除/、余数%，,命题逻辑,：合、析、否定、条件、双条件(,版,),C语言中用,变量x,表示,某些数,，如x*x+x+10是表达式，,命题逻辑中用,变量,p,q,r表示,任意命题,，由,命题常元,与,此类变量,所构成表达式，称为“,命题公式,”。,C有规律 (b*b-4*a*c)/(2*a)括号,单目符(!-),双目符,命题公式,也是括号，单!，双目符(合析条双条),循环方式给出规则，其实也是书写规则（生成规则）,1.2,合法公式,命题公式（,合式,）,定义1.2.1 合法公式判断算法（,生成规则,）,(,版,),(1),单个,命题变元、命题常元为,合法公式,(,原子公式,)。,(2)若A是,合法公式,，则(A)、A是,合法公式,。,(3)若A、B是,合法公式,，则AB、AB、AB、AB是,合法公式,。,(4)有限次使用,(2)(3),形成的字符串均为,合法公式,。,如,：(p1)q是,合法公式。,因为p、1是合公式，则(p1)是,合法公式,，而q是合法公式，故(p1)q是合法公式。,(p1)r不是,合法公式。,因为p、1是合法公式，则(p1)是合法公式，r是合法公式，但(p1)r,不是,合法公式。,1.2,公式,的,值,对于代数式x,2,+y+10，当x与y的值,不确定,时，该代数式的值是,不确定,的。,对于公式(p1)q，由于p与q值,不确定,时，公式(p1)q的,值不确定,，因而,不是命题,。,只有当p与q的值,确定,后，公式(p1)q的值才,确定,，可像表1.2到表1.5一样，给出公式在各种情况下的值，即得到这个公式的,真值表,。,p与q每一种取值称为p、q的一种解释,1.2公式的值,公式(pq)、pq的真值表如下表。,真值表的构造方法,：,(1),命题变元,的取值从,全0,开始，依次加1，直到,全1,，当有n个变元时，则共有,2,n,种不同的取值情况。,(2),分步骤,计算公式的值,(3)见,黑板,上写,成真赋值:如,pq为(0,0),(0,1),(1,1),成假赋值:如,pq为(1,0),1.2公式的值,公式(pq)(qp)、pq的真值表。,无论p/q取何值，这两个公式的值总相等。,(,版,),黑板上慢慢写,1.2公式的值,公式(pq)、p q的真值表。,无论p/q取何值，这两个公式的值总相等。,1.2公式及其值,公式pq、qp的真值表。,无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题,1,1.2公式及其值,公式p(qr)、(pq)(pr)的真值表。,无论p/q取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！,1.3 等值式,定义1.3.1等值：,对于合法的命题公式A、B，若无论其中的,命题变元,取何值，A、B值总相等，称为两个公式,等值,，记为,AB(边播边板),1,1,(1)pqpqqp,条件式的等值式(板),(2)pq(pq)(qp),双条件,(,pq)(p q),(pq)(pq),(3)(pq)pq (pq)pq,德摩律,(4)p(qr)(pq)(pr),分配律,p(qr)(pq)(pr)(边播边板),(5)p(pq)p p(pq)p,吸收律(多吃少),p(,p,q)pq p(,p,q)pq,吸收背判者,(p,q),(p,r),(qr)p,q,p,r,吸收共同助手,(6)pp,双重否定律,(7)ppppp,幂等律,(8)pq qp，pq qp,交换律,(9)p(qr)(pq)r,结合律,p(qr)(pq)r,反演规则(广义德摩律),(,板,),将公式A中：条件式()、双条件(),处理后：,从,左,到,右,依次,完成,以下,反变换,1(T),0(F),0(F),1(T),p,p即p,p,p,得到,A,。,如：(,(pq)(pq),(pq),(pq),(,p,q)(pq),也可用,反演规则,直接写出,对偶等值式规则,(,板,),将等值式两边：条件式()、双条件(),处理后,对等值式从,左,到,右,依次,完成,以下,对偶变换,1(T),0(F),0(F),1(T),得到式子称为,原式,的,对偶式,，仍然,等值式,。,(3)(pq)pq,(pq)pq,德摩律,(4)p(qr)(pq)(pr),p(qr)(pq)(pr),(5)p(pq)p,p(pq)p,吸收律(多吃少),p(,p,q)pq,p(,p,q)pq,吸收背判者,变元换公式规则,(,板,),将等值式中的,变元,换成,合法公式,仍,等值！,如：,pq pq,则有,AB AB,尽管,A/B,可能很复杂，但其值也只有0、1,二种,可能，公式A/B的组合只有,0/0,0/1,1/0,1/1,四种，如下表所示，仍可用真值表证明。,显然有,AB AB,等值演算规则,(,板,),A=(,pq),r,D,=,(,pq),r,将公式A中(,pq,)换成(,pq,),得到公式D,由于(,pq,),(,pq,),所以,A,D,，常直接写成：,(,pq),r,(,pq),r,，称为,等值演算,置换规则(局部等值替换),：,BC,D=A中所有子公式B换成C得到，则,AD,。,局部进行等值,替换后,仍与,原公式,等值。,因为A、D除了“,A中B所在之处、D中C所在之处,”外，其他地方均相同.,而,不同之处,的B与C,等值,，所以A、D的,真值表,应该,完全相同,，故AD。,最基本,的方法。,求证,(pq)r,(pr)(qr),(pq)r,(pq)r,条件式的等值式，转换为熟悉,(pq)r,利用德摩律,r(pq),交换律,(rp)(rq),分配律,(p r)(qr),交换律,(pr)(qr),条件式等值式,等值演算的基本套路,(,板,),(1)转换,：A,BAB,(2)恰当转换,：A,B(AB)(AB),(AB)(AB),确保公式只保留,联结词,(3)否定到底：,A,(A,B),(A,B),(4)恰当使用分配律、吸收律、其他律。,利用等值演算，判断公式的类型,(pq)p)q,解：,(pq)p)q,(,(pq),p)q (,条件式的等值式,),(,(pq),p)q (,条件式的等值式,),(,(pq),p)q (,德摩律,),(pq)p)q (,德摩律,),(pq)(pq)(,结合律,),(pq)(pq)(,逆用德摩律,),AA (,A=(pq),1,称为,永真式,或,重言式,，,即利用等值演算，可以判断公式的类型。,利用等值演算判断公式类型,：,(p(pq)r,解：,(p(pq)r,(p(pq)r (,条件式的等值式,),(pp)q)r (,结合律,),(1q)r (,析取的性质即析取定义真值表,),1r (,析取的性质即析取定义真值表,),0r (,否定的定义,),0 (,析取的性质即析取定义真值表,),永假式,或,矛盾式,。,问题,：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？,1.4 主析取范式与主合取范式,小项,：在含有n个变元的,简单合取式“,”,中,每个,命题变元(原变量)或其否定(反变量),仅出现,一次,且各变元按其字母顺序出现,则该简单合取式为(,极)小项,。,如：pqr,pqr,pqr,pqr,(板),(p r),(qr),非小项,大项,：在含有n个变元的,简单析取式“,”,中,每个,命题变元(原变量)或其否定(反变量),仅出现,一次,且各变元按其字母顺序出现,则该简单析取式为(,极)大项,。,如：pqr,pqr,pqr,pqr,(板),(pr),(qr),非大项,1.4 析取范式与合取范式,主析取范式,：一个析取范式(,整体局部,)中，若所有,简单合取式,均为(,极)小项，,则,为主析取范式,(pq)r,(以右边板书为例),(p,q,r)(p,q,r)(,p,qr)(pqr),是主析取范式,1.4 析取范式与合取范式,主合取范式,：一个,合取,范式(,总体,局部,)中，如果所有,简单析取式,均为(,极)大项，,则为主合取范式.,(pq)r,(以右边板书为例),(p,q,r)(p,q,r)(,p,qr)(,p,qr),是,主合,取范式,如何得到一个公式的析取范式，合取范式,？,1.4 析取范式与合取范式,3变元,各小项,真值表,0,-,反,变量,1,-,原,变量,1、,3个变元,的小项共有8个，它们,各不相,同。,2、,每一行,：命题变元的,每组值,中，只有,一个,小项为1。,3、,每一列,：每小项仅有,一个组值,为1，其余7组均为0。,小项与变元的取值组即指派一一对应,!,4.小项,值为1,时各,变元,的值为,小项,的,编号。,如,pqr=1,p=0,q=0,r=0,，故编号,000,。,小项规则,：,原变量,-,1,反变量,0,反之由,编号,可写出,小项,小项规则,：,原变量,-,1,反变量,-,0,。,(板),(5)根据,小项的编号,，可写出,小项的表达式,。,如小项,m,101,的表达式为pqr。,如,m,00,为pq、,m,01,为pq、,m,10,为pq、,m,11,为pq。,很重要！!,(1),三个变元,的大项共有,8,个。,(2),每一行,:只有一个大项的值为0。,(3),每一列,:每个大项仅在,一个指派,即,一组值,为0。,(4)大项值为0时各,变元,的值为,大项,的,编号。,如pqr=0p=0,q=0,r=0 p=1,q=1,r=1，其编号为,111,。,大项规则,：,原变量,0,反变量,1,。,大项规则,：,原变量,0,反变量,1,(板),如,M,101,其表达式为pqr。,如,M,00,表达式为 pq,M,01,为pq,M,10,表达式为pq,M,11,为pq。,1.4 基于真值表求主析取范式、主合取范式,1、先建立,真值表,，,2、,成真赋值,对应的,小项,之,析取,，为,主析取,范式,3、,成假赋值,对应的,大项,之,合取,，为,主合取,范式,如用真值表求,主范式,:,(pq)r,pq,pq,(pq)q,p(pq),双条件,:当,p与,q值,相同,时,pq,为1,不同为0。称p当且仅当q,例题：,析取范式,=,值1,对应的,小项,的析取,m,00,m,11,=,(pq),(pq),合析范式,=,值0,对应的,大项,的合取,M,01,M,10,=(p q)(,pq),(pq)r的,主析,取范式、,主合,取范式,主析取,范式,公式值为1的指派对应,小项,的,析取,m,001,m,011,m,100,m,111,小项规则：原变量-1 反变量-0,(pqr)(pqr)(pqr)(pqr),(pq)r的,主析,取范式、,主合,取范式,主合取式,范式,大项规则,：,原变量-0 反变量-1,公式值为,0,的指派对应,大项,的合取,两类范式编号互补,M,000,M,010,M,101,M,110,(pqr)(pqr)(pqr)(pqr),(pq)r、,主析取,m,001,m,011,m,100,m,111,、,主合取,M,000,M,010,M,101,M,110,，,互相等值。有如下定理,：,(1),不是,永假,的命题公式，有等值的,主析取范式,。,(2),不是,永真,的命题公式，有等值的,主合取范式,。,因,永假,没有取值为1的解释，故无,相应小,项，故没有主析取范式。永真,没有取值,为0的解释,故没有,主合取范式,.,定理:不是永假公式,存在与之等值的主析取范式,由前述构造方法可知存在主析取范式。,设原式为A,主析取范式为B=,小项,1,小项,2,.,A=1B=1,B=1A=1,A=0B=0,B=0A=0,，,则,AB,(1),当,A为1,时,B是A为1所对应小项的析取,因此B中有一个小项为1,故B为1,.,即,A=1B=1,当,B为1,时,至少有一个,小项为,而小项仅在,原公式为1时才为1,，故,A为1,.,即,B=1A=1,(2),当,A为0,时，由于构成B的小项,仅在A为1时为1,，故A为0时各小项均为0，而B是这些小项的析取，故,B为0,即,A=0B=0,B为0时，假设,A不为0即为1。,而A为1时所对应的小项必为1，,B是这些的小项析取,故B为1，与 前提,“,B为0,”,矛盾，故假设错。,故A只能为0，即,B=0A=0,(1),每一行,：命题变元的,每组值,中，只有,一个,小项为1,(板),(2),每一列,：每小项仅,1个组值,为1，其余7组均为0,(板),(3),小项,值为1,时各,变元,的值为,小项,的,编号。,(4),小项规则,：,原变量,-,1,反变量,0,(板),反之由,编号,可写出,小项,(1),每一行,:只有一个大项的值为0。,(板),(2),每一列,:每个大项仅在,一个指派,即,一组值,为0。,(板),(3)大项值为0时各,变元,的值为,大项,的,编号。,(4),大项规则,：,原变量,0,反变量,1,。,(板),1.4 析取范式与合取范式,用,真值表,构造时，变量多时行数过多，计算量大，,能否用前面介绍,等值演算,来实现呢？,1.4 析取范式(Norm)与合取范式(,板等值,),文字,：命题变项(变元)及其否定称为文字.,如:p,q,r,p,q,r,(板),简单析取式,:仅由有限个,文字,构成的析取式.,如:pq,pq,pq,p q,pqr,(板),简单合取式,:仅由有限个,文字,构成的合取式.,如:pq,pq,pq,pq,pqr,(板),定理,：简单,析取,式与简单,合取式,(1)一个,简单析取,式Ai是,重言,式,含有某个命题,变元,及其,否定式,，如Ai=,p,p,(2)一个,简单合取,式Ai是,矛盾式,含有某个,命题变元,及其,否定式,，如Ai=,p,p,1.4 析取范式与合取范式,析取范式,：由有限个,简单合取,式的,析取,构成的,命题公式,称为,析取范式,。,总体是,析取,式，每对括号内是,合取,式(,板,),A=(p,q)(p,r),合取范式,：由有限个,简单析取,式的,合取,构成的,命题公式,称为,合取范式,。,总体是,合取,式，每对括号内是,析,取式(,板,),A=(p,q)(p,r),1.4 析取范式与合取范式,总体是,析取,式，每对括号内是,合取,式,A=(p,q)(p,r),析取范式,总体是,合取,式，每对括号内是,析,取式,A=(p,q)(p,r),合取范式,定理,：,析取范,式与,合取范式,(1)一个,析取范式,A是矛盾式,每个,简单合取式是矛盾式。A=(p,q)(p,r),(2)一个,合取范式,A是重言式,每个,简单析取式是重言式。A=(p,q)(p,r),1.4 析取范式与合取范式,(先板,),(1)转换,：A,BAB,(2),恰当,转换,：A,B(AB)(AB),(AB)(AB),(3)否定到底(广义德摩),A,(A,B),(A,B),(4),适当,分配律：A,(BC),A,(BC,).,(5)1,A=A,0,A=A,经过第1步、第2步转换后，公式中只有、三种运算符。,经过第,3步,后，从括号外深入到变元前，与变元结合成文文字，文字之间只有,、,，这时比较简单了。,但对,新手,仍是有难度,1.4 析取范式与合取范式,求,(pq)r的析取范式、合取范式(,右边推导,),解：(1),求析取范式,。即,外层,是，内层是,，,转换模式为AB(AB)(AB),(pq)r,(pq)r)(pq)r)(,整体为析取,),(,pq,)r)(,pq,)r)(,ABAB,),(pq)r)(,(pq),r)(,德摩律,),(,(p r)(qr),)(pq)r)(,分配律,),(p r)(qr)(pq r)(,结合律,),1.4 析取范式与合取范式,(右边推导),解：(1),求合取范式,。所以转换模式为AB(AB)(AB),(pq)r,(pq)r)(pq)r)(,整体为合取,),(,pq,)r)(,pq,)r)(,条件等价式,),(,pq,)r)(pq)r)(德摩律),(,(pr)(qr),)(pq)r)(分配律),(pr)(qr)(pq r)(结合律),1.4 析取范式与合取范式,小项,：在含有n个变元的,简单合取式“,”,中,每个,命题变元(原变量)或其否定(反变量),仅出现,一次,且各变元按其字母顺序出现,则该简单合取式为(,极)小项,。,如：pqr,pqr,pqr,pqr,(板),(p r),(qr),非小项,大项,：在含有n个变元的,简单析取式“,”,中,每个,命题变元(原变量)或其否定(反变量),仅出现,一次,且各变元按其字母顺序出现,则该简单析取式为(,极)大项,。,如：pqr,pqr,pqr,pqr,(板),(pr),(qr),非大项,1.4 析取范式与合取范式,主析取范式,：一个析取范式(,整体局部,)中，若所有,简单合取式,均为(,极)小项，,则,为主析取范式,(pq)r,(以右边板书为例),(p r)(qr)(pq,r)不是,(p,q,r)(p,q,r)(,p,qr)(pqr),是主析取范式,1.4 析取范式与合取范式,主合取范式,：一个,合取,范式(,总体,局部,)中，如果所有,简单析取式,均为(,极)大项，,则为主合取范式.,(pq)r,(以右边板书为例),(pr)(qr)(pqr)不是,(p,q,r)(p,q,r)(,p,qr)(,p,qr),是,主合,取范式,1.4 析取范式与合取范式获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，可能还缺少某个变元，,因,pp1，1r r,故 r=(,pp,)r=(,p,r),(,p,r),可将缺少变元加入到,小项,中。,pr,缺q,p,1,r,析1,p(,qq,)r,合取,(,qq,),(pqr)(pqr)。,1.4 析取范式与合取范式获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，这时可能还缺少某个变元，因,pp1，1r r,故 r=(,pp,)r=(,p,r),(,p,r),可将缺少变元加入到,小项,中。,(pq)r,(pr)(qr)(pqr),(p(,qq,)r)(,pp,)qr)(pqr),不细讲,(pqr)(pqr)(pqr),(pqr),(pqr),(pqr)(pqr)(pqr)(pqr),1.4 析取范式与合取范式获取方法,因pp0,q0q,(,pp,),q,(,p,q,),(,p,q,),可将缺少的变元引入到,大项,中。,如,pr,缺q,p,0,r,析取0仍等值,p(,qq,)r,析取互反变元对合取,(pqr)(pqr),两边分配,1.4 析取范式与合取范式获取方法,因pp0,q0q,(,pp,),q,(,p,q,),(,p,q,),可将缺少的变元引入到,大项,中。,(pq)r,(pr)(qr)(pqr),(p(,qq,)r)(,pp,)qr)(pqr),(pqr)(pqr)(pqr)(pqr)(pqr),不细讲,(pqr)(pqr)(pqr)(pqr),设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为,“,通过,”,，则总成绩为,“,通过,”,。,对应的主析取范式值为1的指派对应的小项的析取,m,011,m,101,m,110,m,111,(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3),(,(x1x2x3)(x1x2x3),)(x1x2x3),(x1x2x3),(,(x1x2)(x1x2),)x3)(x1x2(x3x3),(x1x2)(x1x2)x3)(x1x2),(x1x2)(x1x2)x3)(x1x2)卡诺图与非或门表示,某公司要从曹、乔、宋、黎、邹5人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件：,(1)如果曹去，那么乔也去；,(2)黎、邹两人中必有一人去；,(3)乔、宋两人中去且仅去一人；,(4)宋、黎两人同去或同时不去；,(5)若邹去，则曹、乔也同去；,解：用小写字母表示：c:曹去，q：乔去 s：宋去 l：黎去 z：邹去时，以上5句话可表示为如下的公式：,(cq)、(lz)、(qs)(qs)、(sl)、(z(qc)，,5句话同时成立即每句话的值均为1，也即其合取式(cq)(lz)(qs)(qs)(sl)(z(qc)为1,(cq)(lz)(qs)(qs)(sl)(z(qc),(cq)(lz)(qs)(qs)(sl)(sl)(z(qc),(cq)(lz)(z(qc)(qssl)(qssl)(qssl)(qssl),(cq)(lz)(z(qc)(qsl)(qsl),(cq)(lz)(zqsl)(zqsl)(qcsl),(cq)(zqsl)(zqcsl),(czqsl)(zqcsl),因(cq)(lz)(qs)(qs)(sl)(z(qc)为1，故1(czqsl)(zqcsl)，,故1(czqsl)或1(zqcsl)故,方案一是：曹不去、邹不去、乔不去，宋与黎去。,方案二是：曹去、乔去、邹去，宋与黎均不去,在某班班委的选举中，该班的甲、乙、丙学生预言：,甲说：王娟为班长、刘强为生活委员；,乙说：金鑫为班长、王娟为生活委员；,丙说：刘强为班长、王娟为学习委员；,结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？,解,：p1,q1,r1:表示王娟，刘强，金鑫是,班长,；,p2,q2,r2:分别表示王娟，刘强，金鑫是,学习,委员；,p3,q3,r3:分别表示王娟，刘强，金鑫是,生活,委员；,“每个人说法对一半”将是一个非常复杂的公式(,p1q3,r1p3,q1p2,)(p1q3r1p3,q1p2,)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)，要构造这9个变元的真值表，将需要2,9,=512行，工作量实在太大了，！,参考,“,真值表,”,，设计如下的判断表,3、黄、李、肖预测德国A、乌拉圭B、西班牙C、荷兰D的名次，黄说“德国冠军，乌拉圭亚军”，李说“荷兰亚军，西班牙第4名”，肖说“德国亚军，乌拉圭第四名”，结果三人预测的结果都只对了一个，请问最后的名次是什么。,4、某公司要从A、B、C、D、E选派一些人去参观 世博会，必须满足如下条件：,(1)若A去则B肯定不能去；,(2)若A与C只能去一个；,(3)C与D两人同去或同不去；,(4)若B去则C肯定去,(5)若E去则B，C，D肯定有一人陪同。,证明：是否存在满足以上条件的人选？若存在则请给出全部方案。,5、赵、钱、孙、李4个参加ACM程序大赛后，有同学问他们，谁的成绩最好，赵说“不是我”，钱说“是李”，孙说“是钱”，李说“不是我”，4个人的回答只有一个人的说法符合实际情况，请问谁的成绩最好！已知只有一个第一名，即没有并列第一名。要求：用Z表示“赵第一”，Q表示“钱第一”，用S表示“孙第一”，L表示“李第一”，描述解题思想，并给出详细的解题过程。,6、二、三人估计比赛结果，A说“甲第一、丙第二”，B说“甲第二，丙第三”，C说“甲第二，乙第三”。结果三人估计都只对了一半，请问是否有解，若有解，请给出所有解？,7、赵国、钱多、孙少3个人拟加盟天马、岳麓、凤凰三支球队，记者事先预测。王记者说“孙少去天马，赵国去凤凰”，杨记者说“钱多去岳麓，赵国去天马”，刘记者说“钱多去凤凰，孙少去岳麓”！，最后的结果表明：每位记者的话错了一半，现以TZ、TQ、TS表示“赵国去了天马”、“钱多去了天马”、“孙少去了天马”，YZ、YQ、YS表示“赵国去了岳麓”、“钱多去了岳麓”、“孙少去了麓”，FZ、FQ、FS表示“赵国去了凤凰”、“钱多去了凤凰”、“孙少去了凤凰”，请在此基础上写出详细解题过程。,8、A、B、C、D同学有关假期旅游的谈话内容为：A说“如果B去、那我也去”，B说“C与D去，那我去”，C说“A与B不可能同时去”。D说“如果A、B、C有一人去了，我铁定去”，请给出满足这些要求所有结果。,9、高吉、王清、柯立拟转会到天马、岳麓、凤凰三支球队，记者事先预测。A记者说“柯立去天马，高吉去凤凰”，B记者说“王清去岳麓，高吉去天马”，C记者说“柯立去凤凰，王清去岳麓”！，最后的结果表明：每位记者的话都错了，现以TG、TW、TK表示“高吉去天马”、“王清去天马”、“柯立去天马”，YG、YW、YK表示“高吉去岳麓”、“王清去岳麓”、“柯立去麓”，FG、FW、FK表示“高吉去凤凰”、“王清去凤凰”、“柯立去凤凰”，请问此题有解吗？请给出详细的有解答过程。,10、某次考试以后，某班ABCD四位同学特别关心是否及格。每位同学依次作了如下猜测。A说：如果A及格了，则B没及格。B说：如果C及格，B肯定及格。C说：C与D都及格了。D说：如果A与B都及格，则D肯定及格了。最后结果这四句都对了。现用A表示A及格，B表示B及格了，C表示C及格了，D表示D及格了，据此将每人说的话分别表示命题公式，利用这些4个命题公式表示“四句都对了”，然后写出该命令公式的真值表，给出其各个小项，从而给出其析取范式，最终判断该问题是否有解，若有解请给出所有可能的解。,1.6 推理理论,从,已知条件,、,假设,、,前提,或,公理,出发，根据推理规则,推出,结论、定理的过程，称为,推理,。,前提:如果老天下雨,那么我带伞,今天老天下雨,结论:今天我带伞,前提:如果老天下雨,那么我带伞,今天没带伞,结论:老天没下雨,以上推理,当,前提,成立(为1),结论,总成立(为1),因此“,推理,”是指,前提,成立时,判断,结论,是否成立,用符号表示为：,(pq)pq,(pq)qp,当前提(pq)p成立(,为1,)时，结论q成立(,为1),而,不是,假(,0,)，即,10,的情形,不会出现,因此,(pq)pq,(pq)qp 为,永真式,1.6 推理理论,从,已知条件,、,假设,、,前提,或,公理,出发，根据推理规则,推出,结论、定理的过程，称为,推理,