数论谓词逻辑

1、苏格拉底三段论n例 逻辑学中著名的苏格拉底三段论：凡人都是要死的.苏格拉底是人.所以苏格拉底是要死的.n下面在命题逻辑中判断此推理的有效性 p：凡人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的 则推理的形式为 pqrpqrn显然推理形式结构不是重言蕴涵式（赋值110上面的公式便为假）. n这个正确的推理在命题逻辑中却无法表示推理过程. . 从而反映出命题逻辑的局限性. .究其根源，在命题逻辑中，把简单命题看作是最基本单位，它是独立的，没有考虑到命题之间的内在联系. n其实简单命题之间往往是有联系的，常常有一些共同的特性，要反映出它们，需对简单命题进行剖析，刻划其内部结构,再研究它们之间的

2、逻辑关系，给出正确的推理形式和规则.n推理正确不仅取决于各命题之间,更与命题的内部逻辑结构有关,为此引入一阶逻辑. 第二章一阶逻辑（谓词逻辑）一阶逻辑n一阶逻辑的基本概念n一阶逻辑公式及解释n一阶逻辑等值式n前束范式n一阶逻辑的推理理论一阶逻辑的基本概念一阶逻辑一阶逻辑命题符号化体系命题符号化体系 个体词、个体词、谓词谓词、量词量词和和逻辑联结词逻辑联结词个体词n可以独立存在的客体称为个体词（它可以是抽象的概念，也可以是具体的事物）.n如 学生、桌子、自然数、唯物主义等都可以做为个体词.个体词n将表示具体或特定的个体词称为个体常项，一般用a,b,c,等表示.n将表示抽象或泛指的个体词称为个体变

3、项，一般用x,y,z, 等表示.n个体变项的取值范围称为个体域（论域）,记为D.它可以是有穷集合，也可以是无穷集合.n特别地，将宇宙间一切事物组成的个体域称为全总个体域.n如无特殊说明个体域，个体域均指全总个体域.谓词n用来刻划个体词的性质及个体词之间关系的词称为谓词n将表示具体性质或关系的谓词称为谓词常项，一般用F,G,H,等表示.n将表示抽象或泛指的谓词称为谓词变项，一般也用F,G,H,等表示.n我们把用谓词字母后填以个体词,用F(x)表示x具有性质F，用L(a, b) 表示a与b具有关系L ，n例 F(x): x是奇数, a:, b:7. F(a): 9是奇数,F(b): 7是奇数.nH

4、(x,y): x 大于y, a:3 ,b:2. H(a, b): 3大于2.nL(x,y): x比y聪明, a:刘刚, b:张立. L(a,b):刘刚比张立聪明.n令L(x,y,z): x在y与z之间, a:电话, b:台灯,c :笔筒.L(a, b,c): 电话在台灯与笔筒之间谓词n谓词中所含个体变项的个数称为谓词的元数. 含n个个体变项的谓词，称为n元谓词,记为P(x1,x2,xn).nn元谓词是定义在个体域上，以1,0为值域的n元函数.n一般地，一元谓词描述个体词的性质，二元或多元谓词描述两个或多个个体词间的关系. 例F(x)表示x具有性质F； L(x,y)表示x与y具有关系Ln要使P(

5、x1,x2,xn) 成为命题，P必须用谓词常项取代， x1,x2,xn用n个体常项取代，有时将不带个体变项的谓词称为0元谓词,命题逻辑中的命题常项可用0元谓词表示,可视为谓词的特殊情形这样，一阶逻辑可视为命题逻辑的扩张.n令G(x,y)： “x高于y”，于是，G(x,y)是一个二元谓词. a：张三， b：李四，则G(a ,b)就是命题： “张三高于李四” . 但是，G(x,y)不是命题，而是一个命题函数.例n将下列命题在一阶逻辑中用谓词符号化n(1)宋祖英是女歌唱家n(2)若大于且大于，则大于n解 (1)令 F(x)：x是女人, G(y) ：y是歌唱家, a ：宋祖英, (1)符号化为F(a)

