离散数学教程_第1页
离散数学教程_第2页
离散数学教程_第3页
离散数学教程_第4页
离散数学教程_第5页
已阅读5页,还剩88页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2026/5/181上海电力学院离散数学教程2026/5/182

前言一、为什么要学习离散数学?

2、离散数学:是许多数学分支的总称.主要括: 数理逻辑,集合论,代数系统,图论.

1、专业的需要:

2、对本身素质的训练

二、连续数学与离散数学

1、连续数学:微积分,微分方程,复变函数等.

三.教学方法

1)引路2)预习3)作业4)章后总结2026/5/183前言四、参考书五、作业

1)《离散数学》耿素云等编著,高教出版社

2)《离散数学》何自强等编著,科学出版社如何使用参考书?

每章每节后看参考书,然后总结,压缩即:薄厚薄2026/5/184前言离散数学是现代数学的一个重要分支,是学习计算机科学与术的重要第一篇集合论(集合基本概念、关系、无限集)第二篇代数结构(代数系统、群、环、域、格)第三篇图论(图的基本概念以及不同类型的图)第四篇数理逻辑(命题逻辑和谓词逻辑)基础课之一。本课程以集合论、代数结构、数理逻辑、图论的四大部分为主干教学内容,并辅以组合论、数论基础、形式语言与自动机初步等内容。本教案选取课程的主干内容进行组织,包括:2026/5/185第1章命题逻辑数理逻辑是计算机科学的基础理论之一。可分为五大部分:第一篇数理逻辑第一章命题逻辑逻辑演算、集合论、证明论、模型论、递归论。数理逻辑既是数学又是逻辑学:它研究数学中的逻辑问题,用数学方法研究形式逻辑。计算机的硬件,软件,算法及语言都具有数理逻辑的性质。我们在此仅讲授数理逻辑的基础部分——逻辑演算部分。它包括命题演算和(一阶)谓词演算两部分。2026/5/186第1章命题逻辑第一篇数理逻辑第一章命题逻辑1.2联结词1.3命题公式与翻译1.4~1.5

命题逻辑的等值演算1.6其它联结词及联结词完备集1.1 命题及表示法1.7对偶与析取范式和合取范式(范式)1.8命题逻辑推理理论2026/5/187第2章谓词逻辑2.1谓词的概念与表示第一篇数理逻辑第二章谓词逻辑2.2命题函数与量词2.3~2.4一阶谓词公式2.5一阶谓词演算的等价式与蕴含式2.6一阶谓词前束范式2.7一阶逻辑的推理理论2026/5/1881.1命题及表示法命题逻辑研究的中心问题是推理,即研究推理中的前题和结论之

第一篇数理逻辑第一章命题逻辑定义1:命题是能判断真假的陈述句。定义2:真值是陈述句为真或假的这种性质。

间的形式关系,而不涉及前题和结论的具体内容。推理的基本单

位为命题。

注1:上命题必须是陈述句。而疑问句、祈使句和感叹句等不是命题。

注2:命题的真值是唯一的,但与我们是否知道它的真值无关。假命题:凡与事实不相符的命题,其真值为假。符号化:用“0”或“F”表示。真命题:凡与事实相符的命题,其真值为真。符号化:用“1”或“T”表示。2026/5/1891.1命题及表示法(1)三角形的三个内角和为180度。

第一篇数理逻辑第一章命题逻辑(2)4为素数。

例:判断下列语句是否为命题

(3)1+101=110

(4)你喜欢离散数学吗?(5)这朵花真美啊!(6)x>y(7)我正在说谎。2026/5/18101.1命题及表示第一篇数理逻辑第一章命题逻辑例:(1)P:“雪是黑的”命题符号化:一般用大写字母A,B,…,P,Q,…或带下标的大命题常元与命题变元写字母或数字表示。

(2)Q2:“上海是个美丽的城市”命题常元:表示具体确定内容的命题。命题变元:表示任意的,没有赋予具体内容的抽象命题。注1:命题变元与命题常元的区别注2:命题变元与命题常元在逻辑演算中处理原则相同。2026/5/18111.2命题联结词第一篇数理逻辑第一章命题逻辑若干个简单命题通过命题联结词而构成的新命题。

定义:简单命题(原子命题)不能再分解为更简单的命题。

1、否定词“

”注:“

”为一元运算,否定全部而非部分。2、合取词“

”

定义:复合命题定义:设P为一个命题,利用“

”与P组成复合命题称为P的否命题,记为“

P”。读作“非P”,其真值表见表1-1定义:设P和Q为两个命题,由P与Q用二元联结词“

”

成复合命题,记为“PQ”。读作“P且Q”

2026/5/18121.2命题联结词第一篇数理逻辑第一章命题逻辑PQ:例1:P:“李军聪明”,Q:“李军用功”注:内容上无联系的两个命题也可以组成具有确定真值的命题。 3:析取词“

”定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成例1:P:“开关坏了”,Q:“灯炮坏了”:PQ:注:“

”表示可兼或。不可兼或不能用“

