作者：陈志奎 主编
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
离散数学(普通高等教育软件工程“十二五”规划教材)试读：
前言
软件工程作为一个人才培养的独立专业，并单独成立全国示范性软件学院，已经有10多年了。经过10多年的发展，软件工程专业已经成为与计算机科学与技术专业并列的一级学科。但目前，软件工程专业所使用的教材大多来自于计算机科学与技术专业。离散数学是计算机科学与技术和软件工程专业培养体系中的核心基础课程。大多数《离散数学》教材都是针对计算机科学与技术专业的，数学性比较强，着重于数学理论的建立与推导，相对而言工程应用比较薄弱，软件工程专业的学生自学阅读时比较困难。有些国外的教材逻辑性强但实例较少，不太适合自学；有些教材实例较多，但逻辑性较差，中国学生难以接受。
基于我们在软件工程专业教授离散数学多年经验的基础上，经过广泛的调研以及和人民邮电出版社组织“软件学院教材”编写专家会议讨论后，一致认为很有必要编写一本实例较多，逻辑性合理，浅显易懂，便于软件学院学生学习的离散数学课程教材。
离散数学在本科软件工程专业的授课内容一般分为四大部分：数理逻辑、集合论、代数系统、图论，这4个部分紧密连接。数理逻辑描述了一个符号化体系，这个体系可以描述集合论中的所有概念。集合论中又有3个小模块：集合、关系、函数。关系是集合中笛卡儿乘积的子集，函数是关系的子集。代数系统是定义函数的运算。图论是一类特殊的代数系统。本书针对软件工程专业，强调系统逻辑性，前后内容的衔接，在内容安排上点出这种联系并将章节高度的模块化，另外，整本书使用统一的符号化体系描述和解题。因此本教材具有以下一些特点。
首先，本教材着重体现理论与应用的结合。离散数学是软件工程专业的核心课程之一，与高等数学、线性代数等其他公共数学课程不同。但是，对于学生而言，往往误把它作为同高等数学一样的公共数学课，仅仅认识到离散数学的理论公式部分，看不到其在实际中的应用价值以及同软件工程专业之间的关系和在软件工程专业中所处的位置。本书的一个着眼点就是在章节结构清晰的基础上，每一个部分都与具体的应用相结合，比如布尔逻辑与信息检索、图的遍历与网络爬虫、图的最短路径与地图导航等。每一个定义、定理都由软件工程的实例加以解释和说明，增强可读性。对软件学院的学生来说，看到这些应用与实例能够激发学生的学习热情，并培养建立离散模型解题的认识和能力，不断增强对软件工程的认识和理解。为此，在本教材中，我们为这些定义和定理准备了大量的范例，将抽象的内容具体化，来降低理解的难度。
其次，实例同软件工程的相关性强。对知识点的解释方式同被教授对象的知识体系的吻合度越高，其被理解和吸收的效率就越高。为了使教材中的知识点可以更好地被软件工程专业的学生所掌握，我们在教材中应用了许多同计算机科学相关的实例。
最后，离散数学是很多软件工程专业课程的先修课，比如说操作系统、数据结构、编译原理等。本书将相关理论与后续专业课联系，真正实现先修课的价值和无缝衔接，帮助学生构建自己的知识架构。将软件工程的基本原理贯穿到离散数学的知识点，贯穿到后续课程的体系中。
在本书的编写过程中，得到了许多教师的帮助，特别是曹晓东教授和史哲文老师对书稿进行了认真的审阅，并提出了宝贵的修改意见，对此我们表示衷心的感谢。本书的第 3 章至第 5章由周勇完成，其他部分由陈志奎完成。作者还要感谢人民邮电出版社的编辑，在他们的支持下，本书才能很快出版发行。另外，本书在编写过程中参考和引用了有关方面的书籍，作者在此对参考文献中所有的作者表示衷心的感谢。
本书可作为软件工程专业的教材，也可作为计算机科学与技术专业的教材。
由于作者的学识水平有限，书中如出现不准确、不适宜或者疏漏的内容，希望读者给予批评指正，在此表示感谢。编者2013年春于大连理工大学第1章命题逻辑
逻辑为确定一个给出的论证是否有效提供各种方法和技巧，而根据研究对象和方法的不同可以分为形式逻辑、辩证逻辑和数理逻辑。其中数理逻辑就是用数学方法研究人的思维形式和规律,通过建立一套表意符号体系对事物进行抽象并推理，从而研究前提和结论间的形式关系的科学。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。
利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在17世纪就有人提出过。莱布尼茨就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程像数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。
一般认为，旧逻辑学的创始人是公元前4世纪的希腊思想家亚里士多德（Aristotle）；新逻辑学的创始人是 17 世纪的德国哲学家莱布尼兹（Leibniz）和 19 世纪中叶的英国数学家乔治·布尔（George Boole）。1847年，布尔发表了《逻辑的数学分析》，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。
19世纪末20世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了《数论的基础》一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的还有美国人皮尔斯，他也在著作中引入了逻辑符号，从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。之后英国数学家德·摩根（A. De Morgan）和罗素（B.A.W.Russell）等人丰富和完善了数理逻辑。
命题逻辑和谓词逻辑是计算机科学领域中所必需的数理逻辑基础知识。在本章中，将对命题逻辑进行介绍和讨论。1.1 命题和联结词1.1.1 命题的概念
定义1.1 命题是或者为真，或者为假而不是两者同时成立的陈述句。
作为命题的陈述句所表达的判断结果称作命题的真值，真值只能取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。注意：任何命题的真值都是唯一的。
如果一个命题的真值是真，则用1或T(Ture)来表示；如果一个命题的真值是假，则用0或F （False）来表示。
命题用大写的英文字母，如P，Q，R…来表示。
判断给定句子是否为命题分为两步：首先判断该句子是否为陈述句，其次判断它是否有唯一的一个真值。
例1.1 判断下面句子是否是命题。（1）2013年是闰年。（2）2×2=5。（3）小明晚上去看电影。（4）这朵花真漂亮啊！（5）请不要在此处吸烟！（6）你下午会出去吗？（7）2既是素数又是偶数。（8）本句话是错的。
以上句子中（1）、（2）、（3）和（7）都是命题。注意：一个陈述句能否判断真假与现实能否判断真假是两件事。（4）、（5）是感叹句，（6）是疑问句，不是命题。对于（8），如果本句话确实是错的，那么“本句话是错的”便是真；另一方面，如果“本句话是错的”是真，那么本句话便是假。从以上分析我们只能得出这样的结论：本句话既不是对的又不是错的，这显然是矛盾的，也就是说对于该陈述句无法指定它的真值。这样的陈述句称为悖论，不是命题。
在上面的命题中，（1）、（2）、（3）都不能再被分割成为更小的命题，它们是基本的、原始的，这样的命题被称为原子命题。而命题（7）则不是最基本的，它还可以被分解为更小的命题：可由“2是素数”和“2是偶数”这两个命题由“与”联结词组合而成。像这种由更小的命题组合而成的命题称为复合命题。1.1.2 联结词
联结词是逻辑联结词或者命题联结词的简称，它是自然语言中连词的逻辑抽象。有了联结词，就可以通过它和原子命题构成复合命题。常用的逻辑联结词主要包括以下6种。（1）联结词“非”，记为“┓P ”，表示“否定”的意思。（2）联结词“合取”，记为“∧”，表示“且”的意思。（3）联结词“析取”，记为“∨”，表示“或”的意思。（4）联结词“蕴涵”，记为“→”，表示“如果…，则…”的意思。（5）联结词“等价”，记为“↔”，表示“当且仅当”的意思。（6）联结词“异或”，记为“∇”，表示“要么…，要么…”的意思。
下面给出这6种联结词的详细定义。（1）逻辑联结词否定——“┓”
设P是一个命题，则联结词┓和命题P构成┓P，┓P为命题P的否定式复合命题，读作“非P”。联结词┓是自然语言中的“非”、“不”和“没有”等的逻辑抽象。
其真值是这样定义的，若P的真值是T，那么┓P的真值是F；若P的真值是F，则┓P的真值是T。命题P与其否定┓P的如表1.1所示。表1.1 逻辑联结词“┐”的定义
例1.2 给出下列命题的否定。（1）令P表示：大连是北方香港。
于是┓P表示：大连不是北方香港。
注意：逻辑联结词否定是个一元运算符。（2）令Q表示：所有的素数都是奇数。
于是┓Q表示：并非所有的素数都是奇数。
注意：翻译成“所有的素数都不是奇数”是错误的。因为否定是对整个命题进行的。（2）逻辑联结词合取——“∧”
设P是一个命题，Q是一个命题，由联结词∧把P和Q连接成P∧Q，称P∧Q为P和Q的合取式复合命题，P∧Q读作“P与Q”或者“P合取Q”。联结词∧是“并且”的逻辑抽象。
它的真值是这样定义的：当且仅当P和Q的真值都为T时，P∧Q的真值才为T，否则P∧Q的真值为F。逻辑联结词“∧”的定义如表1.2所示。表1.2 逻辑联结词“∧”的定义
例1.3 令P表示：外面正在下雪。
令Q表示：3小于5。
于是P∧Q表示：外面正在下雪并且3小于5。
从自然语言看，上述命题是不合理的、没有意义的，因为P和Q毫不相关。但是，在数理逻辑中是被允许的，也是正确的。P和Q再合取P∧Q仍可成为一个新的命题。只要P和Q的真值给定，P∧Q的真值即可确定。
逻辑联结词“∧”是个二元运算符，且具有对称性，即P∧Q和Q∧P具有相同真值。（3）逻辑联结词析取——“∨”
设P是一个命题，Q是一个命题，由联结词∨把P、Q连接成P∨Q，称P∨Q为P、Q的析取式复合命题，读作“P或Q”，或“P析取Q”。
其真值是这样的定义的：当且仅当P和Q的真值均为F时，P∨Q的真值为F，其余情况均为T。逻辑联结词“∨”的定义如表1.3所示。表1.3 逻辑联结词“∨”的定义
联结词∨是自然语言中“或”、“或者”的逻辑抽象。而在自然语言中，“或”是多义的。从析取的定义不难看出，逻辑联结词“∨”和自然汉语中的“或”的意义并不完全相同。因为汉语中的“或”可表示“排斥或”，亦可表示“可兼或”，而逻辑联结词“析取”指的仅仅是“可兼或”，并不表示其他意义的“或”。
例1.4 令P表示：小明现在正在睡觉。
令Q表示：小明现在正在打球。
于是命题，小明现在正在睡觉或者正在打球不能用P∨Q来表示。因为这里自然语言陈述的或是排斥或，这种意义的或我们用另一个逻辑联结词“异或”“∇”来表示，后面我们将给出它的定义。
例1.5 将句子“他昨晚做了20或者30道作业题”表示为复合命题。
在此例中，该句子不能被表示成复合命题，因为这里的“或”表示的是近似或者猜测的意思。
例1.6 令P表示：张亮是跳高运动员。
令Q表示：张亮是跳远运动员。
于是命题，张亮可能是跳高或跳远运动员就可以用P∨Q来表示，因为这里的或是可兼或。
逻辑联结词析取也是个二元运算符。（4）逻辑联结词单条件——“→”
设P是一个命题，Q是一个命题，由联结词→把P、Q连接成P→Q，称P→Q为P、Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。P→Q读作“如果P则Q”或“如果P那么Q”。其中P被称为前件，Q被称为为后件。很多时候联结词→也被称为蕴涵。
P→Q的真值是这样定义的，当且仅当P→Q的前件P的真值为T，后件Q的真值为F时，P→Q的真值为F，否则，P→Q的真值为T。单条件逻辑联结词“→”的定义如表1.4所示。表1.4 逻辑联结词“→”的定义
例1.7（1）令P表示：天不下雨
令Q表示：植物枯萎
于是P→Q表示：如果天不下雨，则植物枯萎。（2）令R表示：我有时间。
令S表示：我一定去学画画。
于是，R→S表示：如果我有时间，那我一定去学画画。（3）令U表示：大海的颜色是蓝色的。
令V表示：雪的颜色是白色的。
于是，U→V表示：如果大海的颜色是蓝色的，那么雪的颜色是白色的。
此例中（1）和（2）是有因果关系的，而（3）在自然科学中是毫无道理。在自然语言中，条件式的前提和结论之间必含有某种因果关系，但是在命题演算中，一个单条件逻辑联结词的前件并不需要联系到它的后件，它给出的是一种实质性的因果关系，而不单单是形式上的因果关系。也就是说只要前件P和后件Q的真值确定下来，命题P→Q的真值就可以确定。
逻辑联结词单条件是个二元运算符。（5）逻辑联结词双条件——“↔”
设P是一个命题，Q是一个命题，于是联结词↔把P、Q连接成P↔Q，称P↔Q为P和Q的双条件式复合命题，读作“P当且仅当Q”或“P等值于Q”。
P↔Q的真值是这样定义的，当且仅当P和Q有相同的真值时，P↔Q的真值为T，否则， P↔Q的真值为F。P↔Q的运算表如表1.5所示。表1.5 逻辑联结词“↔”的定义
例1.8 使用联结词翻译以下命题。（1）三角形是等边的，当且仅当它的3个内角相等。（2）电灯不亮，当且仅当灯泡发生故障或开关发生故障。（3）2 + 2 = 4，当且仅当今天天晴。
解：令P：三角形是等边的。
Q：三角形3个内角相等。
于是（1）可表示为：P↔Q
令R：电灯不亮。
S：灯泡发生故障。
T：开关发生故障。
于是（2）可表示成：R↔(S∨T)。
令A：2 + 2 = 4。
B：今天天晴。
于是（3）可表示为：A↔B
注意：从上面的例子中可以看出，等值式也和前面的逻辑联结词∧、∨、→一样可以毫无因果关系，而其真值仅仅从等值的定义而确定。
双条件逻辑联结词也是个二元运算符。（6）逻辑联结词异或——“∇”
设P是一个命题，Q是一个命题，于是“P异或Q”是一个新的命题，记作“P∇Q”，读作“P异或Q”。其真值是这样定义的，当且仅当P和Q有不同的真值时，P∇Q的真值为T，否则P∇Q的真值为F。
P∇Q的运算表如表1.6所示。
例1.9 令P表示：大连电视台三套节目今晚八点播放电视剧。
令Q表示：大连电视台三套节目今晚八点播放女排比赛。
于是P∇Q表示大连电视台三套节目今晚八时播放电视剧或播放女排比赛。表1.6 逻辑联结词“∇”的定义
从逻辑联结词“∇”的定义和逻辑联结词“↔”的定义不难得出，它们之间有如下的关系。
P∇Q⇔¬（P↔Q）。也就是说逻辑联结词异或可以用双条件逻辑联结词的否定来代替。
以上我们介绍了五个基本的逻辑联结词：┓，∧，∨，→，↔，它们运算的优先级为：┓优先级最高，其次是∧，∨，→，↔。如果有括号，则括号优先，在括号里从左往右依然遵守这个顺序。1.2 合式公式与真值表1.2.1 合式公式
在上一节中我们曾指出，不可再分的命题称为原子命题。换句话说，不包含任何逻辑联结词的命题称为原子命题。应该指出的是，这里所说的原子命题，是指其中的原子是有了确定的真值的；否则，原子没有确定的真值指派其原子的取值而是在｛T,F｝这个域上的，则称此原子为命题变元。由命题变元，逻辑联结词及圆括号可以构成合式的公式。下面给出命题演算中合式公式的递归定义。
定义1.2 合式公式。（1）真值T和F是合式公式。（2）原子命题公式是一个合式公式。（3）如果A是合式的公式，那么┓A是合式的公式。（4）如果A和B均是合式的公式，那么(A∧B)，(A∨B),(A→B)和(A↔B)都是合式的公式。（5）当且仅当有限次地应用（1）至（4）条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式的公式。
以上定义方法称为递归定义法。其中（1）称为递归定义的基础，（2）、（3）和（4）称为递归定义的归纳，（5）称为递归定义的界限。
今后我们还会经常使用这种递归定义的方法。
按照上面的定义，下面的字符串都是合式的公式。（1）┓(P∧Q)（2）┓(P→Q)（3）(P→(P∧┓Q))（4）(((P→Q)∧(Q→R))↔(S↔T))
下面的字符串则不是合式的公式。（1）(P→Q)→(∧Q)（2）(P→Q（3）(P∧Q)→Q)
今后，我们把合式的公式简称为命题公式。一般一个命题公式的真值是不确定的，只有用确定的命题去取代命题公式中的命题变元，或对其中的命题变元进行真值指派时，命题公式才成为具有确定真值的命题。
给定两个命题公式，若对其中变元的所有可能的真值指派两个命题公式具有相同的真值，则称它们是相互等价的。可以利用真值表技术来判定两个命题公式的等价性。1.2.2 真值表
定义1.3 设A为一命题公式，对其中出现的命题变元做所有可能的每一组真值指派S，连同公式A相应S(A)的取值汇列成表，称为A的真值表。一个真值表由两部分构成。（1）表的左半部分列出公式的每一种解释。（2）表的右半部分给出相应每种解释公式得到的真值。
为构造的真值表方便和一致，有如下约定。（1）命题变元按字典序排列。（2）对公式的每种解释，以二进制数从小到大或者从大到小顺序排列。（3）若公式复杂，可先列出各子公式的真值（若有括号从里层向外展开），最后列出所给公式的真值。
例1.10（1）给出命题公式┓((P∨Q)∧P)的真值表。（2）使用真值表技术证明命题公式P↔Q与P∧Q∨┓P∧┓Q是相互等价的。
解：构造（1）的真值表如下。
对于（2）构造真值表如下。
从真值表可以清楚地看出，命题公式P↔Q与P∧Q∨┓P∧┓Q对于变元P和Q的各种真值指派，他们的真值表完全一致。所以它们是相互等价的。1.3 永真式和等价式1.3.1 永真式
通过对命题公式真值表的讨论，可以清楚地看出对于命题公式nA(P1,P2，…，Pn)(n≥1)，命题变元的真值有2种不同的组合。每一种n组合叫做一种真值指派，以就是说，命题公式含有n个变元时有2种真值指派。而对应于每一组真值指派，命题公式将有一个确定的值，从而使命题公式成为具有确定真值的命题。
例1.11 对命题公式P∨┓P,P∧┓P,P→Q做出真值表。
解：3个命题公式的真值表如下。续表
例1.11中，命题公式P∨┓P，和P∧┓P，虽然都仅含一个命题变元，都有两组真值指派，但是对应于每一组真值指派，命题公式 P∨┓P 均取值为 T(即 1),而命题公式 P∧┓P 却取值为F(即0）。之所以有这样的结果是因为这些命题公式的真值与其变元的真值指派无关，而根本问题在于它们的自身结构。命题公式P→Q含有两个命题变元，有四组真值指派。对于第1，第2和第4这3组真值指派，公式取值为1（即T）；而对于第3组真值指派，公式却取值为0 （即F）。
通过上面对有关公式真值表的讨论，我们总结出如下的定义。
定义1.4 永真式、永假式与可满足式。（1）不依赖于命题变元的真值指派，而总是取值为 T（即 1）的命题公式，称为永真式或称作重言式。（2）不依赖于命题变元的真值指派，而总是取值为F（即0）的命题公式，称为永假式或矛盾式。（3）至少存在一组真值指派使命题公式取值为T的命题公式，称为可满足的。1.3.2 等价式
在有限步内判定一个命题公式是永真式，永假式或是可满足式的问题被称为命题公式的判定问题。我们的着眼点放在对重言式的研究上，因为它最有用，重言式有以下特点。（1）重言式的否定是一个矛盾式，一个矛盾式的否定是重言式，所以只研究其中之一就可以了。（2）重言式的析取，合取，单条件，双条件都是重言式。于是可由简单的重言式推出复杂的重言式。（3）由重言式可以产生许多有用的恒等式。
设 A:A(P1 ,P2 ,…,Pn )
B:B(P1,P2,…,Pn)
是两个命题公式，这里Pi（i=1，2，…，n）不一定在两个公式中同时出现。
由此我们也可以归纳出等价式的定义。
定义1.5 设A和B是两个命题公式，如果A、B在其任意解释下，其真值都是相同的，即A↔B是重言式，则称A和B是等价的，或逻辑相等，记作A⇔B，读作A恒等于B，或A等价于B。
注意符号“⇔”与符号“↔”的意义是有区别的。符号“↔”是逻辑联结词，是个运算符；而符号“⇔”是关系符，A⇔B表示A和B有逻辑等价关系。
常用的逻辑恒等式如表1.7所示。
表中符号P、Q、R代表任意命题，符号T代表真命题，符号F代表假命题。表中所有公式是进行等价变换和逻辑推理的重要依据。表中所有公式均可使用真值表技术得到证明，读者可作为练习。表1.7 常用逻辑恒等式1.3.3 代入规则和替换规则（1）代入规则
在一个重言式中，某个命题变元出现的每一处均代以同一个公式后，所得到的新的公式仍是重言式，这条规则称之为代入规则。
这条规则之所以正确，是因为永真式对任何解释，其值都是真，与所给的某个变元指派的真值是真还是假无关，因此，用一个命题公式代入到原子命题变元R出现的每一处后，所得命题公式的真值还是真。例如：
P∧┓P↔F令以R∧Q代P得，（R∧Q）∧┓(R∧Q)↔F仍是重言式。（2）替换规则
设有恒等式A⇔B若在公式C中出现A的地方替换以B（不一定是每一处都进行）而得到公式D,则C⇔D，这条规则称之为替换规则。
如果A是公式C中完整的部分，且A是合式的公式，则称A是C的子公式。规则中“公式C中出现A”意即“A是C的子公式”。
这条规则之所以正确，是因为在公式C和D中替换部分以外均相同，所以C和D的真值也相同，故C⇔D。
应用代入规则和替换规则及已有的重言式可以证明新的重言式。
例如对公式E12：┓（P∧Q）⇔┓P∨┓Q，我们以A∧B代E12中的P，而以┓A∧┓B代E12中的Q就得出公式┓((A∧B)∧(┓A∧┓B))⇔┓(A∧B)∨┓(┓A∧┓B)
对公式E20：P∧T⇔P，我们利用公式P∨┓P⇔T，对其中的T作替换（对命题常元不能做代换）得公式P∧(P∨┓P)⇔P
…
因此，我们可以说表1.7和表1.9中的字符P、Q和R不仅代表命题变元，而且可以代表命题公式；T和F不仅代表真命题和假命题，而且可以代表重言式和永假式。用这样的观点看待表中的公式，应用就显得更方便。
例1.12（1）试证P→(Q→R)⇔Q→(P→R)⇔┓R→(Q→┓P)
证：P→(Q→R)
⇔┓P∨(┓Q∨R) 两次替换
⇔┓Q∨(┓P∨R) 结合、交换、结合
⇔Q→(P→R) 两次替换
类似可证P→(Q→R)⇔┓R→(Q→┓P)。（2）试证（P→Q）→(Q∨R)⇔P∨Q∨R
证：(P→Q)→(Q∨R)
⇔(┓(┓P∨Q)∨(Q∨R) E27和替换规则
⇔(P∧┓Q)∨(Q∨R) E12和替换规则
⇔((P∧┓Q)∨Q)∨R E4
⇔((P∨Q)∧(Q∨┓Q))∨R
⇔P∨Q∨R 例1.12的（1）和替换规则（3）试将语句“情况并非如此，如果他不来，那么我也不去”化简。
解：设P表示：他来。Q表示：我去。于是上述语句可符号化为：
┓(┓P→┓Q) 对此式化简得
┓(┓P→┓Q)⇔┓(┓┓P∨┓Q)E27和替换规则
⇔┓P∧Q
化简后的语句是“我去了，而他没来”。
从定理及例题可以看到，代入和替换有两点区别：（1）代入是对原子命题变元而言，替换通常是可对命题公式实行；（2）代入必须是处处代入，替换则可部分替换或全部替换。1.4 对偶式与蕴涵式1.4.1 对偶式
定义1.6 设有公式A，其中仅含逻辑联结词┓，∧，∨和逻辑常值T**和F。在A中将∧，∨， T，F分别换以∨，∧，F，T得公式A，则称A*为A的对偶式。同理，A也可称为A的对偶式，即对偶式是相互的。*
定理1.1 设A和A 互为对偶式，P1 ，P2 ，…，Pn 是出现于A和*A 中的所有命题变元，于是：*
┓A（P1，P2，…，Pn）⇔A(P1，P2，…，Pn) （1）*
A（┓P1，┓P2，…，┓Pn）⇔┓A(P1，P2，…，Pn) （2）
证明：由德·摩根律
P∧Q⇔┓(┓P∨┓Q)
P∨Q⇔┓(┓P∧┓Q)*
故┓A(P1，P2，…，Pn）⇔A(P1，P2，…，Pn)
同理：*
┓A(P1，P2，…，Pn)⇔A（┓P1，┓P2，…，┓Pn）
例1.13 证明：（1）┓P∨(Q∧R)和┓P∧（Q∨R）互为对偶式。（2）P∨F和P∧T互为对偶式。
证明：A(P，Q，R)⇔┓P∨（Q∧R）
┓A(P，Q，R)⇔┓(┓P∨(Q∧R))
⇔┓(┓P)∧┓(Q∧R)
⇔┓(┓P)∧(┓Q∨┓R)*
A(P，Q，R)⇔┓P∧(Q∨R)*
A(┓P，┓Q，┓R)⇔┓(┓P)∧(┓Q∨┓R)
所以：*
┓A(P，Q，R)⇔A(┓P，┓Q，┓R)
A(┓P，┓Q，┓R)⇔┓(┓P)∨(┓Q∧┓R)*
┓A(P，Q，R)⇔┓(┓P)∨┓(Q∨R)⇔┓(┓P)∨(┓Q∧┓R)
所以：*
A(┓P，┓Q，┓R)⇔┓A(P，Q，R)
定理1.2 若A⇔B，且A、B为命题变元P1，P2，…，Pn及联结词∧，**∨，┓构成的公式，则A⇔B。
证明：A⇔B意味着：
A(P1，P2，…，Pn）↔B(P1，P2，…，Pn）为永真式，于是
┓A(P1，P2，…，Pn）↔┓B(P1，P2，…，Pn）为永真式，由定理1.1得，**
A(┓P1，┓P2，…，┓Pn）↔B(┓P1，┓P2，…，┓Pn）为永真式。
因为上式是永真式，使用带入规则所得仍为永真式，今以┓Pi代**P（i=1,2,…,n），得A(P1，P2，…，Pn）↔B(P1，P2，…，Pn）为永**真式，所以A⇔B。
本定理称为对偶原理。
例1.14 若(P∧Q)∨(┓P∨(┓P∨Q))⇔┓P∨Q，试证(P∨Q)∧(┓P∧(┓P∧Q)⇔┓P∧Q。
证明：由对偶原理得，*
(P∧Q)∨(┓P∨(┓P∨Q))⇔(┓P∨Q)即(P∨Q)∧(┓P∧(┓P∧Q)⇔┓P∧Q。
定理1.3 如果A⇒ B且A，B为命题变元P1 ，P2 ，…，Pn 及联结**词∧，∨，┓构成的公式，则B⇒A
证明：A⇒B意味着A(P1，P2，…，Pn）→B(P1，P2，…，Pn）为永真式。
由逆反律得，
┓B(P1，P2，…，Pn）→┓A(P1，P2，…，Pn）为永真式。
由定理1.1得，**
B(┓P1，┓P2，…，┓Pn）→A(┓P1，┓P2，…，┓Pn）为永真式。
因为上式是永真式，使用带入规则仍为永真式，今以┓Pi代Pi(i=1，**2，…，n)得B⇒A。1.4.2 蕴涵式
如果单条件联结式A→B是一个永真式，则它被称为永真蕴涵式，记为“A⇒B”,读作“A永真蕴涵B”。其中A称为B的有效前提，B称为A的逻辑结果，可以说由A推出B，也可以说B是由A推出的。从A⇒B的定义不难看出，要证明A永真蕴涵B，只要证明A→B是一个永真式即可。而从A→B的定义不难知道要说明A→B是永真式，只要说明下面两点之一即可。
假定前件A是真，若能推出后件B必为真，则A→B永真，于是A⇒B。
假定后件B是假，若能推出前件A必为假，则A→B永真，于是A⇒B。
也可以用真值表法来证明永真蕴涵式。即证明对于命题公式中命题变元的所有真值指派来说，若其中使逻辑前提取值为真的那些真值指派，也必然使逻辑结果取值为真，则说A⇒B。
例1.15 证明┓Q∧(P→Q)⇒┓P。
证明：方法一，
设┓Q∧(P→Q)为真，于是┓Q，P→Q均为真，从而得出Q为假，因而┓P是真。
所以┓Q∧(P→Q)⇒┓P。
方法二，
设┓P是假，于是P为真，这时不论Q是真是假都使┓Q∧（P→Q）为假。于是
┓Q∧(P→Q)⇒┓P。
方法三，
使用真值表技术，构造前提和结论的真值表如表1.8所示。表1.8 例1.15的方法三
从真值表可以看出，使┓Q∧(P→Q)取T值的那些变元的真值指派，也使┓P取T值；而使┓P取F值的那些变元的真值指派，也使┓Q∧（P→Q）取F值，因此，┓Q∧(P→Q)→┓P。
常用的永真蕴涵式如表1.9所示。表1.9 常用永真蕴涵式1.5 范式和判定问题
前面我们曾提及过在有限步内确定一个合式公式是永真的、永假的或是可满足的，这类问题称为命题公式的判定问题。
在前面的介绍中，我们已看到，由于合式公式的形式不唯一，给判定工作带来一定难度，虽然使用真值表技术可以解决命题公式的判定问题，但是，当命题变元数目多时，使用真值表技术也不是很方便。所以必须通过其它的途径来解决判定问题——这就是把合式公式化为标准型（范式）。1.5.1 析取范式和合取范式
为叙述方便，我们把合取称为积，把析取称为和。
定义1.7 命题公式中的一些变元和一些变元的否定之积，称为基本积；一些变元和变元的否定之和，称为基本和。
例如，给定命题变元P和Q，则：
P，Q，┓P，┓Q，┓P∧Q，P∧Q，┓P∧P，┓Q∧P∧Q都是基本积。P，Q，┓P，┓Q， P∨┓Q，P∨Q，P∨┓P，P∨Q∨┓P都是基本和。
基本积（和）中的子公式称为基本积（和）的因子。
定理1.4 一个基本积是永假式，当且仅当它含有P，┓P形式的两个因子。
证明：（充分性）P∧┓P是永假式，而Q∧F两个因子时，此基本积是永假式，所以含有P和┓P形式的两个因子的基本积是永假式。（必要性）用反证法。设基本积永假但不含P和┓P形式的因子，于是给这个基本积中的命题变元指派真值T，给带有否定的命题变元指派真值F，得基本积的真值是T，与假设矛盾。证毕。
定理1.5 一个基本和是永真式，当且仅当它含有P，┓P形式的两个因子。
证明留给读者作为练习。
定义1.8 一个由基本积的和组成的公式，如果与给定的公式 A 等价，则称它是 A 的析取范式，记为：A＝A1 ∨A2 ∨…∨An ，n≥1，其中Ai (i＝1，2，…，n)是基本积。
对于任何命题公式，都可求得与其等价的析取范式，这是因为命题公式中出现的→和↔可用∧、∨和┓表达，括号可通过德·摩根定律和∧对∨的分配律消去。但是一个命题公式的析取范式不是唯一的。
如果析取范式中每个基本积都是永假式，则该范式必定是永假式。
例1.16（1）求(P∧(Q→R)) →S的析取范式。
解：(P∧(Q→R))→S⇔┓(P∧(┓Q∨R))∨S
⇔(┓P∨(Q∧┓R))∨S
⇔┓P∨(Q∧┓R)∨S析取范式（2）求┓(P∨Q) ↔ (P∧Q)的析取范式。
解：┓(P∨Q) ↔ (P∧Q)
⇔┓(P∨Q)∧(P∧Q)∨┓(┓(P∨Q))∧┓(P∧Q)
⇔(┓P∧┓Q∧P∧Q)∨((P∨Q)∧(┓P∨┓Q))
⇔F∨(P∨Q)∧(┓P∨┓Q)
⇔(P∨Q)∧(┓P∨┓Q)
⇔((P∨Q)∧┓P)∨((P∨Q)∧┓Q)
⇔P∧┓P∨┓P∧Q∨P∧┓Q∨Q∧┓Q
⇔F∨┓P∧Q∨P∧┓Q∨F⇔(┓P∧Q)∨(P∧┓Q)
定义1.9 一个由基本和的积组成的公式，如果与给定的命题公式 A 等价，则称它是 A 的合取范式，记为：A＝A1 ∧A2 ∧…∧An ，n≥1，其中A1 ，A2 ，…，An ，是基本和。
对任何命题公式都可求得与其等价的合取范式，道理同析取范式。同样，一个命题公式的合取范式也不唯一。
如果一个命题公式的合取范式的每个基本和都是永真式，则该式也必定是永真式。
例1.17（1）试证Q∨P∧┓Q∨┓P∧┓Q是永真式。
解：Q∨P∧┓Q∨┓P∧┓Q
⇔Q∨(P∨┓P)∧┓Q
⇔Q∨T∧┓Q
⇔Q∨┓Q
⇔T（2）求┓(P∨Q) →(P∧Q)的合取范式。
解：令A⇔┓(P∨Q)→(P∧Q)，则
┓A⇔┓(┓(P∨Q)∨(P∧Q))
⇔┓((┓(P∨Q)∧(P∧Q))∨(┓(┓(P∨Q)∧┓(P∧Q)))
⇔┓((┓P∧┓Q∧P∧Q)∨((P∨Q)∧(┓P∨┓Q)))
⇔(┓P∧┓Q)∨(P∧Q)
由于A⇔┓┓A＝┓(┓P∧┓Q∨P∧Q)
所以A⇔(P∨Q)∧(┓P∨┓Q)。1.5.2 主析取范式和主合取范式
定义1.10 在含n个变元的基本积中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本积为极小项。n
n个变元可构成2个不同的极小项。例如3个变元P、Q，R可构成8个极小项。我们把命题变元看成1，命题变元的否定看成0，于是每个极小项对应于一个二进制数，也对应一个十进制数。对应情况如下。
┓P∧┓Q∧┓R ——000——0
┓P∧┓Q∧R ——001——l
┓P∧Q∧┓R ——010——2
┓P∧Q∧R ——011——3
P∧┓Q∧┓R ——100——4
P∧┓Q∧R ——101——5
P∧Q∧┓R ——110——6
P∧Q∧R ——111——7
把极小项对应的十进制数当作足标，并用mi(i=0，1，2，…，n2-1)表示这一项，即：
┓P∧┓Q∧┓R ＝m0
┓P∧┓Q∧R ＝m1
┓P∧Q∧┓R ＝m2
┓P∧Q∧R ＝m3
P∧┓Q∧┓R ＝m4
P∧┓Q∧R ＝m5
P∧Q∧┓R ＝m6
P∧Q∧R ＝m7
一般，n个变元的极小项是：
┓P1∧┓P2∧…∧┓Pn ＝m0
┓P1 ∧┓P2 ∧…∧┓Pn-1 ∧Pn ＝m1
┓P1 ∧┓P2 ∧…∧Pn-1 ∧┓Pn ＝m2
…
定义1.11 一个由极小项的和组成的公式，如果与命题公式A等价，则称它是公式A的主析取范式。
对任何命题公式(永假式除外)都可求得与其等价的主析取范式，而且主析取范式的形式唯一。它给范式判定问题带来很大益处。例如：
A⇔P∧Q∨R
⇔(P∧Q)∧(R∨┓R)∨(P∨┓P)∧R
⇔P∧Q∧R∨P∧Q∧┓R∨P∧R∨┓P∧R
⇔P∧Q∧R∨P∧Q∧┓R∨P∧R∧(Q∨┓Q)∨(┓P∧R)∧(Q∨┓Q)
⇔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∧R∨┓P∧Q∧R∨┓P∧┓Q∧R
⇔m7∨m6∨m5∨m3∨m1
⇔∑(1，3，5，6，7)
其中，符号“∑”是借用数学中求和的符号，这里代表析取。
命题公式A不是永真式也不是永假式，而是可满足的。关于这一点将通过考察一个命题公式的主析取范式和它的真值表的关系而得出。
下面我们来研究命题公式A=P∧Q∨R的真值表。表1.10 A=P∧Q∨R的真值表及对应的极小项
从公式 P∧Q∨R 的真值表中不难看出，使命题公式取值为 T 的每一组变元的真值指派也使同行上的极小项取值为T。如果我们把这些极小项析取起来显然它应该和命题公式P∧Q∨R是等价的。当然使命题公式取值为F的那些组命题变元所对应的极小项对公式是不起作用的。
如果命题公式是永真式，则对应于命题变元的所有极小项应在其主析取范式中全部出现。
如果所给命题公式是永假式，则它不存在主析取范式。
定义1.12 在含n个变元的基本和中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本和为极大项。n
n个变元可以构成2个不同的极大项。例如三个变元P，Q，R可构成八个极大项。在极大项中，我们把命题变元看成0,而把命题变元的否定看成1，于是每一个极大项对应于一个二进制数，也对应一个十进制数。对应情况如下。
P∨Q∨R --000—0
P∨Q∨┓R --001—1
P∨┓Q∨R --010—2
P∨┓Q∨┓R --011—3
┓P∨Q∨R --100—4
┓P∨Q∨┓R --101—5
┓P∨┓Q∨R --110—6
┓P∨┓Q∨┓R --111—7
把极大项对应的十进制数当作足标，并用Mi(i=0，1，2，…，n2-1)表示这一项，即：
P∨Q∨R ＝M0
P∨Q∨┓R ＝M1
P∨┓Q∨R ＝M2
P∨┓Q∨┓R ＝M3
┓P∨Q∨R ＝M4
┓P∨Q∨┓R ＝M5
┓P∨┓Q∨R ＝M6
┓P∨┓Q∨┓R ＝M7
一般n个变元的极大项是：
P1∨P2∨…∨Pn ＝M0
P1∨P2∨…∨Pn-1∨Pn ＝M1
P1∨P2∨…∨Pn-1∨Pn ＝M2
…
定义1.13 一个由极大项的积组成的公式，如果与命题公式A等价，则称它是A的主合取范式。
对任何命题公式(永真式除外)都可求得与其等价的主合取范式，且主合取范式的形式唯一。例如：
其中，符号“∏”是借用数学中求积的符号，这里代表合取。从A的主合取范式，我们立刻可以判断出A是可满足的。下面我们通过考察A＝P∧Q∨R及其真值表来说明极大项和主合取范式的关系及极大项和极小项的关系。表1.11 A=P∧Q∨R的真值表及对应的极大项
从表1.11中可以清楚地看出，使公式A取F（即0）的那些真值指派也必然使同行上对应的极大项取F值，把所有这些极大项合取起来当然应和命题公式A等价，省略使命题公式A取T（即1）值的极大项是因为合取上T还等价于原来的命题。
对照表1.10和表1.11我们会发现极小项mi和极大项Mi有下列的关系式：
Mi＝┓mi，mi＝┓Mi
利用求一个命题公式的主析取范式和主合取范式的方法，可以很快地判断一个命题公式是永真的、永假的或是可满足的。一个命题公式是永真式，它的命题变元的所有极小项均出现在其主析取范式中，不存在与其等价的主合取范式；一个命题公式是永假式，它的命题变元的所有极大项均出现在其主合取范式中，不存在与其等价的主析取范式；一个命题公式是可满足的，它既有与其等价的主析取范式，也有与其等价的主合取范式。通过对公式A＝P∧Q∨R的讨论，我们不难看出通过公式直接求主析取、主合取范式的方法。从真值表中我们n也可以看出，如果一个命题公式含有n个变元，则可以写出2个极小n项和2个极大项，并且如果这个命题公式的主析取范式含有i(i 逻辑学的主要任务是提供一套推论规则，按照公认的推论规则，从前提集合中推导出一个结论来，这样的推导过程称为演绎或形式证明。 在任何论证中，倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推论规则，则认为此结论是真的，并且认为这个论证过程是合法的。也就是说，对于任何论证来说，人们所注意的是论证的合法性。数理逻辑则把注意力集中于推论规则的研究，依据这些推论规则推导出的任何结论，称为有效结论，而这种论证规则被称为有效论证。数理逻辑所关心的是论证的有效性而不是合法性，也就是说数理逻辑所注重的是推论过程中推论规则使用的有效，而并不关心前提的实际真值。 推论理论对计算机科学中的程序验证、定理的机械证明和人工智能都十分重要。 定义1.14 设H1，H2,…,Hm,C是一些命题公式。当且仅当H1∧H2∧…∧Hm⇒C，则说C是前提集合{H1，H2，…，Hm}的有效结论。 显然，给定一个前提集合和一个结论，用构成真值表的方法，在有限步内能够确定该结论是否是该前提集合的有效结论。这种方法被称为真值表技术。下面举例说明这种技术。 例1.18 考察结论C是否是下列前提H1 ，H2 和H3 的有效结论。（1）H1：﹁P∨Q H2：﹁(Q∧﹁R) H3：﹁R C：﹁P（2）H1：P→(Q→R) H2：P∧Q C：R（3）H1：﹁P H2：P∨Q C：P∧Q 解：我们首先构造（1）、（2）和（3）的真值表，如表1.12、表1.13和表1.14所示。表1.12续表 在表1.11中仅第一行各前提的真值都为1，结论也有真值1，因此（1）的结论是有效的。表1.13 在表1.12中仅第八行上各前提的真值都为1，结论也有真值1，因此（2）的结论也是有效的。表1.14 在表1.13中，使前提取值均为1的是第二行，但结论却取值为0，因此，（3）的结论无效。 使用真值表技术可以证明某一个结论是否是某一组前提的有效结论，如上面所举的例子。但是，当变元多或前提规模大时，这种方法就显得不是很方便了。为此，我们介绍一套推论理论的推论规则，如果推论规则使用的有效，则说由这套推论规则所推出的结论也是有效的。 规则P：引入一个前提称为使用一次P规则。 规则T：在推导中，如果前面有一个或多个公式永真蕴涵公式S，则可以把公式S引进推导过程中。换句话说，引进前面推导过程中的推论结果称为使用T规则。 规则CP：如果能从R和前提集合中推导出S来，则就能够从前提集合中推导出R→S。实际上恒等式E28就可以推出规则CP。 (P∧Q→R)⇔﹁(P∧Q)∨R ⇔﹁P∨﹁Q∨R ⇔﹁P∨(﹁Q∨R) ⇔﹁P∨(Q→R) ⇔P→(Q→R) 设P表示前提的合取，Q是任意公式，则上述恒等式可表述成：在前提集合中若包含有附加前提Q，并且从P∧Q中可以推导出R来，则可从前提P中推导出Q→R来。 下面举例说明如何使用以上规则进行有效推论。 例1.19 试证明﹁P是﹁(P∧﹁Q)，﹁Q∨R，﹁R的有效结论。 解： {1} (1) ﹁(P∧﹁Q) P规则 {1} (2) ﹁P∨Q T规则 (1)和E11 {1} (3) P→Q T规则(2)和E27 {4} (4) ﹁Q∨R P规则 {4} (5) Q→R T规则 (4)和E27 {1,4 } (6) P→R T, (3) , (5)和 I12 {7} (7) ﹁R P规则 {1,4,7} (8) ﹁P T规则(6) ,(7)和 I11 … 其中，第一列上花括号中的数字集合，指明了本行上的公式所依赖的前提。第二列中的编号既代表了该公式又代表了该公式所处的行。最右边给出的是推论规则和注释，注释包括本行是哪行的结论及所依据的恒等式和永真蕴涵式。 例1.20 证明R→S是前提P→(Q→S)，Q和﹁R∨P的有效结论。 解：把R作为附加前提，首先推导出S来，再由此推导出R→S来。 {1} (1) R P规则（附加前提） {2} (2) ﹁R∨P P规则 {1,2} (3) P T规则 (1) , (2) ,和 I9 {4} (4) P→(Q→S) P规则 {1,2,4} (5) Q→S T规则(3) , (4)和 I10 {6} (6) Q P规则 {1,2,4,6} (7) S T规则，(5), (6)和 I10 {1,2,4,6} (8) R→S CP规则 (1) , (7) … 前面我们曾讨论过范式判定问题。显然，如果在有限步内能断定论证是否有效，也就解决了论证的判定问题。然而，前面讨论过的推导方法，实际上仅是部分地解决了判定问题的求解。也就是说，如果一个论证是有效的，则使用这种方法可以证明论证是有效的；反之，如果论证不是有效的，则经过有限步之后，还难于断定这个论证不是有效的。 下面介绍第四个推论规则。 规则F，也称间接证明法(或反证法)。为了说明规则F，我们给出下面的定义和定理。 定义1.15 设公式H1 ，H2 ，…，Hm 中的原子变元是P1 ，P2 ，…，Pn 。 如果给各原子变元P1，P2，…，Pn指派某一个真值集合，能使H1∧H2∧…∧Hm具有真值T，则命题公式集合{ H1 ，H2 ，…，Hm }称为一致的(或相容的)；对于各原子变元的每一个真值指派，如果命题公式H1 ，H2 ，…，Hm 中至少有一个是假，从而使得H1 ∧H2 ∧…∧Hm 是假，则称命题公式集合{H1 ，H2 ，…，Hm }是不一致的(或不相容的)。 设{H1 ，H2 ，…，Hm }是一个命题公式集合，如果它们的合取蕴涵着一个永假式，也就是说H1 ∧H2 ∧…∧Hm ⇒ R∧﹁R。 这里R是任何一个公式，则公式集合{ H1 ，H2 ，…，Hm }必然是非一致的。因为R∧﹁R是一个永假式，所以它充分而又必要地决定了H1∧H2∧…∧Hm是一个永假式。 在间接证明法中，就是应用了非一致的概念。 定理1.6 设命题公式集合{ H1 ，H2 ，…，Hm ，﹁C}是非一致的，亦即它蕴涵着一个永假式，则可以从前提集合{ H1 ，H2 ,…, Hm }中推导出命题公式C来。 证明：因为H1∧H2∧…∧Hm∧﹁C⇒R∧﹁R，所以H1∧H2∧…∧﹁C必定是永假式。因为前提集合{ H1 ，H2 ,…, Hm }是一致的，所以能使H1 ∧H2 ∧…∧Hm 的真值为T的真值指派，必然会使﹁C的真值为F，从而使C的真值为T，故有： H1，H2，…，Hm⇒C 这样就可以从前提集合{ H1 ，H2 ,…, Hm }中推导出命题公式C来。 例1.21 证明﹁(P∧Q)是﹁P∧﹁Q的有效结论。 解：把﹁﹁(P∧Q)作为假设前提，并证明该假设前提导致一个永假式。 {1} (1) ﹁﹁(P∧Q) P规则（假设前提） {2} (2) P∧Q T规则(1)和E10 {1} (3) P T规则, (2) ,和 I1 {4} (4) ﹁P∧﹁Q P规则 {4} (5) ﹁P T规则, (4)和 I1 {1,4} (6) P∧﹁P T规则(3) , (5)和 I16 {1,4} (7) ﹁(P∧Q) F规则(1), (6) 由以上几个例子，我们可以总结出这样的经验：当要证明的结论是条件式时，可考虑使用CP规则；当要证明的结论比较简单，而仅仅使用前提推导不明显时，可考虑使用间接证明法即F规则，以使推导过程变得简洁。习题 1.下面哪些是命题？（1）2是整数吗？（2）研究逻辑。2（3）x+x+1=0。（4）一月份将会下雪。（5）如果股市下跌，我将会赔钱。 2.给出下列命题的否定命题。（1）大连的每条街道都临海。（2）2是一个偶数和8是一个奇数。（3）2是偶数或-3是负数。 3.给定命题P→Q，我们把Q→P，┓P→┓Q,┓Q→┓P分别叫作命题P→Q的逆命题，反命题，逆反命题。 给出下列命题的逆命题、反命题和逆反命题。（1）如果天不下雨，我将去公园。（2）仅当你去我才逗留。nnn（3）如果n是大于2的正整数，那么方程x+y=z无整数解。（4）如果我不获得更多的帮助，则我不能完成这项任务。 4.给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值。（1）┓(P∧Q∨┓R)∨((Q∨┓P)→(R∨┓S))（2）Q∧(P→Q)→P（3）(P∨(Q→(R∧┓P)))↔(Q∨┓S)（4）(P→R)∧(┓P→S) 5.构成下列公式的真值表。（1）P→(Q∨R)（2）Q∧(P→Q)→P（3）(P∨Q→Q∧P)→P∧┓R（4）((┓P→P∧┓Q→R)→R)∧Q∨┓R 6.符号化以下命题。（1）他既聪明又用功。（2）除非天气好，我才骑自行车上班。（3）老李或者小李是球迷。（4）只有休息好，才能身体好。 7.使用真值表证明如果P↔Q为T，那么P→Q和Q→P都为T，反之亦然。 8.设*是具有两个运算对象的逻辑运算符，如果(x*y)*z和x*(y*z)逻辑等价，那么运算符*是可结合的。（1）确定逻辑运算符∧，∨，→，↔哪些可是可结合的？（2）用真值表证明你的判断。 9.令P表示命题“苹果是甜的”，Q表示命题“苹果是红的”，R表示命题“我买苹果”。 试将下列命题符号化。（1）如果苹果甜而红，那么我买苹果。（2）苹果是酸的。（3）我没买苹果，因为苹果不红也不甜。 10.指出下列命题公式哪些是重言式、永假式或可满足的。（1）P∨┓P（2）P∧┓P（3）P→┓(┓P)（4）┓(P∧Q)↔(┓P∨┓Q)（5）┓(P∨Q)↔(┓P∧┓Q)（6）(P→Q)↔(┓Q→┓P)（7）((P→Q)∧(Q→P))↔(P↔Q)（8）P∧(Q∨R)→(P∧Q∨P∧R)（9）P∧┓P→Q（10）((P→Q)∨(R→S))→((P∨R)→(Q∨S)) 11.写出与下面给出的公式等价并且仅含联结词∧及┓的最简公式。（1）┓(P↔(Q→(R∨P)))（2）((P∨Q)∧R)→(P∨R)（3）P∨Q∨┓R（4）P∨(┓Q∧R→P)（5）P→(Q→P) 12.写出与下面的公式等价并且仅含联结词∨及┓的最简公式。（1）(P∧Q)∧┓P（2）(P→(Q∨┓Q))∧┓P∧Q（3）┓P∧┓Q∧(┓R→P) 13.使用常用恒等式证明下述各式，并给出下述各式的对偶式。（1）┓(┓P∨┓Q)∨┓(┓P∨Q)⇔P（2）(P∨┓Q)∧(P∨Q)∧(┓P∨┓Q)⇔┓(┓P∨Q)（3）Q∨┓((┓P∨Q)∧Q)⇔T 14.试证明下述公式是永真式。（1）(P∧（P→Q）) →Q（2）┓P→（P→Q）（3）（（P→Q）∧（Q→R））→（P→R）（4）（P →（Q→R））→（（P→Q）→（P→R）） 15.不构造真值表证明下列蕴涵式。（1）P∧Q⇒P→Q（2）P→(Q→R)⇒(P→Q)→(P→R)（3）P→Q⇒P→P∧Q（4）(P→Q)→Q⇒P∨Q（5）(P∨┓P→Q)→(P∨┓P→R)⇒Q→R（6）(Q→P∧┓P)→(R→P∧┓P)⇒R→Q 16.求出下列各式的代入实例。（1）(((P→Q)→P)→P)；用P→Q代P，用((P→Q)→R)代Q。（2）((P→Q)→(Q→P))；用Q代P，用┓P代Q。 17.求下列各式的主合取范式和合取范式。（1）(┓P∨┓Q)→(P∧┓Q)（2）(P∧Q)∨(┓P∧Q)∨(P∧┓Q)（3）(P→(Q∧R))∧(┓P→(┓Q∧┓R))（4）(P∧┓Q∧S)∨(┓P∧Q∧R) 18.试采用将公式化为主范式的方法，证明下列各等价式。（1）(┓P∨Q)∧(P→R)⇔P→(Q∧R)（2）(P∧Q)∧(P→┓Q)⇔(┓P∧┓Q)∧(P∨Q)（3）(P→Q)→(P∧Q)⇔(┓P→Q)∧(P∨┓Q)（4）P∨(P→(P∨Q))⇔┓P∨┓Q∨(P∧Q) 19.试用真值表法证明A∧E不是A↔B，B↔(C∧D)，C↔(A∨E)和A∨E的有效结论。 20.H1，H2和H3是前提。在下列情况下，试确定结论C是否有效（可以使用真值表法证明）。（1）H1 : P→Q C: P→(P∧Q)（2）H1 :﹁P∨Q H2 :﹁(Q∧﹁R) H3 :﹁R C:﹁P（3）H1 : P→(Q→R) H2 : P∧Q C: R（4）H1 : P→Q H2 : Q→R C: P→R 21.不构成真值表证明下列命题公式不能同时全是真的。（1）P↔Q,Q→R,﹁R∨S,﹁P→S,﹁S（2）R∨M, ﹁P∨S, ﹁M, ﹁S 22.足坛四支劲旅举行友谊比赛。已知情况如下，请问结论是否成立？（1）若大连阿尔滨队获得冠军，则北京国安队或上海申花队获得亚军。（2）若上海申花队获得亚军，则大连阿尔滨队不能获得冠军。（3）若广州恒大队获得亚军，则北京国安队不能获得亚军。
试读结束[说明：试读内容隐藏了图片]