离散数学 课件 thethirdcourse

1、 (PQ(RR)(PR(QQ)(QR(PP) (PQR)(PQR)(PRQ)(PRQ) (PQR)(PQR)(PQR)(PQR) 2.利用等价式求主析取范式例：（PQ）(PR)(QR) 化归方法步骤： 1. 化为析取范式。 2. 删去析取范式中永假的析取项。 3. 将析取式中重复的合取项和相同的变元合并。1-7对偶与范式4. 对合取项补入没有出现的变元，即添加 PP等。 5.用分配律展开。 1-7对偶与范式 上次课我们学习了析取范式，形式为：（ ）( )( ),合取范式，形式为：（ ）（ ）（ ）（ ），引入了小项（它是变元或变元的否定式组成的合取式，但两者必须出现且仅出现一个。由小项的析取我

2、们可以得到主析取范式；这样对于任一公式，我们都可求出其主析取范式，当其变元的个数、次序固定时，它是唯一的。下面我们主要介绍主合取范式。对应于小项，我们引进了大项。 大项的定义为：n个命题变元的析取式，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次，称为大项，也成为布尔析取。例如:2个变元P、Q，可生成22 =4个大项:PQ PQ PQ PQ 3个变元P,Q,R，可以生成8个大项:PQR PQR 1-7对偶与范式 PQR n个变元对应着2n个大项。 小项用m编号，大项用M表示，两个变元用两位二进制编号。 小项0：变元之否定；1：命题变元。如m01PQ。而大项正好相反。 大项0：变

3、元本身，1：变元否定。如：M00PQ。如上面对应2个变元的4个大项：PQ,PQ,PQ,PQ M00=M0,M01=M1,M10=M2,M11=M3 等等可与上面并在一起写。对应于二进制，大项也可以用十进制编号，如上。 大项有如下性质：1-7对偶与范式1. 每个大项的指派与编号相同时，其值为F，而其余2n1种指派情况下其值均为T。2.任意两个不同大项的析取式都为T。如MiMj（i!=j）总有一个变元与其否定存在。3.全体大项的合取式必为永假F。 （02n1）Mi=M0M1M2M 2n1 =F由大项，可以得到主合取范式。 对于一个公式若存在一个等价式，它由大项的合取所组成，则该等价式称为原式的主合

4、取范式。 求主合取范式的方法： 1 真值表法 定理:在真值表中，一个公式的真值为F的指派所对应的大项的1-7对偶与范式合取，即为此公式的主合取范式。我们求主析取范式时是将所有值为T的指派对应的小项析取；这里求主合取范式是将所有取值为F的所有可能值列出来、取合取。（析取与合取对偶）要注意大项的写法不同于小项，另外列真值表必须注意次序，先列T，后列F1-7对偶与范式1-7对偶与范式对于上述定理就不证明了，方法与前面类似。2 用等价公式，其步骤为： 1) 划归为合取范式。 2) 删去合取式中永真的合取式。 3) 合并相同的析取项和相同的变元。 4)对析取项补入没有出现的变元，即补入形如：(PP) 式

5、。 5) 应用分配律展开。上述五个步骤与主析取范式类似。例：化原式为主析取范式（上例）1-7对偶与范式这样当变元次序一定时，每个公式都有唯一与之等价的主合取范式 一个公式，既有与之相等价的唯一的主析取范式，又有唯一的主合取范式，它们之间有何关系呢？首先它们分别由小项、大项决定的，看看小项、大项之间有何关系。1-7对偶与范式 1） 大项与小项有什么关系？1-7对偶与范式总结：学习数理逻辑主要适用于推理，有了前面的这些基础知识，就可以进行推理1-8推理理论 推理就是用一些已知的东西得出另外一些结论。而在推理过程中，常把一些定律、定理和条件，作为假设前提，使用一些公认的规则，得到另外的命题，形成结论

6、，这种过程就是论证。定义：1-7对偶与范式判别有效结论的过程就是论证过程，方法多种多样，但基本上有三种方法。1-8命题演算的推理理论例如 P41. 例 1. 读题；首先找出命题变元，P : 材料不可靠，Q : 计算有错误。论证 : T T T FT F T F T T T TF F F T1-8命题演算的推理理论(2) 直接证法从已知前提出发，使用公认的推理规则，利用等价式或蕴含式，得到结论。规则有 P规则 前提在论证过程中任何时候都可用。 T规则 在论证中，如果一个或多个公式蕴含公式S，则S可以引入推理中。等价式与蕴含式在书 P 43 表 1- 8. 3 , 1- 8. 4可见。1-8命题演

7、算的推理理论证明：注意：必须将证明过程编号一一写出理由。 这里须将每一步依次编号，得出理由；书上给了两种证明法，论证方法不唯一，但方向是明确的，最终能到达C，且步骤越少越好。（3）间接证法1-8命题演算的推理理论(3) 间接证法：1-8命题演算的推理理论1-8命题演算的推理理论注意：永假不是永真的否定，但若要证A为永真，可证明 A为永假。1-8命题演算的推理理论 前面介绍了逻辑推理，所谓逻辑推理就是由一组前提，用一些公认的推理规则，利用等价或蕴含式，推出结论成立，就是论证。证明 有三种方法。1-8命题演算的推理理论1-8命题演算的推理理论1-8命题演算的推理理论例2P46例题6M：天晴；Q：下

