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

1、离散数学及其应用离散数学及其应用华南理工大学计算机科学与工程学院1离散数学及其应用离散数学研究离散对象及其相互间关系的一门数学学科。它是以研究离散量的结构和相互间的关系为主要目标，描述了计算机科学离散性的特点. 从数学的角度出发：连续数学和离散数学，都是刻画和分析现实世界的重要工具。基础数学的延伸算法与数据结构的理论基础概率统计、算法设计与分析的理论基础其他专业课程的描述和建模工具2离散数学及其应用为什么要学习离散数学？离散数学是现代数学的一个重要分支，是计算机专业的一门重要的专业基础课程。是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智 能、形式语言、编译原理等计算机本科阶

2、段核心课程的基础，也是遗传算法、数据挖掘、模式识别、密码学、网络通信理论等课程的重要基础。 该课程所提供的训练十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于严谨、完整、规范的科学态度的培养。32022年4月30日11时01分Chen Qiong,South China Univ.of Tech.3离散数学及其应用计算机科学与离散数学的关系计算机科学的任务是用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。离散数学就是指出构成一个包括了不同领域的通用模型的思

3、维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言和逻辑语言等）从最简单的对象（集合）出发表示通用模型。4离散数学及其应用计算机科学与离散数学的关系离散数学的思维方法能够为计算机科学所用计算机科学知识的掌握需要三方面的能力-构造模型、算法设计、程序设计的能力思维训练：构造性思维5离散数学及其应用离散数学课程教学目标知识获取能力：建立良好的知识结构，为学习其他课程打下基础基本应用能力：掌握离散数学的语言，能对实际问题给出清晰的描述（建模）工程实践能力：掌握离散数学的分析方法，针对实际问题设计解决方案并加以实施研究能力：培养思维严谨性，提升抽象思考和严格推理能力培养创新意识：了解现代数学思想

4、和学科进展，62022年4月30日11时01分Chen Qiong,South China Univ.of Tech.66离散数学及其应用离散数学的应用在计算机科学方面的应用 是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智 能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是遗传算法、数 据挖掘、模式识别、密码学、网络通信理论、等课程的重要基础。在通信方面的应用 代数系统在开关线路的计数，数字通信的纠错码方面的应用在现实生活中的应用 TSP 在企业管理、交通规划、战争指挥、金 融分析，生物、医药等领域都有重要的应用。 72022年4月30日11时01分Chen Qio

5、ng,South China Univ.of Tech.77离散数学及其应用离散数学的一些应用关系数据库四色定理网络规划信息安全计算复杂性问题：该问题可计算吗？该问题能/不能计算？计算机复杂性如何？操作系统中，如何调度进程使得系统效率最优？程序结构度量：判断程序结构是否相似提高信息传输效率的通信编码的设计通信网络频率分配设计集成电路线路的布局，达到最优效率数字通信的可靠性：如何设计高效的检错码和纠错码？8离散数学及其应用离散数学的一些应用中国邮递员问题学生考试日程表的安排人携带狼、羊和草渡河的问题物流运输的最优路径的计算达到最高效率的工作流程的安排生产调度和人员安排酒店的清洁工的工序安排库房和

6、运输管理航班调度，交通规划考生录取9离散数学及其应用学习内容数理逻辑集合，函数和关系图论 数理逻辑是研究推理的学科，在人工智能、程序理论和数据库理论等的 研究中有重要的应用。集合论和图论为数据结构和算法分析奠定了数学基础， 也为许多问题从算法角度如何加以解决提供了进行抽象描述的一些重要方法。10结束下一页离散数学及其应用关于课程学习课程特点知识点集中、概念定理多方法性强 -阅读、思考、练习、阅读、总结.课程考核过程考核、在线测试、期末考试11离散数学及其应用参考资料教材：陈琼等编著：离散数学及其应用，机械工业出版社Kenneth H.Rosen, Discrete Mathematics an

