离散数学额数理逻辑

离散数学额数理逻辑第一页，共六十七页，2022年，8月28日§2.1等值式等价关系定义：设A和B是两个命题公式,如果在任何赋值下，A和B都有相同的真值，则称A和B是等价的，或逻辑相等，记为AB。或记作A=B。第二章命题逻辑等值演算和的区别(1)不是联接符，是A和B等值的一种简便记法;(2)是联结符, PQ(P→Q)(Q→P)“”的三个性质1.自反性AA。2.对称性若AB则BA。3.传递性若AB,BC则AC。如何判定两个公式是否等值？设A、B为两命题公式，AB的充要条件是AB是重言式。第二页，共六十七页，2022年，8月28日判定方法——真值表法例1用真值表证明下列等式

P→Q┐PQ

即证明P→Q┐PQ为重言式PQ┐PP→Q┐PQP→Q┐PQ001111011111100001110111第三页，共六十七页，2022年，8月28日例2：判断公式P(QR)、(P∧Q)R是否等值。（书例2.2（1））PQRP∧QQRP(QR)(P

∧

Q）R00001110010111010001101101111000111101011111010001111111第四页，共六十七页，2022年，8月28日课堂练习用真值表证明下列等式是否成立

(a)(P┐P)QQ同一律

(b)P┐PQ┐QPQP┐PQ┐Q(P┐P)Q00000010011000011001第五页，共六十七页，2022年，8月28日一、常用的重要等值公式表：1、AA双重否定律2、AAA3、AAA等幂律4、ABBA5、AB

BA交换律判定方法——等值演算6、(AB)

C7、(AB)C

结合律A(BC)A(BC)第六页，共六十七页，2022年，8月28日8、A(B

C)9、A(B

C

)

分配律10、(AB)11、(AB)德·摩根律(AB)(AC)(AB)(AC)A

B

AB12、A(AB)A13、A(AB)A吸收律*14、A1115、A00零律16、A0A17、A1

A同一律第七页，共六十七页，2022年，8月28日19、

A

A0矛盾律20、

AB

AB

蕴涵等值式*假言易位等价否定等值式归谬论*21、

AB(AB)(BA)等价等值式22、

ABB

A23、

ABB

A24、

(AB)(AB)

A18、

A

A1排中律第八页，共六十七页，2022年，8月28日A﹁﹁AA∨AA∧A000011111、AA双重否定律2、AAA3、AAA等幂律第九页，共六十七页，2022年，8月28日ABCA∨BB∨C(A∨B)∨CA∨(B∨C)000

0

0

0

0001

0

1

1

1010

1

1

1

1011

1

1

1

1100

1

0

1

1101

1

1

1

1110

1

1

1

1111

1

1

1

16、(AB)

C7、(AB)C

结合律A(BC)A(BC)第十页，共六十七页，2022年，8月28日ABCB∧CA∨BA∨CA∨(B∧C)(A∨B)∧(A∨C)000

0

0

0

0

0001

0

0

1

0

0010

0

1

0

0

0011

1

1

1

1

1100

0

1

1

1

1101

0

1

1

1

1110

0

1

1

1

1111

1

1

1

1

18、A(B

C)9、A(B

C

)

分配律(AB)(AC)(AB)(AC)第十一页，共六十七页，2022年，8月28日10、(AB)11、(AB)德·摩根律A

B

ABAB﹁A﹁BA∨B﹁(A∨B)﹁A∧﹁B00

1

1

0

1

101

1

0

1

0

010

0

1

1

0

011

0

0

1

0

0第十二页，共六十七页，2022年，8月28日12、A(AB)A13、A(AB)A吸收律*ABA∧BA∨BA∨(A∧B)A∧(A∨B)00

0

0

0

001

0

1

0

010

1

1

1

111

1

1

1

1第十三页，共六十七页，2022年，8月28日20、

AB

AB

蕴涵等值式*假言易位22、

ABB

AAB﹁A﹁BA→B﹁A∨B﹁B→﹁A0011111011011110010001100111第十四页，共六十七页，2022年，8月28日等价否定等值式21、

AB(AB)(BA)等价等值式23、

ABB

AAB﹁A﹁BA→BB→AAB

(AB)(BA)BA001111111011010000100101000110011111第十五页，共六十七页，2022年，8月28日归谬论*24、

(AB)(AB)

A(AB)(AB)(﹁A∨B)∧(﹁A∨﹁B)﹁A∨(B∧﹁B)﹁A∨0﹁A第十六页，共六十七页，2022年，8月28日等值演算与置换规则1．

等值演算——由已知的等值式推演出新的等值式的过程2．置换规则设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中的所有的A后得到的命题公式，若BA，则(B)(A)判定方法——等值演算第十七页，共六十七页，2022年，8月28日例1利用等值演算证明下列等值公式(2)p(pq)(pq)解题思想：可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。(1)p(qr)(pq)r判定方法——等值演算第十八页，共六十七页，2022年，8月28日解：(1)p

(q

r)¬p

(q

r)¬

p(¬q

r)(¬

p¬

q)r

¬(p

q

)r（(p

q)r)蕴涵等值公式，置换规则蕴涵等值公式结合律德·摩根律蕴涵等值公式(1)p(qr)(pq)r第十九页，共六十七页，2022年，8月28日解：(2)pp

