离散数学及其应用 课件 孙志海 第0-2章 概述、命题逻辑、谓词逻辑

离散数学

DiscreteMathematics

我爱你中国定义及学习范畴离散数学(DiscreteMathematics):是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。计算机专业核心基础课程研究离散量的结构和相互间的关系理论2学分+实践1学分离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元素。离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是许多专业课程，如面向对象程序设计、数据结构、操作系统、编译原理、人工智能、数据库、算法设计与分析等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与算法应用、创新性的研究和开发工作打下坚实的基础。学习的意义1数据结构

2操作系统3计算机网络4编译原理5数字电路6数据库7算法分析

8计算机图形图像9计算机程序设计10计算机网络11大数据12人工智能《离散数学》是多门专业课程的先行课离散数学九十九何愁没有女朋友6《离散数学》与古诗词离散与连续7离散数学与数字信号离散数学与音频信号我爱你中国演示罗刹海市离散数学与数字图像离散数学与数字图像白玛木洛李兰娟/s/g2Hs1lNNId-434bEqI2shA离散数学与数字视频时间空间时间空间离散视频序列应用案例离散数学与人脸识别离散数学与人脸识别17大学食堂装上人脸识别机师生可"刷脸吃饭"离散数学与人脸识别18离散数学与抠图技术离散数学与芯片设计离散数学与程序优化if(!((!p||q)&&p)||q){

//for(inti=0;i<5;i++)

//{//for(intj=0;j<100000000;j++)b++;//}}C++程序：0040D9CBmovedx,dwordptr[ebp-2Ch]0040D9CEandedx,0FFh0040D9D4testedx,edx0040D9D6jemain+114h(0040d9e4)0040D9D8moveax,dwordptr[ebp-30h]0040D9DBandeax,0FFh0040D9E0testeax,eax0040D9E2jemain+12Eh(0040d9fe)0040D9E4movecx,dwordptr[ebp-2Ch]0040D9E7andecx,0FFh0040D9EDtestecx,ecx0040D9EFjemain+12Eh(0040d9fe)0040D9F1movedx,dwordptr[ebp-30h]0040D9F4andedx,0FFh0040D9FAtestedx,edx0040D9FCjemain+137h(0040da07)0040D9FEmoveax,dwordptr[ebp-20h]0040DA01addeax,1汇编语言程序：A=((

p

q)

p)

q教学内容1．命题逻辑2．谓词逻辑3．集合论4．图论5.离散数学的应用举例22教材及参考文献23授课教材：离散数学及其应用，孙志海、张蒙，西安电子科技大学出版社，2023年.参考教材：1.应用离散数学（第3版），周丽、方景龙，人民邮电出版社，2021年.2.应用离散数学（第2版），方景龙、周丽，人民邮电出版社，2020年.3.屈婉玲、耿素云、张立昂,《离散数学》(第2版),高等教育出版社,2015.4.KennethH.Rosen.DescreteMathematicsanditsApplications(SeventhEdition,影印版).机械工业出版社，2012.5.B.Kolman,R.C.Busby,S.C.Ross.DiscreteMathematicalStructures(FifthEdition).PrenticeHall.罗平译，离散数学结构（第五版），高等教育出版社，20056.D.S.Malik,DiscreteMathematicalStructures–TheoryandApplications,高等教育出版社,2005.7.左孝凌等,《离散数学》,上海科技文献出版社,2002.8.李盘林等,《离散数学》,高等教育出版社,1999.9.张青、陈更力，《离散数学及其应用》，清华大学出版社，2016.小结离散数学是研究离散量的结构及相互关系的数学学科，应用广泛。数据结构与算法芯片设计计算机图形图像《离散数学及其应用》第1章命题逻辑目录1.1命题和逻辑联结词1.2命题公式及其真值表1.3命题公式的等价演算1.4命题公式的范式1.6命题公式的推理演算1.5联结词的完备集让计算机按业务需求工作，离不开程序设计，那什么是程序？程序=算法+数据算法=逻辑+控制可见“逻辑”对于编程是多么重要。要想学好、使用好计算机，逻辑是重要学习要素。此外，通过学习逻辑，掌握逻辑推理规律和证明方法，可以培养逻辑思维能力，掌握证明问题的技巧。逻辑学是一门研究思维形式及思维规律的科学，也是研究推理过程规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，就是判断；由一个或几个判断推出另一个判断，就是推理。用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。数理逻辑也叫符号逻辑，它已在数字逻辑电路、控制理论、程序设计、人工智能、自然语言以及计算机科学等领域有着广泛应用。最早提出用数学方法描述和处理逻辑问题的是德国数学家、哲学家莱布尼茨（G.W.Leibniz），从此数理逻辑形成了专门的学科。数理逻辑的主要内容包括逻辑演算（logicalcalculus）、公理化集合论（axiomaticsettheory）、模型论（modeltheory）、证明论（prooftheory）和递归论（recursivetheory），第1章和第2章主要介绍作为数理逻辑基础部分的命题逻辑和谓词逻辑（一阶逻辑）。本章首先介绍命题逻辑。命题逻辑是研究命题如何通过一些逻辑联结词构成更复杂的命题以及逻辑推理的方法。命题是指具有确定真假含义的陈述句。如果把命题看作运算对象，如同代数中的数字、字母或代数式，而把逻辑联结词看作运算符号，就像代数中的“加、减、乘、除”那样，这样由简单命题组成复合命题的过程就可以当作逻辑运算的过程，也就是命题演算。戈特弗里德·威廉·莱布尼茨1646年-1716年逻辑运算同代数运算一样具有一定的性质，满足一定的运算规律。例如，满足交换律、结合律、分配律，同时还满足逻辑上的双重否定律、吸收律、零律、同一律、德摩根律等。利用这些定律，可以进行逻辑推理，可以对复杂的复合命题进行简化，可以判断两个命题是否等价等。这些推理和证明在计算机程序设计、程序正确性证明、计算机硬件设计、人工智能等诸多方面都有应用。本章主要介绍命题、逻辑联结词、命题公式及其真值表、命题公式的等价演算、命题公式的范式、联结词的完备集和命题公式的推理演算等命题逻辑中的相关内容。1.1命题和逻辑联结词数理逻辑是研究推理的数学分支，而推理的前提和结论都是表达判断的陈述句（命题），因此，表达判断的陈述句（命题）构成了推理的基本单位。推理由一系列的陈述句（命题）组成。例如，因为5>4，所以5≠4。在这里“5>4”和“5≠4”是两个陈述句，整个“因为5>4，所以5≠4”也是一个陈述句。这三个陈述句都成立，即为真。这种能区分真假的陈述句称为命题（proposition）。作为命题的陈述句所表达的判断结果称作命题的真值，真值只取两个值：真或假。真值为真的命题称作真命题，真值为假的命题称作假命题。真命题表达的判断正确，假命题表达的判断错误。任何命题的真值都是唯一的，没有二义性。当一个命题是真命题时，我们称它的真值为“真”，用“T”或“1”表示；当一个命题是假命题时，我们称它的真值为“假”，用“F”或“0”表示。在命题逻辑中，对命题的组成部分不再进一步细分，以命题为基本研究单位，研究的粒度比较粗。1.1.1命题命题“因为5>4，所以5≠4”由两个更简单的命题“5>4”和“5≠4”组成。“5>4”和“5≠4”不能再分解成更简单的命题了。这种不能被分解成更简单的陈述句的命题称作简单命题或原子命题（simpleproposition）。在命题逻辑中，简单命题是最小的基本单位，对它不再细分。但在各种论述和推理中，所出现的命题多数不是简单命题，如上面的“因为5>4，所以5≠4”。由简单命题通过“联结词”连接而成的命题，称作复合命题（compoundproposition）。简单命题逻辑联结词+复合命题1.1.1命题判断给定的句子是否为命题，可以分两步进行：（1）判断所给定的语句是否为陈述句；（2）判断给定的语句所表达的判断结果是否有唯一的真值。1.1.1命题陈述句？真值唯一？+