”表示。PQ:“李军聪明且用功”复合命题,记为“PQ”。读作“P或Q”

例2:P:“1+11=100”,Q:“熊猫为稀有动物”2026/5/18131.2命题联结词

第一篇数理逻辑第一章命题逻辑4、条件“

”例2:小李下午去打蓝球或在宿舍玩电脑。

定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成复合命例1:有位父亲对儿子说:“如果我去书店,我一给你买光盘。”解:P:父亲去书店,Q:给儿子买光盘题,记为“PQ”。读作“如果P,则Q”,其中P为前件,Q为后件。只有当前件为真,后件为假时,PQ为假。试问:在何种情况下,这位父亲算失信?1)P=1,Q=13)P=0,Q=12)P=1,Q=04)P=0,Q=0注:善意的推论。2026/5/18141.2命题联结词第一篇数理逻辑第一章命题逻辑5、等价词(双条件)“

”例2:雪是黑的,仅当太阳从西方出来。等价于定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成复合命例:将下列命题符号化,并讨论它们的真值1)if:3+3=6,则雪是白的。如果雪是黑的,则太阳从西方出来。题,称为等价复合命题记为“PQ”。读作“P当且仅当Q”,当且仅P和Q的真值相同时,PQ为真。否则为假。2)if:3+3不等于6,则雪是白的。3)if:3+3=6,则雪不是白的。4)if:3+3不等于6,则雪不是白的。5)3为有理数当且仅当美国在亚洲。2026/5/18151.2命题联结词第一篇数理逻辑第一章命题逻辑解:P:3+3=6,Q:雪是白的

1)逻辑词的优先级别分别为:,,,,二、语句形式化1)P

Q,真值为1(P(1)Q(1))2)

P

Q,真值为1(

P(0)Q(1))3)P

Q,真值为0(P(1)

Q(0))5)P

Q,真值为0(P(1)Q(0))4)

P

Q,真值为1(

P(1)

Q(1))

P:3为有理数,Q:美国在亚洲推理问题:自然语言描述逻辑语言逻辑演算规律推理运算在命题形式化时,若命题包含多个联结词时,应注意联结词的运算规律。括号中的运算为最优先级。2026/5/18161.2命题联结词第一篇数理逻辑第一章命题逻辑2)同级联结词,按从左到右的次序运算。

例2:如果你和他不都是傻子,那么你们不会去自讨没趣。

例1:狗急跳墙例3:如果你走路看书,那么你一定会成为近视眼。

例4:如果明天天气好,我们去郊游;否则不去郊游。2026/5/18171.3命题公式及其赋值第一篇数理逻辑第一章命题逻辑一、命题公式(合式公式):由命题常元、命题变元、命题联结词及定义:命题公式的递归定义(简称公式)是否任何字符串都是命题呢?AB,A,B定义:设A为含有命题变元P1,P2,…,Pn的命题公式,给P1,圆括号等组成的字符串。1)单个命题变元为命题公式。2)if:P,Q为命题公式,则

P,PQ,PQ,PQ,PQ也为命题公式。3)仅有有限次地利用上述1)、2)产生的字符串才是命题公式。P2,…,Pn一组确定的真值,称为对A的一个赋值或解释或真值指派。2026/5/18181.3命题公式及其赋值

第一篇数理逻辑第一章命题逻辑成真赋值:若指定的一组值使A的真值为1,则这组值为成真赋值。规定:

1)若A中出现命题变项为P1,P2,…,Pn,给定A的赋值为

1,

成假赋值:若指定的一组值使A的真值为0,则这组值为成假赋值。

2)若A中出现命题变项为P,Q,R,…,给定A的赋值为

1,

2,…,二、定义:真值表2,…,

n,则指P1=

1,P2=

2,…,Pn=

n

n,则指P=

1,Q=

2,…,最后字母赋值

n。上述的

i,取值为0或1。将命题公式A在所有赋值情况列表,称为A的真值表。2026/5/18191.3命题公式及其赋值

第一篇数理逻辑第一章命题逻辑命题公式真值表构造步骤如下:2)按从低到高的顺序写出公式的各个层次。1)找出命题公式中的所有命题变元,按下标或字母次序排列,按二3)计算各个层次的真值,直到最后计算出公式的真值。注:两个公式有相同的真值表或不同的真值表是指真值表的最后例:求下列公式的真值表,并求成真赋值和成假赋值。三、命题公式的类型进制依次写出赋值。一列是否相同。2)(QP)R2026/5/18201.3命题公式及其赋值第一篇数理逻辑第一章命题逻辑定义:重言式或永真式定义:矛盾式或永假式定义:可满足式1)、3)同,2)、4)同。例:下列各公式中均含有两个变元P,Q,它们中哪些有相同的真值表?1)PQ,2)PQ,3)(PQ)

4)(PQ)(QP),5)PQ一个命题公式,如果对它含的命题变元的任一组赋值,取值恒为真。一个命题公式,如果对它含的命题变元的一组赋值,取值恒为假。一个命题公式,如果对它含的命题变元的至少有一组赋值,取值为真。2026/5/18211.4~1.5

