一阶逻辑推理理论

1、离散数学离散数学第第1010课课一阶逻辑推理理论一阶逻辑推理理论内容回顾一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑等值式及前束范式一阶逻辑等值式及前束范式上节课练习：求下列公式的前束范式上节课练习：求下列公式的前束范式( ( xF(x,y)xF(x,y) yG(x,y)yG(x,y) xF(x,y) y G(x,y) x F(x,y) y G(x,y) x F(x,t) y G(s,y) x( F(x,t) y G(s,y) x y( F(x,t) G(s,y)今日内容一阶逻辑推理理论一阶逻辑推理理论推理形式的定义推理形式的定义量词引入和消去规则量词引入和消去规则一阶逻辑下的推理证明

2、一阶逻辑下的推理证明 一阶逻辑推理理论一阶逻辑推理理论在一阶逻辑中，推理的形式结构仍为在一阶逻辑中，推理的形式结构仍为 A1A2AkB 若该式是永真式，则称推理正确，称若该式是永真式，则称推理正确，称B是是A1，A2，Ak的逻辑结论的逻辑结论 此时将该式记为此时将该式记为 A1A2Ak B命题逻辑中的推理规则及在一阶逻辑中的命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑中仍然成立代换实例，在一阶逻辑中仍然成立一阶逻辑中新增加一阶逻辑中新增加4条推理规则条推理规则 消去和引入规则消去和引入规则:全称量词消去规则全称量词消去规则全称量词引入规则全称量词引入规则存在量词引入规则存在量词引入

3、规则存在量词消去规则存在量词消去规则全称量词消去规则全称量词消去规则（简称（简称UI规则规则）这条规则含以下两种形式：这条规则含以下两种形式： xA(x) A(y) xA(x) A(c) 两式成立的条件两式成立的条件是是1.x是是A(x)中自由出现的个体变项；中自由出现的个体变项；2.在在式中，式中，y为任意的不在为任意的不在A(x)中约束出现中约束出现的个体变项；的个体变项；3.在在式中，式中，c为个体域中任意的个体常项。为个体域中任意的个体常项。 只有在满足上述条件时，推理规则才成立！只有在满足上述条件时，推理规则才成立！在推理过程中在推理过程中 ，两种形式可根据需要选两种形式可根据需要选

4、用。用。例：例：设定义域为实数，取设定义域为实数，取F(x,y)F(x,y)为为x xy y， A(x)=A(x)= yF(x,y)yF(x,y)， xA(x) xA(x) x x yF(x,y) yF(x,y) 公式公式 xA(x)xA(x)是真命题。是真命题。考虑如下推理是否正确考虑如下推理是否正确 : : x x yF(yF(x x,y) ,y) 前提引入前提引入 yF(yF(y y,y) ,y) UIUI规则规则 yF(y,y)yF(y,y)是假命题，是假命题，推理不正确推理不正确 出错的原因是违背了条件：出错的原因是违背了条件： xA(x) xA(x) A(y)A(y)中，中， y

5、y应为任意的不在应为任意的不在A(x)A(x)中约束中约束出现的个体变项。出现的个体变项。 全称量词引入规则全称量词引入规则（简称（简称UGUG规则规则） A(y) A(y) xA(x) xA(x) 公式成立的条件公式成立的条件是是 1.y1.y在在A(y)A(y)中自由出现，且中自由出现，且y y取取任何值任何值时时A A均为均为真真 2.2.取代取代y y的的x x不在不在A(y)A(y)中约束出现。中约束出现。 例例: :设定义域为实数，设定义域为实数， 取取F(x,y)F(x,y)为为xyxy，A(y)=A(y)= xF(x,y)=xF(x,y)= x(xy)x(xy)， A A对任意

6、给定的对任意给定的y y都是真的。都是真的。如下推理是否正确如下推理是否正确 : : xF(x,y) xF(x,y) 前提引入前提引入 x x xF(x,x) xF(x,x) UG UG x x x(xx)x(xx)是假命题，推理出错。是假命题，推理出错。 出错的原因是违背了条件出错的原因是违背了条件2 2：取代：取代y y的的x x不在不在A(y)A(y)中约束出现中约束出现 z xF(x,z) UGUG 存在量词引入规则存在量词引入规则（简称（简称EGEG规则规则） A(c) A(c) xA(x) xA(x) 公式成立的条件公式成立的条件是是 1.c1.c是特定的个体常项是特定的个体常项

7、； 2.2.取代取代c c的的x x不能已在不能已在A(c)A(c)中出现过中出现过 。 例例1:1:设定义域为实数，设定义域为实数，取取F(x,y)F(x,y)为为x xy y， A(2)=A(2)= xF(x,2)= xF(x,2)= x(x2)x(x2)，（，（真命题）真命题）如下推理是否正确如下推理是否正确 : : xF(x,2) xF(x,2) 前提引入前提引入 x x xF(x,x) xF(x,x) EG EG 假命题，推理出错。出错的原因是违背了假命题，推理出错。出错的原因是违背了条件条件2,x2,x已在已在A(2)A(2)中出现过。中出现过。 存在量词引入规则存在量词引入规则（

8、简称（简称EGEG规则规则） A(c) A(c) xA(x) xA(x) 公式成立的条件公式成立的条件是是 1.c1.c是特定的个体常项是特定的个体常项 ； 2.2.取代取代c c的的x x不能已在不能已在A(c)A(c)中出现过中出现过 。 例例1:1:设定义域为实数，设定义域为实数，取取F(x,y)F(x,y)为为x xy y， A(2)=A(2)= xF(x,2)= xF(x,2)= x(x2)x(x2)，（，（真命题）真命题）如下推理是否正确如下推理是否正确 : : xF(x,2) PxF(x,2) P y y xF(x,y) EG, xF(x,y) EG, 存在量词消去规则存在量词消

9、去规则（简称（简称EIEI规则规则） xA(x) xA(x) A(c) A(c) 公式成立的条件公式成立的条件是是 1.c1.c是使是使A A为真的特定的个体常项；为真的特定的个体常项； 2.c2.c不曾在不曾在A(x)A(x)中出现过；中出现过； 3.A(x)3.A(x)中除中除x x外没有其他自由出现的个体变项。外没有其他自由出现的个体变项。 例例: : 在自然数集中，设在自然数集中，设F(x)F(x)为为x x是奇数，是奇数，G(x)G(x)是是x x是偶数，则是偶数，则 xF(x)xF(x) xG(x)xG(x)是真命题是真命题. .以下推论以下推论是否正确：是否正确：(1) (1)

10、xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化简规则化简规则(3) (3) xG(x) (1)xG(x) (1)化简规则化简规则(4) F(a) (2)ES(4) F(a) (2)ES规则规则(5) G(a) (3)ES(5) G(a) (3)ES规则规则(6) F(a)G(a) (4)(5)(6) F(a)G(a) (4)(5)合取规则合取规则(7) (7) x(F(x)G(x) (6)EGx(F(x)G(x) (6)EG规则规则例例: : 在自然数集中，设在自然数集中，设F(x)F(x)为为x x是奇数，是奇数，G(x)

11、G(x)是是x x是偶数，则是偶数，则 xF(x)xF(x) xG(x)xG(x)是真命题是真命题. .以下推论以下推论是否正确：是否正确：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化简规则化简规则(3) (3) xG(x) (1)xG(x) (1)化简规则化简规则(4) F(a) (2)EI(4) F(a) (2)EI规则规则(5) G(a) (3)EI(5) G(a) (3)EI规则规则 (6) F(a)G(a) (4)(5)(6) F(a)G(a) (4)(5)合取规则合取规则(7) (7) x(F(

12、x)G(x) (6)EGx(F(x)G(x) (6)EG规则规则出错的原因是存在量词消去规则出错的原因是存在量词消去规则 xA(x) xA(x) A(c) A(c)时违背了条件：时违背了条件：c c是使是使A A为真的特定的个体常项为真的特定的个体常项例例: : 在自然数集中，设在自然数集中，设F(x)F(x)为为x x是奇数，是奇数，G(x)G(x)是是x x是偶数，则是偶数，则 xF(x)xF(x) xG(x)xG(x)是真命题是真命题. . 以下推理以下推理是否正确：是否正确：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)

13、xF(x) (1)化简规则化简规则(3) (3) xG(x) (1)xG(x) (1)化简规则化简规则(4) F(a) (2)EI(4) F(a) (2)EI(5) G(b) (3)EI(5) G(b) (3)EI(6) F(a)G(b) (4)(5)(6) F(a)G(b) (4)(5)合取规则合取规则(7) (7) x(F(x)G(x) (6)EG x(F(x)G(x) (6)EG 例例: : 在自然数集中，设在自然数集中，设F(x)F(x)为为x x是奇数，是奇数，G(x)G(x)是是x x是偶数，则是偶数，则 xF(x)xF(x) xG(x)xG(x)是真命题是真命题. . 以下推理以

14、下推理是否正确：是否正确：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化简规则化简规则(3) (3) xG(x) (1)xG(x) (1)化简规则化简规则(4) F(a) (2)EI(4) F(a) (2)EI(5) G(b) (3)EI(5) G(b) (3)EI(6) F(a)G(b) (4)(5)(6) F(a)G(b) (4)(5)合取规则合取规则(7) (7) x(F(x)G(x) (6)EG x(F(x)G(x) (6)EG (7)(7) x(F(x)G(b) (6)EGx(F(x)G(b) (6

15、)EG(8)(8) x x y(F(x)G(y) (7)EGy(F(x)G(y) (7)EGv在应用以上在应用以上4 4条量词规则时，要特别注意！条量词规则时，要特别注意！ 一阶逻辑推理实例命题逻辑中的推理规则及在一阶逻辑中命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑推理中仍然使的代换实例，在一阶逻辑推理中仍然使用用量词消去和引入规则量词消去和引入规则例例1:1: 证明苏格拉底三段论证明苏格拉底三段论“凡人都是要死的。凡人都是要死的。苏格拉底是人苏格拉底是人. .所以苏格拉底是要死的。所以苏格拉底是要死的。”命题符号化命题符号化：F F（x x）：）：x x是人（是人（特性谓词特性

16、谓词）；）； G G（x x）：）：x x是要死的；是要死的； a a：苏格拉底：苏格拉底前提前提： x x（F(x)G(x)F(x)G(x)），），F(a)F(a)结论结论：G(a)G(a)证明证明：（1 1） x x（F(x)G(x)F(x)G(x)） 前提引入前提引入（2 2）F(a)G(a) UI(1)F(a)G(a) UI(1)（3 3）F(a) F(a) 前提引入前提引入（4 4）G(a) (2)(3)G(a) (2)(3)假言推理假言推理例例2:所有的有理数都是实数，有的有理数是整数。所有的有理数都是实数，有的有理数是整数。 所以，有的实数是整数。所以，有的实数是整数。 请在一阶

17、逻辑中证明上述推理的正确性。请在一阶逻辑中证明上述推理的正确性。 证明：证明： 命题符号化：命题符号化： F(x) ：x为有理数；为有理数； G(x) ：x为实数；为实数； H(x) ：x为整数为整数 前提前提: x ( F(x) G(x) ， x ( F(x) H(x) ) 结论结论: x ( G(x) H(x) ) 前提前提: x ( F(x) G(x) ， x ( F(x) H(x) ) 结论结论: x ( G(x) H(x) ) 证明：证明： x ( F(x) H(x) ) 前提引入前提引入 F（c） H(c) EI x ( F(x) G (x) ) 前提引入前提引入 F(c) G(c

18、) UI F(c) 化简化简 G(c) 假言推理假言推理 H(c) 化简化简 G(c) H(c) 合取合取 x ( G(x) H(x) ) EG将证明的步骤改为：将证明的步骤改为：证明：证明： x ( F(x) G (x) ) 前提引入前提引入 F(c) G(c) UI x ( F(x) H(x) ) 前提引入前提引入 F（c） H(c) EI F(c) 化简化简 G(c) 假言推理假言推理 H(c) 化简化简 G(c) H(c) 合取合取 x ( G(x) H(x) ) EG哪步存在错误？哪步存在错误？例例3 :请在一阶逻辑中证明下述推理的正确请在一阶逻辑中证明下述推理的正确性。性。不存在能

19、表示出分数的无理数，有理数都能表不存在能表示出分数的无理数，有理数都能表示成分数，因此，有理数都不是无理数。示成分数，因此，有理数都不是无理数。 解：解：命题符号化：命题符号化： 设设 F(x):x为无理数；为无理数；G(x):x为有理数；为有理数；H(x)：x能表示成分数。能表示成分数。 前提：前提： x(F(x)H(x), x(G(x)H(x) 结论：结论： x(G(x)F(x) 前提前提：x x（F(x)H(x)F(x)H(x)），）， x x（G(x)H(x)G(x)H(x)）结论结论： x x（G(x)G(x) F(x)F(x)）证明证明: :（1 1）x x（F(x)H(x)F(x

20、)H(x)） 前提引入前提引入（2 2） x x（ F(x)F(x) H(x)H(x)） (1)(1)置换规则置换规则（3 3） x x（H(x) H(x) F(x)F(x)） (2)(2)置换规则置换规则（4 4）H(y)H(y) F(y) UIF(y) UI（3 3）（5 5） x x（G(x)H(x)G(x)H(x)） 前提引入前提引入（6 6）G(y)H(y) UIG(y)H(y) UI（5 5）（7 7）G(y)G(y) F(y) (4)(6F(y) (4)(6）假言三段论）假言三段论（8 8） x x（G(x)G(x) F(x)F(x)） UGUG（7 7）课堂练习：课堂练习：前提：前提： x ( F(x) ( G(y) R(x) ) ) ， x F(x) 结论：结论： x ( F(x) R(x) ) 证明：证明： x F(x) 前提引入前提引入 F（c） EI x ( F(x) ( G(y) R(x) ) ) 前提引入前提引入 F(c) ( G(y) R(c) ) UI G(y) R(c) 假言推理假言推理 R(c) 化简化简 F(c