形式逻辑是以思维形式结构及其规律进行研究的一门工具性学科。
思维的形式结构包括概念、判断和推理。其中，概念是思维的基本单位；判断是通过概念对事物是否具有某种属性进行肯定或否定的回答；由一个或者几个判断推出另一个判断的思维过程就是推理。研究推理有很多方法，其中用数学方法来研究推理的规律的学科统称为数理逻辑，这里所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑也叫符号逻辑。
我们主要介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑，首先介绍命题逻辑。
凡具有真假的陈述句就称为命题(Proposition)。命题通常用小写英文字母表示。
例1.1-1⑴3能被2整除。
⑵C++是一门计算机高级程序语言。
⑶请关上门!
⑷你好吗？
⑸。
其中⑴是命题，对它进行判断的结果是真的；⑵是命题，是假的；⑶、⑷不是陈述句，故不是命题；⑸是陈述句，但由于x、y不确定，使得整个句子可真可假，即没有确定的判断结果，故不是命题；⑹是一个悖论，无法确定其真假，所以不是命题。
例如，在例1.1-1中，⑴的真值为假，故为假命题；⑵的真值为真，所以是真命题。
例1.1-2⑴这盘菜太咸。
⑵太阳系外有宇宙人。
⑶1962年2月3日晚郑州市金水区成立。
⑵是命题。虽然目前尚无法确定其真假，但从事物的本质而论，是可分辨真假的。
容易看出，例1.1-1、例1.1-2中给出的是命题的陈述句都不能进一步分解，类似这种不能再分的命题，称为原子命题(AtomicProposition)或简单命题，原子命题是命题逻辑中最基本、最小的单位。由作为原子命题的简单陈述句通过连词联结而成的命题，称为复合命题(CompoudProposition)。
例1.1-3⑴林刚和林强是三好学生。
⑵离散数学是计算机专业的一门基础课.
⑶如果3+2<4，那么太阳早上将由西边出来。
其中⑴、⑶是复合命题，⑵是原子命题。判断一个命题是否是复合命题的关键是看分解后各部分是否仍为命题。特别指出，有些在表面上互不相干的命题语句通过连词可组成复合命题，如本例中的⑶。
复合命题是用自然语言中的连词联结命题所组成的，为了便于研究，我们还需要对自然语言中的各种连词也用符号表示出来，以便得到形式化了的复合命题。在数理逻辑中，我们将这种自然语言连词的形式符号称为命题逻辑联结词(LogicalConnective)。
⑴否定(Negation)
为了更好地理解联结词所代表的含义，引入一种表格方法─真值表(TruthTable)。
如表1.1-1所示就是否定联结词的真值表。
表1.1-1
p
0
1
⑵合取(Conjunction)
合取联结词的真值表如表1.1-2所示。
⑶析取(Disjunction)
析取联结词的真值表如表1.1-3所示。
表1.1-2
表1.1-3
⑷蕴涵(含)（Implication）
蕴含联结词的真值表如表1.1-4所示。
表1.1-4
表1.1-5
⑸等价(Equivalent)
等价联结词的真值表如表1.1-5所示。
为了叙述方便，我们将用符号表示命题及其联结词的过程称为命题的符号化(Proporsitionalsignify)。
对于命题的符号化我们有必要指出以下几点：
⒈同一个命题联结词在自然语言中可能有不同的表达方法。
例1.1-4将下列命题符号化。
⑴离散数学并非难学的一门课程。
⑵明天我可能看电影也可能逛公园。
⑶尽管他有病但他仍坚持工作。
⑷倘若他病了他就不参加这次会议。
⑸一个数是偶数的充要条件是该数能被2整除。
⒉两个逻辑上完全没有联系的命题可以加以联结词形成复合命题。
例1.1-6符号化下列命题。
⑴今天打雷或下雨。
⑵他明天到北京或到广州。
解设p：今天打雷；q：今天下雨；r：他明天到北京；s：他明天到广州。
⒋对蕴含要注意区分前件与后件。
例1.1-7符号化下列命题。
⑴只要天下雨，我就坐公共汽车上班。
⑵只有天下雨，我才坐公共汽车上班。
⑶我是坐公共汽车上班的，因为天下雨了。
解设p：天下雨；q：我坐公共汽车上班。
则⑴符号化为：，因为p是q的充分条件；
⑵符号化为：，因为p是q的必要条件；
⑶符号化为：，原因同⑵。
⒌在符号化命题时，需要注意复合命题和原子命题的区别。
例1.1-8符号化下列命题。
⑴张刚和张强都是三好学生。
⑵张刚和张强是同桌。
⒍逻辑联结词也称为逻辑运算符，可以规定相应的运算次序。
例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.判断下列语句是否是命题,为什么若是命题请说明是真命题还是假命题
⑴a+b。
⑵x>0。
⑶你说什么？
⑷今天天气多好呀！
⑸我明天或者后天去郑州。
⑹我明天去郑州或后天去郑州是谣传。
⑺一个整数为偶数当且仅当它能被2整除。
⑻这个命题是假的。
⑼太阳是不会发光的。
1.1-2.判断下列语句是否是命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。
⑴他们明天或者后天去百货公司。
⑵你能告诉我我什么时候一定会死吗？你不能！
⑶如果这个语句是命题，那么它就是个假命题。
⑷李刚和李春是兄弟。
⑸王海和李春在学习。
⑹只要努力学习，就一定能取得优异成绩。
⑻如果你想中奖，你就得买奖券；如果你买奖券，你就可能中奖。
⑼你知道这个是真命题还是假命题就请告诉我！
⑽王海不是女孩子。
⑴；⑵；⑶；⑷。
⑴如果天不下大雨，他乘公共汽车上班或者骑自行车上班。
⑵只要天下大雨，他就乘公共汽车上班。
⑶只有天下大雨，他才乘公共汽车上班。
⑷除非天下大雨，否则他不乘公共汽车上班。
⑵若A是命题合式公式，则也是命题合式公式；
⑶若A、B是命题合式公式，则，，，也是命题合式公式；
⑷只有有限次地应用⑴─⑶组成的符号串才是命题合式公式。
今后，我们将命题合式公式称为命题公式(PropositionalFormula)或简称公式。
例如，,等是公式。但,等不是公式。
从命题公式的定义可以看出，我们可以构造出结构复杂的命题公式，为了讨论结构复杂的命题公式的真值变化情况，我们给出命题公式层次的定义。
定义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层公式。
例如，公式中，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各层次公式的真值，直到计算出公式A的真值。
例1.2-1求下列命题公式的真值表。
⑴A=
表1.2-1
q
解公式A的真值表如表1.2-1所示。
⑵A=
解公式A的真值表如表1.2-2.所示。
表1.2-2
⑶A=
解公式A的真值表如表1.2-3所示。
表1.2-3
r
定义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.判定下列符号串是否是命题合式公式，为什么？如果是命题合式公式，请指出它是几层公式，并标明各层次。
⑴；
⑵；
⑶；
⑷；
1.2-2.指出下列公式的层次，并构造其真值表。
⑷。
1.2-3构造下列公式的真值表，并据此说明哪些是其成真赋值,哪些是其成假赋值。
⑶。
1.2-4构造下列公式的真值表,并据此说明它是重言式、矛盾式或者仅为可满足式。
定义1.3-1设A、B是两命题公式，若等价式是重言式，则称A与B逻辑等值(LogicalEquivalence)，记作。
判断两命题公式是否等值，可应用真值表的方法，的真值表的最后一列的填入值若全为1，则为永真式，即A与B等值。当然，也可以通过真值表中公式A、B所在的列的填入值是否对应相同来判定，若相同则说明A与B是等值的，否则就不是等值的。
例1.3-1判断与是否等值。
解根据题义及两个命题公式是否等值的判定方法做真值表如表1.3-1所示。
表1.3-1
可以看到，真值表最后一列的填入值全部为1，故。当然我们也可以不做这一列，仅从和所在的列在所有可能赋值下，填入值均对应相同，可得到和是等值的结论。
除了用真值表验证和等值外我们还可用真值表验证许多等值式，主要有下面一系列公式，我们可以当作定律来运用。
等值演算中的部分等值运算律：
分配律⑶
双重否定律⑷
蕴含等值式⑾
等价等值式⑿
假言易位⒀
归谬论⒂
这里A、B、C代表任意命题公式。
有了这些公式，我们就可以与初等代数中有理式一样进行演算，这种方法可以得到更多的等值公式。在判断一个命题公式是否重言式、矛盾式时就可以通过等值演算来考查公式是否等值于1或0。这个推演过程就是我们所说的等值演算。
在等值演算的过程中我们还会不断地用到下面的规则。
定理1.3-1（置换规则）设是含公式A的命题公式，是用公式B置换了中的A之后得到的命题公式，如果，则。
例1.3-2⑴证明
证明
(蕴含等值式)
(结合律)
⑵证明
（分配律）
（排中律）
（同一律）
例1.3-3判别下列公式的类型。
⑴
解
（矛盾律）
（结合律）
（零律）
故原公式为永真式。
⑵
（排中律、矛盾律）
（蕴含定义）
故原公式为矛盾式。
例2-3.4试将下面的语句化简：情况并非如此，如果他不来那么我也不去。
解设p：他来；q：我去；
则语句符号化为：
化简公式：
故上述语句可简化为：我去了但他没有来。
例1.3-5将下面用程序语言写成的一段程序化简：ifAthenifBthenXelseYelseifBthenXelseY。
解画出流程图如图1.3-1所示。
开始
A
B
X
Y
结束
T
F
图1.3-1
图1.3-2
将程序语言写成如下的命题公式：
于是，程序可化简成：ifBthenXelseY。
程序流程图可简化为如图2-3.2所示。
1.3-1用真值表方法证明下列各等值式。
1.3-2.证明下列等值式。
⑷；；
⑸；
⑹。
1.3-3.用等值演算的方法化简下列公式。
1.3-4.用真值表方法判断下列公式的类型。
1.3-5.尽可能简单地写出下列语句的否定。
⑴他若努力学习则会通过考试。
⑵当且仅当水温暖时他游泳。
⑶如果天冷，他则穿外套但不穿衬衫。
⑷如果他学习，那么他将上清华大学或者北京大学。
1.3-6.张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，问到底谁说真话，谁说假话。
1.3-7.符号化下面问题中的前提和结论，并验证从前提到结论的推理正确性。
前提：
⑴如果甲得到冠军，则乙或者丙将得到亚军；
⑵如果乙得到亚军，则甲不能得到冠军；
⑶如果丁得到亚军，则丙不能得到亚军；
⑷甲得到了冠军。
结论：丁不能得到亚军。
在命题逻辑的研究中，除了前面介绍的五个逻辑联结词外，还有其它一些常用的联结词，它们都有其独特的一面和应用。
它满足以下性质：
⑵交换律：；
⑶结合律：；
⑷分配律：。
表1.4-1
表1.4-2
(表1.4-1)
⑵（自反否定律）；
表1.4-3
定义1.4-5设是联结词的集合，如果对于任意一个真值函数，均存在一个与之等价的真值函数，而且后者仅含有中的联结词，则称是联结词的功能完备集。
在理论上与应用上通过选用不同的功能完备集，可以方便地对真值函数类进行研究。
首先，{，，，，}是最常用的功能完备集。联结词集{，，}是一个重要的功能完备集，使用该功能完备集来表达的真值函数系统，常称为Boole代数系统；在编码理论中，自然地要用到功能完备集{，}表达的真值函数系统，它也称为Boole代数系统。另外在研究逻辑系统的演绎和推理时，{、}是一个重要的功能完备集。在制造大规模集成电路的芯片中完备集{}和{}都有广泛的应用。
所有的这些功能完备集都可以通过真值表利用定义验证。
在进一步的研究中，会遇到极小功能联结词集的提法，在此我们只简单说明其含义。
设为联结词集合，若中存在一个联结词可以由中的其他联结词表示，则称该联结词为联结词集中的冗余联结词，否则称为独立联结词。
定义1.4-6所谓某个联结词集合为极小功能完备联结词集是指满足下面条件：
⑴是一个功能完备集；
⑵中没有冗余联结词。
例如，联结词集{}和联结词结{}都是极小功能完备集；联结词集{、}也是极小功能完备集；但是联结词集{，，}就不是极小功能完备集，因为{，}和{，}都仍然是功能完备集。而{}、{}、{}不是极小功能完备集，因为它们根本就不是功能完备的。
1.4-1符号化下面两个命题，要求细化到原子命题，并且只能用一个联结词。
⑴或者明天下雨或者后天下雨。
⑵明天我将去北京或者去上海。
1.4-2将下列公式进行转化，使之只含有{}中的联结词。
1.4-3已知{}是功能完备联结词集，试证明{}也是功能完备联结词集。
1.4-4已知是极小功能完备集，证明和都是极小功能完备集。
在1.3节中介绍的基本等值式中多数公式是成对出现，这些成对出现的公式通常称为对偶的。
从定义不难看出，如果A*是A的对偶式，那么A也是A*的对偶式，即对偶式是相互的。所以，（A*）*=A。
例如，与，与，与均为对偶式。
关于对偶式有下面两个重要的定理。
定理1.5-2（对偶原理）设A，B为两个命题公式，如果，则A*B*,其中A*，B*分别是A，B的对偶式。
分别用代替即得
给定一个命题公式，判断它是重言式、矛盾式，还是可满足式，这类问题我们称为判定问题，在前面已经讲解过解决判定问题的两种方法，即真值表法和真值演算法，但当命题变元数目比较多时，仅用上述方法判断起来就不那么明显了。为此，我们试图将命题公式标准化。只要能使同一真值函数所对应的所有命题公式具有相同的标准型，就使得对判断两命题公式是否等值以及判断公式的类型变得规范、明显起来。
定义1.5-2由有限个命题变元或其否定构成的合取式称为原子合取式(AtomicConjunctiveForm)；
由有限个命题变元或其否定构成的析取式称为原子析取式(AtomicDisjunctiveForm)。
从定义不难看出：
一个原子析取式是重言式，当且仅当它同时含有一个命题变元及其否定；
一个原子合取式是矛盾式，当且仅当它同时含有一个命题变元及其否定。
例如，原子析取式是重言式，原子合取式是矛盾式。
定义1.5-3由有限个原子合取式构成的析取式称为析取范式(DisjunctiveNormalForm)；
由有限个原子析取式构成的合取式称为合取范式(ConjunctiveNormalForm)。
例如，、A*分别为析取范式和合取范式。
不难发现：
一个析取范式为矛盾式,当且仅当它的每个原子合取式都是矛盾式；
一个合取范式为重言式,当且仅当它的每个原子析取式都是重言式。
那么给定任何一个命题公式,是否都能求出与之等值的析取范式和合取范式呢
定理1.5-3（范式存在定理）任一命题公式都存在着与之等值的析取范式，也都存在着与之等值的合取范式。
若遇到┐(┐p)形式,利用双重否定律将否定号消去：
任一公式A通过上述三步,即得到与A等值的析取范式或合取范式。
求范式的具体步骤:
⑵否定符号的内移或消去；
⑶利用分配律得到析取范式或合取范式。
再利用交换律和吸收律：(p∧┐r)∨(q∧┐r)∨p
可见,与某个命题公式等值的析取范式是不唯一的，合取范式也是不唯一的。
从上面的例1.5-3可以看到，同一个命题公式的析取范式和合取范式都是不唯一的，这说明范式虽然是一种规范的形式，但还不能作为标准形式。为此，我们需要在此基础上做进一步的规范定义。
定义1.5-4对于命题公式A，包含A中的每个命题变元或其否定一次且仅一次的原子合取式称为极小项。
例如，，等是极小项，而，，等不是极小项。
下面我们就仅含有2个命题变元的情形来说明一种极小项的抽象简明的表示方法。
2个命题变元p，q可形成4个极小项，如果将命题变元看成1，命题变元的否定看作0，那么每个极小项就对应一个二进制数，自然也对应一个十进制数。不难看出，二进制数正是该极小项的成真赋值，不妨用对应的十进制数作为该极小项抽象表示法的下角码。
4个对应情况如表1.5-1所示：
表1.5-1
极小项
成真赋值
对应十进制数
简明表示
00
m0
01
m1
10
2
m2
11
3
m3
定义1.5-5如果命题公式A的析取范式中的原子合取式全是极小项，则称该析取范式为A的主析取范式(PrincipalDisjunctiveNormalForm)。
定理1.5-4任何命题公式的主析取范式都存在且唯一。
求主析取范式的步骤可归纳如下：
⑴求出A的析取范式；
⑵利用同一律，去掉析取范式中所有永假的原子合取式；
⑶利用等幂律，将析取范式中重复出现的合取项或者命题变元合并；
⑷利用同一律，若合取项中未出现命题变元，则添加为其一个合取项，并用分配律展开；
⑸再次合并相同的项和消去产生矛盾的项，然后按照下角标从小到大顺序排列，并用形式表示之，如，用表示等。
例1.5-4求的主析取范式。
由极小项的定义可知，上式中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
主析取范式可用于解决以下问题：
①判断两命题公式是否等值。由于任何命题公式的主析取范式都是唯一的，因而若，说明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
成假赋值
M0
M1
M2
M3
定理1.5-4极小项与极大项之间存在下面的关系：
定义1.5-7如果命题公式A的合取范式中的原子析取式全是极大项，则称该合取式为主合取范式(PrincipalConjunctiveNormalForm)。
可以证明：任一命题公式A的主合取范式一定存在且唯一的。
求一命题公式A的主合取范式与求主析取范式的步骤类似，只是在第⑶步中，应添加为析取式中的一个析取项，然后利用分配律，其他步骤一样。
例1.5-6求的主合取范式。
如果求出了公式A的主析取范式，可以直接用主析取范式求出其主合取范式（反之亦然）。下面通过例子来说明这种方法，在例1.5-5中我们求得的主析取范式为：
而
所以
则
公式的主合取范式即为所求。
由A主析取范式求合取范式的步骤为：
⑵求出与⑴中极小项下角码相同的极大项；
⑶由以上极大项构成的合取式就是A的主合取范式。
例1.5-7求的主合取范式。
解由例1.5-4知的主析取范式为m2m4m5m6m7
其中没有出现的极小项为m0，m1，m3，对应得极大项为，因此，的主合取范式为：
当然，类似地可从主合取范式求出主析取范式，具体步骤请读者给出。
同样通过主合取范式也可以用于：
①判断公式之间是否逻辑等值；
②判断公式类型（重言式不含极大项，用1表示）；
③求成假赋值（所含极大项下角码二进制表示）或成真赋值（不含）。
1.5-1.写出下列公式的对偶式。
⑵。
1.5-2.将下列公式化为析取范式和合取范式。
1.5-3.求下列公式的主析取范式和主合取范式。
1.5-4.用真值表法求下列公式的各极小项和极大项，并写出主析取范式和主合取范式。
⑴；⑵；
⑶；⑷。
1.5-5.通过求主析取范式，判断下列公式的类型。
1.5-6.通过求主合取范式证明下列各等值式。
推理是从前提推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则得到的命题公式。从某些给定的前提出发，按照严格定义的形式规则，推出有效的结论，这样的过程称为形式证明或演绎证明。
于是，判断推理是否有效的方法就是判断重言蕴涵式的方法，比如我们前面所讲的真值表法、等值演算和主范式法等。
例1.6-1判断如下推理是否有效。
如果天气凉快，小王就不去游泳。天气凉快。所以小王没有游泳。
解命题符号化，p：天气凉快，q：小王去游泳，
结论：
推理的形式结构：，要判断其推理是否有效，就是判断是否是重言式。
①真值表法：作出的真值表如表1.6-1所示。
由其真值表可以看出，最后一列均为1，即重言式，所以推理有效。
即为重言式。
故推理有效。
表1.6-1
在推理过程中，我们也可以应用已经得到的一些基本蕴含关系（或重言蕴涵式）。
1.附加
2.附加
3.化简
4.化简
5.
6.
7.
8.
9.合取
10.假言推理
11.拒取式
12.析取三段论
13.假言三段论
14.构造性二难推理
在推理过程中，如果命题变元较多，采用真值表、等值演算和主范式方法有时不方便。为此介绍形式证明的方法。
形式证明(FormalProof)的推理过程是一个命题序列，其中每一个命题或者是已知命题，或者是由某些前提根据推理规则推出的结论，序列的最后一个命题是需要论证的结论。
要进行正确的推理，需要使用推理规则，下面给出形式证明中的推理规则：
⑴前提引入规则P：在证明的任何步骤中，都可以引入前提。
⑵结论引入规则T：在证明的任何步骤中，在此之前证明得到的结论都可以作为后续证明的前提引入。
⑶置换规则：在证明任何步骤中，命题公式中的任何子公式都可以用与之等值的命题公式置换，如可以用置换等。
⑷代入规则：在证明的任何步骤中，重言式的任何一个命题变元都可以用一个命题公式代入，得到的仍是重言式。
⑸附加规则：
⑹化简规则：
⑺假言推理规则：
⑻拒取式规则：
⑼析取三段论规则：
⑽假言三段论规则：
⑾等价三段论规则：
⑿构造性二难规则：
⒀合取引入规则：
下面我们通过例题来说明如何构造形式证明。
例1.6-2给出下列的推理的形式证明：，，，，q。
前提：，，，，
结论：q
证明①P
②P
③T①②拒取式
④P
⑤rT③④假言推理
⑥P
⑦T⑤⑥拒取式
⑧P
⑨qT⑦⑧析取三段论
①
②
③
④
⑤
⑥
⑦
⑧
⑨
图1.6-1
图1.6-2
在形式证明的实际应用中，有时候为了使证明过程给人以更清晰的认识，往往在证明后附上证明（推理）树。例如本题的证明树如图1.6-1所示。它的作法是，把证明（推理）过程中作为前提的标号作为树叶，每一步用线相连，得到的相应结论的标号作为相应的结点，直到最后一步的结论作为树根。
例1.6-3写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。
解符号化题目中的命题，设p：今天是星期一，q：进行英语考试，r：进行离散数学考试，s：英语老师有会。
前提：,,p,s
结论：r
证明：①P
②pP
③T①②假言推理
⑤sP
⑥T④⑤假言推理
⑦rT③⑥析取三段论
由有效推理可知，今天进行离散数学考试。其证明树如图1.6-2所示。
在上面的例子中，采用前面的规则进行形式证明的方法，通常也称为直接证明法。在形式证明中，有时可采用一定的技巧，使证明过程简化。
CP规则：
证明类似问题时，我们常采用这种方法。方法是，将结论中蕴涵前件作为一个附加前提来证明结论中蕴涵式中的后件是有效逻辑结论。
这种方法是可以保证整个推理正确的。
根据置换原则可知，上式最后一个式子为重言式与第一个式子为重言式是等价的。
通常我们把这个结论在运用于形式证明时称为CP规则。
例1.6-4用形式证明法证明：，，q
前提：，，q
证明①s附加前提引入
②前提引入
③p①②析取三段论
④前提引入
⑤③④假言推理
⑥q前提引入
⑦r⑤⑥假言推理
⑧①⑦CP规则
间接证明法--归谬法。
归谬法是将结论的否定作为一前提引入，通过有效推理得到矛盾，以此说明推理正确。
例1.6-5用间接证明法证明：，p，
前提：，p，
④P否定结论引入
⑤T③④拒取式
⑥sT⑤化简
⑦P
⑧T⑥⑦合取
由⑧得到矛盾，根据归谬法可知推理正确。
1.6-1.符号化下面问题中的前提和结论,并指出推理是否正确，为什么？
前提：⑴如果这里有演出，则通行是困难的；
结论：这里没有演出。
1.6-2.形式证明给出下列推理的过程的形式证明。
⑶
⑷
⑸前提：
结论：。
1.6-3.下面的推理过程是否正确，结论是否有效，并说明理由。
①P前提引入
②T①化简
③P前提引入
④T②③假言推理
1.6-4.判断下面的推理证明过程是否正确，若不正确请指出错误所在位置及出错原因，若正确则请补足每一步所用的推理规则。
证明：①⑴
②⑵
③⑶
④⑷
⑤⑸
⑥⑹
⑦⑺
⑧⑻
1.6-5.用推理规则证明下列推理的正确性：如果张三努力工作，那么李四或王五感到高兴；如果李四感到高兴，那么张三不努力工作；如果刘强高兴，那么王五不高兴。所以，如果张三努力工作，则刘强不高兴。
1.6-6.已知事实如下，问结论是否有效。
前提：⑴如果天下雪，则马路就会结冰；
⑵如果马路结冰，汽车就不会开快；
⑶如果汽车开得不快，马路上就会塞车；
⑷马路上没有塞车。
结论：天没有下雪。
P
Q
图1.7-1
下面我们来看一个简单的自动控制电路的设计。
例1.7-1试设计红绿灯自动控制线路，要求传感器中记数器内容Z，当时亮绿灯，当时亮红灯，当时亮黄灯。
L1
L2
L3
图1.7-2
对于复杂的问题，运用逻辑知识可以理出清晰的思路，使得设计电路时得心应手。
例1.8-1下面给出的语句是否是命题，若是命题，试给出其真值。
⑴你喜欢周杰伦吗？
⑵大家不要讲话了！
⑶2+x=5。
⑷2是素数。
⑸1是素数。
⑹如果1是素数，2就不是素数。
⑺地球之外的星球上还有生物。
⑻我生于1978年。
⑼我正在说谎！
解本题主要考查我们对命题概念的理解。
⑴、⑵都不是陈述句，不可能是命题；⑶中包含有待赋值的x，所以也不是命题；⑷是真命题；⑸是假命题；⑹是一个复合条件命题，因为前件为假，所以它是一个真命题；
虽然⑺、⑻的真值我们还不知道，但他它是有真假的，所以也是命题；⑼虽然也是陈述句，但是它不是命题，它是一个典型的悖论。
例1.8-2符号化下列命题公式。
⑴当我想起我母亲劳碌的身影时我就禁不住哭了。
⑶一个正整数是素数当且仅当它只能被1和它自身整除。
⑷小李总是在图书馆看书，除非图书馆不开门或者小李有病。
⑸假如上午天不下雨，我去看电影，否则就在家里读书。
解在数理逻辑中，命题逻辑的翻译是比较简单的，容易混淆的地方主要在于：
⑴设p：我想起我母亲劳碌的身影；q：我禁不住哭了。则原语句符号化为：。
⑶设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）
故选择答案（C）。
例1.8-5一个公安人员审查一件盗窃案，已知事实如下：
⑴甲或乙盗窃了录音机；
⑶如乙的证词正确，则午夜时屋里的灯光未灭；
⑸午夜时屋里的灯光灭了。问到底是谁盗窃了录音机？
结论：根据逻辑推理求出
推理过程：①P
由⑨说明是乙盗窃了录音机。
例1.8-6判断下式是否为重言式。。
解对于判断一个命题公式是重言式、矛盾式还是可满足式，我们可以采用的方法很多。利用等值演算法，真值表法和化为主范式的方法都很有效，并且也是我们经常采用的，对本题当然也适合。对真值表方法是很基本的，主要在于我们要细心，并且对于本题这样出现命题变元较多的，作出的表会很大；对于主范式和等值演算法的道理是一样的，就是利用我们已经掌握的等值式逐步演算，关键在于我们要掌握好等值式，对于本题命题公式比较复杂，用起来也有一定的难度，那么是否可以从公式的形式找到一种更好的方法呢？事实上，在做题目是我们要善于发现题目的特点，像这个题我们看到公式有反复的蕴涵联结词，并且是要判断是否是重言式，所以我们可以采用构造形式证明的方法证明：
，而由CP规则就是要证明：
构造形式证明：
①P
②P附加前提引入
③T①蕴涵等值式，置换
④T③添加
⑤T④蕴涵等值式，置换
⑥T②蕴涵等值式，置换
⑦T⑥添加
⑧T⑦蕴涵等值式，置换
⑨P附加前提引入
⑩P⑤⑧⑨构造性二难推理
由上面的推理过程可知推理有效，根据CP规则可知所给公式是重言式。
1.下列句子中，哪些是命题？如果是命题，指出其是简单命题还是复合命题，并判断真假。
⑴中国有四大发明。
⑵吸烟请到吸烟室去！
⑶是无理数！
⑷李春和李红是姐妹。
⑸李春在说谎。
⑹如果3是偶数，那么中国人的母语是汉语。
⑺只要你抽烟，你就很容易得病。
⑻只有今天是星期一，明天才是星期二。
⑼李春这个学期《离散数学》和《数据结构》都考了100分。
⑽下雪路滑，他迟到了。
⑾不经一事，不长一智。
⑿一朝被蛇咬，十年怕井绳。
2.符号化第1题中的复合命题，要求细化到原子命题。
表2-1
s
A（其他为0）
说李刚不会拳击或李春不会唱歌是正确的，而说如果李刚会唱歌，李春就会拳击是不正确的。
5.命题公式A包含4个命题变元：p，q，r，s，其真值表如表2-1所示：
⑴写出A的极小项和极大项；
⑵写出与A等值的主析取范式和主合取范式；
⑶写出与A等值的析取范式的最简形式。
6.证明下列命题的等值关系。
7.用真值表、等值演算和求主范式的方法判断下面公式的类型。
8.证明下列推理。
⑵前提：，，，，
结论：；
⑶，，。
9.用推理规则说明：
，，是否能同时成立。
10.用真值表、等值演算、求主范式和构造推理证明下面的推理正确。
只要小王曾经到过受害人的房间并且11点以前没有离开，小王就犯了谋杀罪。小王曾经到过受害者房间。如果小王在1点以前离开，看门人会看到他。看门人没有看到他。所以小王犯了谋杀罪。
11.有一位逻辑学家被一伙强盗绑架。强盗头目天生好玩刺激的游戏，他把逻辑学家拘于有两个门的牢狱，两个门中其中一个是生门，一个是死门。如果从生门出去将可以安全离开，如果从死门出去，将立即处死。但是到底哪个是生门，哪个是死门不可能告诉逻辑学家。
在每个门旁强盗头目各派有一名强盗把守，这两名强盗一个所说的每一句话都是假话，另外一个则说的每一句话都是真话，当然到底哪个是说假话的哪个是说真话的不可能让逻辑学家知道。现在强盗头目给逻辑学家一次可能生还的机会，他允许逻辑学家问两个守门强盗中的一个且只能问其中一个，并且被问的强盗只能回答一次且只能回答一句话。现在逻辑学家可以安全的出去吗？