6、G(a).n (2) 令G(x,y) ：x大于y , a ：6, b：4, c:2, (2)符号化为G(a, b)G(b, c)G(a, c).量词n例 将下列命题在一阶逻辑中符号化 所有人都呼吸. 有的人吸烟.n在谓词逻辑中用个体词和谓词还不足以准确描述命题，还需要引进表示数量的词.n表示数量的词称为量词.n量词分为全称量词和存在量词.量词n全称量词全称量词 对应语言 “一切”，“所有的”，“任意的”，“每一个” . 用符号表示全称量词 ，用x表示个体域中所有个体，用xF(x)表示个体域中所有个体具有性质F . n存在量词存在量词 对应语言 “存在着”，“有一个”，“至少有一个”，用符号表示

7、存在量词，用x表示存在个体域中的个体， xF(x)表示存在个体域中的个体具有性质F . 使用量词将命题符号化与个体域有关n例 （1）所有人都呼吸. （2）有的人吸烟.n个体域为人类集合 （1）符号化为xF(x) ，其中F(x)：x呼吸（真命题 ） （2）符号化为xG(x) ， 其中G(x)：x吸烟（真命题 ）n个体域为全总个体域. 设M(x)：x是人； F(x)：x呼吸； G(x)：x吸烟 （1）符号化为x(M(x)F(x)， （真命题 ） （2）符号化为x(M(x)G(x) ， （真命题 ）nM(x)称为特性谓词 在一阶逻辑中使用量词应注意的问题n在不同的个体域中，命题的符号化形式可能不同，

8、命题的真值也可能会改变. 如 xG(x),其中G(x):x+9=6 ,当个体域取自然数集时真值为；当个体域取实数集时真值为.n在考虑命题的符号化时，如果对个体域未做声明，一律使用全总个体域.n多个量词同时出现时，不能随意改变它们的次序，否则将改变原命题的涵义. 如令H(x,y):xy ,D:R , xyH(x,y) 1 yxH(x,y) 0在一阶逻辑中将命题符号化n(1)对于任意的x，均有x-1=(x-1)(x+1) (2)存在x ，使得x+6=4. 要求:个体域为自然数集N 个体域为实数集Rn解 个体域为自然数集N (1) xF(x)，其中F(x)： x-1 =(x-1)(x+1) 1 (2

9、) xG(x)，其中(x)： x+6=4 0个体域为实数集R (1) xF(x)，其中F(x)：x-1 =(x-1)(x+1)1 (2) xG(x)，其中(x)： x+6=4 1在一阶逻辑中将命题符号化n(1)并非每个实数都是有理数 (2)没有不犯错误的人 (3)参加考试的人未必都能取得好成绩 (4)尽管有人聪明，但未必一切人都聪明n解 个体域取全总个体域 (1) x(R(x)Q(x) 或x(R(x)Q(x) 其中R(x): x是实数, Q(x): x是有理数 (2) x(M(x)F(x)或x(M(x)F(x) 其中M(x): x是人, F(x): x犯错误(3)参加考试的人未必都能取得好成绩

10、(4)尽管有人聪明，但未必一切人都聪明(3) x(F(x)G(x)或x(F(x)G(x) 其中F(x): x是参加考试的人, G(x): x取得好成绩.(4) x(M(x)P(x) x(M(x)P(x) 其中M(x): x是人, P(x): x聪明在一阶逻辑中将命题符号化n(1)兔子比乌龟跑得快 (2)有的兔子比所有的乌龟跑得快 (3)并非所有的兔子比所有的乌龟跑得快 (4)不存在同样高的两个人n解个体域取全总个体域 设F(x): x是兔子, G(y):y是乌龟， H(x,y): x比y跑得快. (1) xy(F(x)G(y)H(x,y) (2) x(F(x)y(G(y)H(x,y) (3)x

11、y(F(x)G(y)H(x,y)或xy(F(x)G(y)H(x,y) (4)设M(x): x是人, L(x,y): xy， P(x,y): x与y一样高. xy(M(x)M(y)L(x,y)P(x,y) 或xy(M(x)M(y)L(x,y) P(x,y)一阶逻辑公式及解释一阶逻辑中的字母表n个体常项：a,b,c, ,ai,bi,ci,i1n个体变项：x,y,z, , xi,yi,zi, , i1n函数符号：f,g,h, , fi,gi,hi ,i1n谓词符号：F,G,H,Fi,Gi,Hi, ,i1n量词符号： , n联结词：, ,n括号与逗号： ( )与 ,项n定义定义 (1)个体常项和个体变

12、项是项； (2)若(x1,x2,xn)是任意n元函数， t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.n(3)只有有限次使用(1),(2)生成的符号串才是项. 原子公式n定义定义 设P(x1,x2,xn)是任意n元谓词， t1,t2,tn是任意的n个项，则称P(t1,t2,tn)为原子公式.n例F(x)，G(y)，H(x,y)，(x,a+2y)都是原子公式谓词合式公式（一阶逻辑公式）n定义定义 (1)原子公式是合式公式； (2)若A是合式公式，则(A)是合式公式； (3)若A，B是合式公式，则 (AB) ，(AB) ，(AB) ，(AB)是合式公式； (4)若A是合式公式，则xA

13、 ，xA是合式公式. (5)当且仅当能够有限次地应用(1)(4)生成的符号串才是合式公式.n注:(1)（AB）,（AB） ,（AB） ,（AB） 外面的括号可省去. (2) 谓词合式公式也称一阶逻辑公式，简称为公式.辖域、指导变项、自由变项、约束变项n定义定义 在公式xA和xA中，称x为指导变项，A为相应量词的辖域， 在x和x的辖域中，x的所有出现都称为约束出现， A中不是约束出现的其它变项均称为自由出现的.n公式x(P(x,y)Q(x,z)R(x)从左向右算起，变项x的第一，第二次出现是约束的，第三次出现是自由的；变项y，z的出现是自由的.n公式x(F(x,y,z)yG(x,y)从左向右算起

14、，变项y的第一次出现是自由的，第二次出现是约束的；变项x的出现都是约束的.n用A(x)等表示x是自由出现的任意公式如A(x)=zy F(x,y,z)yG(x,y) B(y)=x(F(x,y)G(y) A(x,y)=zF(x,y,z)G(x,y) nA(x)等前加上量词后， A(x)中的x就变成约束出现的nxA(x)，xA(x)中的量词去掉，A(x)中的x就又变成自由出现的了 闭式n定义定义设A为任意公式，若A中无自由出现的个体变项，则称A为封闭式公式，简称闭式n如 xy (F(x)G(y)H(x,y)为闭式 谓词公式的解释n定义定义 一个解释I由4部分组成：n(1)非空个体域D;n(2) D中

15、一部分特定元素；n(3) D上一些特定的函数；n(4) D上一些特定的谓词.例n给定一个解释I如下：(1) 个体域为自然数集N;(2)个体常项a=0；(3)函数f(x,y)=x+y , g(x,y)=xy ；(4)谓词F(x,y) 为x=y.在解释I下，研究下列各公式(1)xy (F(f(x,a),y)F(f(y,a),x)(2) xy (F(f(x,y), g(x,y) (3) F(f(x,y), f(y,z) (4) F(g(x,y), g(y,x)n在解释I下,公式分别为 (1)xy (x+0=yy+0=x) 真命题 (2) xy (x+y=xy) 假命题 (3) x+y=y+z 真值不

16、确定，不是命题 (4) xy=yx 真命题n有的公式在具体解释下真值确定，即变成命题；有的公式在具体解释下真值仍不能确定，因而仍然不是命题.n闭式在任何解释下都成为命题.n不是闭式的公式在某一解释下，也可能成为命题.谓词公式的类型n定义定义 设A为一谓词公式。n若A在它的所有解释下均为真，则称A为永真式（或有效式）；n若A在它的所有赋值下均为假，则称A为矛盾式（或永假式）；n如A不是矛盾式，则称A为可满足式.谓词公式的分类n谓词公式矛盾式非永真式的可满足式永真式可满足式代换实例n定义定义 设A0是含n个命题变项p1 , p2 , , pn的命题公式，用谓词公式Ai(1in)处处取代A0中的pi

17、，所得公式A称为A0的代换实例.n重言式的代换实例是永真式.n矛盾式的代换实例是矛盾式.判断下列公式的类型n(1)xF(x)(xyG(x,y)xF(x) (2) (xF(x,y)yG(y) yG(y) (3) xF(x)xF(x) (4) x(F(x)G(x)yF(y)n(1)为p(qp)的代换实例，p(qp)为重言式，故(1)是永真式 (2)为(pq)q的代换实例，(pq)q为矛盾式，故(2)是矛盾式 (3) 当xF(x)为真时，xF(x)为真，故(3)是永真式(4)取解释I：个体域为自然数集N; F(x)：x是偶数G(x) ：x是素数这时(4)为假取解释I：个体域为实数集R; F(x)：x

18、是正数G(x) ：x是负数这时(4)为真故(4)为非永真式的可满足式第五章一阶逻辑等值式一阶逻辑等值式n定义定义 设A、B为一阶逻辑公式， 若AB是永真式，则称A与B是等值的，记作AB ，称AB为等值式.一阶逻辑等值式n命题逻辑中的基本等值式的代换实例都是一阶逻辑等值式.n例 xF(x)xF(x)xF(x) xF(x)xF(x)0 xF(x)xF(x) 1 (xF(x)yG(y) xF(x)yG(y)一阶逻辑基本等值式n在有限域D=a1,a2,an中消去量词等值式.(1) xA(x)A(a1)A(a2)A(an)(2) xA(x)A(a1)A(a2)A(an)一阶逻辑基本等值式n量词否定等值式

19、 (1) xA(x)xA(x) (2) xA(x)xA(x)一阶逻辑基本等值式 n量词辖域收缩与扩张等值式 x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x) BxA(x) 其中B中不出现约束变项x一阶逻辑基本等值式n量词辖域收缩与扩张等值式 x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x) BxA(x) 其中B中不出现约束变项x一阶逻辑基本等值式n量词分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x)n注意：nx(A(x)B(x)xA(x)

20、xB(x)不成立 解释I D: N，A(x):x是奇数，B(x):x是偶数. x(A(x)B(x) xA(x)xB(x) 1 0 x(A(x)B(x)xA(x)xB(x)不成立n解释I D: R, A(x):x是正数，B(x):x是负数 x(A(x)B(x) xA(x)xB(x) 0 1置换规则n置换规则 设(A)是含公式A的谓词公式， BA则可用B置换(A)中的A ，得(B) ，保证(A) (B) .n在一个公式中，同一个个体变项可以既是自由出现的又是约束出现的，这样容易引起混淆，为研究问题带来不便，我们希望一个个体变项在一个公式中以一种身份出现为此引入下面两条规则约束变项换名规则n约束变项

21、换名规则 n(1) 在A公式中,将某量词的指导变项,以及该量词辖域中所出现的所有该约束变项都用新的个体变项替换,其余部分不变.n(2)新的个体变项在该辖域中不出现.n(3)所得公式与原公式A等值例n对于x(P(x,y)Q(x,z)G(x) ，可换名为 u(P(u,y)Q(u,z)G(x) n但下面的改名都是不对的 u(P(u,y)Q(x,z)G(x) x(P(u,y)Q(u,z)G(x) u(P(x,y)Q(x,z)G(x) y(P(y,y)Q(y,z)G(x) u(P(u,y)Q(u,z)G(u) 自由变项代替规则n自由变项代替规则 n(1) 将A公式中某一自由出现的所有个体变项都用新的个体

22、变项代替,其余部分不变.n(2)新的个体变项在原公式A中不出现.n(3)所得公式与原公式A等值例n对于xH(x,y)yG(y)L(y,z) ，可代替为 xH(x,u)yG(y)L(u,z) n但下面的代替都是不对的 xH(x,u)yG(u)L(u,z) xH(x,z)yG(y) )L(z,z) xH(x,u)yG(y) )L(y,z) n利用约束变项换名规则和自由变项代替规则可使同一个体变项在一个公式中以一种身份出现n在一阶逻辑等值演算过程中，需不断使用置换规则,约束变项换名规则和自由变项代替规则.例n设个体域D=a,b,c，消去下列公式中的量词. (1)xF(x)yG(y) (2) x(F(

23、x)yG(y) (3) xy(F(x)G(y) n解(1)xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c) (2) x(F(x)yG(y) xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c)(3) xy(F(x)G(y) x(F(x)yG(y) xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c)例证明(1) x(F(x)G(x)x(F(x)G(x)(2)xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y) n证(1) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x)

24、n(2) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy( F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y)n与命题逻辑一样，在一阶逻辑中，我们给出一阶逻辑公式的规范形式，即前束范式前束范式前束范式n定义 设A为一阶逻辑公式， 若A具有如下形式 Q1x1QnxnB 则称A为前束范式. 其中 Qi或者是，或者是，i=1，n，B是不含量词的公式.n例如xyz(P(x,y)H(x,z) xyzP(x,y,z)定理n定理2.1 对任意一阶逻辑公式都存在与其等值的前束范式（但形式不唯一）. .求前束范式的方法n主要利用基本等值式、约束变量换名规则、自由变量代

25、替规则等进行等值演算.n一阶逻辑公式的前束范式形式不唯一.这与命题逻辑中的主析取范式和主合取范式不同n一个公式的前束范式中，各个指导变项应该不同，原来自由出现的个体变项还应该是自由出现的，且自由出现的次数不变例求公式(1) xF(x)xG(x)(2) xF(x)xG(x)的前束范式n解 (1) xF(x)xG(x) xF(x)xG(x) 量词否定等值式 x(F(x)G(x)量词分配等值式n(2) xF(x)xG(x) xF(x)xG(x)量词否定等值式 yF(y)xG(x)约束变项换名规则 yx (F(y)G(x)量词收缩扩张等值式 yx (G(x)F(y)例n求公式(x(F(x,y)yG(x

26、,y) 的前束范式.n解 (x(F(x,y)yG(x,y) xF(x,y)yG(x,y) xF(x,y)yG(x,y) 量词否定等值式 uF(u,y)vG(x,v) 约束变项换名规则 u(F(u,y)vG(x,v) 量词收缩扩张等值式 uv(F(u,y)G(x,v) 量词收缩扩张等值式例n求公式 x(F(x)yG(x,y,z)zH(x,y,z) 的前束范式.n解 x(F(x)yG(x,y,z)zH(x,y,z)x(F(x)yG(x,y,u)zH(v,w,z) 自由变项代替规则xy(F(x)G(x,y,u)zH(v,w,z) 量词收缩扩张等值式xyz(F(x)G(x,y,u)H(v,w,z) 量

27、词收缩扩张等值式一阶逻辑的推理理论推理的形式结构n定义定义 称蕴涵式 (A1A2Ak)B 为一阶逻辑推理的形式结构. A1, A2 , , Ak为推理的前提， B为推理的结论. 若(A1A2Ak)B为永真式，则称从前提A1, A2 , , Ak推出结论B的推理有效， B是A1, A2 , , Ak的逻辑结论.其中A1, A2 , , Ak,， B为谓词公式.n判断(A1A2Ak)B为永真式比命题逻辑困难，判断推理是否有效主要靠形式证明的方法.n一阶逻辑的推理方法可看作是命题逻辑方法的扩张，因为作为扩大的系统，命题逻辑是包含在一阶逻辑之中的，所以命题逻辑的推理定律，推理规则可在一阶逻辑中应用推理

28、定律（永真蕴涵式）n命题逻辑中推理定律的代换实例.例 (xF(x)yG(y)xF(x) yG(y) xF(x)yG(y) xF(x)n每个基本等值式均产生两个推理定律.例 (xF(x)yG(y)xF(x)yG(y) xF(x)yG(y)(xF(x)yG(y)推理定律n量词分配的推理定律 xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x)推理规则n规则P(前提引入规则)：在证明的任何步骤上都可以引用前提.n规则T(结论引入规则)：在证明的任何步骤上所得到的结论都可作为后续证明的前提. (置换规则,附加，化简,合取，假言推理, 拒取式 ,析取三段论,假言三段论,等价

29、三段论 ,构造性二难等.)n在一阶逻辑中，某些前提与结论可能受量词的制约，必须在推理过程中有消去和添加量词的规则，以使证明能如命题逻辑中那样进行n除与命题逻辑相同的推理规则外，一阶逻辑还有下面关于量词4条消去和添加量词的推理规则.使用这4条规则时必须注意条件.推理规则 n全称量词消去规则（UI规则） xA(x)A(y) xA(x)A(c)nUI规则成立的条件：(1) x为A(x)中自由出现的个体变项；(2)第一式中的y是任意的不在A(x)中约束出现的个体变项；(3)第二式中的c是任意的个体常项.n例 D: R F(x,y): xy A(x)=yF(x,y) xA(x)yF(z,y)n xA(x

30、)yF(y,y)错误原因违背(2). 推理规则n全称量词引入规则（UG规则） A(y)xA(x)nUG规则成立的条件： (1) y在A(y)中自由出现，且y取个体域中任何值时，A均为真. (2)取代y的x不能在A(y)中约束出现. n例 D: R F(x,y): xy A(y)=xF(x,y) A(y)zxF(x,z) A(y)xxF(x,x) 错误原因违背(2).推理规则n存在量词引入规则（EG规则）n A(c)xA(x) nEG规则成立的条件：(1) c是使A为真的特定的个体常项. (2)取代c的x不能已在A(c)中出现过. n例 D: R F(x,y): xy A(3)=xF(x,3)

31、A(3)yxF(x, y) n A(3)xxF(x, x) 错误原因违背(2).推理规则n存在量词消去规则（EI规则）n xA(x)A(c)nEI规则成立的条件：(1) c是使A为真的特定的个体常项. (2) c不在A(x)中出现过. (3) A(x)中除x外，不能有另外的自由出现的个体变项. 例 指出下面推理中的错误n(1) x(F(x)G(x) 前提引入n(2) F(c)G(c) (1)EIn(3) F(c) (2)化简 n(4) y(H(y)I(y) 前提引入n(5) H(c)I(c) (4)EIn(6) H(c) (5)化简 n(7) F(c)H(c) (3)(6)合取n(8) x(F

32、(x)H(x) (7)EG例 指出下面推理中的错误n1. (1) xy(xy) 前提引入n (2) y(zy) (1)UIn (3) zc (2)EIn (4) x(xc) (3)UGn2. (1) xF(x)G(x) 前提引入n (2) F(y)G(y) (1)UI例 指出下面推理中的错误n(1) x(F(x)G(x) 前提引入n(2) F(c)G(c) (1)UI n(3) x(F(x)H(x) 前提引入n(4) F(c)H(c) (3)EIn(5) F(c) (4)化简n(6) G(c) (2)(5)假言推理n(7) H(c) (4)化简n(8) G(c)H(c) (6)(7)合取n(9

33、) x(G(x)H(x) (8)EG使用以上这4条规则时必须注意n必须对辖域为整个公式的量词使用它们,不能对出现在公式中的量词使用它们.故在构造推理证明时,若要应用EI规则和UI规则消去量词,应首先将含量词公式化为前束范式.nEI规则中得到的c一定满足UI规则中的条件,但反之不真.一阶逻辑自然推理系统的构成n一阶逻辑字母表n一阶逻辑合式公式n一阶逻辑推理规则例 在一阶逻辑中构造下面推理的证明前提: x(F(x)H(x), x(G(x)H(x)结论: x(G(x)F(x)n证明(1) x(F(x)H(x)前提引入(2) x(F(x)H(x) (1)置换(3) x(H(x)F(x) (2)置换(4

34、) H(y)F(y) (3)UI(5) x(G(x)H(x)前提引入(6) G(y)H(y)(5)UI(7) G(y)F(y) (6)(4)假言三段论(8) x(G(x)F(x)(7) UG 例 在一阶逻辑中证明苏格拉底三段论:“凡人都是要死的.苏格拉底是人. 所以苏格拉底是要死的.”n取全总个体域 设F(x):x是人, G(x):x是要死的,a:苏格拉底.n前提: x(F(x)G(x), F(a) 结论: G(a).n证明 (1) x(F(x)G(x) 前提引入 (2) F(a)G(a) (1)UI (3) F(a) 前提引入 (4) G(a) (2)(3)假言推理 例 在一阶逻辑中构造下面

35、推理的证明n有些病人相信所有的医生.但是病人都不相信骗子.所以医生都不是骗子.n取全总个体域 设F(x):x是病人, G(x): x是医生, H(x):x是骗子, L(x,y):x相信y.n前提: x(F(x)y(G(y)L(x,y), x(F(x)y(H(y)L(x,y) 结论: x(G(x)H(x)前提: x(F(x)y(G(y)L(x,y), x(F(x)y(H(y)L(x,y)结论: x(G(x)H(x)n证明(1) x(F(x)y(G(y)L(x,y) 前提引入(2) F(c)y(G(y)L(c,y) (1)EI(3) F(c) (2)化简(4) y(G(y)L(c,y) (2)化简(5) x(F(x)y(H(y)L(x,y) 前提引入(6) F(c)y(H(y)L(c,y) (5)UI(7) y(H(y)L(c,y) (3)(6)假言推理(8) y(L(c,y)H(y) (7)置换(9) G(z)L(c,z) (4) UI(10) L(c,z)H(z) (8) UI(11) G(z)H(z) (9)(10)假言