命题逻辑的等值演算第一篇数理逻辑第一章命题逻辑一、等值式(等价公式)定义:命题公式的等价关系注1:A与B为等价公式可定义为AB为重言式。例2:判断下列公式是否等价?注2:AB不表示公式(命题),仅代表A与B之间逻辑等价公式。例1:证明设A与B为两个命题公式,若A与B有相同的真值表时称公式A与B为等价公式。记为:ABAB表示命题公式(命题)。1)P(QR)与(PQ)R2)(PQ)R与(PQ)R2026/5/18221.4~1.5命题逻辑的等值演算第一篇数理逻辑第一章命题逻辑“

”公式之间等价关系满足:2)幂等律:AAA,AAA等价式的基本定律:1)双重否定定律:A

A3)交换律:A

BBA,A

BBA4)结合律:

(A

B)CA(BC) (A

B)CA(BC)5)分配律:

A(BC)(AB)(AC)

A(BC)(AB)(AC)

1)自反性:A,AA2)对称性:A,B,if:AB,则BA3)可传递性:

A,B,R,if:AB,BR,则:AR2026/5/18231.4~1.5命题逻辑的等值演算

第一篇数理逻辑第一章命题逻辑8)零律:A

11,A006)德摩根律:

(A

B)BA

(A

B)BA7)吸收律:

A(AB)A

A(AB)A

9)同一律:A

0A,A1A

10)排中律:AA1

11)矛盾律:AA012)条件等价式:ABAB13)双等价等值式:

(AB)(AB)(BA)2026/5/18241.4~1.5命题逻辑的等值演算

第一篇数理逻辑第一章命题逻辑定义:等值演算16)归谬论:(AB)(AB)A14)假言易位:ABBA15)等价否定等价式:ABAB二、等值演算置换规律则设F(A)为包含公式A的命题公式,F(B)是用公式B置换了F(A)中所由一些等值式推算另一些等值式的过程。有A后得到的命题公式,若BA,则F(B)F(A)2026/5/18251.4~1.5命题逻辑的等值演算

第一篇数理逻辑第一章命题逻辑1)解:(PQ)R(PQ)R例2:用等值演算证明等值式例1:(PQ)R(PQ)R

1)(PQ)R(PR)(QR)2)(PQ)(PQ)(QP)例3:用等值演算判断下列公式的类型(PQ)R3)P(PQ)PQ2026/5/18261.4~1.5命题逻辑的等值演算第一篇数理逻辑第一章命题逻辑三、蕴含式1)(PQ)(PQ)定义:当且仅当PQ是一个重言式时,我们称“P蕴含Q”,并记作PQ。对于PQ来说,除P的真值取T,Q的真值取F这样一种指派时,PQ2)(P(PQ))RTRF 证明P

Q,即是证明PQ是重言式。的真值为F外,其余情况,PQ的真值为T。故要证P

Q,只需对条件命题PQ的前件P,指定真值为T,若由此推出Q的真值亦为T,则PQ是重言式,即P

Q成立;同理,如对条件命题PQ中,假定后件Q的真值取F,若由此推出P的真值亦为F,即推证了QP故P

Q成立。2026/5/18271.4~1.5命题逻辑的等值演算第一篇数理逻辑第一章命题逻辑例:推证

Q(PQ)P对PQ来说,QP称作它的逆换式;PQ称作它的反换式;定义:逆换式、反换式、逆反式证法1:证法2:

假定P为F,则P为T。

QP称作它的逆反式。假定Q(PQ)为T,则Q为T。且(PQ)为T。由Q为F,PQ为T,则必须P为F,故P为T。(a):若Q为F,则PQ为F,Q(PQ)为F。(b):若Q为T,则Q为F,Q(PQ)为F。所以Q(PQ)P成立。常用的蕴含式如表1-5.2。2026/5/18281.6其它联结词及联结词完备集

第一篇数理逻辑第一章命题逻辑1:不可兼析取“

”一、其它联结词2:条件否定“

”二、联结词完备集(最小联结词组)合命题,记为PQ。当且仅当P和Q有不同的真值时,P不可定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成复析取Q为1;否则为零。其真值表见表定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成复合命题,记为PQ。当且仅当P为真,Q为假时,其真值为1。2026/5/18291.6其它联结词及联结词完备集

第一篇数理逻辑第一章命题逻辑定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成3:与非“

