离散数学thethirdcourse省公共课一等奖全国赛课获奖课件.pptx

(PQ(R(PQ(RR)(R)(PR(QPR(QQ)(QR(PQ)(QR(PP)P)(PQR)(PQ (PQR)(PQR)(R)(PRQ)(PRQ)(PRPRQ)Q)(PQR)(PQ (PQR)(PQR)(R)(PQR)(PQR)(PPQR)QR)2.2.利用等价式求主析取范式利用等价式求主析取范式例：（例：（PQPQ）(PR)(QR)PR)(QR)化归方法步骤：化归方法步骤：1.化为析取范式。2.删去析取范式中永假析取项。3.将析取式中重复合取项和相同变元合并。1-7对偶与范式对偶与范式第1页4.对合取项补入没有出现变元，即添加 PP等。5.用分配律展开。1-7对偶与范式对偶与范式第2页 上次课我们学习了析取范式，形式为：（）()(),合取范式，形式为：（）（）（）（），引入了小项（它是变元或变元否定式组成合取式，但二者必须出现且仅出现一个。由小项析取我们能够得到主析取范式；这么对于任一公式，我们都可求出其主析取范式，当其变元个数、次序固定时，它是唯一。下面我们主要介绍主合取范式。对应于小项，我们引进了大项。大大项项定定义为义为：n n个命个命题变题变元析取式，其中每个元析取式，其中每个变变元与它否定不元与它否定不能同能同时时存在，但二者必存在，但二者必须须出出现现且且仅仅出出现现一次，称一次，称为为大大项项，也成，也成为为布布尔尔析取。析取。比如比如:2个变元P、Q，可生成22=4个大项:PQ PQ PQ PQ 3个变元P,Q,R，能够生成8个大项:PQR PQR 1-7对偶与范式对偶与范式第3页 PPQQR nR n个变元对应着个变元对应着2 2n n个大项。个大项。小项用小项用m m编号，大项用编号，大项用M M表示，两个变元用两位二进制表示，两个变元用两位二进制编号。编号。小项小项0 0：变元之否定；：变元之否定；1 1：命题变元。如：命题变元。如m m0101PQPQ。而。而大项恰好相反。大项恰好相反。大项大项0 0：变元本身，：变元本身，1 1：变元否定。如：变元否定。如：M M0000PQPQ。如上。如上面对应面对应2 2个变元个变元4 4个大项：个大项：PQ,PPQ,PQ,Q,PQ,PQ,PPQ Q M M0000=M=M0 0,M,M0101=M=M1 1,M,M1010=M=M2 2,M,M1111=M=M3 3 等等可与上面并在一起写。等等可与上面并在一起写。对应于二进制，大项也能够用十进制编号，如上。对应于二进制，大项也能够用十进制编号，如上。大项有以下性质：大项有以下性质：1-7对偶与范式对偶与范式第4页1.每每个个大大项项指指派派与与编编号号相相同同时时，其其值值为为F，而而其其余余2n1种种指指派情况下其值均为派情况下其值均为T。2.任任意意两两个个不不一一样样大大项项析析取取式式都都为为T。如如MiMj（i!=j）总总有一个变元与其否定存在。有一个变元与其否定存在。3.全体大项合取式必为永假全体大项合取式必为永假F。（02n1）Mi=M0M1M2M2n1=F由大项，能够得到主合取范式。由大项，能够得到主合取范式。对对于于一一个个公公式式若若存存在在一一个个等等价价式式，它它由由大大项项合合取取所所组组成成，则该等价式称为原式主合取范式。则该等价式称为原式主合取范式。求主合取范式方法求主合取范式方法：1 1 真值表法真值表法 定理定理:在真值表中，一个公式真值为在真值表中，一个公式真值为F F指派所对应大项指派所对应大项1-7对偶与范式对偶与范式第5页合取，即为此公式主合取范式。合取，即为此公式主合取范式。我我们们求求主主析析取取范范式式时时是是将将全全部部值值为为T T指指派派对对应应小小项项析析取取；这这里里求求主主合合取取范范式式是是将将全全部部取取值值为为F F全全部部可可能能值值列列出出来来、取取合合取取。（析析取取与与合取对偶）合取对偶）要要注注意意大大项项写写法法不不一一样样于于小小项项，另另外外列列真真值值表表必必须须注注意意次次序序，先先列列T T，后列，后列F F1-7对偶与范式对偶与范式第6页1-7对偶与范式对偶与范式第7页对于上述定理就不证实了，方法与前面类似。对于上述定理就不证实了，方法与前面类似。2 2 用等价公式，其步骤为：用等价公式，其步骤为：1)1)划归为合取范式。划归为合取范式。2)2)删去合取式中永真合取式。删去合取式中永真合取式。3)3)合并相同析取项和相同变元。合并相同析取项和相同变元。4)4)对对析析取取项项补补入入没没有有出出现现变变元元，即即补补入入形形如如：(P(PP)P)式。式。5)5)应用分配律展开。应用分配律展开。上述五个步骤与主析取范式类似。上述五个步骤与主析取范式类似。例：化原式为主析取范式（上例）例：化原式为主析取范式（上例）1-7对偶与范式对偶与范式第8页这么当变元次序一定时，每个公式都有唯一与之等价主合取范式这么当变元次序一定时，每个公式都有唯一与之等价主合取范式一个公式，现有与之相等价唯一主析取范式，又有唯一主合取范式，它们一个公式，现有与之相等价唯一主析取范式，又有唯一主合取范式，它们之间有何关系呢？首先它们分别由小项、大项决定，看看小项、大项之间有何之间有何关系呢？首先它们分别由小项、大项决定，看看小项、大项之间有何关系。关系。1-7对偶与范式对偶与范式第9页1）大项与小项有什么关系？大项与小项有什么关系？1-7对偶与范式对偶与范式第10页总结：学习数理逻辑主要适合用于推理，有了前面这些基础知识，就能够进行总结：学习数理逻辑主要适合用于推理，有了前面这些基础知识，就能够进行推理推理1-8推理理论推理理论推理就是用一些已知东西得出另外一些结论。而在推理过推理就是用一些已知东西得出另外一些结论。而在推理过程中，常把一些定律、定理和条件，作为假设前提，使用一些公认规则，得到程中，常把一些定律、定理和条件，作为假设前提，使用一些公认规则，得到另外命题，形成结论，这种过程就是论证。另外命题，形成结论，这种过程就是论证。定义：定义：1-7对偶与范式对偶与范式第11页判别有效结论过程就是论证过程，方法各种多样，但基本上有三种方法。判别有效结论过程就是论证过程，方法各种多样，但基本上有三种方法。1-8命题演算推理理论命题演算推理理论第12页比如比如P41.例例1.读题；首先找出命题变元，读题；首先找出命题变元，P:材料不可靠，材料不可靠，Q:计算有错误。计算有错误。论证论证:TTTFTFTFTTTTFFFT1-8命题演算推理理论命题演算推理理论第13页(2)直接证法直接证法从已知前提出发，使用公认推理规则，利用等价式或蕴含式，得到结论。从已知前提出发，使用公认推理规则，利用等价式或蕴含式，得到结论。规则有规则有P规则规则前提在论证过程中任何时候都可用。前提在论证过程中任何时候都可用。T规则规则在论证中，假如一个或多个公式蕴含公式在论证中，假如一个或多个公式蕴含公式S，则，则S能够引入推理中。能够引入推理中。等价式与蕴含式在书等价式与蕴含式在书P43表表1-8.3,1-8.4可见。可见。1-8命题演算推理理论命题演算推理理论第14页证实：证实：注意：必须将证实过程编号一一写出理由。注意：必须将证实过程编号一一写出理由。这里须将每一步依次编号，得出理由；书上给了两种证实法，论证方法不唯一，这里须将每一步依次编号，得出理由；书上给了两种证实法，论证方法不唯一，但方向是明确，最终能抵达但方向是明确，最终能抵达C，且步骤越少越好。，且步骤越少越好。（3）间接证法）间接证法1-8命题演算推理理论命题演算推理理论第15页(3)间接证法：间接证法：1-8命题演算推理理论命题演算推理理论第16页1-8命题演算推理理论命题演算推理理论第17页注意：永假不是永真否定，但若要证注意：永假不是永真否定，但若要证A为永真，可证实为永真，可证实A为永假。为永假。1-8命题演算推理理论命题演算推理理论第18页前面介绍了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认推理规则，前面介绍了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认推理规则，利用等价或蕴含式，推出结论成立，就是论证。证实利用等价或蕴含式，推出结论成立，就是论证。证实有三种方法。有三种方法。1-8命题演算推理理论命题演算推理理论第19页1-8命题演算推理理论命题演算推理理论第20页1-8命题演算推理理论命题演算推理理论第21页例2P46例题6M：天晴；Q：下雨；S：我看电影；R：我看书。1-8命题演算推理理论命题演算推理理论第22页要证实：MQ,MS,SRRQ证：(1)RP(附加前提)(2)SRP(3)RST(2)E(4)ST(1)(3)I11(5)MSP(6)SMT(5)E(7)MT(4)(6)I11(8)(MQ)P1-8命题演算推理理论命题演算推理理论第23页(9)MQT(8)E22(10)(MQ)(QM)T(9)E(11)QMT(10)I(12)MQT(11)E(13)QT(7)(12)I11(14)RQCP或(8)MQP(9)MQT(8)E1-8命题演算推理理论命题演算推理理论第24页(10)(MQ)(QM)T(9)E(11)MQT(10)I(12)QT(7)(11)I全部推理方法不唯一，使用等价或蕴含式也不一定相同，不过越简练越好。关于命题逻辑就介绍这么多。主要有命题九个联接词；五个主要联接词，最小连接词组为,或,或或等，和一些公式（重言式，蕴含式，对偶式，合取、析取范式）以及推理。下面介绍谓词逻辑（数理逻辑另一基本内容）。1-8命题演算推理理论命题演算推理理论第25页在在命命题题逻逻辑辑中中，P,QR是是无无法法推推出出。命命题题逻逻辑辑含含有有不不足足，刻刻画画命命题不够深刻，所以有必要研究谓词逻辑。题不够深刻，所以有必要研究谓词逻辑。在在命命题题逻逻辑辑中中，基基本本单单位位是是原原子子命命题题，它它是是不不可可再再分分。不不过过原原子子命命题间还是有一些共同特征，需要深入解析。比如：题间还是有一些共同特征，需要深入解析。比如：例例1：P：小李是学生。：小李是学生。Q：小张是学生。小张是学生。在在命命题题逻逻辑辑中中，这这是是两两个个不不一一样样命命题题，无无法法再再分分了了，但但共共性性“是是学学生生”（命命题题本本质质属属性性）无无法法深深入入刻刻划划出出来来，还还有有些些很很简简单单三段论也是无法用命题逻辑理论推出。三段论也是无法用命题逻辑理论推出。例例2：P：人是要呼吸。人是要呼吸。Q：老张是人。：老张是人。R：老张是要呼吸。：老张是要呼吸。第二章谓词逻辑第二章谓词逻辑第26页命题逻辑含有不足，刻画命题不够深刻。有必要研究谓词逻辑。命题逻辑含有不足，刻画命题不够深刻。有必要研究谓词逻辑。命题是反应判断陈说句，它最少有主语和谓语两部分组成。命题是反应判断陈说句，它最少有主语和谓语两部分组成。如：小王是学生。如：小王是学生。5大于大于7。点点a位于点位于点b与点与点c之间。之间。1定义定义1）主主语语：称称为为客客体体（个个体体），用用a,b,c表表示示。客客观观存存在在东西，能够是详细，也能够是抽象。东西，能够是详细，也能够是抽象。2）用用来来描描述述客客体体性性质质，或或客客体体之之间间关关系系称称为为谓谓词词。用用P,Q,R（大写字母）表示。（大写字母）表示。2-1谓词概念与表示谓词概念与表示第27页1a:5b:7B:大于大于B(a,b):5大于大于7a:点点Ab:点点Bc:点点CL:位于位于与与之间之间L(a,b,c)表表示示，A位位于于B与与C之间之间2.这么命题就可用谓词与客体表示：这么命题就可用谓词与客体表示：a:小王小王A:是学生是学生A(a):小王是学生小王是学生a:老张老张H:是老师是老师H(a):老张是老师老张是老师2-1谓词概念与表示谓词概念与表示第28页所所以以，单单独独一一个个谓谓词词不不是是命命题题，只只有有填填入入客客体体后后才才是是命命题题，叫叫谓词填式。谓词填式。定义：H是n元谓词，a1,a2,a3an是n个客体，H(a1,a2an)所代表式子是一个命题，称为谓词填式。（当ai是客体时，A(a1an)才是命题。）3除了谓词，我们今后还要用到函数这一概念除了谓词，我们今后还要用到函数这一概念例：老张是小张父亲。例：老张是小张父亲。小张父亲小张父亲=老张老张f:.父亲；父亲；a:小张；小张；b:老张；老张；则则b=f(a)2-1谓词概念与表示谓词概念与表示第29页今天南京气温是今天南京气温是20度度a:今天今天；b:南京；南京；g:某天某城市温度某天某城市温度则则g(a,b)=20度度所以，函数是将客体映射到客体。而谓词是将客体映射到真或假所以，函数是将客体映射到客体。而谓词是将客体映射到真或假命题命题。如：小王是学生如：小王是学生是谓词填入客体得到命题。是谓词填入客体得到命题。7大于大于5是两个客体填入后得到命题，是两个客体填入后得到命题，T用用f,g,h.表示函数，如表示函数，如h表示：表示：和和.之和，之和，则则a:3,b:4h(a,b)=72-1谓词概念与表示谓词概念与表示第30页4.定义定义1）个体域（客体叙述范围）个体域（客体叙述范围）2）客客体体变变元元（个个体体变变元元）：以以个个体体域域中中客客体体为为值值变变元元，用用x,y,z表示表示3）论论域域：全全部部客客体体集集合合。全全总总个个体体域域：各各种种个个体体域域综综合合在在一起，作为叙述范围域。一起，作为叙述范围域。2-2命题函数与量词命题函数与量词例例1：H:抵达山顶抵达山顶l:李四李四t:老虎老虎c:汽车汽车H(l):李四抵达山顶。李四抵达山顶。2-1谓词概念与表示谓词概念与表示第31页H(t):老虎抵达山顶。老虎抵达山顶。H(c):汽车抵达山顶。汽车抵达山顶。H(x)表示表示H共同形式。但单写共同形式。但单写H不知是几元谓词，所以需加客体不知是几元谓词，所以需加客体变元。变元。例例2：L(x,y):xyL(2,3):2zA(4,3,5):4+35所所 以以，H(x),L(x,y),M(x,y,z)本本 身身 不不 是是 命命 题题，但但 当当 变变 元元 取取 特特 定定 值后成为命题。值后成为命题。2-2命题函数与量词命题函数与量词第32页定定 义义：（1）简简 单单 命命 题题 函函 数数：一一 个个 谓谓 词词+一一 些些 客客 体体 变变 元元 组组 成成 表表 示示 式式 称为简单命题函数。但称为简单命题函数。但A(x,y,z)不是命题不是命题（2）n元谓词就是有元谓词就是有n个客体变元命题函数。个客体变元命题函数。（3）复合命题函数：由简单命题函数和逻辑联结词组成）复合命题函数：由简单命题函数和逻辑联结词组成命题函数命题函数比如1：S(x)表示表示x学习很好学习很好W(x):x工作很好工作很好S(x)：x学习不是很好学习不是很好S(x)W(x):x学习很好，工作也好学习很好，工作也好S(x)W(x):若若x学习好，则学习好，则x工作也好工作也好2-2命题函数与量词命题函数与量词第33页又如例又如例2：H(x,y):x比比y长得高长得高l:李四李四c:张三张三H(l,c):李四比张三长得高李四比张三长得高例例3：R(x):x是大学生是大学生x个体域：某大学中某班个体域：某大学中某班P(x)永真永真x个体域：某中学中某班个体域：某中学中某班P(x)永假永假x个体域：某剧场中观众个体域：某剧场中观众P(x)有真有假有真有假2-2命题函数与量词命题函数与量词第34页命命题题函函数数不不是是命命题题，只只有有客客体体变变元元取取特特定定客客体体时时，才才是是命命题题。而且真假与其取值也相关系。而且真假与其取值也相关系。例例4：又（又（P(x,y)P(y,z)）P(x,z)若若P(x,y):xxF(x):x是自然数G(x):x是素数H(x,y):xy每一步必须非常清楚，内在关系把握住，就不会错。2-3谓词公式与翻译谓词公式与翻译第54页(4)没有不犯错误人。(F(x),M(x)(书上)译为：不存在x，x是人且x是不犯错误。F(x):x犯错误。M(x):x是人所以(5)爱新觉罗弘历父亲到北京去了。“到去了”是谓词。F(x,y):x到y去了。a:爱新觉罗弘历,f(x):x父亲，b:北京所以F(f(a),b)(6)戴婷婷和他父亲及祖父三人一起去看演出。F(x,y,z):x,y和z一起去看演出2-3谓词公式与翻译谓词公式与翻译第55页f(x):x父亲a:戴婷婷(7)这只大红书柜摆满了那些古书。F(x,y):x摆满了ya:这只大红书柜b:那些古书可译为：F(a,b)，但描述太粗略。另译为：R(x):x是书柜B(x):x是大C(x):x是红D(y):y是古老E(y):y是书a:这只b:那些详细表示B(a)C(a)R(a)D(b)E(b)F(a,b)思索：书上解法1中能否表示为F(R(a),Q(b)?因而若需将命题表述越精细，所需谓词越多。2-3谓词公式与翻译谓词公式与翻译第56页(8)尽管有些人聪明，但未必一切人都聪明。2-3谓词公式与翻译谓词公式与翻译第57页24变元约束变元约束首先引进一些概念：给定一个谓词公式首先引进一些概念：给定一个谓词公式，其中含有公式，其中含有公式量词后面量词后面x叫做指导变元或作用变元，而叫做指导变元或作用变元，而P(x)这么对于日常生活中碰到一些命题普通都能翻译成公式，而且谓词这么对于日常生活中碰到一些命题普通都能翻译成公式，而且谓词公式比命题公式表示更为准确明了。公式比命题公式表示更为准确明了。2-4变元约束变元约束第58页