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)xy(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