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

(P∧Q∧(R∨﹁R))∨(﹁P∧R∧(Q∨﹁Q))∨(Q∧R∧(P∨﹁P))(P∧Q∧R)∨(P∧Q∧﹁R)∨(﹁P∧R∧Q)∨(﹁P∧R∧﹁Q)(P∧Q∧R)∨(P∧Q∧﹁R)∨(﹁P∧Q∧R)∨(﹁P∧﹁Q∧R)4.对合取项补入没有出现变元，即添加P∨﹁P等。5.用分配律展开。上次课我们学习了析取范式，形式为：（）∨()∨…∨(),合取范式，形式为：（）∧（）∧（）∧…∧（），引入了小项（它是变元或变元否定式组成合取式，但二者必须出现且仅出现一个。由小项析取我们能够得到主析取范式；这么对于任一公式，我们都可求出其主析取范式，当其变元个数、次序固定时，它是唯一。下面我们主要介绍主合取范式。对应于小项，我们引进了大项。大项定义为：n个命题变元析取式，其中每个变元与它否定不能同时存在，但二者必须出现且仅出现一次，称为大项，也成为布尔析取。﹁P∨﹁Q∨﹁Rn个变元对应着2n个大项。小项用m编号，大项用M表示，两个变元用两位二进制编号。小项0：变元之否定；1：命题变元。如m01﹁P∧Q。而大项恰好相反。大项0：变元本身，1：变元否定。如：M00P∨Q。如上面对应2个变元4个大项：P∨Q,P∨﹁Q,﹁P∨Q,﹁P∨﹁Q1.每个大项指派与编号相同时，其值为F，而其余2n－1种指派情况下其值均为T。2.任意两个不一样大项析取式都为T。如Mi∨Mj（i!=j）总有一个变元与其否定存在。3.全体大项合取式必为永假F。∏（0—>2n－1）Mi=M0∧M1∧M2∧……∧M2n－1=F由大项，能够得到主合取范式。对于一个公式若存在一个等价式，它由大项合取所组成，则该等价式称为原式主合取范式。合取，即为此公式主合取范式。我们求主析取范式时是将全部值为T指派对应小项析取；这里求主合取范式是将全部取值为F全部可能值列出来、取合取。（析取与合取对偶）1-7对偶与范式对于上述定理就不证实了，方法与前面类似。2．用等价公式，其步骤为：这么当变元次序一定时，每个公式都有唯一与之等价主合取范式1）大项与小项有什么关系？判别有效结论过程就是论证过程，方法各种多样，但基本上有三种方法。比如P41.例1.读题；首先找出命题变元，P:材料不可靠，Q:计算有错误。论证:(2)直接证法从已知前提出发，使用公认推理规则，利用等价式或蕴含式，得到结论。规则有P规则前提在论证过程中任何时候都可用。T规则在论证中，假如一个或多个公式蕴含公式S，则S能够引入推理中。等价式与蕴含式在书P43表1-8.3,1-8.4可见。(3)间接证法：1-8命题演算推理理论注意：永假不是永真否定，但若要证A为永真，可证实A为永假。前面介绍了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认推理规则，利用等价或蕴含式，推出结论成立，就是论证。证实有三种方法。1-8命题演算推理理论1-8命题演算推理理论例2P46例题6M：天晴；Q：下雨；S：我看电影；R：我看书。(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)E(10)(MQ)(QM)T(9)E(11)MQT(10)I(12)QT(7)(11)I在命题逻辑中，P,QR是无法推出。命题逻辑含有不足，刻画命题不够深刻，所以有必要研究谓词逻辑。命题逻辑含有不足，刻画命题不够深刻。有必要研究谓词逻辑。1．a:5b:7B:…大于…B(a,b):5大于7所以，单独一个谓词不是命题，只有填入客体后才是命题，叫谓词填式。今天南京气温是20度a:今天；b:南京；g:某天某城市温度则g(a,b)=20度4.定义H(t):老虎抵达山顶。H(c):汽车抵达山顶。H(x)表示H共同形式。但单写H不知是几元谓词，所以需加客体变元。定义：（1）简单命题函数：一个谓词+一些客体变元组成表示式称为简单命题函数。但A(x,y,z)不是命题（2）n元谓词就是有n个客体变元命题函数。（3）复合命题函数：由简单命题函数和逻辑联结词组成命题函数又如例2：H(x,y):x比y长得高l:李四c:张三H(l,c):李四比张三长得高命题函数不是命题，只有客体变元取特定客体时，才是命题。而且真假与其取值也相关系。这节课主要介绍了一些概念我们介绍了谓词逻辑，引进了客体、谓词填式、函数、个体域等概念。对命题可作深入分析，不过，仅有这些还是不够。我们还需要引进量词概念。请看下面例子：下面我们将同学们作业犯错较多题目讲解一下：P8(3)b)读题Q:我将去镇上。R：我有时间。当关系不明朗时，可经过列真值表，直接得出原命题。即我将去镇上，那么我必定有时间，但我有时间时，我不一定会去。去了则表示“我有时间则我去镇上。”P12(5)a)P:你没有给我写信。Q:信在途中丢失了。2-2命题