一阶逻辑基本概念

1、第4章 一阶逻辑基本概念,离 散 数 学,本章说明,本章的主要内容 一阶逻辑基本概念、命题符号化 一阶逻辑公式、解释及分类 本章与后续各章的关系 克服命题逻辑的局限性 是第五章的先行准备,命题逻辑的缺陷,把命题看成是一个个孤立的命题，忽略了命题之间的联系，不能反映某些重要的常见的逻辑思维过程。 1. 繁琐 例. 表述集合个体性质及相互关系 s=1,2,50 表述s中所有元素都大于3这样一个性质，需要 13, 23, , 503 等50个命题,2. 不能描述命题间的逻辑联系 例如，逻辑学中著名的苏格拉底三段论：p：所有人必死q：苏格拉底是人r：苏格拉底必死 表示为命题逻辑：应该有 (pq) r，

2、也就是公式(pq)r应该是恒真的。 显然该公式不是恒真的，解释p，q，r就能弄假该公式,原因：命题r和命题p, q是有内在关系的，只是这种关系在命题逻辑中无法表示。 因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这正是谓词逻辑所要研究的问题,本章内容,4.1 一阶逻辑命题符号化 4.2 一阶逻辑公式及解释 本章小结 习题 作业,4.1 一阶逻辑命题符号化,一阶逻辑命题符号化的三个基本要素 个体词 谓词 量词,个体词及相关概念,个体词一般是充当陈述句主语的名词或代词,说明,个体词：指所研究对象中可以独立存在

3、的具体或抽象的客体。 举例 命题：电子计算机是科学技术的工具。个体词：电子计算机。 命题：他是三好学生。个体词：他,心物一元 or 心物二元？ 量子力学中的测不准原理,个体常项：表示具体或特定的客体的个体词，用小写字母a, b,c，表示。 个体变项：表示抽象或泛指的客体的个体词，用x,y,z,表示。 个体域（或称论域）：指个体变项的取值范围。 可以是有穷集合，如a, b, c, 1, 2。 可以是无穷集合，如n,z,r,。 全总个体域（universe）由宇宙间一切事物组成,个体词及相关概念,本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域,说明,谓词及相关概念,谓词（p

