数理逻辑命题逻辑

数理逻辑命题逻辑第1页，本讲稿共55页引言给定一个命题公式，如何判断它的类型—是重言式、矛盾式、还是可满足式？目前已经给出了两种方法，即真值表法和逻辑等价演算法。还有第三种方法，这就是把命题公式化成一种统一的、标准的公式—范式。2第2页，本讲稿共55页给定命题变元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都等都是简单合取式。

1.简单析取式和简单合取式定义

仅由有限个命题变元或其否定构成的析取式称为简单析取式。仅由有限个命题变元或其否定构成的合取式称为简单合取式。3第3页，本讲稿共55页2.析取范式和合取范式定义(1)仅由有限个简单合取式构成的析取式称为析取范式；(2)仅由有限个简单析取式构成的合取式称为合取范式。显然任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式。4第4页，本讲稿共55页例如：A=(p∧┒q∧r)∨(┒p∧q)∨(p∧┒q)则A为析取范式。

A的对偶式为：A*=(p∨┒q∨r)∧(┒p∨q)∧(p∨┒q)显然，A*为合取范式。对任何给定的命题公式，都能求出与之等价的析取范式与合取范式。5第5页，本讲稿共55页定理(范式存在定理)任一命题公式都存在着与之等价的析取范式和合取范式。下述分析给出了任何命题公式范式存在性的证明，这证明同时也是求其范式的具体步骤，即(1).消去对{┒、∧、∨}来说冗余的联结词。即用基本的逻辑恒等式及置换规则将→、↔联结词消去，所用的逻辑恒等式是p→q⇔┒p∨qp

↔q⇔(┒p∨q)∧(p∨┒q)6第6页，本讲稿共55页(2).否定号消去或内移若遇有┒┒p或┒(p∧q)，┒(p∨q)等形式，利用双重否定律和德.摩根律可将否定号消去或内移，即┒┒p⇔p；

┒(p∧q)⇔┒p∨┒q；

┒(p∨q)⇔┒p∧┒q。7第7页，本讲稿共55页(3).利用分配律

若是求析取范式，应该利用“∧”对“∨”的分配律；若是求合取范式，应该利用“∨”对“∧”的分配律。任给一个命题公式A，经过以上三步演算，可得到一个与A逻辑等价的析取范式或合取范式。值得注意的是，任何命题公式的析取范式和合取范式都不是唯一的，我们把其中运算符最少的称为最简析取(合取)范式。

8第8页，本讲稿共55页例1求下面命题公式的合取范式和析取范式。解(1)求合取范式

至此，求出了原公式的合取范式。但上式可再化简，得：⇔(p∨q)∧(┒r∨p)，该式也是原公式的合取范式（最简），这说明与某个命题公式等价的合取范式是不唯一的。

9第9页，本讲稿共55页(2)求析取范式

最后结果为原公式的析取范式，利用交换律和吸收律得，也是原公式的析取范式，由此可见，与命题公式等值的析取范式也是不唯一的。

10第10页，本讲稿共55页例2求P∧(P→Q)的最简析取范式。解：P∧(P→Q)⇔P∧(┒P∨Q)

⇔

P∧┒P∨P∧Q⇔

0∨P∧Q⇔

P∧Q

11第11页，本讲稿共55页3.极小项与主析取范式定义

在含n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i位上(若命题变元无下标，则按字典顺序)，这样的简单合取式称为极小项。显然，n个变元可构成2n个不同的极小项。12第12页，本讲稿共55页例如，3个命题变元可形成8个极小项。

┒P∧┒Q∧┒R

┒P∧┒Q∧R

┒P∧Q∧┒R

┒P∧Q∧R P∧┒Q∧┒RP∧┒Q∧RP∧Q∧┒RP∧Q∧R 13第13页，本讲稿共55页如果将命题变元看成1，命题变元的否定看成0，则每个极小项对应一个二进制数，因而也对应一个十进制数。14第14页，本讲稿共55页3个命题变元构成的8个极小项对应情况如下：

┒P∧┒Q∧┒R 0000

┒P∧┒Q∧R 0011

┒P∧Q∧┒R 0102

┒P∧Q∧R 0113P∧┒Q∧┒R 1004P∧┒Q∧R 1015P∧Q∧┒R 1106P∧Q∧R 1117极小项二进制十进制15第15页，本讲稿共55页可用对应的十进制数作下标，用mi表示这一项,即：

┒P∧┒Q∧┒R 0000m0

┒P∧┒Q∧R 0011m1

┒P∧Q∧┒R 0102m2

┒P∧Q∧R 0113m3

P∧┒Q∧┒R 1004m4

P∧┒Q∧R 1015m5

P∧Q∧┒R 1106m6

P∧Q∧R 1117m7

极小项二进制十进制mi表示16第16页，本讲稿共55页一般地,n个变元的极小项是:m0⇔┒P1∧┒P2∧┒P3