”4:或非“”题,记为PQ。当且仅当P与Q同时为假时,PQ为1;否则为0。定义:n元真值函数复合命题,记为“PQ”。当且仅当P与Q同时为真时,pq为零,否则为1。其真值表见表1-6.3(左图定义:设P和Q为两个命题,由P与Q用二元联结词“

”组成复合命真值表见表1-6.4(右图)。称F:{0,1}n{0,1}为n元真值函数。F:自变量为n个命题变元{0,1}组成的长度为n的符号串。值域:{0,1}2026/5/18301.6其它联结词及联结词完备集

第一篇数理逻辑第一章命题逻辑n=1时,1元真值函数为22个n个命题变元共构成2的2n次幂个不同的真值函数。定义:(联结词完备集)设S是一个联结词完备集合,如果任何n(n1)元真值函数都可以仅定理:S={,,}是联结词完备集。推论:下列联结词集都是完备集n=2时,1元真值函数为24个由S中的联结词构成的公式表示。2026/5/18311.6其它联结词及联结词完备集

第一篇数理逻辑第一章命题逻辑6)S6={}7)S7={}例1:仅用,表示(pq)p。例2:用表示p。定理:S={,}或S={,}是最小联结词完备集。2026/5/18321.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑在给定的命题公式中,将联结词“

”换成“

”,将联结词“

”换成注:A也为A*的对偶式。例:写出下列各式的对偶式一、对偶式定义:A的对偶式定理:设A与A*是对偶式,P1,P2,…,Pn是出现在A与A*中的原子A(P1,P2,…,Pn)

A*(P1,P2,…,Pn)定理:设P1,P2,…,Pn是出现在A与B中的原子变元,如果AB,则A*

B*。“

”,若有特殊元“0”或“1”亦相互取代,所得公式A*称为A的对偶式。(PQ)R,(PQ)1,PQ,PQ则:A(P1,P2,…,Pn)

A*(P1,P2,…,Pn)2026/5/18331.7对偶与析取范式和合取范式(范式)

第一篇数理逻辑第一章命题逻辑简单析取式:仅由有限个文字构成的析取式。简单合取式:仅由有限个文字构成的合取式。二、析取范式和合取范式定义:例:P,PQ,PQQ为简单析取式注:单个文字既可为简单析取式又为简单合取式。定理:文字:命题变元或命题变元的否定。P,PQ,PQQ为简单合取式1)一个简单析取式为重言式的充要条件是它同时含有命题变元和命题变元的否定。2026/5/18341.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑析取范式:由有限个简单合取式构成的析取式。合取范式:由有限个简单析取式构成的合取式。

2)一个简单合取式为矛盾式的充要条件是它同时含有命题变元和定义:注1:析取范式与合取范式仅含有,,注2:单个文字,简单析取范式与简单合取范式既为析取范式又是合取范式。定理:2)一个合取范式为重言式的充要条件是它的每个简单析取式都是重言式。命题变元的否定。1)一个析取范式为矛盾式的充要条件是它的每个简单合取式都是矛盾式。

2026/5/18351.7对偶与析取范式和合取范式(范式)

第一篇数理逻辑第一章命题逻辑求给定公式范式的步骤:1)消去联结词“

”,“

”定理(范式存在定理)对任意公式A,都存在等价于它的析取范式和合取范式。PQPQ(PQ)(PQ)(PQ)(求合取范式)2)消去否定号“

”3)利用分配律和结合律例1:求公式(PQ)R的合取范式(PQ)(PQ)(PQ)(求析取范式)2026/5/18361.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑3)全体小项的析取式为永真。三命题变元P,Q和R,其极小项为:一般n个命题变元有2n个极小项。一个极小项对一组赋值使其真值m7=PQR,m6=PQR,m5=PQR,m4=PQR,m3=PQR,极小项有下列性质:1)每个小项当其真值指派与编码相同时,其真值为1,其余的指派为0。2)任意两个不同小项的合取式为永假。定义:布尔析取或极大项n个变元的析取式,称作布尔析取或极大项,其中每个变元为1,此时所对应的二进制数为i,引入记号mi表示。m2=PQR,

m1=PQR,m0=PQR它的否定不能同时存在,但两者必须出现且仅出现一次。2026/5/18371.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑1)每个大项当其真值指派与编码相同时,其真值为0,其余的指派为1。例:两命题变元P和Q,其极大项为:三命题变元P,Q和R,其极大项为:一般说,n个命题变元共有2n个极大项。一个极大项对一组赋值使极大项有下列性质:2)任意两个不同大项的析取式为永真。3)全体大项的合取式为永假。M0=PQ,M1=PQ,M2=PQ,M3=PQM0=PQR,M1=PQR,M2=PQR,M4=PQR,M3=PQR,M6=PQR,M5=PQR,M7=PQR其真值为0,此时所对应的二进制数为i,引入记号Mi表示。2026/5/18381.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑定理:在真值表中,一个公式的真值为0的指派所对应的大项的合定义:主析取范式、主合取范式对于一个给定的命题公式,如果有一个等价公式,它仅由小项组对于一个给定的命题公式,如果有一个等价公式,它仅由大项组定理:在真值表中,一个公式的真值为1的指派所对应的小项的求主范式的方法:方法1:已知公式的真值表求。例:求PQ,PQ,

PQ的主析取范式和主合取范式。成析取范式,则该等价公式称为原式的主析取范式。成合取范式,则该等价公式称为原式的主合取范式。析取,即为此公式的主析取范式。取,即为此公式的主合取范式。2026/5/18391.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑求主析取范式步骤:P

