第四章 一阶逻辑基本概念

null第四章 一阶逻辑基本概念 第四章 一阶逻辑基本概念 1.准确地将给出的命符号化： ①当给定个体域时, 在给定个体域内将命题符号化 ②当没给定个体域时, 应在全总个体域内符号化 ③在符号化时, 注意全称量词与蕴含联结词的搭配, 存在量词与合取联结词的搭配.   2. 深刻理解逻辑有效式、矛盾式、可满足式的概念.   3. 记住闭式的性质：在任何解释下均为命题.   4. 对给定的解释, 会判别公式的真值或不能确定真值. null 命题逻辑中，命题是最基本的单位，简单命题不能再分解，并且不考虑命题之间的内在联系，因此有局限性，甚至无法判断一些简单命题。因此，需将简单命题再细分，分析出个体词、谓词、量词，以便达个体与总体的内在联系和数量关系，这是一阶逻辑要研究的内容。 null一、一阶逻辑的符号化 个体词：个体词是指所研究对象中可以独立存在的具体的或抽象的客体. 例如, 小王, 小李, 中国, , 3等都可以作为个体词. 将表示具体或特定的客体的个体词称作个体常项, 一般用小写英文字母a, b, c…表示；而将表示抽象或泛指的个体词称为个体变项, 常用x, y, z…表示. 称个体变项的取值范围为个体域(或称论域). 个体域可以是有穷集合, 例如, {1, 2, 3}, {a, b, c, d}, {a, b, c, …, x, y, z}, …；也可以是无穷集合, 例如, 自然数集合N={0, 1, 2, …}, 实数集合R={x|x是实数}…. 有一个特殊的个体域, 它是由宇宙间一切事物组成的, 称它为全总个体域. 本课程在论述或推理中如没有指明所采用的个体域, 都是使用全总个体域.  谓词：谓词是用来刻画个体词性质及个体词之间相互关系的词. null考虑下面四个命题(或命题公式):          (1)是无理数.           (2)x是有理数.           (3)小王与小李同岁.   (4)x与y具有关系L 同个体词一样, 谓词也有常项和变项之分. 表示具体性质或 关系的谓词称为谓词常项, 表示抽象的、泛指的性质或关系的谓词称为谓词变项. 无论是谓词常项或变项都用大写英文字母F, G, H, …表示, 可根据上下文区分. 一般地, 用P(x1,x2,…,xn)表示含n(n≥1)个命题变项的n元谓词. n=1时, P(x1)表示x1具有性质P；n≥2时, P(x1,x2,…,xn)表示x1,x2,…,xn具有关系P.实质上, n元谓词P(x1,x2,…,xn)可以看成以个体域为定义域, 以{0,1}为值域的n元函数或关系. 它不是命题. 要想使它成为命题, 必须用谓词常项取代P, 用个体常项a1,a2,…,an取代x1,x2,…,xn, 得P(a1,a2,…,an)是命题. null例4.1 将下列命题在一阶逻辑中用0元谓词符号化, 并讨论它们的真值:          (1)只有2是素数, 4才是素数.           (2)如果5大于4, 则4大于6. 解 (1)设一元谓词F(x):x是素数, a:2, b:4. (1)中命题符号化为0元谓词的蕴涵式:             F(b)→F(a) 由于此蕴涵前件为假, 所以(1)中命题为真.         (2) 设二元谓词G(x,y):x大于y, a:4, b:5, c:6. G(b,a), G(a,c)是两个0元谓词, 把(2)中命题符号化为             G(b,a)→G(a,c) 由于G(b,a)为真, 而G(a,c)为假, 所以(2)中命题为假.  null量词 有了个体词和谓词之后, 有些命题还是不能准确的符号化, 原因是还缺少表示个体常项或变项之间数量关系的词. 称表示个体常项或变项之间数量关系的词为量词. 量词可分两种: (1) 全称量词      日常生活和数学中所用的“一切的”, “所有的”, “每一个”, “任意的”, “凡”, “都”等词可统称为全称量词, 将它们符号化为“”. 并用 x,  y等表示个体域里的所有个体, 而用 xF(x),  yG(y)等分别表示个体域里所有个体都有性质F和都有性质G.      (2) 存在量词      日常生活和数学中所用的“存在”, “有一个”, “有的”, “至少有一个”等词统称为存在量词, 将它们都符号化为“”. 并用 x,  y等表示个体域里有的个体, 而用 xF(x),  yG(y)等分别表示个体域里存在个体具有性质F和存在个体具有性质G等.  null一阶逻辑命题符号化 例4.2 在个体域分别限制为(a)和(b)条件时, 将下面两个命题符号化:      (1) 凡人都呼吸.       (2) 有的人用左手写字.       其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域. null解 (a)令F(x):x呼吸. G(x):x用左手写字.  (1) 在D1中除了人外, 再无别的东西, 因而“凡人都呼吸”应符号化为 ：xF(x)                (4.1) (2) 在D1中的有些个体(人)用左手写字, 因而“有的人用左手写字”符号化为： xG(x)                (4.2)    (b) D2中除了有人外, 还有万物, 因而在(1), (2)符号化时, 必须考虑将人分离出来. 令M(x):x是人. 在D2中, (1), (2)可以分别重述如下:         (1)对于宇宙间一切事物而言, 如果事物是人, 则他要呼吸.          (2)在宇宙间存在着用左手写字的人.  于是(1), (2)的符号化形式分别为           x(M(x)→F(x))         (4.3) 和        x(M(x)∧G(x))         (4.4) 其中F(x)与G(x)的含义同(a)中.  null例4.3 在个体域限制为(a)和(b)条件时, 将下列命题符号化: (1) 对于任意的x, 均有x2-3x+2=(x-1)(x-2).        (2) 存在x, 使得x+5=3. 其中: (a)个体域D1=N(N为自然数集合)       (b)个体域D2=R(R为实数集合) 解 (a)令F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3. 命题(1)的符号化形式为 ：  xF(x)               (4.7) 命题(2)的符号化形式为 ：  xG(x)               (4.8) 显然(1)为真命题；而(2)为假命题, 因为N不含负数.       (b) 在D2内, (1)和(2)的符号化形式还是(4.7)式和(4.8)式, (1)依然是真命题, 而此时(2)也是真命题.  null 从例4.2和例4.3可以看出以下两点: 1. 在不同个体域内, 同一个命题的符号化形式可能不同, 也可能相同.  2. 同一个命题, 在不同个体域中的真值也可能不同. null  例4.4 将下列命题符号化, 并讨论真值.  (1)所有的人都长着黑头发.       (2)有的人登上过月球.  (3)没有人登上过木星.           (4)在美国留学的学生未必都是亚洲人.  null解 由于本题没有提出个体域, 因而应该采用全总个体域, 令M(x):x为人.  (1)令F(x):x长着黑头发. 命题(1)符号化为 ：  x(M(x)→F(x))            (4.9) 设a为某个金发姑娘, 则M(a)为真, 而F(a)为假, 所以M(a)→F(a)为假, 故(4.9)所表示的命题为假.   (2)令G(x):x登上过月球. 命题(2)的符号化形式为          x(M(x)∧G(x))            (4.10) 设a是1969年登上月球完成阿波罗的一个美国人, 则M(a)∧G(a)为真, 所以(4.10)表示的命题为真.  (3)令H(x):x登上过木星. 命题(3)符号化形式为              ┐  x(M(x)∧H(x))          (4.11) 到目前为止, 对于任何一个人(含已经去世的人)都还没有登上过木星, 所以对任何人a, M(a)∧H(a)均为假, 因而 x(M(x)∧H(x))为假, 所以(4.11)表示的命题为真.      (4)令F(x):x是在美国留学的学生, G(x):x是亚洲人. 命题(4)符号化形式为              ┐  x(F(x)→G(x))          (4.12) 这个命题也为真.  null 例4.5 将下列命题符号化:       (1) 兔子比乌龟跑得快.        (2) 有的兔子比所有的乌龟跑得快.        (3) 并不是所有的兔子都比乌龟跑得快.        (4) 不存在跑得同样快的两只兔子.   解 本题没有指明个体域, 因而采用全总个体域. 因为本例中出现二元谓词, 因而引入两个个体变项x与y.令F(x):x是兔子, G(y):y是乌龟, H(x,y):x比y跑得快, L(x,y):x与y跑得一样快. 这4个命题分别符号化为           x  y(F(x)∧G(y)→H(x,y))     (4.13)           x(F(x)∧  y(G(y)→H(x,y))   (4.14)       ┐  x  y(F(x)∧G(y)→H(x,y))    (4.15)       ┐  x  y(F(x)∧F(y)∧L(x,y))    (4.16) 注意注意1. 一般说来, 多个量词出现时, 它们的顺序不能随意调换. 例如, 考虑个体域为实数集, H(x,y)表示x+y=10, 则命题“对于任意的x, 都存在y, 使得x+y=10”的符号化形式为                 x  yH(x,y)             (4.17) 所给命题显然为真命题. 但是如果改变两个量词的顺序, 得                 y  xH(x,y)             (4.18) (4.18)已经不表示原命题, 而且它所表示的命题是假命题.  2. 有些命题的符号化形式可不止一种. 例如, 在例4.5中, (3)还可以符号化为  x  y(F(x)∧G(y)∧┐H(x,y))      (4.19) (4)还可以符号化为  x  y(F(x)∧F(y)→┐L(x,y))      (4.20) 这样, 4.15)和(4.19)都是(3)的符号化形式, (4.16)与(4.20)都是(4)的符号化形式, 它们都是正确的.      由于引进了个体词, 谓词和量词的概念, 现在可以将本章开始时讨论的推理在一阶逻辑中符号化为如下形式:                x(F(x)→G(x))∧F(a)→G(a)       (4.21) 其中, F(x):x是偶数, G(x):x能被2整除, a:6.下一章可以证明(4.21)是永真式.  4.2 一阶逻辑公式及解释 4.2 一阶逻辑公式及解释 一阶语言 一阶语言用来定义一阶谓词逻辑形式系统中的形式语言, 即定义符号集与公式集. 下一章将定义推理规则.   定义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       (4)谓词符号:F,G,H,…,Fi,Gi,Hi, …, i≥1       (5)量词符号:,       (6)联结词符号:┐,∧,∨,→,       (7)括号与逗号:(,),,  上节(4.1)～(4.21)所用符号均为字母表中的符号.  null定义4.2 F的项的定义如下:       (1)个体常项和个体变项是项.        (2)若f(x1,x2,…,xn)是任意的n元函数, t1,t2,…,tn是任意的n个项, 则f(t1,t2,…,tn)是项.        (3)所有的项都是有限次使用(1), (2)得到的.    定义4.3 设R(x1,x2,…,xn)是的任意n元谓词,  t1,t2,…,tn是的任意的n个项, 则称R(t1,t2,…,tn)是的原子公式.  null 定义4.4 的合式公式定义如下:       (1)原子公式是合式公式.        (2)若A是合式公式, 则(┐A)也是合式公式.        (3)若A, B是合式公式, 则(A∧B), (A∨B), (A→B), (AB)也是合式公式.        (4)若A是合式公式, 则xA, xA也是合式公式.        (5)只有有限次的应用(1)～(4)构成的符号串才是合式公式.        的合式公式也称为谓词公式, 简称公式.  null二、自由与约束 下面讨论一阶公式的一些性质.  定义4.5 在公式xA和xA中, 称x为指导变元, A为相应量词的辖域. 在x和x的辖域中, x的所有出现都称为约束出现. A中不是约束出现的其他变项均称为是自由出现的.  null例4.6 指出下列各公式中的指导变元, 各量词的辖域,自由出现以及约束出现的个体变项:      (1) x(F(x,y)→G(x,z))                      (4.22)      (2) x(F(x)→G(y))→  y(H(x)∧L(x,y,z))   (4.23)  解(1)x是指导变元. 量词的辖域A=(F(x,y)→G(x,z)), 在A中, x是约束出现的. 而且约束出现两次, y和z均为自由出现的, 而且各自由出现一次.      (2)公式中含有两个量词, 前件上的量词的指导变元为x, 的辖域A=(F(x)→G(y)), 其中x是约束出现的, y是自由出现的. 后件中的量词的指导变元为y, 的辖域为(H(x)∧L(x,y,z)), 其中y是约束出现的, x, z均为自由出现的. 在整个公式中, x约束出现一次, 自由出现2次, y自由出现一次, 约束出现一次, z只自由出现一次.  null三、闭公式 定义4.6 设A是任意的公式, 若A中不含有自由出现的个体变项, 则称A为封闭的公式, 简称闭式.  易知(4.1)～(4.21)以及(4.24)都是闭式, 而(4.22)和(4.23)则不是闭式. 要想使含有r(r≥1)个自由出现个体变项的公式变成闭式, 至少要加上r个量词, 将公式(4.22)加上两个量词就变成了闭式(4.24). 类似的, 也可以用加量词的方法将(4.23)变成闭式.  null例4.7 将下列两个公式中的变项指定成常项使其成为命题: (1)x(F(x)→G(x))                            (4.25) (2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))  (4.26) 解 (1)指定个体变项的变化范围, 并且指定谓词F, G的含义, 下面给出两种指定法:      (a)令个体域D1为全总个体域, F(x)为x是人, G(x)为x是黄种人, 则(4.25)表达的命题为“所有人都是黄种人”, 这是假命题.      (b)令个体域D2为实数集合R, F(x)为x是自然数, G(x)为x是整数, 则(4.25)表达的命题为“自然数都是整数”, 这是真命题.     (2)(4.26)中含有两个2元函数变项, 两个1元谓词变项, 两个2元谓词变项. 指定个体域为全总个体域, F(x)为x是实数, G(x,y)为x≠y, H(x,y)为x>y, f(x,y)=x2+y2, g(x,y)=2xy, 则(4.26)表达的命题为“对于任意的x, y, 若x与y都是实数, 且x≠y, 则x2+y2>2xy”, 这是真命题. 如果H(x,y)改为x