1p

(q¬

q)(p

q)(p

¬

q)同一律排中律分配律(2)p(pq)(pq)第二十页，共六十七页，2022年，8月28日例2证明p(qr)⇎(pq)r证方法一真值表法（自己证）方法二观察赋值法.易知000,010等是左边的成真赋值，是右边的成假赋值方法三用等值演算先化简两个公式，再观察.用等值演算不能直接证明两个公式不等值第二十一页，共六十七页，2022年，8月28日例3判别下列公式的类型(1)q

¬((¬

pq)

p)(2)(p

¬

p)((q

¬

q)

r)解题分析：真值表法可以判别公式类型(重言、永假、可满足)，但等值演算的方法更简捷。（3）((pq)(pq))r)第二十二页，共六十七页，2022年，8月28日解：(1)q

¬((¬

pq)

p)q

¬(q

p)分配律矛盾律同一律(1)q

¬((¬

pq)

p)q

(¬

q

¬

p)德·摩根律结合律排中律q¬((¬

p

p)(q

p))q¬(0(q

p))1¬

p(q¬

q)¬

p1零律故(1)是重言式第二十三页，共六十七页，2022年，8月28日

¬1000010(2)(p

¬

p)((q

¬

q)

r)解：(2)(p

¬

p)((q

¬

q)

r)1((q

¬q)

r)1(0

r)故(2)是矛盾式第二十四页，共六十七页，2022年，8月28日（3）((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其中101,111是成真赋值，000,010等是成假赋值.第二十五页，共六十七页，2022年，8月28日将下面一段程序简化：IfABthen

IfBCthenXelseYendElse

IfACthenYelseXendEnd

第二十六页，共六十七页，2022年，8月28日解实际问题（见书上例2.6）

在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人乙说王教授不是上海人，是苏州人丙说王教授既不是上海人，也不是杭州人听完以上3人的判断后，王教授笑着说，你们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？第二十七页，共六十七页，2022年，8月28日解:

设命题P:王教授是苏州人。Q:王教授是上海人。R:王教授是杭州人。设甲的判断为A1=┐P∧Q

乙的判断为A2=P∧┐Q

丙的判断为A3=┐Q

∧┐R则甲的判断全对B1=A1=┐P∧Q甲的判断对一半B2=（（┐P∧┐Q）∨（P∧Q））甲的判断全错B3=P∧┐Q乙的判断全对C1=A2=P∧┐Q乙的判断对一半C2=（（P∧Q）∨（┐P∧┐Q））乙的判断全错C3=┐P∧Q丙的判断全对D1=A3=┐Q

∧┐R丙的判断对一半D2=（Q

∧┐R）∨（┐

Q

∧R）丙的判断全错D3=Q

∧

R由王教授所说E=（B1∧C2∧D3）∨（B1∧C3∧D2）∨（B2∧C1∧D3

）∨（B2∧C3∧D1）∨（B3∧C1∧D2）∨（B3∧C2∧D1

）为真命题第二十八页，共六十七页，2022年，8月28日（1）文字——命题变项及其否定的总称（2）简单析取式——有限个文字构成的析取式p,q,pq,pqr,…（3）简单合取式——有限个文字构成的合取式p,q,pq,pqr,…（4）析取范式——由有限个简单合取式组成的析取式A1A2Ar(r1)（5）合取范式——由有限个简单析取式组成的合取式A1A2Ar(r1)（6）范式——析取范式与合取范式的总称

一、基本概念说明：单个文字既是简单析取式，又是简单合取式形如pqr,pqr的公式既是析取范式，又是合取范式§2.2析取范式与合取范式主要性质：简单析取式与简单合取式的性质见定理2.1析取范式与合取范式的性质见定理2.2第二十九页，共六十七页，2022年，8月28日定理2.3（范式存在定理）任何命题公式都存在着与之等值的析取范式与合取范式(1)消除┐,,

以外的联结词，如→和

其中 P→Q┐PQ PQ（┐

PQ）(P┐Q）(2)┐的削去或内移利用德.摩根定律把括号外┐内移(3)再利用在上的分配律：（P(QR)(PQ)(PR)）可得析取范式（P(QR)(PQ)(PR)）可得合取范式经过以上三步演算，便得到析取范式或合取范式。解题思想：第三十页，共六十七页，2022年，8月28日

例1：求(PQ)R的析取范式与合取范式。解:原式((PQ)R)∧(R(PQ))(┐(PQ)∨R)∧(┐R∨(PQ))(┐(┐P∨Q)∨R)∧(┐R∨┐P∨Q)((P∧┐Q)∨R)∧(┐R∨┐P∨Q)((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)((P∧┐Q)∧(┐R∨┐P∨Q))∨(R∧(┐R∨┐P∨Q))(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q)(析取范式)课堂练习求命题公式((pq)r)p的合取范式和析取范式.第三十一页，共六十七页，2022年，8月28日解：1)求合取范式((p

q)r)p(

¬(p

q)

r)p¬

(¬

(p

q)r)

p¬

(

(¬

p

¬

q)

r)p(¬

(¬p

¬

q)¬r)p((¬

¬p

¬

¬

q)¬

r)p((p

q)¬

r)p(p

q

p)(¬r

p)(p

q)(¬

rp)第三十二页，共六十七页，2022年，8月28日2)求析取范式((p

q)r)p¬

(¬(p

q)

r)p¬

(

(¬p

¬

q)

r)p(¬(¬p

¬

q)¬

r)p((¬¬p

¬

¬

q)¬

r)p(¬

(p

q)

r)p((p

q)¬

r)p(p

¬

r)

(q

¬

r)pp

(q

¬

r)(吸收律)第三十三页，共六十七页，2022年，8月28日谁是说谎者？张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，请问三人到底谁说真话，谁说假话?解:

设A：张三说真话；B：李四说真话；c：王五说真话．依题意第三十四页，共六十七页，2022年，8月28日极小项：含有n个命题变元的简单合取式,极大项：含有n个命题变元的简单析取式，且具有形式：且具有形式：主析取范式与主合取范式1、

极小项与极大项注2.极小项，极大项中必含有n–1个联结词(或)注3.一定位于第i个位置，顺序不能乱。注1.其中指Pi或¬Pi，1in第三十五页，共六十七页，2022年，8月28日由p,q两个命题变项形成的极小项与极大项由下表给出极小项极大项公式成真赋值名称公式成假赋值名称pqpqpqpq

00011011m0m1m2m3

pqpq

pq

pq

00011011M0M1M2M3第三十六页，共六十七页，2022年，8月28日由p,q,r三个命题变项形成的极小项与极大项由下表给出.极小项极大项公式成真赋值名称公式成假赋值名称p

qrp

qrpq

rpqrp

qrp

qrpq

rpqr000001010011100101110111m0m1m2m3m4m5m6m7

pqrpq

rp

qrp

qrpqrpq

rp

qrp

qr000001010011100101110111M0M1M2M3M4M5M6M7mi与Mi的关系由书上定理2.4给出，即miMi,Mimi

第三十七页，共六十七页，2022年，8月28日主析取范式：与命题公式A对应的析取范式中的简单合取式全是极小项，主合取范式：与命题公式A等值的合取范式中的简单析取式全是极大项，定理2.5

任何命题公式都存在着与之等值的主析取范式与主合取范式，并且是唯一的。第三十八页，共六十七页，2022年，8月28日例1：求(PQ)R的主析取范式。解:原式(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q)(析取范式)(P∧┐Q∧┐R)∨((R∧┐P)∧(Q∨┐Q))∨

((P∨┐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)(主析取范式)m1∨m3∨m4∨m7第三十九页，共六十七页，2022年，8月28日

例2：求(PQ)R的主合取范式。解:原式((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)((P∨R)∨(Q∧┐Q))∧((P∧┐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

)

(主合取范式)M0∧M2∧M5∧M6第四十页，共六十七页，2022年，8月28日例求命题公式A＝¬(pq)(pq)的主析取范式和主合取范式求命题公式的主析取范式和主合取范式的两个基本方法：真值表法和等值演算解题思想：第四十一页，共六十七页，2022年，8月28日解：本例采用真值表法(1)先构造A的真值表 p

q¬(pq)(pq)pqA0 00100100110011010111001(2)

根据成真赋值写出对应极小项，并排序；根据成假赋值定出对应的极大项,并全部排序;成真赋值01，10，对应的极小项m1=¬pq

m2=p¬

q;成假赋值00，11，对应的极大项M0=pqM3=¬p¬q;

(3)按(2)中约定的顺序写主析取范式和主合取范式:主析取式：m1

m2主合取范式：M0

M3A＝¬(pq)(pq)第四十二页，共六十七页，2022年，8月28日课堂练习求公式A＝((pr)q)(qp)的主析取范式和主合取范式第四十三页，共六十七页，2022年，8月28日(1)先构造A=((pr)q)(qp)的真值表：

(pr)q(pr)q

pAp

q

r000001010011100101110111

1

1

1

1

1

1

1

1

1

100

1

10000

10

1

1

1

1

0

1

1

1

1

1

1

1解法一：用真值表法第四十四页，共六十七页，2022年，8月28日(2)成真赋值000，001，101，110，111，成假赋值010，011，100，m7=pq

r;m6=p

q

¬

rm5=p¬

q

r，m1=¬

p

¬

q

rm0=¬

p¬

q

¬

r， M2=p

¬

q

r，M3=p

¬

q

¬

rM4=¬

pq

r对应的极小项对应的极大项(3)主析取范式：m0

m1

m5

m6m7主合取范式：

M2M3

M4第四十五页，共六十七页，2022年，8月28日解法二：等值演算(以求主析取范式为例)(1)将命题公式化归为等值的析取范式。A((¬p

r)

q)(¬

q

p)((¬pr)(¬

q

p))(q

(¬q

p))(¬

p

¬

q)(r

¬

q)(r

p)(q

p)求公式A＝((pr)q)(qp)的主析取范式和主合取范式(¬p

(¬

qp)(r

(¬

qp))((q¬

q)(q

p))

(¬

p¬

q)(¬

p

p))(r

¬

q)(r

p)(qp)第四十六页，共六十七页，2022年，8月28日(2)检查每一个简单合取式，对其中没有出现的命题变元，在其相应的位置上添加一个析取项即：(¬

p

¬

q

(r

¬r))((p¬

p)¬q

r)(p(q

¬

q)r)(p

q

(r

¬

r))(¬

p

¬

q)(r

¬

q)(r

p)(q

p)第四十七页，共六十七页，2022年，8月28日(3)利用分配律展开(2)中添加项,去掉相同的极小项，即：(¬p

¬

q

r)(¬p

¬q

¬

r)(p

¬

q

r)(¬

p¬

q

r)(p

q

r)(p

¬

q

r)(p

qr)(p

q

¬r)(¬p¬

qr)(¬p¬

q¬

r)(p¬

qr)(pqr)(p

q

¬

r)(4)按字典法排序，即：(¬

p

¬

q

¬

r)(¬p

¬q

r)(p

¬q

r)(p

q

¬

r)(p

q

r)第四十八页，共六十七页，2022年，8月28日

2、主范式的用途——与真值表相同.

（1）求公式的成真成假赋值

(pq)r

m1m3m5

m6m7，其成真赋值为001,011,101,110,111，当然成假赋值为000,010,100.类似地，由主合取范式也立即求出成假或成真赋值.第四十九页，共六十七页，2022年，8月28日（2）判断公式的类型设A含n个命题变项.A为重言式

A的主析取范式含2n个极小项

A的主合取范式不含任何极大项，记A的主合取范式为1

。

A为矛盾式

A的主合取范式含2n个极大项

A的主析取范式不含任何极小项，记A的主析取范式为0。

A为非重言式的可满足式

A的主析取范式中至少含一个（但不是全部）极小项

A的主合取范式中至少含一个（但不是全部）极大项第五十页，共六十七页，2022年，8月28日（3）判断两个公式是否等值例

用主析取范式判两个公式是否等值(pq)r与(pq)r解

(pq)r=m1m3

m4m5

m7

(pq)r=m0m1m2m3

m4m5

m7显见，两公式不等值.第五十一页，共六十七页，2022年，8月28日（4）解实际问题有—仓库被盗，公安人员经侦察，怀疑甲、乙、丙和丁四人作案，又经细查，知道这四人中只有两人作案，在盗窃案发生的那段时间，可靠的线索有：

(1)甲、乙两人中有且只有一个人去过仓库；

(2)乙和丁不会同时去仓库；

(3)丙若去仓库，丁必一同去；

(4)丁若没去仓库，则甲也没去．试判断四人个哪两人去仓库作案?解:设A:甲作案。B:乙作案。C:丙作案。D:丁作案。第五十二页，共六十七页，2022年，8月28日（4）解实际问题（见书上例2.12）某科研所有三名青年高级工程师A，B，C。所里要选派他们中的1到2人出国进修，由于所里工作的需要，选派时必须满足以下条件：①若A去，则C也可以去②若B去，则C不能去③若C不去，则A或B可以去问所里应如何选派他们？解:

设P:派A去。Q:派B去。R:派C去。根据所要满足的条件，得命题公式为：

(PR)∧(Q

┐R)∧(┐R(P∨Q))第五十三页，共六十七页，2022年，8月28日解:

命题公式为：

(PR)∧(Q

┐R)∧(┐R(P∨Q))

求此公式的主析取范式:

原式(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(P∧┐Q∧R)因此有三种选派方案：Ｃ去，而Ａ、Ｂ都不去；Ｂ去，而Ａ、Ｃ都不去；Ａ、Ｃ都去，而Ｂ不去.第五十四页，共六十七页，2022年，8月28日一、真值函数1．

问题的提出问：含n个命题变项的所有公式共产生多少个互不相同的真值表？答案为个§2.3联结词的完备集0100110101书上表2.5第五十五页，共六十七页，2022年，8月28日书上表2.6第五十六页，共六十七页，2022年，8月28日2、真值函数的定义称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数为n元真值函数，定义域中的元素为2n个长为n的0,1组成的符号串.常用F:{0,1}n{0,1}表示F是n元真值函数.易知，全体n元函数共有个.设F:{0,1}n{0,1}，且F(00)=F(01)=F(11)=0，F(10)=1，则F为一个确定的2元函数.第五十七页，共六十七页，2022年，8月28日3、命题公式与真值函数对于任何一个含n个命题变项的命题公式A，都存在唯一的一个n元真值函数F为A的真值表，等值的公式对应的真值函数相同.于是解决了1提出的问题.n=2时，每个命题公式的真值表都可以在书上表2.6中找到.例如：pq,pq,(pq)((pq)q),…,都对表2.6中的

第五十八页，共六十七页，2022年，8月28日定义2.7

设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集说明：若S是联结词完备集，则任何命题公式都可由S中的联结词所表示定理2.6S={,,}是联结词完备集证明的关键：主析取（主合取）范式存在唯一性定理联结词的完备集

第五十九页，共六十七页，2022年，8月28日推论以下联结词集都是完备集（1）S1={,,,}（2）S2={,,,,}（3）S3={,}（4）S4={,}（5）S5={,}联结词的完备集证明线索：若S