Q的主析取范式为:m3m1m0(4)对合取项补入没有出现的命题变元,即添加(

PP),再用分配律展开。方法2:用求范式的方法来求(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。P

Q的主合取范式为:M2P

Q的主析取范式为:m3m2m1

P

Q的主合取范式为:M0PQ的主析取范式为:m1PQ的主合取范式为:M3

M2

M02026/5/18401.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑求主合取范式步骤:例:求下列公式的主析取范式(4)对合取项补入没有出现的命题变元,即添加(

PP),再用分配律展开.(1)化归为合取范式

(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。例:求(PQ)R的主合取范式.

2026/5/18411.7对偶与析取范式和合取范式(范式)第一篇数理逻辑第一章命题逻辑A:有三个变元,if:Am1m2m3, 则方法3:由主析取范式求主合取范式A:有两个变元,if:Am1m2, 则AM0M3AM0M4M5M6M72026/5/18421.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑一、推理的形式结构推理是由已知命题得到新命题的思维过程。前题:已知命题定义:设A1,A2,…,An,B都是命题公式,如果A1

A2

…

AnB注:由前提推出的结论是否正确与诸前题的排列次序无关。判断一个推理是否正确的方法有四种:(1)真值表演算(2)直接证明(3)间接证明推理=前提+结论结论:新命题为重言式,则称从前提A1,A2,…,An推出B。A1

A2

…

An

B,称{A1,A2,…,An}为前提集合。2026/5/18431.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑1)真值表演算判断A1

A2

…

AnB是否为重言式。if:B亦有真值1,则推理正确。Or看真值为0的行,if:在每2)直接演算法判断下列推理是否正确?例1:若a能被4整除,则a能被2整除。a能被4整除,故a能被2整除。在真值表中找出所有A1,A2,…,An的真值为的行,对这样的行,一个这样的行中,A1,A2,…,An的为真值中至少有一个为0,则推理正确。看书p41例12026/5/18441.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑解:P:a能被4整除,Q:a能被2整除判断A1

A2

…

AnB是否为重言式。前提:PQ,P, 结论:Q推理形式:(PQ)PQ例2:下午马芳或者去看电影,或去游泳。她没去看电影,所以她去游泳了。解:P:马芳去看电影,Q:马芳去游泳前提:PQ,P结论:Q推理形式:(PQ)PQ2026/5/18451.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑例3:若下午温度超过30度,则王小燕必去游泳;若她去游泳,她解:P:下午温度超过30度Q:王小燕必去游泳,R:王小燕去看电影前提:PQ,QR定义:自然推理系统由三部份组成1)字母表 2)合式公式 3)推理规则其中字母表为:a)命题变元符号:P,Q,R,…不去看电影。所以若王小燕去看电影,下午气温必不超过30度。结论:RP2026/5/18461.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑b)联结词符号:,,,,c)括号与逗号:(),推理规则:1o:前提引入规则2o:结论引入规则3o:置换规则4o:假言推理规则:AB,AB5o:化简规则:ABB6o:附加规则:AAB7o:拒取式规则:AB,BA9o:析取三段论规则:AB,BA8o:假言三段论规则:AB,BCAC10o:构造性二难规则:AB,CD,ACBD2026/5/18471.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑在自然推理系统中构造下列推理证明例4: 前提:PQ,QR,PS,

S

结论:R(PQ)证明

P

S

前提引入

S前提引入

P拒取式

PQ前提引入

Q析取三段论

QR前提引入

R假言推理规则

R(PQ)

2026/5/18481.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑例5:前提:PQ,PR,QS

结论:SR证明

PR

前提引入

PQRQ附加规则

QS

前提引入

RQRS附加规则

PQRS假言三段论

PQ前提引入

RS

2026/5/18491.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑二、运算和推理1、A蕴含B证明A

B为重言式,可用前件或后件方法2、A、B两公式的等价(1)比较真值表;(2)A

B为重言式4、推理3、求主析(合)取范式(1)真值表;(2)步骤法;(3)互换法(1)真值表;(2)直接法;(3)间接法2026/5/18501.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑PC规则:if:证明A1,A2,…,An

B

C,可引入附加前提B,去推出C。例:证明A(BC),DA,B

D

C证明

D附加前提引入

DA前提引入

A析取三段论

B前提引入

A(BC)前提引入

BC假言推理

C假言推理

D

C则推理正确。2026/5/18511.8命题逻辑推理理论

第一篇数理逻辑第一章命题逻辑3)间接证明(归谬法)A1,A2,…,An

B,若

B可推出矛盾,如AA则说明推理正确。例1:PQ,

(PQ)P

证明

PQ前提引入

Q假言推理规则

P附加前提

(PQ)前提引入

PQ徳摩根律

Q

QQ(矛盾)

否则错误。2026/5/18521.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑例2:证明CB,ABAC证明

(AC) 附加前提引入

A I7

C I8

AB 前提引入

CB

前提引入

B 析取三段论

B

假言推理

BB

矛盾例3:设有下列情况,结论是否有效?

2026/5/18531.8命题逻辑推理理论