7、d Applications, 机械工业出版社耿素云、屈婉玲著：离散数学，高教出版社傅彦、顾小丰著：离散数学及其应用，电子工业出版社B Kolman,Robert C. Busby, Sharon Ross, Discrete Mathematics Structures, 高等教育出版社12离散数学及其应用第一部分 数理逻辑数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性等。数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算、集合论、模型论、递归论和证明论。数理逻辑是形式逻辑与数学相结合的产

8、物。但数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。 13离散数学及其应用第1章 命题逻辑1.1 命题与联结词 1.2 命题公式及其分类1.3 命题演算的关系式 1.4 范式1.5 命题演算的推理 14离散数学及其应用1.1 命题与联接词 1.1.1 命题的概念 定义 命题的真值 联结词15离散数学及其应用命题及其真值命题:是用陈述句表示的一个或者为真或者为假，但不能同时既为真又为假的判断语句。命题的真值: 判断的结果,真（T或1）或假（F或0)真命题: 真值为真的命题假命题: 真值为假的命题16离散数学及其应用例题判断下列句子中那些是命题？若是

9、命题的，判断其真值。 1.北京是中国的首都。2.2+3=6。3.3-x=5。4.请关上门。5.几点了？6.除地球外的星球有生物。7.多漂亮的花啊！8.我只给所有不给自己理发的人理发。17Y 真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离散数学及其应用简单命题与

10、复合命题简单命题(原子命题):不能分解为更简单的陈述语句的命题 简单命题：“北京是中国的首都”。 复合命题:由两个或几个简单句和连词组合而成的命题 复合命题：“如果明天天气好, 我们就去爬山。”命题的符号化：用英文字母或英文字母和联结词的组合表示命题，称为命题的符号化。 联结词 - 连词19离散数学及其应用联结词（一）否定 定义定义1.1.4 设p是一个命题，p表示一个新命题“非p”。命题p称为p的否定。当且仅当p的真值为假时，p的真值为真。 p的真值表：例如：p：今天是晴天。则 p：今天不是晴天。“非非”，“不不”，“没有没有”，“无无”，“并非并非”等都可用等都可用 来来表示。表示。 20

11、ppTFFT离散数学及其应用联结词（二）合取 定义定义1.1.5 设p、q表示任意两个命题, pq 可表示复合命题“p并且q”。当且仅当p和q的真值同时为真时，pq的真值为真。 pq的真值表：例如： p: 今天是晴天； q: 今天去公园。 pq: 今天是晴天并且今天去公园。 “和和”，“与与”，“也也”，“并且并且”，“既既 . .又又. .”，“不仅不仅. .而且而且.”.”，“虽然虽然. .但是但是.”.”等都可用等都可用 来表示。来表示。21p qpqT TT FF TF FT FFF离散数学及其应用联结词（三）析取 定义定义1.1.6 设p、q表示任意两个命题, p q 可表示复合命题

12、“p或q”。当且仅当p和q的真值同时为假时，p q的真值为假。 p q的真值表：例如： p: 今天去看电影； q: 今天去公园。 p q: 今天去看电影或今天去公园。 “或或”，“可能可能. .可能可能. .”，“或者或者. .或者或者. .”等等可用可用 表示。表示。22p qp qT TT FF TF FT TTF离散数学及其应用联结词自然语言中的“或”具有二义性：兼容性或和不兼容性或。兼容性或 电灯不亮是灯泡或线路有问题所致. 不兼容性或（排斥或） 派小王或小李中的一人去开会表示兼容性或例如：p: 电灯不亮是灯泡有问题所致； q: 电灯不亮是线路有问题所致。 p q :电灯不亮是灯泡或线