1.1.1命题

解例1.1.1的13个句子中，语句（1)、（2）、（4）、（9）、（10）和（12）是命题，语句（3）、（5）、（6）、（7）、（8）、（11）和（13）不是命题。语句（1）和（2）是真命题。语句（3）的真值不确定，因为根据x和y的不同取值情况“x大于y”可真可假，即无唯一的真值，因而不是命题。语句（4）也是命题，虽然限于现在的认知，语句（4）的真值还不能确定，但该语句的真值客观存在而且唯一。语句（5）是感叹句，语句（6）是祈使句，语句（7）、（11）和（13）是疑问句，因而这5个语句都不是命题，语句（9）和（12）是真命题，语句（10）是假命题。1.1.1命题解例1.1.1的13个句子中，语句（1)、（2）、（4）、（9）、（10）和（12）是命题，语句（3）、（5）、（6）、（7）、（8）、（11）和（13）不是命题。语句（8）特别有意思，假设语句（8）为真，即“我正在说假话”是真的，那么我正在说真话，因而语句（8）的真值应为假，这与假设矛盾；反之，假设语句（8）为假，即“我正在说假话”是假的，那么我正在说假话，因而语句（8）的真值应为真，同样这与假设也矛盾。可见语句（8）既不能为真，也不能为假，真值无法确定，所以语句（8）也不是命题。像语句（8）这样由真能推出假，又由假能推出真，从而既不能为真也不能为假的陈述句称作悖论（paradox）。悖论的例子很多，例如，“我正在说谎”、“这句话是错的”、“本命题是假的”等语句也是悖论。悖论不是命题。由例1.1.1可知，命题是陈述句，而不能是疑问句、祈使句、感叹句等。判断结果不唯一确定的陈述句不是命题（有时需根据该命题所涉及的时间、空间来确定）。陈述句中的悖论不是命题。1.1.1命题

1.1.1命题

1.1.1命题1.1.1命题

说明

例1.1.2中出现的5个命题都是复合命题。不妨称“非p”，“q并且r”，“s或t”，“如果r，则u”和“r当且仅当u”上述表述形式为半形式化的，这种半形式化的表述形式不能令人满意。在数理逻辑中，经常将论述或推理中的各种要素都进行符号化，即构造各种符号语言来代替自然语言。为达到这个目的，需要进一步抽象化，即将联结词也符号化。在例1.1.2中出现的联结词共有5个，分别如下：“非”、“并且”、“或”、“如果……则……”、“当且仅当”以上这些联结词是自然语言中常用的联结词，但往往具有二义性（ambiguity），为了排除二义性，在数理逻辑中必须给出联结词的严格定义，并且将它们用特定的符号表示。完全由符号构成的语言称为形式语言（formallanguage）。1.1.1命题自然语言中常常使用下面的一些联结词，例如：（1）“非”、“不”、“没有”、“无”、“并非”、“并不”等来表示否定；（2）“并且”、“同时”、“以及”、“而（且）”、“不但……，而且……”、“既……，又……”、“尽管……，仍然……”、“和”、“也”、“同”、“与”等来表示同时；（3）“虽然……，也……”、“可能……，可能……”“或许……，或许……”等和“或（者）”的意义一样；（4）“若……，则……”、“当……，则……”、“如果……，就……”与“如果……，那么……”意义相同；（5）“充分必要”、“等同”、“一样”、“相同”与“当且仅当”的意义一样。也就是说，在自然语言中，这些联结词一般是同义的。在数理逻辑中将这些同义的联结词统一用专用符号表示，消除其二义性，以便书写、推演和讨论。1.1.2逻辑联结词与命题符号化命题逻辑中常用的5种逻辑联结词（logicalconnectives）有：否定词、合取词、析取词、蕴涵词和等值词。类似实数的加、减、乘、除运算，这5种逻辑联结词也可称为命题的5种运算。通过这些逻辑联结词可以把多个原子命题复合成一个复合命题。否定词合取词析取词蕴涵词等值词1.1.2逻辑联结词与命题符号化1.1.2逻辑联结词与命题符号化定义1.1.1设p为命题，复合命题“非p”（或“p的否定”）称作p的否定式，记作