第一篇数理逻辑第一章命题逻辑(1)或者天晴,或者下雨。(2)如果是晴天,我去看电影。(3)如果我去看电影,我就不看书。结论:如果我在看书则天在下雨。

2026/5/18541.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑第一章:小结

一、基本概念和术语

命题,原子命题,复合命题,命题常元,命题变元,公合式公式否定词、析取词、合取词、条件词,双条件,优先顺序 对偶式,简单析取式,简单合取式,析取范式,合取范式,真值表,重言式,矛盾式,可满足式,蕴含式,等价式,逆反式小项,大项,主析取范式,主合取范式2026/5/18551.8命题逻辑推理理论第一篇数理逻辑第一章命题逻辑二、运算和推理1、A蕴含B证明A

B为重言式,可用前件或后件方法2、A、B两公式的等价(1)比较真值表;(2)A

B为重言式3、求主析(合)取范式(1)真值表;(2)步骤法;(3)互换法4、推理

(1)真值表;(2)直接法;(3)间接法2026/5/18562.1谓词的概念与表示第一篇数理逻辑第二章谓词逻辑在命题演算中,把简单命题作为基本研究单位而不在进行分解,例1: 所有人总是要死的。P:所有人总是要死的PQR显然此不是命题逻辑的重言式。这使得命题逻辑有很大的局限性。有些很简单的推理形式,如典型逻辑三段论,用命题演算的推理理论无法论证。苏格拉底是人。所以苏格拉底是要死的。Q:苏格拉底是人R:苏格拉底是要死的2026/5/18572.1谓词的概念与表示第一篇数理逻辑第二章谓词逻辑造成上述的原因在于我们没有对简单命题自身内部特征作进一例2: 熊猫是动物。P:熊猫是动物P和Q不能揭示这两个命题的共性对简单命题的成份、结构和简单命题间的共性等作进一步的步的分析,无法揭示前提和结论在形式结构方面的联系,所以不能认识到这种推理的形式和规律。 狗是动物。Q:狗是动物分析,这正是一阶逻辑所要研究的问题。一阶逻辑又称一谓词逻辑或谓词逻辑。2026/5/18582.1谓词的概念与表示第一篇数理逻辑第二章谓词逻辑一、个体词和个体域定义:个体常元:表示具体、特指的个体词。常用小写字a,b,c等表示。个体变元:表示抽象的、泛指的或一定范围个体词。常用小写字个体域:个体变元的取值范围。常用D表示。注1:个体域可以是有限的或无限的。个体:可以独立存在的事物。母x,y,z等表示。注2:全总个体域:最大的个体域包含整个宇宙全体事物。注3:如果无特别声明个体域均为全总个体域。2026/5/18592.1谓词的概念与表示

第一篇数理逻辑第二章谓词逻辑一般句子是有主语和谓语两部份组成。个体通常是主语,可以是抽象的或具体的。如:小张,小王,熊猫,计算机等。谓词:用来刻划一个个体的性质或多个个体之间的关系的词。元数:谓词中包含个体的数目。谓词常元:表示有具体意义的性质或关系的谓词。谓词变元:表示有抽象的或泛指的性质或关系的谓词。从数学角度来讲:谓词是一个以D为定义域,以{0,1}为值域的函数。0元谓词:将不带个体变元的谓词。2026/5/18602.1谓词的概念与表示

第一篇数理逻辑第二章谓词逻辑一元谓词:表示一个个体的性质。二元谓词:表示两个个体之间关系。n元谓词:表示n个个体之间关系。用谓词表达式写出下列命题元数:谓词中包含个体的数目。例1:只有2为素数,4才是素数。解:一元谓词F(x):x为素数

a=2,b=4F(a)F(b)例2:如果5大于4,则4大于6解:二元谓词G(x,y):x>y2026/5/18612.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑定义:简单命题函数:由一个谓词,一些个体变元组成的表达式。复合命题函数:由一个或n个简单命题函数以及逻辑联结词组成的表达式。仅在命题中分析出个体或谓词后,还不足以表达逻辑三段论和日定义:量词:表示数量的词。分为全称量词和存在量词。

全称量词:表示“所有的”,“任意的”,“每一个”,“凡”等的词。记为:

xA(x)or(x)A(x):表示个体域中的所有个体都有性质A。存在量词:表示“存在着”,“有某些”,“至少存在一个”等的词。记常生活中的各种问题。因为还缺少表示个体常元与变元之间的数量关系。“

”,x表示个体域中的所有个体,x称为全称变元。为:“

”,x表示存在个体域中的个体,x为存在性变元。2026/5/18622.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑

xA(x)or(x)A(x):表示存在个体域中的某个体都具有性质A。量词也称为对个体所附加的约束词。例1:设F(x):表示x会飞,D为鸟集合例2:设G(x):x为白的,D:为菊花集合注:带有量词的命题函数必须确定其个体域;否则无法准确表达命题含义。

xA(x)or(x)A(x):表示个体域中的所有个体都有性质A。定义:特定谓词

xF(x):

xF(x):

xG(x):

xG(x):

