命题逻辑等值演算

命题逻辑等值演算第一页，共四十二页，编辑于2023年，星期五基本要求：1.深刻理解等值式的概念。

2.牢记24个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算。

3.了解简单析取式、简单合取式、析取范式、合取范式的概念。

4.深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。

5.熟练掌求公式的主析取范式的方法。

6.熟练掌握由公式的主析取范式求公式的主合取范式的方法。

7.会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值。8.会将公式等值地化为任何联结词完备集中的公式。第二页，共四十二页，编辑于2023年，星期五某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？解：复合命题（公式）例题(p∨q)(pr)(qs)r∧∧∧A=第三页，共四十二页，编辑于2023年，星期五(p∨q)(pr)(qs)r∧∧∧A=pqrsp∨qprqsr(p∨q)∧(pr)∧(qs)∧r000001110000101110001001100001101100010011010010111111011011000011111100100010110100110110101011100101111100110010010110110110111011000111111100麻烦！！计算量大！！方法很多：

真值表法等值演算法第四页，共四十二页，编辑于2023年，星期五2.1等值式1.例子看下面三个公式的真值表

PQPQP∨QQP00111011111000011111

从真值表可以看出，不论对P、Q作何指派，都使得PQ、P∨Q和QP的真值相同，表明它们之间彼此等价。第五页，共四十二页，编辑于2023年，星期五2.定义：A、B是含有命题变元P1,P2,…,

Pn的命题公式，如不论对P1,P2,…,

Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。显然PQP∨QQP3.重要的等价公式⑴双重否定律AA⑵幂等律A∨AAA∧AA⑶交换律A∨BB∨AA∧BB∧A⑷结合律A∨(B∨C)(A∨B)∨C

A∧(B∧C)(A∧B)∧C

第六页，共四十二页，编辑于2023年，星期五(6)德摩根律(A∨B)A∧B

(A∧B)A∨B(7)吸收律A∨(A∧B)AA∧(A∨B)A(8)零律A∨11A∧00(9)同一律A∨0AA∧1A(10)排中律A∨A1(11)矛盾律A∧A0⑸分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)(∨对∧的分配律)互补律(∧对∨的分配律)第七页，共四十二页，编辑于2023年，星期五(13)等价等值式AB(AB)∧(BA)

AB(A∨B)∧(A∨B)AB(A∧B)∨(A∧B)(14)假言易位ABBA(15)等价否定等值式

ABAB

(16)归谬论

(AB)∧(AB)A(12)蕴含等值式ABA∨B

第八页，共四十二页，编辑于2023年，星期五4.等价公式的证明方法方法1：用列真值表。（不再举例）方法2：用公式的等价变换.(用置换定律)置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。等值演算：由已知等值式推演出新的等值式的过程。第九页，共四十二页，编辑于2023年，星期五例题1.用等值演算法证明下面等值式：((p∨q)∧(p∧q))(pq)q(pr)(p∧q)r证明：(1)从左边开始演算(p∨q)∧(p∧q)

(p∨q)∧(p∧q)(双重否定律)

((p∨q)∨(p∧q))(德摩根律)

((p∧q)∨(p∧q))(德摩根律)

((p∨p)∧(p∨q)∧(q∨p)∧(q∨q))(分配律)

((p∨q)∧(q∨p))(同一律)((p

q)∧(qp))(蕴含等值式)(pq)(等价等值式)11第十页，共四十二页，编辑于2023年，星期五例题1.用等值演算法证明下面等值式：(2)q(pr)(p∧q)r证明：(2)从右边开始演算

(p∧q)r

(p∧q)∨r(蕴含等值式)

p∨q∨r(德摩根律)

q∨(p∨r)(交换律)

q∨(pr)(蕴含等值式)q(pr)(蕴含等值式)

第十一页，共四十二页，编辑于2023年，星期五例题2.用等值演算法判断下列公式的类型：(p∨q)→(p∧q)p→(p∨q∨r)((p→q)∧q)∧r解：(1)(p∨q)→(p∧q)

(p∨q)∨(p∧q)(蕴含等值式)(p∧q)∨(p∧q)(德摩根定律)(p∧q)∨(p∧q)(双重否定律)

p∧(q∨q)(分配律)

p∧1(排中律)

p(同一律)因为p是可满足式，故式(1)为可满足式第十二页，共四十二页，编辑于2023年，星期五例题2.用等值演算法判断下列公式的类型：(2)p→(p∨q∨r)解：(2)

p→(p∨q∨r)

p∨(p∨q∨r)(蕴含等值式)(p∨p)∨(q∨r)(分配律)1∨(q∨r)(排中律)

