1、离散数学离散数学离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。数理逻辑简介数理逻辑简介 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广
2、泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。第一章命题逻辑第一节 命题符号化及联结词内容：内容：命题，逻辑联结词，命题符号化(1)掌握命题概念(2)掌握联结词含义及真值表(3)掌握命题符号化方法 重点：重点：一、命题的概念一、命题的概念 命题：能判断真假的陈述句。TF真（记为 或1）真值假（记为 或0）例例1、判断下列句子中哪些是命题。(1)北京是中国的首都。(2)雪是黑色的。(4)请把门关上！(6)地球外的星球上也有人。3 412(3)。x(5)是有理数。例例1、判断下列句子中哪些是命题。(7)明天有课吗？(8)本语句是
3、假的。(9)小明和小林都是三好生。(10)小明和小林是好朋友。判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。,iiip q rp q r表示。命题常项，命题变项均用二、逻辑联结词。二、逻辑联结词。简单命题（不能再分解成更简单的命题）命题复合命题（由简单命题用联结词联结而成的命题）,这五种常用的联结词有真值表 ppp1、“非”称为 的否定式，记作pp例如：11是素数；：11不是素数pp取值1，取值0。真值表 pq,p qpq2、“并且”称为的合取式，记作。pqpq在例1.(9)中，：小明是三好生，：小林是三好生则小明和小林是三好生表示为。(1)李平既聪明又用功。pq(2)李平虽
4、然聪明，但不用功。pq(3)李平不但聪明，而且用功。pq(4)李平不是不聪明，而是不用功。()pq pq例例2、设：李平聪明，：李平用功。真值表 pq,p qpq3、“或者”称的析取式，记作。pqpq例如，：小明学过英语，：小明学过日语，则小明学过英语或日语可表示为真值表：pq,p qpqpq4、“如果 那么”称的蕴涵式，记作其中为前件，为后件。例例3、一位父亲对儿子说：“如果我去书店，就一定给你买本儿童画报。”问：什么情况下父亲食言？解解：可能情况有四种：(1)父亲去了书店，给儿子买了儿童画报。(2)父亲去了书店，却没给儿子买儿童画报。(3)父亲没去书店，却给儿子买了儿童画报。(4)父亲没去
5、书店，也没给儿子买儿童画报。(1)如果天不下雨，我就骑车上班。pq(2)只要天不下雨，我就骑车上班。pq(3)只有天不下雨，我才骑车上班。(4)除非天下雨，否则我就骑车上班。pq(5)如果天下雨，我就不骑车上班。pq qp(或 )pq pq例例4、：天下雨，：我骑车上班。真值表：pq,p qpq5、“当且仅当”称的等价式，记作。ppqq是的充要条件，也是的充要条件。pqpq pq pq 224pq例例5、：，：3是奇数224(1)当且仅当3是奇数。224(2)当且仅当3不是奇数。224(3)当且仅当3是奇数。224(4)当且仅当3不是奇数。6、逻辑联结词与自然语言中联结词的关系。否定否定不是，
6、没有，非，不。合取合取并且，同时，和，既又，不但而且，虽然但是。析取析取或者，或许，可能。蕴涵蕴涵若则，假如那么，既然那就，倘若就，如果就，只要就，因为所以，仅当。只有q才p，除非q才p，除非q否则非p。等价等价当且仅当，充分必要，相同，一样。7、运算顺序 逻辑联结词也称逻辑运算符，规定优先级的顺,，若有括号时，先进行括号序为内运算。()()pqpqrq 例如：三、命题符号化。三、命题符号化。步骤：(1)找出各简单命题，分别符号化。(2)找出各联结词，把简单命题逐个联结起来。例例6、将下列命题符号化。(1)小王是游泳冠军或百米赛跑冠军。(2)小王现在在宿舍或在图书馆。：小王是游泳冠军，p：小王
7、是百米赛跑冠军。q设原语句化为pq。：小王在宿舍，p：小王在图书馆。q设原语句化为pq。例6、将下列命题符号化。(3)选小王或小李中的一人当班长。(4)如果我上街，我就去书店看看，除非我很累。：选小王当班长，p：选小李当班长。q设原语句化为()()pqpq 。：我上街，pq：我很累。r：我去书店看看，设原语句化为()rpq()rpq)。(或(5)小丽是计算机系的学生，她生于1982或1983年，她是三好生。：小丽是计算机系的学生，：小丽生于1982年，：小丽生于1983年，：小丽是三好生。pqrs设原语句化为()pqrs。第二节第二节 命题公式及分类命题公式及分类 内容：内容：命题公式，重言式
8、，矛盾式，可满足公式。重点：重点：(1)掌握命题公式的定义及公式的真值表。(2)掌握重言式和矛盾式的定义及使用真 值表进行判断。一、命题公式一、命题公式 通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。规定：公式中最外层的括号，及()A的括号可省略。例例1、判断以下字符串中哪些是命题公式。(1)()pqr()pqr (2)pqr(3)(4)(pqr(5)pq(6)()pqr 解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。2、命题公式的层次。5ppqrpr 例2、为_层公式。kAAk若的最高层次为，则称为 层公式。3、真值表。AA成真赋值（使 为真的赋值）赋
9、值成假赋值（使 为假的赋值），()Apqr1,1,0pqrAA如公式，110(按字典序)为的成假赋值，111，011，010等是的成真赋值。个命题变项的命题公式，共有(1)n n 2n含组不同赋值。A公式的解释或赋值3、真值表。(3)对应每个赋值，计算各层次的值，直至整个公式。的真值表指AA在所有赋值之下取值列成的表。构造A的真值表步骤：(1)列出所有命题变项的所有赋值(2,3n 2n个，掌握)。(2)从低到高写出A的各层次。例例3、求下列命题公式的真值表。(1)()qpp解解：例例3、求下列命题公式的真值表。(2)()()pqqp 解：解：二、重言式、矛盾式，可满足式。二、重言式、矛盾式，可
10、满足式。重言式可满足式命题公式其它矛盾式2、判定方法:真值表法。1、定义 例例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？(1)()()pqpq(2)()pqpqqp(3)()pqq(4)()ppq(5)()ppq例例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？(6)pqpp(7)()()pqpq(8)()ppqqr(9)()()pqrpqr (10)()pqr解：解：列出各题真值表如下(步骤简略)(1)、(2)、(5)、(6)、(9)为重言式；(3)、(8)为矛盾式；(4)、(7)、(10)及以上的重言式均为可满足式。第三节第三节 等值
11、演算等值演算 内容：内容：等值关系，24个重要等值式，等值演算。重点：重点：(1)掌握两公式等值的定义。(2)掌握24个重要等值式，并能利用其进行等值演算。一、两命题公式间的等值关系。一、两命题公式间的等值关系。2、判定。,A BABABAB1、定义：设为两命题公式，若等价式是重言式，则称与 是等值的，记作。,A BAB是否重言式。是否等值，即判断判断两公式(1)，()Apq Bpq 解：解：作真值表如下：例例1、判断,A B两公式是否等值。解解：作真值表如下：(2)，Apq()()Bpqqp例例1、判断,A B两公式是否等值。二、重要等值式。二、重要等值式。2、结合律()()ABCABC()
12、()ABCABC，3、分配律()()()ABCABAC()()()ABCABAC，1、交换律ABBAABBA，二、重要等值式。二、重要等值式。4、德摩根律()ABAB ()ABAB ，6、吸收律()AABA()AABA，5、等幂律AAAAAA，二、重要等值式。二、重要等值式。10、双重否定律()AA 9、互否律1AA 0AA(矛盾律)(排中律)，7、零律11A 00A，8、同一律0AA1AA，二、重要等值式。二、重要等值式。11、蕴涵等值式 ABAB 12、等价等值式()()ABABBA13、假言易位 ABBA 14、等价否定等值式 ABAB 15、归谬论()()ABABA 三、等值演算。三、
13、等值演算。例例2、验证下列等值式。(1)()()pqrpqr(2)()()pqrpqrqr (3)()1qpqp 置换定理：如果AB()()AB。，则例例2、验证下列等值式。(1)()()pqrpqr解解：()pqr()pqr 蕴涵等值式()pqr 蕴涵等值式()pqr 结合律()pqr 德摩根律()pqr蕴涵等值式例例2、验证下列等值式。(2)()()pqrpqrqr ()()pqrpqr 解解：()()qrpqrp交换律()()qrpp分配律()1qr排中律 qr同一律(3)()1qpqp 解：解：()qpqp()()qppqp 分配律 0()qqp矛盾律()qqp同一律()qqp 德摩根
14、律()qqp结合律 1p 排中律 1零律 考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法真值表法和等值演算法等值演算法。例3、用两种方法证明:()()pqpqpq 证法一 用真值表法 由最后两列真值完全相同，于是命题成立。例3、用两种方法证明:()()pqpqpq 证法二 用等值式法()()pqpq pqpq 蕴涵等值式()()pqpq 双重否定律()()pqpq 交换律 pqpq 结合律 pq 吸收律 例4、将下图所示的逻辑电路简化 rqp解：将上述逻辑电路写成命题公式：p
15、qprqr利用等值式将公式化简 pqprqrpqrqr分配律 pqrqr结合律()pqr等幂律 所以，该电路可简化为下图：rqp第四节第四节 联结词的全功能集联结词的全功能集 内容：内容：联结词的全功能集，极小功能集。了解：了解：全功能集，极小功能集。真值表：由定义知：()()pqpqpq 一、联结词一、联结词,。,p q,p q记作pq1、“的排斥或(异或)，之间恰有一个成立”称。真值表：()pqpq 的与非式，记作pq,p qpq并且2、“的否定”称。真值表：()pqpq 的或非式，记作pq,p qpq3、“或者 的否定”称。二、全功能集，极小功能集。二、全功能集，极小功能集。全功能集全功
16、能集：若干个联结词的集合，其余的联结词均可由它们表示。最小全功能集最小全功能集：不含冗余联结词的全功能集。,例如：等都是全功能集。,等都是极小全功能集。第五节第五节 对偶与范式对偶与范式 内容：内容：对偶原理，命题公式的范式。重点：重点：(1)掌握对偶式，对偶原理。(2)掌握析取范式和合取范式的定义和求法步骤。(3)掌握极小项，极大项的概念及主范式的求法。一、对偶原理。一、对偶原理。1、对偶式。pq例如：与pq，与，()pqr()pqr 与()0pq()1pqA,0,1,1,0*AA定义：设公式仅含联结词，则将分别用替代，所得的公式称 的对偶式。与A*A互为对偶式。2、对偶原理。所以可得：()
17、()()ABCABAC若AB*AB。，则例如：已知()()()ABCABAC(分配律)，与()()ABAC()()ABAC均为相互对偶式，且()ABC()ABC，与二、范式。二、范式。1、简单析取式，简单合取式。简单析取式简单析取式:由有限个命题变项或其否定构成的析取式简单合取式简单合取式:由有限个命题变项或其否定构成的合取式例如：pqpqpq 等都是简单析取式。，例如：pqpqpq 等都是简单合取式。，2、析取范式，合取范式。例如：()()()Apqppqpq 为析取范式，()()Bpqpqq 为合取范式。定义：定义：由有限个简单合取式构成的析取式称作析取范式析取范式。由有限个简单析取式构成
18、的合取式称作合取范式合取范式。2、析取范式，合取范式。例如：()()()Apqppqpq 为析取范式，显然，*()()()Apqppqpq 为合取范式，()()Bpqpqq 为合取范式。例如：*()()Bpqpqq 为析取范式。2、析取范式，合取范式。范式存在定理：范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。求范式步骤：求范式步骤：(2)否定消去或内移。(3)利用分配律。(1)消去联结词,解：解：原式 pqrp 消去 pqrp 内移 pqrp消去()()prqrp 上式即析取范式 例例1、求公式pqrp的析取范式和合取范式。分配律 对(分配)解：解：原式 pqrp 消去 pq
19、rp 内移 pqrp消去()()pqprp 上式即合取范式 例例1、求公式pqrp的析取范式和合取范式。分配律(分配)对二、范式。二、范式。简单析取式简单析取式:由有限个命题变项或其否定构成的析取式简单合取式简单合取式:由有限个命题变项或其否定构成的合取式由有限个简单合取式构成的析取式称作析取范式析取范式。由有限个简单析取式构成的合取式称作合取范式合取范式。求范式步骤：求范式步骤：(2)否定消去或内移。(3)利用分配律。(1)消去联结词,解解：原式()()prqrp析取范式()pqr 析取范式 合取范式()()pqprp 原式()()pqrp 合取范式 例例1、求公式pqrp的析取范式和合取范
20、式。三、主范式。三、主范式。1、极小项，极大项。1,2,np ppn12*nppp12*nppp*(1,2,)ipinipip定义：定义：设命题公式含这个命题变项，则和分别称为极小项极小项和极大项极大项，其中为或。都是极小项，,pq pq,pqpq 都是极大项，例如，对只含变项,p q的命题公式中，但pqq不是极小项。但ppq不是极大项。极大项，极小项。3n,p q r3下面分别讨论，即个命题变项的极小项 pqr pq r p qr p q r pqr pqr pqr pqr成真赋值(二进制数)000 001 010 011 100 101 110 111 对应十进制数 01234567记法
21、0m1m2m3m4m5m6m7m极大项 pqrpqrpqr pqr pqr pqr pqr pqr 成假赋值(二进制数)000 001 010 011 100101110111 对应十进制数 01234567记法 0M1M2M3M4M5M6M7M2、主析取范式，主合取范式。主析取范式主析取范式每个简单合取式都是极小项的析取范式。主合取范式主合取范式每个简单析取式都是极大项的合取范式。两种求法，等值式法等值式法和真值表法真值表法。定理：定理：任何命题公式的主析取范式、主合取范式 都存在且都是唯一的。步骤：(3)消去重复的及永假项。2.1、利用等值式法求命题公式A的主析取范式。(1)求AA，的析取
22、范式(2)利用 1()iiBBBpp()()iiBpBp补充变元ip，(4)按角码顺序排序，并用“”表示。解：解：由例1的析取范式为()()prqrp qrpp pqqrr()()qrpqrp ()()pqrpqr()()pqrpqr 例例2、求公式Apqrp的主析取范式。()Aqrp()prpp吸收律)解：解：由例1的析取范式为()()prqrp()()Apqrpqr ()()pqrpqr()()pqrpqr 627654mmmmmm24567mmmmm(2,4,5,6,7)例例2、求公式Apqrp的主析取范式。步骤：(3)求每个成真赋值对应的十进制数，即极小项的角码，将极小项按序析取即成。
23、2.2、利用真值表求命题公式A的主析取范式。(1)列出A的真值表，(2)找出A的所有成真赋值，解：解：(1)列真值表 例例3、用真值表求Apqrp的主析取范式。解：解：(2)的成真赋值有010，100，101，110，111(3)对应的十进制数为2，4，5，6，7 所以的主析取范式为 24567mmmmm(2,4,5,6,7)例例3、用真值表求Apqrp的主析取范式。步骤：(3)消去重复的及永真项；2.3、利用等值式法求命题公式A的主合取范式。(1)求AA；的合取范式(2)利用 0()iiBBBpp()()iiBpBp补充变元ip；(4)按角码顺序排序，并用符号“”表示；如134MMM(1,3
24、,4)。记为解：解：由例1，()()Apqpr合取范式 pqrrprqq()()pqrpqr()()prqprq 例例4、求公式Apqrp的主合取范式。解：解：由例1，()()Apqrpqr()()pqrpqr 013MMM(0,1,3)例例4、求公式Apqrp的主合取范式。2.4、利用真值表求命题公式的主合取范式。步骤：(3)求每个成假赋值对应的十进制数，即极大项的角码，将极大项按序合取即成。(1)列出A的真值表，(2)找出A的所有成假赋值，例例5、用真值表求Apqrp的主合取范式。解：解：(1)由例3知A真值表，的(3)对应的十进制数为0，1，3。例例5、用真值表求Apqrp的主合取范式。
25、解：解：(2)A的成假赋值有000，001，011，013(0,1,3)AMMM 所以A的主合取范式：思考：思考：命题公式间有什么联系，能否通过其中一个求另一个？(观察例3，例5)A的主合取范式，主析取范式由例3、例5知：013(0,1,3)AMMM 24567Ammmmm(2,4,5,6,7)013Ammm()AA 013()mmm 013mmm 013MMM2.5、已知命题公式的主析取范式(主合取范式)，求主合取范式(主析取范式)。(2)写出与(1)中极小项角码相同的极大项，由AA的主合取范式步骤：的主析取范式求(1)写出A的主析取范式未出现的极小项，(3)由以上极大项合取即成A的主合取范
26、式。13457AMMMMM(1,3,4,5,7)例例6、(1)已知命题公式026(0,2,6)Ammm 的主合取范式。(AAA主析取范式为：求含3个命题变项)解：解：A的主合取范式为：13(1,3)Amm()()Apqpq 02(0,2)MM 例例6、(2)已知命题公式A主合取范式为：的主析取范式。(AA求含2个命题变项)解：解：A的主析取范式为：3、主范式的用途。(1)判断两命题公式是否等值。(2)判断命题公式的类型。重言式主析取范式含全部的极小项主合取范式不含任何极大项(主合取范式记为1)矛盾式主析取范式不含任何极小项(主析取范式记为0)主合取范式含全部的极大项3、主范式的用途。(2)判断
27、命题公式的类型。可满足式主析取范式至少含一个极小项主合取范式至少缺一个极大项(3)求成真(假)赋值。(4)求真值表。例例7、已知含3个命题变项的公式：0167Ammmm和01234567BMMMMMMMM(1)判断,A B的类型。解：解：AB为矛盾式。为可满足式，(2)判断,A B是否等值。解：解：,A B不等值。的成假赋值有010，011，100，101。A例例7、已知含3个命题变项的公式：0167Ammmm和01234567BMMMMMMMM(3)求A的成真赋值和成假赋值。的成真赋值有000，001，110，111。A解：解：(4)求A的真值表。解：解：真值表 第六节第六节 推理规则推理规
28、则 内容：内容：重点：重点：(1)理解推理的概念；(2)掌握8条推理定律；(3)掌握推理规则；(4)掌握构造证明法。了解：了解：附加前提证明法和归谬法。推理规则，构造证明法。推理的概念，推理定律，一、推理的形式结构。一、推理的形式结构。2、判断推理的方法。等值演算法等值演算法，真值表法真值表法，主析取范式法主析取范式法。1、定义：定义：12()kAAAB记作12()kAAAB则称前提12,kA AABB12,kA AA若为重言式，推结论的推理正确，为的逻辑结论或有效结论。例例1、判断下面各推理是否正确。(1)如果天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。结论：q推理形式结构为：pq
29、pq判断此蕴涵式是否为重言式。前提：,pq p，解：解：设pq小王去游泳。：天气凉快，方法一方法一 用等值式法。用等值式法。1pqpq 所以推理正确。方法二方法二 用真值表法。用真值表法。其真值表中最后一列全为1，所以推理正确。方法三方法三 用主析取范式法。用主析取范式法。pqpq0123mmmm(0,1,2,3)主析取范式含全部最小项，所以推理正确。(2)如果我上街，我一定去新华书店，我没上街，所以我没去新华书店。前提：,pqp结论：q推理的形式结构为：pqpq解：解：设pq：我去新华书店，：我上街，方法一方法一 pqpq023mmm(0,2,3)其主析取范式中缺极小项1m所以推理不正确。，
30、方法二方法二 pqpqpqpq 蕴涵等值式 pq 吸收律 pq方法三方法三所以推理不正确。列出真值表，其最后一列不全为1,由于01是pq推理不正确。的成假赋值，并非重言式，二、构造证明法。二、构造证明法。1、推理定律有以下8条：(1)附加附加()AAB(2)化简化简ABA(3)假言推理假言推理ABAB(4)拒取式拒取式 ABBA(5)析取三段论析取三段论 ABAB二、构造证明法。二、构造证明法。1、推理定律有以下8条：(6)假言三段论假言三段论 ABBCAC(7)等价三段论等价三段论 ()ABBCAC(8)构造性二难构造性二难()()()()ABCDACBD2、推理规则。(1)前提引入规则(3
31、)置换规则 3、构造证明法。依照推理规则，应用推理规律。(2)结论引入规则 例例2、构造下列推理的证明。(1)前提：,pr qs pq结论：rs证明：证明：前提引入 qs前提引入 前提引入 pq rs构造性二难 pr例例2、构造下列推理的证明。(2)前提：结论：,pq pr stsrt q证明：证明：st前提引入 前提引入 ts 拒取式 sr 前提引入 r假言推理 例例2、构造下列推理的证明。(2)前提：结论：,pq pr stsrt q证明：证明：pr 前提引入 p拒取式 pq前提引入 q析取三段论 例例3、写出对应下面推理的证明。(1)如果今天是星期一，则要进行英语或离散数学考试。如果英语
32、老师有会，则不考英语，今天是星期一，英语老师有会，所以进行离散数学考试。解：解：前提：(),pqr sq p s 结论：r：今天是星期一，pq：进行离散数学考试，rs：进行英语考试，：英语老师有会。证明：证明：()pqr前提引入 p前提引入 qr假言推理 sq 前提引入 s前提引入 q假言推理 r析取三段论 前提：(),pqr sq p s 结论：r(2)如果6是偶数，则2不能整除7；或者5不是素数，或者2整除7；5是素数。因此，6是奇数。解：解：前提：,pqrq r 结论：p：6是偶数，pqr：5是素数。：2整除7，证明：证明：rq 前提引入 rq置换规则 r前提引入 q假言推理 pq 前提
33、引入 p拒取式 前提：,pqrq r 结论：p(3)如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加。因此，如果甲参加篮球赛，那么丙就参加。解：解：前提：,()pq pqr 结论：qr：乙参加篮球赛，：丙参加篮球赛。pqr：甲参加篮球赛，(3)如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加。因此，如果甲参加篮球赛，那么丙就参加。解：解：前提：,()pq pqr 结论：qr：乙参加篮球赛，：丙参加篮球赛。pqr：甲参加篮球赛，证明：证明：前提引入 置换规则 前提引入 假言三段论 pq qp()pqr()qqr qr置换规则 qqrqqr qqqr q
34、rqr ()前提：,()pq pqr 结论：qr3、附加前提证明法和归谬法。(1)附加前提证明法。12()()kAAAAB12()()kAAAAB 12()kAAAAB 12()kAAAAB例如：例3 (3)前提：,()pq pqr 结论：qr用附加前提证明：pq q附加前提引入 前提引入 p拒取式 例如：例3 (3)前提：,()pq pqr 结论：qr用附加前提证明：()pqr 前提引入 qr 假言推理 r化简 由附加前提证明法知推理正确。(2)归谬法。因为12()kAAAB12()kAAAB 即证明 12kAAABCC(其中C为任意命题公式)例如：例3 (2)前提：,pqrq r 结论：p
35、用归谬法证明：p否定结论引入 pq 前提引入 q假言推理 rq 前提引入 例如：例3 (2)前提：,pqrq r 结论：p用归谬法证明：r析取三段论 r前提引入 rr合取 由归谬法知推理正确。第一章第一章 小结与例题小结与例题 一、命题与联结词。一、命题与联结词。1、基本概念。2、应用。(1)选择适当的联结词将命题符号化。(2)判断命题(简单或复合)的真假。命题与真值；简单命题和复合命题；命题常项和变项；五个联结词真值表。,，二、命题公式及分类。二、命题公式及分类。1、基本概念。命题公式的定义；公式的赋值；重言式，矛盾式，可满足式。2、应用。(1)求给定公式的真值表，及成真赋值，成假赋值。(2
36、)用真值表判断给定公式的类型。三、等值演算。三、等值演算。1、基本概念。两个公式等值的含义；等值演算。2、应用。(1)灵活运用24个重要等值式。(2)用等值演算判断公式的类型及两个公式 是否等值(也可用真值表)。四、联结词的全功能集。四、联结词的全功能集。基本概念联结词的全功能集，极小全功能集。五、对偶与范式。五、对偶与范式。1、基本概念。对偶式，对偶原理；简单析取式，简单合取式；析取范式，合取范式；极小项，极大项；主析取范式，主合取范式。五、对偶与范式。五、对偶与范式。2、应用。(1)求给定公式的主析取范式和主合取范式。(2)用主析取范式或主合取范式判断两公式是否等值。(3)用主析取范式或主
37、合取范式求公式的成真或成假赋值。(4)用主析取范式或主合取范式判断公式的类型。六、推理理论。六、推理理论。1、基本概念。推理，推理规则，推理定律；构造证明法。2、应用。(1)判断推理是否正确：真值表法 等值演算法 主析取范式法(主合取范式法)。(2)用8条推理定律构造推理的证明。例例1、判断下列各语句中，命题，简单命题，复合命题，真命题，假命题，真值待定的命题各有哪些？(2)2是素数或是合数，(4)只有4是奇数，5才能被3整除。(5)明年5月1日是晴天。(1)230 x，(3)若224，则5是偶数，例例1、判断下列各语句中，命题，简单命题，复合命题，真命题，假命题，真值待定的命题各有哪些？解：
38、解：命题有(2)(5)，其中(5)是简单命题，(2)，(3)，(4)是复合命题，(2)，(4)为真命题，(3)为假命题，(5)真值待定。(1)()qrp解：解：我将进城去当且仅当我有空且天不下雪。(2)pq解：解：虽然天正在下雪，但我将进城去。例例2、设：天正在下雪；：我将进城；：我有空。用自然语言写出下列命题。pqr(3)()()qrrq解：解：我进城当且仅当我有空。(4)()rp解：解：天不下雪且我没空。例例2、设：天正在下雪；：我将进城；：我有空。用自然语言写出下列命题。pqr例例3、设试求下列命题的真值。p q的真值为0，、r s的真值为1，、(1)()pqr解：解：()pqr0(01
39、)1例例3、设试求下列命题的真值。p q的真值为0，、r s的真值为1，、(2)()()pqrs 解：解：()()pqrs (00)(1 1)1(01)1 1 1例例3、设试求下列命题的真值。p q的真值为0，、r s的真值为1，、(3)()()()prspqrs解：解：()()()prspqrs(0(1 1)(00)(1 1)001例例3、设试求下列命题的真值。p q的真值为0，、r s的真值为1，、(4)()()pqrprs解：解：()()pqrprs(0(0(10)(11)011例例4、简化下列命题公式。(1)()()pqqpr 解：解：()()pqqpr ()()pqpqr1r r例例
40、4、简化下列命题公式。(2)()ppqq 解：解：()ppqq (1)pp pp1例例4、简化下列命题公式。(3)()()pqrpqr 解：解：()()pqrpqr ()()ppqr1()qr qr例例4、简化下列命题公式。(4)()pqprr解：解：()pqprrr例例5、判断下列各命题公式，哪些是重言式，矛盾式，可满足式？(1)()pqr(2)()ppq(3)()pqpq解：解：可用真值表法，等值演算法，主析取(主合取)范式等方法判断公式的类型，(2)为重言式，(3)为矛盾式，(1)，(2)均为可满足式。例例6、求命题公式()()pqqp 的主析取范式，主合取范式，成真赋值和成假赋值。解：
41、解：先求主析取范式()()pqqp ()pqqp ()()pqppq ()pqq()()()pqpqpq 例例6、求命题公式()()pqqp 的主析取范式，主合取范式，成真赋值和成假赋值。解：解：先求主析取范式()()pqqp 023mmm(0,2,3)故主合取范式为()()pqqp 1M例例6、求命题公式()()pqqp 的主析取范式，主合取范式，成真赋值和成假赋值。解：解：成真赋值为极小项角码对应的二进制数，即00，10，11。成假赋值为极大项角码对应的二进制数，即01。例例7、设()()Aprqrp(1)求的真值表。A(2)求的主析取范式、主合取范式。A解：解：例例7、设()()Aprq
42、rp(2)求的主析取范式、主合取范式。A解：解：()()Apqrpqr ()()pqrpqr ()()pqrpqr 012357mmmmmm(0,1,2,3,5,7)例例7、设()()Aprqrp(2)求的主析取范式、主合取范式。A解：解：()()Apqrpqr 46MM(4,6)例例8、判断下列推理是否正确。解：解：可用多种方法(如真值表法，等值演算法，主范式法)验证，()ppqpq 并非重言式，故推理不正确。(1)前提：ppq结论：pq，例例8、判断下列推理是否正确。(2)如果今天是星期二，则明天是星期四。今天是星期二，所以明天是星期四。以上推理即假言推理，所以是正确的。解：解：pq：明天
43、是星期四，：今天是星期二，p前提：结论：pqq，例例9、写出对应下面推理的证明。有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四。证明：证明：设：红队第三，p：黄队第二，q：蓝队第四，r：白队第一。s前提：(),pqrsp q 结论：sr前提：(),pqrsp q 结论：sr前提引入 附加前提引入析取三段论前提引入()pqr sp p sqr假言推理前提：(),pqrsp q 结论：sr假言推理前提引入假言推理qrrq由附加前提证明法知推理正确。例例10、一公安人员审查一件盗窃案，已知的
44、事实如下：(1)甲或乙盗窃了录音机；(2)若甲盗窃了录音机，则作案时间不能发生在午夜前；(3)若乙的证词正确，则午夜时屋里灯光未灭；(4)若乙的证词不正确，则作案时间发生在午夜之前；(5)午夜时屋里灯光灭了。问是谁盗窃了录音机。：乙盗窃了录音机，q：作案时间发生在午夜前，r：乙的证词正确，s：午夜灯光未灭。t解：解：设p：甲盗窃了录音机，前提：pqpr stsr，t，结论：pq 或者 t前提引入 st前提引入 s拒取式 sr 前提引入 r假言推理 前提：pqpr stsr，t，p拒取式 pq前提引入 q析取三段论 所以是乙盗窃了录音机。pr 前提引入 r假言推理 前提：pqpr stsr，t，
