版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、陈瑜,Email: 2020年9月4日星期五,离散数学,计算机学院,2020/9/4,计算机学院,2/112,主要内容,1. 谓词逻辑的推理方法 2.消解(归结)法,2020/9/4,计算机学院,3/112,2.5 谓词逻辑的推理,推理演算过程: 首先将以自然语句表示的推理问题引入谓词 加以形式化; 若不能直接使用基本推理公式则消去量词; 在无量词的情形下使用推理规则和公式进行 推理; 最后再引入量词以求得结论。,2020/9/4,计算机学院,4/112,推理规则,命题逻辑推理的三条推理规则继续实用于谓词逻辑推理!(P、T、CP) 在前面介绍的推理演算过程中,如何消去量词或引入量词? 下面介绍
2、4条专门针对量词的推理规则。,2020/9/4,计算机学院,5/112,推理规则,命题逻辑推理的三条推理规则继续实用于谓词逻辑推理!(P、T、CP) 在前面介绍的推理演算过程中,如何消去量词或引入量词? 下面介绍4条专门针对量词的推理规则。,2020/9/4,计算机学院,6/112,推理规则,量词的四条重要的推理规则:,1) US规则(全称指定规则、全称量词消去规则): (x)G(x)G(y) 或 (x)G(x)G(c) 注意:以上2公式的成立条件: 1)y是任意的不在G(x)中受约束出现的个体变项; 2)c为任意个体变项; US规则表明“每一个均成立,则其中任一个也必成立”。,2020/9/
3、4,计算机学院,7/112,推理规则,量词的四条重要的推理规则:,1) US规则(全称指定规则、全称量词消去规则): (x)G(x)G(y) 或 (x)G(x)G(c) 注意:以上2公式的成立条件: 1)y是任意的不在G(x)中受约束出现的个体变项; 2)c为任意个体变项; US规则表明“每一个均成立,则其中任一个也必成立”。,2020/9/4,计算机学院,8/112,推理规则,2) UG规则(全称推广规则、全称量词附加规则): G(y) (x)G(x) 注意:以上公式的成立条件: 1)y在G(x)中自由出现,并且y取任意yD时,G(y)为真; 2)取代y的x不能在G(y)中出现; 3)US规
4、则不是UG规则的逆命题; 4)US规则中y是“某一个”,而UG规则中的y是“每一个”。,2020/9/4,计算机学院,9/112,推理规则,2) UG规则(全称推广规则、全称量词附加规则): G(y) (x)G(x) 注意:以上公式的成立条件: 1)y在G(x)中自由出现,并且y取任意yD时,G(y)均为真; 2)取代y的x不能在G(y)中出现; 3)US规则不是UG规则的逆命题; 4)US规则中y是“某一个”,而UG规则中的y是“每一个”。,2020/9/4,计算机学院,10/112,推理规则,3) ES规则(存在指定规则、存在量词消去规则): (x)G(x) G(c) 注意:以上公式的成立
5、条件: 1)c是使G(x)为真的特定的个体常项; 2)c不曾在G(x)中出现过; 3)G(x)中除x外,还有其他自由变项时,不可用此规则; 尤其第一条,c不是任取一个,而是某些特定的个体! 例:G(x):x是男生,c:王芳。则:(x)G(x) G(c)是错误的推理!,2020/9/4,计算机学院,11/112,推理规则,3) ES规则(存在指定规则、存在量词消去规则): (x)G(x) G(c) 注意:以上公式的成立条件: 1)c是使G(x)为真的特定的个体常项; 2)c不曾在G(x)中出现过; 3)G(x)中除x外,还有其他自由变项时,不可用此规则; 尤其第一条,c不是任取一个,而是某些特定
6、的个体! 例:G(x):x是男生,c:王芳。则:(x)G(x) G(c)是错误的推理!,2020/9/4,计算机学院,12/112,推理规则,3) ES规则(存在指定规则、存在量词消去规则): (x)G(x) G(c) 注意:以上公式的成立条件: 1)c是使G(x)为真的特定的个体常项; 2)c不曾在G(x)中出现过; 3)G(x)中除x外,还有其他自由变项时,不可用此规则; 尤其第一条,c不是任取一个,而是某些特定的个体! 例:G(x):x是男生,c:王芳。则:(x)G(x) G(c)是错误的推理!,2020/9/4,计算机学院,13/112,推理规则,4) EG规则(存在推广规则、存在量词
7、附加规则): G(c) (x)G(x) 注意:以上公式的成立条件: 1)c是某个个体常项; 2)取代c的x不能在G(c)中出现过;,2020/9/4,计算机学院,14/112,推理方法,1)直接证明法 2)CP规则证明法 3)反证法等。,2020/9/4,计算机学院,15/112,例5-1:证明论断“人都是要死的,苏格拉底是人,所以苏格拉底是要死的”的正确性。 证: 设谓词 Man(x):x是人; Mortal(x):x是要死的; 客体 s:苏格拉底。则以上论断符号化为: (x)Man(x) Mortal(x)Man(s) Mortal(s),2020/9/4,计算机学院,16/112,例5-
8、1:证明论断“人都是要死的,苏格拉底是人,所以苏格拉底是要死的”的正确性。 证: 设谓词 Man(x):x是人; Mortal(x):x是要死的; 客体 s:苏格拉底。则以上论断符号化为: (x)Man(x) Mortal(x)Man(s) Mortal(s),2020/9/4,计算机学院,17/112,证: (续)(直接证明法可采用如下步骤进行) 1)(x)Man(x) Mortal(x) P 2) Man(s) Mortal(s) US 1) 3) Man(s) P 4) Mortal(s) T(2,3)I3,2020/9/4,计算机学院,18/112,例: (p40 例2.19),202
9、0/9/4,计算机学院,19/112,例5-2:试证 (x)(C(x)W(x)R(x)(x)(C(x)Q(x) (x)(Q(x)R(x) 分析: 前提: (x)(C(x)W(x) R(x), (x)(C(x)Q(x) 结论: (x)(Q(x)R(x) 思路:在使用前提时,尽量先使用前提。因为成立,即有一个特定的个体c存在,并且c对前提中每个个体均成立,但反之不一定成立。,2020/9/4,计算机学院,20/112,例5-2:试证 (x)(C(x)W(x)R(x)(x)(C(x)Q(x) (x)(Q(x)R(x) 分析: 前提: (x)(C(x)W(x) R(x), (x)(C(x)Q(x) 结
10、论: (x)(Q(x)R(x) 思路:在使用前提时,尽量先使用前提。因为成立,即有一个特定的个体c存在,并且c对前提中每个个体均成立,但反之不一定成立。,2020/9/4,计算机学院,21/112,例5-2:试证 (x)(C(x)W(x)R(x)(x)(C(x)Q(x) (x)(Q(x)R(x) 分析: 前提: (x)(C(x)W(x) R(x), (x)(C(x)Q(x) 结论: (x)(Q(x)R(x) 思路:在使用前提时,尽量先使用前提。因为成立,即有一个特定的个体c存在,并且c对前提中每个个体均成立,但反之不一定成立。,2020/9/4,计算机学院,22/112,证明: (1) (x)
11、(C(x)Q(x) P (2) C(a) Q(a) ES (1) (注:此处a是特定的) (3) (x)(C(x)W(x) R(x) P (4) C(a)W(a) R(a) US (3) (注:因(3)中“任意”的,所以此处可以使用 (2)中的a。若(3)中是 ,则此处不可用a。) (5) C(a) T (2)I2,2020/9/4,计算机学院,23/112,证明: (1) (x)(C(x)Q(x) P (2) C(a) Q(a) ES (1) (注:此处a是特定的) (3) (x)(C(x)W(x) R(x) P (4) C(a)W(a) R(a) US (3) (注:因(3)中“任意”的,
12、所以此处可以使用 (2)中的a。若(3)中是 ,则此处不可用a。) (5) C(a) T (2)I2,2020/9/4,计算机学院,24/112,证明: (1) (x)(C(x)Q(x) P (2) C(a) Q(a) ES (1) (注:此处a是特定的) (3) (x)(C(x)W(x) R(x) P (4) C(a)W(a) R(a) US (3) (注:因(3)中“任意”的,所以此处可以使用 (2)中的a。若(3)中是 ,则此处不可用a。) (5) C(a) T (2)I2,2020/9/4,计算机学院,25/112,证明: (1) (x)(C(x)Q(x) P (2) C(a) Q(a
13、) ES (1) (注:此处a是特定的) (3) (x)(C(x)W(x) R(x) P (4) C(a)W(a) R(a) US (3) (注:因(3)中“任意”的,所以此处可以使用 (2)中的a。若(3)中是 ,则此处不可用a。) (5) C(a) T (2)I2,2020/9/4,计算机学院,26/112,证明: (1) (x)(C(x)Q(x) P (2) C(a) Q(a) ES (1) (注:此处a是特定的) (3) (x)(C(x)W(x) R(x) P (4) C(a)W(a) R(a) US (3) (注:因(3)中“任意”的,所以此处可以使用 (2)中的a。若(3)中是 ,
14、则此处不可用a。) (5) C(a) T (2)I2,2020/9/4,计算机学院,27/112,证明(续) :,(6) W(a) R(a) T(4)(5)I3 (7) R(a) T(6)I2 (8) Q(a) T(2)I2 (9) Q(a) R(a) T(7)(8)I1 (10)(x)(Q(x)R(x) EG (9)证毕,2020/9/4,计算机学院,28/112,证明(续) :,(6) W(a) R(a) T(4)(5)I3 (7) R(a) T(6)I2 (8) Q(a) T(2)I2 (9) Q(a) R(a) T(7)(8)I1 (10)(x)(Q(x)R(x) EG (9)证毕,2
15、020/9/4,计算机学院,29/112,证明(续) :,(6) W(a) R(a) T(4)(5)I3 (7) R(a) T(6)I2 (8) Q(a) T(2)I2 (9) Q(a) R(a) T(7)(8)I1 (10)(x)(Q(x)R(x) EG (9)证毕,2020/9/4,计算机学院,30/112,证明(续) :,(6) W(a) R(a) T(4)(5)I3 (7) R(a) T(6)I2 (8) Q(a) T(2)I2 (9) Q(a) R(a) T(7)(8)I1 (10)(x)(Q(x)R(x) EG (9)证毕,2020/9/4,计算机学院,31/112,证明(续) :
16、,(6) W(a) R(a) T(4)(5)I3 (7) R(a) T(6)I2 (8) Q(a) T(2)I2 (9) Q(a) R(a) T(7)(8)I1 (10)(x)(Q(x)R(x) EG (9)证毕,2020/9/4,计算机学院,32/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(
17、y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,33/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6
18、 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,34/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中
19、y指代任意的),2020/9/4,计算机学院,35/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,36/112,例5-
20、3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,37/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)
21、H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,38/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x
22、)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,39/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (
23、3) (x)( H(x) F(x) T(2)E (4) H(y) F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,40/112,例5-3:试证明: 前提: (x)(F(x)H(x), (x)(G(x)H(x) 结论: (x)(G(x)F(x) 证明: (x)(F(x)H(x) P (2) (x)(F(x) H(x) T(1)E (3) (x)( H(x) F(x) T(2)E (4) H(y)
24、F(y) US(3) (5) (x)(G(x)H(x) P G(y)H(y) US (5) (7) G(y) F(y) T(4)(6)I6 (8) (x)(G(x)F(x) UG(7)证毕 (因为(7)中y指代任意的),2020/9/4,计算机学院,41/112,例5-4: “有些病人相信所有的医生,而病人均不相信江湖骗子”。试证明“医生不是骗子”。 符号化:R(x):x是病人 D(x):x是医生 S(x):x是江湖骗子 L(x,y):x相信y 前提:(x)(R(x)(y)(D(y) L(x,y), (x )(R(x) (y)(S(y) L(x,y) 结论: (x )(D(x) S(x) 思路
25、:先用再用 ,即先找特殊的再找一般的!,2020/9/4,计算机学院,42/112,例5-4: “有些病人相信所有的医生,而病人均不相信江湖骗子”。试证明“医生不是骗子”。 符号化:R(x):x是病人 D(x):x是医生 S(x):x是江湖骗子 L(x,y):x相信y 前提:(x)(R(x)(y)(D(y) L(x,y), (x )(R(x) (y)(S(y) L(x,y) 结论: (x )(D(x) S(x) 思路:先用再用 ,即先找特殊的再找一般的!,2020/9/4,计算机学院,43/112,例5-4: “有些病人相信所有的医生,而病人均不相信江湖骗子”。试证明“医生不是骗子”。 符号化
26、:R(x):x是病人 D(x):x是医生 S(x):x是江湖骗子 L(x,y):x相信y 前提:(x)(R(x)(y)(D(y) L(x,y), (x )(R(x) (y)(S(y) L(x,y) 结论: (x )(D(x) S(x) 思路:先用再用 ,即先找特殊的再找一般的!,2020/9/4,计算机学院,44/112,例5-4: “有些病人相信所有的医生,而病人均不相信江湖骗子”。试证明“医生不是骗子”。 符号化:R(x):x是病人 D(x):x是医生 S(x):x是江湖骗子 L(x,y):x相信y 前提:(x)(R(x)(y)(D(y) L(x,y), (x )(R(x) (y)(S(y
27、) L(x,y) 结论: (x )(D(x) S(x) 思路:先用再用 ,即先找特殊的再找一般的!,2020/9/4,计算机学院,45/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的
28、人,那么就应包括(2)中的那个特定的人) (7) R(a) T(2)I2,2020/9/4,计算机学院,46/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的
29、那个特定的人) (7) R(a) T(2)I2,2020/9/4,计算机学院,47/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的那个特定的人) (7) R
30、(a) T(2)I2,2020/9/4,计算机学院,48/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的那个特定的人) (7) R(a) T(2)I2,20
31、20/9/4,计算机学院,49/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的那个特定的人) (7) R(a) T(2)I2,2020/9/4,计算机学院,
32、50/112,证明:,(1) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的那个特定的人) (7) R(a) T(2)I2,2020/9/4,计算机学院,51/112,证明:,(1
33、) (x)(R(x)(y)(D(y) L(x,y) P (2) R(a)(y)(D(y) L(a,y) ES (1) (a是相信所有医生的那个人) (3) (y)(D(y) L(a,y) T(2)I2 (4) D(t) L(a,t) US(3) (此处t是所有的人,与(2)中a不同) (5) (x)(R(x) (y)(S(y)L(x,y) P (6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a:既然(5)中指所有的人,那么就应包括(2)中的那个特定的人) (7) R(a) T(2)I2,2020/9/4,计算机学院,52/112,证明:,(8) (y)(S(y)L(a
34、,y) T(6)(7)I3 (9) S(t) L(a,t) US (8) (10) L(a,t) S(t) T(9)E22 (11)D(t) S(t) T(4)(10)I6 (12) (x)(D(x)S(x) UG (11)证毕 (因为(11)中的t指代的是任意的人!),2020/9/4,计算机学院,53/112,证明:,(8) (y)(S(y)L(a,y) T(6)(7)I3 (9) S(t) L(a,t) US (8) (10) L(a,t) S(t) T(9)E22 (11)D(t) S(t) T(4)(10)I6 (12) (x)(D(x)S(x) UG (11)证毕 (因为(11)中
35、的t指代的是任意的人!),2020/9/4,计算机学院,54/112,证明:,(8) (y)(S(y)L(a,y) T(6)(7)I3 (9) S(t) L(a,t) US (8) (10) L(a,t) S(t) T(9)E22 (11)D(t) S(t) T(4)(10)I6 (12) (x)(D(x)S(x) UG (11)证毕 (因为(11)中的t指代的是任意的人!),2020/9/4,计算机学院,55/112,证明:,(8) (y)(S(y)L(a,y) T(6)(7)I3 (9) S(t) L(a,t) US (8) (10) L(a,t) S(t) T(9)E22 (11) D(
36、t) S(t) T(4)(10)I6 (12) (x)(D(x)S(x) UG (11)证毕 (因为(11)中的t指代的是任意的人!),2020/9/4,计算机学院,56/112,证明:,(8) (y)(S(y)L(a,y) T(6)(7)I3 (9) S(t) L(a,t) US (8) (10) L(a,t) S(t) T(9)E22 (11) D(t) S(t) T(4)(10)I6 (12) (x)(D(x)S(x) UG (11)证毕 (因为(11)中的t指代的是任意的人!),2020/9/4,计算机学院,57/112,消解(归结)法,消解证明的过程: (1)为了证明 G1,G2,G
37、n H 根据反证法,即需证明 G=G1,G2,Gn,H RR (2)建立子句集 先将G化成等值的前束范式 将前束范式化成Skolem范式(消去存在量词),得到仅含全称量词的公式G*,从而对G的不可满足性,可由G*的不可满足性得到。,2020/9/4,计算机学院,58/112,消解(归结)法,消解证明的过程: (1)为了证明 G1,G2,Gn H 根据反证法,即需证明 G=G1,G2,Gn,H RR (2)建立子句集 先将G化成等值的前束范式 将前束范式化成Skolem范式(消去存在量词),得到仅含全称量词的公式G*,从而对G的不可满足性,可由G*的不可满足性得到。,2020/9/4,计算机学院
38、,59/112,消解(归结)法,消解证明的过程: (1)为了证明 G1,G2,Gn H 根据反证法,即需证明 G=G1,G2,Gn,H RR (2)建立子句集 先将G化成等值的前束范式 将前束范式化成Skolem范式(消去存在量词),得到仅含全称量词的公式G*,从而对G的不可满足性,可由G*的不可满足性得到。,2020/9/4,计算机学院,60/112,消解(归结)法(续),将G*的全称量词省略。 G*的母式(已合取化)的合取词以,表示,得G的子句集S。 (3) 对S作归结(消解) 归结:设C1,C1是两个无共同变元的子句,L1,L2分别是C1,C2中的句节 。如果L1和L2有合一置换(一致化
39、) (L1,L2中的变元x用代入),(C1-L1)U(C2-L2)称作子句C1,C2的归结式。,2020/9/4,计算机学院,61/112,消解(归结)法(续),将G*的全称量词省略。 G*的母式(已合取化)的合取词以,表示,得G的子句集S。 (3) 对S作归结(消解) 归结:设C1,C1是两个无共同变元的子句,L1,L2分别是C1,C2中的句节 。如果L1和L2有合一置换(一致化) (L1,L2中的变元x用代入),(C1-L1)U(C2-L2)称作子句C1,C2的归结式。,2020/9/4,计算机学院,62/112,消解(归结)法(续),将G*的全称量词省略。 G*的母式(已合取化)的合取词
40、以,表示,得G的子句集S。 (3) 对S作归结(消解) 归结:设C1,C1是两个无共同变元的子句,L1,L2分别是C1,C2中的句节 。如果L1和L2有合一置换(一致化) (L1,L2中的变元x用代入),(C1-L1)U(C2-L2)称作子句C1,C2的归结式。,2020/9/4,计算机学院,63/112,消解(归结)法(续),(例如 C1=P(x) Q(x) C2=P(a) R(y) P(x)与P(a)合一置换a/x,即将变元x换 成a,便为互补对,可作归结了,有归结式 R(C1,C2)=Q(a) R(y)) 对子句集S的任意两个子句作归结(如果可作归结)并将归结式仍放入S,重复这一过程。
41、(4)直到归结出空子句,证明结束。,2020/9/4,计算机学院,64/112,消解(归结)法(续),(例如 C1=P(x) Q(x) C2=P(a) R(y) P(x)与P(a)合一置换a/x,即将变元x换 成a,便为互补对,可作归结了,有归结式 R(C1,C2)=Q(a) R(y)) 对子句集S的任意两个子句作归结(如果可作归结)并将归结式仍放入S,重复这一过程。 (4)直到归结出空子句,证明结束。,2020/9/4,计算机学院,65/112,消解(归结)法(续),(例如 C1=P(x) Q(x) C2=P(a) R(y) P(x)与P(a)合一置换a/x,即将变元x换 成a,便为互补对,
42、可作归结了,有归结式 R(C1,C2)=Q(a) R(y)) 对子句集S的任意两个子句作归结(如果可作归结)并将归结式仍放入S,重复这一过程。 (4)直到归结出空子句,证明结束。,2020/9/4,计算机学院,66/112,例5-5 利用消解法证明: (p66例2.22) 前提:(x)(P(x) (y)(Q(y) R(x,y), (x)(P(x) (y)(S(y) R(x,y) 结论: (x)(S(x) Q(x) 证明:首先将结论的否定作为附加前提,与原有前提 一起转化为Skolem范式: (x)(P(x) (y)(Q(y) R(x,y) (x)(P(x) (y)(S(y) R(x,y) (x
43、)(S(x) Q(x),2020/9/4,计算机学院,67/112,例5-5 利用消解法证明: (p66例2.22) 前提:(x)(P(x) (y)(Q(y) R(x,y), (x)(P(x) (y)(S(y) R(x,y) 结论: (x)(S(x) Q(x) 证明:首先将结论的否定作为附加前提,与原有前提 一起转化为Skolem范式: (x)(P(x) (y)(Q(y) R(x,y) (x)(P(x) (y)(S(y) R(x,y) (x)(S(x) Q(x),2020/9/4,计算机学院,68/112,(x) (y)( P(x) Q(y) R(x,y) (u)(P(u) (z)( S(z)
44、 R(u,z) (v)(S(v) Q(v) (u) (v) (x) (y) (z) (P(x) Q(y) R(x,y) P(u) ( S(z) R(u,z) S(v) Q(v) (x) (y) (z) (P(x) Q(y) R(x,y) P(a) ( S(z) R(a,z) S(b) Q(b) 上面即为Skolem范式,由此得到子句集: P(x) Q(y) R(x,y)、 P(a) 、 S(z) R(a,z)、 S(b) 、 Q(b) 。,2020/9/4,计算机学院,69/112,(x) (y)( P(x) Q(y) R(x,y) (u)(P(u) (z)( S(z) R(u,z) (v)(
45、S(v) Q(v) (u) (v) (x) (y) (z) (P(x) Q(y) R(x,y) P(u) ( S(z) R(u,z) (S(v) Q(v) (x) (y) (z) (P(x) Q(y) R(x,y) P(a) ( S(z) R(a,z) S(b) Q(b) 上面即为Skolem范式,由此得到子句集: P(x) Q(y) R(x,y)、 P(a) 、 S(z) R(a,z)、 S(b) 、 Q(b) 。,2020/9/4,计算机学院,70/112,(x) (y)( P(x) Q(y) R(x,y) (u)(P(u) (z)( S(z) R(u,z) (v)(S(v) Q(v) (
46、u) (v) (x) (y) (z) (P(x) Q(y) R(x,y) P(u) ( S(z) R(u,z) S(v) Q(v) (x) (y) (z) (P(x) Q(y) R(x,y) P(a) ( S(z) R(a,z) S(b) Q(b) 上面即为Skolem范式,由此得到子句集: P(x) Q(y) R(x,y)、 P(a) 、 S(z) R(a,z)、 S(b) 、 Q(b) 。,2020/9/4,计算机学院,71/112,(x) (y)( P(x) Q(y) R(x,y) (u)(P(u) (z)( S(z) R(u,z) (v)(S(v) Q(v) (u) (v) (x) (
47、y) (z) (P(x) Q(y) R(x,y) P(u) ( S(z) R(u,z) S(v) Q(v) (x) (y) (z) (P(x) Q(y) R(x,y) P(a) ( S(z) R(a,z) S(b) Q(b) 上面即为Skolem范式,由此得到子句集: P(x) Q(y) R(x,y)、 P(a) 、 S(z) R(a,z)、 S(b) 、 Q(b) 。,2020/9/4,计算机学院,72/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b)
48、 (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,73/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,74/112,然后,
49、在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,75/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4
50、),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,76/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,77/112,然后,在此基础上利用代换进行消解的过程如下
51、: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,78/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R
52、(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,79/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕,2020/9/4,计算机学院,80/112,然后,在此基础上利用代换进行消解的过程如下: (1) P(x) Q(y) R(
53、x,y) (2) P(a) (3) Q(y) R(a,y) (1)和(2),代换a/x (4) Q(b) (5) R(a,b) (3)和(4),代换b/y (6) S(z) R(a,z) (7) S(b) (5)和(6),代换b/z (8) S(b) (9) 证毕 ((7)和(8),2020/9/4,计算机学院,81/112,小结:谓词演算的综合推理方法,一、基本推理方法 1、直接证明方法 2、间接证明方法(反证法) 3、利用CP规则 二、推理中需注意的几个问题 1)当所要求的结论可能被定量时,此时可引用规则UG和规则EG将其量词加入。 2)在推导过程中,如既要使用规则US又要使用规则ES消去
54、公式中的量词(要先使用规则ES,再使用规则US)。然后再使用命题演算中的推理规则,最后使用规则UG或规则EG引入量词,得到所要的结论。,2020/9/4,计算机学院,82/112,3)如一个变量是用规则ES消去量词,对该变量在添加量词时,则只能使用规则EG,而不能使用规则UG;如使用规则US消去量词,对该变量在添加量词时,则可使用规则EG和规则UG。 4)如有两个含有存在量词的公式,当用规则ES消去量词时,不能选用同样的一个常量符号来取代两个公式中的变元,而应用不同的常量符号来取代它们。,2020/9/4,计算机学院,83/112,5)在用规则US和规则ES消去量词时,此量词必须位于整个公式的
55、最前端,并且它的辖域为其后的整个公式。 6)在添加量词(x)、(x)时,所选用的x不能在公式G(c)或G(y)中以任何约束出现。 7) 在使用EG规则引入存在量词(x),此x不得为G(c)或G(y)中的函数变元。在使用UG规则引入全称量词(x)时,此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。,2020/9/4,计算机学院,84/112,例5-6,将下列三条自然公理翻译成谓词公式: 每个自然数有且仅有一个直接后继; 没有任何自然数以0为其直接后继; 对0以外的任何自然数,有且仅有一个直接先行。 解:设个体域D为自然数 令p(x):x的直接先行; s(x):x的直接后继; EQ
56、UAL(x,y):x=y (x)(y)EQUAL(y,s(x) (z)EQUAL(z,s(x)EQUAL(y,z),有,且仅有,2020/9/4,计算机学院,85/112,(x)EQUAL(0,s(x) (x)EQUAL(x,0) (y)EQUAL(y,p(x)(z)EQUAL(z,p(x) EQUAL(y,z),0以外的任何自然数,2020/9/4,计算机学院,86/112,例5-7,解:设H(x):x是人; M(x):x是要死的; s:苏格拉底。 则符号化为:(x)(H(x)M(x),H(s) M(s),证明:“所有的人都是要死的;苏格拉底是人。所以苏格拉底是要死的。”,证明:(1)(x)(H(x)M(x)P (2)H(x)M(x)US,(1) (3)H(s)P (4)M(s)T,(2),(3),I,证明:(1)(x)(H(x)M(x)P (2)H(s)M(s)US,(1) (3)H(s)P (4)M(s)T,(2),(3),I,(2)错了! 正确的为?,2020/9/4,计算机学院,87/112,例5-8,证明: (x)(P(x)Q(x),(x)P(x)(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 后勤提升培训课件
- 黄气球绘本课件
- 2026及未来5年有机压榨大豆油项目可行性研究报告(市场调查与数据分析)
- 2026事业单位工勤技能-北京-北京工程测量员四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-内蒙古-内蒙古防疫员三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-内蒙古-内蒙古医技工五级(初级工)历年参考题库含答案详解
- 2026事业单位工勤技能-上海-上海造林管护工五级(初级工)历年参考题库含答案详解
- 2026事业单位工勤技能-上海-上海保育员四级(中级工)历年参考题库含答案详解
- 2026中级会计-中级会计实务(官方)-第五章长期股权投资参考试题库历年考点答案详解
- 初中数学教资面试试讲历年真题题库及参考答案
- 二十届五中全会客观测试题及答案解析
- GB/T 48188.2-2026光伏系统用额定电压1.5 kV直流电缆第2部分:铝合金导体电缆
- 2027中国华能校园招聘考试模拟试题及答案解析
- JJF(苏) 317-2026 差压式流量计(气体)在线校准规范
- 新版小学道德与法治新部编版六年级上册全册教案(2026秋版)合集
- 2027届初三中考全年备考统筹实施方案
- 重卡充电站项目可行性研究报告
- 2026年青海中考(地生会考)真题(含答案)
- 2025年浙江省杭州市余杭区事业单位招聘考试真题及答案(回忆版)
- DL 5106-2017 跨越电力线路架线施工规程
- 2026年体育单招真题卷全套及答案
评论
0/150
提交评论