离散数学课件the_third_course.ppt

? (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∨﹁R n个变元对应着2n个大项。 ??小项用m编号，大项用M表示，两个变元用两位二进制编号。 小项0：变元之否定；1：命题变元。如m01?﹁P∧Q。而大项正好相反。 大项0：变元本身，1：变元否定。如：M00?P∨Q。如上面对应2个变元的4个大项：P∨Q,P∨﹁Q,﹁P∨Q,﹁P∨﹁Q ;1. 每个大项的指派与编号相同时，其值为F，而其余2n－1种指派情况下其值均为T。 2.????任意两个不同大项的析取式都为T。如Mi∨Mj（i!=j）总有一个变元与其否定存在。 3.?????全体大项的合取式必为永假F。 ∏（0—>2n－1）Mi=M0∧M1∧M2∧……∧M 2n－1 =F 由大项，可以得到主合取范式。 对于一个公式若存在一个等价式，它由大项的合取所组成，则该等价式称为原式的主合取范式。;合取，即为此公式的主合取范式。 我们求主析取范式时是将所有值为T的指派对应的小项析取；这里求主合取范式是将所有取值为F的所有可能值列出来、取合取。（析取与合取对偶）;1-7　对偶与范式;对于上述定理就不证明了，方法与前面类似。 ? 2． 用等价公式，其步骤为： ;这样当变元次序一定时，每个公式都有唯一与之等价的主合取范式; 1） 大项与小项有什么关系？;;判别有效结论的过程就是论证过程，方法多种多样，但基本上有三种方法。;例如 P41. 例 1. 读题；首先找出命题变元，P : 材料不可靠，Q : 计算有错误。 论证 : ;(2) 直接证法 从已知前提出发，使用公认的推理规则，利用等价式或蕴含式，得到结论。 规则有 P规则 前提在论证过程中任何时候都可用。 T规则 在论证中，如果一个或多个公式蕴含公式S，则S可以引入推理中。 等价式与蕴含式在书 P 43 表 1- 8. 3 , 1- 8. 4可见。;;(3) 间接证法：;1-8　命题演算的推理理论;注意：永假不是永真的否定，但若要证A为永真，可证明 　A为永假。; 前面介绍了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认的推理规则， 利用等价或蕴含式，推出结论成立，就是论证。证明 有三种方法。;1-8　命题演算的推理理论;1-8　命题演算的推理理论;例2　P46例题6 M：天晴；Q：下雨；S：我看电影； R：我看书。;;(9)M 　　 Q T(8)E22 (10)(M 　 Q)　( Q　 M) T(9)E (11) Q　　M T(10)I (12) M　　Q T(11)E (13)Q T(7)(12)I11 (14)R　　Q CP 或 (8)M　　Q P (9) M　　Q T(8)E ;(10)( M Q) (Q M) T(9)E (11) M Q T(10)I (12)Q T(7)(11)I; 在命题逻辑中，P, Q R是无法推出的。命题逻辑具有局限性，刻画命题不够深刻，因此有必要研究谓词逻辑。;命题逻辑具有局限性，刻画命题不够深刻。有必要研究谓词逻辑。;1． a:5 b:7 B:…大于… B(a,b):5大于7;