4.6谓词逻辑中的推理.ppt

*/ 上讲回顾 4.3 谓词公式的解释及类型 谓词公式的解释 谓词公式的类型 4.4 谓词等值的谓词公式 谓词公式等值的定义 基本等值式 4.5 谓词公式的前束范式 谓词公式的前束范式的定义 谓词公式的前束范式的计算 */ 本讲内容 4.6 谓词公式中的推理 教学目标： 1. 掌握与量词相关的逻辑蕴含式 2. 掌握量词消去和引入的4种规则 3. 掌握谓词逻辑的推理方法 重点与难点分析 谓词逻辑的推理 */ 4.6 谓词逻辑中的推理 1. 谓词逻辑中推理的形式结构 首先，A1, A2, Ak, B是谓词公式， A1?A2???Ak ?B的含义同上章3.7节。 A1?A2???Ak ?B的充要条件是式A1?A2???Ak ?B是永真式。 若式A1?A2???Ak ?B是永真式, 则称推理正确, 记作A1?A2???Ak ?B。其中：前提: A1, A2,?, Ak ， 结论: B 例4-19 证明?xA(x) ? A(t). 证明：因为由4.3节例4-9知, ?xA(x) ? A(t)永真. 例4-20 证明?x?yA(x, y) ? ?y?xA(x, y). 证明：因为由4.3节4-11知，?x?yA(x,y) ? ?y?xA(x,y) 永真。 举例说明：I：D=R，A(x,y):xy I：D={班上同学}，A(x,y):x与y是朋友 */ 2.基本推理规则 1. 命题逻辑中的命题逻辑中的基本推理规则可以很方便地推广到谓词逻辑。 2.谓词逻辑中有两个非常重要与量词有关的逻辑蕴涵式。 定理4-1 下列逻辑蕴涵式成立： (1)?xA(x) ? ?xB(x) ? ?x(A(x) ? B(x)) (2)?x(A(x) ? B(x)) ? ?xA(x) ? ?xB(x) How to remember? D = {班上同学}，A(x): x会唱歌，B(x): x会跳舞。 注：(1)?xA(x) ??xB(x) = ?x(A(x) ? B(x)) (2)?x(A(x) ?B(x)) = ?xA(x) ? ?xB(x) */ 3.与量词有关的四个基本推理规则 I. US规则：全称量词消去规则 (1)?xA(x) (2)A(c) (其中c为个体域中任意个体) II. UG规则： (1)A(c) (其中c为个体域中任意个体) (2)?xA(x) 注：取代c的x不能出现在A(c)中。 ?y?xF(x,y) 个体域为实数集R,F(x,y):x＞y 例：设A(c)= ?xF(x,c),若取x代替c得：?xA(x) ??x?xF(x,x)，结论为“?x?x(xx)”,是假命题。 */ III. ES规则: 存在量词消去规则 (1)?xA(x) (2)A(c) (其中c为个体域中某个体) 注：该式成立的条件是：? ①c是使A为真的特定个体常元；c不在A(x)或其前的推导中出现。 ②如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则。 */ 3.与量词有关的四个基本推理规则 反例②：例如：对于?x(x=y),D=R。若使用ES规则，得到c=y, 即在实数集中有一实数c等于任意实数y.结论显然不成立。 反例①: (1) ?xP(x) ? ?xQ(x) P (2) ?xP(x) T(1)I (3) ?xQ(x) T(1)I (4) P(c) ES(2) (5) Q(c) ES(3) (6) P(c) ? Q(c) T(4)(5)I (7) ?x(P(x) ? Q(x)) EG(6) */ 3.与量词有关的四个基本推理规则 IV. EG规则: 存在量词产生规则 (1)A(c) (其中c为个体域中某个体) (2)?xA(x) 注：x不出现在A(c)中 反例：设解释I为：D=N，F(x,y)：x=y (1) F(x,c) P (2) ?xF(x,x) EG(1) */ 3.与量词有关的四个基本推理规则 例：?x(A(x) ? B(x)) ? ?xA(x) ? ?xB(x) 证明：(1) ?x(A(x) ? B(x)) P (2) A(c) ? B(c) ES(1) (3)A(c)