13、路有问题所致。 p：派小王去开会，q：派小李去开会， (p q)(p q): 派小王或小李中的一人去开会23离散数学及其应用联结词（四）蕴涵定义定义1.1.7 设p、q表示任意两个命题, p q 可表示复合命题“如果p，则q”。当且仅当p的真值为真，q的真值为假时，pq的真值为假。 p q的真值表：例如： p:今天天气晴朗； q:我们去海滩。 p q: 如果今天天气晴朗，我们就去海滩。24p qpqT TT FF TF FT FTT离散数学及其应用联结词蕴涵式：pqp为蕴涵前件，q为蕴涵后件p是q的充分条件，q是p的必要条件表示：“如果p，则q”，“如果p，那么q”，“当p则q”，“p仅当q”

14、等。假设：p：天气晴朗；q：我们去海滩。1.如果天气晴朗，我们去海滩。pq2.仅当天气晴朗，我们去海滩。 qp25离散数学及其应用联结词（五）等价定义定义1.1.8 设p、q表示任意两个命题, p q 可表示复合命题“p当且仅当q”。当且仅当p和q的真值同时为真或同时为假时，pq的真值为真。 p q的真值表：例如： p:两个三角形是全等的。q：两个三角形的三条对应边相等。 pq表示“两个三角形是全等的当且仅当它们的三条对应边相等”。26p qpqT TT FF TF FT FFT离散数学及其应用联结词等值式pq表示p与q互为充分必要条件的逻辑关系表示形如“p当且仅当q”，“如果p，那么q，反之

15、亦然”等的命题。27离散数学及其应用例题将下列命题符号化：虽然天气很冷，老王还是来了。小王和小李是好朋友。小王和小李是好学生。小王或小李中的一人是游泳冠军。只有你学过微积分或是数学系的学生，才可以选修这门课。如果明天早晨6点不下雨，我就去跑步。今天下雨与3+3=6。登陆服务器必须输入一个有效的口令。2+3=5的充要条件是加拿大位于亚洲。28离散数学及其应用 解解：虽然天气很冷，老王还是来了。 设p：天气很冷。q：老王来了。 则符号化为：pq。小王和小李是好朋友。 这句虽然有连词“和”，但是个简单句， 可用p表示：小王和小李是好朋友。小王和小李是好学生。 设p：“小王是好学生” q ：“小李是好

16、学生”， 则符号化为： pq。29离散数学及其应用 解解：小王或小李中的一人是游泳冠军。 设p：“小王是游泳冠军”，q：“小李是游泳冠军” (pq)( pq)只有你学过微积分或是数学系的学生，才可以选修这门课。 设 p：你学过微积分；q：你是数学系的学生；r：你可以选修这门课。 r(pq)如果明天早晨6点不下雨，我就去跑步。 设p：明天早晨6点下雨。q：我去跑步 符号化为： pq, 或者： q p。30离散数学及其应用 解解：今天下雨与3+3=6。设p：今天下雨。q：3+3=6。符号化为：pq。登陆服务器必须输入一个有效的口令。设p：登陆服务器,q: 输入一个有效的口令, 符号化为：pq。2+

17、3=5的充要条件是加拿大位于亚洲。设p：2+3=5,q: 加拿大位于亚洲, 符号化为pq。31离散数学及其应用联结词 （）， ， ，优先级 高 低 32括号有时被省略，如pq是p和q的合取，这里是省略了p的括号，即(p)q p q p pq pq pq pq 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=61+1=2或猴子是飞禽若2+3=6，则猴子是飞禽。若猴子不是飞禽，则1+1=2和2+3=6。若2+3=6或猴子是飞禽，则1+

