第2章 谓词逻辑 习题课.ppt

* 离散数学 Discrete Mathematics 主讲：陈哲云 青岛理工大学计算机工程学院 2011.09 * 谓词逻辑符号化(重点) 谓词公式的解释（难点） 谓词逻辑等值式 谓词逻辑 * 能准确地将给定命题谓词逻辑符号化； 熟练地给出公式的解释； 记住闭式的性质； 会判断简单公式的类型； 会求取谓词公式的前束范式。 基本要求 谓词逻辑符号化 2.1 2.3 2.11 （1）在没有任何说明的情况下，默认个体域为全总个体域，不需对每个问题设定自己的个体域。 （2）谓词的刻画不是越细致越好，根据问题需要提取合适的谓词。 （3）注意量词与联结词的搭配。 （4）每个命题谓词符号化的形式可能不止一种。 * 作业讲解 出错较多的题目：2.3 （1）每个大学生不是文科生就是理科生。 解：设M(x)：x是大学生。 P(x)：x是文科生。 Q(x):x是理科生。 或 * 作业讲解 出错较多的题目：2.3 （2）有些人喜欢所有的花。 解：设M(x)：x是人。 P(x)：x喜欢所有的花。 或 * 设M(x)：x是人。 L(x,y)：x喜欢y。 P(x): x是花。 * 出错较多的题目：2.3 （6）凡是对顶角都相等。 解：设L(x，y)：x与y是对顶角。 H(x，y)：x与y相等。 或 设 M(x):x是角。 L(x，y)：x与y是对顶角。 H(x，y)：x与y相等。 出错较多的题目：2.11 要求用全称量词来符号化。 * 作业讲解 谓词公式的解释：2.6,2.12, 2.13 课件补充题 （1）根据解释中个体域的有限性和无限性，对公式的解释可分为两类：若为有穷集合，则通常采取消除量词的方法，且在消除量词之前，通常将量词辖域最小化。若为无穷集合，则只能保留量词，将相应谓词代入公式给出一定的意义，根据已有知识来判断公式的真值。注意要有判断的过程。 * 作业讲解 谓词公式的解释：2.6，2.12，2.13 课件补充题 （2）给出公式的成真或成假解释，通常的做法是将个体域设置为二元集，然后将公式中量词消除，等值转换成0元谓词组合的形式。根据问题要求给出各个谓词的值。 （3）判断谓词公式的类型有两种方法：代换实例法和定义法。代换实例法用来判断逻辑有效式和矛盾式，定义法通常用来判断可满足式。 * 作业讲解 出错较多的题目：2.6 原因：缺少判断的过程。 例：（1） 在解释R下表示：任意实数都大于零。为假命题。 * 出错较多的题目：2.13 一般的做法是消除量词。要有判断的过程。 例： （1） * 作业讲解 或也可保留量词，将谓词代入。 即表示：在个体域D={-2,3,6}中，所有的元素x都满足 ,真值为假。 * 作业讲解 出错较多的题目：2.12 在消除量词时，先将量词辖域缩小。不要转换成前束范式。 例： * 作业讲解 出错较多的题目：课件补充题 一定要有判断的过程。 * 作业讲解 * （1）试判断?xA(x)∨?xB(x) → ?x(A(x)∨B(x))是否是永真式，并说明理由。 出错之一：代换实例法 方法一：给出成假解释 D={a,b}, A(a)=?, A(b)=?, B(a)=?, B(b)=? 使 ?xA(x)∨?xB(x) → ?x(A(x)∨B(x)) ?（A(a) ?A(b) ∨(B(a) ∨B(b) ) → ((A(a)∨B(a)) ? (A(b)∨B(b)) ?0 可用真值表法 作业讲解 方法二：给出解释I 个体域D={-1,2}, A(x):x是自然数。 B(x):x是偶数。 在该解释下，该公式前件为“在个体域D中，所有的个体都是自然数，或存在一个个体是偶数”，为真。 公式后件为“在个体域D中，所有个体或者是自然数，或者是偶数”，为假。 故在此解释下，整个公式的值为假。 * 作业讲解 * （2）设有公式： (?x)(P(x)→Q(x)) ?((?x)P(x)→(?x)Q(x))， 在个体域D={a, b}上，构造两个使公式分别为真和假的解释。 作业讲解 求取前束范式：2.14，2.15 一个公式要成为前束范式，具备两个条件： （1）所有的量词都在公式的最前端，且这些量词的辖域都延伸到公式的最末端。 （2）前端的量词不能含有否定联结词。 * 作业讲解 出错较多的题目：2.15 （2）使用自由变元换名规则求前束范式。