1(零律)因为1是重言式，故式(2)为重言式第十三页，共四十二页，编辑于2023年，星期五例题2.用等值演算法判断下列公式的类型：(3)((p→q)∧q)∧r解：(3)

((p→q)∧q)∧r

(p∨q)∧q)∧r

(蕴含等值式)p∧(q∧q)∧r

(德摩根律、结合律)p∧0∧r(矛盾律)

0(零律)因为p是矛盾式，故式(3)为矛盾式第十四页，共四十二页，编辑于2023年，星期五某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？(p∨q)(pr)(qs)r∧∧∧A=例题.用等值演算法解决实际问题p：派小李去上海出差q：派小张去上海出差r：小赵要加班s：小王也去上海出差(p∨q)∧(p∨r)∧(q∨s)∧r(德摩根律)(p∨q)∧(p∨r)∧r∧

(q∨s)(交换律)(p∨q)∧(p∧r)∧

(q∨s)(分配律、矛盾律)((p∧p∧r)∨(q∧p∧r))∧(q∨s)(分配律)(q∧p∧r)∧(q∨s)(矛盾律)(q∧p∧r∧s)(分配律、矛盾律)结论：派遣方案为：派小张和小王去上海出差，只有这一种方案第十五页，共四十二页，编辑于2023年，星期五2.2.范式范式就是命题公式形式的规范形式。这里约定在范式中只含有联结词、∨和∧。一.析取范式与合取范式1.合取式与析取式

合取式：是用“∧”联结命题变元或变元的否定构成的式子。如P、P、P∧Q、P∧Q∧R

析取式：是用“∨”联结命题变元或变元的否定构成的式子。如P、P、P∨Q、P∨Q∨R注:∵P∨PPP∧PP∴P是合(析)取式.第十六页，共四十二页，编辑于2023年，星期五2.析取范式公式A如果写成如下形式：A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式，称之为A的析取范式。

3.合取范式公式A如果写成如下形式：A1∧A2∧...∧An(n≥1)

其中每个Ai(i=1,2..n)是析取式，称之为A的合取范式。例如，PQ的析取范式与合取范式：PQ(P∧Q)∨(P∧Q)----析取范式PQ(P∨Q)∧(P∨Q)----合取范式第十七页，共四十二页，编辑于2023年，星期五4.析取范式与合取范式的写法

⑴先用相应的公式去掉和。蕴含等值式PQP∨Q等价等值式PQ(P∧Q)∨(P∧Q)

PQ(PQ)∧(QP)

PQ(P∨Q)∧(P∨Q)

⑵用公式的否定公式或德摩根律将后移到命题变元之前。

A(P1,P2,…,Pn)A*(P1,P2,…,Pn)

(P∨Q)P∧Q

(P∧Q)P∨Q

⑶用分配律、幂等律等公式进行整理，使之成为所要求的形式。

(对偶式)第十八页，共四十二页，编辑于2023年，星期五例如求(PQ)R的析取范式与合取范式(PQ)R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式(PQ)R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式第十九页，共四十二页，编辑于2023年，星期五二.主析取范式与主合取范式一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。㈠主析取范式1.极小项⑴定义：在一个有n个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是个极小项。例如，有两个变元的极小项：P∧Q、P∧Q、P∧Q、P∧Q

第二十页，共四十二页，编辑于2023年，星期五

⑵极小项的性质m3m2m1

m0PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFF

a).有n个变元，则有2n个极小项。

b).每一组指派有且只有一个极小项为T。为了记忆方便，可将各组指派对应的为T的极小项分别记作m0,m1,m2,…,m2n-1上例中m0P∧Qm1P∧Q

m2P∧Qm3P∧Q第二十一页，共四十二页，编辑于2023年，星期五2.主析取范式定义

析取范式A1∨A2∨...∨An,,其中每个Ai(i=1,2..n)都是极小项，称之为主析取范式。3.主析取范式的写法

方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中每个“T”对应的极小项。(如何根据一组指派写对应的为“T”的项：如果变元P被指派为T，P在极小项中以P形式出现；如变元P被指派为F,P在极小项中以P形式出现(因要保证该极小项为T))。⑶用“∨”联结上述极小项，即可。第二十二页，共四十二页，编辑于2023年，星期五例如求PQ和PQ的主析取范式

PQPQPQFFTTFTTFTFFFTTTT

PQm0∨m1∨m3

(P∧Q)∨(P∧Q)∨(P∧Q)PQm0∨m3(P∧Q)∨(P∧Q)思考题:永真式的主析取范式是什么样？第二十三页，共四十二页，编辑于2023年，星期五方法Ⅱ：用公式的等价变换⑴先写出给定公式的析取范式

