离散数学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页第1页4.对合取项补入没有出现变元，即添加 PP等。5.用分派律展开。1-7对偶与范式对偶与范式第2页第2页 上次课我们学习了析取范式，形式为：（）()(),合取范式，形式为：（）（）（）（），引入了小项（它是变元或变元否认式构成合取式，但两者必须出现且仅出现一个。由小项析取我们能够得到主析取范式；这样对于任一公式，我们都可求出其主析取范式，当其变元个数、顺序固定期，它是唯一。下面我们主要简介主合取范式。相应于小项，我们引进了大项。大大项项定定义为义为：n n个命个命题变题变元析取式，其中每个元析取式，其中每个变变元与它否元与它否认认不不能同能同时时存在，但两者必存在，但两者必须须出出现现且且仅仅出出现现一次，称一次，称为为大大项项，也成，也成为为布布尔尔析取。析取。比如比如:2个变元P、Q，可生成22=4个大项:PQ PQ PQ PQ 3个变元P,Q,R，能够生成8个大项:PQR PQR 1-7对偶与范式对偶与范式第3页第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页第4页1.每个大项指派与编号相同时，其值为F，而其余2n1种指派情况下其值均为T。2.任意两个不同大项析取式都为T。如MiMj（i!=j）总有一个变元与其否认存在。3.全体大项合取式必为永假F。（02n1）Mi=M0M1M2M2n1=F由大项，能够得到主合取范式。对于一个公式若存在一个等价式，它由大项合取所组成，则该等价式称为原式主合取范式。求主合取范式办法求主合取范式办法：1 1 真值表法真值表法 定理定理:在真值表中，一个公式真值为在真值表中，一个公式真值为F F指派所相应大项指派所相应大项1-7对偶与范式对偶与范式第5页第5页合取，即为此公式主合取范式。合取，即为此公式主合取范式。我我们们求求主主析析取取范范式式时时是是将将所所有有值值为为T T指指派派相相应应小小项项析析取取；这这里里求求主主合合取取范范式式是是将将所所有有取取值值为为F F所所有有也也许许值值列列出出来来、取取合合取取。（析析取取与与合取对偶）合取对偶）要注意大项写法不同于小项，另外列真值表必须注意次序，先列T，后列F1-7对偶与范式对偶与范式第6页第6页1-7对偶与范式对偶与范式第7页第7页对于上述定理就不证实了，办法与前面类似。对于上述定理就不证实了，办法与前面类似。2 2 用等价公式，其环节为：用等价公式，其环节为：1)1)划归为合取范式。划归为合取范式。2)2)删去合取式中永真合取式。删去合取式中永真合取式。3)3)合并相同析取项和相同变元。合并相同析取项和相同变元。4)4)对对析析取取项项补补入入没没有有出出现现变变元元，即即补补入入形形如如：(P(PP)P)式。式。5)5)应用分派律展开。应用分派律展开。上述五个环节与主析取范式类似。上述五个环节与主析取范式类似。例：化原式为主析取范式（上例）例：化原式为主析取范式（上例）1-7对偶与范式对偶与范式第8页第8页这样当变元顺序一定期，每个公式都有唯一与之等价主合取范式这样当变元顺序一定期，每个公式都有唯一与之等价主合取范式一个公式，既有与之相等价唯一主析取范式，又有唯一主合取范式，它们一个公式，既有与之相等价唯一主析取范式，又有唯一主合取范式，它们之间有何关系呢？首先它们分别由小项、大项决定，看看小项、大项之间有何之间有何关系呢？首先它们分别由小项、大项决定，看看小项、大项之间有何关系。关系。1-7对偶与范式对偶与范式第9页第9页1）大项与小项有什么关系？大项与小项有什么关系？1-7对偶与范式对偶与范式第10页第10页总结：学习数理逻辑主要适合用于推理，有了前面这些基础知识，就能够进行总结：学习数理逻辑主要适合用于推理，有了前面这些基础知识，就能够进行推理推理1-8推理理论推理理论推理就是用一些已知东西得出另外一些结论。而在推理过推理就是用一些已知东西得出另外一些结论。而在推理过程中，常把一些定律、定理和条件，作为假设前提，使用一些公认规则，得到程中，常把一些定律、定理和条件，作为假设前提，使用一些公认规则，得到另外命题，形成结论，这种过程就是论证。另外命题，形成结论，这种过程就是论证。定义：定义：1-7对偶与范式对偶与范式第11页第11页判别有效结论过程就是论证过程，办法各种多样，但基本上有三种办法。判别有效结论过程就是论证过程，办法各种多样，但基本上有三种办法。1-8命题演算推理理论命题演算推理理论第12页第12页比如比如P41.例例1.读题；首先找出命题变元，读题；首先找出命题变元，P:材料不可靠，材料不可靠，Q:计算有错误。计算有错误。论证论证:TTTFTFTFTTTTFFFT1-8命题演算推理理论命题演算推理理论第13页第13页(2)直接证法直接证法从已知前提出发，使用公认推理规则，利用等价式或蕴含式，得到结论。从已知前提出发，使用公认推理规则，利用等价式或蕴含式，得到结论。规则有规则有P规则规则前提在论证过程中任何时候都可用。前提在论证过程中任何时候都可用。T规则规则在论证中，假如一个或多个公式蕴含公式在论证中，假如一个或多个公式蕴含公式S，则，则S能够引入推理中。能够引入推理中。等价式与蕴含式在书等价式与蕴含式在书P43表表1-8.3,1-8.4可见。可见。1-8命题演算推理理论命题演算推理理论第14页第14页证实：证实：注意：必须将证实过程编号一一写出理由。注意：必须将证实过程编号一一写出理由。这里须将每一步依次编号，得出理由；书上给了两种证实法，论证办法不唯一，这里须将每一步依次编号，得出理由；书上给了两种证实法，论证办法不唯一，但方向是明确，最后能到达但方向是明确，最后能到达C，且环节越少越好。，且环节越少越好。（3）间接证法）间接证法1-8命题演算推理理论命题演算推理理论第15页第15页(3)间接证法：间接证法：1-8命题演算推理理论命题演算推理理论第16页第16页1-8命题演算推理理论命题演算推理理论第17页第17页注意：永假不是永真否认，但若要证注意：永假不是永真否认，但若要证A为永真，可证实为永真，可证实A为永假。为永假。1-8命题演算推理理论命题演算推理理论第18页第18页前面简介了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认推理规则，前面简介了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认推理规则，利用等价或蕴含式，推出结论成立，就是论证。证实利用等价或蕴含式，推出结论成立，就是论证。证实有三种办法。有三种办法。1-8命题演算推理理论命题演算推理理论第19页第19页1-8命题演算推理理论命题演算推理理论第20页第20页1-8命题演算推理理论命题演算推理理论第21页第21页例2P46例题6M：天晴；Q：下雨；S：我看电影；R：我看书。1-8命题演算推理理论命题演算推理理论第22页第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页第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页第24页(10)(MQ)(QM)T(9)E(11)MQT(10)I(12)QT(7)(11)I所有推理办法不唯一，使用等价或蕴含式也不一定相同，但是越简练越好。关于命题逻辑就简介这样多。主要有命题九个联接词；五个主要联接词，最小连接词组为,或,或或等，和一些公式（重言式，蕴含式，对偶式，合取、析取范式）以及推理。下面简介谓词逻辑（数理逻辑另一基本内容）。1-8命题演算推理理论命题演算推理理论第25页第25页在在命命题题逻逻辑辑中中，P,QR是是无无法法推推出出。命命题题逻逻辑辑含含有有不不足足，刻刻画画命命题不够深刻，因此有必要研究谓词逻辑。题不够深刻，因此有必要研究谓词逻辑。在在命命题题逻逻辑辑中中，基基本本单单位位是是原原子子命命题题，它它是是不不可可再再分分。但但是是原原子子命命题间还是有一些共同特性，需要进一步解析。比如：题间还是有一些共同特性，需要进一步解析。比如：例1：P：小李是学生。Q：小张是学生。在命题逻辑中，这是两个不同命题，无法再分了，但共性“是学生”（命题本质属性）无法深入刻划出来，还有些很简朴三段论也是无法用命题逻辑理论推出。例2：P：人是要呼吸。Q：老张是人。R：老张是要呼吸。第二章谓词逻辑第二章谓词逻辑第26页第26页命题逻辑含有不足，刻画命题不够深刻。有必要研究谓词逻辑。命题逻辑含有不足，刻画命题不够深刻。有必要研究谓词逻辑。命题是反应判断陈说句，它至少有主语和谓语两部分构成。命题是反应判断陈说句，它至少有主语和谓语两部分构成。如：小王是学生。如：小王是学生。5不小于不小于7。点点a位于点位于点b与点与点c之间。之间。1定义定义1）主主语语：称称为为客客体体（个个体体），用用a,b,c表表示示。客客观观存存在在东西，能够是详细，也能够是抽象。东西，能够是详细，也能够是抽象。2）用用来来描描述述客客体体性性质质，或或客客体体之之间间关关系系称称为为谓谓词词。用用P,Q,R（大写字母）表示。（大写字母）表示。2-1谓词概念与表示谓词概念与表示第27页第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页第28页因因此此，单单独独一一个个谓谓词词不不是是命命题题，只只有有填填入入客客体体后后才才是是命命题题，叫叫谓词填式。谓词填式。定义：H是n元谓词，a1,a2,a3an是n个客体，H(a1,a2an)所代表式子是一个命题，称为谓词填式。（当ai是客体时，A(a1an)才是命题。）3除了谓词，我们此后还要用到函数这一概念除了谓词，我们此后还要用到函数这一概念例：老张是小张父亲。例：老张是小张父亲。小张父亲小张父亲=老张老张f:.父亲；父亲；a:小张；小张；b:老张；老张；则则b=f(a)2-1谓词概念与表示谓词概念与表示第29页第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页第30页4.定义定义1）个体域（客体叙述范围）个体域（客体叙述范围）2）客客体体变变元元（个个体体变变元元）：以以个个体体域域中中客客体体为为值值变变元元，用用x,y,z表示表示3）论论域域：所所有有客客体体集集合合。全全总总个个体体域域：各各种种个个体体域域综综合合在在一起，作为叙述范围域。一起，作为叙述范围域。2-2命题函数与量词命题函数与量词例例1：H:到达山顶到达山顶l:李四李四t:老虎老虎c:汽车汽车H(l):李四到达山顶。李四到达山顶。2-1谓词概念与表示谓词概念与表示第31页第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页第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页第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页第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页第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页第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页第56页(8)尽管有些人聪明，但未必一切人都聪明。2-3谓词公式与翻译谓词公式与翻译第57页第57页24变元约束变元约束首先引进一些概念：给定一个谓词公式首先引进一些概念：给定一个谓词公式，其中含有公式，其中含有公式量词后面量词后面x叫做指导变元或作用变元，而叫做指导变元或作用变元，而P(x)这样对于日常生活中碰到一些命题普通都能翻译成公式，并且谓词这样对于日常生活中碰到一些命题普通都能翻译成公式，并且谓词公式比命题公式表示更为准确明了。公式比命题公式表示更为准确明了。2-4变元约束变元约束第58页第58页