《[理学]第2章一阶逻辑》由会员分享，可在线阅读，更多相关《[理学]第2章一阶逻辑（91页珍藏版）》请在金锄头文库上搜索。
1、第二章 一阶逻辑,凡人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,例：,p,q,r,(pq) r,2.1 一阶逻辑基本概念,简单命题,个体词,谓词,用来刻画个体词的性质或个体词之间关系的词,所研究对象中可以独立存在的具体的或抽象的客体,2是无理数。 王宏是程序员。 小李比小赵高2厘米。,例：,个体常项,个体变项,表示具体的或特定的个体的词,a,b,c, ,表示抽象的或泛指的个体的词,x,y,z, ,个体域（或论域）,全总个体域,宇宙间一切 事物组成的 个体域,个体变项的 取值范围,谓词常项,谓词变项,表示具体性质或关系的谓词,F,G,H,表示抽象的或 泛指的谓词,F,G,H, ,F(
2、x) 个体变项x,y具有关系L L(x,y),以后常称这种个体变项和谓词 的联合体F(x),L(x,y)等为谓词,个体变项x具有性质F,元数,谓词中所包含个体变项的个数,n元谓词,含n(n1)个个体变项的谓词,P(x1,x2, ,xn),定义域 值域 个体变项的顺序能否改变？ 是否命题？需要满足什么条件？ 0元谓词与简单命题,P(x1,x2, ,xn),、2是素数且是偶数 、如果2大于3，则2大于4 、如果张明比李民高，李民比赵亮高，则张明比赵亮高。,例2.1 将下列命题用0元谓词符号化,例：将下列命题符号化,、所有的人都是要死的。 、有的人活百岁以上。,称表示个体常项或变项之 间数量关系的词
3、为量词,1. 全称量词,对应日常语言中的“一切”， “所有的”， “任意的”等词。,xF(x),x,对个体域里的所有个体,个体域里的所有个体都有性质F,2. 存在量词,对应日常语言中的“存在着”， “有一个”， “至少有一个”等词。,xF(x),x,存在个体域里的个体,存在着个体域中的个体具有性质F,例：将下列命题符号化,、所有的人都是要死的。 、有的人活百岁以上。 第一种情况：个体域D为人类集合 第二种情况：个体域D为全总个体域 1) 对所有个体而言，如果它是人，则它是要死的。 2) 存在着个体，它是人并且活百岁以上。,特性谓词,使用量词时应注意：,1、不同的个体域命题符号化的形式可能不一样
4、。 2、若未给出个体域，应为全总个体域。 3、引入特性谓词后，全称量词与存在量词符号化的形式不同。 4、n元谓词转化为命题至少需要n个量词。 5、D为有限集时，注意xA(x), xA(x) 6、多个量词同时出现时，不能随意颠倒顺序。,例2.2 在一阶逻辑中将下面命题符号化 凡有理数均可表成分数。 有的有理数是整数。,要求：1)个体域为有理数集合。 2)个体域为实数集合。 3)个体域为全总个体域。,凡有理数均可表成分数。 有的有理数是整数。 个体域为有理数集合。,凡有理数均可表成分数。 有的有理数是整数。 个体域为实数集合(全总个体域)。,例2.3 将下面命题符号化 对所有的x，均有 -1=(x
5、+1)(x-1)。 存在x，使得x+5=2.,要求：1)个体域为自然数集合。 2)个体域为实数集合。,1)对所有的x，均有 -1=(x+1)(x-1)。,要求：1)个体域为自然数集合。 2)个体域为实数集合。,2)存在x，使得x+5=2.,要求：1)个体域为自然数集合。 2)个体域为实数集合。,凡偶数均能被2整除。 存在着偶素数。 没有不犯错误的人。 在北京工作的人未必都是北京人。,例2.4 在一阶逻辑中将下面命题符号化,一切人都不一样高。 每个自然数都有后继数。 有的自然数无先驱数。,例2.5在一阶逻辑中将下面命题符号化,主要内容,个体词 谓词 量词,掌握：一阶逻辑中的命题符号化 练习：P5
6、5 2.1，2.2，2.3,复习,个体词 谓词 量词,2.2 一阶逻辑合式公式及解释,定义2.1 字母表,1、个体常项：a,b,c,ai,bi,ci,i1 2、个体变项：x,y,z,xi,yi,zi, i1 3、函数符号：f,g,h,fi,gi,hi, i1 4、谓词符号：F,G,H,Fi,Gi,Hi, i1 5、量词符号：, 6、联结词符：, , , , 7、括号和逗号: ( , ) , ，,定义2.2 项（递归定义）,1、个体常项和个体变项是项； 2、若(x1,x2,xn)是任意n元函数，t1,t2,tn是项，则(t1,t2,tn) 是项； 3、只有有限次地使用1,2生成的符号串才是项。,
7、定义2.3 原子公式,设R(x1,x2,xn)是任意的n元谓词， t1,t2,tn是项，则称R(t1,t2,tn)为原子公式 。,定义2.4 合式公式,1、原子公式是合式公式； 2、若A是合式公式，则(A)也是合式公式 3、若A,B是合式公式，则(AB)， (AB)， (AB)， (AB)也是合式公式； 4、若A是合式公式，则xA,xA 也是合式 公式 5、只有有限次的应用1 4组成的符号串才是合式公式。,公式,指,导,变,项,相,应,量,词,的,辖,域,约束出现,自由出现,1、 2、 3、,例2.6 指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现,设A为任一公式，若
8、A中无自由出现的个体变项，则称A是封闭的合式公式。,将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一辖域中未曾出现过的个体变项符号，公式中其余部分不变。,换名规则：,代替规则,对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。,1、 2、 3、,例2.6 指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现,定义2.7 解释I,1、非空个体域D; 2、D中一部分特定元素； 3、D上一些特定的函数； 4、D上一些特定的谓词。,例2.7 给定解释I如下 : 1)DI=2,3; 2)DI中特定元素a=2 3)函数f(x)为f(2
9、)=3,f(3)=2; 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0.求下列各式的值:,例2.7 给定解释I如下 : 1)Di=2,3; 2) Di中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2; 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0.求下列各式的值:,例2.7 给定解释I如下 : 1)Di=2,3; 2) D
10、i中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2; 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0.求下列各式的值:,例2.7 给定解释I如下 : 1)Di=2,3; 2) Di中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2; 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0.求下列各式的值:,例2.8 给定
11、解释N如下 : 1)个体域为自然数DN; 2) DN中特定元素a=； 3) DN上特定函数f(x,y)=x+y,g(x,y)=xy; 4) DN特定谓词F(x,y)为x=y 在解释N下判断下列公式的真假:,例2.8 给定解释N如下 : 1)个体域为自然数Di; 2) Di中特定元素a=； 3) Di上特定函数f(x,y)=x+y,g(x,y)=xy; 4) Di特定谓词F(x,y)为x=y 在解释N下判断下列公式的真假:,例2.8 给定解释N如下 : 1)个体域为自然数Di; 2) Di中特定元素a=； 3) Di上特定函数f(x,y)=x+y,g(x,y)=xy; 4) Di特定谓词F(x,
12、y)为x=y 在解释N下判断下列公式的真假:,例2.8 给定解释N如下 : 1)个体域为自然数Di; 2) Di中特定元素a=； 3) Di上特定函数f(x,y)=x+y,g(x,y)=xy; 4) Di特定谓词F(x,y)为x=y 在解释N下判断下列公式的真假:,例2.8 给定解释N如下 : 1)个体域为自然数Di; 2) Di中特定元素a=； 3) Di上特定函数f(x,y)=x+y,g(x,y)=xy; 4) Di特定谓词F(x,y)为x=y 在解释N下判断下列公式的真假:,例2.8 给定解释N如下 : 1)个体域为自然数Di; 2) Di中特定元素a=； 3) Di上特定函数f(x,y
13、)=x+y,g(x,y)=xy; 4) Di特定谓词F(x,y)为x=y 在解释N下判断下列公式的真假:,闭式在任何解释之下都变成命题,逻辑有效式（永真式）,谓词公式（公式）,矛盾式（永假式）,在任何解释下都是假的,可满足式,至少存在一个解释使之为真,在任何解释下都是真的,定义2.9 代换实例,设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An,是n个谓词公式，用Ai(1in)处处代换pi，所得公式A称为A0的代换实例。,重言式的代换实例是永真式， 矛盾式的代换实例是矛盾式。,例2.9 判断下列公式的类型,例2.9 判断下列公式的类型,主要内容,谓词公式及其解释 谓词公式的类型 换
14、名规则，代替规则 代换实例,练习：P56 2.42.9 作业：2.5(1)，2.6,2.3 一阶逻辑等值式,定义2.10 设A,B为一阶逻辑中任意的两公式，若AB为逻辑有效式，则称A与B是等值的。,AB,一阶逻辑中的等值式,命题逻辑中等值式的代换实例 一阶逻辑中特有的四组等值式 三个变换规则 置换规则 换名规则 代替规则,消去量词等值式,定理2.1 量词否定等值式,（A(x)是任意的公式）,定理2.2 量词辖域收缩与扩张等值式,1、,2、,定理2.3 量词分配等值式,例2.10 证明：,证明：,不是逻辑有效式,解释I:个体域D为自然数集 F(x)为x是奇数，G(x)为x是偶数,为真,为假,所以不是逻辑有效式,F,F,G,G,证明：,不是逻辑有效式,解释I:个体域D为自然数集 F(x)为x是奇数，G(x)为x是偶数,为真,为假,所以不是逻辑有效式,F,F,G,G,定理2.4 下面两等值式成立,进行等值演算需要的知识：,1、等值式 2、置换规则 3、换名规则 4、代替规则,定义2.11 前束范式,设A为一谓词公式，如果A具有如下形式：
