离散数学及应用 课件 第1章 命题逻辑

DiscreteMathematics离散数学大家心中的离散数学？2离散数学的知识体系还有哪些？我发誓我再也不发誓了德国数学家、哲学家莱布尼茨(1647~1716)首先提出用数学方法研究逻辑,就是建立一套表意符号体系,在符号之间进行形式推理.莱布尼茨是数理逻辑的创始人.也正因为这样,数理逻辑又称为符号逻辑.逻辑学是研究思维形式及思维规律尤其是推理的学科,早在两千多年前就受到人们的重视,古希腊著名逻辑学家亚里士多德(公元前384~公元前322)是形式逻辑的创始人.数理逻辑的发展历程秒懂逻辑学

逻辑学:

研究人的思维形式和规律的科学．由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑．数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，这里所指的数学方法就是引进一套符号体系的方法。简言之数理逻辑是计算理论的基础，计算理论是计算机科学的核心基础。数理逻辑学家的工作对于通用计算机的产生是决定性的，许多计算机科学的先驱既是数学家又是逻辑学家。符号主义认为智能是基于逻辑规则的符号操作数理逻辑的重要性EdsgerW.Dijkstra（图灵奖获得者）我（迪杰斯特拉）现在年纪大了,做了这么多年的软件,错误不知道犯了多少,现在觉悟了,我想假若我早年在数理逻辑上好好下点工夫的话,我就不会犯这么多的错误。不少东西,逻辑学家早就说了,可我不知道。要是我能年轻20岁,我要回去学习逻辑。专家系统架构在python中实现基于不同推理规则的医疗专家系统网页、APP的形式都可以项目介绍数理逻辑学命题逻辑谓词逻辑1.1

命题及联结词

命题与真值原子命题复合命题联结词

命题与真值注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不唯一确定的也不是命题命题：判断结果唯一的陈述句真值：命题的判断结果，包括真与假，分别用1和0表示真命题：真值为真的命题假命题：真值为假的命题

判断下列句子中哪些是命题？

(1)深职大在深圳.(2)2+5＝8.(3)x+3＞5.(4)深职大校园美吗？

(5)深职大校园真美啊！

(6)请说普通话！

真命题假命题真值不确定疑问句感叹句祈使句(3)~(6)都不是命题课堂练习

课后习题的第1题课堂练习命题的分类

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题

例:“你是风儿。”，“我是沙。”——简单命题“你是风儿，我是沙。”——复合命题对应：自然语言中“并非……”，“不……”，“没有……”等

例：令p：雪是白色的

则p的否定

：雪不是白色的

表示逻辑上相反的意思思考：“雪是黑色的”是不是p的否定

？

“今天是晴天”的否定？联结词与复合命题

1.否定式与否定联结词“

”P¬P0110p的真值与

p的真值相反联结词与复合命题

1.否定式与否定联结词“

”

定义

设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作

p.符号

称作否定联结词，并规定

p

为真当且仅当p为假.例：令p为3是偶数

则：

p

为3不是偶数从键盘输入命题p的真值，程序自动输出

p

（假设为r）的真值注意：利用Pycharm编程实现，将代码保存，后面需要用到。

函数命名规则：用大写首字母。

课堂练习r=FD(p)print("pleaseinputp:")

p=int(input())

ifp==0:

r=1

else:

r=0

print("theresultis:")

print(r)

参考答案：否定式与否定联结词将该代码转换为函数：r=FD(p)参考答案：否定式与否定联结词defFD(p)ifp==0:

r=1

else:

r=0

returnr情景引入“我爱深职大，他也爱深职大”，这个命题该如何进行符号化？利用否定联结词，无法实现，需要根据逻辑关系，引入其他的联结词。联结词与复合命题(续)

2.合取式与合取联结词“∧”

对应：自然语言中“与”,“和”,“也”,“且”,“既.…又…”,“不仅…而且…”,“虽然…但是…”,“一面…一面…”等；英文中的and.例如：深职大不仅校园很美，而且学生很优秀.