…∧┒Pnm1⇔┒P1∧┒P2∧┒P3

…∧Pn……m2n-1⇔P1∧P2∧P3…∧Pn

17第17页，本讲稿共55页极小项有以下3个性质：(1)在极小项中，将命题变元记为1，命题变元的否定记为0，则每个极小项对应一个二进制数。则该二进制数是该极小项唯一的成真赋值。

18第18页，本讲稿共55页极小项有以下3个性质：(1)在极小项中，将命题变元记为1，命题变元的否定记为0，则每个极小项对应一个二进制数。则该二进制数是该极小项唯一的成真赋值。(2)任意两个不同的极小项的合取式的值永假。例如，

19第19页，本讲稿共55页极小项有以下3个性质：(1)在极小项中，将命题变元记为1，命题变元的否定记为0，则每个极小项对应一个二进制数。则该二进制数是该极小项唯一的成真赋值。(2)任意两个不同的极小项的合取式的值永假。例如，

(3)全体极小项的析取式的值永真，即20第20页，本讲稿共55页定义

设命题公式A中含n个命题变元，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。定理任何命题公式的主析取范式都是存在的，并且是唯一的。这是因为任何一个命题公式都可求得它的析取范式（范式存在定理），而析取范式可化为主析取范式。21第21页，本讲稿共55页求给定命题公式A的主析取范式的步骤如下：

1.求A的最简析取范式A′；

22第22页，本讲稿共55页求给定命题公式A的主析取范式的步骤如下：

1.求A的最简析取范式A′；2.若A′的某简单合取式B中不含命题变元pi

或其否定┒pi，则将B展成如下形式：

23第23页，本讲稿共55页求给定命题公式A的主析取范式的步骤如下：

1.求A的最简析取范式A′；2.若A′的某简单合取式B中不含命题变元pi

或其否定┒pi，则将B展成如下形式：

3.将重复出现的命题变元、矛盾式及重复出现的极小项都“消去”。即将p∧p用p代替，p∧┒p用0代替、mi∨mi用mi代替。

24第24页，本讲稿共55页求给定命题公式A的主析取范式的步骤如下：

1.求A的最简析取范式A′；2.若A′的某简单合取式B中不含命题变元pi

或其否定┒pi，则将B展成如下形式：

3.将重复出现的命题变元、矛盾式及重复出现的极小项都“消去”。即将p∧p用p代替，p∧┒p用0代替、mi∨mi用mi代替。

4.将极小项按由小到大的顺序排列，并用Σ表示之，如m1∨m2∨m5用表示。25第25页，本讲稿共55页例1求命题公式的主析取范式

解先求地原公式的析取范式为：p∨(q∧┑r)含两个简单合取式p和(q∧┑r)。在p中无q或┑q，r或┑r出现，因而应该用p∧(┒q∨q)∧(┒r∨r)取代。在(q∧┑r)中无┒p或p，因而应该用(┒p∨p)∧(q∧┑r)取代，然后展开得极小项。于是有：26第26页，本讲稿共55页(析取范式)27第27页，本讲稿共55页由由极小项定义可知，上式中，2，4，5，6，7的二进制表示010，100，101，110，111为原公式的成真赋值，而此公式的主析取范式中没出现的极小项m0、m1、m3的下标为0、1、3，则对应的二进制表示000，001，011为原公式的成假赋值。因而，只要知道一个命题公式A的主析取范式，可立即写出A的真值表。

反之，若知道了A的真值表，找出A的所有成真赋值，用其对应的十进制数作为极小项的下标，就可求得A的主析取范式中所含的全部极小项，从而可得到A的主析取范式。定理

在公式A的真值表中，所有真值为1的赋值所对应的极小项的析取式即为A的主析取范式。28第28页，本讲稿共55页例2试由p∧q∨r的真值表求它的主析取范式。1111111011101010000110110000101010000000p∧q∨rp∧qrqp由表可知，001，011，101，110，111是原公式的成真赋值，因而对应的十进制数1，3，5，6，7为下标的极小项构成的主析取范式，而其它极小值不在它的主析取范式中，即29第29页，本讲稿共55页主析取范式的用途

1.判断两命题公式是否逻辑等价。由于任何命题公式的主析取范式都是唯一的，因而若A⇔B，说明A与B有相同的主析取范式，反之，若A，B有相同的主析取范式，必有A⇔B。

举例2.判断命题公式的类型。设A是含n个命题变元的命题公式，A为重言式，当且仅当A的主析取范式中含全部2n个极小项；A为矛盾式，当且仅当A的主析取范式中不含任何极小项，可设A的主析取范式为0；若A的主析取范式中至少含一个极小项，则A是可满足式。举例3.求命题公式的成真和成假赋值。举例30第30页，本讲稿共55页练习：用主析取范式法判断题下列公式的类型，并求公式的成真赋值。(p→q)→(┐q→┐p)分析：求主析取范式可用真值表法，也可以用逻辑等价演算法：(p→q)→(┐q→┐p)⇔┐(┐p∨q)∨(q∨┐p)(消去→)⇔(p∧┐q)∨┐p∨q(┐内移)(已为析取范式)⇔(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)⇔m2∨m0∨m1∨m1∨m3⇔m0∨m1∨m2∨m3所以，该式为重言式，00，01，10，11为成真赋值。31第31页，本讲稿共55页4.极大项与主合取范式

