数论谓词逻辑

苏格拉底三段论例逻辑学中著名的苏格拉底三段论：凡人都是要死的.苏格拉底是人.所以苏格拉底是要死的.下面在命逻辑中判断此推理的有效性p：凡人都是要死的q：苏格拉底是人r：苏格拉底是要死的则推理的形式为pqrpqr显然推理形式结构不是重言蕴涵式（赋值110上面的公式便为假）.这个正确的推理在命题逻辑中却无法示推理过程.从而反映出命题逻辑的局限性.究其根源，在命题逻辑中，把简单命题看作是最基本单位，它是独立的，没有考虑到命题之间的内在联系.其实简单命题之间往往是有联系的，常常有一些共同的特性，要反映出它们，需对简单命题进行剖析，刻划其内部结构,再研究它们之间的逻辑关系，给出正确的推理形式和规则.推理正确不仅取决于各命题之间,更与命题的内部逻辑结构有关,为此引入一阶逻辑.第二章一阶逻辑（谓词逻辑）一阶逻辑一阶逻辑的基本概念一阶逻辑公式及解释一阶逻辑等值式前束范式一阶逻辑的推理理论一阶逻辑的基本概念一阶逻辑命题符号化体系个体词、谓词、量词和逻辑联结词个体词可以独立存在的客体称为个体词（它可以是抽象的概念，也可以是具体的事物）.如学生、桌子、自然数、唯物主义等都可以做为个体词.个体词将表示具体或特定的个体词称为个体常项，一般用a,b,c,…等表示.将表示抽象或泛指的个体词称为个体变项，一般用x,y,z,…等表示.个体变项的取值范围称为个体域（论域）,记为D.它可以是有穷集合，也可以是无穷集合.特别地，将宇宙间一切事物组成的个体域称为全总个体域.如无特殊说明个体域，个体域均指全总个体域.谓词用来刻划个体词的性质及个体词之间关系的词称为谓词．将表示具体性质或关系的谓词称为谓词常项，一般用F,G,H,…等表示.将表示抽象或泛指的谓词称为谓词变项，一般也用F,G,H,…等表示.我们把用谓词字母后填以个体词,用F(x)表示x具有性质F，用L(a,b)表示a与b具有关系L，．例F(x):x是奇数,a:９,b:7.　F(a):9是奇数,F(b):7是奇数.H(x,y):x大于y,a:3,b:2.H(a,b):3大于2.L(x,y):x比y聪明,a:刘刚,b:张立.　L(a,b):刘刚比张立聪明.令L(x,y,z):x在y与z之间,a:电话,b:台灯,c:笔筒.　L(a,b,c):电话在台灯与笔筒之间．谓词谓词中所含个体变项的个数称为谓词的元数.含n个个体变项的谓词，称为n元谓词,记为P(x1,x2,…xn).n元谓词是定义在个体域上，以{1,0}为值域的n元函数.一般地，一元谓词描述个体词的性质，二元或多元谓词描述两个或多个个体词间的关系.例　F(x)表示x具有性质F；L(x,y)表示x与y具有关系L．　要使P(x1,x2,…xn)成为命题，P必须用谓词常项取代，x1,x2,…xn用n个体常项取代，有时将不带个体变项的谓词称为0元谓词,命题逻辑中的命题常项可用0元谓词表示,可视为谓词的特殊情形．这样，一阶逻辑可视为命题逻辑的扩张.令G(x,y)：“x高于y”，于是，G(x,y)是一个二元谓词.　a：张三，b：李四，则G(a,b)就是命题：“张三高于李四”.但是，G(x,y)不是命题，而是一个命题函数.例将下列命题在一阶逻辑中用谓词符号化(1)宋祖英是女歌唱家．(2)若６大于４且４大于２，则６大于２．解　(1)令F(x)：x是女人,G(y)：y是歌唱家,a：宋祖英,(1)符号化为F(a)G(a).　(2)令G(x,y)：x大于y,a：6,b：4,c:2,(2)符号化为G(a,b)G(b,c)→G(a,c).量词例将下列命题在一阶逻辑中符号化所有人都呼吸.有的人吸烟.在谓词逻辑中用个体词和谓词还不足以准确描述命题，还需要引进表示数量的词.表示数量的词称为量词.量词分为全称量词和存在量词.量词全称量词对应语言“一切”，“所有的”，“任意的”，“每一个”.用符号表示全称量词，用x表示个体域中所有个体，用xF(x)表示个体域中所有个体具有性质F.存在量词对应语言“存在着”，“有一个”，“至少有一个”，用符号表示存在量词，用x表示存在个体域中的个体，xF(x)表示存在个体域中的个体具有性质F.使用量词将命题符号化与个体域有关例（1）所有人都呼吸.（2）有的人吸烟.个体域为人类集合（1）符号化为xF(x)，其中F(x)：x呼吸（真命题）（2）符号化为xG(x)，其中G(x)：x吸烟（真命题）个体域为全总个体域.设M(x)：x是人；F(x)：x呼吸；G(x)：x吸烟（1）符号化为x(M(x)F(x))，（真命题）（2）符号化为x(M(x)G(x))，（真命题）M(x)称为特性谓词．在一阶逻辑中使用量词应注意的问题在不同的个体域中，命题的符号化形式可能不同，命题的真值也可能会改变.如xG(x),其中G(x):x+9=6,当个体域取自然数集时真值为０；当个体域取实数集时真值为１.　在考虑命题的符号化时，如果对个体域未做声明，一律使用全总个体域.多个量词同时出现时，不能随意改变它们的次序，否则将改变原命题的涵义.如　令H(x,y):x>y,D:R,xyH(x,y)1yxH(x,y)0在一阶逻辑中将命题符号化(1)对于任意的x，均有x２-1=(x-1)(x+1)　　　　　(2)存在x，使得x+6=4.要求:①个体域为自然数集N　　②个体域为实数集R解①个体域为自然数集N(1)xF(x)，其中F(x)：x２-1=(x-1)(x+1)　1(2)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在一阶逻辑中将命题符号化(1)并非每个实数都是有理数(2)没有不犯错误的人(3)参加考试的人未必都能取得好成绩．(4)尽管有人聪明，但未必一切人都聪明．解个体域取全总个体域(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)参加考试的人未必都能取得好成绩．(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聪明在一阶逻辑中将命题符号化(1)兔子比乌龟跑得快．(2)有的兔子比所有的乌龟跑得快．(3)并非所有的兔子比所有的乌龟跑得快．(4)不存在同样高的两个人．解　个体域取全总个体域．设F(x):x是兔子,G(y):y是乌龟，H(x,y):x比y跑得快.(1)xy(F(x)G(y)→H(x,y))(2)x(F(x)y(G(y)→H(x,y)))(3)xy(F(x)G(y)→H(x,y))或xy(F(x)G(y)H(x,y))(4)设M(x):x是人,L(x,y):xy，P(x,y):x与y一样高.　xy(M(x)M(y)L(x,y)P(x,y))或xy(M(x)M(y)L(x,y)→P(x,y))一阶逻辑公式及解释一阶逻辑中的字母表个体常项：a,b,c,…,ai,bi,ci,…,i1个体变项：x,y,z,…,xi,yi,zi,…,i1函数符号：f,g,h,…,fi,gi,hi…,i1谓词符号：F,G,H,…,Fi,Gi,Hi,…,i1量词符号：,联结词：¬,,,,↔括号与逗号：()与,项定义(1)个体常项和个体变项是项；(2)若(x1,x2,…xn)是任意n元函数，t1,t2,…tn是任意的n个项，则(t1,t2,…tn)是项.(3)只有有限次使用(1),(2)生成的符号串才是项.原子公式定义设P(x1,x2,…xn)是任意n元谓词，t1,t2,…tn是任意的n个项，则称P(t1,t2,…tn)为原子公式.例　F(x)，G(y)，H(x,y)，Ｌ(x,a+2y)都是原子公式．谓词合式公式（一阶逻辑公式）定义(1)原子公式是合式公式；(2)若A是合式公式，则(A)是合式公式；(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)是合式公式；(4)若A是合式公式，则xA，xA是合式公式.(5)当且仅当能够有限次地应用(1)(4)生成的符号串才是合式公式.注:(1)（AB）,（AB）,（AB）,（A↔B）外面的括号可省去.(2)谓词合式公式也称一阶逻辑公式，简称为公式.辖域、指导变项、自由变项、约束变项定义在公式xA和xA中，称x为指导变项，A为相应量词的辖域，在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其它变项均称为自由出现的.公式x(P(x,y)Q(x,z))R(x)从左向右算起，变项x的第一，第二次出现是约束的，第三次出现是自由的；变项y，z的出现是自由的.公式x(F(x,y,z)yG(x,y))从左向右算起，变项y的第一次出现是自由的，第二次出现是约束的；变项x的出现都是约束的.用A(x)等表示x是自由出现的任意公式．　如A(x)=zyF(x,y,z)yG(x,y)　B(y)=x(F(x,y)G(y))　　A(x,y)=zF(x,y,z)G(x,y)A(x)等前加上量词后，A(x)中的x就变成约束出现的．xA(x)，xA(x)中的量词去掉，A(x)中的x就又变成自由出现的了．　　闭式定义　设A为任意公式，若A中无自由出现的个体变项，则称A为封闭式公式，简称闭式．如xy(F(x)G(y)H(x,y))为闭式．　谓词公式的解释定义一个解释I由4部分组成：(1)非空个体域D;(2)D中一部分特定元素；(3)D上一些特定的函数；(4)D上一些特定的谓词.例给定一个解释I如下：(1)个体域为自然数集N;(2)个体常项a=0；(3)函数f(x,y)=x+y,g(x,y)=xy；(4)谓词F(x,y)为x=y.在解释I下，研究下列各公式(1)xy(F(f(x,a),y)→F(f(y,a),x))(2)xy(F(f(x,y),g(x,y))(3)F(f(x,y),f(y,z))(4)F(g(x,y),g(y,x))在解释I下,公式分别为(1)xy(x+0=y→y+0=x)真命题(2)xy(x+y=xy)假命题(3)x+y=y+z　　真值不确定，不是命题(4)xy=yx真命题有的公式在具体解释下真值确定，即变成命题；有的公式在具体解释下真值仍不能确定，因而仍然不是命题.闭式在任何解释下都成为命题.不是闭式的公式在某一解释下，也可能成为命题.谓词公式的类型定义设A为一谓词公式。若A在它的所有解释下均为真，则称A为永真式（或有效式）；若A在它的所有赋值下均为假，则称A为矛盾式（或永假式）；如A不是矛盾式，则称A为可满足式.谓词公式的分类谓词公式代换实例定义设A0是含n个命题变项p1,p2,…,pn的命题公式，用谓词公式Ai(1in)处处取代A0中的pi，所得公式A称为A0的代换实例.重言式的代换实例是永真式.矛盾式的代换实例是矛盾式.判断下列公式的类型(1)xF(x)→(xyG(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)(1)为p→(q→p)的代换实例，p→(q→p)为重言式，故(1)是永真式．(2)为(p→q)q的代换实例，(p→q)q为矛盾式，故(2)是矛盾式．(3)当xF(x)为真时，xF(x)为真，故(3)是永真式．(4)取解释I１：个体域为自然数集N;　　　　　　F(x)：x是偶数　　　　　　G(x)：x是素数这时(4)为假．　取解释I２：个体域为实数集R;　　　　　　F(x)：x是正数　　　　　　G(x)：x是负数这时(4)为真　故(4)为非永真式的可满足式．第五章一阶逻辑等值式一阶逻辑等值式定义设A、B为一阶逻辑公式，若A↔B是永真式，则称A与B是等值的，记作AB，称AB为等值式.一阶逻辑等值式命题逻辑中的基本等值式的代换实例都是一阶逻辑等值式.例xF(x)xF(x)xF(x)xF(x)¬xF(x)0xF(x)¬xF(x)1¬(xF(x)yG(y))¬xF(x)¬yG(y))一阶逻辑基本等值式在有限域D={a1,a2,…an}中消去量词等值式.(1)xA(x)A(a1)A(a2)…A(an)(2)xA(x)A(a1)A(a2)…A(an)一阶逻辑基本等值式量词否定等值式(1)¬xA(x)x¬A(x)(2)¬xA(x)x¬A(x)一阶逻辑基本等值式量词辖域收缩与扩张等值式x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)其中B中不出现约束变项x．一阶逻辑基本等值式量词辖域收缩与扩张等值式x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)其中B中不出现约束变项x．一阶逻辑基本等值式量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：x(A(x)B(x))xA(x)xB(x)不成立解释I　D:N，A(x):x是奇数，B(x):x是偶数.x(A(x)B(x))xA(x)xB(x)10x(A(x)B(x))xA(x)xB(x)不成立解释I　D:R,A(x):x是正数，B(x):x是负数x(A(x)B(x))xA(x)xB(x)01置换规则置换规则设Ф(A)是含公式A的谓词公式，BA则可用B置换Ф(A)中的A，得Ф(B)，保证Ф(A)Ф(B).在一个公式中，同一个个体变项可以既是自由出现的又是约束出现的，这样容易引起混淆，为研究问题带来不便，我们希望一个个体变项在一个公式中以一种身份出现．为此引入下面两条规则．约束变项换名规则约束变项换名规则(1)在A公式中,将某量词的指导变项,以及该量词辖域中所出现的所有该约束变项都用新的个体变项替换,其余部分不变.(2)新的个体变项在该辖域中不出现.(3)所得公式与原公式A等值．例对于x(P(x,y)Q(x,z))G(x)，可换名为u(P(u,y)Q(u,z))G(x)但下面的改名都是不对的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)自由变项代替规则自由变项代替规则(1)将A公式中某一自由出现的所有个体变项都用新的个体变项代替,其余部分不变.(2)新的个体变项在原公式A中不出现.(3)所得公式与原公式A等值．例对于xH(x,y)yG(y)→L(y,z)，可代替为xH(x,u)yG(y)→L(u,z)但下面的代替都是不对的xH(x,u)yG(u)→L(u,z)xH(x,z)yG(y))→L(z,z)xH(x,u)yG(y))→L(y,z)利用约束变项换名规则和自由变项代替规则可使同一个体变项在一个公式中以一种身份出现．在一阶逻辑等值演算过程中，需不断使用置换规则,约束变项换名规则和自由变项代替规则.例设个体域D={a,b,c}，消去下列公式中的量词.(1)xF(x)→yG(y)(2)x(F(x)yG(y))(3)xy(F(x)→G(y))解(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)xy(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)xy(F(x)G(y)→H(x,y))xy(F(x)G(y)H(x,y))证(1)x(F(x)→G(x))　x(F(x)G(x))　x(F(x)G(x))　x(F(x)G(x))(2)xy(F(x)G(y)→H(x,y))xy(F(x)G(y)→H(x,y))xy((F(x)G(y))H(x,y))xy(F(x)G(y)H(x,y))与命题逻辑一样，在一阶逻辑中，我们给出一阶逻辑公式的规范形式，即前束范式．前束范式前束范式定义设A为一阶逻辑公式，若A具有如下形式Q1x1…QnxnB则称A为前束范式.其中Qi或者是，或者是，i=1，…，n，B是不含量词的公式.例如xyz(P(x,y)H(x,z))xyzP(x,y,z)定理定理2.1对任意一阶逻辑公式都存在与其等值的前束范式（但形式不唯一）.求前束范式的主要利用基本等值式、约束变量换名规则、自由变量代替规则等进行等值演算.一阶逻辑公式的前束范式形式不唯一.这与命题逻辑中的主析取范式和主合取范式不同．一个公式的前束范式中，各个指导变项应该不同，原来自由出现的个体变项还应该是自由出现的，且自由出现的次数不变．例　求公式　(1)xF(x)xG(x)　　(2)xF(x)xG(x)　的前束范式解(1)xF(x)xG(x)xF(x)xG(x)　　　　　量词否定等值式x(F(x)G(x))　　　　　　量词分配等值式(2)xF(x)xG(x)xF(x)xG(x)　　　　　量词否定等值式yF(y)xG(x)　　　　　约束变项换名规则yx(F(y)G(x))　　　量词收缩扩张等值式yx(G(x)F(y))例求公式(x(F(x,y)yG(x,y))的前束范式.解(x(F(x,y)yG(x,y))xF(x,y)yG(x,y))xF(x,y)yG(x,y))量词否定等值式uF(u,y)vG(x,v))约束变项换名规则u(F(u,y)vG(x,v))量词收缩扩张等值式uv(F(u,y)G(x,v))量词收缩扩张等值式例求公式x(F(x)yG(x,y,z))zH(x,y,z)的前束范式.解x(F(x)yG(x,y,z))zH(x,y,z)x(F(x)yG(x,y,u))zH(v,w,z)自由变项代替规则xy(F(x)G(x,y,u))zH(v,w,z)量词收缩扩张等值式xyz((F(x)G(x,y,u))H(v,w,z))量词收缩扩张等值式一阶逻辑的推理理论推理的形式结构定义称蕴涵式(A1A2…Ak)B为一阶逻辑推理的形式结构.A1,A2,…,Ak为推理的前提，B为推理的结论.若(A1A2…Ak)B为永真式，则称从前提A1,A2,…,Ak推出结论B的推理有效，B是A1,A2,…,Ak的逻辑结论.其中A1,A2,…,Ak,，B为谓词公式.判断(A1A2…Ak)B为永真式比命题逻辑困难，判断推理是否有效主要靠形式证明的方法.一阶逻辑的推理方法可看作是命题逻辑方法的扩张，因为作为扩大的系统，命题逻辑是包含在一阶逻辑之中的，所以命题逻辑的推理定律，推理规则可在一阶逻辑中应用．推理定律（永真蕴涵式）命题逻辑中推理定律的代换实例.例(xF(x)yG(y))xF(x)yG(y)xF(x)yG(y)xF(x)每个基本等值式均产生两个推理定律.例¬(xF(x)yG(y))¬xF(x)¬yG(y))¬xF(x)¬yG(y))¬(xF(x)yG(y))推理定律量词分配的推理定律xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x))推理规则规则P(前提引入规则)：在证明的任何步骤上都可以引用前提.规则T(结论引入规则)：在证明的任何步骤上所得到的结论都可作为后续证明的前提.(置换规则,附加，化简,合取，假言推理,拒取式,析取三段论,假言三段论,等价三段论,构造性二难等.)在一阶逻辑中，某些前提与结论可能受量词的制约，必须在推理过程中有消去和添加量词的规则，以使证明能如命题逻辑中那样进行．除与命题逻辑相同的推理规则外，一阶逻辑还有下面关于量词4条消去和添加量词的推理规则.使用这4条规则时必须注意条件.推理规则全称量词消去规则（UI规则）xA(x)A(y)xA(x)A(c)UI规则成立的条件：　(1)x为A(x)中自由出现的个体变项；　(2)第一式中的y是任意的不在A(x)中约束出现的个体变项；　(3)第二式中的c是任意的个体常项.例D:RF(x,y):x>yA(x)=yF(x,y)xA(x)yF(z,y)　xA(x)yF(y,y)错误．原因违背(2).推理规则全称量词引入规则（UG规则）A(y)xA(x)UG规则成立的条件：(1)y在A(y)中自由出现，且y取个体域中任何值时，A均为真.(2)取代y的x不能在A(y)中约束出现.例D:RF(x,y):x>yA(y)=xF(x,y)　A(y)zxF(x,z)A(y)xxF(x,x)错误．原因违背(2).推理规则存在量词引入规则（EG规则）A(c)xA(x)EG规则成立的条件：(1)c是使A为真的特定的个体常项.(2)取代c的x不能已在A(c)中出现过.例D:RF(x,y):x>yA(3)=xF(x,3)A(3)yxF(x,y)　A(3)xxF(x,x)错误．原因违背(2).推理规则存在量词消去规则（EI规则）xA(x)A(c)EI规则成立的条件：(1)c是使A为真的特定的个体常项.(2)c不在A(x)中出现过.(3)A(x)中除x外，不能有另外的自由出现的个体变项.例指出下面推理中的错误(1)x(F(x)G(x))前提引入(2)F(c)G(c)(1)EI(3)F(c)(2)化简(4)y(H(y)I(y))　　　前提引入(5)H(c)I(c)　　　(4)EI(6)H(c)　　　　(5)化简(7)F(c)H(c)　　(3)(6)合取(8)x(F(x)H(x))　　　　　(7)EG例指出下面推理中的错误1.(1)xy(x>y)前提引入(2)y(z>y)(1)UI(3)z>c(2)EI(4)x(x>c)　　　(3)UG2.(1)xF(x)→G(x)前提引入(2)F(y)→G(y)(1)UI例指出下面推理中的错误(1)x(F(x)→G(x))前提引入(2)F(c)→G(c)(1)UI(3)x(F(x)H(x))　　　前提引入(4)F(c)H(c)(3)EI(5)F(c)(4)化简(6)G(c)(2)(5)假言推理(7)H(c)(4)化简(8)G(c)H(c)　　(6)(7)合取(9)x(G(x)H(x))　　　　　(8)EG使用以上这4条规则时必须注意必须对辖域为整个公式的量词使用它们,不能对出现在公式中的量词使用它们.故在构造推理证明时,若要应用EI规则和UI规则消去量词,应首先将含量词公式化为前束范式.EI规则中得到的c一定满足UI规则中的条件,但反之不真.一阶逻辑自然推理系统的构成一阶逻辑字母表一阶逻辑合式公式一阶逻辑推理规则例在一阶逻辑中构造下面推理的证明前提:x(F(x)H(x)),x(G(x)→H(x))结论:x(G(x)→F(x))证明(1)x(F(x)H(x))　　　　　　　　　　　前提引入(2)x(F(x)H(x))　　　　　　　(1)置换(3)x(H(x)→F(x))　　　　　　　　　　(2)置换(4)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例在一阶逻辑中证明苏格拉底三段论:“凡人都是要死的.苏格拉底是人.所以苏格拉底是要死的.”取全总个体域设F(x):x是人,G(x):x是要死的,a:苏格拉底.前提:x(F(x)→G(x)),F(a)结论:G(a).证明(1)x(F(x)→G(x))前提引入(2)F(a)G(a)(1)UI(3)F(a)前提引入(4)G(a)(2)(3)假言推理例在一阶逻辑中构造下面推理的证明有些病人相信所有的医生.但是病人都不相信骗子.所以医生都不是骗子.取全总个体域设F(x):x是病人,G(x):x是医生,H(x):x是骗子,L(x,y):x相信y.前提: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))证明(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)假言三段论(12)x(G(x)→H(x))　　　　　　　　　　　　　　　(11)UG例在一阶逻辑中构造路易卡路尔的断言的证明没有鸭子喜欢跳舞．没有军官不喜欢跳舞．我家的家禽都是鸭子．因此我家的家禽都不是军官．取全总个体域设F(x):x是鸭子,G(x):x喜欢跳舞,M(x):x是家禽,H(x):x是军官.前提:x(F(x)→G(x)),y(H(y)→G(y)),z(M(z)→F(z))结论:w(M(w)→H(w))前提:x(F(x)→G(x)),y(H(y)→G(y)),z(M(z)→F(z))结论:w(M(w)→H(w))证明(1)x(F(x)→G(x))前提引入(2)F(t)→G(t)　　　(1)UI(3)y(H(y)→G(y))前提引入(4)H(t)→G(t)(3)UI(5)z(M(z)→F(z))前提引入(6)M(t)→F(t)(5)UI(7)M(t)→G(t)(6)(2)假言三段论(8)G(t)→H(t)　　　　　(4)置换(9)M(t)→H(t)　　　　　(7)(8)假言三段论(10)w(M(w)→H(w))(9)UG附加前提证明法CP规则若(A1A2…AkA)B,则(A1A2…Ak)(AB)其中A1,A2,…,Ak,,A,B为谓词公式.此规则把结论AB中的A做为附加前提,也称为附加前提引入规则.例在一阶逻辑中构造下面推理的证明每个在银行存款的人都能得到利息．所以,若没有人得到利息,则没有人在银行存款．取全总个体域设F(x):x是在银行存款的人,G(x):x是得到利息的人.前提:x(F(x)→G(x))结论:xG(x)→xF(x)前提:x(F(x)→G(x))结论:xG(x)→xF(x)证明(1)x(F(x)→G(x))前提引入(2)F(y)→G(y)　　　(1)UI(3)xG(x)附加前提引入(4)xG(x)(3)置换(5)G(y)(4)UI(6)F(y)(2)(5)拒取式(7)xF(x)(6)UG(8)xF(x)　　　　　(7)置换xG(x)→xF(x)CP规则归谬法(A1A2…Ak)B当且仅当(A1A2…Ak¬B)0其中A1,A2,…,Ak，B为谓词公式.这种在推理过程中,将结论的否定式作为附加前提引出矛盾式的证明方法称为归谬法.在一阶逻辑中构造下面推理的证明前提:x(P(x)Q(x)),xP(x)结论:xQ(x)证明用归谬法(1)xP(x)前提引入(2)P(y)(1)UI(3)xQ(x)否定结论引入(4)xQ(x)(3)置换(5)Q(y)(4)UI(6)P(y)Q(y)(2)(5)合取(7)x(P(x)Q(x))前提引入(8)P(y)Q(y)(7)UI(9)(P(y)Q(y))(6)置换(10)(P(y)Q(y))(P(y)Q(y))(8)(9)合取