华工离散数学命题逻辑课件

离散数学及其应用,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,离散,数学及其应用,华南理工大学,计算机科学与工程学院,1,离散数学,研究离散对象及其相互间关系的一门数学学科。,它是以研究离散量的结构和相互间的关系为主要目标，描述了计算机科学离散性的特点,.,从数学的角度出发：连续数学和离散数学，都是刻画和分析现实世界的重要工具。,基础数学的延伸,算法与数据结构的理论基础,概率统计、算法设计与分析的理论基础,其他专业课程的描述和建模工具,2,为什么要学习离散数学？,离散数学是现代数学的一个重要分支，是计算机专业的一门重要的专业基础课程。,是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智 能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是遗传算法、数据挖掘、模式识别、密码学、网络通信理论等课程的重要基础。,该课程所提供的训练十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于严谨、完整、规范的科学态度的培养。,3,2024/9/12 23:30,Chen Qiong,South China Univ.of Tech.,3,计算机科学与离散数学的关系,计算机科学的任务是用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。,为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。,离散数学就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言和逻辑语言等）从最简单的对象（集合）出发表示通用模型。,4,计算机科学与离散数学的关系,离散数学的思维方法能够为计算机科学所用,计算机科学知识的掌握需要三方面的能力,-,构造模型、算法设计、程序设计的能力,思维训练：构造性思维,5,离散数学课程教学目标,知识获取能力：建立良好的知识结构，为学习其他课程打下基础,基本应用能力：掌握离散数学的语言，能对实际问题给出清晰的描述（建模）,工程实践能力：掌握离散数学的分析方法，针对实际问题设计解决方案并加以实施,研究能力：培养思维严谨性，提升抽象思考和严格推理能力,培养创新意识：了解现代数学思想和学科进展，,6,2024/9/12 23:30,Chen Qiong,South China Univ.of Tech.,6,6,离散数学的应用,在计算机科学方面的应用,是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智 能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是遗传算法、数 据挖掘、模式识别、密码学、网络通信理论、等课程的重要基础。,在通信方面的应用,代数系统在开关线路的计数，数字通信的纠错码方面的应用,在现实生活中的应用,TSP,在企业管理、交通规划、战争指挥、金 融分析，生物、医药等领域都有重要的应用。,7,2024/9/12 23:30,Chen Qiong,South China Univ.of Tech.,7,7,离散数学的一些应用,关系数据库,四色定理,网络规划,信息安全,计算复杂性问题：该问题可计算吗？该问题能,/,不能计算？计算机复杂性如何？,操作系统中，如何调度进程使得系统效率最优？,程序结构度量：判断程序结构是否相似,提高信息传输效率的通信编码的设计,通信网络频率分配,设计集成电路线路的布局，达到最优效率,数字通信的可靠性：如何设计高效的检错码和纠错码？,8,离散数学的一些应用,中国邮递员问题,学生考试日程表的安排,人携带狼、羊和草渡河的问题,物流运输的最优路径的计算,达到最高效率的工作流程的安排,生产调度和人员安排,酒店的清洁工的工序安排,库房和运输管理,航班调度，交通规划,考生录取,9,学习内容,数理逻辑,集合，函数和关系,图论,数理逻辑是研究推理的学科，在人工智能、程序理论和数据库理论等的 研究中有重要的应用。集合论和图论为数据结构和算法分析奠定了数学基础， 也为许多问题从算法角度如何加以解决提供了进行抽象描述的一些重要方法。,10,结束,下一页,关于课程学习,课程特点,知识点集中、概念定理多,方法性强,-,阅读、思考、练习、阅读、总结,.,课程考核,过程考核、在线测试、期末考试,11,参考资料,教材：陈琼等编著：离散数学及其应用，机械工业出版社,Kenneth H.Rosen, Discrete Mathematics and Applications,机械工业出版社,耿素云、屈婉玲著：离散数学，高教出版社,傅彦、顾小丰著：离散数学及其应用，电子工业出版社,B Kolman,Robert C. Busby, Sharon Ross, Discrete Mathematics Structures,高等教育出版社,12,第一部分 数理逻辑,数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性等。,数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算、集合论、模型论、递归论和证明论。,数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。,13,第,1,章 命题逻辑,1,.1 命题,与联结词,1,.2 命题公式及其分类,1,.3,命题演算的关系式,1,.,4,范式,1,.,5,命题演算的推理,14,1,.1 命题与联接词,1,.,1,.,1,命题的概念,定义,命题的真值,联结词,15,命题及其真值,命题,:是用陈述句表示的一个或者为真或者为假，但不能同时既为真又为假的判断语句。,命题的真值,: 判断的结果,真（,T,或,1,）或假（,F,或,0),真命题,: 真值为真的命题,假命题,: 真值为假的命题,16,例题,判断下列句子中那些是命题？,若是命题的，判断其真值。,北京是中国的首都。,2+3=6,。,3-x=5,。,请关上门。,几点了？,除地球外的星球有生物。,多漂亮的花啊！,我只给所有不给自己理发的人理发,。,17,Y,真,Y,假,N,真值不确定,N,疑问句,N,感叹句,N,祈使句,N,悖论,Y,真值确定, 但未知,命题的表示,引入英文字母表示任意的命题,表示命题的符号称为,命题变量,，通常用,p,、,q,、,r.,、,P,、,Q,、,R.,表示命题变量。,命题变量没有真值，只有表示一个确定的命题后，才有真值。,如用,p,表示命题：“,2+3=6,”，这时,p,的真值为,假（,F,）,，,也可以用,p,表示命题：“,2+3=5,”,这时,p,的真值为真,（,T,）,。,18,简单命题与复合命题,简单命题(原子命题),:不能分解为更简单的陈述语句的命题,简单命题：“北京是中国的首都”。,复合命题,:,由,两,个或几个简单句和连词组合而成,的命题,复合命题：“如果明天天气好, 我们就去爬山。”,命题的符号化,：用英文字母或英文字母和联结词的组合表示命题,，,称为命题的符号化。,联结词,-,连词,19,联结词,（一）否定,定义,1.1.4,设,p,是一个命题，,p,表示一个新命题“非,p,”。命题,p,称为,p,的否定。当且仅当,p,的真值为假时，,p,的真值为真。,p,的真值表,：,例如：,p,：今天是晴天。则,p,：今天不是晴天。,“非”，“不”，“没有”，“无”，“并非”等都可用,来表示。,20,p,p,T,F,F,T,联结词,（二）合取,定义,1.1.5,设,p,、,q,表示任意两个命题, p,q,可表示复合命题“,p,并且,q,”。当且仅当,p,和,q,的真值同时为真时，,p,q,的真值为真。,p,q,的真值表,：,例如：,p:,今天是晴天；,q:,今天去公园。,p,q:,今天是晴天并且今天去公园。,“和”，,“,与,”,，,“也”，“并且”，“既,.,又,.,”，,“,不仅,.,而且,.”,，,“,虽然,.,但是,.”,等都可用,来表示。,21,p,q,p,q,T,T,T,F,F,T,F,F,T,F,F,F,联结词,（三）析取,定义,1.1.6,设,p,、,q,表示任意两个命题, p,q,可表示复合命题“,p,或,q,”。当且仅当,p,和,q,的真值同时为,假,时，,p,q,的真值为,假,。,p,q,的真值表,：,例如：,p:,今天,去看电影,；,q:,今天去,公,园。,p,q:,今天,去看电影或,今天去公园。,“或”，“可能,.,可能,.,”，“或者,.,或者,.,”等,可用,表示。,22,p,q,p,q,T,T,T,F,F,T,F,F,T,T,T,F,联结词,自然语言中的“或”具有二义性,：,兼容性或,和,不兼容性或。,兼容性或,电灯不亮是灯泡或线路有问题所致,.,不兼容性或,（排斥或）,派小王或小李中的一人去开会,表示兼容性或,例如：,p:,电灯不亮是灯泡有问题所致,；,q:,电灯不亮是线路有问题所致,。,p,q :,电灯不亮是灯泡或线路有问题所致,。,p,：,派小王去开会,，,q,：,派小李去开会,，,(p,q),(,p,q):,派小王或小李中的一人去开会,23,联结词,（四）,蕴涵,定义,1.1.7,设,p,、,q,表示任意两个命题, p,q,可表示复合命题“,如果,p,，则,q,”。当且仅当,p,的真值为真，,q,的真值为假时，,p,q,的真值为假。,p,q,的真值表,：,例如：,p:,今天天气晴朗；,q:,我们去海滩。,p,q:,如果,今天天气晴朗,，,我们,就,去海滩。,24,p,q,p,q,T,T,T,F,F,T,F,F,T,F,T,T,联结词,蕴涵式,：,p,q,p,为蕴涵前件，,q,为蕴涵后件,p,是,q,的充分条件，,q,是,p,的必要条件,表示：,“如果,p,，则,q,”，“如果,p,，那么,q,”，“当,p,则,q,”，“,p,仅当,q,”等,。,假设：,p,：天气晴朗；,q,：我们去海滩。,如果天气晴朗，我们去海滩,。,p,q,仅当天气晴朗，我们去海滩。,q,p,25,联结词,（五）等价,定义,1.1.8,设,p,、,q,表示任意两个命题, p,q,可表示复合命题“,p,当且仅当,q,”。当且仅当,p,和,q,的真值同时为真或同时为假时，,p,q,的真值为真。,p,q,的真值表,：,例如：,p:,两个三角形是全等的。,q,：两个三角形的三条对应边相等。,p,q,表示“两个三角形是全等的当且仅当它们的三条对应边相等”。,26,p,q,p,q,T,T,T,F,F,T,F,F,T,F,F,T,联结词,等值式,p,q,表示,p,与,q,互为充分必要条件的逻辑关系,表示形如“,p,当且仅当,q,”，“如果,p,，那么,q,，反之亦然”等的命题。,27,例题,将下列命题符号化：,虽然天气很冷，老王还是来了。,小王和小李是好朋友。,小王和小李是好学生。,小王或小李中的一人是游泳冠军。,只有你学过微积分或是数学系的学生，才可以选修这门课。,如果明天早晨,6,点不下雨，我就去跑步。,今天下雨与,3+3=6,。,登陆服务器必须输入一个有效的口令。,2+3=5,的充要条件是加拿大位于亚洲。,28,解,：,虽然天气很冷，老王还是来了。,设,p,：天气很冷。,q,：老王来了。,则符号化为,：,p,q,。,小王和小李是好朋友。,这句虽然有连词“和”，但是个简单句，,可用,p,表示：小王和小李是好朋友。,小王和小李是好学生。,设,p,：,“,小王是好学生,”,q,：,“,小李是好学生,”，,则符号化为,：,p,q,。,29,解,：,小王或小李中的一人是游泳冠军。,设,p,：,“,小王是游泳冠军,”，,q,：,“,小李是游泳冠军,”,(,p,q,),(,p,q,),只有你学过微积分或是数学系的学生，才可以选修这门课。,设,p,：,你学过微积分,；,q,：,你是数学系的学生,；,r,：,你可以选修这门课。,r,(,p,q,),如果明天早晨,6,点不下雨，我就去跑步。,设,p,：,明天早晨,6,点下雨,。,q,：,我去跑步,符号化为,：,p,q,或者,：,q,p,。,30,解,：,今天下雨与,3+3=6,。,设,p,：今天下雨。,q,：,3+3=6,。,符号化为,：,p,q,。,登陆服务器必须输入一个有效的口令。,设,p,：,登陆服务器,q,:,输入一个有效的口令,符号化为,：,p,q,。,2+3=5,的充要条件是加拿大位于亚洲。,设,p,：,2+3=5,q,:,加拿大位于亚洲,符号化为,p,q,。,31,联结词,（），,，,，,，,，,优先级 高 低,32,括号有时被省略，如,pq,是,p,和,q,的合取，这里是省略了,p,的括号，即,(p)q,p q,p p,q p,q p,q p,q,0 0 1 0 0,1,1,0 1 1 0 1,1,0,1 0 0 0 1,0,0,1 1 0 1 1,1,1,联结词的真值表,例题,将下列命题符号化，并指出它们的真值：,1+1=2,和,2+3=6,1+1=2,或猴子是飞禽,若,2+3=6,，则猴子是飞禽。,若猴子不是飞禽，则,1+1=2,和,2+3=6,。,若,2+3=6,或猴子是飞禽，则,1+1=2,。,2+3=6,当且仅当猴子不是飞禽。,33,解,设,p,：,1+1=2,，,q,：,2+3=6,，,r,:,猴子是飞禽,1+1=2,和,2+3=6,p,q,，真值为,0,，,1+1=2,或猴子是飞禽,p,q,，真值为,1,，,若,2+3=6,，则猴子是飞禽,q,r,，真值为,1,若猴子不是飞禽，则,1+1=2,和,2+3=6,。,r,p,q,，真值为,0,，,34,例题,(,续）,例题（续）,若,2+3=6,或猴子是飞禽，则,1+1=2,q,r,p,，真值为,1,，,2+3=6,当且仅当猴子不是飞禽。,q,r,，真值为,0,35,其它联结词,定义,1,.,1.9,设,p,和,q,是任意两个命题, p,q,可表示复合命题,“p,和,q,的与非,”,称为与非联结词。命题,p,q,称为,p,和,q,的与非式。当且仅当,p,和,q,的真值同时为真时，,p,q,的真值为假,.,p,q,的真值表,36,p,q,p,q,T,T,T,F,F,T,F,F,F,T,T,T,其它联结词,定义,1,.,1.10,设,p,、,q,是任意两个命题, p,q,可表示复合命题,“p,和,q,的或非,”,称为或非联结词。命题,p,q,称为,p,和,q,的或非式。当且仅当,p,和,q,的真值同时为假时，,p,q,的真值为真,.,p,q,的真值表,37,p,q,p,q,T,T,T,F,F,T,F,F,F,F,F,T,其它联结词,定义,1,.,1.11,设,p,和,q,是任意两个命题, p,q,可表示复合命题,“p,、,q,之中恰有一个成立,”,称为异或（不兼容性或）联结词。命题,p,q,称为,p,和,q,的异或式。当且仅当,p,和,q,的真值恰有一个为真时，,p,q,的真值为真。,p,q,的真值表,38,p,q,p,q,T,T,T,F,F,T,F,F,F,T,T,F,联结词的真值,39,p q,p,q p,q p,q p,q,p,q,p,q,0 0,0,1,0,1,1 0,0 1,0,1,1,0,0,1,1 0 0,1,1,0,0,1,1 1,1,0,1,0,1 0,联结词的真值,逻辑关系的数字门电路实现,用数字电路中的“非门”实现，,联结词用“与门”实现，,联结词用“或门”实现,40,非门 与门 或门,逻辑门电路符号,命题公式的门电路实现,命题公式,G,(,p,q,),p,41,逻辑电路,联结词的应用,布尔检索中，联结词,AND,用于匹配同时包含两个检索项的记录，联结词,OR,用于匹配至少包含一个检索项的记录，而联结词,NOT,用于排除某个特定的检索项。,如：,把自然语言表示的命题翻译成由命题变量和逻辑联结词组成的表达式，进行判断和推理,42,例题,三个客人坐在餐馆，服务生问：“每个人都要咖啡吗？”，第一位客人回答：“我不知道。”接着第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每个人都要咖啡。”一会儿，服务生回来，将咖啡递给需要的客人。请问服务生是如何判断哪位客人需要咖啡的？,解,：根据三位客人的回答，服务生给第一位客人和第二为客人送来咖啡。,43,例题,设,p,、,q,、,r,分别表示第一、二、三位客人要咖啡,如果每个人都要咖啡，则,p,q,r,为真。,如果第一位客人不要咖啡，则,p,为假，根据第一个客人的回答“我不知道。”，服务生可以判断,p,为真；,根据第二个人的回答“我不知道。”可以判断,q,为真,；,第三位客人的回答： “不是每个人都要咖啡。”说明,r,为假,因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。,44,1.2,命题公式及其分类,命题常元,: 代表特定简单命题,命题变元,: 代表任意命题，取值,1(,真,),或,0(,假,),的变量,定义,1,.,2.1,命题公式（公式）的定义如下：,每一个命题常,元,或命题变,元,都是命题公式。,如果,A,是命题公式，则,(,A),是命题公式。,如果,A,和,B,都是命题公式，则,(A,B),，,(A,B),，,(A,B),，,(A,B),都是命题公式。,一个由命题常,元,或命题变,元,、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。,45,命题公式,一个含有命题变元的命题公式的真值是不确定的,.,只有当公式中的所有命题变元被指定代表特定的命题时，命题公式才成为命题，其真值才唯一确定。,例如，命题公式,p,q,若指定,p,为,“2,是素数,”,，,q,为,“3,是奇数,”,则,p,q,为真命题,若指定,p,为,“2,是素数,”,，,q,为,“3,是偶数,”,则,p,q,为假命题,46,公式的赋值,定义,1,.,2.2,若命题公式,A,含有的全部命题变,元,为,p,1,p,2, ,p,n,，给,p,1,p,2, ,p,n,指定一组真值，称为对,A,的,一个,解释,或,赋值,。使,A,的真值为真的赋值称为,成真赋值,，使,A,的真值为假的赋值称为,成假赋值,。,说明,通常赋值与命题变元之间按下标或字母顺序对应, 即当,A,的全部命题变元为,p,1, p,2, , p,n,时, 给,A,赋值,1,2,n,，是指,p,1,=,1,p,2,=,2,p,n,=,n,;,当,A,的全部命题变,元,为,p,q,r,时,给,A,赋值,1,2,3,是指,p,=,1,q,=,2,r,=,3, ,。,47,命题公式的真值表,例,给出公式的真值表,p,(,q,r,),(,p,q,),(,p,q,),(,p,q,),q,48,真值表,: 命题公式在所有可能的赋值下的取值的列表,含,n,个变项的公式有2,n,个赋值,例题(续),(,1) p,(q,r),49,p q r,r,q,r,p,(,q,r,),0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,1,1,1,0,0,1,0,例题(续),（,2,）,(,p,q,),(,p,q,),50,p q,p,q,p,q,(,p,q,),(,p,q,),0 0,0 1,1 0,1 1,1,1,0,1,0,1,1,1,1,1,1,1,例题(续),(,3),(,p,q),q,51,p q,p,p,q,(,p,q,),(,p,q,),q,0 0,0 1,1 0,1 1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,N,个命题变元的不同的真值表有,命题公式的分类,定义,1.2.3,设,A,为一个命题公式,(1),若,A,在它的各种赋值下取值均为真，则称,A,为,重言式,或,永真式,。,(2),若,A,在它的各种赋值下取值均为假，则称,A,为,矛盾式,或,永假式,。,(3),若至少存在一种赋值使,A,的真值为真，则称,A,为,可满足式,。,例如,(1,) p,(q,r),为非重言式的可满足式,（,2,）,(p,q),(,p,q),为重言式,(,3,),(,p,q),q,为矛盾式,52,命题公式的分类,这三类公式之间有下面的关系：,公式,A,永真，则,A,永假，反之亦然。,公式,A,是可满足的，当且仅当,A,不是永真式。,公式,A,不是可满足的，则一定是永假式。,公式,A,不是永假式，则一定是可满足的。,判断命题公式类型的方法：构造真值表,53,1.3,命题演算的关系式,等价关系式,定义,1.3.1,设,A,和,B,是两个命题,(,或命题公式,),，若,A,B,是永真式，命题,A,和,B,称为,逻辑等价,的，可记为,A,B,。,说明：,A,B,是永真式,，,表示命题公式,A,和,B,在所有的赋值下都有相同的真值，也就是说命题公式,A,和,B,有相同的真值表。,可以用真值表判定两个命题是否等价。,54,例题,证明：,p,q,和,p,q,等价。,证,列出真值表,55,所以有:,p,q,p,q,p,q,p,q,p,p,q,0 0,1,1,1,0 1,1,1,1,1 0,0,0,0,1 1,1,0,1,例题,证明,p,(,q,r,),和,(,p,q,),(,p,r,),逻辑等价,证,列出真值表,56,所以有：,p,(,q,r,),和,(,p,q,),(,p,r,),等价,p,q,r,p,(,q,r,),(,p,q,),(,p,r,),0 0 0,0,0,0 0 1,0,0,0 1 0,0,0,0 1 1,0,0,1 0 0,0,0,1 0 1,1,1,1 1 0,1,1,1 1 1,1,1,等价关系式,双重否定律,p,p,同一律,p,0,p, p,1,p,零元律,p,1,1, p,0,0,等,幂律,p,p,p, p,p,p,交换律,p,q,q,p, p,q,q,p,结合律 (,p,q),r,p,(q,r),(p,q),r,p,(q,r),德摩根律,(,p,q),p,q,(p,q),p,q,吸收律,p,(p,q),p, p,(p,q),p,57,基本等值式(续),分配律,p,(q,r),(p,q),(p,r),p,(q,r),(p,q),(p,r,),排中律,p,p,1,矛盾律,p,p,0,蕴涵等值式,p,q,p,q,等价等值式,p,q,(p,q),(q,p),假言易位,p,q,q,p,等价否定等值式,p,q,p,q,归谬论 (,p,q),(p,q),p,58,等价运算,置换规则,若公式,G,中的一部分,A,(,包含,G,中几个连续的符号,),是公式，称,A,为,G,的子公式；用与,A,逻辑等价的公式,B,置换,A,不改变公式,G,的真值。,利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其它一些等价关系式，这一过程称为,命题的等价运算,。利用命题的等价运算，可以,判断两个命题是否等价,判断命题公式的类型,命题公式的化简等。,59,例题,例,1.3.3,证明,p,q,q,p,解,p,q,p,q,蕴涵等价式,(,q,),p,交换律和双重否定式,q,p,蕴涵等价式,条件命题：,p,q,否命题,：,p,q,逆命题,：,q,p,逆否命题,：,q,p,条件命题和它的逆否命题等价,60,例题,例,1.3.4,利用命题的等价运算判断下列公式的类型。,（,1,）,p,(,p,q,),解,p,(,p,q,),p,(,p,q,),蕴涵等价式,p,(,p,q,),摩根律,(,p,p,),q,结合律,F,q,矛盾式,F,零元律,该式是永假式,61,例题,（,2,）,p,(p,q ),解,p,(p,q),p,(,p,q),蕴涵等价式,(p,p),(p,q),分配律,F,(p,q),零元律,p,q,同一律,该式是可满足式,62,例题,(3) (p,q),(,q,p),解,(p,q),(,q,p),(p,q),(q,p),摩根律,(p,q),(p,q),交换律,T,排中律,该式是永真式,63,例题,化简公式,(,p,q,),(,p,q,),解,(,p,q,),(,p,q,),p,(,q,q,),分配律,p,T,排中律,p,同一律,64,例题,对于图,1.3.1,所示的逻辑电路，可否用更简单的电路实现该逻辑关系？,65,解,：,F,(,p,q,),(,p,q,),(,p,q,),(,p,q,),q,p,q,全功能联结词集,定义,1,.,3.2,设,G,是一个联结词的集合，若任意一个命题公式都可用,G,中的联结词构成的公式来表示，则称,G,为,全功能联结词集,。如在,G,中去掉任何一个联结词，就不再具有这种特性，就称其为,最小全功能联结词集,。,、,、,，,、,，,、,，,、,，,和,都是全功能联结词集，而,、,，,、,，,、,，,和,都是最小全功能联结词集。,66,A,B, (,A,B,)(,B,A,),A,B,A,B,A,B, (,A,B,), (,A,B,),A,B, (,A,B,),A,B,(,A,),B,A,B,例题,证明：,是最小全功能联结词集,证 ：,p, (,p,p),p,p,p,q, (,p,q,) (,p,q), (,p,q),(,p,q),得证,是联结词完备集. 对于,可类似证明.,只用一个,或,就可以实现联结词,，,，,、,、,表示的逻辑关系。在数字电子技术中，只用与非门或,者,或非门组成的电路就可以实现任何逻辑运算。,67,与非门 或非门,例题,用只有一种与非门的逻辑电路实现,F,(,p,q,),(,p,q,),(,p,q,),。,解：,F,(,p,q,),(,p,q,),(,p,q,),p,q,(,p,q,),(,p,p,),q,68,对偶式,定义,1.3.3,在仅含有联结词,，,，,的公式,A,中，将其中的,换成,，,换成,，,T(,或,1),换成,F,(,或,0),，,F,(,或,0),换成,T(,或,1),，其它符号不变得到的公式称为,A,的,对偶式,，记为,A,*,。,p,q,和,p,q,，,p, ,q,和,p, ,q,，,p,(,q, ,r,),和,p,(,q, ,r,),，,p,q,和,p,q,都互为对偶式,69,对偶式,设,A,(,p,1,，,p,2,，,p,n,),和,A,*(,p,1,，,p,2,，,p,n,),互为对偶式，其中,p,1,，,p,2,，,p,n,是出现在,A,和,A,*,中的全部的命题变元，则,A,(,p,1,，,p,2,，,p,n,),A,*(,p,1,，,p,2,，,p,n,),A,(,p,1,，,p,2,，,p,n,),A,*(,p,1,，,p,2,，,p,n,),定理,1.3.1,设,A,和,B,为两个命题公式，,A,和,A,*,，,B,和,B,*,互为对偶式，若,A,B,，则,A,*,B,*,。,证明,因为,A,(,p,1,，,p,2,，,p,n,), ,A,*(,p,1,，,p,2,，,p,n,),，,B,(,p,1,，,p,2,，,p,n,), ,B,*(,p,1,，,p,2,，,p,n,),，若,A,(,p,1,，,p,2,，,p,n,),B,(,p,1,，,p,2,，,p,n,),，则,A,*(,p,1,，,p,2,，,p,n,), ,B,*(,p,1,，,p,2,，,p,n,),，即,A,*(,p,1,，,p,2,，,p,n,),B,*(,p,1,，,p,2,，,p,n,),，则,A,*(,p,1,，,p,2,，,p,n,),B,*(,p,1,，,p,2,，,p,n,),。,70,例题,求公式,A,p,(,p,(,q,q,),的对偶式。,解,公式,A,的对偶式,A,*,为：,A,*,p,(,p,(,q,q,),重言式,A,的对偶式,A,*,是矛盾式,71,1.4,范式,1.4,.1 析取范式与合取范式,1.4,.2 主析取范式与主合取范式,极小项与极大项,主析取范式与主合取范式,主范式的用途,72,析取范式与合取范式,定义,1.4.1,一个命题公式具有形式,A,1,A,2,.,.,A,n,(,n,1),，其中,A,1,，,A,2,，,.,，,A,n,都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。,如：,p,(,p,q,r,),(,p,q,),q,是析取范式。,定义,1.4.2,一个命题公式具有,A,1,A,2,.,.,A,n,(,n,1),，其中,A,1,，,A,2,，,.,，,A,n,都是由命题变元或其否定所组成的析取式，则称该命题公式为合取范式。,如：,(,p,q,r,),(,p,q,),q,是合取范式。,73,范式存在定理,定理,1.4.1,任何一个命题公式都存在着与之等值的析取范式与合取范式.,证,设,G,为任意一个公式，,将公式化成只含,、,、,3,个联结词的形式。,将否定联结词内移或消去。,利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。,通过上面,3,个步骤可以求出与,G,等价的析取范式和合取范式，任意一个命题公式都存在着与之等价的析取范式和合取范式。,以上亦是求析取范式和合取范式的步骤。,74,例题,求命题公式,(,p,(,p,q,),q,的析取范式和合取范式。,解,(,p,(,p,q,),q,(,p,(,p,q,),q,(,p, ,p,),(,p,q,),q,析取范式,(,p,q,),q,析取范式,q,析取范式,(,p,q,),q,合取范式,(,p,q,),(,p,q,),合取范式,q,合取范式,注意: 公式的析取范式与合取范式不惟一.,75,主析取范式与主合取范式,定义,1,.,4.3,含有,n,个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为,极小项,。,定义,1,.,4.4,含有,n,个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为,极大项,。,说明,:(1),由,n,个命题变元产生的不同的极大项和极小项的个数均为,2,n,个。,(2),每个极小项在它的,2,n,个赋值中只有一个成真赋值,(3),每个极大项在它的,2,n,个赋值中只有一个成假赋值,76,主析取范式与主合取范式(续),77,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,m,000,或,m,0,m,001,或,m,1,m,010,或,m,2,m,011,或,m,3,m,100,或,m,4,m,101,或,m,5,m,110,或,m,6,m,111,或,m,7,3,个,命题变元,的,极,小项,一般地，,n,个命题变元形成的极小项可表示为：,主析取范式与主合取范式(续),3,个命题变元,的,极,大,项,78,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,M,000,或,M,0,M,001,或,M,1,M,010,或,M,2,M,011,或,M,3,M,100,或,M,4,M,101,或,M,5,M,110,或,M,6,M,111,或,M,7,一般地，,n,个命题变元形成的,极,大,项,可表示为：,主析取范式与主合取范式,定义,1.4.5,如果含,n,个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式,为主析取范式,。,定理,1.4.2,任何命题公式的主析取范式都是存在的，并且是唯一的。,证明,给定命题公式,A,，,1.,求,A,的析取范式,A,；,2.,若,A,的某合取式,B,不是极小项，则补入没有出现的变元。例如，若,p,i,不在,B,中，则将,B,展成如下形式：,B,B,1,B,(p,i,p,i,),(B,p,i,),(B,p,i,),3.,消去重复出现的命题变项、矛盾式及重复出现的极小项。,按上述步骤求得的就是,A,的主析取范式。,唯一性证明（略）,79,例题,求命题公式,( p,(q,r),(p,q,r),的主析取范式。,解,( p,(q,r),(p,q,r),( p,(q,r),(p,q,r),(,p,(,q,r),(p,q,r),(,p,q),(,p,r),(p,q,r),析取范式,(,p,q),(r,r),(,p,r),(q,q),(p,q,r),(,p,q,r),(,p,q,r),(,p,r,q),(,p,r,q),(p,q,r),(,p,q,r),(,p,q,r),(,p,q,r),(p,q,r),m,0,m,1,m,2,m,7,(0,，,1,，,2,，,7),80,主析取范式,例题,试由,p,q,r,的真值表求它的主析取范式。,p,q,r,的真值表,解：,成真赋值为,001,，,011,，,101,，,110,，,111,p,q,r,(1,，,3,，,5,，,6,，,7),(,p,q,r,),(,p,q,r,),(,p,r,q,),(,p,r,q,),(,p,q,r,),一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值,81,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,1,0,1,0,1,1,1,主析取范式与主合取范式,定义,1.4.6,如果含,n,个命题变元的命题公式的合取范式的每个析取式全是极,大,项，则称该析取范式为,主,合,取范式,。,定理,1.4.3,任何命题公式的主,合,取范式都是存在的，并且是唯一的。,证明,给定命题公式,A,，,1.,求,A,的,合,取范式,A,；,2.,若,A,的某,析,取式,B,不是极,大,项，则补入没有出现的变元。例如，若,p,i,不在,B,中则将,B,展成如下形式：,B,B,1,B,(,pi,pi,),(,B,pi,),(,B,pi,),3.,消去重复出现的命题变项、重言式及重复出现的极大项。,按上述步骤求得的就是,A,的主,合,取范式。,唯一性证明（略）,82,例题,求命题公式,(,p,(,q,r,),(,p,q,r,),的主,合,取范式。,解,(,p,(,q,r,),(,p,q,r,),(,p,(,q,r,),(,p,q,r,),(,p,q,),(,p,r,),(,q,r,p,),合取范式,(,p,q,),(,r,r,),(,p,r,),(,q,q,),(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),主合取范式,M,3,M,4,M,5,M,6,(3,，,4,，,5,，,6),m,0,m,1,m,2,m,7,(0,，,1,，,2,，,7),83,主析取范式的用途,(1) 求公式的成真赋值和成假赋值,设公式,A,含,n,个命题变项,A,的主析取范式有,s,个极小项, 则,A,有,s,个成真赋值, 它们是极小项下标的二进制表示, 其余2,n,-s,个赋值都是成假赋值,例如,(,p,q),r,m,0,m,2,m,4,m,5,m,6,成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111,84,主析取范式的用途(续),(2) 判断公式的类型,设,A,含,n,个命题变项，则,A,为重言式当且仅当,A,的主析取范式含2,n,个极小项,A,为矛盾式当且仅当,A,的主析取范式不含任何极小项,记作0,A,为可满足式当且仅当,A,的主析取范式中至少含一个极小项,85,例题,判断公式,G,(p,q),(,q,p),是否重言式？,解,G,(p,q),(,q,p),(,p,q),(q,p),(p,q),q,p,m,10,(,m,01,m,11,),(,m,00,m,01,),m,2,m,1,m,3,m,0,m,1,(0,，,1,，,2,，,3),公式,G,(p,q),(,q,p),是重言式,86,例题,一种简单的三人表决器，表决者每人座位旁有一个按钮，表决时，若表示同意则按按钮，若不同意不按按钮；表决结果超过半数时，喇叭发出声音。设计满足上述条件的表决器。,解,三个表决者的按钮分别为,p,，,q,，,r,，喇叭为,A,。,A,(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,),(,p,r,),(,q,r,),(,p,(,q,r,),(,q,r,),87,p,q,r,A,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,0,0,1,0,1,1,1,例题,某单位选派,A,、,B,、,C,三位业务骨干去进修，由于工作需要，选派要满足如下条件：,若,A,去，则,C,同去。,若,B,去，则,C,不能去。,若,C,不去，则,A,或,B,可以去。,问可以有哪些选派方案？,88,例题（续）,解,设,p,:,派,A,去，,q,:,派,B,去，,r,:,派,C,去。,89,有,3,个成真赋值，所以有,3,种选派方案：,A,和,B,不去，,C,去；,A,和,C,不去，,B,去；,A,和,C,去，,B,不去。,该公式的成真赋值就是可行的选派方案。写出该公式的主析取范式：,由已知条件可得：,1.5,命题演算的推理,1.5.1,推理理论,1.5.2,推理证明方法,90,推理理论,定义,1.5.1,设,A,和,B,是两个命题公式，当且仅当命题,A,B,是重言式时,(,即,A,B,T,时,),，称从,A,可推出,B,，或,A,蕴涵,B,，或,B,是前提,A,的结论，可以表示成,A,B,。,一般地，推理的前提可以有多个，若,(,A,1,A,2,A,n,),B,是重言式，则称由前提,A,1,，,A,2,，,，,A,n,可推出结论,B,，可表示为,(,A,1,A,2,A,n,),B,。,91,例题,判断下列推理是否正确：,p,(,p,q,),q,(,p,q,),q,p,解,写出,p,(,p,q,),q,和,(,p,q,),q,p,的真值表。,p,(,p,q,),q,正确,(,p,q,),q,p,不,正确,92,p,q,p,(,p,q,),q,(,p,q,),q,p,0 0,1,1,0 1,1,0,1 0,1,1,1 1,1,1,例题,证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草。”是正确的推理。,证明,设：,p,：牛吃草；,q,：马会飞。,前提符号化为：,p,q,，,q,，结论符号化为：,p,。,而,(p,q),q,p,(p,q),q),p,(p,q),q,p,(p,q),(p,q),T,所以，,p,是,p,q,和,q,的,有效,结论，,这个推理是正确的。,注意：推理时,，只要推理过程的每一步骤都遵循正确的推理规则，推出的结论都称为有效结论,，推理都是有效的。,93,推理定律,94,定理（,CP,规则,）,若,H,1,，,H,2,，,.,，,H,m,和,P,推出,Q,，则,H,1,，,H,2,，,.,，,H,m,推出,P,Q,。,证明,从定理的假设有：,H,1,H,2,.,H,m,P,Q,根据定义,1.5.1,，即有：,H,1,H,2,.,H,m,P,Q,T,令,H,1,H,2,.,H,m,H,，则,H,P,Q,(,H,P,),Q,H,P,Q,H,(,P,Q,),T,所以,H,P,Q,，即：,H,1,H,2,.,H,m,P,Q,95,推理证明方法,真值表法,等价演算法,演绎法,附加前提证明法,间接推演法,(,归谬法,),归结证明法,96,1,、,真值表法,通过写出真值表判断,A,