定义在含n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在左起的第i位上(若命题变元无角码，则按字典顺序排列)，这样的简单析取式称为极大项。

同极小项情况类似，n个命题变元可产生2n个极大项，每个极大项对应一个二进制数和一个十进制数，二进制数为该极大项的成假赋值，十进制数作为该极大项的抽象表示的角码。

32第32页，本讲稿共55页例如，n=3时，有8个极大项，对应的二进制数(成假赋值)、下标及名称如下：

-----000------0，记作M0-----001------1，记作M1

------010------2，记作M2------011------3，记作M3

------100------4，记作M4------101------5，记作M5------110------6，记作M6------111------7，记作M733第33页，本讲稿共55页一般情况下，n个命题变项共产生个极大项，分别记为。极大项也有3个性质：(1)在极大项中，将命题变元记做0，命题变元的否定记为1，则每个极大项对应一个二进制数，该二进制数是该极大项唯一的成假赋值。(2)任意两个不同的极大项的析取式的值永真。例如，

(3)全体极大项的合取式的值永假，即34第34页，本讲稿共55页定义设命题公式A中含n个命题变项，如果A的合取范式中的简单析取式全是极大项，则称该合取范式为主合取范式。

任一命题公式的主合取范式一定存在，且是唯一的。

求一命题公式A的主合取范式与求主析取范式的步骤非常相似，也是先求出合取范式A′。若A′的某简单析取式B中不含命题变项pi或其否定┒pi，则将B展成如下形式：35第35页，本讲稿共55页例

求的主合取范式。解:其中表示合取。

36第36页，本讲稿共55页5.主析取范式与主合取范式的关系

一个命题公式的主析取和主合取范式关系非常密切。因为极小项与极大项之间存在着如下关系：

例如，

37第37页，本讲稿共55页设命题公式A中含n个命题变元，如果A的主析取范式中含k个极小项。则┒A的主析取范式中必含个极小项，设为即38第38页，本讲稿共55页简而言之，一个命题公式的极小项下标与极大项下标是互补的。因此，只要求出了一个命题公式的主析取范式，就可根据它的极小项下标立即求得极大项，并求出主合取范式(反之亦然)。39第39页，本讲稿共55页例如，A中含3个命题变项，主析取范式为

因为极大项与极小项小标互补，则A的主合取范式为

40第40页，本讲稿共55页6.主析取范式在实际中的应用

例

某科研所要从3名骨干A、B、C中挑选1-2名出国进修，由于工作需要选派时要满足以下条件：（1）若A去，则C同去。（2）若B去，则C不能去。（3）若C不去，则A或B可以去。问所里应如何选派他们？

41第41页，本讲稿共55页解

先命题符号化。设p：派A去。q：派B去。r：派C去。则由已知条件可得公式：

(p→r)∧(q→┑r)∧(┑r→p∨q)经过演算可得(p→r)∧(q→┑r)∧(┑r→p∨q)⇔m1∨m2∨m5由于m1=┓p∧┓q∧r,m2=┓p∧q∧┓r,m5=p∧┓q∧r。故，选派方案有以下三种：1.C去，A、B不去。2.B去，A、C不去。3.A、C同去，B不去。42第42页，本讲稿共55页7.主析取范式的个数

一般来说，含n个变元的命题公式，其数量是无限的，但每个命题公式都对应着一个与它等价的主析取范式。如果两个命题公式有相同的主析取范式，我们称这两个命题公式属于一个等价类。属于一个等价类的命题公式，显然是互相等价的那么，含n个命题变元的命题公式，有多少个等价类呢？43第43页，本讲稿共55页当n=1时,极小项有21=2个,即P、┒P。主析取范式有:没有极小项全部极小项44第44页，本讲稿共55页当n=2时，极小项有22=4个。即┒P∧┒Q、┒P∧Q、P∧┒Q、P∧Q。主析取范式有45第45页，本讲稿共55页共222=16个。以此类推,n个命题变元,可构造22n个不同的主析取范式(包括F)。这个数字增长非常快,如n=3时223=256,n=4时224=65536。

主合取范式和主析取范式是一一对应的，因此，n个命题变元，也可构造22n个不同的主合取范式(包括T)。46第46页，本讲稿共55页第一章命题逻辑1.5联结词的扩充与归约47第47页，本讲稿共55页1.联结词的扩充1）.一元运算Pf1f2

f3f

40100110101永假恒等