If:所有命题函数的个体域为全总个体域,对每个个体的性质要特别指明。为了讨论个体域中某部分个体的性质,引入刻划这部分个体的谓词。2026/5/18632.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑一般对全称量词,此特性谓词常作蕴涵前件。如

xA(x)可写成

x(M(x)

A(x)),M(x)为A(x)的特性谓词。一般对存在量词,此特性谓词常作合取项。如

xH(x)可写成

x(M(x)

H(x)),M(x)限制H(x)的变化。三、一阶逻辑命题中的符号化问题1、一元谓词符号化例1:凡人都有呼吸。解:F(x):x为人,H(x):x呼吸

x(F(x)

H(x))例2:有人用左手写字。2026/5/18642.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑解:F(x):x为人,G(x):x用左手写字

x(F(x)

G(x))例3:小李是大学生和运动员。解:L(x):x是大学生,P(x):x是运动员

a:小李L(a)

P(a)注:在命题符号化时,如果没有特别指明个体域,则采用全总体域。将下列命题符号化,并指明其真值。例1:所有人都长黑头发。解:M(x):x为人,F(x):x长黑头发例2:每个学生都要参加考试。

x(M(x)

F(x))2026/5/18652.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑解:M(x):x为学生,F(x):x要参加考试

x(M(x)

F(x))例3:任何整数或是正的或是负的。解:P(x):x为整数,Q(x):x是正数R(x):x是负数例4:在美国留学的学生未必是亚州人。解:M(x):x在美国留学的学生F(x):x是亚州人

x(M(x)

F(x))例5:没有人登上木星。解:M(x):x为人,F(x):x登上木星

x(M(x)

F(x))2026/5/18662.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑注:量词与否定词的关系,约定:出现在量词之前的否定词是否定被量化的整个命题。练习:勇敢者未必是成功者。2、n(n2)元命题符号化将下列命题符号化例1:兔子比乌龟跑的快。解:F(x):x是兔子,Q(y):y是乌龟H(x,y):x比y跑的快例2:有的兔子比所有的乌龟跑的快。2026/5/18672.2命题函数与量词

第一篇数理逻辑第二章谓词逻辑例3:不是所有的兔子比乌龟跑的快。例4:不存在跑的同样快的兔子和乌龟。

L(x,y):x与y跑的一样快2026/5/18682.3~2.4一阶谓词公式第一篇数理逻辑第二章谓词逻辑定义:一阶语言的字母表如下:1)个体常元:a,b,c,…2)个体变元:x,y,z,…3)函数符号:f,g,h,…4)谓词符号:F,G,H,…5)量词符号:,7)括号与逗号:(),定义:中项的定义1)个体常元和个体变元是项。2026/5/18692.3~2.4一阶谓词公式

第一篇数理逻辑第二章谓词逻辑2)若(x1,x2,…,xn)是任意的n元函数,t1,t2,…,tn是任意的n个项,则(t1,t2,…,tn)是项。3)所有的项都是有限次使用1)、2)得到的。定义:原子公式设R(x1,x2,…,xn)是的n元谓词,t1,t2,…,tn是的任意n个项,则称R(t1,t2,…,tn)是的原子公式定义:谓词合式公式1)原子公式是谓词合式公式。2)若A为谓词合式公式,则

A为谓词合式公式3)若A和B为谓词合式公式,则AB,AB,AB,AB也是谓词合式公式。4)若A为谓词合式公式,则

xA(x),

xA(x)也是谓词合式公式。2026/5/18702.3~2.4一阶谓词公式

第一篇数理逻辑第二章谓词逻辑5)仅由有限次使用1)—4)构成的符号串才是谓词合式公式。合式公式也称谓词公式,简称公式。定义:辖域,指导变元约束出现,自由出现在

xA(x),

x

A(x)中,x指导变元,A为相应量词的辖域。x,例:指出下列公式中的辖域,指导变元,约束出现,自由出现。1)x(F(x,y)G(x,z))1)解:x:约束出现,指导变元

x的辖域中,x的所有出现为约束出现;A中不是约束出现的那些项为自由出现

x的辖域为:F(x,y)G(x,z)

y:自由出现2026/5/18712.3~2.4一阶谓词公式第一篇数理逻辑第二章谓词逻辑2)x(F(x)G(y))y(H(x)L(x,y,z))定义:约束变元换名对公式中的约束变元更改名称符号,这种遵守一定规则的更改称为约束变元换名。规则:1)更改的变元名称符号是量词中的指导(约束)变元,以及该辖域中所2)换名时一定要改为辖域中没有出现的变元名称。例:x(P(x)R(x,y))L(x,y)定义:闭式出现的变元,在公式中的其余部分不变。可写为z(P(z)R(z,y))L(x,y)2026/5/18722.3~2.4一阶谓词公式第一篇数理逻辑第二章谓词逻辑设A为任意公式,若A中不含自由出现的个体变元,则称A为封闭公式。简称闭式。2026/5/18732.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑一、等值公式定义:设A,B为一阶逻辑中的任意两个公式,若AB为永真式,一阶逻辑等值演算的主要内容:给出一些重要的等值式,有这些下面给出一些重要的等值式:第一组:在命题逻辑中的重言式的代换实例均为一阶逻辑永真式。例1:(PQ)(PQ)例2:HHF (x)H(x)(x)H(x)F第二组:则称A,与B等值。记为AB。等值式可以推出更多的等值式。1、消去量词等值式2026/5/18742.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑设个体域为有限值,D={a1,a2,…,an},则有(1)xA(x)