A1∨A2∨...∨An

。⑵为使每个Ai都变成极小项，对缺少变元的Ai补全变元，比如缺变元R，就用∧联结永真式(R∨R)形式补R。⑶用分配律等公式加以整理。

PQP∨Q(P∧(Q∨Q))∨((P∨P)∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)第二十四页，共四十二页，编辑于2023年，星期五㈡主合取范式1.极大项⑴定义:在有n个命题变元的析取式中，每个变元必出现且仅出现一次,称之为极大项。例如，有两个变元的极大项及其真值表：M0M1M2M3PQP∨QP∨QP∨QP∨QFF

FTTTFTT

FTTTFTTFTTTTTT

F第二十五页，共四十二页，编辑于2023年，星期五⑵极大项的性质a).有n个变元，则有2n个极大项。

b).每一组指派有且只有一个极大项为F。为了记忆方便，可将各组指派对应的为F的极大项分别记作M0,M1,M2,…,M2n-1。上例中M0P∨QM1P∨Q

M2

P∨QM3P∨Q第二十六页，共四十二页，编辑于2023年，星期五⑵极大项与极小项之间的关系

定理2.3：第二十七页，共四十二页，编辑于2023年，星期五2.主合取范式定义合取范式A1∧A2∧...∧An,,其中每个Ai(i=1,2..n)都是极大项，称之为主合取范式。3.主合取范式的写法

方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中每个“F”对应的极大项。

如何根据一组指派写对应的为“F”的极大项：如果变元P被指派为F，P在极大项中以P形式出现；如变元P被指派为T，P在极大项中以P形式出现(确保该极大项为F)。⑶用“∧”联结上述大项，即可。第二十八页，共四十二页，编辑于2023年，星期五例如求PQ和PQ的主合取范式

PQPQPQFFTTFTTFTFFFTTTT

PQM2P∨QPQM1∧M2(P∨Q

)∧(P∨Q)第二十九页，共四十二页，编辑于2023年，星期五方法Ⅱ：用公式的等价变换⑴先写出给定公式的合取范式

A1∧A2∧...∧An

。⑵为使每个Ai变成极大项，对缺少变元的析取式Ai补全变元，比如缺变元R，就用∨联结永假式(R∧R)形式补R。⑶用分配律等公式加以整理。第三十页，共四十二页，编辑于2023年，星期五例如，求(PQ)R的主合取范式(PQ)R(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧

(P∨Q∨R)∧(P∨Q∨R)第三十一页，共四十二页，编辑于2023年，星期五三.主范式的应用

1.应用主析取范式解决实际问题某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？A＝(p∨q)∧(pr)∧(qs)∧r(p∨q)∧(p∨r)∧(q∨s)∧r

((p∧p)∨(p∧s)∨(q∧p)∨(q∧s))∧

((q∧r)∨(r∧r))00((p∧s)∨(q∧p)∨(q∧s))∧(q∧r)(p∧s∧q∧r)∨0∨0(p∧s∧q∧r)m9第三十二页，共四十二页，编辑于2023年，星期五应用2

用主析取范式或主合取范式判断两个命题公式是否等值(1)设A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))解：求A与B的主析取范式A=(p∧q)∨(p∧q∧r)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)

(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)m6m7m3m3∨m6∨m7B=(p∨(q∧r))∧(q∨(p∧r))(p∧q)∨(p∧p∧r)∨(q∧r∧q)∨(q∧r∧p∧r)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)m3∨m6∨m7m7m6m3m3∨m6∨m7由于A与B有相同的主析取范式，所以A

B第三十三页，共四十二页，编辑于2023年，星期五解：求A与B的主合取范式A=(p∧q)∨(p∧q∧r)(p∨p)

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

(p∨q)∧(p∨r)∧(q∨p)∧(q∨p)∧(q∨r)(p∨q)∧(p∨r)∧(p∨q)∧(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)应用2

用主析取范式或主合取范式判断两个命题公式是否等值(1)设A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))M1M0M2M5M4M0∧M1∧M2∧M4∧M5M0∧M1∧M2∧M4∧M5第三十四页，共四十二页，编辑于2023年，星期五B=(p∨(q∧r))∧(q∨(p∧r))

(p∨q)∧(p∨r)∧(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)

解：求A与B的主合取范式A=(p∧q)∨(p∧q∧r)应用2

用主析取范式或主合取范式判断两个命题公式是否等值(1)设A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))M1M0M2M5M4M0∧M1∧M2∧M4∧M5M0∧M1∧M2∧M4∧M