【5A版】谓词逻辑

《【5A版】谓词逻辑》由会员分享，可在线阅读，更多相关《【5A版】谓词逻辑（91页珍藏版）》请在金锄头文库上搜索。

1、第2章 谓词逻辑,2.1 个体、 谓词与命题函数 2.2 量词 2.3 谓词公式与翻译 2.4 谓词演算的推理理论 2.5 前束范式 习 题 2,2. 个体、 谓词与命题函数,2.1.1 个体与谓词 在谓词逻辑中, 我们首先对原子命题加以分解, 引入个体和谓词的概念。 例1 讨论以下原子命题: (1) 张三是共青团员。 (2) 100 是自然数。 (3) 马列主义是真理。,定义 2.11 一个可以独立存在的物体称为个体。 个体可以是抽象的, 如“马列主义”; 也可以是具体的, 如“100”。 个体常用小写字母a, b, c等表示。,例2 讨论以下原子命题: (1) 25。 (2) 南京位于武汉

2、和上海之间。 原子命题(1)可以分解为个体“2”、 “5”和“”两部分; 原子命题(2)可以分解为个体“南京”、 “武汉”、 “上海”和“位于和之间”两部分。 我们将例2中的“”和“位于和之间”也称为谓词, 它们表示了两个和两个以上个体之间的关系。,定义 2.12 用于刻画个体的性质或个体间关系的词称为谓词。 谓词常用大写字母, , 等表示。 如用表示谓词“是共青团员”, a 表示个体“张三”, b表示个体“李四”, 则命题“张三是共青团员”和“李四是共青团员”可分别用(a)和(b) 表示。,例3 将下列命题符号化: (1) 赵子龙救出阿斗。 解 设 P: 救出 。 a: 赵子龙。 b: 阿斗

3、。 则原命题可表示为P(a,b)。,(2) 如果你不出去, 我就不进来。 解 设 P: 出去。 Q: 进来。 a: 你。 b: 我。 则原命题可表示为 P(a) Q(b)。,(3) 123是偶数当且仅当2整除123。 解 设 A: 是偶数。 B: 整除。 a: 2。 b: 123。 则原命题可表示为A(b)B(a,b)。,2.1.2 命题函数 定义 2.13 一个命题函数由n个个体变元和n元谓词组成。 由n个个体变元x1, x2, , xn及n元谓词P所组成的命题函数记为P(x1, x2, , xn)。 这种命题函数以个体域为定义域, 以真值, 1所组成的集合为值域（关于函数、 定义域、 值域

4、的概念见第5章）。,2.2 量 词,有了个体、 谓词、 命题函数的概念以后, 能不能将本章开始所讲的三段论方法正确地符号化呢？以下面的断言为例: P: 凡人要死。 Q: 苏格拉底是人。 R: 苏格拉底要死。,令 H(x): x是人。 M(x): x要死。 a: 苏格拉底。,2.2.1 全称量词 命题“凡人要死”也可以说“对所有的x, 如果x是人, 则x要死”。 这种涉及到普遍性问题的命题还可以举出很多。,例如: 对任意一个x, 如果x是自然数, 则x是实数。 对每一个x, x是偶数当且仅当2整除x。 为表示上面所讲的“对所有的x”、 “对任意一个x”、 “对每一个x”, 我们引入全称量词的概念