18、1=2。2+3=6当且仅当猴子不是飞禽。33离散数学及其应用解解 设p：1+1=2，q：2+3=6，r: 猴子是飞禽 1+1=2和2+3=6, pq，真值为0， 1+1=2或猴子是飞禽, pq，真值为1， 若2+3=6，则猴子是飞禽, qr，真值为1若猴子不是飞禽，则1+1=2和2+3=6。 r pq，真值为0， 34例题(续）离散数学及其应用例题（续）若2+3=6或猴子是飞禽，则1+1=2 qrp，真值为1， 2+3=6当且仅当猴子不是飞禽。 qr，真值为035离散数学及其应用其它联结词定义定义1.1.9 设p和q是任意两个命题, p q可表示复合命题“p和q的与非”, 称为与非联结词。命题

19、p q 称为p和q的与非式。当且仅当p和q的真值同时为真时，p q的真值为假.p q的真值表36p qpqT TT FF TF FFTTT离散数学及其应用其它联结词定义定义1.1.10 设p、q是任意两个命题, p q可表示复合命题“p和q的或非”, 称为或非联结词。命题p q 称为p和q的或非式。当且仅当p和q的真值同时为假时，p q的真值为真. p q的真值表37p qpqT TT FF TF FFFFT离散数学及其应用其它联结词定义定义1.1.11 设p和q是任意两个命题, p q可表示复合命题“p、q之中恰有一个成立”, 称为异或（不兼容性或）联结词。命题p q 称为p和q的异或式。当

20、且仅当p和q的真值恰有一个为真时，p q的真值为真。 p q的真值表 38p qpqT TT FF TF FFTTF离散数学及其应用联结词的真值 39 p q pq p q pq p q pq 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 (pq)p41逻辑电路离散数学及其应用联结词的应用

21、布尔检索中，联结词AND用于匹配同时包含两个检索项的记录，联结词OR用于匹配至少包含一个检索项的记录，而联结词NOT用于排除某个特定的检索项。如：把自然语言表示的命题翻译成由命题变量和逻辑联结词组成的表达式，进行判断和推理42离散数学及其应用例题 三个客人坐在餐馆，服务生问：“每个人都要咖啡吗？”，第一位客人回答：“我不知道。”接着第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每个人都要咖啡。”一会儿，服务生回来，将咖啡递给需要的客人。请问服务生是如何判断哪位客人需要咖啡的？解解：根据三位客人的回答，服务生给第一位客人和第二为客人送来咖啡。43离散数学及其应用例题设p、q、r分别

22、表示第一、二、三位客人要咖啡如果每个人都要咖啡，则pqr为真。如果第一位客人不要咖啡，则p为假，根据第一个客人的回答“我不知道。”，服务生可以判断p为真；根据第二个人的回答“我不知道。”可以判断q为真 ；第三位客人的回答： “不是每个人都要咖啡。”说明r为假 因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。44离散数学及其应用1.2 命题公式及其分类命题常元: 代表特定简单命题 命题变元: 代表任意命题，取值1(真)或0(假)的变量定义定义1.2.1 命题公式（公式）的定义如下：1.每一个命题常元或命题变元都是命题公式。2.如果A是命题公式，则(A)是命题公式。3.如果A和B

23、都是命题公式，则(AB)，(AB)，(AB)，(AB)都是命题公式。4.一个由命题常元或命题变元、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。45离散数学及其应用命题公式一个含有命题变元的命题公式的真值是不确定的. 只有当公式中的所有命题变元被指定代表特定的命题时，命题公式才成为命题，其真值才唯一确定。 例如，命题公式p q 若指定 p为“2是素数”，q为“3是奇数” 则p q为真命题 若指定 p为“2是素数”，q为“3是偶数” 则p q为假命题 46离散数学及其应用公式的赋值定义定义1.2.2 若命题公式A含有的全部命题变元为p1, p2, , pn

24、，给p1, p2, , pn指定一组真值，称为对A的一个解释解释或赋值赋值。使A的真值为真的赋值称为成真赋值成真赋值，使A的真值为假的赋值称为成假赋值成假赋值。说明说明 通常赋值与命题变元之间按下标或字母顺序对应, 即当A的全部命题变元为p1, p2, , pn时, 给A赋值12n，是指p1=1,p2=2,pn=n;当A的全部命题变元为p,q,r,时, 给A赋值123是指p=1, q=2, r=3, 。47离散数学及其应用命题公式的真值表例例 给出公式的真值表(1) p(q r) (2) (pq)(pq) (3) ( pq)q48真值表: 命题公式在所有可能的赋值下的取值的列表含n个变项的公式

25、有2n个赋值离散数学及其应用例题(续)(1) p(qr)49 p q r r qr p(qr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 1010101 0 0010001 0 11110010离散数学及其应用例题(续)（2） (pq)(pq) 50 p q pq pq (pq) ( pq)0 00 11 01 1 1101 0111 1111离散数学及其应用例题(续)(3) (pq)q51 p q p pq ( pq) ( pq) q0 00 11 01 1 1100011110000000N个命题变元的不同的真值表有22n离散数学及其应用命题公式的分

26、类定义定义1.2.3 设A为一个命题公式(1)若A在它的各种赋值下取值均为真，则称A为重言式或永真式。(2)若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式。(3)若至少存在一种赋值使A的真值为真，则称A为可满足式。 例如 (1) p(qr) 为非重言式的可满足式 （2）(p q)( p q)为重言式 (3) (pq)q 为矛盾式52离散数学及其应用命题公式的分类这三类公式之间有下面的关系：公式A永真，则A永假，反之亦然。公式A是可满足的，当且仅当A不是永真式。公式A不是可满足的，则一定是永假式。公式A不是永假式，则一定是可满足的。判断命题公式类型的方法：构造真值表53离散数学及其应用1

27、.3 命题演算的关系式等价关系式定义定义1.3.1设A和B是两个命题(或命题公式)，若AB是永真式，命题A和B称为逻辑等价的，可记为AB。说明：AB是永真式，表示命题公式A和B在所有的赋值下都有相同的真值，也就是说命题公式A和B有相同的真值表。 可以用真值表判定两个命题是否等价。 54离散数学及其应用例题证明：p q和pq等价。证证 列出真值表55所以有所以有: p q pqp qpq p pq0 01110 11111 00001 1101离散数学及其应用例题证明p (qr )和(p q) (p r)逻辑等价证证 列出真值表56所以有： p(qr)和(p q)(pr)等价p q rp (qr

28、 )(p q) (p r)0 0 0000 0 1000 1 0000 1 1001 0 0001 0 1111 1 0111 1 111离散数学及其应用等价关系式双重否定律 pp同一律 p0p, p1p零元律 p11, p00 等幂律 ppp, ppp交换律 pqqp, pqqp结合律 (pq)rp(qr) (pq)rp(qr)德摩根律 (pq)pq (pq)pq 吸收律 p(pq)p, p(pq)p57离散数学及其应用基本等值式(续)分配律 p(qr)(pq)(pr) p(qr) (pq)(pr)排中律 pp1矛盾律 pp0蕴涵等值式 pqpq等价等值式 pq(pq)(qp)假言易位 pq

29、qp等价否定等值式 pqpq归谬论 (pq)(pq) p58离散数学及其应用等价运算置换规则置换规则 若公式G中的一部分A(包含G中几个连续的符号)是公式，称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。 利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其它一些等价关系式，这一过程称为命题的等价运算。利用命题的等价运算，可以判断两个命题是否等价判断命题公式的类型命题公式的化简等。59离散数学及其应用例题例1.3.3 证明pqqp解解 pq pq 蕴涵等价式 (q) p 交换律和双重否定式 qp 蕴涵等价式 条件命题： pq 否命题：pq 逆命题： qp 逆否命

30、题：qp 条件命题和它的逆否命题等价60离散数学及其应用例题例1.3.4 利用命题的等价运算判断下列公式的类型。（1）p(pq)解解 p(pq)p(pq) 蕴涵等价式 p(pq) 摩根律 (pp)q 结合律 Fq 矛盾式 F 零元律 该式是永假式61离散数学及其应用例题（2）p (p q ) 解 p(pq) p(pq) 蕴涵等价式 (pp) (pq) 分配律 F (pq) 零元律 pq 同一律 该式是可满足式62离散数学及其应用例题 (3) (pq) (qp) 解 (pq) (qp) (pq) (qp) 摩根律 (pq) (pq) 交换律 T 排中律 该式是永真式63离散数学及其应用例题化简公

31、式 (p q) (p q)解解 (pq)(pq)p(qq) 分配律 pT 排中律 p 同一律64离散数学及其应用例题对于图1.3.1所示的逻辑电路，可否用更简单的电路实现该逻辑关系？65解：F (pq)(pq)(pq)(pq)q pq离散数学及其应用全功能联结词集定义1.3.2 设G是一个联结词的集合，若任意一个命题公式都可用G中的联结词构成的公式来表示，则称G为全功能联结词全功能联结词集集。如在G中去掉任何一个联结词，就不再具有这种特性，就称其为最小全功能联结词集最小全功能联结词集。、，、，、，、，和都是全功能联结词集，而、，、，、，和都是最小全功能联结词集。66AB (AB) (BA)AB

32、 A BA B (A B) ( AB)A B ( AB)A B ( A) B AB离散数学及其应用例题证明：,是最小全功能联结词集证 ： p (pp) pp pq (pq) (pq) (pq)(pq)得证是联结词完备集. 对于可类似证明. 只用一个或就可以实现联结词，、表示的逻辑关系。在数字电子技术中，只用与非门或者或非门组成的电路就可以实现任何逻辑运算。67 与非门 或非门离散数学及其应用例题用只有一种与非门的逻辑电路实现F(pq)(pq)( pq)。解： F (pq)(pq)(pq) pq (pq) (pp) q68离散数学及其应用对偶式定义定义1.3.3 在仅含有联结词， ， 的公式A中

33、，将其中的换成 ， 换成 ，T(或1)换成F(或0)，F(或0)换成T(或1)，其它符号不变得到的公式称为A的对偶式，记为A*。p q 和p q ， p q和 p q，p (q r)和p (q r)， pq和pq 都互为对偶式69离散数学及其应用对偶式设A(p1，p2，pn) 和A*(p1，p2，pn)互为对偶式，其中p1，p2，pn是出现在A和A*中的全部的命题变元，则 A(p1，p2，pn) A*( p1，p2，pn) A( p1，p2，pn) A*(p1，p2，pn)定理1.3.1 设A和B为两个命题公式，A和A*，B和B*互为对偶式，若AB，则A*B*。证明证明 因为A(p1，p2，p

34、n) A*( p1，p2，pn)，B(p1，p2，pn) B*( p1，p2，pn)，若A(p1，p2，pn) B(p1，p2，pn)，则 A*( p1，p2，pn) B*( p1，p2，pn)，即A*(p1，p2，pn)B*( p1，p2，pn)，则A*(p1，p2，pn)B*(p1，p2，pn)。70离散数学及其应用例题求公式Ap (p (q q)的对偶式。解解 公式A的对偶式A*为：A* p(p(qq)重言式A的对偶式A*是矛盾式71离散数学及其应用1.4 范式1.4.1 析取范式与合取范式1.4.2 主析取范式与主合取范式 极小项与极大项 主析取范式与主合取范式 主范式的用途72离散数

35、学及其应用析取范式与合取范式定义定义1.4.1 一个命题公式具有形式A1 A2 . .An(n1)，其中A1，A2， .，An 都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。 如： p(pqr)(pq)q是析取范式。定义定义1.4.2 一个命题公式具有A1 A2 . .An(n1)，其中A1，A2， .，An都是由命题变元或其否定所组成的析取式，则称该命题公式为合取范式。 如： (pqr)(pq)q是合取范式。73离散数学及其应用范式存在定理定理定理1.4.1 任何一个命题公式都存在着与之等值的析取范式与合取范式.证证 设G为任意一个公式， 1.将公式化成只含、 3个联结词的

36、形式。2.将否定联结词内移或消去。3.利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。通过上面3个步骤可以求出与G等价的析取范式和合取范式，任意一个命题公式都存在着与之等价的析取范式和合取范式。 以上亦是求析取范式和合取范式的步骤。74离散数学及其应用例题求命题公式 (p (p q) q 的析取范式和合取范式。解解 (p (p q)q (p (pq)q (p p)(p q)q 析取范式 (p q) q 析取范式 q 析取范式 (pq) q 合取范式 (pq) (p q) 合取范式 q 合取范式 注意: 公式的析取范式与合取范式不惟一.75离散数学及其应用主析取范式与主合取范式定义定

37、义1.4.3 含有n个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为极小项。定义定义1.4.4 含有n个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为极大项。说明:(1)由n个命题变元产生的不同的极大项和极小项的个数均为2n个。(2)每个极小项在它的2n个赋值中只有一个成真赋值(3)每个极大项在它的2n个赋值中只有一个成假赋值 76离散数学及其应用主析取范式与主合取范式(续)77 p q r p q r p q r p q rp q rp q rp q rp q rm000 或 m0 m

38、001 或 m1m010 或 m2m011 或 m3m100 或 m4m101 或 m5m110 或 m6m111 或 m73个命题变元的极小项一般地，n个命题变元形成的极小项可表示为：1210, nmmm离散数学及其应用主析取范式与主合取范式(续)3个命题变元的极大项78p q rp q rp q rp q r p q r p q r p q r p q rM000 或 M0M001 或 M1M010 或 M2M011 或 M3M100 或 M4M101 或 M5M110 或 M6M111 或 M7一般地，n个命题变元形成的极大项可表示为：1210, nMMM离散数学及其应用主析取范式与主合

39、取范式定义定义1.4.5 如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为主析取范式。 定理定理1.4.2 任何命题公式的主析取范式都是存在的，并且是唯一的。证明 给定命题公式A， 1.求A的析取范式A； 2.若A的某合取式B不是极小项，则补入没有出现的变元。例如，若pi不在B中，则将B展成如下形式：B B1 B(pipi) (Bpi)(Bpi) 3.消去重复出现的命题变项、矛盾式及重复出现的极小项。 按上述步骤求得的就是A的主析取范式。 唯一性证明（略） 79离散数学及其应用例题求命题公式 ( p (q r) (p q r) 的主析取范式。 解 ( p (q r

40、) (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 qr)(p rq) ( p r q) (p q r) (p qr) (p q r) (p q r) (p q r) m0 m1 m2 m7 (0，1，2，7)80主析取范式离散数学及其应用例题试由pqr的真值表求它的主析取范式。 pqr的真值表 解：成真赋值为001，011，101，110，111pqr(1，3，5，6，7)(p q r) (p qr) (p rq) ( p

41、 r q) (p q r)一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值81p q rpqr0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 101010111离散数学及其应用主析取范式与主合取范式定义定义1.4.6 如果含n个命题变元的命题公式的合取范式的每个析取式全是极大项，则称该析取范式为 主合取范式。 定理定理1.4.3 任何命题公式的主合取范式都是存在的，并且是唯一的。证明 给定命题公式A， 1.求A的合取范式A； 2.若A的某析取式B不是极大项，则补入没有出现的变元。例如，若pi不在B中则将B展成如下形式： BB1 B (pi

42、 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 qr) (p q r) (p q r) 主合取范式 M3M4 M5 M6 (3，4，5，6) m0 m1 m2 m7 (0，1，2，7)83离散数学

43、及其应用主析取范式的用途(1) 求公式的成真赋值和成假赋值设公式A含n个命题变项, A的主析取范式有s个极小项, 则A有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s个赋值都是成假赋值 例如 (pq)r m0 m2 m4 m5 m6 成真赋值: 000,010,100,101,110; 成假赋值: 001,011,11184离散数学及其应用主析取范式的用途(续)(2) 判断公式的类型 设A含n个命题变项，则 A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当 A的主析取范式不含任何极小项,记作0 A为可满足式当且仅当A的主析取范式中至少含一个极小项85离散数学及其应

44、用例题判断公式G (pq)(q p)是否重言式？解 G (pq)(q p) (pq)(qp)(pq)qp m10(m01m11)(m00m01) m2 m1 m3 m0 m1 (0，1，2，3)公式G (pq)(qp)是重言式86离散数学及其应用例题 一种简单的三人表决器，表决者每人座位旁有一个按钮，表决时，若表示同意则按按钮，若不同意不按按钮；表决结果超过半数时，喇叭发出声音。设计满足上述条件的表决器。解解 三个表决者的按钮分别为p，q，r，喇叭为A。A (p q r) (p qr)(p q r) (p q r) (p q) (p r)(q r) (p(qr) (qr)87p q rA0 0

45、 00 0 10 1 00 1 11 0 01 0 11 1 01 1 100010111离散数学及其应用例题 某单位选派A、B、C三位业务骨干去进修，由于工作需要，选派要满足如下条件：若A去，则C同去。若B去，则C不能去。若C不去，则A或B可以去。问可以有哪些选派方案？88离散数学及其应用例题（续）解解 设p:派A去，q:派B去， r:派C去。89()()()prqrrpq ()()()()()()prqrrpqpqrpqrpqr 有3个成真赋值，所以有3种选派方案：1. A和B不去，C去；2. A和C不去，B去；3. A和C去，B不去。该公式的成真赋值就是可行的选派方案。写出该公式的主析取

46、范式：由已知条件可得：离散数学及其应用 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的结论，可以表示成AB。一般地，推理的前提可以有多个，若(A1 A2 An) B是重言式，则称由前提A1， A2， ， An可推出结论B，可表示为(A1 A2 An) B。91离散数学及其应用例题判断下列推理是否正确：1.p(pq) q2.(pq) q p解解 写出p(pq) q和(pq) q p的真值表。 p(pq) q 正确 (

47、pq) qp不正确 92p qp(pq) q(pq) q p0 0110 1101 0111 111离散数学及其应用例题证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草。”是正确的推理。证明证明 设：p：牛吃草；q：马会飞。前提符号化为：pq，q，结论符号化为：p。 而 (pq)qp (pq)q)p (pq) q p(pq)(pq) T所以，p是pq和q的有效结论，这个推理是正确的。注意：推理时，只要推理过程的每一步骤都遵循正确的推理规则，推出的结论都称为有效结论，推理都是有效的。93离散数学及其应用推理定律 941. 2. 3. , 4. , pqppqqppqqpqp pqqq pqp

48、化简附加假言推理 5. , 6. , 7. , 8. , 9. ,p pqqp qpqpq qrprpq qrprpq rs p拒取式析取三段论合取假言三段论等价三段论 , rqspqprqr 构造性二难10.归结式离散数学及其应用定理（CP规则）若H1，H2，.，Hm和P推出Q，则H1，H2，.，Hm推出P Q。证明证明 从定理的假设有：H1 H2 . Hm P Q 根据定义1.5.1，即有：H1 H2 . Hm P Q T令H1 H2 . Hm H，则 H P Q ( H P) Q H P Q H ( P Q) T所以H P Q，即：H1 H2 . Hm P Q95离散数学及其应用推理证明

49、方法1.真值表法2.等价演算法3.演绎法4.附加前提证明法5.间接推演法(归谬法)6.归结证明法96离散数学及其应用1、真值表法通过写出真值表判断AB的类型，若AB是重言式，则由前提A可以推出结论B。例 证明前提pq和pr，可以推出结论qr。证明证明 根据定义1.5.1，只需证明(pq) (pr) qr是重言式。列出真值表： 97离散数学及其应用 p q rpqprqr(pq) (pr)qr0 0 001010 0 101110 1 011110 1 111111 0 010011 0 111111 1 010111 1 1111198由真值表可知，(pq) (pr) qr是重言式，所以前提pq和pr，可以推出结论qr。离散数学及其应用2、等价演算法利用命题的等值演算判断AB的类型，若AB是重言式，则由前提A可以推出结论B。证明q是p和 pq的结论。证明证明 p (pq) q (p (pq) q p(pq) q pqq T99离