p。符号

称作否定词（negation）。规定：

p

为真，当且仅当p为假。定义1.1.2设p，q为两个命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p∧q。∧称作合取词（conjunction）。规定：p∧q为真，当且仅当p与q同时为真。定义1.1.3设p，q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q。∨称作析取词（disjunction）。规定：p∨q为假，当且仅当p与q同时为假。（相容或、排斥或）定义1.1.4

设p，q为两个命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作p

q，p称作是蕴涵式的前件，q称作蕴涵式的后件，

称作蕴涵词（implication）。规定：“p

q为假，当且仅当p为真、q为假”。1.1.2逻辑联结词与命题符号化使用蕴涵词

时，要特别注意以下几点：在自然语言里，特别是在数学中，q是p的必要条件有许多不同的叙述方式，例如，“若p则q”、“如果p，则q”、“只要p，就q”、“因为p，所以q”、“p仅当q”、“只有q才p”、“除非q才p”、“除非q，否则‘非p’”、“若不q，则不p”等等。以上各种叙述方式表面看来有所不同，但都表示q是p的必要条件，因而都应使用蕴涵词

，符号化为p

q的形式，如下表所示。自然语义逻辑形式如果p，那么qp

q如果p，就qp

q只要p，就qp

q因为p，所以qp

q若p，则qp

qp仅当qp

q只有q，才pp

q除非q才pp

q除非q，否则非pp

q若不q，则不pp

qq是p的必要条件p

qpq

pp∧qp∨qp

q001001011011100010110111表1.1.1

p、p∧q、p∨q

与p

q的真值1.1.2逻辑联结词与命题符号化例1.1.3

将下列命题符号化（合取词）。（1）陈颖既用功又聪明。（2）陈颖不仅用功而且聪明。（3）陈颖虽然聪明，但不用功。（4）吴丽与林晗都是三好学生。（5）吴丽与林晗是同学。（6）2+2=4且雪是白色的。（7）你喜欢用微信，但我喜欢用QQ。解解题时，首先将涉及的原子命题符号化。（1）设p：陈颖用功；q：陈颖聪明。则命题（1）符号化为：p∧q。（2）设p：陈颖用功；q：陈颖聪明。则命题（2）符号化为：p∧q。（3）设p：陈颖用功；q：陈颖聪明。则命题（3）符号化为：q∧

p。（4）设r：吴丽是三好学生；s：林晗是三好学生。则命题（4）符号化为：r∧s。1.1.2逻辑联结词与命题符号化例1.1.3

将下列命题符号化（合取词）。（5）吴丽与林晗是同学。（6）2+2=4且雪是白色的。（7）你喜欢用微信，但我喜欢用QQ。解解题时，首先将涉及的原子命题符号化。（5）这里虽然使用了“与”，但这个“与”是连接该句主语中的“吴丽”与“林晗”的，而整个句子仍是简单陈述句，即（5）是原子命题，可将该原子命题符号化为如下形式：f：吴丽与林晗是同学。（6）设p：2+2=4；q：雪是白的。则命题（6）符号化为p∧q。（7）设p：你喜欢用微信；q：我喜欢用QQ。则命题（7）符号化为p∧q。1.1.2逻辑联结词与命题符号化例1.1.4将下列命题符号化（析取词）。（1）张静爱唱歌或爱跳舞。（2）张静只能选择1号楼的101或102寝室。（3）张静是浙江人或福建人。解先给出原子命题，并将其符号化，然后再将整个（复合）命题符号化。（1）设p：张静爱唱歌；q：张静爱跳舞。命题（1）符号化为：p∨q。显然这里的“或”为相容或，即当p与q有一个为真或同时为真时，这个复合命题为真。1.1.2逻辑联结词与命题符号化（2）设r：张静选择1号楼101寝室；s：张静选择1号楼102寝室。结合题意，这里的“或”应该为排斥或。r与s的取值有4种可能：同时为真，同时为假，一真一假和一假一真。如果符号化为r∨s，则当r和s都为真时r∨s为真，即表示张静可能同时选择1号楼的101和102两间寝室，这不符合原意。原意是张静只能选择1号楼101和102中的一间。然而，如何实现只能挑选一间寝室的要求呢？可以使用多个联结词，符号化为：(r∧

s)∨(

r∧s)。可以验证，该复合命题为真当且仅当r与s中一个为真，一个为假，而式子(r∧

s)∨(

r∧s)准确地表达了原意。当r为真s为假时，张静选择了1号楼的101寝室；当r为假s为真时，张静选择了1号楼的102寝室。r与s同时为真的情况是不允许的。(r∧

s)∨(

r∧s)的真值情况如表所示。rs(r∧

s)∨(

r∧s)FFFFTTTFTTTF1.1.2逻辑联结词与命题符号化例1.1.4将下列命题符号化（析取词）。（3）张静是浙江人或福建人。解

设t：张静是浙江人；u：张静是福建人。结合题意，这里的“或”应为排斥或。与例1.1.4（2）一样，可以将其符号化为(t∧

u)∨(

t∧u)。然而，张静不可能既是浙江人又是福建人，即t与u实际上不能同时为真，因而这种情况下也可以简单符号化为：t∨u。1.1.2逻辑联结词与命题符号化

1.1.2逻辑联结词与命题符号化自然语义逻辑形式如果p，那么qp

q如果p，就qp

q只要p，就qp

q因为p，所以qp

q若p，则qp

qp仅当qp

q只有q，才pp

q除非q才pp

q除非q，否则非pp

q若不q，则不pp

qq是p的必要条件p

