中财网峻青的《秋色赋》:命题逻辑
来源：百度文库 编辑：中财网 时间：2024/05/05 20:02:15
形式逻辑是以思维形式结构及其规律进行研究的一门工具性学科。
思维的形式结构包括概念、判断和推理。其中，概念是思维的基本单位；判断是通过概念对事物是否具有某种属性进行肯定或否定的回答；由一个或者几个判断推出另一个判断的思维过程就是推理。研究推理有很多方法，其中用数学方法来研究推理的规律的学科统称为数理逻辑，这里所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑也叫符号逻辑。
我们主要介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑，首先介绍命题逻辑。
1.1 命题与命题联结词
1.1.1 命题
凡具有真假的陈述句就称为命题(Proposition)。命题通常用小写英文字母表示。
例如，“2是素数”是命题，可用符号表示为 p：2是素数。
例1.1-1 ⑴3能被2整除。
⑵C++是一门计算机高级程序语言。
⑶请关上门!
⑷你好吗？
⑸ 。
⑹“本语句是假的”。
其中⑴是命题，对它进行判断的结果是真的；⑵是命题，是假的；⑶、⑷不是陈述句，故不是命题；⑸是陈述句，但由于x、y不确定，使得整个句子可真可假，即没有确定的判断结果，故不是命题；⑹是一个悖论，无法确定其真假，所以不是命题。
作为命题的陈述句所表达的判断结果称为该命题的真值(Truth Value)。一个命题的真值为“真”，用“1”或“T”表示，此时称该命题为真命题(True Proposition)；一个命题的真值为“假”，用“0”或“F”表示，此时称该命题为假命题(False Proposition)。
例如，在例1.1-1中，⑴的真值为假，故为假命题；⑵的真值为真，所以是真命题。
例1.1-2 ⑴这盘菜太咸。
⑵太阳系外有宇宙人。
⑶1962年2月3日晚郑州市金水区成立。
注意 要把“已知其真假”与“本身具有真假”区别开来。在判断一个陈述句是否是命题时必须明确，只要能分辨出真假的语句就是命题。
⑴是命题。虽然语句表达的判断结果似乎不唯一，但实际上其真假是唯一确定的。我们可以认为其真假取决于说话人的主观判断，可理解为“我认为这盘菜太咸”。
⑵是命题。虽然目前尚无法确定其真假，但从事物的本质而论，是可分辨真假的。
⑶是命题。虽然一时难辨其真假，但其本身是有真假的，若能查到相关资料，结果自然就明了了。
容易看出，例1.1-1、例1.1-2中给出的是命题的陈述句都不能进一步分解，类似这种不能再分的命题，称为原子命题(Atomic Proposition)或简单命题，原子命题是命题逻辑中最基本、最小的单位。由作为原子命题的简单陈述句通过连词联结而成的命题，称为复合命题(Compoud Proposition)。
例1.1-3 ⑴林刚和林强是三好学生。
⑵离散数学是计算机专业的一门基础课.
⑶如果3+2<4，那么太阳早上将由西边出来。
其中⑴、⑶是复合命题，⑵是原子命题。判断一个命题是否是复合命题的关键是看分解后各部分是否仍为命题。特别指出，有些在表面上互不相干的命题语句通过连词可组成复合命题，如本例中的⑶。
1.1.2 命题联结词
复合命题是用自然语言中的连词联结命题所组成的，为了便于研究，我们还需要对自然语言中的各种连词也用符号表示出来，以便得到形式化了的复合命题。在数理逻辑中，我们将这种自然语言连词的形式符号称为命题逻辑联结词(Logical Connective)。
⑴否定(Negation)
定义1.1-1 设p是命题，“非 p”称为 p的否定式，记作 ，称符号 为否定联结词。并规定， 为真当且仅当p为假。
例如，设p表示“3是偶数”，则p的否定，即“3不是偶数”可用符号表示为： 。由于p的真值为0，所以 真值为1。
为了更好地理解联结词所代表的含义，引入一种表格方法─真值表(Truth Table)。
如表1.1-1所示就是否定联结词的真值表。
表1.1-1中的“1”、“0”分别表示标记在该列顶端的命题取值为真或假。
表1.1-1
p
0
1
1
0
⑵合取 (Conjunction)
定义1.1-2 设p、q都是命题，复合命题“p并且q”称为p与q的合取式，记作 ，称符号 为合取联结词。并规定， 为真当且仅当p与q同时为真。
合取联结词的真值表如表1.1-2所示。
例如，设p表示“2是素数”，q表示“2是偶数”。
则“2是素数并且是偶数”可用符号表示为： 。由于p、q真值均为1，故 真值为1。
⑶析取 (Disjunction)
定义1.1-3 设p、q都是命题，复合命题“p或者q”称为p与q的析取式，记作 ，称符号 为析取联结词。并规定， 为真当且仅当p与q中至少有一个为真。
析取联结词的真值表如表1.1-3所示。
例如，设p表示“王燕学过英语”；q表示“王燕学过法语”。则“王燕学过英语或法语”可用符号表示为： 。
表1.1-2
表1.1-3
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
0
1
1
1
⑷ 蕴涵(含)（Implication）
定义1.1-4 设p、q都是命题，复合命题“如果p，那么q”称为p与q的蕴含式，记作： ，其中p称为其前件，q称为其后件，称符号 为蕴含联结词。并规定， 为假当且仅当p为真且q为假。
蕴含联结词的真值表如表1.1-4所示。
例如，设p表示“我是老师”；q表示“我年龄大了”。则“如果我是老师，那么我年龄大了”可用符号表示为： 。若我是一名年轻教师，则此时p为真，q为假，故 为假。
表1.1-4
表1.1-5
0
0
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
⑸ 等价(Equivalent)
定义1.1-5 设p、q都是命题，复合命题“p当且仅当q”称作p与q的等价式，记作： ，称符号 为等价联结词。并规定， 为真当且仅当p、q真值相同。
等价联结词的真值表如表1.1-5所示。
例如，设p表示“两圆的面积相等”；q表示“两圆的半径相等”。则“两圆的面积相等当且仅当其半径相等”可用符号化表示为： 。
为了叙述方便，我们将用符号表示命题及其联结词的过程称为命题的符号化(Proporsitional signify)。
对于命题的符号化我们有必要指出以下几点：
⒈ 同一个命题联结词在自然语言中可能有不同的表达方法。
例1.1-4 将下列命题符号化。
⑴ 离散数学并非难学的一门课程。
⑵ 明天我可能看电影也可能逛公园。
⑶ 尽管他有病但他仍坚持工作。
⑷ 倘若他病了他就不参加这次会议。
⑸ 一个数是偶数的充要条件是该数能被2整除。
解 ⑴设p：离散数学是难学的一门课程。则命题符号化为 。其中“…并非…”逻辑含义上表示否定。
⑵设p：明天我看电影；q：明天我逛公园。则命题符号化为 。其中“…可能…也可能…”在逻辑上具有析取的含义。
⑶设p：他有病；q：他坚持工作。则命题符号化为 。其中“尽管…但…”具有合取的逻辑含义。
⑷设p：他病了；q：他不参加这次会议。则命题符号化为 。其中“倘若…就…”与逻辑上的蕴涵具有相同的含义。
⑸设p：一个数是偶数；q：一个数能被2整除。则命题符号化为 。其中“…的充要条件是…”在逻辑上表示等价的含义。
⒉ 两个逻辑上完全没有联系的命题可以加以联结词形成复合命题。
例1.1-5 ⑴p：2+3=5；q：有的人可以长生不老。则 仍是一个命题，它表示的含义是：“2+3=5”并且有的人可以长生不老。虽然p是真命题，但显然q的真值为假，所以根据合取联结词的定义 是一个假命题。
⑵在例1.1-3⑶中，令r表示“3+2<4”，s表示“早上太阳将从西边出来”，则该语句符号化为： 。由于r真值为假，所以整个命题的真值为真。
⒊ 自然语言中的“或”应注意加以区别。自然语言中的“或”有“可兼或”和“不可兼或”之分，前者在逻辑上就是析取，后者可转换后符号化。
例1.1-6 符号化下列命题。
⑴今天打雷或下雨。
⑵他明天到北京或到广州。
解 设p：今天打雷；q：今天下雨；r：他明天到北京； s：他明天到广州。
⑴中的“或”是“可兼或”，也就是说可以打雷，也可以下雨，还可以既打雷又下雨，所以命题符号化为： ；
⑵中的“或”是“不可兼或”，因为他只能到一个地方，所以不能用逻辑联结词 来符号化它，我们可以转换为“他明天到北京且不到广州或者他明天到广州且不到北京”来符号化：
⒋ 对蕴含要注意区分前件与后件。
例1.1-7 符号化下列命题。
⑴只要天下雨，我就坐公共汽车上班。
⑵只有天下雨，我才坐公共汽车上班。
⑶我是坐公共汽车上班的，因为天下雨了。
解 设p：天下雨； q：我坐公共汽车上班。
则⑴符号化为： ，因为p是q的充分条件；
⑵符号化为： ，因为p是q的必要条件；
⑶符号化为： ，原因同⑵。
⒌ 在符号化命题时，需要注意复合命题和原子命题的区别。
例1.1-8符号化下列命题。
⑴张刚和张强都是三好学生。
⑵张刚和张强是同桌。
解 ⑴是应用合取联结词联结“张刚是三好学生”和“张强是三好学生”组成的复合命题，若设p：张刚是三好学生；q：张强是三好学生；则可符号化为： 。
⑵仅是原子命题，“和”在这里连接的是“张刚”和“张强”，因为若对语句进一步分解，“张刚是同桌”、“张强是同桌”都不再是命题，故可符号化为r。
⒍ 逻辑联结词也称为逻辑运算符，可以规定相应的运算次序。
规定逻辑联结词的优先级从高到低依次为： ， ， ， ， ，并可以用“（ ）”来改变运算的优先次序。求复合命题的真值时，先运算括号内的部分，没有括号限制的按优先级从高到低的顺序运算。对于同一优先级或同一个联结词，按从左到右的顺序运算。
例1.1-9 符号化下列命题，并按照逻辑运算顺序求其真值。
⑴如果飞机速度没有汽车快，并且在二进制数运算中01+10=11，那么地球是静止的或者人是可以长生不老的。
⑵如果人可以长生不老或者在二进制数运算中01+10=11，那么汽车比飞机速度快或者地球是静止的。
解 设p：飞机比汽车速度快；q：在二进制数运算中01+10=11；r：地球是静止的；
s：人可以长生不老。
则⑴符号化为： 。因为p、q真值为1，所以 真值为0， 真值为0，故其真值为1。⑵可符号化为： 。因为p、q真值为1，r、s真值为0，所以 真值为1， 真值为0， 真值为0，故其真值为0。
习题1.1
1.1-1.判断下列语句是否是命题,为什么?若是命题请说明是真命题还是假命题?
⑴a+b。
⑵x>0。
⑶你说什么？
⑷今天天气多好呀！
⑸我明天或者后天去郑州。
⑹我明天去郑州或后天去郑州是谣传。
⑺一个整数为偶数当且仅当它能被2整除。
⑻这个命题是假的。
⑼太阳是不会发光的。
1.1-2.判断下列语句是否是命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。
⑴他们明天或者后天去百货公司。
⑵你能告诉我我什么时候一定会死吗？你不能！
⑶如果这个语句是命题，那么它就是个假命题。
⑷李刚和李春是兄弟。
⑸王海和李春在学习。
⑹只要努力学习，就一定能取得优异成绩。
⑺李春对李刚说：“今天天气真好呀！”
⑻如果你想中奖，你就得买奖券；如果你买奖券，你就可能中奖。
⑼你知道这个是真命题还是假命题就请告诉我！
⑽王海不是女孩子。
1.1-3.设p表示命题“李春迟到了”，q表示命题“李春错过了考试”，r表示命题“李春通过了考试”。请将下列命题翻译成自然语言（汉语）。
⑴ ；⑵ ；⑶ ；⑷ 。
1.1-4.设p表示命题“天下大雨”，q表示命题“他乘公共汽车上班”，r表示命题“他骑自行车上班”。请将下列命题符号化。
⑴如果天不下大雨，他乘公共汽车上班或者骑自行车上班。
⑵只要天下大雨，他就乘公共汽车上班。
⑶只有天下大雨，他才乘公共汽车上班。
⑷除非天下大雨，否则他不乘公共汽车上班。
1.2 命题公式及其分类
1.2.1 命题公式
在上一节例1.1-1中，已经看到⑸“ ”是陈述句，但由于x、y不确定，使得整个语句没有确定的真值，故不是命题。但是，若给定x、y一组确定的值，其真假值也就确定了。
我们把这种本身并非原子命题，但给其赋予一定的具体内容后便可成为原子命题的陈述句称为命题变元(Propositional Variable)，命题变元与初等数学里的变量类似，不过命题变元只能取值1（真）或0（假）。而原子命题则相应地称为命题常元(Propositional Constant)。命题常元和命题变元我们都用小写英文字母p,q,r,…表示，在必要的时候我们可以根据上下文加以判断。
在符号形式的命题中，代表原子命题的符号，有的代表命题常元，有的代表命题变元，因此对应的命题符号串的就不一定是命题了，我们称之为命题合式公式，当使用联结词集{Ø，Ù，Ú，®，«}时，合式公式定义如下。
定义1.2-1 ⑴单个命题常元（0，1）或单个变元p，q，r，…，pi，qi，ri，…等是命题合式公式，并称之为原子命题合式公式；
⑵若A是命题合式公式，则 也是命题合式公式；
⑶若A、B是命题合式公式，则 ， ， ， 也是命题合式公式；
⑷只有有限次地应用⑴─⑶组成的符号串才是命题合式公式。
今后，我们将命题合式公式称为命题公式(Propositional Formula)或简称公式。
例如， , 等是公式。但 , 等不是公式。
从命题公式的定义可以看出，我们可以构造出结构复杂的命题公式，为了讨论结构复杂的命题公式的真值变化情况，我们给出命题公式层次的定义。
定义1.2-2 ⑴若A是单个命题常元或命题变元，则称A是0层公式；
⑵称A是n+1( )层公式是指A符合下列情况之一：
① ，其中B为n层公式；
② ，其中B，C分别为i层公式、j层公式， ；
③ ，其中B，C层次及n取值同②；
④ ，其中B，C层次及n取值同②；
⑤ ，其中B，C层次及n取值同②。
⑶若A的最高层次为r，则称A是r层公式。
例如， 是2层公式, 是2层的, 则是4层公式。
1.2.2 公式的赋值及分类
定义1.2-3 设A是一个命题公式， ， ，…， 为出现在A中的全部命题变元，给 ， ，…， 各指定一个确定的真值，称为公式A关于 ， ，…， 的一组真值指派(True value assignment)，也称为对公式A的一个赋值(Value assignment)或解释(Explanation)。若指定的一个赋值使A的真值为1，则称该赋值为公式A的成真赋值；若使A的真值为0，则称该赋值为公式A的成假赋值。
例如，公式 中，001（p1,p2,p3分别指派0,0,1），101,111都是其成真赋值，而000，010，011，100，111都是其成假赋值。公式 中，01（p1,p2分别指派0, 1），10，11都是其成真赋值，而00是其成假赋值。
由定义易知，含有n ( )个命题变元的命题公式，共有2n组不同的赋值。将命题公式A在所有赋值下的取值情况列表，用类似于联结词真值表的形式表示出来，称之为命题公式A的真值表。
下面给出命题公式真值表具体的构造步骤：
⑴找出公式A中含有的所有命题变元p1，p2，…，pn ，列出所有可能的赋值 (共2n种)，建议按二进制数从小到大的顺序，即按照从00…0开始到11…1的顺序列出，以避免漏写或多写。
⑵按由低到高的顺序写出各层次。
⑶对应每一个赋值，计算公式A各层次公式的真值，直到计算出公式A的真值。
例1.2-1 求下列命题公式的真值表。
⑴A=
表1.2-1
p
q
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
解 公式A的真值表如表1.2-1所示。
⑵A=
解 公式A的真值表如表1.2-2.所示。
表1.2-2
p
q
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
⑶A=
解 公式A的真值表如表1.2-3所示。
表1.2-3
p
q
r
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
1
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
1
1
定义1.2-4 设A为一个命题公式，
⑴若A在它的所有可能赋值下取值均为真，则称A为重言式或永真式(Tautology)；
⑵若A在它的所有可能赋值下取值均为假，则称A为矛盾式或永假式(Contradiction)；
⑶若A至少存在一个赋值是成真赋值，则称A为可满足式(Contingency)。
由定义可知，重言式一定是可满足式，但反之不成立。
给定一个命题公式，判断其类型的一种直观方法是利用命题公式真值表技术。
从公式A的真值表构造过程可以看出，若公式A所在的列（一般在真值表的最后一列）中某行的填入值为1，则表明该行所对应的公式A的赋值为成真；若填入值为0，则表明该行所对应的公式A的赋值为成假。
所以若公式A的真值表最后一列的填入值全部为1，则说明对公式A的所有赋值都是成真赋值，即公式A为重言式，如例1.2-1⑴；若A的真值表最后一列的填入值全为0，则说明对公式A的所有赋值都是成真赋值，即公式A为矛盾式，如例1.2-1⑵；若A的真值表最后一列的填入值中有0也有1，则说明对公式A的所有赋值中至少有一个是成真赋值，且存在至少一个是成假赋值，即公式A仅为可满足式，如例1.2-1⑶。
习题1.2
1.2-1.判定下列符号串是否是命题合式公式，为什么？如果是命题合式公式，请指出它是几层公式，并标明各层次。
⑴ ；
⑵ ；
⑶ ；
⑷ ；
⑸ 。
1.2-2.指出下列公式的层次，并构造其真值表。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.2-3 构造下列公式的真值表，并据此说明哪些是其成真赋值,哪些是其成假赋值。
⑴ ；
⑵ ；
⑶ 。
1.2-4 构造下列公式的真值表,并据此说明它是重言式、矛盾式或者仅为可满足式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.3 等值演算
1.3.1 基本等值式
给定n ( )个命题变元，按照命题公式的形成规则，可以形成多个不同形式的命题公式。对其中许多很长、很复杂的公式，如果用真值表方法来研究，就需要作出很大的一张表。但是，如果针对我们所关注的赋值和最终一列来讲，这些真值表有许多其实是相类同的。如 时， 、 和 的真值表在相同的赋值下，最后一列的填入值都是对应相同的。
定义1.3-1 设A、B是两命题公式，若等价式 是重言式，则称A与B逻辑等值(Logical Equivalence)，记作 。
判断两命题公式是否等值，可应用真值表的方法， 的真值表的最后一列的填入值若全为1，则 为永真式，即A与B等值。当然，也可以通过真值表中公式A、B所在的列的填入值是否对应相同来判定，若相同则说明A与B是等值的，否则就不是等值的。
例1.3-1 判断 与 是否等值。
解 根据题义及两个命题公式是否等值的判定方法做真值表如表1.3-1所示。
表1.3-1
p
q
0
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
0
1
0
0
1
可以看到，真值表最后一列的填入值全部为1，故 。当然我们也可以不做 这一列，仅从 和 所在的列在所有可能赋值下，填入值均对应相同，可得到 和 是等值的结论。
除了用真值表验证 和 等值外我们还可用真值表验证许多等值式，主要有下面一系列公式，我们可以当作定律来运用。
等值演算中的部分等值运算律：
交换律 ⑴ ⑴′
结合律 ⑵ ⑵′
分配律 ⑶
⑶′
双重否定律 ⑷
等幂律 ⑸ ⑸′
吸收律 ⑹ ⑹′
零律 ⑺ ⑺′
同一律 ⑻ ⑻′
排中律 ⑼ 矛盾律 ⑼′
德•摩根律 ⑽ ⑽′
蕴含等值式 ⑾
等价等值式 ⑿
假言易位 ⒀
归谬论 ⒂
这里A、B、C代表任意命题公式。
有了这些公式，我们就可以与初等代数中有理式一样进行演算，这种方法可以得到更多的等值公式。在判断一个命题公式是否重言式、矛盾式时就可以通过等值演算来考查公式是否等值于1或0。这个推演过程就是我们所说的等值演算。
1.3.2 等值演算
在等值演算的过程中我们还会不断地用到下面的规则。
定理1.3-1 （置换规则）设 是含公式A的命题公式， 是用公式B置换了 中的A之后得到的命题公式，如果 ，则 。
证明 设 ， ，…， 是公式 和 中出现的全部命题变元，因为A、B分别是 、 中一部分合式公式，所以A、B中所出现的命题变元都包含在 ， ，…， 之中，又因为 ，故对 ， ，…， 的任一种赋值，A、B的取值均相同，自然 、 取值相同，故 。
例1.3-2 ⑴证明
证明
(蕴含等值式)
(蕴含等值式)
(结合律)
(德•摩根律)
(蕴含等值式)
⑵证明
证明
（分配律）
（排中律）
（同一律）
例1.3-3 判别下列公式的类型。
⑴
解
（分配律）
（矛盾律）
（同一律）
（德•摩根律）
（结合律）
（排中律）
（零律）
故原公式 为永真式。
⑵
解
（排中律、矛盾律）
（零律）
（蕴含定义）
故原公式 为矛盾式。
例2-3.4 试将下面的语句化简：情况并非如此，如果他不来那么我也不去。
解 设p：他来；q：我去；
则语句符号化为：
化简公式：
故上述语句可简化为：我去了但他没有来。
例1.3-5 将下面用程序语言写成的一段程序化简：if A then if B then X else Y else if B then X else Y。
解 画出流程图如图1.3-1所示。
开始
A
B
B
X
Y
结束
T
T
T
F
F
F
图1.3-1
开始
B
X
Y
T
F
结束
图1.3-2
将程序语言写成如下的命题公式：
[A®((B®X)Ù(ØB®Y))]Ù[ØA®((B®X)Ù(ØB®Y))]
化简后得： (B®X)Ù(ØB®Y)
于是，程序可化简成：if B then X else Y。
程序流程图可简化为如图2-3.2所示。
可以看出，整个语句中执行X的条件其实就是 ，执行Y的条件其实就是ØB。
习题1.3
1.3-1 用真值表方法证明下列各等值式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.3-2.证明下列等值式。
⑴ ；
⑵ ；
⑶ ；
⑷ ；；
⑸ ；
⑹ 。
1.3-3.用等值演算的方法化简下列公式。
⑴ ；⑵ ；⑶ ；⑷ 。
1.3-4.用真值表方法判断下列公式的类型。
⑴ ；
⑵ ；
⑶ ；
⑷ ；
⑸ ；
⑹ 。
1.3-5.尽可能简单地写出下列语句的否定。
⑴他若努力学习则会通过考试。
⑵当且仅当水温暖时他游泳。
⑶如果天冷，他则穿外套但不穿衬衫。
⑷如果他学习，那么他将上清华大学或者北京大学。
1.3-6.张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，问到底谁说真话，谁说假话。
1.3-7.符号化下面问题中的前提和结论，并验证从前提到结论的推理正确性。
前提：
⑴如果甲得到冠军，则乙或者丙将得到亚军；
⑵如果乙得到亚军，则甲不能得到冠军；
⑶如果丁得到亚军，则丙不能得到亚军；
⑷甲得到了冠军。
结论：丁不能得到亚军。
*1.4 其他联结词及功能完备集
1.4.1 其它常用联结词介绍
在命题逻辑的研究中，除了前面介绍的五个逻辑联结词外，还有其它一些常用的联结词，它们都有其独特的一面和应用。
定义1.4-1 不可兼或通常用符号“ ”表示，其真值表如表1.4-1所示。由真值表可知
它满足以下性质：
⑴ ；
⑵ 交换律： ；
⑶ 结合律： ；
⑷ 分配律： 。
这些性质可以采用真值表的方法证明。其中⑷指出了联结词“ ”与联结词“ ”、“ ”和“ “之间的联系。这表明含有“ ”的公式可以通过“ ”、“ ”和“ ”表达。
表1.4-1
p
q
0
0
0
0
1
1
1
0
1
1
1
0
表1.4-2
p
q
0
0
1
0
1
1
1
0
1
1
1
0
定义1.4-2 与非联结词，通常用符号“ ”表示，其真值表如表1.4-2所示， 为假当且仅当p、q均为真。
(表1.4-1)
联结词“ ”一般满足交换律，不满足分配律。
联结词“ ”与其他联结词的关系主要有：
⑴ ；
⑵ （自反否定律）；
⑶ ；
⑷ ；
定义1.4-3 或非联结词，通常用符号“ ”表示，其真值表如表1.4-3所示， 为真当且仅当p、q均为假。
和联结词“ ”类似，或非联结词“ ”也一般满足交换律，不满足结合律。
或非联结词“↓”与其它联结词之间的关系有：
⑴ ；
⑵ （自反否定律）；
⑶ ；
⑷ ；
从“ ”和“ ”的性质可以看出，含有“ ”和“ ”公式也可用“ ”、“ ”和“ ”表达。
1.4.2 联结词的功能完备集
在上面定义的联结词中，它们之间都是有联系的，特别是这一节所定义的联结词，都是可以转换为1.1节中所研究的五个基本联结词 “ ”、“ ”、“ ”、“ ”和“ ”来表达的。而且，对于任何含有条件联结词和等价联结词的真值函数，可以通过公式转化成“ ”、“ ”、“ ”来表达。这说明在数理逻辑中，虽然为了应用方便我们定义一些实用的联结词，但通过理论分析可以看出，这并不是必要的。
表1.4-3
p
q
0
0
1
0
1
0
1
0
0
1
1
0
定义1.4-5 设 是联结词的集合，如果对于任意一个真值函数，均存在一个与之等价的真值函数，而且后者仅含有 中的联结词，则称 是联结词的功能完备集。
在理论上与应用上通过选用不同的功能完备集，可以方便地对真值函数类进行研究。
首先，{ ， ， ， ， }是最常用的功能完备集。联结词集{ ， ， }是一个重要的功能完备集，使用该功能完备集来表达的真值函数系统，常称为Boole代数系统；在编码理论中，自然地要用到功能完备集{ ， }表达的真值函数系统，它也称为Boole代数系统。另外在研究逻辑系统的演绎和推理时，{ 、 }是一个重要的功能完备集。在制造大规模集成电路的芯片中完备集{ }和{ }都有广泛的应用。
所有的这些功能完备集都可以通过真值表利用定义验证。
在进一步的研究中，会遇到极小功能联结词集的提法，在此我们只简单说明其含义。
设 为联结词集合，若 中存在一个联结词可以由 中的其他联结词表示，则称该联结词为联结词集 中的冗余联结词，否则称为独立联结词。
定义1.4-6 所谓某个联结词集合 为极小功能完备联结词集是指 满足下面条件：
⑴ 是一个功能完备集；
⑵ 中没有冗余联结词。
例如，联结词集{ }和联结词结{ }都是极小功能完备集；联结词集{ 、 }也是极小功能完备集；但是联结词集{ ， ， }就不是极小功能完备集，因为{ ， }和{ ， }都仍然是功能完备集。而{ }、{ }、{ }不是极小功能完备集，因为它们根本就不是功能完备的。
应该说明，寻求极小功能完备集，不是个理论性问题，而主要是为了满足工程实践中的需要。但是，一般情况下不至于因联结词的数目减少或者增多使公式形式变得复杂。我们常采用能完备集：“ ”、“ ”、“ ”、“→”和“↔”五个基本联结词构成的联结词集合。但这个完备集不是极小功能完备集。
习题1.4
1.4-1 符号化下面两个命题，要求细化到原子命题，并且只能用一个联结词。
⑴或者明天下雨或者后天下雨。
⑵明天我将去北京或者去上海。
1.4-2 将下列公式进行转化，使之只含有{ }中的联结词。
⑴ ；
⑵ ；
⑶ 。
1.4-3 已知{ }是功能完备联结词集，试证明{ }也是功能完备联结词集。
1.4-4 已知 是极小功能完备集，证明 和 都是极小功能完备集。
1.5 对偶与范式
1.5.1 对偶
在1.3节中介绍的基本等值式中多数公式是成对出现，这些成对出现的公式通常称为对偶的。
若命题公式A中只出现联结词“ ”、“ ”或“ ”，则称它是受限命题公式。
定义1.5-1 在受限命题公式A中，将“ ”换成“ ”，“ ”换成“ ”，0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。
从定义不难看出，如果A*是A的对偶式，那么A也是A*的对偶式，即对偶式是相互的。所以，（A*）*=A。
例如， 与 ， 与 ， 与 均为对偶式。
关于对偶式有下面两个重要的定理。
定理1.5-1 设A和A*互为对偶式，p1，p2，…，pn是出现在A和A*中的全部命题变元，若将A和A*写成n元函数形式，则：
⑴ ⇔ A* ；
⑵ A ⇔ 。
例1.5-1 ⇔ ，则A* ⇔ ；
因为 ⇔ ⇔ ⇔ ，
所以 ⇔A* 。
因此， ⇔ØA* ，用 分别代替此公式中的
即得A ⇔ 。
定理1.5-2（对偶原理） 设A，B为两个命题公式，如果 ，则A* B*,其中A* ，B*分别是A，B的对偶式。
证明 设A(p1，p2，…，pn)⇔ B(p1，p2，…，pn)，
所以 A(p1，p2，…，pn)⇔ B(p1，p2，…，pn)；
又∵ A(p1，p2，…，pn)⇔A* ，
⇔B* ，
于是，A* ⇔ B* ，
分别用 代替 即得
A* ⇔ B* 。
例如，由 ⇔ ，可推得：
⇔ 。
1.5.2 范式
给定一个命题公式，判断它是重言式、矛盾式，还是可满足式，这类问题我们称为判定问题，在前面已经讲解过解决判定问题的两种方法，即真值表法和真值演算法，但当命题变元数目比较多时，仅用上述方法判断起来就不那么明显了。为此，我们试图将命题公式标准化。只要能使同一真值函数所对应的所有命题公式具有相同的标准型，就使得对判断两命题公式是否等值以及判断公式的类型变得规范、明显起来。
定义1.5-2由有限个命题变元或其否定构成的合取式称为原子合取式(Atomic Conjunctive Form)；
由有限个命题变元或其否定构成的析取式称为原子析取式(Atomic Disjunctive Form)。
给定命题变元p，q，则 ， ，p， 等是原子合取式， ， ， p， 等是原子析取式。通常用A1，A2，…，An来表示n个原子析（合）取式。
从定义不难看出：
一个原子析取式是重言式，当且仅当它同时含有一个命题变元及其否定；
一个原子合取式是矛盾式，当且仅当它同时含有一个命题变元及其否定。
例如，原子析取式 是重言式，原子合取式 是矛盾式。
定义1.5-3由有限个原子合取式构成的析取式称为析取范式(Disjunctive Normal Form)；
由有限个原子析取式构成的合取式称为合取范式(Conjunctive Normal Form)。
例如， 、A* 分别为析取范式和合取范式。
不难发现：
一个析取范式为矛盾式,当且仅当它的每个原子合取式都是矛盾式；
一个合取范式为重言式,当且仅当它的每个原子析取式都是重言式。
那么给定任何一个命题公式,是否都能求出与之等值的析取范式和合取范式呢?
定理1.5-3（范式存在定理） 任一命题公式都存在着与之等值的析取范式，也都存在着与之等值的合取范式。
若公式A中含有联结词→, 等，可以用基本等值式及置换原则将它们消去：
①p→q⇔┐p∨q；②p q⇔(┐p∨q)∧(p∨┐q)。
若遇到┐(┐p)形式,利用双重否定律将否定号消去：
┐(┐p)⇔p。
若遇到┐(p∧q), ┐(p∨q)等形式，利用德·摩根律将否定号内移：
①┐(p∧q)⇔┐p∨┐q；②┐(p∨q)⇔┐p∧┐q。
最后，若是求析取范式，应当利用“∧”对“∨”的分配律, 若是求取范式，应当利用“∨”对“∧”的分配律。
任一公式A通过上述三步,即得到与A等值的析取范式或合取范式。
求范式的具体步骤:
⑴将含有联结词→, 的公式转化为仅含┐、∨和∧形式的公式；
⑵否定符号的内移或消去；
⑶利用分配律得到析取范式或合取范式。
例1.5-3 求命题公式((p∨q)→r)→p的合取范式和析取范式。
解 ①求析取范式：((p∨q)→r)→p⇔┐(┐(p∨q)∨r)∨p⇔((p∨q)∧┐r)∨p
⇔(p∧┐r)∨(q∧┐r)∨p即为所求的析取范式。
再利用交换律和吸收律：(p∧┐r)∨(q∧┐r)∨p
⇔p∨(p∧┐r)∨(q∧┐r)⇔p∨(q∧┐r)也是所求的析取范式。
②求合取范式：((p∨q)→r)→p⇔((p∨q)∧┐r)∨p
⇔(p∨q∨p)∧(┐r∨p)即为所求的合取范式。
利用交换律和等幂律：(p∨q∨p)∧(┐r∨p)⇔(p∨q)∧(┐r∨p)也是所求的合取范式。
可见,与某个命题公式等值的析取范式是不唯一的，合取范式也是不唯一的。
从上面的例1.5-3可以看到，同一个命题公式的析取范式和合取范式都是不唯一的，这说明范式虽然是一种规范的形式，但还不能作为标准形式。为此，我们需要在此基础上做进一步的规范定义。
1.5.3 主范式
定义1.5-4 对于命题公式A，包含A中的每个命题变元或其否定一次且仅一次的原子合取式称为极小项。
例如， ， 等是极小项，而 ， ， 等不是极小项。
下面我们就仅含有2个命题变元的情形来说明一种极小项的抽象简明的表示方法。
2个命题变元p，q可形成4个极小项，如果将命题变元看成1，命题变元的否定看作0，那么每个极小项就对应一个二进制数，自然也对应一个十进制数。不难看出，二进制数正是该极小项的成真赋值，不妨用对应的十进制数作为该极小项抽象表示法的下角码。
4个对应情况如表1.5-1所示：
表1.5-1
极小项
成真赋值
对应十进制数
简明表示
00
0
m0
01
1
m1
10
2
m2
11
3
m3
一般地，n个命题变元共产生2n个极小项，逐个记作m0，m1，…， 。
定义1.5-5 如果命题公式A的析取范式中的原子合取式全是极小项，则称该析取范式为A的主析取范式(Principal Disjunctive Normal Form)。
定理1.5-4 任何命题公式的主析取范式都存在且唯一。
求主析取范式的步骤可归纳如下：
⑴求出A的析取范式 ；
⑵利用同一律，去掉析取范式 中所有永假的原子合取式；
⑶利用等幂律，将析取范式 中重复出现的合取项或者命题变元合并；
⑷利用同一律，若合取项中未出现命题变元 ，则添加 为其一个合取项，并用分配律展开；
⑸再次合并相同的项和消去产生矛盾的项，然后按照下角标从小到大顺序排列，并用 形式表示之，如 ，用 表示等。
例1.5-4 求 的主析取范式。
解 由例1.5-3知 ⇔
⇔
⇔
⇔m4 m5 m6 m7 m2 m6⇔m2 m4 m5 m6 m7
⇔
由极小项的定义可知，上式中2，4，5，6，7对应的二进制数010，100，101，111为原公式的成真赋值，而没出现的m0，m1，m3的下角码0，1，3对应的二进制数000，001，011为原公式的成假赋值。因而，知道了一个命题公式的主析取范式，可立即写出A的真值表。
反之，若作出了A的真值表，找出所有的成真赋值，并将其二进制表示对应的十进制数作为下角码得到极小项，并做析取即为A的主析取范式。
例1.5-5 试由 的真值表求出它的主析取范式。
解 作 的真值表如表1.5-2所示：
表1.5-2
p
q
r
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
可见， 的成真赋值为001，011，101，110，111，其对应极小项为m1，m3，m5，m6，m7。故其主析取范式： ⇔m1 m3 m5 m6 m7⇔∑(1，3，5，6，7)。
主析取范式可用于解决以下问题：
①判断两命题公式是否等值。由于任何命题公式的主析取范式都是唯一的，因而若 ，说明A与B有相同的主析取范式，反之，若A、B有相同的主析取范式，必有 。
②判断命题公式的类型。设A是含n个命题变项的命题公式，A为重言式，当且仅当A的主取范式中含全部2n个极小项；A为矛盾式，当且仅当A的主析取范式中不含任何极小项，可设A的主析取范式为0；当然，若A主析取范式中至少含一极小项，则A是可满足式。
③求命题公式的成真或成假赋值。若A是一个含有n个变元的命题公式，则A的主析取范式的下角码所对应的n位二进制数都是命题公式A的成真赋值，而其余的n位二进制数都是命题公式A的成假赋值。
和前面讲过析取范式和合取范式一样，除了主析取范式外，还有其对偶形式，即主合取范式，为此首先给出极大项的定义。
定义1.5-6 对于命题公式A，包含A中的每个命题变元或其否定一次且仅一次的原子析取式称为A的极大项。
例如， ， 等是极大项，而 ， 等不是极大项。
同极小项类似，n个命题变元可产生2n个极大项，每个极大项对应一个二进制数，若将命题变元看成0，命题变元的否定看作1，则该二进制数为对应的极大项的成假赋值，可取其对应十进制数作为其简明抽象表示的下角码。如n=2时，对应关系如表1.5-3所示：
表1.5-3
极小项
成假赋值
对应十进制数
简明表示
00
0
M0
01
1
M1
10
2
M2
11
3
M3
定理1.5-4 极小项与极大项之间存在下面的关系：
⇔Mi ， ⇔mi。
定义1.5-7 如果命题公式A的合取范式中的原子析取式全是极大项，则称该合取式为主合取范式(Principal Conjunctive Normal Form)。
可以证明：任一命题公式A的主合取范式一定存在且唯一的。
求一命题公式A的主合取范式与求主析取范式的步骤类似，只是在第⑶步中，应添加 为析取式中的一个析取项，然后利用分配律，其他步骤一样。
例1.5-6 求 的主合取范式。
解 ⇔ （合取范式）
⇔
⇔
⇔
⇔M0 M2 M4⇔∏（0，2，4），其中∏表示合取。
如果求出了公式A的主析取范式，可以直接用主析取范式求出其主合取范式（反之亦然）。下面通过例子来说明这种方法，在例1.5-5中我们求得 的主析取范式为：
⇔m1 m3 m5 m6 m7
而
所以
则
公式 的主合取范式即为所求。
由A主析取范式求合取范式的步骤为：
⑴求出A的主析取范式中没有出现的极小项 ， ，…， ；
⑵求出与⑴中极小项下角码相同的极大项 ；
⑶由以上极大项构成的合取式就是A的主合取范式。
例1.5-7 求 的主合取范式。
解 由例1.5-4知 的主析取范式为m2 m4 m5 m6 m7
其中没有出现的极小项为m0，m1，m3，对应得极大项为 ，因此， 的主合取范式为：
当然，类似地可从主合取范式求出主析取范式，具体步骤请读者给出。
同样通过主合取范式也可以用于：
①判断公式之间是否逻辑等值；
②判断公式类型（重言式不含极大项，用1表示）；
③求成假赋值（所含极大项下角码二进制表示）或成真赋值（不含）。
习题1.5
1.5-1.写出下列公式的对偶式。
⑴ ；
⑵ 。
1.5-2.将下列公式化为析取范式和合取范式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-3.求下列公式的主析取范式和主合取范式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-4.用真值表法求下列公式的各极小项和极大项，并写出主析取范式和主合取范式。
⑴ ； ⑵ ；
⑶ ； ⑷ 。
1.5-5.通过求主析取范式，判断下列公式的类型。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-6.通过求主合取范式证明下列各等值式。
⑴ ；
⑵ ；
⑶ 。
1.6 推理理论
1.6.1 命题的蕴含关系
推理是从前提推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则得到的命题公式。从某些给定的前提出发，按照严格定义的形式规则，推出有效的结论，这样的过程称为形式证明或演绎证明。
定义1.6-1 设 都是命题公式，若 为重言式，记作 ，则称A1，A2，…，Ak能推出结论B，或称B是前提集合{A1，A2，…，Ak}的逻辑结论(Logical consequence)或者有效结论。
同用“ ”表示“ ”为重言式类似，“ ”当且仅当“ ”是重言式。
于是，判断推理是否有效的方法就是判断重言蕴涵式的方法，比如我们前面所讲的真值表法、等值演算和主范式法等。
例1.6-1 判断如下推理是否有效。
如果天气凉快，小王就不去游泳。天气凉快。所以小王没有游泳。
解 命题符号化， p：天气凉快，q：小王去游泳，
前提：
结论：
推理的形式结构： ，要判断其推理是否有效，就是判断 是否是重言式。
①真值表法：作出 的真值表如表1.6-1所示。
由其真值表可以看出，最后一列均为1，即 重言式，所以推理有效。
②等值演算法： ⇔
⇔ ⇔
⇔ ⇔1∧1⇔1。
即 为重言式。
故推理有效。
表1.6-1
p
q
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
1
③主析取范式法： ⇔1⇔∑（0，1，2，3）为重言式，故推理是有效的。
在推理过程中，我们也可以应用已经得到的一些基本蕴含关系（或重言蕴涵式）。
1. 附加
2. 附加
3. 化简
4. 化简
5.
6.
7.
8.
9. 合取
10. 假言推理
11. 拒取式
12. 析取三段论
13. 假言三段论
14. 构造性二难推理
1.6.2 形式证明
在推理过程中，如果命题变元较多，采用真值表、等值演算和主范式方法有时不方便。为此介绍形式证明的方法。
形式证明(Formal Proof)的推理过程是一个命题序列，其中每一个命题或者是已知命题，或者是由某些前提根据推理规则推出的结论，序列的最后一个命题是需要论证的结论。
要进行正确的推理，需要使用推理规则，下面给出形式证明中的推理规则：
⑴前提引入规则P：在证明的任何步骤中，都可以引入前提。
⑵结论引入规则T：在证明的任何步骤中，在此之前证明得到的结论都可以作为后续证明的前提引入。
⑶置换规则：在证明任何步骤中，命题公式中的任何子公式都可以用与之等值的命题公式置换，如可以用 置换 等。
⑷代入规则：在证明的任何步骤中，重言式的任何一个命题变元都可以用一个命题公式代入，得到的仍是重言式。
⑸附加规则：
⑹化简规则：
⑺假言推理规则：
⑻拒取式规则：
⑼析取三段论规则：
⑽假言三段论规则：
⑾等价三段论规则：
⑿构造性二难规则：
⒀合取引入规则：
下面我们通过例题来说明如何构造形式证明。
例1.6-2 给出下列的推理的形式证明： ， ， ， ， q。
前提： ， ， ， ，
结论：q
证明 ① P
② P
③ T①②拒取式
④ P
⑤r T③④假言推理
⑥ P
⑦ T⑤⑥拒取式
⑧ P
⑨q T⑦⑧析取三段论
①
②
③
④
⑤
⑥
⑦
⑧
⑨
①
②
⑤
④
③
⑥
⑦
图1.6-1
图1.6-2
在形式证明的实际应用中，有时候为了使证明过程给人以更清晰的认识，往往在证明后附上证明（推理）树。例如本题的证明树如图1.6-1所示。它的作法是，把证明（推理）过程中作为前提的标号作为树叶，每一步用线相连，得到的相应结论的标号作为相应的结点，直到最后一步的结论作为树根。
例1.6-3 写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。
解 符号化题目中的命题，设p：今天是星期一，q：进行英语考试，r：进行离散数学考试，s：英语老师有会。
前提： , ,p,s
结论：r
证明：① P
②p P
③ T①②假言推理
④ P
⑤s P
⑥ T④⑤假言推理
⑦r T③⑥析取三段论
由有效推理可知，今天进行离散数学考试。其证明树如图1.6-2所示。
在上面的例子中，采用前面的规则进行形式证明的方法，通常也称为直接证明法。在形式证明中，有时可采用一定的技巧，使证明过程简化。
CP规则：
证明类似 问题时，我们常采用这种方法。方法是，将结论中蕴涵前件作为一个附加前提来证明结论中蕴涵式中的后件是有效逻辑结论。
这种方法是可以保证整个推理正确的。
⇔
⇔
⇔
根据置换原则可知，上式最后一个式子为重言式与第一个式子为重言式是等价的。
通常我们把这个结论在运用于形式证明时称为CP规则。
例1.6-4 用形式证明法证明： ， ，q
前提： ， ，q
结论：
证明 ①s 附加前提引入
② 前提引入
③p ①②析取三段论
④ 前提引入
⑤ ③④假言推理
⑥q 前提引入
⑦r ⑤⑥假言推理
⑧ ①⑦CP规则
间接证明法--归谬法。
归谬法是将结论的否定作为一前提引入，通过有效推理得到矛盾，以此说明推理正确。
先补充一个概念：设A1，A2，…，Ak是k个命题公式，若A1 A2 … Ak是可满足式，则称A1，A2，…，Ak是相容的，否则，即A1ÙA2Ù…ÙAk为矛盾式则称A1，A2，…，Ak是不相容的。因
⇔
⇔
所以，若A1，A2，…，Ak， 不相容，则说明 是重言式，即B是公式A1，A2，…，Ak的逻辑结论，故应用这种方法推理构造有效。
例1.6-5 用间接证明法证明： ，p，
前提： ，p，
结论：
证明 ① P
②p P
③ T①②假言推理
④ P否定结论引入
⑤ T③④拒取式
⑥s T⑤化简
⑦ P
⑧ T⑥⑦合取
由⑧得到矛盾，根据归谬法可知推理正确。
习题1.6
1.6-1.符号化下面问题中的前提和结论,并指出推理是否正确，为什么？
前提：⑴如果这里有演出，则通行是困难的；
⑵如果他们按照指定的时间到达，则通行是不困难的；
⑶他们按照指定时间到达了。
结论：这里没有演出。
1.6-2.形式证明给出下列推理的过程的形式证明。
⑴
⑵
⑶
⑷
⑸前提：
结论： 。
1.6-3.下面的推理过程是否正确，结论是否有效，并说明理由。
① P前提引入
② T ①化简
③ P前提引入
④ T ②③假言推理
1.6-4.判断下面的推理证明过程是否正确，若不正确请指出错误所在位置及出错原因，若正确则请补足每一步所用的推理规则。
前提：
结论：
证明：① ⑴
② ⑵
③ ⑶
④ ⑷
⑤ ⑸
⑥ ⑹
⑦ ⑺
⑧ ⑻
1.6-5.用推理规则证明下列推理的正确性：如果张三努力工作，那么李四或王五感到高兴；如果李四感到高兴，那么张三不努力工作；如果刘强高兴，那么王五不高兴。所以，如果张三努力工作，则刘强不高兴。
1.6-6.已知事实如下，问结论是否有效。
前提：⑴如果天下雪，则马路就会结冰；
⑵如果马路结冰，汽车就不会开快；
⑶如果汽车开得不快，马路上就会塞车；
⑷马路上没有塞车。
结论：天没有下雪。
1.7 * 命题逻辑在门电路中的应用介绍
P
P
Q
Q
P
P
Q
P
Q
P
Q
P
Q
P
Q
图1.7-1
在自动控制系统和电子计算机中采用由电子元件组成，用信号控制的开关，我们称之为“门”。在控制系统和电子集成以及机电设计中设计出来的由“门”联结而设计出来的电路称为“门电路”。基本的门电路有三种：“或”门电路、“与”门电路和“非”门电路，其功能完全与三种基本逻辑运算“ ”、“ ”和“ ”相对应。事实上，在门电路的理论中还经常用到其他类型的门电路，如我们在讲其他联结词时曾经提到过的“或非”门、“与非”门等，这些都是可以与逻辑联结词相对应的。首先给出部分常用命题逻辑联结词与门电路对应如图1.7-1所示。
下面我们来看一个简单的自动控制电路的设计。
例1.7-1 试设计红绿灯自动控制线路，要求传感器中记数器内容Z，当 时亮绿灯，当 时亮红灯，当 时亮黄灯。
解 设p： 且p⇒L1（亮绿灯） q： 且q ⇒L2（亮红灯）
r： 且r⇒L3（亮黄灯）
因为r⇔ ⇔ ，所以控制电路如图1.7-2所示。
P
Q
L1
L2
L3
图1.7-2
对于复杂的问题，运用逻辑知识可以理出清晰的思路，使得设计电路时得心应手。
习题1.7
1.7-1 一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞机计划正确或有误的回答。由于计算机也可能发生故障，因此采用三台计算机同时复核的策略。由所给出的答案，再根据“少数服从多数”的原则作出判断，试将结果用命题公式表示，并加以简化，画出电路图。
1.8 例题解析
例1.8-1下面给出的语句是否是命题，若是命题，试给出其真值。
⑴你喜欢周杰伦吗？
⑵大家不要讲话了！
⑶2+x=5。
⑷2是素数。
⑸1是素数。
⑹如果1是素数，2就不是素数。
⑺地球之外的星球上还有生物。
⑻我生于1978年。
⑼我正在说谎！
解 本题主要考查我们对命题概念的理解。
⑴、⑵都不是陈述句，不可能是命题；⑶中包含有待赋值的x，所以也不是命题；⑷是真命题；⑸是假命题；⑹是一个复合条件命题，因为前件为假，所以它是一个真命题；
虽然⑺、⑻的真值我们还不知道，但他它是有真假的，所以也是命题；⑼虽然也是陈述句，但是它不是命题，它是一个典型的悖论。
例1.8-2 符号化下列命题公式。
⑴当我想起我母亲劳碌的身影时我就禁不住哭了。
⑵仅当我有时间并且天不下雨，我将去书店。
⑶一个正整数是素数当且仅当它只能被1和它自身整除。
⑷小李总是在图书馆看书，除非图书馆不开门或者小李有病。
⑸假如上午天不下雨，我去看电影，否则就在家里读书。
解 在数理逻辑中，命题逻辑的翻译是比较简单的，容易混淆的地方主要在于：
①“当…则…”、“仅当…才…”句型的符号化；②“…除非…”句型的符号化；③可兼或与不可兼或符号化时的分辨；④蕴涵和等价容易用反；⑤蕴涵的前件和后件的区分。
⑴设p：我想起我母亲劳碌的身影； q：我禁不住哭了。则原语句符号化为： 。
⑵设p：我有时间；q：天不下雨；r：我去书店。则原语句符号化为： 。
⑶设p：一个正整数是素数；q：一个正整数能被1整除； r：一个正整数能被它自身整除； s：一个正整数能被除了1和它自身之外的正整数整除。则原语句可符号化为：
。
⑷设p：小李在图书馆看书；q：图书馆开门；r：小李没病。则原语句符号化为：
。
⑸设p：上午天下雨；q：我去看电影； r：我在家里读书。
则原语句可符号化为：
。
例1.8-3 给定命题公式 的主析取范式中含有如下极小项： ， ， ， 。请写出 主合取范式并回答下列问题， 主合取范式中含有（ ）个极大项，成真赋值个数有（ ）个，成假赋值个数有（ ）个。
解 这是一类很典型的题目。对于求命题公式的极小项和极大项、成真赋值和成假赋值与求命题公式的主范式是同一种问题。
由已知条件可很容易地看出命题公式A的主析取范式中的极小项为m7，m6，m5，m2，其主析取范式为 ，故其主合取范式可根据与主析取范式之间的关系直接写出为 ，所以极大项即为M0，M1，M3，M4，共4个极大项。而极小项和极大项对应的二进制数就是公式的成真赋值和成假赋值，故成真赋值为010，101，110，111共4个，成假赋值为000，001，011，100共4个。
例1.8-4 命题公式 的对偶式为（ ）。
（A） （B） （C） （D）
解 对于对偶式是在仅含联结词“ ”，“ ”和“ ”的命题公式中“ ”与“ ”置换、0与1置换而得到的，因此，求像本题这样含由其它联结词的公式的对偶式时，就先等值转化成仅含联结词“ ”，“ ”和“ ”的命题公式来求。
∵ ⇔ ∴其对偶式为： ⇔ ，
故选择答案（C）。
例1.8-5 一个公安人员审查一件盗窃案，已知事实如下：
⑴甲或乙盗窃了录音机；
⑵若甲盗窃了录音机，则作案时间不能发生在午夜前；
⑶如乙的证词正确，则午夜时屋里的灯光未灭；
⑷若乙的证词不正确，则作案时间发生在午夜之前；
⑸午夜时屋里的灯光灭了。问到底是谁盗窃了录音机？
解 题目中的命题符号化，p：甲盗窃了录音机， q：乙盗窃了录音机， r：作案时间在午夜前，s：乙的证词正确，t：午夜时灯光未灭。
前提： ， ， ， ，
结论：根据逻辑推理求出
推理过程：① P
② P
③ T①②拒取式
④ P
⑤r T③④假言推理
⑥ P
⑦ T⑤⑥拒取式
⑧ P
⑨q T⑦⑧析取三段论
由⑨说明是乙盗窃了录音机。
例1.8-6 判断下式是否为重言式。 。
解 对于判断一个命题公式是重言式、矛盾式还是可满足式，我们可以采用的方法很多。利用等值演算法，真值表法和化为主范式的方法都很有效，并且也是我们经常采用的，对本题当然也适合。对真值表方法是很基本的，主要在于我们要细心，并且对于本题这样出现命题变元较多的，作出的表会很大；对于主范式和等值演算法的道理是一样的，就是利用我们已经掌握的等值式逐步演算，关键在于我们要掌握好等值式，对于本题命题公式比较复杂，用起来也有一定的难度，那么是否可以从公式的形式找到一种更好的方法呢？事实上，在做题目是我们要善于发现题目的特点，像这个题我们看到公式有反复的蕴涵联结词，并且是要判断是否是重言式，所以我们可以采用构造形式证明的方法证明：
，而由CP规则就是要证明：
构造形式证明：
① P
② P附加前提引入
③ T①蕴涵等值式，置换
④ T③添加
⑤ T④蕴涵等值式，置换
⑥ T②蕴涵等值式，置换
⑦ T⑥添加
⑧ T⑦蕴涵等值式，置换
⑨ P附加前提引入
⑩ P⑤⑧⑨构造性二难推理
由上面的推理过程可知推理有效，根据CP规则可知所给公式是重言式。
复习题二
1.下列句子中，哪些是命题？如果是命题，指出其是简单命题还是复合命题，并判断真假。
⑴中国有四大发明。
⑵吸烟请到吸烟室去！
⑶ 是无理数！
⑷李春和李红是姐妹。
⑸李春在说谎。
⑹如果3是偶数，那么中国人的母语是汉语。
⑺只要你抽烟，你就很容易得病。
⑻只有今天是星期一，明天才是星期二。
⑼李春这个学期《离散数学》和《数据结构》都考了100分。
⑽下雪路滑，他迟到了。
⑾不经一事，不长一智。
⑿一朝被蛇咬，十年怕井绳。
2.符号化第1题中的复合命题，要求细化到原子命题。
表2-1
p
q
r
s
A（其他为0）
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
3.设p：李春生于1979年，q：李春生于1980年，说明命题“李春生于1979年或生于1980年”既可以符号化为“ ”，又可以符号化为“ ”的理由。4.在什么情况下，下面的一段话是真的。
说李刚不会拳击或李春不会唱歌是正确的，而说如果李刚会唱歌，李春就会拳击是不正确的。
5.命题公式A包含4个命题变元：p，q，r，s，其真值表如表2-1所示：
⑴写出A的极小项和极大项；
⑵写出与A等值的主析取范式和主合取范式；
⑶写出与A等值的析取范式的最简形式。
6.证明下列命题的等值关系。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
7.用真值表、等值演算和求主范式的方法判断下面公式的类型。
⑴ ；
⑵ ；
⑶ 。
8.证明下列推理。
⑴ ；
⑵前提： ， ， ， ，
结论： ；
⑶ ， ， 。
9.用推理规则说明：
， ， 是否能同时成立。
10.用真值表、等值演算、求主范式和构造推理证明下面的推理正确。
只要小王曾经到过受害人的房间并且11点以前没有离开，小王就犯了谋杀罪。小王曾经到过受害者房间。如果小王在1点以前离开，看门人会看到他。看门人没有看到他。所以小王犯了谋杀罪。
11. 有一位逻辑学家被一伙强盗绑架。强盗头目天生好玩刺激的游戏，他把逻辑学家拘于有两个门的牢狱，两个门中其中一个是生门，一个是死门。如果从生门出去将可以安全离开，如果从死门出去，将立即处死。但是到底哪个是生门，哪个是死门不可能告诉逻辑学家。
在每个门旁强盗头目各派有一名强盗把守，这两名强盗一个所说的每一句话都是假话，另外一个则说的每一句话都是真话，当然到底哪个是说假话的哪个是说真话的不可能让逻辑学家知道。现在强盗头目给逻辑学家一次可能生还的机会，他允许逻辑学家问两个守门强盗中的一个且只能问其中一个，并且被问的强盗只能回答一次且只能回答一句话。现在逻辑学家可以安全的出去吗？
(提示：逻辑学家对A（其中任意一个门旁的强盗）说“我问B（即另一个门旁的强盗）‘你身边的门是生门吗？’，他说‘不是’，你说他回答的正确吗？”)
思维的形式结构包括概念、判断和推理。其中，概念是思维的基本单位；判断是通过概念对事物是否具有某种属性进行肯定或否定的回答；由一个或者几个判断推出另一个判断的思维过程就是推理。研究推理有很多方法，其中用数学方法来研究推理的规律的学科统称为数理逻辑，这里所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑也叫符号逻辑。
我们主要介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑，首先介绍命题逻辑。
1.1 命题与命题联结词
1.1.1 命题
凡具有真假的陈述句就称为命题(Proposition)。命题通常用小写英文字母表示。
例如，“2是素数”是命题，可用符号表示为 p：2是素数。
例1.1-1 ⑴3能被2整除。
⑵C++是一门计算机高级程序语言。
⑶请关上门!
⑷你好吗？
⑸ 。
⑹“本语句是假的”。
其中⑴是命题，对它进行判断的结果是真的；⑵是命题，是假的；⑶、⑷不是陈述句，故不是命题；⑸是陈述句，但由于x、y不确定，使得整个句子可真可假，即没有确定的判断结果，故不是命题；⑹是一个悖论，无法确定其真假，所以不是命题。
作为命题的陈述句所表达的判断结果称为该命题的真值(Truth Value)。一个命题的真值为“真”，用“1”或“T”表示，此时称该命题为真命题(True Proposition)；一个命题的真值为“假”，用“0”或“F”表示，此时称该命题为假命题(False Proposition)。
例如，在例1.1-1中，⑴的真值为假，故为假命题；⑵的真值为真，所以是真命题。
例1.1-2 ⑴这盘菜太咸。
⑵太阳系外有宇宙人。
⑶1962年2月3日晚郑州市金水区成立。
注意 要把“已知其真假”与“本身具有真假”区别开来。在判断一个陈述句是否是命题时必须明确，只要能分辨出真假的语句就是命题。
⑴是命题。虽然语句表达的判断结果似乎不唯一，但实际上其真假是唯一确定的。我们可以认为其真假取决于说话人的主观判断，可理解为“我认为这盘菜太咸”。
⑵是命题。虽然目前尚无法确定其真假，但从事物的本质而论，是可分辨真假的。
⑶是命题。虽然一时难辨其真假，但其本身是有真假的，若能查到相关资料，结果自然就明了了。
容易看出，例1.1-1、例1.1-2中给出的是命题的陈述句都不能进一步分解，类似这种不能再分的命题，称为原子命题(Atomic Proposition)或简单命题，原子命题是命题逻辑中最基本、最小的单位。由作为原子命题的简单陈述句通过连词联结而成的命题，称为复合命题(Compoud Proposition)。
例1.1-3 ⑴林刚和林强是三好学生。
⑵离散数学是计算机专业的一门基础课.
⑶如果3+2<4，那么太阳早上将由西边出来。
其中⑴、⑶是复合命题，⑵是原子命题。判断一个命题是否是复合命题的关键是看分解后各部分是否仍为命题。特别指出，有些在表面上互不相干的命题语句通过连词可组成复合命题，如本例中的⑶。
1.1.2 命题联结词
复合命题是用自然语言中的连词联结命题所组成的，为了便于研究，我们还需要对自然语言中的各种连词也用符号表示出来，以便得到形式化了的复合命题。在数理逻辑中，我们将这种自然语言连词的形式符号称为命题逻辑联结词(Logical Connective)。
⑴否定(Negation)
定义1.1-1 设p是命题，“非 p”称为 p的否定式，记作 ，称符号 为否定联结词。并规定， 为真当且仅当p为假。
例如，设p表示“3是偶数”，则p的否定，即“3不是偶数”可用符号表示为： 。由于p的真值为0，所以 真值为1。
为了更好地理解联结词所代表的含义，引入一种表格方法─真值表(Truth Table)。
如表1.1-1所示就是否定联结词的真值表。
表1.1-1中的“1”、“0”分别表示标记在该列顶端的命题取值为真或假。
表1.1-1
p
0
1
1
0
⑵合取 (Conjunction)
定义1.1-2 设p、q都是命题，复合命题“p并且q”称为p与q的合取式，记作 ，称符号 为合取联结词。并规定， 为真当且仅当p与q同时为真。
合取联结词的真值表如表1.1-2所示。
例如，设p表示“2是素数”，q表示“2是偶数”。
则“2是素数并且是偶数”可用符号表示为： 。由于p、q真值均为1，故 真值为1。
⑶析取 (Disjunction)
定义1.1-3 设p、q都是命题，复合命题“p或者q”称为p与q的析取式，记作 ，称符号 为析取联结词。并规定， 为真当且仅当p与q中至少有一个为真。
析取联结词的真值表如表1.1-3所示。
例如，设p表示“王燕学过英语”；q表示“王燕学过法语”。则“王燕学过英语或法语”可用符号表示为： 。
表1.1-2
表1.1-3
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
0
1
1
1
⑷ 蕴涵(含)（Implication）
定义1.1-4 设p、q都是命题，复合命题“如果p，那么q”称为p与q的蕴含式，记作： ，其中p称为其前件，q称为其后件，称符号 为蕴含联结词。并规定， 为假当且仅当p为真且q为假。
蕴含联结词的真值表如表1.1-4所示。
例如，设p表示“我是老师”；q表示“我年龄大了”。则“如果我是老师，那么我年龄大了”可用符号表示为： 。若我是一名年轻教师，则此时p为真，q为假，故 为假。
表1.1-4
表1.1-5
0
0
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
⑸ 等价(Equivalent)
定义1.1-5 设p、q都是命题，复合命题“p当且仅当q”称作p与q的等价式，记作： ，称符号 为等价联结词。并规定， 为真当且仅当p、q真值相同。
等价联结词的真值表如表1.1-5所示。
例如，设p表示“两圆的面积相等”；q表示“两圆的半径相等”。则“两圆的面积相等当且仅当其半径相等”可用符号化表示为： 。
为了叙述方便，我们将用符号表示命题及其联结词的过程称为命题的符号化(Proporsitional signify)。
对于命题的符号化我们有必要指出以下几点：
⒈ 同一个命题联结词在自然语言中可能有不同的表达方法。
例1.1-4 将下列命题符号化。
⑴ 离散数学并非难学的一门课程。
⑵ 明天我可能看电影也可能逛公园。
⑶ 尽管他有病但他仍坚持工作。
⑷ 倘若他病了他就不参加这次会议。
⑸ 一个数是偶数的充要条件是该数能被2整除。
解 ⑴设p：离散数学是难学的一门课程。则命题符号化为 。其中“…并非…”逻辑含义上表示否定。
⑵设p：明天我看电影；q：明天我逛公园。则命题符号化为 。其中“…可能…也可能…”在逻辑上具有析取的含义。
⑶设p：他有病；q：他坚持工作。则命题符号化为 。其中“尽管…但…”具有合取的逻辑含义。
⑷设p：他病了；q：他不参加这次会议。则命题符号化为 。其中“倘若…就…”与逻辑上的蕴涵具有相同的含义。
⑸设p：一个数是偶数；q：一个数能被2整除。则命题符号化为 。其中“…的充要条件是…”在逻辑上表示等价的含义。
⒉ 两个逻辑上完全没有联系的命题可以加以联结词形成复合命题。
例1.1-5 ⑴p：2+3=5；q：有的人可以长生不老。则 仍是一个命题，它表示的含义是：“2+3=5”并且有的人可以长生不老。虽然p是真命题，但显然q的真值为假，所以根据合取联结词的定义 是一个假命题。
⑵在例1.1-3⑶中，令r表示“3+2<4”，s表示“早上太阳将从西边出来”，则该语句符号化为： 。由于r真值为假，所以整个命题的真值为真。
⒊ 自然语言中的“或”应注意加以区别。自然语言中的“或”有“可兼或”和“不可兼或”之分，前者在逻辑上就是析取，后者可转换后符号化。
例1.1-6 符号化下列命题。
⑴今天打雷或下雨。
⑵他明天到北京或到广州。
解 设p：今天打雷；q：今天下雨；r：他明天到北京； s：他明天到广州。
⑴中的“或”是“可兼或”，也就是说可以打雷，也可以下雨，还可以既打雷又下雨，所以命题符号化为： ；
⑵中的“或”是“不可兼或”，因为他只能到一个地方，所以不能用逻辑联结词 来符号化它，我们可以转换为“他明天到北京且不到广州或者他明天到广州且不到北京”来符号化：
⒋ 对蕴含要注意区分前件与后件。
例1.1-7 符号化下列命题。
⑴只要天下雨，我就坐公共汽车上班。
⑵只有天下雨，我才坐公共汽车上班。
⑶我是坐公共汽车上班的，因为天下雨了。
解 设p：天下雨； q：我坐公共汽车上班。
则⑴符号化为： ，因为p是q的充分条件；
⑵符号化为： ，因为p是q的必要条件；
⑶符号化为： ，原因同⑵。
⒌ 在符号化命题时，需要注意复合命题和原子命题的区别。
例1.1-8符号化下列命题。
⑴张刚和张强都是三好学生。
⑵张刚和张强是同桌。
解 ⑴是应用合取联结词联结“张刚是三好学生”和“张强是三好学生”组成的复合命题，若设p：张刚是三好学生；q：张强是三好学生；则可符号化为： 。
⑵仅是原子命题，“和”在这里连接的是“张刚”和“张强”，因为若对语句进一步分解，“张刚是同桌”、“张强是同桌”都不再是命题，故可符号化为r。
⒍ 逻辑联结词也称为逻辑运算符，可以规定相应的运算次序。
规定逻辑联结词的优先级从高到低依次为： ， ， ， ， ，并可以用“（ ）”来改变运算的优先次序。求复合命题的真值时，先运算括号内的部分，没有括号限制的按优先级从高到低的顺序运算。对于同一优先级或同一个联结词，按从左到右的顺序运算。
例1.1-9 符号化下列命题，并按照逻辑运算顺序求其真值。
⑴如果飞机速度没有汽车快，并且在二进制数运算中01+10=11，那么地球是静止的或者人是可以长生不老的。
⑵如果人可以长生不老或者在二进制数运算中01+10=11，那么汽车比飞机速度快或者地球是静止的。
解 设p：飞机比汽车速度快；q：在二进制数运算中01+10=11；r：地球是静止的；
s：人可以长生不老。
则⑴符号化为： 。因为p、q真值为1，所以 真值为0， 真值为0，故其真值为1。⑵可符号化为： 。因为p、q真值为1，r、s真值为0，所以 真值为1， 真值为0， 真值为0，故其真值为0。
习题1.1
1.1-1.判断下列语句是否是命题,为什么?若是命题请说明是真命题还是假命题?
⑴a+b。
⑵x>0。
⑶你说什么？
⑷今天天气多好呀！
⑸我明天或者后天去郑州。
⑹我明天去郑州或后天去郑州是谣传。
⑺一个整数为偶数当且仅当它能被2整除。
⑻这个命题是假的。
⑼太阳是不会发光的。
1.1-2.判断下列语句是否是命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。
⑴他们明天或者后天去百货公司。
⑵你能告诉我我什么时候一定会死吗？你不能！
⑶如果这个语句是命题，那么它就是个假命题。
⑷李刚和李春是兄弟。
⑸王海和李春在学习。
⑹只要努力学习，就一定能取得优异成绩。
⑺李春对李刚说：“今天天气真好呀！”
⑻如果你想中奖，你就得买奖券；如果你买奖券，你就可能中奖。
⑼你知道这个是真命题还是假命题就请告诉我！
⑽王海不是女孩子。
1.1-3.设p表示命题“李春迟到了”，q表示命题“李春错过了考试”，r表示命题“李春通过了考试”。请将下列命题翻译成自然语言（汉语）。
⑴ ；⑵ ；⑶ ；⑷ 。
1.1-4.设p表示命题“天下大雨”，q表示命题“他乘公共汽车上班”，r表示命题“他骑自行车上班”。请将下列命题符号化。
⑴如果天不下大雨，他乘公共汽车上班或者骑自行车上班。
⑵只要天下大雨，他就乘公共汽车上班。
⑶只有天下大雨，他才乘公共汽车上班。
⑷除非天下大雨，否则他不乘公共汽车上班。
1.2 命题公式及其分类
1.2.1 命题公式
在上一节例1.1-1中，已经看到⑸“ ”是陈述句，但由于x、y不确定，使得整个语句没有确定的真值，故不是命题。但是，若给定x、y一组确定的值，其真假值也就确定了。
我们把这种本身并非原子命题，但给其赋予一定的具体内容后便可成为原子命题的陈述句称为命题变元(Propositional Variable)，命题变元与初等数学里的变量类似，不过命题变元只能取值1（真）或0（假）。而原子命题则相应地称为命题常元(Propositional Constant)。命题常元和命题变元我们都用小写英文字母p,q,r,…表示，在必要的时候我们可以根据上下文加以判断。
在符号形式的命题中，代表原子命题的符号，有的代表命题常元，有的代表命题变元，因此对应的命题符号串的就不一定是命题了，我们称之为命题合式公式，当使用联结词集{Ø，Ù，Ú，®，«}时，合式公式定义如下。
定义1.2-1 ⑴单个命题常元（0，1）或单个变元p，q，r，…，pi，qi，ri，…等是命题合式公式，并称之为原子命题合式公式；
⑵若A是命题合式公式，则 也是命题合式公式；
⑶若A、B是命题合式公式，则 ， ， ， 也是命题合式公式；
⑷只有有限次地应用⑴─⑶组成的符号串才是命题合式公式。
今后，我们将命题合式公式称为命题公式(Propositional Formula)或简称公式。
例如， , 等是公式。但 , 等不是公式。
从命题公式的定义可以看出，我们可以构造出结构复杂的命题公式，为了讨论结构复杂的命题公式的真值变化情况，我们给出命题公式层次的定义。
定义1.2-2 ⑴若A是单个命题常元或命题变元，则称A是0层公式；
⑵称A是n+1( )层公式是指A符合下列情况之一：
① ，其中B为n层公式；
② ，其中B，C分别为i层公式、j层公式， ；
③ ，其中B，C层次及n取值同②；
④ ，其中B，C层次及n取值同②；
⑤ ，其中B，C层次及n取值同②。
⑶若A的最高层次为r，则称A是r层公式。
例如， 是2层公式, 是2层的, 则是4层公式。
1.2.2 公式的赋值及分类
定义1.2-3 设A是一个命题公式， ， ，…， 为出现在A中的全部命题变元，给 ， ，…， 各指定一个确定的真值，称为公式A关于 ， ，…， 的一组真值指派(True value assignment)，也称为对公式A的一个赋值(Value assignment)或解释(Explanation)。若指定的一个赋值使A的真值为1，则称该赋值为公式A的成真赋值；若使A的真值为0，则称该赋值为公式A的成假赋值。
例如，公式 中，001（p1,p2,p3分别指派0,0,1），101,111都是其成真赋值，而000，010，011，100，111都是其成假赋值。公式 中，01（p1,p2分别指派0, 1），10，11都是其成真赋值，而00是其成假赋值。
由定义易知，含有n ( )个命题变元的命题公式，共有2n组不同的赋值。将命题公式A在所有赋值下的取值情况列表，用类似于联结词真值表的形式表示出来，称之为命题公式A的真值表。
下面给出命题公式真值表具体的构造步骤：
⑴找出公式A中含有的所有命题变元p1，p2，…，pn ，列出所有可能的赋值 (共2n种)，建议按二进制数从小到大的顺序，即按照从00…0开始到11…1的顺序列出，以避免漏写或多写。
⑵按由低到高的顺序写出各层次。
⑶对应每一个赋值，计算公式A各层次公式的真值，直到计算出公式A的真值。
例1.2-1 求下列命题公式的真值表。
⑴A=
表1.2-1
p
q
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
解 公式A的真值表如表1.2-1所示。
⑵A=
解 公式A的真值表如表1.2-2.所示。
表1.2-2
p
q
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
⑶A=
解 公式A的真值表如表1.2-3所示。
表1.2-3
p
q
r
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
1
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
1
1
定义1.2-4 设A为一个命题公式，
⑴若A在它的所有可能赋值下取值均为真，则称A为重言式或永真式(Tautology)；
⑵若A在它的所有可能赋值下取值均为假，则称A为矛盾式或永假式(Contradiction)；
⑶若A至少存在一个赋值是成真赋值，则称A为可满足式(Contingency)。
由定义可知，重言式一定是可满足式，但反之不成立。
给定一个命题公式，判断其类型的一种直观方法是利用命题公式真值表技术。
从公式A的真值表构造过程可以看出，若公式A所在的列（一般在真值表的最后一列）中某行的填入值为1，则表明该行所对应的公式A的赋值为成真；若填入值为0，则表明该行所对应的公式A的赋值为成假。
所以若公式A的真值表最后一列的填入值全部为1，则说明对公式A的所有赋值都是成真赋值，即公式A为重言式，如例1.2-1⑴；若A的真值表最后一列的填入值全为0，则说明对公式A的所有赋值都是成真赋值，即公式A为矛盾式，如例1.2-1⑵；若A的真值表最后一列的填入值中有0也有1，则说明对公式A的所有赋值中至少有一个是成真赋值，且存在至少一个是成假赋值，即公式A仅为可满足式，如例1.2-1⑶。
习题1.2
1.2-1.判定下列符号串是否是命题合式公式，为什么？如果是命题合式公式，请指出它是几层公式，并标明各层次。
⑴ ；
⑵ ；
⑶ ；
⑷ ；
⑸ 。
1.2-2.指出下列公式的层次，并构造其真值表。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.2-3 构造下列公式的真值表，并据此说明哪些是其成真赋值,哪些是其成假赋值。
⑴ ；
⑵ ；
⑶ 。
1.2-4 构造下列公式的真值表,并据此说明它是重言式、矛盾式或者仅为可满足式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.3 等值演算
1.3.1 基本等值式
给定n ( )个命题变元，按照命题公式的形成规则，可以形成多个不同形式的命题公式。对其中许多很长、很复杂的公式，如果用真值表方法来研究，就需要作出很大的一张表。但是，如果针对我们所关注的赋值和最终一列来讲，这些真值表有许多其实是相类同的。如 时， 、 和 的真值表在相同的赋值下，最后一列的填入值都是对应相同的。
定义1.3-1 设A、B是两命题公式，若等价式 是重言式，则称A与B逻辑等值(Logical Equivalence)，记作 。
判断两命题公式是否等值，可应用真值表的方法， 的真值表的最后一列的填入值若全为1，则 为永真式，即A与B等值。当然，也可以通过真值表中公式A、B所在的列的填入值是否对应相同来判定，若相同则说明A与B是等值的，否则就不是等值的。
例1.3-1 判断 与 是否等值。
解 根据题义及两个命题公式是否等值的判定方法做真值表如表1.3-1所示。
表1.3-1
p
q
0
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
0
1
0
0
1
可以看到，真值表最后一列的填入值全部为1，故 。当然我们也可以不做 这一列，仅从 和 所在的列在所有可能赋值下，填入值均对应相同，可得到 和 是等值的结论。
除了用真值表验证 和 等值外我们还可用真值表验证许多等值式，主要有下面一系列公式，我们可以当作定律来运用。
等值演算中的部分等值运算律：
交换律 ⑴ ⑴′
结合律 ⑵ ⑵′
分配律 ⑶
⑶′
双重否定律 ⑷
等幂律 ⑸ ⑸′
吸收律 ⑹ ⑹′
零律 ⑺ ⑺′
同一律 ⑻ ⑻′
排中律 ⑼ 矛盾律 ⑼′
德•摩根律 ⑽ ⑽′
蕴含等值式 ⑾
等价等值式 ⑿
假言易位 ⒀
归谬论 ⒂
这里A、B、C代表任意命题公式。
有了这些公式，我们就可以与初等代数中有理式一样进行演算，这种方法可以得到更多的等值公式。在判断一个命题公式是否重言式、矛盾式时就可以通过等值演算来考查公式是否等值于1或0。这个推演过程就是我们所说的等值演算。
1.3.2 等值演算
在等值演算的过程中我们还会不断地用到下面的规则。
定理1.3-1 （置换规则）设 是含公式A的命题公式， 是用公式B置换了 中的A之后得到的命题公式，如果 ，则 。
证明 设 ， ，…， 是公式 和 中出现的全部命题变元，因为A、B分别是 、 中一部分合式公式，所以A、B中所出现的命题变元都包含在 ， ，…， 之中，又因为 ，故对 ， ，…， 的任一种赋值，A、B的取值均相同，自然 、 取值相同，故 。
例1.3-2 ⑴证明
证明
(蕴含等值式)
(蕴含等值式)
(结合律)
(德•摩根律)
(蕴含等值式)
⑵证明
证明
（分配律）
（排中律）
（同一律）
例1.3-3 判别下列公式的类型。
⑴
解
（分配律）
（矛盾律）
（同一律）
（德•摩根律）
（结合律）
（排中律）
（零律）
故原公式 为永真式。
⑵
解
（排中律、矛盾律）
（零律）
（蕴含定义）
故原公式 为矛盾式。
例2-3.4 试将下面的语句化简：情况并非如此，如果他不来那么我也不去。
解 设p：他来；q：我去；
则语句符号化为：
化简公式：
故上述语句可简化为：我去了但他没有来。
例1.3-5 将下面用程序语言写成的一段程序化简：if A then if B then X else Y else if B then X else Y。
解 画出流程图如图1.3-1所示。
开始
A
B
B
X
Y
结束
T
T
T
F
F
F
图1.3-1
开始
B
X
Y
T
F
结束
图1.3-2
将程序语言写成如下的命题公式：
[A®((B®X)Ù(ØB®Y))]Ù[ØA®((B®X)Ù(ØB®Y))]
化简后得： (B®X)Ù(ØB®Y)
于是，程序可化简成：if B then X else Y。
程序流程图可简化为如图2-3.2所示。
可以看出，整个语句中执行X的条件其实就是 ，执行Y的条件其实就是ØB。
习题1.3
1.3-1 用真值表方法证明下列各等值式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.3-2.证明下列等值式。
⑴ ；
⑵ ；
⑶ ；
⑷ ；；
⑸ ；
⑹ 。
1.3-3.用等值演算的方法化简下列公式。
⑴ ；⑵ ；⑶ ；⑷ 。
1.3-4.用真值表方法判断下列公式的类型。
⑴ ；
⑵ ；
⑶ ；
⑷ ；
⑸ ；
⑹ 。
1.3-5.尽可能简单地写出下列语句的否定。
⑴他若努力学习则会通过考试。
⑵当且仅当水温暖时他游泳。
⑶如果天冷，他则穿外套但不穿衬衫。
⑷如果他学习，那么他将上清华大学或者北京大学。
1.3-6.张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，问到底谁说真话，谁说假话。
1.3-7.符号化下面问题中的前提和结论，并验证从前提到结论的推理正确性。
前提：
⑴如果甲得到冠军，则乙或者丙将得到亚军；
⑵如果乙得到亚军，则甲不能得到冠军；
⑶如果丁得到亚军，则丙不能得到亚军；
⑷甲得到了冠军。
结论：丁不能得到亚军。
*1.4 其他联结词及功能完备集
1.4.1 其它常用联结词介绍
在命题逻辑的研究中，除了前面介绍的五个逻辑联结词外，还有其它一些常用的联结词，它们都有其独特的一面和应用。
定义1.4-1 不可兼或通常用符号“ ”表示，其真值表如表1.4-1所示。由真值表可知
它满足以下性质：
⑴ ；
⑵ 交换律： ；
⑶ 结合律： ；
⑷ 分配律： 。
这些性质可以采用真值表的方法证明。其中⑷指出了联结词“ ”与联结词“ ”、“ ”和“ “之间的联系。这表明含有“ ”的公式可以通过“ ”、“ ”和“ ”表达。
表1.4-1
p
q
0
0
0
0
1
1
1
0
1
1
1
0
表1.4-2
p
q
0
0
1
0
1
1
1
0
1
1
1
0
定义1.4-2 与非联结词，通常用符号“ ”表示，其真值表如表1.4-2所示， 为假当且仅当p、q均为真。
(表1.4-1)
联结词“ ”一般满足交换律，不满足分配律。
联结词“ ”与其他联结词的关系主要有：
⑴ ；
⑵ （自反否定律）；
⑶ ；
⑷ ；
定义1.4-3 或非联结词，通常用符号“ ”表示，其真值表如表1.4-3所示， 为真当且仅当p、q均为假。
和联结词“ ”类似，或非联结词“ ”也一般满足交换律，不满足结合律。
或非联结词“↓”与其它联结词之间的关系有：
⑴ ；
⑵ （自反否定律）；
⑶ ；
⑷ ；
从“ ”和“ ”的性质可以看出，含有“ ”和“ ”公式也可用“ ”、“ ”和“ ”表达。
1.4.2 联结词的功能完备集
在上面定义的联结词中，它们之间都是有联系的，特别是这一节所定义的联结词，都是可以转换为1.1节中所研究的五个基本联结词 “ ”、“ ”、“ ”、“ ”和“ ”来表达的。而且，对于任何含有条件联结词和等价联结词的真值函数，可以通过公式转化成“ ”、“ ”、“ ”来表达。这说明在数理逻辑中，虽然为了应用方便我们定义一些实用的联结词，但通过理论分析可以看出，这并不是必要的。
表1.4-3
p
q
0
0
1
0
1
0
1
0
0
1
1
0
定义1.4-5 设 是联结词的集合，如果对于任意一个真值函数，均存在一个与之等价的真值函数，而且后者仅含有 中的联结词，则称 是联结词的功能完备集。
在理论上与应用上通过选用不同的功能完备集，可以方便地对真值函数类进行研究。
首先，{ ， ， ， ， }是最常用的功能完备集。联结词集{ ， ， }是一个重要的功能完备集，使用该功能完备集来表达的真值函数系统，常称为Boole代数系统；在编码理论中，自然地要用到功能完备集{ ， }表达的真值函数系统，它也称为Boole代数系统。另外在研究逻辑系统的演绎和推理时，{ 、 }是一个重要的功能完备集。在制造大规模集成电路的芯片中完备集{ }和{ }都有广泛的应用。
所有的这些功能完备集都可以通过真值表利用定义验证。
在进一步的研究中，会遇到极小功能联结词集的提法，在此我们只简单说明其含义。
设 为联结词集合，若 中存在一个联结词可以由 中的其他联结词表示，则称该联结词为联结词集 中的冗余联结词，否则称为独立联结词。
定义1.4-6 所谓某个联结词集合 为极小功能完备联结词集是指 满足下面条件：
⑴ 是一个功能完备集；
⑵ 中没有冗余联结词。
例如，联结词集{ }和联结词结{ }都是极小功能完备集；联结词集{ 、 }也是极小功能完备集；但是联结词集{ ， ， }就不是极小功能完备集，因为{ ， }和{ ， }都仍然是功能完备集。而{ }、{ }、{ }不是极小功能完备集，因为它们根本就不是功能完备的。
应该说明，寻求极小功能完备集，不是个理论性问题，而主要是为了满足工程实践中的需要。但是，一般情况下不至于因联结词的数目减少或者增多使公式形式变得复杂。我们常采用能完备集：“ ”、“ ”、“ ”、“→”和“↔”五个基本联结词构成的联结词集合。但这个完备集不是极小功能完备集。
习题1.4
1.4-1 符号化下面两个命题，要求细化到原子命题，并且只能用一个联结词。
⑴或者明天下雨或者后天下雨。
⑵明天我将去北京或者去上海。
1.4-2 将下列公式进行转化，使之只含有{ }中的联结词。
⑴ ；
⑵ ；
⑶ 。
1.4-3 已知{ }是功能完备联结词集，试证明{ }也是功能完备联结词集。
1.4-4 已知 是极小功能完备集，证明 和 都是极小功能完备集。
1.5 对偶与范式
1.5.1 对偶
在1.3节中介绍的基本等值式中多数公式是成对出现，这些成对出现的公式通常称为对偶的。
若命题公式A中只出现联结词“ ”、“ ”或“ ”，则称它是受限命题公式。
定义1.5-1 在受限命题公式A中，将“ ”换成“ ”，“ ”换成“ ”，0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。
从定义不难看出，如果A*是A的对偶式，那么A也是A*的对偶式，即对偶式是相互的。所以，（A*）*=A。
例如， 与 ， 与 ， 与 均为对偶式。
关于对偶式有下面两个重要的定理。
定理1.5-1 设A和A*互为对偶式，p1，p2，…，pn是出现在A和A*中的全部命题变元，若将A和A*写成n元函数形式，则：
⑴ ⇔ A* ；
⑵ A ⇔ 。
例1.5-1 ⇔ ，则A* ⇔ ；
因为 ⇔ ⇔ ⇔ ，
所以 ⇔A* 。
因此， ⇔ØA* ，用 分别代替此公式中的
即得A ⇔ 。
定理1.5-2（对偶原理） 设A，B为两个命题公式，如果 ，则A* B*,其中A* ，B*分别是A，B的对偶式。
证明 设A(p1，p2，…，pn)⇔ B(p1，p2，…，pn)，
所以 A(p1，p2，…，pn)⇔ B(p1，p2，…，pn)；
又∵ A(p1，p2，…，pn)⇔A* ，
⇔B* ，
于是，A* ⇔ B* ，
分别用 代替 即得
A* ⇔ B* 。
例如，由 ⇔ ，可推得：
⇔ 。
1.5.2 范式
给定一个命题公式，判断它是重言式、矛盾式，还是可满足式，这类问题我们称为判定问题，在前面已经讲解过解决判定问题的两种方法，即真值表法和真值演算法，但当命题变元数目比较多时，仅用上述方法判断起来就不那么明显了。为此，我们试图将命题公式标准化。只要能使同一真值函数所对应的所有命题公式具有相同的标准型，就使得对判断两命题公式是否等值以及判断公式的类型变得规范、明显起来。
定义1.5-2由有限个命题变元或其否定构成的合取式称为原子合取式(Atomic Conjunctive Form)；
由有限个命题变元或其否定构成的析取式称为原子析取式(Atomic Disjunctive Form)。
给定命题变元p，q，则 ， ，p， 等是原子合取式， ， ， p， 等是原子析取式。通常用A1，A2，…，An来表示n个原子析（合）取式。
从定义不难看出：
一个原子析取式是重言式，当且仅当它同时含有一个命题变元及其否定；
一个原子合取式是矛盾式，当且仅当它同时含有一个命题变元及其否定。
例如，原子析取式 是重言式，原子合取式 是矛盾式。
定义1.5-3由有限个原子合取式构成的析取式称为析取范式(Disjunctive Normal Form)；
由有限个原子析取式构成的合取式称为合取范式(Conjunctive Normal Form)。
例如， 、A* 分别为析取范式和合取范式。
不难发现：
一个析取范式为矛盾式,当且仅当它的每个原子合取式都是矛盾式；
一个合取范式为重言式,当且仅当它的每个原子析取式都是重言式。
那么给定任何一个命题公式,是否都能求出与之等值的析取范式和合取范式呢?
定理1.5-3（范式存在定理） 任一命题公式都存在着与之等值的析取范式，也都存在着与之等值的合取范式。
若公式A中含有联结词→, 等，可以用基本等值式及置换原则将它们消去：
①p→q⇔┐p∨q；②p q⇔(┐p∨q)∧(p∨┐q)。
若遇到┐(┐p)形式,利用双重否定律将否定号消去：
┐(┐p)⇔p。
若遇到┐(p∧q), ┐(p∨q)等形式，利用德·摩根律将否定号内移：
①┐(p∧q)⇔┐p∨┐q；②┐(p∨q)⇔┐p∧┐q。
最后，若是求析取范式，应当利用“∧”对“∨”的分配律, 若是求取范式，应当利用“∨”对“∧”的分配律。
任一公式A通过上述三步,即得到与A等值的析取范式或合取范式。
求范式的具体步骤:
⑴将含有联结词→, 的公式转化为仅含┐、∨和∧形式的公式；
⑵否定符号的内移或消去；
⑶利用分配律得到析取范式或合取范式。
例1.5-3 求命题公式((p∨q)→r)→p的合取范式和析取范式。
解 ①求析取范式：((p∨q)→r)→p⇔┐(┐(p∨q)∨r)∨p⇔((p∨q)∧┐r)∨p
⇔(p∧┐r)∨(q∧┐r)∨p即为所求的析取范式。
再利用交换律和吸收律：(p∧┐r)∨(q∧┐r)∨p
⇔p∨(p∧┐r)∨(q∧┐r)⇔p∨(q∧┐r)也是所求的析取范式。
②求合取范式：((p∨q)→r)→p⇔((p∨q)∧┐r)∨p
⇔(p∨q∨p)∧(┐r∨p)即为所求的合取范式。
利用交换律和等幂律：(p∨q∨p)∧(┐r∨p)⇔(p∨q)∧(┐r∨p)也是所求的合取范式。
可见,与某个命题公式等值的析取范式是不唯一的，合取范式也是不唯一的。
从上面的例1.5-3可以看到，同一个命题公式的析取范式和合取范式都是不唯一的，这说明范式虽然是一种规范的形式，但还不能作为标准形式。为此，我们需要在此基础上做进一步的规范定义。
1.5.3 主范式
定义1.5-4 对于命题公式A，包含A中的每个命题变元或其否定一次且仅一次的原子合取式称为极小项。
例如， ， 等是极小项，而 ， ， 等不是极小项。
下面我们就仅含有2个命题变元的情形来说明一种极小项的抽象简明的表示方法。
2个命题变元p，q可形成4个极小项，如果将命题变元看成1，命题变元的否定看作0，那么每个极小项就对应一个二进制数，自然也对应一个十进制数。不难看出，二进制数正是该极小项的成真赋值，不妨用对应的十进制数作为该极小项抽象表示法的下角码。
4个对应情况如表1.5-1所示：
表1.5-1
极小项
成真赋值
对应十进制数
简明表示
00
0
m0
01
1
m1
10
2
m2
11
3
m3
一般地，n个命题变元共产生2n个极小项，逐个记作m0，m1，…， 。
定义1.5-5 如果命题公式A的析取范式中的原子合取式全是极小项，则称该析取范式为A的主析取范式(Principal Disjunctive Normal Form)。
定理1.5-4 任何命题公式的主析取范式都存在且唯一。
求主析取范式的步骤可归纳如下：
⑴求出A的析取范式 ；
⑵利用同一律，去掉析取范式 中所有永假的原子合取式；
⑶利用等幂律，将析取范式 中重复出现的合取项或者命题变元合并；
⑷利用同一律，若合取项中未出现命题变元 ，则添加 为其一个合取项，并用分配律展开；
⑸再次合并相同的项和消去产生矛盾的项，然后按照下角标从小到大顺序排列，并用 形式表示之，如 ，用 表示等。
例1.5-4 求 的主析取范式。
解 由例1.5-3知 ⇔
⇔
⇔
⇔m4 m5 m6 m7 m2 m6⇔m2 m4 m5 m6 m7
⇔
由极小项的定义可知，上式中2，4，5，6，7对应的二进制数010，100，101，111为原公式的成真赋值，而没出现的m0，m1，m3的下角码0，1，3对应的二进制数000，001，011为原公式的成假赋值。因而，知道了一个命题公式的主析取范式，可立即写出A的真值表。
反之，若作出了A的真值表，找出所有的成真赋值，并将其二进制表示对应的十进制数作为下角码得到极小项，并做析取即为A的主析取范式。
例1.5-5 试由 的真值表求出它的主析取范式。
解 作 的真值表如表1.5-2所示：
表1.5-2
p
q
r
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
可见， 的成真赋值为001，011，101，110，111，其对应极小项为m1，m3，m5，m6，m7。故其主析取范式： ⇔m1 m3 m5 m6 m7⇔∑(1，3，5，6，7)。
主析取范式可用于解决以下问题：
①判断两命题公式是否等值。由于任何命题公式的主析取范式都是唯一的，因而若 ，说明A与B有相同的主析取范式，反之，若A、B有相同的主析取范式，必有 。
②判断命题公式的类型。设A是含n个命题变项的命题公式，A为重言式，当且仅当A的主取范式中含全部2n个极小项；A为矛盾式，当且仅当A的主析取范式中不含任何极小项，可设A的主析取范式为0；当然，若A主析取范式中至少含一极小项，则A是可满足式。
③求命题公式的成真或成假赋值。若A是一个含有n个变元的命题公式，则A的主析取范式的下角码所对应的n位二进制数都是命题公式A的成真赋值，而其余的n位二进制数都是命题公式A的成假赋值。
和前面讲过析取范式和合取范式一样，除了主析取范式外，还有其对偶形式，即主合取范式，为此首先给出极大项的定义。
定义1.5-6 对于命题公式A，包含A中的每个命题变元或其否定一次且仅一次的原子析取式称为A的极大项。
例如， ， 等是极大项，而 ， 等不是极大项。
同极小项类似，n个命题变元可产生2n个极大项，每个极大项对应一个二进制数，若将命题变元看成0，命题变元的否定看作1，则该二进制数为对应的极大项的成假赋值，可取其对应十进制数作为其简明抽象表示的下角码。如n=2时，对应关系如表1.5-3所示：
表1.5-3
极小项
成假赋值
对应十进制数
简明表示
00
0
M0
01
1
M1
10
2
M2
11
3
M3
定理1.5-4 极小项与极大项之间存在下面的关系：
⇔Mi ， ⇔mi。
定义1.5-7 如果命题公式A的合取范式中的原子析取式全是极大项，则称该合取式为主合取范式(Principal Conjunctive Normal Form)。
可以证明：任一命题公式A的主合取范式一定存在且唯一的。
求一命题公式A的主合取范式与求主析取范式的步骤类似，只是在第⑶步中，应添加 为析取式中的一个析取项，然后利用分配律，其他步骤一样。
例1.5-6 求 的主合取范式。
解 ⇔ （合取范式）
⇔
⇔
⇔
⇔M0 M2 M4⇔∏（0，2，4），其中∏表示合取。
如果求出了公式A的主析取范式，可以直接用主析取范式求出其主合取范式（反之亦然）。下面通过例子来说明这种方法，在例1.5-5中我们求得 的主析取范式为：
⇔m1 m3 m5 m6 m7
而
所以
则
公式 的主合取范式即为所求。
由A主析取范式求合取范式的步骤为：
⑴求出A的主析取范式中没有出现的极小项 ， ，…， ；
⑵求出与⑴中极小项下角码相同的极大项 ；
⑶由以上极大项构成的合取式就是A的主合取范式。
例1.5-7 求 的主合取范式。
解 由例1.5-4知 的主析取范式为m2 m4 m5 m6 m7
其中没有出现的极小项为m0，m1，m3，对应得极大项为 ，因此， 的主合取范式为：
当然，类似地可从主合取范式求出主析取范式，具体步骤请读者给出。
同样通过主合取范式也可以用于：
①判断公式之间是否逻辑等值；
②判断公式类型（重言式不含极大项，用1表示）；
③求成假赋值（所含极大项下角码二进制表示）或成真赋值（不含）。
习题1.5
1.5-1.写出下列公式的对偶式。
⑴ ；
⑵ 。
1.5-2.将下列公式化为析取范式和合取范式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-3.求下列公式的主析取范式和主合取范式。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-4.用真值表法求下列公式的各极小项和极大项，并写出主析取范式和主合取范式。
⑴ ； ⑵ ；
⑶ ； ⑷ 。
1.5-5.通过求主析取范式，判断下列公式的类型。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
1.5-6.通过求主合取范式证明下列各等值式。
⑴ ；
⑵ ；
⑶ 。
1.6 推理理论
1.6.1 命题的蕴含关系
推理是从前提推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则得到的命题公式。从某些给定的前提出发，按照严格定义的形式规则，推出有效的结论，这样的过程称为形式证明或演绎证明。
定义1.6-1 设 都是命题公式，若 为重言式，记作 ，则称A1，A2，…，Ak能推出结论B，或称B是前提集合{A1，A2，…，Ak}的逻辑结论(Logical consequence)或者有效结论。
同用“ ”表示“ ”为重言式类似，“ ”当且仅当“ ”是重言式。
于是，判断推理是否有效的方法就是判断重言蕴涵式的方法，比如我们前面所讲的真值表法、等值演算和主范式法等。
例1.6-1 判断如下推理是否有效。
如果天气凉快，小王就不去游泳。天气凉快。所以小王没有游泳。
解 命题符号化， p：天气凉快，q：小王去游泳，
前提：
结论：
推理的形式结构： ，要判断其推理是否有效，就是判断 是否是重言式。
①真值表法：作出 的真值表如表1.6-1所示。
由其真值表可以看出，最后一列均为1，即 重言式，所以推理有效。
②等值演算法： ⇔
⇔ ⇔
⇔ ⇔1∧1⇔1。
即 为重言式。
故推理有效。
表1.6-1
p
q
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
1
③主析取范式法： ⇔1⇔∑（0，1，2，3）为重言式，故推理是有效的。
在推理过程中，我们也可以应用已经得到的一些基本蕴含关系（或重言蕴涵式）。
1. 附加
2. 附加
3. 化简
4. 化简
5.
6.
7.
8.
9. 合取
10. 假言推理
11. 拒取式
12. 析取三段论
13. 假言三段论
14. 构造性二难推理
1.6.2 形式证明
在推理过程中，如果命题变元较多，采用真值表、等值演算和主范式方法有时不方便。为此介绍形式证明的方法。
形式证明(Formal Proof)的推理过程是一个命题序列，其中每一个命题或者是已知命题，或者是由某些前提根据推理规则推出的结论，序列的最后一个命题是需要论证的结论。
要进行正确的推理，需要使用推理规则，下面给出形式证明中的推理规则：
⑴前提引入规则P：在证明的任何步骤中，都可以引入前提。
⑵结论引入规则T：在证明的任何步骤中，在此之前证明得到的结论都可以作为后续证明的前提引入。
⑶置换规则：在证明任何步骤中，命题公式中的任何子公式都可以用与之等值的命题公式置换，如可以用 置换 等。
⑷代入规则：在证明的任何步骤中，重言式的任何一个命题变元都可以用一个命题公式代入，得到的仍是重言式。
⑸附加规则：
⑹化简规则：
⑺假言推理规则：
⑻拒取式规则：
⑼析取三段论规则：
⑽假言三段论规则：
⑾等价三段论规则：
⑿构造性二难规则：
⒀合取引入规则：
下面我们通过例题来说明如何构造形式证明。
例1.6-2 给出下列的推理的形式证明： ， ， ， ， q。
前提： ， ， ， ，
结论：q
证明 ① P
② P
③ T①②拒取式
④ P
⑤r T③④假言推理
⑥ P
⑦ T⑤⑥拒取式
⑧ P
⑨q T⑦⑧析取三段论
①
②
③
④
⑤
⑥
⑦
⑧
⑨
①
②
⑤
④
③
⑥
⑦
图1.6-1
图1.6-2
在形式证明的实际应用中，有时候为了使证明过程给人以更清晰的认识，往往在证明后附上证明（推理）树。例如本题的证明树如图1.6-1所示。它的作法是，把证明（推理）过程中作为前提的标号作为树叶，每一步用线相连，得到的相应结论的标号作为相应的结点，直到最后一步的结论作为树根。
例1.6-3 写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。
解 符号化题目中的命题，设p：今天是星期一，q：进行英语考试，r：进行离散数学考试，s：英语老师有会。
前提： , ,p,s
结论：r
证明：① P
②p P
③ T①②假言推理
④ P
⑤s P
⑥ T④⑤假言推理
⑦r T③⑥析取三段论
由有效推理可知，今天进行离散数学考试。其证明树如图1.6-2所示。
在上面的例子中，采用前面的规则进行形式证明的方法，通常也称为直接证明法。在形式证明中，有时可采用一定的技巧，使证明过程简化。
CP规则：
证明类似 问题时，我们常采用这种方法。方法是，将结论中蕴涵前件作为一个附加前提来证明结论中蕴涵式中的后件是有效逻辑结论。
这种方法是可以保证整个推理正确的。
⇔
⇔
⇔
根据置换原则可知，上式最后一个式子为重言式与第一个式子为重言式是等价的。
通常我们把这个结论在运用于形式证明时称为CP规则。
例1.6-4 用形式证明法证明： ， ，q
前提： ， ，q
结论：
证明 ①s 附加前提引入
② 前提引入
③p ①②析取三段论
④ 前提引入
⑤ ③④假言推理
⑥q 前提引入
⑦r ⑤⑥假言推理
⑧ ①⑦CP规则
间接证明法--归谬法。
归谬法是将结论的否定作为一前提引入，通过有效推理得到矛盾，以此说明推理正确。
先补充一个概念：设A1，A2，…，Ak是k个命题公式，若A1 A2 … Ak是可满足式，则称A1，A2，…，Ak是相容的，否则，即A1ÙA2Ù…ÙAk为矛盾式则称A1，A2，…，Ak是不相容的。因
⇔
⇔
所以，若A1，A2，…，Ak， 不相容，则说明 是重言式，即B是公式A1，A2，…，Ak的逻辑结论，故应用这种方法推理构造有效。
例1.6-5 用间接证明法证明： ，p，
前提： ，p，
结论：
证明 ① P
②p P
③ T①②假言推理
④ P否定结论引入
⑤ T③④拒取式
⑥s T⑤化简
⑦ P
⑧ T⑥⑦合取
由⑧得到矛盾，根据归谬法可知推理正确。
习题1.6
1.6-1.符号化下面问题中的前提和结论,并指出推理是否正确，为什么？
前提：⑴如果这里有演出，则通行是困难的；
⑵如果他们按照指定的时间到达，则通行是不困难的；
⑶他们按照指定时间到达了。
结论：这里没有演出。
1.6-2.形式证明给出下列推理的过程的形式证明。
⑴
⑵
⑶
⑷
⑸前提：
结论： 。
1.6-3.下面的推理过程是否正确，结论是否有效，并说明理由。
① P前提引入
② T ①化简
③ P前提引入
④ T ②③假言推理
1.6-4.判断下面的推理证明过程是否正确，若不正确请指出错误所在位置及出错原因，若正确则请补足每一步所用的推理规则。
前提：
结论：
证明：① ⑴
② ⑵
③ ⑶
④ ⑷
⑤ ⑸
⑥ ⑹
⑦ ⑺
⑧ ⑻
1.6-5.用推理规则证明下列推理的正确性：如果张三努力工作，那么李四或王五感到高兴；如果李四感到高兴，那么张三不努力工作；如果刘强高兴，那么王五不高兴。所以，如果张三努力工作，则刘强不高兴。
1.6-6.已知事实如下，问结论是否有效。
前提：⑴如果天下雪，则马路就会结冰；
⑵如果马路结冰，汽车就不会开快；
⑶如果汽车开得不快，马路上就会塞车；
⑷马路上没有塞车。
结论：天没有下雪。
1.7 * 命题逻辑在门电路中的应用介绍
P
P
Q
Q
P
P
Q
P
Q
P
Q
P
Q
P
Q
图1.7-1
在自动控制系统和电子计算机中采用由电子元件组成，用信号控制的开关，我们称之为“门”。在控制系统和电子集成以及机电设计中设计出来的由“门”联结而设计出来的电路称为“门电路”。基本的门电路有三种：“或”门电路、“与”门电路和“非”门电路，其功能完全与三种基本逻辑运算“ ”、“ ”和“ ”相对应。事实上，在门电路的理论中还经常用到其他类型的门电路，如我们在讲其他联结词时曾经提到过的“或非”门、“与非”门等，这些都是可以与逻辑联结词相对应的。首先给出部分常用命题逻辑联结词与门电路对应如图1.7-1所示。
下面我们来看一个简单的自动控制电路的设计。
例1.7-1 试设计红绿灯自动控制线路，要求传感器中记数器内容Z，当 时亮绿灯，当 时亮红灯，当 时亮黄灯。
解 设p： 且p⇒L1（亮绿灯） q： 且q ⇒L2（亮红灯）
r： 且r⇒L3（亮黄灯）
因为r⇔ ⇔ ，所以控制电路如图1.7-2所示。
P
Q
L1
L2
L3
图1.7-2
对于复杂的问题，运用逻辑知识可以理出清晰的思路，使得设计电路时得心应手。
习题1.7
1.7-1 一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞机计划正确或有误的回答。由于计算机也可能发生故障，因此采用三台计算机同时复核的策略。由所给出的答案，再根据“少数服从多数”的原则作出判断，试将结果用命题公式表示，并加以简化，画出电路图。
1.8 例题解析
例1.8-1下面给出的语句是否是命题，若是命题，试给出其真值。
⑴你喜欢周杰伦吗？
⑵大家不要讲话了！
⑶2+x=5。
⑷2是素数。
⑸1是素数。
⑹如果1是素数，2就不是素数。
⑺地球之外的星球上还有生物。
⑻我生于1978年。
⑼我正在说谎！
解 本题主要考查我们对命题概念的理解。
⑴、⑵都不是陈述句，不可能是命题；⑶中包含有待赋值的x，所以也不是命题；⑷是真命题；⑸是假命题；⑹是一个复合条件命题，因为前件为假，所以它是一个真命题；
虽然⑺、⑻的真值我们还不知道，但他它是有真假的，所以也是命题；⑼虽然也是陈述句，但是它不是命题，它是一个典型的悖论。
例1.8-2 符号化下列命题公式。
⑴当我想起我母亲劳碌的身影时我就禁不住哭了。
⑵仅当我有时间并且天不下雨，我将去书店。
⑶一个正整数是素数当且仅当它只能被1和它自身整除。
⑷小李总是在图书馆看书，除非图书馆不开门或者小李有病。
⑸假如上午天不下雨，我去看电影，否则就在家里读书。
解 在数理逻辑中，命题逻辑的翻译是比较简单的，容易混淆的地方主要在于：
①“当…则…”、“仅当…才…”句型的符号化；②“…除非…”句型的符号化；③可兼或与不可兼或符号化时的分辨；④蕴涵和等价容易用反；⑤蕴涵的前件和后件的区分。
⑴设p：我想起我母亲劳碌的身影； q：我禁不住哭了。则原语句符号化为： 。
⑵设p：我有时间；q：天不下雨；r：我去书店。则原语句符号化为： 。
⑶设p：一个正整数是素数；q：一个正整数能被1整除； r：一个正整数能被它自身整除； s：一个正整数能被除了1和它自身之外的正整数整除。则原语句可符号化为：
。
⑷设p：小李在图书馆看书；q：图书馆开门；r：小李没病。则原语句符号化为：
。
⑸设p：上午天下雨；q：我去看电影； r：我在家里读书。
则原语句可符号化为：
。
例1.8-3 给定命题公式 的主析取范式中含有如下极小项： ， ， ， 。请写出 主合取范式并回答下列问题， 主合取范式中含有（ ）个极大项，成真赋值个数有（ ）个，成假赋值个数有（ ）个。
解 这是一类很典型的题目。对于求命题公式的极小项和极大项、成真赋值和成假赋值与求命题公式的主范式是同一种问题。
由已知条件可很容易地看出命题公式A的主析取范式中的极小项为m7，m6，m5，m2，其主析取范式为 ，故其主合取范式可根据与主析取范式之间的关系直接写出为 ，所以极大项即为M0，M1，M3，M4，共4个极大项。而极小项和极大项对应的二进制数就是公式的成真赋值和成假赋值，故成真赋值为010，101，110，111共4个，成假赋值为000，001，011，100共4个。
例1.8-4 命题公式 的对偶式为（ ）。
（A） （B） （C） （D）
解 对于对偶式是在仅含联结词“ ”，“ ”和“ ”的命题公式中“ ”与“ ”置换、0与1置换而得到的，因此，求像本题这样含由其它联结词的公式的对偶式时，就先等值转化成仅含联结词“ ”，“ ”和“ ”的命题公式来求。
∵ ⇔ ∴其对偶式为： ⇔ ，
故选择答案（C）。
例1.8-5 一个公安人员审查一件盗窃案，已知事实如下：
⑴甲或乙盗窃了录音机；
⑵若甲盗窃了录音机，则作案时间不能发生在午夜前；
⑶如乙的证词正确，则午夜时屋里的灯光未灭；
⑷若乙的证词不正确，则作案时间发生在午夜之前；
⑸午夜时屋里的灯光灭了。问到底是谁盗窃了录音机？
解 题目中的命题符号化，p：甲盗窃了录音机， q：乙盗窃了录音机， r：作案时间在午夜前，s：乙的证词正确，t：午夜时灯光未灭。
前提： ， ， ， ，
结论：根据逻辑推理求出
推理过程：① P
② P
③ T①②拒取式
④ P
⑤r T③④假言推理
⑥ P
⑦ T⑤⑥拒取式
⑧ P
⑨q T⑦⑧析取三段论
由⑨说明是乙盗窃了录音机。
例1.8-6 判断下式是否为重言式。 。
解 对于判断一个命题公式是重言式、矛盾式还是可满足式，我们可以采用的方法很多。利用等值演算法，真值表法和化为主范式的方法都很有效，并且也是我们经常采用的，对本题当然也适合。对真值表方法是很基本的，主要在于我们要细心，并且对于本题这样出现命题变元较多的，作出的表会很大；对于主范式和等值演算法的道理是一样的，就是利用我们已经掌握的等值式逐步演算，关键在于我们要掌握好等值式，对于本题命题公式比较复杂，用起来也有一定的难度，那么是否可以从公式的形式找到一种更好的方法呢？事实上，在做题目是我们要善于发现题目的特点，像这个题我们看到公式有反复的蕴涵联结词，并且是要判断是否是重言式，所以我们可以采用构造形式证明的方法证明：
，而由CP规则就是要证明：
构造形式证明：
① P
② P附加前提引入
③ T①蕴涵等值式，置换
④ T③添加
⑤ T④蕴涵等值式，置换
⑥ T②蕴涵等值式，置换
⑦ T⑥添加
⑧ T⑦蕴涵等值式，置换
⑨ P附加前提引入
⑩ P⑤⑧⑨构造性二难推理
由上面的推理过程可知推理有效，根据CP规则可知所给公式是重言式。
复习题二
1.下列句子中，哪些是命题？如果是命题，指出其是简单命题还是复合命题，并判断真假。
⑴中国有四大发明。
⑵吸烟请到吸烟室去！
⑶ 是无理数！
⑷李春和李红是姐妹。
⑸李春在说谎。
⑹如果3是偶数，那么中国人的母语是汉语。
⑺只要你抽烟，你就很容易得病。
⑻只有今天是星期一，明天才是星期二。
⑼李春这个学期《离散数学》和《数据结构》都考了100分。
⑽下雪路滑，他迟到了。
⑾不经一事，不长一智。
⑿一朝被蛇咬，十年怕井绳。
2.符号化第1题中的复合命题，要求细化到原子命题。
表2-1
p
q
r
s
A（其他为0）
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
3.设p：李春生于1979年，q：李春生于1980年，说明命题“李春生于1979年或生于1980年”既可以符号化为“ ”，又可以符号化为“ ”的理由。4.在什么情况下，下面的一段话是真的。
说李刚不会拳击或李春不会唱歌是正确的，而说如果李刚会唱歌，李春就会拳击是不正确的。
5.命题公式A包含4个命题变元：p，q，r，s，其真值表如表2-1所示：
⑴写出A的极小项和极大项；
⑵写出与A等值的主析取范式和主合取范式；
⑶写出与A等值的析取范式的最简形式。
6.证明下列命题的等值关系。
⑴ ；
⑵ ；
⑶ ；
⑷ 。
7.用真值表、等值演算和求主范式的方法判断下面公式的类型。
⑴ ；
⑵ ；
⑶ 。
8.证明下列推理。
⑴ ；
⑵前提： ， ， ， ，
结论： ；
⑶ ， ， 。
9.用推理规则说明：
， ， 是否能同时成立。
10.用真值表、等值演算、求主范式和构造推理证明下面的推理正确。
只要小王曾经到过受害人的房间并且11点以前没有离开，小王就犯了谋杀罪。小王曾经到过受害者房间。如果小王在1点以前离开，看门人会看到他。看门人没有看到他。所以小王犯了谋杀罪。
11. 有一位逻辑学家被一伙强盗绑架。强盗头目天生好玩刺激的游戏，他把逻辑学家拘于有两个门的牢狱，两个门中其中一个是生门，一个是死门。如果从生门出去将可以安全离开，如果从死门出去，将立即处死。但是到底哪个是生门，哪个是死门不可能告诉逻辑学家。
在每个门旁强盗头目各派有一名强盗把守，这两名强盗一个所说的每一句话都是假话，另外一个则说的每一句话都是真话，当然到底哪个是说假话的哪个是说真话的不可能让逻辑学家知道。现在强盗头目给逻辑学家一次可能生还的机会，他允许逻辑学家问两个守门强盗中的一个且只能问其中一个，并且被问的强盗只能回答一次且只能回答一句话。现在逻辑学家可以安全的出去吗？
(提示：逻辑学家对A（其中任意一个门旁的强盗）说“我问B（即另一个门旁的强盗）‘你身边的门是生门吗？’，他说‘不是’，你说他回答的正确吗？”)