A(a1)

A(a2)

…

A(an)(2)xA(x)

A(a1)

A(a2)

…

A(an)2、量词否定等值式约定:出现在量词之前的否定,不是否定该量词,而是否定被量化例1:A(x)表示x(人)今天来校上课

xA(x)表示任何人今天都来上课。了的整个命题。2026/5/18752.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑

(xA(x))表示任何人今天都不来上课。

(xA(x))表示不是任何人今天都来上课。3、量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变元x的公式,B中不含x的出现,则:(1)x(A(x)B)xA(x)BxA(x)Bx(A(x)B)x(BA(x))BxA(x)(2)x(A(x)B)xA(x)Bx(A(x)B)xA(x)B2026/5/18762.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑xA(x)Bx(A(x)B)x(BA(x))BxA(x)例:证明

xA(x)Bx(A(x)B)xA(x)B(x)A(x)Bx(A(x)B)说明:A(x):x(人)为张村人,B:姓张左:对所有人,为张村人或姓张

x(A(x)B)xA(x)B

x(A(x)B)xA(x)B右:所有人为张村人,或姓张2026/5/18772.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑左:对所有人,既为张村人又姓张右:所有人为张村人且姓张

xA(x)Bx(A(x)B)左:若每个人是张村人,则姓张

右:有些人,若是张村人则姓张

x(BA(x))BxA(x)左:对所有人,若姓张则是张村人右:若姓张,则所有人都是张村人4、量词的分配等值式2026/5/18782.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑(1)x(A(x)B(x))xA(x)xB(x)(2)x(A(x)B(x))xA(x)xB(x)说明:A(x):x(人)很努力 B(x):x(人)很聪明

x(A(x)B(x))xA(x)xB(x)左:所有人,既努力又聪明右:所有人很努力同时所有人很聪明

x(A(x)B(x))xA(x)xB(x)左:有些人,很努力或者很聪明右:有些人很努力或者有些人很聪明2026/5/18792.5一阶谓词演算的等价式与蕴含式第一篇数理逻辑第二章谓词逻辑5、量词与命题联结词之间的一些蕴含式(1)xA(x)xB(x)x(A(x)B(x))(2)x(A(x)B(x))xA(x)xB(x)(3)x(A(x)B(x))xA(x)x

B(x)(4)x(A(x)B(x))xA(x)x

B(x)仅对二元谓词,且不考虑自由变元,有下列八种形式:xy(A(x,y)), yx(A(x,y))xy(A(x,y)), yx(A(x,y))xy(A(x,y)), yx(A(x,y))xy(A(x,y)), yx(A(x,y))2026/5/18802.6一阶谓词前束范式第一篇数理逻辑第二章谓词逻辑在命题逻辑中,析取范式与合取范式是两种不同的等值形式,在一阶定义:前束范式设A为一阶逻辑公式,若A具有如下形式:例2:(x)(y)(F(x)H(y)G(x,y))例3:(x)(F(x)(y)(G(y)H(x,y))定理:(前束范式存在定理)一阶逻辑公式中的任何公式都存在与之等值的前束范式。化为前束范式的步骤:谓词也有范式。

Q1x1Q2x2…QkxkB则称A为前束范式,其中QI为或,B为不含量词的公式。2026/5/18812.6一阶谓词前束范式第一篇数理逻辑第二章谓词逻辑1)将“”移至命题变元or谓词之前。2)约束元换名3)将量词移到全式的最前面

x(A(x)B)xA(x)B注:一般前束范式不唯一。求下列公式的前束范式例1:xF(x)xG(x)解:

xF(x)xG(x)xF(x)x(G(x))xF(x)y(G(y))x(A(x)B)xA(x)Bxy(F(x)(G(y)))2026/5/18822.6一阶谓词前束范式第一篇数理逻辑第二章谓词逻辑例3:

xP(x)xQ(x)

解:

xP(x)xQ(x)xP(x)xQ(x)x(P(x))xQ(x)定义:前束合取范式和前束析取范式设A为前束范式,且具有Q1x1Q2x2…QkxkB的形式,如果B为合取范式,则A为前束合取范式。如果B为析取范式,则A为前束析取范式。如何求前束合取范式和前束析取范式?2026/5/18832.6一阶谓词前束范式第一篇数理逻辑第二章谓词逻辑定理:每一个前束范式都可以转化为与其等价的前束合取范式或前束析取范式。步骤 1:取消多余的量词;2:换名;3:消去条件联结词;4:例:将A=x[(yP(x)zQ(z,y))yR(x,y)]化为与其等价的前束合

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论