5、。,定义 2.21 符号x表示“对所有的x”、 “对任意一个x”、 “对每一个x”, 称为全称量词。 例1 把下面命题符号化:,(1) 凡人要死。 解 设 H: 是人。 M: 要死。 则原命题可以表示为x(H(x)M(x)。 (2) 所有的自然数都是实数。 解 设 N: 是自然数。 R: 是实数。 则原命题可以表示为x(N(x)R(x)。,(3) 对每一个x, x是偶数当且仅当2整除x。 解 设 : 是偶数。 2|x: 2整除x。 则原命题可以表示为x(x)2|x)。,2.2.2 存在量词 定义 2.22 符号x表示“对某一个x”、 “至少存在某一个x”、 “存在某一个x”, 称为存在量词。,

6、例2 把下面命题符号化: (1) 至少有一个人不死。 解 设 H: 是人。 M: 要死。 则原命题可以表示为x(H(x)M(x) (2) 所有的苹果都是红的。 解 设 P: 是苹果。 M: 是红的。 则原命题可以表示为x(P(x)Q(x),(3) 我看见一朵香花。 解 设 P: 看见。 Q: 香。 R: 是花。 a: 我。 则原命题可表示为x(P(a,x)Q(x)R(x)。,2.3 谓词公式与翻译,2.3.1 谓词公式 在命题逻辑中我们引入了命题公式的概念, 它是由命题常元、 命题变元、 命题联结词和圆括号按照一定的规律所组成的符号串。 谓词逻辑是命题逻辑的进一步延伸, 在谓词逻辑中我们也相应

7、地引入原子谓词公式和谓词公式的概念。,定义 2.31 (1) 一个命题是原子谓词公式; (2) 一个命题变元是原子谓词公式; (3) 由n个个体变元x1, x2, , xn及n 元谓词P所组成的命题函数 P(x1, x2, , xn) 也是一个原子谓词公式。 原子谓词公式简称为原子公式。,定义 2.32 (1) 一个原子公式是一个谓词公式; (2) 若A是谓词公式, 则A也是谓词公式; (3) 若A、 B是谓词公式, 则(AB)、 (AB)、 (AB)、 (AB)也是谓词公式; (4) 若A是谓词公式, x是A中的个体变元, 则(xA)、 (xA)也是谓词公式; (5) 只有有限次地运用规则(

8、1)、(2)、 (3)、(4)所得到的符号串才是谓词公式。 谓词公式也简称为公式。,例1 对下列不同的个体域, 用谓词公式表示命题“所有的自然数都大于”: (1) 自然数集合。 解 个体域是自然数集合时, 原命题可以表示为 x(x0)。 (2) 实数集合。 解 设 N: 是自然数。 因为个体域是实数集合, 所以原命题可表示为 x(N(x)(x0)。 例1说明, 对不同的个体域, 同一命题可能有不同形式的谓词公式, 这对我们讨论问题是很不方便的。 为了统一起见, 我们使用全总个体域的概念。,定义 2.33 由所有个体组成的集合称作全总个体域。 以后若无特别的说明, 我们都约定在全总个体域中讨论问

9、题, 这样个体变元的变化范围就一致了。 定义 2.34 在全总个体域中, 表示特殊个体域中个体的谓词称为特性谓词。,2.3.2 命题的符号化 例2 将下列命题符号化: (1) 人都要犯错误。 解 该命题可以说成“对于所有的x, 如果x是人, 则x要犯错误”。 设 H(x): x是人。 Q(x): x犯错误。 则命题可表示为x(H(x)Q(x)。,(2) 有些孩子是神童。 解 该命题可以说成“有些x, x是孩子且x是神童”。 设 (x): x是孩子。 (x): x是神童。 则命题可表示为x(x)(x)。,例3 将下列命题符号化: (1) 李涛无书不读。 解 该命题即是说“李涛所有的书都读”。 设

10、 P: 是书。 Q: 读。 a: 李涛。 则命题可表示为x(P(x)Q(a,x)。 (2) 有些人聪明, 但不是所有的人都聪明。 解 设 H: 是人。 B: 聪明。 则命题可表示为x(H(x)B(x)(x(H(x)B(x)。,(3) 如果b24ac 0, 则实系数一元二次方程 ax2bxc0 有实数解。 解 设 R: 是实数, 并将数学中的运算符“”、 “”、 “”、 “”等作谓词使用, 则命题可表示为 R(a)R(b)R(c)(b24ac 0) x(R(x)(ax2bxc0) 用多元谓词表示命题, 往往要用到多个量词。,例 把下列命题用谓词公式表示: (1) 对所有的正数x、 y, 都有xy

11、0。 解 该命题可以说成“对所有的x和y, 如果x、 y是正数, 则xy0”, 所以用谓词公式表示时要用到两个量词。 设 P: 是正数。 则该命题可表示为x(y(P(x)P(y)(xy0)。,(2) 对所有的自然数x和y, 都有自然数z, 使得xyz。 解 设 N: 是自然数。 则该命题可以表示为 xyz(N(x)N(y)N(z)(xyz) (1) 注: 该命题显然是真命题。 若将命题修改为“存在自然数z, 使得对一切自然数x、 y, 都有xyz”, 则修改后的命题可符号化为 zxy(N(x)N(y)N(z)(xyz) (2),例5 将函数极限的定义 (a, A是实数)在实数集中符号化。 解

12、的具体含义是: 任给, 存在一个, 使得|xa|时有|f (x)A|. 因此, 在实数集中， 可表示为 (0)(0)x(0|xa|) (|f(x)A|),2.3.3 自由变元和约束变元 在2.节中, 我们曾经讲过, 公式H(x)M(x)中的x是个体变元, 它可以取任何个体, 而公式 x(H(x)M(x)中的x不再起变元作用, 它被量词x限制住了。 为了区分这两种变元, 我们引入自由变元和约束变元的概念。,定义 2.35 在一个谓词公式中, 形如xA(x)或 xA(x) 的那一部分称为是公式的x约束部分, 而A(x)称为是量词x或x的辖域。 x在公式的x约束部分的任一出现都称为是x的约束出现。

13、若x的出现不是约束出现, 则称为是x的自由出现。 为简便起见, 如果辖域是一个原子公式, 则可以省略括号。,例 指出下列公式的辖域和变元约束的情况: (1) xP(x)Q (2) x(P(x)yQ(x,y) (3) xP(x)yQ(x,y) (4) xy(P(x,y)Q(y,z)xP(x,y),解 (1) x的辖域是P(x), x的所有出现都是约束出现。 (2) x的辖域是P(x)yQ(x,y); y的辖域是Q(x,y)。 x和y的所有出现都是约束出现。 (3) x的辖域是P(x); y的辖域是Q(x,y)。 y的所有出现都是约束的; x除最后一次出现是自由的外, 其余都是约束出现。,(4)

14、x的辖域是y(P(x,y)Q(y,z); y的辖域是P(x,y)Q(y,z); x的辖域是P(x,y)。 x的所有出现都是约束出现; y除最后一次出现是自由的外, 其余都是约束出现; z的出现是自由的。,定义 2.36 一个公式中, 约束出现的变元叫约束变元, 自由出现的变元叫自由变元。 在本节开头所提到的公式H(x)M(x)中, x是自由变元; 而公式x(H(x)M(x)中的x是约束变元。 前者是命题函数, 后者是命题。 一般地, 一个谓词公式如果表示一个命题, 则公式中的所有变元都是约束变元; 如果公式中出现自由变元, 则该公式是一个命题函数。,为了使改名后的公式中出现的变元要么是约束的,

15、 要么是自由的, 我们提出如下的改名规则: (1) 约束变元在改名时, 必须将在量词及其辖域中出现的该变元一起更改, 公式的其余部分不变。 (2) 改名时一定要选用量词的辖域中没有出现的变元符号。,例7 将例中(3)、 (4)、 (5)题的约束变元改名。 解 (3)中的公式改名为 zP(z)yQ(x,y) (4) 中的公式改名为 uv(P(u,v)Q(v,z)xP(x,y) (5) 中的公式改名为 tP(t)R(x,y),2.4 谓词演算的推理理论,2.4.1 谓词演算的等价式和蕴含式 定义 2.41 当谓词公式中的自由变元用其个体域中确定的个体代入, 命题变元用确定的命题代入时, 这样一组确定的个体和命题称为该公式的一组指派。 例1 若个体域为1, 2, 3, 试对谓词公式 x(x=y)(x2=y)的任一组指派讨论其真值。,解 公式x(x=y)(x2=y)中只有自由变元y, 而