第二章一阶逻辑教程方案.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 例2.30 构造下面推理的证明。 前提：?xF(x)∨?xG(x) 结论：?x(F(x)∨G(x)) 解 (1) ?xF(x)∨?xG(x) 前提引入 (2) ?x?y(F(x)∨G(y)) (1)置换 (3) ? y(F(x)∨G(y)) (2)UI (4) F(x)∨G(x) (3)UI (5) ?x(F(x)∨G(x)) (4)UG 例2.31 前提：?y?xP(x,y) 结论：?x?yP(x,y) 解 (1) ? y?xP(x,y) 前提引入 (2) ?xP(x,a) (1)EI (3) P(x,a) (2)UI (4) ?yP(x,y) (3)EG (5) ?x?yP(x,y) (4)UG 例 用构造证明的方法证明以下推理的正确性。 每个不用功的学生都考不上大学。小张是考上了大学的学生。所以，小张是用功的学生。 解 首先将前提和结论符号化。 取个体域为人的集合。 S(x)：x是学生。 D(x)：x考上大学。 G(x)：x是用功的。 a：小张。 “每个不用功的学生都考不上大学”符号化为： ? x(S(x)∧┐G(x)→┐D(x))。 “小张是考上了大学的学生”符号化为：S(a)∧D(a)。 “小张是用功的学生”符号化为：S(a)∧G(a) 前提：x(S(x)∧┐G(x)→┐D(x))，S(a)∧D(a) 结论：S(a)∧G(a) (1) x(S(x)∧┐G(x)→┐D(x)) 前提引入 (2) S(a)∧┐G(a)→┐D(a) (1)UI (3) S(a)∧D(a) 前提引入 (4) S(a) (3)化简 (5) D(a)∧S(a) (3)置换 (6) D(a) (5)化简 (7) ┐┐D(a) (6)置换 (8) ┐( S(a)∧┐G(a)) (2)(7)拒取式 ( 9 ) G(a)∨┐S(a) (8)置换 (10) ┐┐S(a) (4)置换 (11) G(a) (9)(10)析取三段论 (12) S(a)∧G(a) (4)(11)合取引入 * * * * * * * * * * * * * * * * * * * * * * * * * * * ⑶ ?xE(g(x,a),x)是闭式，没有自由变元，不需考虑赋值。在解释I下，它表示命题： 对于每个自然数x，x·0＝x。 显然，这是一个假命题。 ⑷ ?x?yL(x,y)是闭式，没有自由变元，不需考虑赋值。在解释I下，它表示命题： 对于每个自然数x，存在自然数y，使得x＜y。 显然，这是一个真命题。 设解释I的个体域DI＝｛e1,…,en｝，在解释I和I中赋值v下， ?xA(x)＝A(e1)∧…∧A(en) ?xA(x)＝A(e1)∨…∨A(en) 例2.9 设f是一元运算符号，P是一元谓词符号，Q是二元谓词符号。给定解释I如下： DI＝｛2,3｝，f(2)＝3，f(3)＝2，P(2)＝1，P(3)＝0 Q(2,2)＝Q(3,3)＝1，Q(2,3)＝Q(3,2)＝0 求下列闭式在解释I下的真值。 ⑴ ?x(Q(f(x),x)→P(x)) ⑵ ?xQ(x,x) ⑷ ?x?yQ(x,y) 解 ⑴ ?x(Q(f(x),x)→P(x)) ＝(Q(f(2),2)→P(2))∧(Q(f(3),3)→P(3)) ＝(Q(3,2)→P(2))∧(Q(2,3)→P(3)) ＝(0→1)∧(0→0)＝1 ⑵ ?xQ(x,x)＝Q(2,2)∧Q(3,3)＝1∧1＝1 ⑷ ? x?yQ(x,y)＝ ? yQ(2,y)∧ ? yQ(3,y) ＝(Q(2,2)∨Q(2,3))∧(Q(3,2)∨Q(3,3))＝(1∨0)∧(0∨1)＝1 定义2.9 设A是公式，I是解释。如果A在I和I中任意赋值下均为真，则称A在I下为真。如果A在I和I中任意赋值下均为假，则称A在I下为假。 例2.10 设f,g,h是二元运算符号，E,L是二元谓词符号。给定解释I如下： 个体域DI为有理数集， f(x,y)＝x·y, g(x,y)＝x＋y, h(x,y)＝x2－y2, a＝0, b＝1, E(x,y): x＝y, L(x,y): x＜