小芳长的好看，又善良.张辉和王丽都是好学生.注意：不是所有的“与”、“和”等都能用合取联结词替代.例如：张辉和王丽是同学.联结词与复合命题

2.合取式与合取联结词“∧”

定义

设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词，并规定

p∧q为真当且仅当p与q同时为真.PQP∧Q000110110001合取式与合取联结词从键盘输入两个命题p和q的真值，求它们的合取式p∧q的真值（假设为r）学习通APP提交代码截图p=int(input("pleaseinputp:"))

q=int(input("pleaseinputq:"))

ifp==1andq==1:

r=1

else:

r=0

print("theresultis:“+str(r))参考答案：合取式与合取联结词将该代码转换为函数：r=HQ(p,q)联结词与复合命题(续)对应：自然语言中的“或”，英文中的“or”.注意：“或”联结的两个命题可以具有相容性，也可以具有排斥性。前者称为相容或，后者称为排斥或。析取联结词∨指的是“相容或”。例如：小明或小红是学生（相容或）。

国庆节是周一或者周二（排斥或）。3.析取式与析取联结词“∨”联结词与复合命题

定义设p,q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.3.析取式与析取联结词“∨”

PQP∨Q000110110111联结词与复合命题

p=int(input("pleaseinputp:"))

q=int(input("pleaseinputq:"))

ifp==0andq==0:

r=0

else:

r=1

print("theresultis:“+str(r))从键盘输入两个命题p和q的真值，求它们的析取式的真值（假设为r）将该代码转换为函数：r=XQ(p,q)联结词与复合命题(续)4.蕴涵式与蕴涵联结词“

”对应：在自然语言中，“如果p,则q”这种命题还有其它叙述方式，比如：“只要p,就q”，“因为p，所以q”,“p仅当q”,“只有q才p”，“除非q才p”,“除非q，否则非p”等等，它们都可符号化为p→q。例如：因为深职大是最好的学校，所以我来这里学习。

只有学好本领，我们才能找到好工作。联结词与复合命题

定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作p

q，并称p是蕴涵式的前件，q为蕴涵式的后件.

称作蕴涵联结词，并规定，p

q为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“

”PQP→Q000110111101联结词与复合命题

p=int(input("pleaseinputp:"))

q=int(input("pleaseinputq:"))ifp==1andq==0:

r=0

else:

r=1

print("theresultis:“+str(r))从键盘输入两个命题p和q的真值，求它们的蕴涵式的真值（假设为r）将该代码转换为函数：r=YH(p,q)联结词与复合命题(续)对应：自然语言中的“等价”、“当且仅当”、“充要条件”，英文中“ifandonlyif”例子：三角形相等当且仅当三条边相等5.等价式与等价联结词“

”联结词与复合命题定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p

q.

称作等价联结词.并规定p

q为真当且仅当p与q同时为真或同时为假.5.等价式与等价联结词“

”PQP

Q000110111001说明:

(1)p

q的逻辑关系:p与q互为充分必要条件

(2)p

q为真当且仅当p与q同真或同假联结词与复合命题

p=int(input("pleaseinputp:"))

q=int(input("pleaseinputq:"))if(p==1andq==1)and(p==0andq==0):

r=1

else:

r=0

print("theresultis:“+str(r))从键盘输入两个命题p和q的真值，求它们的等价式的真值（假设为r）将该代码转换为函数：r=DJ(p,q)课堂练习课后习题的第3题，判断是否为公式扩展扩展本章小节否定：

p

为真当且仅当p为假.合取：

p∧q为真当且仅当p与q同时为真.析取：

p∨q假当且仅当p与q同时为假.蕴涵：

p

q为假当且仅当p为真q为假（表1-2）.由假命题，如何推出真命题？由于p的前提是假的，它们不提供任何新的信息，不能用来判断q的真假，推出的q都为真.等价：

p

q为真当且仅当p与q同时为真或同时为假.本章小结以上给出了5个联结词：

,

,

,

,

，组成一个联结词集合{

,

,

,

,

}，

联结词的优先顺序为：

,

,

,

,;

如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;

若遇有括号时，应该先进行括号中的运算.本章小结PQP®Q000110111101PQP«Q000110111001PQPÚQ000110110111PQPÙQ000110110001PØP0110DiscreteMathematics鄢小虎

离散数学课程引入

如何判断两个命题公式相同？将命题符号化之后，使用真值表，判断命题所有可能的真值是否相等；若相等，则命题相等。

如何构建真值表？1.2命题公式及分类命题符号化命题变项与合式公式公式的赋值真值表命题的分类

例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.解令p：王晓用功，q：王晓聪明，则

(1)p∧q(2)p∧q(3)q∧

p.

例将下列命题符号化.(4)张辉与王丽都是三好生.(5)我爱深职大，他也爱深职大.(6)我在深职大，但他不在深职大.

令r:张辉是三好学生，s:王丽是三好学生

(4)r∧s.令r:我爱深职大，s:他爱深职大

(5)r∧s.令r:我在深职大，s:他在深职大

(6)r∧

s.课堂练习例

将下列命题符号化

(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)如果他没来见你，那么他或者是生病了，或者是不在本地.(5)只要明天不下雨或不下雪，我就去学校.

课堂练习解

令p:2是素数,q:3是素数,r:4是素数,s:6是素数,

则(1),(2),(3)均为相容或.

分别符号化为:p∨r,p∨q,r∨s,

它们的真值分别为1,1,0.

(4)令P：他来见你；Q：他生病；R：他在本地，则该语句可符号化为(5)

例

设p:天冷，q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)如果天不冷，则小王不穿羽绒服.

p

qp

q

q

p

p

q求下列复合命题的真值（提示先符号化）

(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝4当且仅当美国位于非洲.

1100课堂练习利用函数r=DJ(p,q)是否得到相同的真值？

课后习题的第2题课堂练习命题变项与合式公式

命题常项：简单命题命题变项：真值不确定的陈述句定义

合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r,…,pi,qi,ri,…,0,1

是合式公式(2)若A是合式公式，则(

A)也是合式公式(3)若A,B是合式公式，则(A

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式说明:外层括号可以省去

合式公式的层次定义

(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一：

(a)A=

B,B是n层公式；

(b)A=B

C,其中B,C分别为i层和j层公式，且

n=max(i,j)；

(c)A=B

C,其中B,C的层次及n同(b)；

(d)A=B

C,其中B,C的层次及n同(b)；

(e)A=B

C,其中B,C的层次及n同(b).合式公式的层次(续)

例如公式

p0层

p1层

p

q2层

(p

q)

r3层

((

p

q)

r)

(

r

s)4层公式的赋值

定义

给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值说明：

赋值

=

1

2…

n之间不加标点符号，

i=0或1.

A中仅出现p1,p2,…,pn，给A赋值

1

2…

n是指p1=

1,p2=

2,…,pn=

n

A中仅出现p,

q,r,…,给A赋值

1

2

3…是指p=

1,q=

2,r=

3…

含n个变项的公式有2n个赋值.

真值表

真值表:公式A在所有赋值下的取值情况列成的表

构成真值表的具体步骤:（1）找出命题公式中所含的所有命题变元，变元按字母顺序排列；（2）列出变元所有可能的赋值，以二进制从小到大顺序排列；（3）按从低到高的顺序写出各层次;（4）对应每个赋值，计算命题公式各层次的值，直到最后计算出命题公式的值。例给出公式的真值表

A=(q

p)

q

p

的真值表pq

q

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

1111写出以下公式的真值表

A=(q

p)

r

的真值表课堂练习键盘输入p、q的值，程序自动输出以下公式的真值：A=(p

q)

q

p.否定词“¬”：r=FD(p)合取词“∧”：r=HQ(p,q)析取词“∨”：r=XQ(p,q)蕴含词“

”：r=YH(p,q)等价词“

”：r=DJ(p,q)提示：将命题写成函数参考答案：deffunA(p,q)returnYH(HQ(YH(p,q),q),p)例B=(

p

q)

q

的真值表pq

p

p

q

(

p

q)

(

p

q)

q00011011

1100110100100000实例将以上命题写成函数？将命题写成函数参考答案：deffunB(p,q)returnHQ(FD(XQ(FD(p),q),q)例C=(p

q)

r

的真值表pqrp

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

11101010将以上命题写成函数？将命题写成函数参考答案：deffunC(p,q,r)returnYH(XQ(p,q),FD(r))公式的类型

定义设A为一个命题公式

(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式

A=(q

p)

q

p，B=(

p

q)

q，C=(p

q)

r

课后习题的第3题(5)-(7)课堂练习本章小结否定：

p

为真当且仅当p为假.合取：

p∧q为真当且仅当p与q同时为真.析取：

p∨q假当且仅当p与q同时为假.蕴涵：

p

q为假当且仅当p为真q为假（表1-2）.由假命题，如何推出真命题？由于p的前提是假的，它们不提供任何新的信息，不能用来判断q的真假，推出的q都为真.等价：

p

q为真当且仅当p与q同时为真或同时为假.本章小结真值表：公式A在所有赋值下的取值情况列成的表重难点是对公式进行分层，按如下规则分层：联结词的优先顺序为：

,

,

,

,;

如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;

若遇有括号时，应该先进行括号中的运算.DiscreteMathematics鄢小虎

离散数学课程引入

为什么需要进行等值演算？n个命题变项，共有2n个可能的赋值，有2n行，计算量太大。例如：6个命题变项，有64行，这是不能接受的。

如何进行等值演算？1.3命题逻辑等值演算

等值式基本等值式代入定理、置换定理等值演算等值式

定义若等价式A

B是重言式，则称A与B等值，记作A

B，并称A

B是等值式说明：A,B,

均为元语言符号,

与、=不同，不能混为一谈。

是关系符，不是联结词，不能进行运算。“”的三个性质1.自反性A

A。2.对称性若A

B则B

A。3.传递性若A

B,B

C则A

C。A,B是否等值等价于A,B的真值表是否相同。课堂测验用真值表和编程验证以下公式是否等值（6分钟）请验证：p

(q

r)

(p

q)

r

(p

q)

r参考课本第9页的表1-5，1-6

基本等值式

双重否定律

:

A

A等幂律：

A

A

A,A

A

A交换律:A

B

B

A,A

B

B

A结合律:(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律:A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)真值表验证等值式(a)

AA双重否定(b)AAA 等幂律课堂练习：用真值表和编程证明分配律：

A

(B

C)

(A

B)

(A

C)基本等值式(续)德·摩根律:

(A

B)

A

B

(A

B)

A

B吸收律:A

(A

B)

A,A

(A

B)

A零律:A

1

1,A

0

0同一律:A

0

A,

A

1

A排中律:A

A

1矛盾律:A

A

0基本等值式(续)蕴涵等值式:A

B

A

B等价等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等价否定等值式:A

B

A

B归谬论:(A

B)

(A

B)

A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础真值表验证等值式用真值表证明常用等式（10分钟）蕴涵等值式:A

B

A

B等价等值式:A

B

(A

B)

(B

A)德·摩根律:

(A

B)

A

B

如何利用程序验证？等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式（16个）

(3)置换规则吸收律等值演算与置换规则

置换规则：若A

B,则

(B)

(A).

将

作为函数进行推理代换规则：证明两个公式等值

证明:

Q→（P

（P

Q））

Q→P

证：Q→（P

（P

Q））

Q→P~~~~~~~~~P（吸收律）证明两个公式等值

证明两个公式等值

证明：

p

(q

r)

(p

q)

r（前面真值表证明过）

课堂练习:从右边开始演算一遍（5分钟）提示：去掉

证

p

(q

r)

p

(

q

r)（蕴涵等值式，置换规则）

(

p

q)

r

（结合律，置换规则）

(p

q)

r

（德

摩根律，置换规则）

(p

q)

r

（蕴涵等值式，置换规则）课堂练习习题7中的(2)-(4)判断公式类型

用等值演算法判断下列公式的类型(真值表？编程实现？)(1)P→(Q→P)

提示：去除

和括号（蕴涵等值式）（排中等值式）（零律等值式）（交换律+结合律）解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德

摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.

用等值演算法判断下列公式的类型（编程验证）(2)q

(p

q)

提示：去除

、

和括号用等值演算法判断下列公式的类型（编程验证）(3)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律，将

p

q

设为A）

1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？A

A

(A

A

)

(A

A

)（去除

和

）

(

A

A

)

(

A

A

)

11

1课堂练习习题6中的(1)-(3)DiscreteMathematics鄢小虎

离散数学课前复习16个重要的等值式，还记得哪些？等值演算的基本思路是怎么样的？有哪些作用？1.4范式

析取范式与合取范式

主析取范式与主合取范式

课程引入

为什么需要范式？由上节等值演算可知，与一个给定命题等值而形式不同的命题可以有无穷多个。存在大量的命题公式看起来互不相同，实际上是等价的。需要通过标准形式，判断命题是否相等。（形似神似）

如何把命题化为标准形式（范式）？析取范式与合取范式

质析取式:有限个命题变项或其否定构成的析取式如p,

q,p

q,p

q

r,…质合取式:有限个命题变项或其否定构成的合取式如p,

q,p

q,p

q

r,…析取范式:由有限个质合取式组成的析取式

A1

A2

Ar,其中A1,A2,,Ar是质合取式合取范式:由有限个质析取式组成的合取式

A1

A2

Ar,其中A1,A2,,Ar是质析取式析取范式与合取范式(续)范式:析取范式与合取范式的总称

公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：

简单命题p,

q既是质析取式，又是质合取式命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：

(1)消去A中的

,

（若存在）

(2)否定联结词

的内移或消去

(3)使用分配律

对

分配（析取范式）

对

分配（合取范式）公式的范式存在，但不唯一命题公式的范式

求范式的步骤：求公式的范式举例

解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（

A由3个质合取式

p、

q、

r组成的析取式），又是A的合取范式（将

p

q

r置换为P，A由一个质析取式组成的合取式P）例

求下列公式的析取范式与合取范式（1）A=(p

q)

r求公式的范式举例(续)解：

P

（P→Q）

P

（

P

Q）

（P

P）

（P

Q）

0

（P

Q）

P

Q(2)求P

（P→Q）的析取范式与合取范式（消去

）（分配律）（矛盾律）（同一律）P

Q既是析取范式，也是合取范式求公式的范式举例(续)解

(p

q)

r

(

p

q)

r

（消去第一个

）

(

p

q)

r

（消去第二个

）

(p

q)

r

（否定号内移——德

摩根律）这一步已为析取范式（由两个质合取式构成）继续：

(p

q)

r

(p

r)

(q

r)（

对

分配律）这一步得到合取范式（由两个质析取式构成）

(3)求B=(p

q)

r析取范式与合取范式课堂练习

习题12中(1)-(2)，计算析取范式、合取范式请同学上台推理极小项与极大项定义

在含有n个命题变项的质合取式(质析取式)中，若每个命题变项与其否定出现且仅出现一次，称这样的质合取式(质析取式)为极小项(极大项）.说明：n个命题变项产生2n个极小项和2n个极大项在极小项和极大项中文字均按下标或字母顺序排列用mi表示第i个极小项，其中i是该极小项成真赋值的十

进制表示.用Mi表示第i个极大项，其中i是该极大项成

假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

由p,q,r三个命题变项形成的极小项与极大项

极小项

极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

主析取范式与主合取范式

主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

A的主析取范式:与A等值的主析取范式

A的主合取范式:与A等值的主合取范式.

真值表求主析取范式与主合取范式

掌握例1.21的求法求主析取范式，找出表中真值为真的行，编码对应的极小项，组成的析取式求主合取范式，找出表中真值为假的行，编码对应的极大项，组成的合取式课堂练习

习题13中(1)，计算主析取范式、主合取范式请同学上台推理主析取范式与主合取范式

定理

任何命题公式都存在唯一的主析取范式和

主合取范式。作用：判断两个命题是否等值；判断公式的类型。对应关系主析（合）取范式与析（合）取范式的区别:每一项都是由极小（大）项构成的。简单而言：每一项中都含义所有的命题变项，例如p、q、r…主析（合）取范式对应于析（合）取范式极小（大）项对应于质合取（析取）式小结掌握析取范式与合取范式：等值演算求解了解主析取范式与主合取范式：用真值表求解DiscreteMathematics鄢小虎

离散数学1121.5联结词全功能集

联结词全功能集与非联结词,或非联结词113课程引入为什么要有联结词全功能集？

目前有很多的联结词，但是不同的联结词之间是可以相互推导的，存在一定的冗余（例如：蕴涵、等价等值式）。一个形式系统中，有多少个联结词是最合适的呢？全功能集不仅需要少，而且能表达所有真值函数。114联结词的全功能集定义

设S是一个联结词集合，如果任何n(n

1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.

设S1,S2是两个联结词集合，且S1

S2.若S1是全功能集，则S2也是全功能集.

反之，若S2不是全功能集，则S1也不是全功能集.115联结词全功能集实例定理{

,∧,∨}、{

,∧}、{

,∨}、{

,→}都是联结词全功能集.证明每一个真值函数都可以用一个主析取范式表示,故{

,∧,∨}是联结词全功能集.p∨q

(

p∧

q)，由德摩根律（反用），则∨可以由{

,∧}替代，故{

,∧}是全功能集.

p∧q

(

p∨

q)，同理，故{

,∨}是全功能集.p→q

p∨q，同理，故{

,→}也是全功能集.116复合联结词

与非式:p

q(p

q)或非式:p

q(p

q)

定理{

},{

}是联结词全功能集.证明：{

},{

}包括{

，∧,∨}，因此{

},{

}是全功能集.组合电路逻辑门:实现逻辑运算的电子元件.与门,或门,非门组合电路:实现命题公式的由电子元件组成的电路.117与门（合取）或门（析取）非门（否定）xx∧yx∨y

xyxyx课堂练习

习题12中(3)-(4)，计算析取范式、合取范式请同学上台推理1191.7

推理理论

推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明

直接证明法,附加前提证明法,归缪法120推理的形式结构—问题的引入

推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若AÈCÍBÈD，则AÍB且CÍD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确的过程.121推理的形式结构定义若对于每组赋值，或者A1ÙA2Ù…Ù

Ak

均为假，或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,…,Ak

推B”的推理正确当且仅当A1ÙA2Ù…ÙAk®B为重言式.推理的形式结构:A1ÙA2Ù…ÙAk®B或前提：A1,A2,…,Ak

结论：B

若推理正确，则记作：A1ÙA2Ù…ÙAkÞB.122判断推理是否正确的方法真值表法等值演算法判断推理是否正确主析取范式法构造证明法证明推理正确说明：用前3个方法时采用形式结构

“A1ÙA2Ù…ÙAk®B”.用构造证明时,采用

“前提:A1,A2,…,Ak,结论:B”.

123实例例判断下面推理是否正确

(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.

解设p：今天是1号，q：明天是5号.推理的形式结构为:(p®q)Ùp®q证明（用等值演算法）

(p®q)Ùp®q

Û

Ø((ØpÚq)Ùp)Úq

Û

ØpÚØqÚq

Û1得证推理正确124实例(续)(2)若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.

推理的形式结构为:(p®q)Ùq®p

证明（用主析取范式法）

(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

Ø((ØpÚq)Ùq)Úp

Û

ØqÚp

Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq)

Û

m0Úm2Úm3

结果不含m1,故01是成假赋值，所以推理不正确.125推理定律——重言蕴涵式

重要的推理定律

A

Þ(AÚB)附加律

(AÙB)Þ

A

化简律

(A®B)ÙA

Þ

B

假言推理

(A®B)ÙØB

Þ

ØA

拒取式

(AÚB)ÙØB

Þ

A

析取三段论

(A®B)Ù(B®C)Þ(A®C)假言三段论

(A«B)Ù(B«C)Þ(A«C)等价三段论

(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难126推理定律(续)(A®B)Ù(ØA®B)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)

破坏性二难证明:描述推理过程的命题公式序列，其中每个命题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论.127推理规则

(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则

A®BA

\B(5)附加规则

A

\AÚB

(6)化简规则

AÙB

\A(7)拒取式规则

A®B

ØB

\ØA(8)假言三段论规则

A®B

B®C

\A®C

128构造证明之一——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课推理的形式结构为前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

129直接证明法(续)证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换编程实践作业根据推理理论，开发医疗专家系统，可以3-4人分组完成，比较系统的智能化水平。可以利用PyKe、PyClips库，或者自己开发推理引擎。如何实现有界面的？医疗诊断专家系统优化方向给出控制台的程序，对医疗专家系统进行优化，使系统更加智能好用，参考以下方向：1、增加规则库2、增加诊断建议3、使用rule-engine，PyKe、PyClips等推理引擎，比较不同情况4、使用界面实现输入输出推荐用rule-engine引擎#!/usr/bin/envpython3importrule_enginefromrule_engineimportRule,Context,SymbolResolutionErrorclassMedicalExpertSystem:def__init__(self):#初始化系统信息self.patient_data={}self.diagnoses=[]#定义所有可能的症状self.symptoms=["发烧","咳嗽","流鼻涕","喉咙痛","打喷嚏","头痛","肌肉疼痛","疲劳","呕吐","腹泻","胃痛","呼吸困难","胸闷","皮疹","关节疼痛"]#定义疾病知识库self.diseases={"普通感冒":{"rule":"咳嗽and流鼻涕and喉咙痛and打喷嚏andnot呼吸困难andnot胸闷","description":"普通感冒是一种病毒感染，通常影响上呼吸道，症状包括咳嗽、流鼻涕等。","recommendation":"多休息，多喝水，可服用非处方感冒药缓解症状。如症状持续超过一周，请就医。"},"流感":{"rule":"发烧and咳嗽and头痛and肌肉疼痛and疲劳","description":"流感是由流感病毒引起的急性呼吸道传染病，症状通常比普通感冒更严重。","recommendation":"建议休息，补充水分，可使用抗病毒药物。如出现高烧不退或呼吸困难，请立即就医。"},"肠胃炎":{"rule":"呕吐and腹泻and(胃痛or发烧)","description":"肠胃炎是胃肠道的炎症，通常由病毒或细菌感染引起，表现为呕吐和腹泻。","recommendation":"补充水分防止脱水，避免刺激性食物。如呕吐腹泻严重或持续超过24小时，请就医。"},"过敏反应":{"rule":"流鼻涕and打喷嚏and皮疹andnot发烧","description":"过敏反应是免疫系统对某些物质的过度反应，常见症状包括皮疹、打喷嚏等。","recommendation":"避免接触过敏原，可服用抗组胺药物缓解症状。如出现严重反应，请立即就医。"},"肺炎":{"rule":"发烧and咳嗽and呼吸困难and胸闷","description":"肺炎是肺部的感染，可能由细菌、病毒或真菌引起，需要及时治疗。","recommendation":"这可能是严重的疾病，请立即就医进行诊断和治疗。可能需要抗生素或其他药物。"},"关节炎":{"rule":"关节疼痛and(肌肉疼痛or疲劳)andnot发烧andnot咳嗽","description":"关节炎是关节的炎症，可能导致疼痛和肿胀，通常不伴随呼吸道症状。","recommendation":"建议休息，避免过度使用受影响的关节。如症状持续或加重，请咨询医生进行进一步评估。"}}#编译所有规则piled_rules=self._compile_rules()def_compile_rules(self):"""编译所有诊断规则"""compiled={}fordisease,infoinself.diseases.items():try:#编译规则rule=Rule(info["rule"])compiled[disease]={"rule":rule,"description":info["description"],"recommendation":info["recommendation"]}exceptrule_engine.errors.RuleSyntaxErrorase:print(f"规则编译错误（{disease}）:{e}")retur