4、redicate）是用来刻画个体词性质及个体词之间相互关系的词。 (1) 是无理数。是个体常项，“是无理数”是谓词，记为f，命题符号化为f() 。 (2) x是有理数。x是个体变项，“是有理数”是谓词，记为g，命题符号化为g(x)。 (3) 小王与小李同岁。小王、小李都是个体常项，“与同岁”是谓词，记为h，命题符号化为h(a,b) ，其中a：小王，b：小李。 (4) x与y具有关系l。x，y都是个体变项，谓词为l，命题符号化为l(x,y,谓词常项：表示具体性质或关系的谓词。用大写字母表示。如(1)、 (2) 、(3) 中谓词f、g、h。 谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写字母

5、表示。如(4) 中谓词l。 n(n1)元谓词：p(x1,x2,xn)表示含n个个体变项的n元谓词。 n=1时，一元谓词表示x1具有性质p。 n2时，多元谓词表示x1,x2,xn具有关系p。 0元谓词：不含个体变项的谓词。如f(a)、g(a,b)、 p(a1,a2,an)。若f、g、p为谓词常项，则上述0元谓词为命题常项；若f、g、p为谓词变项，则为命题变项,n元谓词是命题吗？ 不是，只有用谓词常项取代p，用个体常项取代x1,x2,xn时，才能使n元谓词变为命题,思考,谓词及相关概念,谓词的形式化定义,设d是非空个体名称集合，定义在dn上取值于0，1上的n元函数，称为n元命题函数或n元谓词。其中

6、dn表示集合d的n次笛卡尔乘积。 例：令g(x，y)： “x高于y”，g(x，y)是一个二元谓词。 将x代以个体 “张三”，y代以个体 “李四”，则g(张三，李四)就是命题： “张三高于李四”。 g(x，y)不是命题，而是一个命题函数即谓词。 将x，y代以任意确定的个体，由g(x，y)都能得到一个命题,d=2, 3, 4 设p(x)：x大于3，则p(x)为一元谓词。 指定元素-命题：p(2)=0, p(3)=0, p(4)=1 设p(x,y)：x大于y,则p(x,y)为二元谓词。 指定元素-命题：p(2,3)=0, p(4,2)=1 设p(x,y,z)：若x+y-1=z，则p(x,y,z)为1

7、，否则为0 。则p(x,y,z)为三元谓词。 指定元素-命题：p(2,3,4)=1,p(4,2,2)=0,例题,例题,将命题“这只大红书柜摆满了那些古书。”符号化. (1)设f(x,y)：x摆满了y，r(x)：x是大红书柜 q(y)：y是古书，a：这个书柜b：那些书 符号化为：r(a)q(b)f(a,b) (2)设a(x)：x是书柜，b(x)：x是大的 c(x)：x是红的，d(y)：y是古老的 e(y)： y是图书，f(x,y)：x摆满了y a：这个东西b：那些东西 符号化为：a(a)b(a)c(a)d(b)e(b)f(a,b,用谓词的概念可将苏格拉底三段论做如下的符号化： 令h(x)表示 “

8、x是人”，m(x)表示 “x必死”。 则三段论的三个命题表示如下：p： h(x)m(x)q： h(苏格拉底)r： m(苏格拉底,现在可以将苏格拉底三段论符号化为,令命题p為：所有人都会死 ，其否定命題為 p = (h(x)m(x)= (h(x)m(x)= h(x)m(x) 亦即，命题 p“所有人都会死” 的否定命题是 “所有人都不會死”。这和人们对命题 “所有人都必死”的否定的理解並不一致,但问题是,原因命题p的确切意思应该是： “对任意x，如果x是人，则x必死”。 但是 h(x)m(x) 中并没有确切的表示出 “对任意x”这个意思，因此，在谓词逻辑中除引进谓词外，还需要引进 “对任意x”这个

9、语句，及其对偶的语句 “存在一个x,量词（quantifier）是表示个体常项或个体变项数量屬性的词。 1. 全称量词：符号化为“” （all） 日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。 x表示个体域里的某個个体，x f(x)表示个体域里所有个体都有性质f。 2.存在量词：符号化为“” （exist） 日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。 y表示个体域里某個个体，y g(y)表示个体域里存在个体y具有性质g,量词及相关概念,引入谓词后，命题p就可确切地符号化如下：x(h(x)m

10、(x)命题p的否定命题为： p = (x(h(x)m(x) = x(h(x)m(x)亦即 “至少有一个人是不死的”。这个命题才是 “所有人都要死”的否定。 三段论的三个命题，在谓词逻辑中可以如下表示：p：x(h(x)m(x)q：h(苏格拉底)r：m(苏格拉底) 以后可以证明，在谓词逻辑中，r是p和q的逻辑结果,例 符号化下述命题： （1）所有的老虎都要吃人； （2）每一个大学生都会说英语； （3）所有的人都长着黑头发； （4）有一些人登上过月球； （5）有一些自然数是素数,解 设有如下谓词： p(x)：x会吃人； q(x)：x会说英语； r(x)：x长着黑头发； s(x)：x登上过月球； t(

11、x)：x是素数,1）(x)p(x) x 老虎 ； （2）(x)q(x) x大学生； （3）(x)r(x) x人； （4）(x)s(x) x人； （5）(x)t(x) x自然数,不便之处,1）从书写上十分不便，总要特别注明个体域； （2）在同一个比较复杂的句子中，不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达； 如例 (1)和(4)的合取 (x)p(x) (x)r(x,x人,x老虎,不便之处(续,3）若个体域的注明不清楚，将造成无法确定命题真值。即对于同一个n元谓词，不同的个体域有可能带来不同的真值。 例如 对于语句“(x)(x+6 = 5)”可表示为：“有一些x，使得x+6 = 5

12、”。该语句在下面两种个体域下有不同的真值： （a）在实数范围内时，确有x=-1使得x+6 = 5，因此，(x)(x+6 = 5)为“真”； （b）在正整数范围内时，则找不到任何x，使得x+6=5为“真”，所以，(x)(x+6=5)为“假,不便之处的根源,因为需要特别标注每个谓词的个体域,特性谓词,新的问题出现了，u(x)如何与(x)p(x)，(x)s(x)结合才符合逻辑呢,例 将下面两个命题符号化: (1) 所有的老虎都会吃人。 (2) 有些人登上过月球,特性谓词的使用,1）令 p(x)：x会吃人 u(x)：x是老虎 则符号化的正确形式应该是 (x)(u(x)p(x) 它的含义是：“对于任意的

13、x,如果x是老虎，则x会吃人”，符合原命题的逻辑含义,若符号化为 (x)(u(x)p(x) 它的含义是：“对于任意的x, x是老虎，并且x会吃人”，与原命题“所有的老虎都要吃人”的逻辑含义不符,2）令 s(x)：x登上过月球 u(x)：x是人 则符号化的正确形式应该是 ( x)(u(x) s(x) 它的含义是：“存在x, x是人并且x登上过月球”，符合原命题的逻辑含义,若符号化为 (x)(u(x) s(x) 它的含义是：“存在x, 如果x是人，则x登上过月球”，与原命题“有人登上过月球”的逻辑含义 似乎差不多,谓词逻辑符号化的规则,若统一个体域为全总个体域，对每一个句子中个体变量的变化范围用一

14、元特性谓词刻划，这种特性谓词在加入到命题函数中时必须遵循如下原则,1）对于全称量词(x)，刻划其对应个体域的特性谓词作为蕴涵式之前件加入,2）对于存在量词(x)，刻划其对应个体域的特性谓词作为合取式之合取项加入,例题,用谓词逻辑符号化下述语句： (1) 天下乌鸦一般黑； (2) 没有人登上过木星； (3) 在美国留学的学生未必都是亚洲人； (4) 每个实数都存在比它大的另外的实数； (5) 尽管有人很聪明，但未必一切人都聪明； (6) 对于任意给定的0，必存在着0，使得对任意的x，只要|x-a|，就有|f(x)-f(a)|成立,例题(续,1）天下乌鸦一般黑 设 f(x)：x是乌鸦；g(x, y

15、)：x与y一般黑，则： (x)(y)(f(x)f(y)g(x, y) 或者(x)(y)(f(x)f(y)g(x, y)； （2）没有人登上过木星 设h(x)：x是人；m(x)：x登上过木星，则： (x)(h(x)m(x) 或者 (x)(h(x)m(x,例题(续,3）在美国留学的学生未必都是亚洲人 设a(x)：x是亚洲人； h(x)：x是在美国留学的学生，则： (x)(h(x)a(x) 或者 (x)(h(x)a(x)； （4）每个实数都存在比它大的另外的实数 设r(x)：x是实数；l(x, y)：x小于y，则： (x)(r(x)(y)(r(y)l(x, y,例题(续,5）尽管有人很聪明，但未必一

16、切人都聪明 设m(x)：x是人；c(x)：x很聪明，则： (x)(m(x)c(x) (x)(m(x)c(x)； （6）对于任意给定的0，必存在着0，使得对任意的x，只要|x-a|0)()(0)(x) (|x-a|)(|f(x)-f(a),例题 n元谓词的符号化,例4.5 将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。 解：令 f(x):x是兔子， g(y):y是乌龟， h(x,y):x比y跑得快， l(x,y):x与y跑得同样快。 （1）xy(f(x)g(y)h(x,y) （2） x(f(x)y

17、(g(y)h(x,y) （3） xy(f(x)g(y)h(x,y) （4） xy(f(x)f(y)l(x,y,一阶逻辑命题符号化时需要注意的事项,分析命题中表示性质和关系的谓词，分别符号化为一元和n（ n2）元谓词。 根据命题的实际意义选用全称量词或存在量词。 一般说来，多个量词出现时，它们的顺序不能随意调换。 例如，考虑个体域为实数集，h(x，y)表示x+y=10， 则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为xyh(x,y)，为真命题。 如果改变两个量词的顺序，得yxh(x,y)，为假命题。 有些命题的符号化形式可不止一种。（例4.5之(3)） xy(f(x)g(y)h

18、(x,y) xy(f(x)g(y)h(x,y,量词的语义规定,设g(x)是一元谓词，任取x0d，则g(x0)是一个命题。于是xg(x)是这样一个命题 “对任意xd，都有g(x)”。故对命题xg(x)的真值做如下规定： xg(x)取1值对任意xd，g(x)都取1值；xg(x)取0值至少有一个x0d，使g(x0)取0值,xg(x)是命题 “存在一个x0d，使得g(x0)成立”。对命题xg(x)的真值规定如下： xg(x)取1值至少有一个x0d，使g(x0)取1值；xg(x)取0值对所有xd，g(x)都取0值。 语义上，当d=x0,x1,是可数集合时，xg(x)等价于g(x0)g(x1) xg(x)

19、等价于g(x0)g(x1,例. d=2，3，4，p(x)：x3 则x p(x)等价于 p(2) p(3) p(4) 所以其真值为 0 0 0 x p(x)等价于 p(2) p(3) p(4) 所以其真值为 0 0,课堂练习,设个体域d=1，2，3，p(x) ：x2。 试判断下列公式的真值： (1) xp(x) p(2)； (2) p(3) xp(x,xp(x) p(2) 等价于(p(1) p(2) p(3) p(2) 所以其真值为 (001) 0 =1 0 = 0,p(3) xp(x) 等价于1( p(1) p(2) p(3) 所以其真值为 1 ( 0 0 1) = 1 0 = 0,课堂练习（

20、续,设 p(x)：x是素数；i(x)：x是整数；q(x, y)：x+y=0。用语句描述下述句子，并判断其真假值。 （1）(x)(i(x)p(x)； （2）(x) (i(x)p(x)； （3）(x) (y)(i(x)i(y)q(x, y)； （4）(x)(i(x)(y)(i(y)q(x, y)； （5）(x)(y)(i(x)(i(y)q(x, y,解,句子(1)可描述为：“对任意的整数x，x一定是素数”，真值为“假”； 句子(2)可描述为：“存在一些整数x，x是素数”，真值为“真”； 句子(3)可描述为：“对任意的整数x，y，都有x+y=0”，真值为“假”； 句子(4)可描述为：“对任意的整数x

21、，都存在着整数y，使得x+y=0”，真值为“真”； 句子(5)可描述为：“存在着整数x，使得对任意的整数y，都有x+y=0”，真值为“假,例,符号化下述一组语句： 只要是需要室外活动的课，郝帥都喜欢；所有的公共体育课都是需要室外活动的课；篮球是一门公共体育课；郝帥喜欢篮球这门课。 解 设 o(x)：表示x是需要室外活动的课； l (x, y)：表示x喜欢y； s (x)：表示x是一门公共体育课； hao：表示郝帥；ball：表示篮球,上述句子可符号化为： (x)(o(x)l(hao, x)； (x)(s(x)o(x)； s(ball)；l(hao, ball,例,符号化下述一组语句： 海关人员

22、检查每一个进入本国的不重要人物；某些走私者进入该国时仅仅被走私者所检查；没有一个走私者是重要人物；海关人员中的某些人是走私者。 解 设 e(x)：表示x进入国境； v(x)：表示x是重要人物； c(x)：表示x是海关人员； p(x)：表示x是走私者； b(x, y)：表示y检查x,解,上述句子可符号化为： (x)(e(x) v(x)(y)(c(y)b(x, y)； (x)(p(x)e(x)(y)( b(x,y)p(y)； (x)(p(x)v(x)； (x)(p(x)c(x,4.2 一阶逻辑公式及解释,同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的

23、分类及解释。 一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。 一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为f,一阶语言中的字母表,定义4.1 一阶语言f的字母表定义如下: (1)个体常项：a , b , c , , ai , bi , ci , , i 1 (2)个体变项：x , y , z, , xi , yi , zi , , i 1 (3)函数符号：f , g , h , , fi , gi , hi , , i 1；当个体名称集合d给出时，n

24、元函数符号f(x1，xn)可以是dn到d的任意一个映射。 (4)谓词符号：f , g , h , , fi , gi , hi , , i 1；当个体名称集合d给出时，n元谓词符号p(x1，xn)可以是dn上的任意一个谓词，换言之，是dn到0, 1的任意一个映射。 (5)量词符号: ， (6)联结词符号:, (7)括号与逗号:(,),为何需要函数符号,例如 符号化“周红的父亲是教授”： 设f(x)：x的父亲；p(x)：x是教授；c：周红 此时p(f(c)表示“周红的父亲是教授”这一命题,函数的使用给谓词逻辑中的个体词表示 带来了很大的方便,否则就需要引入二元谓词g(x, y): x 是 y 的

25、父亲，符号化为：p(x) g(x, c)，不如函数简单明了,一阶语言中的项,定义4.2 一阶语言f的项的定义如下: (1) 个体常项和个体变项是项。 (2) 若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项。 (3) 所有的项都是有限次使用(1)，(2)得到的,一阶语言中的原子公式,定义4.3 设r(x1 ,x2 , ,xn)是一阶语言f的任意n元谓词， t1 ,t2 , ,tn是一阶语言f的任意的n个项，则称r(t1 ,t2 , ,tn)是一阶语言f的原子公式。 例如：1元谓词f(x)，g(x)，2元谓词h(x,y)，l(x,y)等都是原子公

26、式,一阶语言 f 的合式公式,定义4.4 一阶语言f的合式公式(well-formed formula)定义如下: (1) 原子公式是合式公式。 (2) 若a是合式公式，则(a)也是合式公式。 (3) 若a，b是合式公式，则(ab)，(ab)，(ab)，(ab) 也是合式公式。 (4) 若a是合式公式，则xa，xa也是合式公式。 (5) 只有有限次的应用(1)(4)构成的符号串才是合式公式。 一阶语言f的合式公式也称为谓词公式，简称公式,a，b代表任意公式，是元语言符号。 下文的讨论都是在一阶语言f中，因而不再提及,说明,自由出现与约束出现,定义4.5 指导变元、辖域、约束出现、自由出现 在公

27、式xa和xa中，称x为指导变元。 在公式xa和xa中，a为相应量词的辖域。 在x和x的辖域中，x的所有出现都称为约束出现。 a中不是约束出现的其他个体变项均称为是自由出现的,量词辖域的确定方法： （1）若量词后有括号，则括号内的子公式就是该量词的辖域； （2）若量词后无括号，则与量词邻接的子公式为该量词的辖域,例,确定以下公式各量词的辖域以及各个体变量为自由变元还是约束变元。 （1）(x)(p(x)(y)r(x, y)； （2）(x)p(x)q(x, y)； （3）(x)(y)(p(y,z)q(x,y)(x)r(x,y)； （4）(x)(p(x)r(x)(y)q(x,y,解,在(1)中，p(x

28、)中的x，r(x,y)的x，y都为约束变元。 在(2)中，p(x)中的x为约束变元，q(x,y)中的x，y是自由变元。 在(3)中，p(y,z)、q(x,y)中的x,y都为约束变元，z为自由变元；r(x,y)中的x为约束变元，y为自由变元。 在(4)中，p(x)，r(x)中的x为约束变元，q(x, y)中的x为自由变元、y为约束变元,变元混淆,4）(x)(p(x)r(x)(y)q(x, y,约束变元,自由变元,在一个公式中，某一个变元的出现既可以是自由的，又可以是约束的，如(4)中的x。为了使得我们的研究更方便，而不致引起混淆，同时为了使公式给人以一目了然的结果，对于表示不同意思的个体变元，我

29、们总是以不同的变量符号来表示,改名规则,约束变元的改名规则 （1）将量词中出现的变元以及该量词辖域中此 变量的所有约束出现都用新的个体变元替换； （2）新的变元应有别于公式中的所有其它变量,代入规则,自由变元的代入规则 （1）将公式中出现该自由变元的每一处都用新的个体变元替换； （2）新变元不允许在原公式中以任何约束形式出现,例,1）将公式(x)(p(x)q(x, y)r(x, y)中的约束变元x进行改名； （2）将公式(x)(p(x)q(x, y)r(x, y)中的约束变元y进行代入。 解 利用改名规则对x进行改名，则： (z)(p(z)q(z, y)r(x, y) (z)(p(z)r(x,

30、 y)r(x, y) (y)(p(y)r(y, y)r(x, y,对 -错 -错,利用代入规则对y进行代入，则： (x)(p(x)q(x, z)r(x, z) (x)(p(x)q(x, z)r(x, y) (x)(p(x)q(x, x)r(x, x,对 -错 -错,改名规则和代入规则的关系,改名规则和代入规则之间的共同点都是不能改变原有的约束关系，而不同点是： （1）施行的对象不同：改名规则是对约束变元施行，代入规则是对自由变元施行； （2）施行的范围不同：改名规则可以只对公式中的一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行，

31、即必须对整个公式施行,改名规则和代入规则的关系（续,3）施行后的结果不同：改名后，公式含义不变，因为约束变元只改名为另一个个体变元，约束关系不改变，约束变元不能改名为个体常量；代入后，不仅可用另一个个体变元进行代入，并且也可用个体常量去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了,封闭的公式,定义4.6 设a是任意的公式，若a中不含有自由出现的个体变项，则称a为封闭的公式，简称闭式。 例如： xy(f(x)g(y)h(x , y) 为闭式， x(f(x)g(x , y) 不是闭式,一阶公式的解释 一阶公式没有确定的意义，一旦将其中的变项（项的变项、谓词变项）用指定

32、的常项代替后，所得公式就具备一定的意义，有时就变成命题了,一阶公式的解释,定义4.7 一阶公式的解释i由下面4部分组成: (a)非空个体域di。 (b)di中一些特定元素的集合 。 (c)di上特定函数集合 |i, n1。 (d)di上特定谓词的集合 | i, n1,a中的第i个n元函数变项 被解释为某个函数常项,a中的第i个n元谓词变项 被解释成某个谓词常项,对解释i的几点说明,被解释的公式不一定全部包含解释中的四个部分,被解释的公式a中的个体变项均取值于di,a中的个体常项 ai 被解释成,在解释的定义中引进了几个元语言符号，如,给定解释 i 如下： (a) 个体域 d=r (b) (c)

33、 (d) 写出下列公式在i下的解释, 并指出它的真值. (1) xf(f(x,a),g(x,a,例,x(x+0=x0) 真,2) xy(f(f(x,y),g(x,y)f(x,y,xy(x+y=xyx=y) 假,3) xf(g(x,y),a,x(xy=0) 真值不定, 不是命题,定理4.1 封闭的公式在任何解释下都变成命题,一阶公式的分类,定义4.8 永真式、永假式、可满足式 设a为一个公式，若a在任何解释下均为真，则称a为永真式(或称逻辑有效式)。 设a为一个公式，若a在任何解释下均为假，则称a为矛盾式(或永假式)。 设a为一个公式，若至少存在一个解释使a为真，则称a为可满足式,永真式一定是可

34、满足式，但可满足式不一定是永真式。 在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况完全不同。 但对某些特殊的公式还是可以判断的,说明,谓词公式的可判定性,1）谓词逻辑公式是不可判定的； （2）只含有一元谓词变项的公式是可判定的； （3）如下形式的公式： (x1)(x2)(xn)p(x1, x2, , xn)， (x1)(x2)(xn)p(x1, x2, ,xn)。 若p中无量词和其它自由变元时，也是可判定的； （4）个体域有穷时的谓词公式是可判定的,谓词逻辑中公式恒真、恒假性的判断异常困难。 原因： 谓词逻辑中的恒真(恒假)公式，要求

35、所有解释i都满足(弄假)该公式。 而解释i依赖于一个非空集合d。由于集合d可以是无穷集合，而集合d的 “数目”也可能是无穷多个。 因此，所谓公式的 “所有”解释，实际上是无法考虑的。 1936年church和turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。 谓词逻辑是半可判定的：如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该公式不是恒真的(当然也不是恒假的)，则无法在有限步内判定这个事实,谓词逻辑公式的判定问题,英国天才数学家、计算机科学家图灵,alan mathison turing,1912-1954) 在孩提时代就对化学和机械着迷,做过大

36、量化学实验。 1931年,获得了剑桥大学皇家学院的奖学金。在完成毕业论文后，被选为该学院的成员。在毕业论文中，发现了统计学中的一个著名定理中心极限定理。 1935年，对判定问题着了迷，这是伟大的德国数学家希尔伯特提出的一个问题：是否有一个能用于判断任何命题是否为真的一般方法,图灵喜欢跑步，一天，在跑步之后的休息中，发现了解决判定问题的关键思想。在他的解决方案中，他发明了今天称为图灵机的计算模型，并用它作为计算机器的最一般模型。利用这个机器，发现了一个不能用一般方法判定的问题，也就是停机问题。通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。 从1936年到1938年，

37、图灵在普林斯顿大学访问，与丘奇(alonze church)一起工作，丘奇也独立解决了希尔伯特提出的判定问题,停机问题,不存在这样一个程序（算法），它能够计算任何程序（算法）在给定输入上是否会结束（停机）。 證明：反證法。假设我们真做出了这么一个极度聪明的万能算法（就叫god_algo吧），只要给它一段程序（二进制描述），再给它这段程序的输入，它就能告诉你这段程序在这个输入上会不会结束（停机） bool god_algo(char* program, char* input) if( halts on ) return true; return false;,bool satan_algo(c

38、har* program) if(god_algo(program, program) while(1); / loop forever! return false; / can never get here! else return true;,satan_algo(satan_algo); 显然，這個函數調用要么能够结束，要么不能结束。 如果它能够结束，那么santa_algo算法里面的那个if判断就会成立（因为god_algo(santa_algo,santa_algo)将会返回true），从而进入一个无穷循环（while(1);），从而函數調用satan_algo(satan_algo

39、) 就永远不会结束。 而如果它不能结束，则if判断就会失败，从而跳过那个while(1)返回true，即我们调用satan_algo(satan_algo)又能够結束。 总之，satan_algo(satan_algo)能够停机=它不能停机。satan_algo(satan_algo)不能停机=它能够停机。所以它停也不是，不停也不是。得出矛盾。 于是，我们的假设，god_algo算法的存在性不成立,为现代人工智能做出巨大贡献的图灵在理论上奠定了计算机产生的基础。对于计算机人士而言，获得图灵奖就等于物理学家获得诺贝尔奖一样。 图灵测试：图灵认为如果机器能成功的伪装成人欺骗观察者，那么就认为它具有

40、了智能。 由计算机、被测试的人和主持试验人组成。计算机和被测试的人分别在两个不同的房间里。测试过程由主持人提问，由计算机和被测试的人分别做出回答。观测者能通过电传打字机与机器和人联系。被测人在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维方式和思维过程。如果试验主持人听取他们各自的答案后，分辨不清哪个是人回答的，哪个是机器回答的，则可以认为该计算机具有了智能。这是一种行为主义的思想，如今看来并不正确。 图灵测试的重要意义：使实验研究智能行为成为可能,在1939年，图灵回到皇家学院。在第二次世界大战爆发期间，他进入了英国外交部，从事对德国密码的分析工作。他对破译机

41、械的德国密码机enigma的密码作出了重要贡献，在赢得这次战争中起到了重要作用。 1954年，图灵服氰化物自杀，没有留下遗言作明确解释。（事实上可能与图灵是同性恋有关，图灵因此被化学去势。）此外，图灵具有典型的荒岛心态来源于鲁滨逊漂流记亦即尽可能的自行制造所需的一切，譬如肥皂等，甚至连图灵自杀的氰化钾都是自己提炼的。,丘奇,丘奇(alonze church，1903-1995) 出生于华盛顿特区。 曾在哥廷根跟随希尔伯特学习，后来转到阿姆斯特丹。 从1927年到1967，执教于普林斯顿大学 1967年调到加州大学洛衫矶分校(ucla)。 是符号逻辑学会(association of symbolic logic)的创始人。对可计算性理论作出了实质性的贡献，其中包括对判定问题的解、演算的发明，以及对现今称为丘奇图灵论题的陳述。 在90岁生日后还发表文章,代换实例,定义4.9 设a0是含有命题变项p1,p2,pn的命题公式，a1,a2,an是n个谓词公式，用ai(1in)处处代替a0中的pi，所得公式a称为a0的代换实例,例如，f(x)g(x), xf(x)yg(y)等都是pq的代换实例，而x(f(x)g(x)等不是pq的代换实例,定理4.2 重言式的代换实例都是永真式，矛盾式的