q解在解题时，首先将涉及的原子命题符号化，然后再符号化复合命题。（1）设p：你的月工资收入超过5000元；q：你必须缴纳个人所得税。则命题（1）符号化为：

p

q（2）设p：1+1=2；q：雪是白色的。则命题（2）符号化为：

p

q设r：a能被4整除，s：a能被2整除。（3）~（7）描述的都是a能被2整除是a能被4整除的必要条件，因而均可符号化为：r

s在（3）~（7）中，由于a是给定的正整数，因而r与s的真值是客观存在的，但是真是假与a的具体取值有关，现在并不知道。然而，仔细分析可知，r与s是存在内在联系的，当r为真（即a能被4整除）时，s必为真（a能被2整除）。当r为假时，蕴涵式r

s前件为假，蕴涵式r

s也为真。综上，r

s真值为1。1.1.2逻辑联结词与命题符号化定义1.1.5

设p，q为两个命题，复合命题“p当且仅当q”称作p与q的等值式，记作p

q，

称作等值词。规定：p

q为真，当且仅当p与q同时为真，或同时为假。p

q的逻辑关系为p与q互为充分必要条件，即当p

q为真时，p取1（0）时q必须取1（0），而q取1（0）时p也必须取1（0），因此，p

q与(p

q)∧(q

p)等价。还需要注意的是，“p成立仅当q成立”表示“仅当q成立时p才可能成立，但q成立时p并不一定成立”，这与“p成立当且仅当q成立”意思不一样，前者的符号化结果是“p

q”，而后者的符号化结果是“p

q”。1.1.2逻辑联结词与命题符号化

1.1.2逻辑联结词与命题符号化

1.1.2逻辑联结词与命题符号化以上共定义了5种基本且常用，也是最重要的逻辑联结词，它们组成一个逻辑联结词集{

，∧，∨，

，

}，其中

为一元逻辑联结词，其余4个是二元逻辑联结词。这5个逻辑联结词的真值情况如表1.1.3所示。表1.1.3

p、p∧q、p∨q、p

q与

p

q的真值pq

pp∧qp∨qp

qp

q00100110110110100010011011111.1.2逻辑联结词与命题符号化使用多个联结词可以组成更复杂的复合命题，此外还可以使用圆括号“(”和“)”，“(”和“)”必须成对出现。复合命题也是命题，是陈述句，可以判断真假，并且真值唯一。在求解比较复杂的复合命题的真值时，除依据表1.1.3的取值以外，还要规定联结词的优先顺序。将圆括号计算在内，规定运算的优先顺序为（从左到右）：（高优先级）()，

，∧，∨，

，

（低优先级）由于基于运算的先后次序来理解逻辑表达式往往费时费力，而且容易出错，因而建议采用添加括号的办法，按先括号内后括号外的规则进行命题运算。本书推荐采用添加括号的方法来处理逻辑运算的先后次序。实际写程序的时候，添加一些成对的括号也有利于程序的解读和维护。

注意：布尔运算（例如C语言中的按位布尔运算）和命题运算的符号相同（

，∧，∨），但在推导过程中，布尔运算一般读作“非”、“与”和“或”，而在命题运算中则对应为“否定”、“合取”和“析取”。1.1.2逻辑联结词与命题符号化例1.1.7

令p：中国是世界四大文明古国之一，q：π是无理数，r：地球上没有水。求下列复合命题的真值。（1）((

p∧q)∨(p∧

q))

r（2）(q∨r)

(p

r)（3）(

p∨r)

(p∧

r)解p，q，r的真值分别为1，1，0，容易求出命题（1），（2），（3）的真值分别为1，1，0。例1.1.8

将命题“锲（qiè）而舍之，朽木不折；锲而不舍，金石可镂（lòu）”符号化。解设p：你锲，q：你舍，r：金石可镂，s：朽木可折。则该命题符号化为：((p∧

q)

r)∧((p∧q)

s)1.1.2逻辑联结词与命题符号化例1.1.9

将命题“只有努力学习、认真复习，才能取得好成绩”符号化。解

设p：努力学习，q：认真复习，s：取得好成绩，则该命题可符号化为：s

(p∧q)注意，该命题不能符号化为(p∧q)

s，符号化时要考虑条件的必要性和充分性。1.1.2逻辑联结词与命题符号化逻辑联结词与C语言的逻辑运算符有所不同，在C语言中，逻辑运算符有“&&”、“||”和“!”，其用法如下：（1）“&&”表示“与”的意思，需要两端的表达式的值都为True，该式的值才为True。（2）“||”表示“或”的意思，两端的表达式的值只要有一端为True，该式的值就为True。（3）“!”表示“非”的意思，将该式的真值换成相反的真值，即False和True互换。下表给出了逻辑联结词与C语言逻辑运算符的对应关系示例。1.1.2逻辑联结词与命题符号化逻辑联结词C语言逻辑运算符否定：

!p合取：∧p&&q析取：∨p||q蕴涵：

if(p)q;等值：

(p&&q)||(!p&&!q)异或：⊕(p||q)&&(!p||!q)1.2命题公式及其真值表1.2.1命题公式简单命题是命题逻辑中最基本的研究单位，其真值是确定的，它又称作命题常项或命题常元（propositionalconstant）。命题常项相当于初等数学中的常量。初等数学中还有变量，对应的，这里有命题变项。取值1（真）或0（假）的变项称作命题变项或命题变元（propositionalvariable）。用命题变项可以表示真值可变的陈述句。命题变项不是命题。命题变项与命题常项的关系如同初等数学中变量与常量的关系。今后也用p，q，r等表示命题变项。这样一来，p、q、r、s、t等既可以表示命题常项，又可以表示命题变项，具体可结合上下文（context）确定。1.2.1命题公式将命题变项用逻辑联结词和圆括号按照一定的逻辑关系连接起来的符号串称作命题公式（又称为合式公式，简称为公式）。当使用联结词集{

，∧，∨，

，

}时，命题公式的定义如下。定义1.2.1

