21
2
练习1
在分别取个体域为 (a) D1=N (b) D2=R (c) D3为全总个体域 的条件下, 将下面命题符号化，并讨论真值 (1) 对于任意的数x，均有(x2-4)=(x-2)(x+2) (2) 存在数x，使得 x+7=5 解：(1) 设G(x): (x2-4)=(x-2)(x+2) 假 (a) xG(x) 真 (b) xG(x) (c) 又设F(x):x是实数 真 x(F(x)G(x))
6
练习3
3. 给定解释 I 如下: (a) 个体域D=N (b) a=2 (c) f(x,y)=x+y, g(x,y)=xy (d) F(x,y):x=y 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x) (2) xy(F(f(x,a),y)F(f(y,a),x)) (3) xyzF(f(x,y),z) (4) xyzF(f(y,z),x) (5) xF(f(x,x),g(x,x))
7
练习3
(1)xF(g(x,a),x) x(2x=x) (2) xy(F(f(x,a),y)F(f(y,a),x)) xy(x+2=yy+2=x) (3) xyzF(f(x,y),z) xyz(x+y=z) (4) xyzF(f(y,z),x) xyz(y+z=x) (5) xF(f(x,x),g(x,x)) x(x+x=xx) 假 假 真 假 真
17
练习3（续）
(3)前提：x(F(x)G(x)), x(G(x)H(x)) 结论：xF(x)xH(x) 证明: 用附加前提法 ① xF(x) 附加前提引入 ② F(x) ① ③ x(F(x)G(x)) 前提引入 ④ F(x)G(x) ③ ⑤ x(G(x)H(x)) 前提引入 ⑥ G(x)H(x) ⑤ ⑦ F(x)H(x) ④⑥假言三段论 ⑧ H(x) ②⑦假言推理 ⑨ xH(x) ⑧ +
求下述在I下的解释及其真值: xy(F(f(x))G(y,f(a))) 解 xF(f(x))yG(y,f(a)) F(f(2))F(f(3))(G(2,f(2))G(3,f(2))) 10(10)0
13
练习2
2.求下述公式的前束范式: xF(x)y(G(x,y)H(x,y)) 解 使用换名规则, xF(x)y(G(x,y)H(x,y)) zF(z)y(G(x,y)H(x,y)) z(F(z)y(G(x,y)H(x,y)) zy(F(z)(G(x,y)H(x,y)))
14
练习2
使用代替规则 xF(x)y(G(x,y)H(x,y)) xF(x)y(G(z,y)H(z,y)) x(F(x)y(G(z,y)H(z,y)) xy(F(x)(G(z,y)H(z,y)))
15
习3
3.构造下面推理的证明: (1) 前提：x(F(x)G(x)), xF(x) 结论：xG(x) 证明： ① x(F(x)G(x)) 前提引入 ② F(y)G(y) ① ③ xF(x) 前提引入 ④ F(y) ③ ⑤ G(y) ②④假言推理 ⑥ yG(y) ⑤ + ⑦ xG(x) ⑥置换
9
练习5
5. 证明下列公式为永真式: (1) (xF(x)yG(y))xF(x)yG(y) (AB)AB的代换实例 (2) x(F(x)(F(x)G(x))) 设I是任意的一个解释, 对每一个xDI, F(x)(F(x)G(x))恒为真
10
习题课-谓词逻辑(2)
19
练习4（续）
证明：用归谬法 (1) x(F(x)G(x)H(x)) (2) x(F(x)G(x)H(x)) (3) (F(y)G(y)H(y)) (4) G(y) F(y)H(y) (5) x(F(x)G(x)) (6) F(y)G(y) (7) F(y) F(y)H(y) 论
习题课-谓词逻辑(1)
主要内容 个体词、谓词、量词 一阶逻辑命题符号化 一阶语言L：项、原子公式、合式公式 公式的解释
量词的辖域、指导变元、个体变项的自由出现与约 束出现、闭式、解释
公式的类型
永真式(逻辑有效式)、矛盾式(永假式)、可满足式
1
习题课-谓词逻辑(1)
基本要求 准确地将给定命题符号化 理解一阶语言的概念 理解一阶语言的解释 熟练地给出公式的解释 记住闭式的性质并能应用它 深刻理解永真式、矛盾式、可满足式的概 念, 会判断简单公式的类型
12
练习1
1. 给定解释I如下: (1) 个体域D={2,3} (2) a 2 (3) f ( x ) : f ( 2) 3, f ( 3) 2 (4) F ( x ) : F ( 2) 0, F ( 3) 1
G ( x , y ) : G ( 2,2) G ( 2,3) G ( 3,2) 1, G ( 3,3) 0
主要内容 一阶逻辑等值式
基本等值式，置换规则、换名规则、代替规则
前束范式 推理的形式结构 自然推理系统NL
推理定律、推理规则
11
习题课-谓词逻辑(2)
基本要求 深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟练地应用它们． 熟练正确地使用置换规则、换名规则、代 替规则． 能够理解公式的前束范式． 深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用、 +、+、 4条推理规则的条件． 能正确地给出有效推理的证明．
5
练习2
(4) 没有不爱吃糖的人。 设F(x): x是人，G(x): x爱吃糖 x(F(x)G(x)) 或 x(F(x)G(x)) (5) 任何两个不同的人都不一样高。 设F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高 x(F(x)y(F(y)H(x,y)L(x,y))) 或 xy(F(x)F(y)H(x,y)L(x,y)) (6) 不是所有的汽车都比所有的火车快。 设F(x):x是汽车, G(y):y是火车, H(x,y):x比y快 xy(F(x)G(y)H(x,y)) 或 xy(F(x)G(y)H(x,y))
结论否定引入 (1)置换 (2) (3)置换 前提引入 (5) (4)(6)假言三段
20
练习4(续)
(8) F(y) H(y) (9) y(F(y) H(y)) (10) x(F(x) H(x)) (11) x(F(x) H(x)) (12) 0 (7)置换 (8)+ (9)置换 前提引入 (10)(11)合取
18
练习4
4. 在自然推理系统NL 中，构造推理的证 明． 人都喜欢吃蔬菜．但不是所有的人都喜欢吃 鱼．所以, 存在喜欢吃蔬菜而不喜欢吃鱼的 人． 解 令F(x): x为人，G(x): x喜欢吃蔬菜，H(x): x喜欢吃鱼． 前提：x(F(x)G(x)), x(F(x)H(x)) 结论：x(F(x)G(x)H(x))
3
练习1(续)
(2) 存在数x，使得 x+7=5 解 设H(x)：x+7=5 (a) xH(x) (b) xH(x) (c) 又设F(x)：x为实数 x(F(x)H(x))
假
真 真
本例说明：不同个体域内，命题符号化形式可 能不同（也可能相同），真值可能不同（也可 能相同）.
4
练习2
2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱。 设F(x): x为大熊猫，G(x): x可爱 x(F(x)G(x)) (2) 有人爱发脾气。 设F(x): x是人，G(x): x爱发脾气 x(F(x)G(x)) (3) 说所有人都爱吃面包是不对的。 设F(x): x是人，G(x): x爱吃面包 x(F(x)G(x)) 或 x(F(x)G(x))
8
练习4
4. 证明下面公式既不是永真式也不是矛盾式: (1) x(F(x)G(x)) (2) xy(F(x)G(y)H(x,y)) 解： 1)解释1: D1=N, F(x):x是偶数, G(x): x是奇数 真 解释2: D2=N, F(x):x是负数, G(x): x是无理数 假 2)解释1: D1=Z, F(x):x是正数, G(x): x是负数, H(x,y):x>y 真 解释2: D2=Z, F(x):x是偶数, G(x): x是奇数, H(x,y):x>y 假
16
练习3（续）
(2) 前提：x(F(x)G(x)), xG(x) 结论：xF(x) 证明：用归谬法 ① xF(x) 结论否定引入 ② xF(x) ①置换 ③ xG(x) 前提引入 ④ xG(x) ③置换 ⑤ x(F(x)G(x)), 前提引入 ⑥ F(c) ② ⑦ G(c) ④ ⑧ F(c)G(c) ⑤ ⑨ G(c) ⑥⑧析取三段论 ⑩ G(c)G(c) ⑦⑨合取引入