8、雨；S：我看电影；R：我看书。1-8命题演算的推理理论要证明：MQ,MS,S RRQ证： (1)R P(附加前提) (2)S R P (3)R S T(2)E (4) S T(1)(3)I11 (5)MS P (6) S M T(5)E (7) M T(4)(6)I11 (8) (MQ) P1-8命题演算的推理理论(9)M Q T(8)E22(10)(M Q)( Q M) T(9)E(11) QM T(10)I(12) MQ T(11)E(13)Q T(7)(12)I11(14)RQ CP 或(8)MQ P(9) MQ T(8)E1-8命题演算的推理理论(10)( M Q) (Q M) T(9

9、)E(11) M Q T(10)I(12)Q T(7)(11)I所有推理方法不唯一，使用的等价或蕴含式也不一定相同，但是越简洁越好。关于命题逻辑就介绍这么多。主要有命题九个联接词；五个主要联接词，最小连接词组为 ,或 ,或或等，和一些公式（重言式，蕴含式，对偶式，合取、析取范式）以及推理。下面介绍谓词逻辑（数理逻辑的另一基本内容）。1-8命题演算的推理理论 在命题逻辑中，P, Q R是无法推出的。命题逻辑具有局限性，刻画命题不够深刻，因此有必要研究谓词逻辑。在命题逻辑中，基本单位是原子命题，它是不可再分的。但是原子命题间还是有一些共同特征的，需要进一步解析。例如：例1：P：小李是学生。 Q：

10、小张是学生。 在命题逻辑中，这是两个不同命题，无法再分了，但共性“是学生”（命题的本质属性）无法进一步刻划出来，还有些很简单的三段论也是无法用命题逻辑的理论推出的。例2： P： 人是要呼吸的。 Q ：老张是人。 R：老张是要呼吸的。第二章谓词逻辑命题逻辑具有局限性，刻画命题不够深刻。有必要研究谓词逻辑。命题是反映判断的陈述句，它至少有主语和谓语两部分组成。 如：小王是学生。 5大于7。 点a位于点b与点c之间。 1定义 1） 主语：称为客体（个体），用a,b,c表示。客观存在的东西，可以是具体的，也可以是抽象的。 2） 用来描述客体的性质，或客体之间的关系的称为谓词。用P,Q,R（大写字母）表

11、示。2-1谓词的概念与表示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谓词的概念与表示 所以，单独一个谓词不是命题，只有填入客体后才是命题，叫谓词填式。定义：H是n元谓词，a1,a2,a3an是n个客体，H(a1,a2an)所代表的式子是一个命题，称为谓词填式。（当ai是客体时，A(a1an)才是命题。）3除了谓词，我们今后还要用到函数这一概念例：老张是小张的父亲。 小张的父亲=老张 f:.

12、的父亲； a:小张； b:老张； 则b=f(a)2-1谓词的概念与表示 今天南京的气温是20度 a :今天 ； b:南京； g:某天某城市的温度 则g(a,b)=20度 所以，函数是将客体映射到客体。而谓词是将客体映射到真或假 的命题。 如：小王是学生 是谓词填入客体得到的命题。 7大于5 是两个客体填入后得到命题，T 用f,g,h.表示函数，如h表示：和.之和， 则a:3,b:4 h(a,b)=72-1谓词的概念与表示4. 定义1）个体域（客体的论述范围） 2）客体变元（个体变元）：以个体域中客体为值的变元，用 x,y,z表示 3）论域：所有客体的集合。全总个体域：各种个体域综合在 一起，作

13、为论述范围的域。 2-2命题函数与量词 例1：H:到达山顶 l:李四 t:老虎 c:汽车 H(l):李四到达山顶。2-1谓词的概念与表示 H(t):老虎到达山顶。 H(c): 汽车到达山顶。 H(x)表示H的共同形式。但单写H不知是几元谓词，所以需加客体变元。例2： L(x,y):xy L(2,3):2z A(4,3,5):4+35 所以，H(x),L(x,y),M(x,y,z)本身不是命题，但当变元取特定 值后成为命题。2-2命题函数与量词定义：（1）简单命题函数：一个谓词+一些客体变元组成的表达式 称为简单命题函数。但A(x,y,z)不是命题 （2）n元谓词就是有n个客体变元的命题函数。

14、（3）复合命题函数：由简单命题函数和逻辑联结词构成的 命题函数 例如1：S(x)表示x学习很好 W(x): x工作很好 S(x)：x学习不是很好 S(x)W(x): x学习很好，工作也好 S(x) W(x):若x学习好，则x工作也好 2-2命题函数与量词又如例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命题函数与量词 命题函数不是命题，只有客体变元取特定客体时，才是命题。而且真假与其取值也有关系。

15、例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谓词公式与翻译(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谓词公式与翻译f(x):x的父亲a:戴婷婷(7)这只大红书柜摆满了那些古书。F(x,y):x摆满了y a:这只大红书柜 b:那些古书可译为：F(a, b)，但描述太粗略。另译为：R(x):x是书柜 B(x):x是大的 C(x):x是红的 D(y):y是古老的E(y):y是书