命题公式是按下列规则定义的符号串。（1）单个命题变项和命题常项（0和1）是命题公式，称为原子命题公式。（2）若X是命题公式，则(

X)是命题公式。（3）若X，Y是命题公式，则(X∧Y)，(X∨Y)，(X

Y)，(X

Y)均是命题公式。（4）有限次地应用（1）~（3）形成的符号串是命题公式。上述定义是以递归的形式给出的，其中（1）称为基础，（2）和（3）称为归纳，（4）称为界限。设X为命题公式，Y为X中的一部分，若Y也是命题公式，则称Y为X的子公式。1.2.1命题公式说明：（1）定义1.2.1给出的命题公式的定义方式称作归纳定义或递归定义方式。（2）为方便起见，当(

X)，(X∧Y)，(X∨Y)，(X

Y)，(X

Y)等公式单独出现时，外层括号可以省去，写成

X，X∧Y，X∨Y，X

Y，X

Y等。另外，公式中不影响运算次序的括号也可以省去，例如公式(p∨r)∨(

s)可以写成p∨r∨

s。（3）由以上定义可知，如(p

q)∧(r

s)、(s∧q)∧

r、s∧(q∧

r)等都是命题公式，而sq

r、sqr、s

(r

q、p(r

q)和p∧q∧

等都不是命题公式。（4）一个含有命题变项的命题公式，该命题公式的真值是不确定的，这种情况下，命题公式本身不是命题。只有对该命题公式中的每个命题变项用指定的命题常项代替后，该命题公式才变成命题，其真值也唯一确定了。1.2.1命题公式

1.2.2真值表

1.2.2真值表

1.2.2真值表例1.2.1

写出下列命题公式真值表，并求它们的成真赋值和成假赋值。（1）(

p

q)

(q

p)（2）(p

q)∨(q

r)（3）

(p

q)∧q∧r解命题公式（1）是含2个命题变项的3层命题公式，它的真值表如表1.2.1所示。从表1.2.1可知，命题公式（1）的成假赋值为01，其余3个赋值（00、10、11）都是成真赋值。pq

pq

p

p

q(

p

q)

(q

p)001101011010100111110111表1.2.1(

p

q)

(q

p)的真值表1.2.2真值表命题公式（2）是含3个命题变项的2层命题公式，它的真值表如表1.2.2所示。由表1.2.2可以看出，该命题公式的8个赋值全是成真赋值，即无成假赋值。pqrp

qq

r(p

q)∨(q

r)000111001111010101011111100011101011110101111111表1.2.2(p

q)∨(q

r)的真值表1.2.2真值表命题公式（3）是含3个命题变项的4层命题公式，它的真值表如表1.2.3所示。不难看出，该命题公式的8个赋值全是成假赋值，无成真赋值。pqrp

q

(p

q)

(p

q)∧q

(p

q)∧q∧r00010000011000010100001110001000100101010011010001111000表1.2.3

(p

q)∧q∧r的真值表1.2.2真值表定义1.2.5

设X为任一命题公式。（1）若X在它的各种赋值下取值均为真，则称X为永真式或重言式（tautology）。（2）若X在它的各种赋值下取值均为假，则称X为永假式或矛盾式（contradictory）。（3）若X不是永假式，则称X是可满足式（satisfiable）。从定义1.2.5不难看出以下几点：（1）X是可满足式说明X至少存在一个成真赋值。（2）永真式一定是可满足式，但可满足式不一定是永真式。若公式X是可满足式，且它至少存在一个成假赋值，则称X为非永真式的可满足式。（3）真值表可用来判断公式X的类型。①若真值表最后一列全为1，则公式X为永真式。②若真值表最后一列全为0，则公式X为永假式。③若真值表最后一列中至少有一个为1，则公式X为非永真的可满足式。永真式可满足式1.2.2真值表pq(

p

q)

(q

p)001010101111表1.2.1(

p

q)

(q

p)的真值表pqr(p

q)∨(q

r)00010011010101111001101111011111表1.2.2(p

q)∨(q

r)的真值表pqrp

q

(p

q)

(p

q)∧q

(p

q)∧q∧r00010000011000010100001110001000100101010011010001111000表1.2.3

(p

q)∧q∧r的真值表非永真式的可满足式永假式永真式1.2.2真值表

1.2.2真值表例1.2.2

下列各公式均含2个命题变项p与q，它们中哪些具有相同的真值表？（1）p

q（2）p

q（3）

q∨p（4）

(p∧

q)（5）(p

q)∧(q

p)解表1.2.4给出了5个公式的真值表。从表1.2.4中可以看出，公式（1）与公式（4）具有相同真值表，公式（2）与公式（5）具有相同的真值表。pqp

qp

q

q∨p

(p∧

q)(p

q)∧(q

p)0011111011001010001001111111表1.2.45个公式的真值表1.2.2真值表

1.2.2

真值表解本例中给出的4个公式，总共有3个命题变项p，q和r，r是公式（1）的哑元，p是公式（2）的哑元，在讨论它们是否有相同的真值表时，均按照3个命题变项列出它们的真值表。表1.2.5列出了4个公式的真值表，中间过程省略了。从表1.2.5中可以看出，公式（1）与公式（4）有相同的真值表，公式（2）与公式（3）有相同的真值表。pqrp

q

q∨r(q

r)∧(p

p)(

p∨q)∧((p∧r)

p)00011110011111010100101111111000110101011011010011111111表1.2.54个公式的真值表1.2.2

真值表—哑元应用举例哑元参数：

（1）定义函数时，只有类型而没有变量名的形参被称为哑元；（2）哑元参数在函数实体中无法使用，但还必须传。需要使用哑元的场景：（1）在操作符重载函数中，区分前后++、--；（2）为了兼容旧的代码。例如布尔函数f(x，y，z)，其中f(x，y，1)=f(x，y，0)，即z取1或0都不影响函数f，这里z就成了哑元。在C++函数中，有类型无名字的形参可看成哑元，如：voidfun(double){cout<<"哑元"<<endl;}某函数升级中，以下形式可以实现新版本兼容老版本：老版本：voidfun(intn1,intn2,intn3){……}新版本：voidfun(intn1,intn2,int){……}1.3命题公式的等价演算1.3命题公式的等价演算

1.3命题公式的等价演算

1.3命题公式的等价演算

st

s

ts∨t

(s∨t)

s∧

t

(s∨t)

s∧

t00110111011010011001100111001001表1.3.1

(s∨t)，

s∧

t与

(s∨t)

(

s∧

t)的真值表1.3命题公式的等价演算

st

ts∧

ts

t(s∧

t)(s

t)001010010010101100110010

表1.3.2s∧

t，s

t与(s∧

t)

(s

t)的真值表1.3命题公式的等价演算

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.3命题公式的等价演算

1.3命题公式的等价演算（7）吸收律X∨(X∧Y)⇔X，X∧(X∨Y)⇔X（8）零律X∨1⇔1，X∧0⇔0（9）同一律X∨0⇔X，X∧1⇔X（10）否定律X∨

X⇔1，X∧

X⇔0（11）蕴涵律X

Y⇔

X∨Y（12）等值律X

Y⇔(X

Y)∧(Y

X)（13）逆反律X

Y⇔

Y

X（14）归谬律(X

Y)∧(X

Y)⇔

X1.3命题公式的等价演算

1.3命题公式的等价演算

左边=A

(B

A)

⇔A

(

B∨A)（蕴涵律）⇔

A∨(

B∨A)（蕴涵律）⇔(

A∨A)∨

B（交换律、结合律）⇔1∨

B（否定律）⇔1（零律）右边=

A

(A

B)

⇔

A

(

A∨

B)（蕴涵律）⇔

(

A)∨(

A∨

B)（蕴涵律）⇔A∨(

A∨

B)（双重否定律）⇔(A∨

A)∨

B（结合律）⇔1∨

B（否定律）⇔1（零律）所以A

(B

A)⇔

A

(A

B)1.3命题公式的等价演算

右边=(A∨B)∧(

A

B)

⇔(A∨B)∧((

A

B)∧(B

A))（等值律）⇔(A∨B)∧((A∨B)∧(

B∨

A))（蕴涵律）⇔(A∨B)∧(A∨B)∧(

A∨

B)（交换律）⇔(A∨B)∧(

A∨

B)（幂等律）1.3命题公式的等价演算例1.3.2

证明下面命题公式等价。（2）

(A

B)⇔(A∨B)∧(

A

B)解（2）再从左边开始演算：左边=

(A

B)

⇔

((A

B)∧(B

A))

（等值律）⇔

(A

B)∨

(B

A)

（德∙摩根律）⇔

(

A∨B)∨

(

B∨A)

（蕴涵律）⇔(A∧

B)∨(B∧

A)

（德∙摩根律）⇔(A∨(B∧

A))∧(

B∨(B∧

A))

（分配律）⇔(A∨B)∧(A∨

A)∧(

B∨B)∧(

B∨

A)（分配律）⇔(A∨B)∧1∧1∧(

B∨

A)

（否定律）⇔(A∨B)∧(

A∨

B)（同一律、交换律）所以

(A

B)⇔(A∨B)∧(

A

B)。1.3命题公式的等价演算例1.3.2

证明下面命题公式等价。（3）((A∧B)

C)∧(B

(D∨C))⇔(B∧(D

A))

C解（3）先从左边开始演算：左边=((A∧B)

C)∧(B

(D∨C))

⇔(

(A∧B)∨C)∧(

B∨(D∨C))（蕴涵律）⇔(

A∨

B∨C)∧(D∨

B∨C)（德∙摩根律、交换律）⇔(

A∨(

B∨C))∧(D∨(

B∨C))（结合律）⇔(

A∧D)∨(

B∨C)（分配律）右边=(B∧(D

A))

C

⇔(B∧(

D∨A))

C（蕴涵律）⇔

(B∧(

D∨A))∨C（蕴涵律）⇔

B∨

(

D∨A)∨C（德∙摩根律）⇔

B∨(D∧

A)∨C（德∙摩根律）⇔(

A∧D)∨(

B∨C)（交换律）再从右边开始演算：所以((A∧B)

C)∧(B

(D∨C))⇔(B∧(D

A))

C。1.3命题公式的等价演算

也可以从右边开始演算：

左边=(A∧B)

C

（蕴涵律）（结合律）（蕴涵律）（蕴涵律）右边=A

(B

C)

（蕴涵律）（蕴涵律）（结合律）（蕴涵律）

1.3命题公式的等价演算

左边=(A∧

B)∨(

A∧B)

（分配律）

（否定律）

（同一律）

（交换律）

（交换律）1.3命题公式的等价演算例1.3.3

化简程序段 ifp∧qthen ifq∨rthen

X else

Y end else ifp∧rthen

Y else

X end end解从左边程序段可知，执行程序段X的条件为：((p∧q)∧(q∨r))∨(

(p∧q)∧

(p∧r))⇔(p∧(q∧(q∨r)))∨((

p∨

q)∧(

p∨

r))⇔(p∧q)∨(

p∨(

q∧

r))⇔((p∧q)∨

p)∨(

q∧

r)⇔((p∨

p)∧(

p∨q))∨(

q∧

r)⇔(1∧(

p∨q))∨(

q∧

r)⇔(

p∨q)∨(

q∧

r)⇔((

p∨q)∨

q)∧((

p∨q)∨

r)⇔(

p∨q∨

q)∧(

p∨q∨

r)⇔1∧(

p∨q∨

r)⇔

p∨q∨

r⇔

(p∧

q∧r)1.3命题公式的等价演算例1.3.3

化简程序段 ifp∧qthen ifq∨rthen

X else

Y end else ifp∧rthen

Y else

X end end解从左边程序段可知，执行程序段Y

的条件为：((p∧q)∧

(q∨r))∨(

(p∧q)∧(p∧r))⇔(p∧q∧

q∧

r)∨((

p∨

q)∧(p∧r))⇔0∨((

p∨

q)∧(p∧r))⇔(

p∨

q)∧(p∧r)⇔(

p∧(p∧r))∨(

q∧(p∧r))⇔(

p∧p∧r)∨(

q∧p∧r)⇔0∨(p∧

q∧r)⇔p∧

q∧r因此例1.3.3的程序段可以化简为： ifp∧

q∧rthen

Y else

X end1.3命题公式的等价演算例1.3.4

设A，B，C是任意的命题公式，请用等价演算法化简下列命题公式并将最后结果用只含

和∨联结词表示。（1）

A∧

B∧(

C

A)（2）(A

(B∨

C))∧

A∧B解（1）

A∧

B∧(

C

A)

（蕴涵律）（双重否定律）（分配律）（否定律）（同一律）1.3命题公式的等价演算例1.3.4

设A，B，C是任意的命题公式，请用等价演算法化简下列命题公式并将最后结果用只含

和∨联结词表示。（1）

A∧

B∧(

C

A)（2）(A

(B∨

C))∧

A∧B解（2）(A

(B∨

C))∧

A∧B

（蕴涵律）（结合律）（吸收律）1.4命题公式的范式古代文献中多用来表示模子、法则。

1.4.1析取范式和合取范式本节给出命题公式的两种规范化表示方法，这种规范化的表达式能表达真值表所能提供的一切信息。定义1.4.1

单个命题变项及其否定统称为文字（literals）。如果文字包含否定符号“

”，将其称为负文字（negativeliteral），否则称为正文字（positiveliteral）。L为文字，形如L、

L的一对字符称为互补文字对。仅由有限个文字构成的析取式称作简单析取式（初等和）。仅由有限个文字构成的合取式称作简单合取式（初等积）。例如，p、

p、q、

r等均为文字，p、q为正文字，

p、

r为负文字。p、

p为互补文字对。s、

t，s∨

s、

s∨t和

s∨

t∨r、s∨

t∨

r、

s∨

t∨

r都是简单析取式，分别由1个文字、2个文字和3个文字构成。

s、t，s∧

s、s∧

t和s∧

t∧

r、

s∧t∧

r、

s∧

t∧

r都是简单合取式，分别由1个文字、2个文字和3个文字构成。注意，一个文字既是简单合取式，又是简单析取式。所以，如s，

t，

r既是简单析取式又是简单合取式。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.1析取范式和合取范式设Xi是含n个文字的简单析取式，若Xi中既含某个命题变项pj，又含它的否定式

pj，则由交换律、否定律和零律可知，Xi为永真式。反之，若Xi为永真式，则它必同时含有某个命题变项及它的否定式。否则，若将Xi中的不带否定符的命题变项都取0值，带否定符的命题变项都取1，此赋值为Xi的成假赋值，这与Xi是永真式相矛盾。类似地，设Xi是含n个文字的简单合取式，若Xi中既含某个命题变项sj，又含有它的否定式

sj，则Xi为永假式。反之，若Xi为永假式，则Xi中必同时含某个命题变项及它的否定式。1.4.1析取范式和合取范式

1.4.1析取范式和合取范式例如，(

s∧t)∨(

t∧

r)、(s∧

t)∨

r是析取范式，(

s∨t)∧(

s∨

t∨

r)、(s∨

r)∧

t是合取范式。

s∧t∧

r既是由一个简单合取式构成的析取范式，又是由3个简单析取式构成的合取范式；类似情况，

s∨t∨

r既是由3个简单合取式构成的析取范式，又是由一个简单析取式构成的合取范式。析取范式和合取范式具有下述性质。定理1.4.2

（1）一个析取范式是永假式，当且仅当它的每个简单合取式都是永假式。（2）一个合取范式是永真式，当且仅当它的每个简单析取式都是永真式。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.1析取范式和合取范式常见命题公式中含有5个逻辑联结词{∧，∨，

，

，

}，如何把这些命题公式化成等价的析取范式和合取范式呢？首先，可以利用蕴涵律和等值律X

Y⇔

X∨YX

Y⇔(X

Y)∧(Y

X)消去任何命题公式中的逻辑联结词

和

。其次，对范式中出现的如下形式：

X、

(X∧Y)、

(X∨Y)，利用双重否定律和德∙摩根律，即

X⇔X

(X∧Y)⇔

X∨

Y

(X∨Y)⇔

X∧

Y1.4.1析取范式和合取范式再次，对析取范式中出现的X∧(Y∨Z)形式，和合取范式中出现的X∨(Y∧Z)形式，利用分配律，即X∧(Y∨Z)⇔(X∧Y)∨(X∧Z)X∨(Y∧Z)⇔(X∨Y)∧(X∨Z)由以上3步，可将任一公式化成与之等价的析取范式和合取范式。于是得到下述定理。定理1.4.3

任意命题公式都存在与之等价的析取范式和合取范式。求给定命题公式的范式的步骤如下：（1）消去逻辑联结词“

”“

”；（2）用双重否定律消去双重否定词，用德∙摩根律内移否定词；（3）利用分配律，即求析取范式时使用∧对∨的分配律，求合取范式时使用∨对∧的分配律。1.4.1析取范式和合取范式例1.4.1

求下面公式的析取范式和合取范式。

r

(r

s)

解

先消去蕴涵联结词

r

(r

s)

（消去

）（双重否定律）（合取范式、析取范式）1.4.1析取范式和合取范式例1.4.2求下面公式的析取范式和合取范式。

(r∨s)

(r∧s)

解

先消去等值联结词

(r∨s)

(r∧s)

（消去

）（消去

）（分配律、德∙摩根律）（幂等律、分配律）（合取范式）（∧对∨的分配律）（∧对∨的分配律）（否定律）（交换律）（析取范式）1.4.1析取范式和合取范式例1.4.3求下面公式的析取范式和合取范式。(r

s)

t

解

为了让演算过程尽可能清晰和无误，利用交换律使每个简单析取式和简单合取式中的命题变项都按照字典顺序出现。

（1）求合取范式(r

s)

t

（消去

）（消去

）（消去

）（德∙摩根律、交换律）（∨对∧的分配律）这是由3个简单析取式构成的合取范式。1.4.1析取范式和合取范式（2）求析取范式求析取范式与求合取范式的前两步相同，只是在利用分配律时有所不同，因而前4步与（1）相同，接着使用∧对∨的分配律，具体如下：(r

s)

t

⇔(

r∨s)

t（消去

）⇔((

r∨s)

t)∧(t

(

r∨s))（消去

）⇔(

(

r∨s)∨t)∧(

t∨(

r∨s))（消去

）⇔((r∧

s)∨t)∧(

r∨s∨

t)（德∙摩根律、交换律）⇔((r∧

s)∧(

r∨s∨

t))∨(t∧(

r∨s∨

t))（∧对∨的分配律）⇔(r∧

s∧

r)∨(r∧

s∧s)∨(r∧

s∧

t)

∨(t∧

r)∨(t∧s)∨(t∧

t)（∧对∨的分配律）⇔0∨0∨(r∧

s∧

t)∨(t∧

r)∨(t∧s)∨0（否定律）⇔(r∧

s∧

t)∨(

r∧t)∨(s∧t)（同一律、交换律）可以看出，最后一步与倒数第三步的结果都是析取范式。一般情况下，命题公式的析取范式是不唯一的。同样，合取范式也是不唯一的。为了使命题公式的范式唯一，需进一步将简单合取式和简单析取式规范化。1.4.2标准析取范式和标准合取范式由于一般范式的不唯一性，机器仍然不能以此机械地作出识别和判定，因此本小节追求一种更为严格的范式形式——标准范式（主范式），它存在且唯一。定义1.4.4

在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按照下标从小到大或按照字典顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）。例如，r∧

s是关于r、s的极小项，

t是关于t的极小项，r∧s∧t、r∧

s∧

t、

r∧s∧

t均是关于r、s、t的极小项，但r∧

s、

t就不是关于r、s、t的极小项。又如r∨

s是关于r、s的极大项，

t是关于t的极大项，r∨s∨t、r∨

s∨

t、

r∨s∨

t均是关于r、s、t的极大项，但r∨

s、t就不是关于r、s、t的极大项。1.4.2标准析取范式和标准合取范式由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可以构成2n个不同的极小项，而且每个极小项都有且仅有一个成真赋值。利用二进制数讨论极小项最方便：以mk表示极小项，其下标k是二进制数，当最小项中出现第i个命题变项时，二进制下标k左起的第i位为1；当极小项中出现第i个命题变项的否定时，二进制下标k左起的第i位为0。例如，命题变项s，t形成的极小项

s∧t的符号是m01。同理，n个命题变项可以构成2n个极大项：以Mk表示极大项，其下标k是二进制数，当极大项中出现第i个命题变项时，二进制下标k左起的第i位为0；当极大项中出现第i个命题变项的否定时，二进制下标k左起的第i位为1。例如，命题变项s，t形成的极大项

s∨t的符号是M10。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.2标准析取范式和标准合取范式表1.4.1列出了含s、t的全部极小项与极大项。极小项极大项公式成真赋值符号（二进制）符号（十进制）公式成假赋值符号（二进制）符号（十进制）

s∧

t00m00m0s∨t00M00M0

s∧t01m01m1s∨

t01M01M1s∧

t10m10m2

s∨t10M10M2s∧t11m11m3

s∨

t11M11M3表1.4.1含s、t的全部极小项与极大项1.4.2标准析取范式和标准合取范式表1.4.2列出了含r、s、t的全部极小项和极大项。表1.4.2含r、s、t的全部极小项与极大项极小项极大项公式成真赋值符号（二进制）符号（十进制）公式成假赋值符号（二进制）符号（十进制）

r∧

s∧

t000m000m0r∨s∨t000M000M0

r∧

s∧t001m001m1r∨s∨

t001M001M1

r∧s∧

t010m010m2r∨

s∨t010M010M2

r∧s∧t011m011m3r∨

s∨

t011M011M3r∧

s∧

t100m100m4

r∨s∨t100M100M4r∧

s∧t101m101m5

r∨s∨

t101M101M5r∧s∧

t110m110m6

r∨

s∨t110M110M6r∧s∧t111m111m7

r∨

s∨

t111M111M71.4.2标准析取范式和标准合取范式定义1.4.5

在析取范式中，若每个简单合取式都是极小项，且极小项按下标递增排序，则称该析取范式为标准析取范式（主析取范式，principaldisjunctivenormalform）。若这个标准析取范式与命题公式X等价，则称它为公式X的标准析取范式。定义1.4.6

在合取范式中，若每个简单析取式都是极大项，且极大项按下标递增排序，则称该合取范式为标准合取范式（主合取范式，principalconjunctivenormalform）。若这个标准合取范式与命题公式X等价，则称它为公式X的标准合取范式。1.4.2标准析取范式和标准合取范式定理1.4.4

任意含n个命题变项的非永假式的命题公式X都存在唯一的与之等价的标准析取范式。证明

这先证明存在性。（1）先把命题公式X化成析取范式。（2）将简单合取式中重复出现的命题变项、永假式及重复出现的极小项都“消去”，即用t代替t∧t，0代替t∧

t，mi代替mi∨mi等。（3）用同一律和否定律补进简单合取式中未出现的其他变项。例如，根据t⇔1∧t⇔(s∨

s)∧t⇔(s∧t)∨(

s∧t)补进命题变项s，根据t⇔1∧1∧t⇔(r∨

r)∧(s∨

s)∧t⇔(r∨

r)∧((s∧t)∨(

s∧t))⇔((r∨

r)∧(s∧t))∨((r∨

r)∧(

s∧t))