2.2谓词公式与解释
- 格式：ppt
- 大小：189.00 KB
- 文档页数：19
下载文档原格式
合集下载
谓词公式与翻译(精)
（4）谓词
P（x）为P（a）= 0，P（b）= 1；
Q（x，y）为Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）
= 1；
L（x，y）为L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）=
1。
求下列公式在解释I下的真值
2）x（ P（f（x））∧Q（x，f（x）））；
在解释I下
5
2.3 谓词公式与翻译
由例可知，对于命题翻译成谓词公式时，机动性很大，由于对个 体描述性质的刻划深度不同，就可翻译成不同形式的谓词公式。
例如：这只大红书柜摆满了那些古书
解法1：
解法2：
设：F(x,y): x摆满了y
设：F(x,y): x摆满了y
R(x): x是大红书柜
x（ P（f（x））∧Q（x，f（x）））
=（ P（f（a））∧Q（a，f（a）））∨（ P（f（b））∧Q（b，f
（b）））
=（ P（b）∧Q（a，b））∨（ P（a）∧Q（b，a））
=（ 1∧1）∨（ 0∧1）
= 1∨0
= 1 2019/6/3
10
【例2.2.1】给定解释I如下
（1）U =｛a，b｝；
人总是要犯错误的。
解：设F(x)：x犯错误，M(x)：x是人。则上句符
号化为：
(a) ┒(x)(M(x)⋀┒F(x)) (b) x(M(x)→F(x)) 【例2】尽管有人聪明但未必一切人都聪明。
解：设P(x)：x聪明，M(x)：x是人。则上句符号 化为：
2019/6/3 x(M(x)⋀P(x))⋀┒(x(M(x)→P(x)))
2019/6/3
7
2.3 谓词公式与翻译
最新2.2谓词公式与解释
四、谓词公式的类型
西
设A是公式。如果A在任何的解释下都
华
大 是真的，则A是永真式；如果A在任何的
学 解释下都是假的，则A是永假式；如果A
在一些解释下为假，一些解释下为真，
则A是非永真的可满足式。
例如： x A(x) x A(x)是永真式； x A(x)∧x A(x）是永假式。
代换实例
西华设A0是含命题变元p1, p2, …, pn的命题逻辑公式，
2.2谓词公式与解释
一、合式公式的定义：
原子公式： f(x1,x2,,xn) 为n元谓词符号，t1,t2,…,tn 是
项，则 f(t1,t2,,tn) 是原子公式；
西 合式公式的归纳定义：
华 大
1、任意的原子公式是公式
学 2、若A是公式，则xA、xA是公式；
3、若A、B是公式，则 A、A∧ B、A∨B、A → B、A B是 公式；
2. 对于某些简单的公式，特别对于简单的闭式，
西 华
可在假定给定任意解释的前提下该公式的真值
大 学
都为真（或者为假）来证明该公式是永真式
（或矛盾式）。
3. 要证明一个公式是可满足式，只要找到一个 解释，使得该公式的真值为真即可。同时为了 证明它不是永真式，只要找一个解释，使得该 公式的真值为假即可。
解释的说明
(1) 一个谓词公式如果不含自由变元,则在一个解释下, 可以得到确定的真值,不同的解释下可能得到不同的 真值。
(2) 公式的解释并不对变元进行指定,如果公式中含有自 由变元,即使对公式进行了一个指派,也得不到确定的 真值,其仅是个命题函数,但约束变元不受此限制。
3）有公式的解释定义可以看出,公式的解释有许多的解 释,当D为无限集时,公式有无限多个解释,根本不可能 将其一一列出,因而谓词逻辑的公式不可能有真值表 可列。
谓词公式的分类与解释
第二节 谓词公式的分类与解释为了给出谓词公式的定义，先给出项和原子公式的定义。
定义2.1 项：（1） 个体常项和个体变项是项；（2） 设),...,,(21n x x x ϕ是任意的n 元函数，n t t t ,...,,21是项，则),...,,(21n t t t ϕ是项；（3） 有限地使用（1），（2）形成的符号串是项。
定义2.2 设),...,,(21n x x x R 是任意的n 元谓词，n t t t ,...,,21是项，则称),...,,(21n t t t R 是原子公式。
定义2.3合式公式：（1） 原子公式是合式公式；（2） 若A 是合式公式，则)(A ¬也是合式公式；（3） 若B A ,是合式公式，则)(),(),(),(B A B A B A B A ↔→∨∧也是合式公式；（4） 若A 是合式公式，则(),()xA xA ∀∃也是合式公式。
其中x 为任意的个体变项；（5） 有限次地应用（1）～（4）形成的字符串是合式公式。
这样定义的合式公式又称作谓词公式，简称公式。
合式公式的最外层括号可以省去。
定义2.4（1） 在公式xA ∀和xA ∃中，A 是相应量词的辖域，x 称为指导变量。
（2） 在公式xA ∀和xA ∃中，x 的所有出现都是约束出现的，不是约束出现的变项称为自由出现的。
例如：在公式))),,()((),((z y x L y G y y x F x ∧∃→∀中，∀的辖域为))),,()((),((z y x L y G y y x F ∧∃→∃的辖域为)),,()((z y x L y G ∧x ∀中的x 和y ∃中的y 都是指导变量。
x 的出现都是约束的，),(y x F 中的y 是自由出现的，)(y G 与),,(z y x L 中的y 是约束出现的，z 的出现是自由的。
一般情况下，在一个谓词公式A 中，除了可能含若干个个体常项，函数常项，谓词常 项外，还可能含个体变项，函数变项，谓词变项等。
谓词逻辑I 谓词、量词与谓词公式
如 F(x)G(x), xF(x)yG(y)是pq的代换实例 定理 重言式的代换实例都是重言式，矛盾式的代 换实例都是矛盾式.
26
实例
例 判断下列公式的类型 (1) ∀xF(x)→∃xF(x)；
设I为任意的解释，若∀xF(x)为假，则 ∀xF(x)→∃xF(x)为真. 若∀xF(x)为真，则∃xF(x)也为 真，所以∀xF(x)→∃xF(x)恒为真. 是逻辑有效式. (2) ∀xF(x)→(∀x∃yG(x,y)→∀xF(x))； 重言式p→(q→p) 的代换实例，是逻辑有效式.
7
基本概念 —谓词：0元谓词
例 将命题“2是素数且是偶数”用0元谓词 符号化 设F(x)：x是素数； G(x)：x是偶数；a: 2 则F(a)G(a)表示“2是素数且是偶数” F(a)和G(a)都是0元谓词，不仅如此 F(a)G(a)也是0元谓词， F(x)G(x)是一个1 元谓词，表示x既是素数又是偶数这一性质. 以个体常元a代入x，从而消去个体变元，便 得到0元谓词F(a)G(a)
10
例 (续 )
(2) 2 是无理数仅当 3是有理数 在命题逻辑中, 设 p： 2 是无理数，q： 3 是有理数. 符号化为 p q 在谓词逻辑中, 设F(x): x是无理数, G(x): x是有理数 符号化为 F ( 2 ) G( 3 ) (3) 如果2>3，则3<4 在命题逻辑中, 设 p：2>3，q：3<4. 符号化为 pq 在谓词逻辑中, 设 F(x,y)：x>y，G(x,y)：x<y, 符号化为 F(2,3)G(3,4)
基本概念 ——谓词：元数
谓词的元数: 谓词中包含的个体的个数， 例如 F(x,y,z)含有三个个体，其元数为3 一元谓词: 表示事物的性质或状态，如F(苏) 多元谓词 (n元谓词, n2): 表示事物之间的 关系. 例如 L(x,y)表示x与y有L关系， 若L表示…大于…，则L(x,y)表示x>y， 若 L 表示 …是 … 的妻子，则 L( 圆 , 又 ) 表示 高圆圆是赵又廷的妻子. n 元谓词规定了 n个个体的顺序，不可随意颠 倒 . 例如 L(圆,又)不能写L(又,圆)
26
实例
例 判断下列公式的类型 (1) ∀xF(x)→∃xF(x)；
设I为任意的解释，若∀xF(x)为假，则 ∀xF(x)→∃xF(x)为真. 若∀xF(x)为真，则∃xF(x)也为 真，所以∀xF(x)→∃xF(x)恒为真. 是逻辑有效式. (2) ∀xF(x)→(∀x∃yG(x,y)→∀xF(x))； 重言式p→(q→p) 的代换实例，是逻辑有效式.
7
基本概念 —谓词：0元谓词
例 将命题“2是素数且是偶数”用0元谓词 符号化 设F(x)：x是素数； G(x)：x是偶数；a: 2 则F(a)G(a)表示“2是素数且是偶数” F(a)和G(a)都是0元谓词，不仅如此 F(a)G(a)也是0元谓词， F(x)G(x)是一个1 元谓词，表示x既是素数又是偶数这一性质. 以个体常元a代入x，从而消去个体变元，便 得到0元谓词F(a)G(a)
10
例 (续 )
(2) 2 是无理数仅当 3是有理数 在命题逻辑中, 设 p： 2 是无理数，q： 3 是有理数. 符号化为 p q 在谓词逻辑中, 设F(x): x是无理数, G(x): x是有理数 符号化为 F ( 2 ) G( 3 ) (3) 如果2>3，则3<4 在命题逻辑中, 设 p：2>3，q：3<4. 符号化为 pq 在谓词逻辑中, 设 F(x,y)：x>y，G(x,y)：x<y, 符号化为 F(2,3)G(3,4)
基本概念 ——谓词：元数
谓词的元数: 谓词中包含的个体的个数， 例如 F(x,y,z)含有三个个体，其元数为3 一元谓词: 表示事物的性质或状态，如F(苏) 多元谓词 (n元谓词, n2): 表示事物之间的 关系. 例如 L(x,y)表示x与y有L关系， 若L表示…大于…，则L(x,y)表示x>y， 若 L 表示 …是 … 的妻子，则 L( 圆 , 又 ) 表示 高圆圆是赵又廷的妻子. n 元谓词规定了 n个个体的顺序，不可随意颠 倒 . 例如 L(圆,又)不能写L(又,圆)
第2章 谓词逻辑
构和命题之间的关系。如，在命题逻辑中，“张三是大学生”和“李四 是大学生”之间的关系是无法表达的，现在可用谓词“„是大学生”及
个体“张三”、“李四”刻画之；再如， “张三和李四是表兄弟”，
在命题逻辑中也是无法刻画其内在结构的，现在可用谓词“„和„是表 兄弟”及个体“张三”、“李四”刻画之。 命题变元是真值不确定的陈述句，反映在上述结构中，就是由个体 或谓词不确定来体现。
(3)李林比张强高。
(4)如果你不出去，我就不进来。 解 (1)符号化为S(a)∧S(b)，其中，S(x)：x是三好学生，
a：张三，b：李四。
2015-7-10
第2章 谓词逻辑 (2)符号化为Q(a)∨R(a)，其中，Q(x)：x是象棋迷， R(x)：x是围棋迷，a：赵斌。 (3)符号化为T(a，b)，其中，T(x，y)：x比y高，a：李林，
2015-7-10
第2章 谓词逻辑 定义2.5 个体的取值范围称为个体域或论域；所有个体的 取值范围称为全总个体域。 一般情况下，如果没有特别说明，个体的取值范围为全总 个体域。当给定个体域后，个体常元为该个体域中的一个确定 的元素，个体变元则可取该个体域中的任一元素。
2015-7-10
第2章 谓词逻辑 例3 将下列命题符号化： (1)张三和李四都是三好学生。 (2)赵斌是象棋迷或围棋迷。
2015-7-10
第2章 谓词逻辑 定义2.2 表示具体或特定个体的词称为个体常元，用小写
字母a、b等表示。表示抽象或泛指个体的词称为个体变元，用x、
y等表示。
定义2.3 表示具体性质或关系的谓词称为谓词常元，表示 抽象或泛指的性质或关系的谓词称为谓词变元。谓词常元或谓 词变元都用大写字母F、G等表示。
束部分的任一出现都称为 x 的约束出现， x 称为约束变元，
个体“张三”、“李四”刻画之；再如， “张三和李四是表兄弟”，
在命题逻辑中也是无法刻画其内在结构的，现在可用谓词“„和„是表 兄弟”及个体“张三”、“李四”刻画之。 命题变元是真值不确定的陈述句，反映在上述结构中，就是由个体 或谓词不确定来体现。
(3)李林比张强高。
(4)如果你不出去，我就不进来。 解 (1)符号化为S(a)∧S(b)，其中，S(x)：x是三好学生，
a：张三，b：李四。
2015-7-10
第2章 谓词逻辑 (2)符号化为Q(a)∨R(a)，其中，Q(x)：x是象棋迷， R(x)：x是围棋迷，a：赵斌。 (3)符号化为T(a，b)，其中，T(x，y)：x比y高，a：李林，
2015-7-10
第2章 谓词逻辑 定义2.5 个体的取值范围称为个体域或论域；所有个体的 取值范围称为全总个体域。 一般情况下，如果没有特别说明，个体的取值范围为全总 个体域。当给定个体域后，个体常元为该个体域中的一个确定 的元素，个体变元则可取该个体域中的任一元素。
2015-7-10
第2章 谓词逻辑 例3 将下列命题符号化： (1)张三和李四都是三好学生。 (2)赵斌是象棋迷或围棋迷。
2015-7-10
第2章 谓词逻辑 定义2.2 表示具体或特定个体的词称为个体常元，用小写
字母a、b等表示。表示抽象或泛指个体的词称为个体变元，用x、
y等表示。
定义2.3 表示具体性质或关系的谓词称为谓词常元，表示 抽象或泛指的性质或关系的谓词称为谓词变元。谓词常元或谓 词变元都用大写字母F、G等表示。
束部分的任一出现都称为 x 的约束出现， x 称为约束变元，
谓词公式与翻译(精)
xP(x)→x Q(x)) ┒(x)P(x) ⋁x Q(x)
定义2:
设A为谓词公式，若在任何解释下，A的真值都为真，则 称A为永真式；
若至少存在一种解释，使A的真值为真，则称A为可满足 式；
若在任何解释下，A的真值都为假，则称A为矛盾式，矛 盾式也称不可满足式。
2019/6显/3 然，永真式是可满足式。
2019/6/3
7
2.3 谓词公式与翻译
2．谓词公式的解释 定义 谓词公式的一个解释I，由下面4部分组成 1）非空的论域U； 2）U中的特定的个体常项； 3）U上特定的函数； 4）U上特定的谓词。
若将谓词公式中的个体常项，函数和谓词分别指定 为U中的特定个体常项，U上特定的函数和U上特定的谓 词，即为该公式在解释I下的真值。
彐x(P(z)∧R(x,z)) 但是彐x(P(x)∧R(x,x))与彐x(P(z)∧R(x,y))这两种代入都是与
规则不符的。
2019/6/3
15
2.5谓词公式的等价与蕴涵
1、谓词逻辑中常见的等价与蕴含关系 谓词公式的赋值:
在谓词公式中常包含命题变元和客体变元，当客体 变元由确定的客体所取代，命题变元用确定的命题 所取代时，就称作对谓词公式的赋值。一个谓词公 式经过赋值以后，就成为具有确定真值T或F的命 题。
17
(1)命题逻辑中等价和蕴含的推广
在命题演算中，任一永真公式，其中同一命题变元， 用同一公式取代时，其结果也是永真公式。我们可以 把这个情况推广到谓词公式之中，当谓词演算中的公 式代替命题演算中永真公式的变元时，所得的谓词公 式即为有效公式，故命题演算中的等价公式表和蕴含 式表都可推广到谓词演算中使用。
例题 2 对x(P(x)→R(x,y))∧Q(x,y)换名。 解 可换名为： z(P(z)→R(z,y))∧Q(x,y)， 但不能改名为： y(P(y)→R(y,y))∧Q(x,y) 以及 z(P(z)→R(x,y))∧Q(x,y)。
2.2--谓词逻辑表示法
2013-7-9源自智能信息处理联合实验室制作
29
人工智能
7. 谓词逻辑表示知识的举例
例1：用谓词逻辑表示下列知识： 武汉是一个美丽的城市，但她不是一个沿海城市。 如果马亮是男孩，张红是女孩，则马亮比张红长得 高。 解：按照知识表示步骤，用谓词公式表示上述知识。 第一步：定义谓词如下： BCity(x)：x是一个美丽的城市 HCity(x)：x是一个沿海城市 Boy(x):x是男孩 Girl(x):x是女孩 High(x,y):x比y长得高
标点符号、括号、逻辑联结词、常量符 号集、变量符号集、n元函数符号集、n 元谓词符号集、量词
·谓词演算
合法表达式 (原子公式、合式公式)， 表达式的演算化简方法，标准式 (合取 的前束范式或析取的前束范式)
2013-7-9
智能信息处理联合实验室制作
14
人工智能
·语法元素
常量符号。
变量符号。
函数符号。
谓词符号。
联结词： ┐、∧、∨、→、 。
量词： 全称量词、 存在量词。和 后面跟着的x叫做量词的指导变元。
2013-7-9
智能信息处理联合实验室制作
15
人工智能
2 基本概念
函数符号与谓词符号 · 若函数符号f中包含的个体数目为n,则称f
为n元函数符号。 若谓词符号P中包含的个体数目为n,则称P为 n元谓词符号。 如：father(x)是一元函数,less(x,y)是二 元谓词. 一般一元谓词表达了个体的性质,而多元谓 词表达了个体之间的关系.
2013-7-9
智能信息处理联合实验室制作
8
人工智能
注意:
在命题逻辑中，每个表达式都是句 子，表示事实。 在谓词逻辑中，有句子，但是也有 项，表示对象。常量符号、变量和 函数符号用于表示项，量词和谓词 符号用于构造句子。
29
人工智能
7. 谓词逻辑表示知识的举例
例1：用谓词逻辑表示下列知识： 武汉是一个美丽的城市，但她不是一个沿海城市。 如果马亮是男孩，张红是女孩，则马亮比张红长得 高。 解：按照知识表示步骤，用谓词公式表示上述知识。 第一步：定义谓词如下： BCity(x)：x是一个美丽的城市 HCity(x)：x是一个沿海城市 Boy(x):x是男孩 Girl(x):x是女孩 High(x,y):x比y长得高
标点符号、括号、逻辑联结词、常量符 号集、变量符号集、n元函数符号集、n 元谓词符号集、量词
·谓词演算
合法表达式 (原子公式、合式公式)， 表达式的演算化简方法，标准式 (合取 的前束范式或析取的前束范式)
2013-7-9
智能信息处理联合实验室制作
14
人工智能
·语法元素
常量符号。
变量符号。
函数符号。
谓词符号。
联结词： ┐、∧、∨、→、 。
量词： 全称量词、 存在量词。和 后面跟着的x叫做量词的指导变元。
2013-7-9
智能信息处理联合实验室制作
15
人工智能
2 基本概念
函数符号与谓词符号 · 若函数符号f中包含的个体数目为n,则称f
为n元函数符号。 若谓词符号P中包含的个体数目为n,则称P为 n元谓词符号。 如：father(x)是一元函数,less(x,y)是二 元谓词. 一般一元谓词表达了个体的性质,而多元谓 词表达了个体之间的关系.
2013-7-9
智能信息处理联合实验室制作
8
人工智能
注意:
在命题逻辑中，每个表达式都是句 子，表示事实。 在谓词逻辑中，有句子，但是也有 项，表示对象。常量符号、变量和 函数符号用于表示项，量词和谓词 符号用于构造句子。
《应用离散数学》方景龙版-2.2 谓词公式及其解释
§2.2 谓词公式及其解释习题2.21. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）))()((y x Q x P x ，→∀ （2）)()(y x yQ y x xP ，，∃→∀（3）)())()((z y x xR z y Q y x P y x ，，，，∃∨∧∃∀解 （1）x ∀中的x 是指导变元；量词x ∀的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。
（2）x ∀中的x ，y ∃中的y 都是指导变元；x ∀的辖域是)(y x P ，，y ∃的辖域是)(y x Q ，；)(y x P ，中的x 是x ∀的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元，y 是y ∃的约束变元。
（3）x ∀中的x ，y ∃中的y 以及x ∃中的x 都是指导变元；x ∀的辖域是))()((z y Q y x P y ，，∧∃，y ∃的辖域是)()(z y Q y x P ，，∧，x ∃的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元，)(z y x R ，，中的x 为约束变元，y ，z 是自由变元。
2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。
（1）))()((x Q x P x →∀（2）))()((x Q x P x ∧∃解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。
（2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。
3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。
（1）)))()(()((y x R y Q y x P x ，∧∃→∀ （2）)),()()((y x R y Q x P y x →∧∀∀解 （1）成真解释：个体域D ＝{1,2,3},0:)(<x x P ,2:)(>y y Q ,3:),(>+y x y x R 。
天津理工大学《离散数学》教学教案(第二章)
47
《离散数学》教学教案
全称量词和存在量词统称为量词。 可以用个体、谓词和量词将命题符号化，并且可以刻划命题的内在结构以及命题之间 的关系。因此，引进个体、谓词和量词后，用形式符号表示命题的功能得到加强，表达意思 更加全面、确切。 例 2.1.4 符号化下列命题。 （1） 所有的人是要呼吸的。 （2） 任何整数或是正的或是负的。 （3） 有些人是聪明的。 （4） 有的人早饭吃面包。 解 （1） x( M ( x) H ( x)) ， 其中 M ( x) ： x 是人。 H ( x) ： x 要呼吸的。
需要指出的是，在谓词演算的原子公式中不能出现命题联结词和量词。 定义 2.2.1 谓词演算的合式公式定义如下： （1）原子谓词公式是合式公式。 （2）若 A 是合式公式，则 A 也是合式公式。 （3）若 A 和 B 是合式公式，则 A B ， A B ， A B 与 A B 是合式公式。 （4）若 A 是合式公式， x 是 A 中出现的任何变元，则 xA 和 xA 都是合式公式。 （5）只有经过有限次地应用规则（1） 、 （2） 、 （3） 、 （4）所得到的公式是合式公式。 谓词演算的合式公式，简称为谓词公式(Predicate Formula)。 由定义可知，命题公式也是谓词公式，因此命题逻辑包含在谓词逻辑中。 谓词公式中的某些括号也可以省略，其规定与命题公式相同，但量词后若有括号则不能 省略。
P Q R 并不是永真式，所以借助命题演算的推理理论不能证明其为重言式。
45
《离散数学》教学教案
为了克服命题逻辑的局限性，我们有必要对原子命题的结构作进一步的细分，划分出 个体词、谓词和量词，研究它们的形式结构和逻辑关系、正确的推理形式和规则，这就是谓 词逻辑的基本内容。
《应用离散数学》方景龙版-2.2 谓词公式及其解释
§2.2 谓词公式及其解释习题2.21. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）))()((y x Q x P x ，→∀ （2）)()(y x yQ y x xP ，，∃→∀（3）)())()((z y x xR z y Q y x P y x ，，，，∃∨∧∃∀解 （1）x ∀中的x 是指导变元；量词x ∀的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。
（2）x ∀中的x ，y ∃中的y 都是指导变元；x ∀的辖域是)(y x P ，，y ∃的辖域是)(y x Q ，；)(y x P ，中的x 是x ∀的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元，y 是y ∃的约束变元。
（3）x ∀中的x ，y ∃中的y 以及x ∃中的x 都是指导变元；x ∀的辖域是))()((z y Q y x P y ，，∧∃，y ∃的辖域是)()(z y Q y x P ，，∧，x ∃的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元，)(z y x R ，，中的x 为约束变元，y ，z 是自由变元。
2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。
（1）))()((x Q x P x →∀（2）))()((x Q x P x ∧∃解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。
（2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。
3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。
（1）)))()(()((y x R y Q y x P x ，∧∃→∀ （2）)),()()((y x R y Q x P y x →∧∀∀解 （1）成真解释：个体域D ＝{1,2,3},0:)(<x x P ,2:)(>y y Q ,3:),(>+y x y x R 。
谓词公式的分类与解释
第二节 谓词公式的分类与解释为了给出谓词公式的定义，先给出项和原子公式的定义。
定义2.1 项：（1） 个体常项和个体变项是项；（2） 设),...,,(21n x x x ϕ是任意的n 元函数，n t t t ,...,,21是项，则),...,,(21n t t t ϕ是项；（3） 有限地使用（1），（2）形成的符号串是项。
定义2.2 设),...,,(21n x x x R 是任意的n 元谓词，n t t t ,...,,21是项，则称),...,,(21n t t t R 是原子公式。
定义2.3合式公式：（1） 原子公式是合式公式；（2） 若A 是合式公式，则)(A ¬也是合式公式；（3） 若B A ,是合式公式，则)(),(),(),(B A B A B A B A ↔→∨∧也是合式公式；（4） 若A 是合式公式，则(),()xA xA ∀∃也是合式公式。
其中x 为任意的个体变项；（5） 有限次地应用（1）～（4）形成的字符串是合式公式。
这样定义的合式公式又称作谓词公式，简称公式。
合式公式的最外层括号可以省去。
定义2.4（1） 在公式xA ∀和xA ∃中，A 是相应量词的辖域，x 称为指导变量。
（2） 在公式xA ∀和xA ∃中，x 的所有出现都是约束出现的，不是约束出现的变项称为自由出现的。
例如：在公式))),,()((),((z y x L y G y y x F x ∧∃→∀中，∀的辖域为))),,()((),((z y x L y G y y x F ∧∃→∃的辖域为)),,()((z y x L y G ∧x ∀中的x 和y ∃中的y 都是指导变量。
x 的出现都是约束的，),(y x F 中的y 是自由出现的，)(y G 与),,(z y x L 中的y 是约束出现的，z 的出现是自由的。
一般情况下，在一个谓词公式A 中，除了可能含若干个个体常项，函数常项，谓词常 项外，还可能含个体变项，函数变项，谓词变项等。
数理逻辑中的谓词函数与谓词公式
数理逻辑中的谓词函数与谓词公式数理逻辑（mathematical logic）是研究形式逻辑（formal logic）的一个分支，它运用数学方法来研究逻辑的基本原理与推理规则。
在数理逻辑中，谓词函数和谓词公式是非常重要的概念。
本文将介绍谓词函数与谓词公式的概念、性质及其在数理逻辑中的应用。
一、谓词函数的定义与性质在数理逻辑中，谓词函数（Predicate Function）是一种将一组变量映射到真值的函数。
它通过变量的赋值将谓词的真值确定下来。
谓词函数的定义可以用集合和映射来描述。
1.1 谓词函数的定义设P是一个谓词，n是一个正整数，X1, X2, ..., Xn是n个变量，则称(P, n)为一个n元谓词，也称为谓词函数。
通常用P(x1, x2, ..., xn)来表示一个具体的n元谓词函数。
1.2 谓词函数的性质（1）真值集合：对于给定的变量赋值，谓词函数的结果是一个命题（proposition），即取值要么为真，要么为假。
谓词函数的真值集合可以用集合来表示。
（2）变元：谓词函数中的变量称为变元（arguments）。
变元的个数决定了谓词函数的元数（arity）。
（3）布尔函数：谓词函数可以看作是一种特殊的布尔函数，即输入是布尔值，输出也是布尔值的函数。
（4）值域：谓词函数的取值范围称为值域（range）。
值域通常是真值集合{真, 假}。
二、谓词公式的定义与性质谓词公式（Predicate Formula）是由谓词函数和逻辑连接词（如否定、合取、析取、蕴含、等价等）通过逻辑运算得到的复合命题。
谓词公式可以描述系统中的关系、属性和规则等。
2.1 谓词公式的定义谓词公式由谓词及其变元，逻辑连接词和量词（如全称量词∀、存在量词∃等）组成。
谓词公式可以使用自由变量或约束变量形式来表示。
2.2 谓词公式的性质（1）合法公式：符合数理逻辑规则的谓词公式称为合法公式，也称为良构公式。
（2）可满足性：对于合法公式，如果存在一种变量赋值使该谓词公式成为真命题，则称该谓词公式是可满足的。
离散数学_谓词逻辑
(3) 当个体域为全体整数的集合时： 令P(x): x是正的。N(x): x是负的。则（3）符 号化为 （x）(P(x)∨N(x)) 当个体域为全总个体域时： 令I(x): x是整数。则（3）符号化为 （x）(I(x)(P(x)∨N(x))).
全称量词的一些重要性质： 设P是任意的命题，F(x)与A(x,y)均为谓词， 则有：
【例】设 P 表示命题：张辉是工人。 Q 表示命题：李明是工人。 仅仅从命题符号 P 和 Q 看不出张辉和李明 都是工人这一特性。 【例】 x=3 ? x+y=z ? f(x)=0 ?
第二章 谓词逻辑（Predicate Logic）
2.1 谓词的概念与表示(Predicate and Its Expression)
2.1 谓词的概念与表示(Predicate and Its Expression) 谓词：用来刻划个体的性质或个体之间的相互关系的词。 例如在下面命题中： （1）张明是个劳动模范。 （2）李华是个劳动模范。 刻划客体的性质 （3）王红是个大学生。 （4）小李比小赵高2cm。 （5）点a在b与c之间。 刻划客体之间的相互关系 （6）阿杜与阿寺同岁。 （7） x与y具有关系L。 “是个劳动模范”、“是个大学生”、“…比…高2cm”、 “… 在…与…之间”、“…与…具有关系L”都是谓词。
2.1 谓词的概念与表示(Predicate and Its Expression)
（2）当个体域为人类集合时： 令G(x): x活百岁以上。则（2）符号化为 （ x）G(x) 当个体域为全总个体域时： 令M(x): x是人。则（2）符号化为 （x） (M(x) ∧ G(x))
存在量词的一些重要性质： 设P是任意的命题，F(x)与A(x,y)均为谓词， 则有：
谓词逻辑——精选推荐
第二章谓词逻辑在命题逻辑中，我们把原子命题看作命题演算和推理的基本单位，是不可再分的整体。
因而命题逻辑无法研究命题的内部结构及命题之间的内在联系，甚至无法有效地研究一些简单的推理。
例如，著名的“苏格拉底三段论”：凡是人都是要死的；苏格拉底是人；所以苏格拉底是要死的。
我们知道，这个推理是正确的，但用命题逻辑无法说明这一点。
设p:凡人都是要死的；q：苏格拉底是人；r：苏格拉底是要死的。
则“苏格拉底三段论”可符号化为（p∧q）→r。
显然（p∧q）→r不是重言式。
因此，为了能够进一步深入地研究推理，需要对原子命题做进一步的分析。
2.1 谓词逻辑的基本概念2.1.1 个体与谓词我们可以将原子命题的结构分解为个体和谓词。
定义2.1-1 个体(Individual)：个体是我们思维的对象，它是具有独立意义、可以独立存在的客体。
谓词(Predicate)：谓词是表示一个个体的性质或若干个个体之间的关系的词。
个体和谓词一起构成了原子命题中的主谓结构。
例2.1-1⑪海水是咸的。
⑫张强与张亮是兄弟。
⑬无锡位于上海与南京之间。
⑪、⑫、⑬都是原子命题，其中海水、张强、张亮、无锡、上海和南京都是个体，“…是咸的”、“…与…是兄弟”和“…位于…与…之间”都是谓词。
⑪中的谓词描述了一个个体的性质，称为一元谓词，⑫中的谓词表示两个个体之间的关系，称为二元谓词，⑬中的谓词表示三个个体之间的关系，称为三元谓词。
依次类推，我们将描述n个个体之间关系的谓词称为n元谓词，通常用大写英文字母来表示谓词。
为方便起见，将命题称为零元谓词。
例如，例2.1-1中的三个谓词可符号化为：P(x)：x是咸的；Q(x，y)：x与y是兄弟；R(x，y，z)：x位于y和z之间。
这里P 、Q 和R表示的都是具体的谓词，称为谓词常元；否则称为谓词变元。
P(x)、Q(x，y)和R(x，y，z)等都是谓词表示的函数形式，通常称为谓词函数，简称为谓词。
然而，仅仅一个谓词，即使是谓词常元，也不能构成一个命题。
第二章谓词逻辑
特性谓词在加入到命题函数中式遵循如下规 则：
(1).对应全称量词，刻划其对应个体域的特性 谓词作为蕴含式的前件加入；
(2).对应存在量词，刻划其对应个体域的特性 危险作为合取项加入。
16/86
2.1 谓词逻辑的基本概念与表示
•例2-5：符号化下列语句。
(1).天下乌鸦一般黑； (2).那位身体强健的，用功的，肯于思考问题的大学
9/86
Hale Waihona Puke 2.1 谓词逻辑的基本概念与表示
•例2-2：符号化如下命题。
P：上海是一个现代化城市； Q：甲是乙的父亲； R：3介于2和5之间； T：布什和萨达姆是同班同学。
• 注意：
(1).谓词中个体词的顺序是十分重要的，不能随意变 更。如前面的F (b, c)与F (c, b)的真值就不同；
(2).一元谓词用以描述一个个体的某种特性，而n元 谓词则用以描述n个个体之间的关系；
19/86
2.1 谓词逻辑的基本概念与表示
2.1.3谓词的语言翻译
设G (x)是关于x的一元谓词，D是其个体域， 任取x0∈D，则G (x0)是一个命题。
(x)G(x)是这样的一个命题:“对任意x， x∈D，G(x)都成立”其真值规定如下：
1对所 x 有 D ，的 都 G( 有 x 1) ( x)G (x) 0否则。
任意的n个项，则f(t1, t2, …, tn)是项； (3).所有的项都是有限次使用(1)，(2)得到的。
25/86
2.2 谓词的合式公式及解释
我们定义的项，包括了常量，变量及函数。 例如，x，a，f(x, a)，f(g(x, a),b)，h(x)均是项。
函数的使用，能给谓词表示带来很大的方便。
5/86
(1).对应全称量词，刻划其对应个体域的特性 谓词作为蕴含式的前件加入；
(2).对应存在量词，刻划其对应个体域的特性 危险作为合取项加入。
16/86
2.1 谓词逻辑的基本概念与表示
•例2-5：符号化下列语句。
(1).天下乌鸦一般黑； (2).那位身体强健的，用功的，肯于思考问题的大学
9/86
Hale Waihona Puke 2.1 谓词逻辑的基本概念与表示
•例2-2：符号化如下命题。
P：上海是一个现代化城市； Q：甲是乙的父亲； R：3介于2和5之间； T：布什和萨达姆是同班同学。
• 注意：
(1).谓词中个体词的顺序是十分重要的，不能随意变 更。如前面的F (b, c)与F (c, b)的真值就不同；
(2).一元谓词用以描述一个个体的某种特性，而n元 谓词则用以描述n个个体之间的关系；
19/86
2.1 谓词逻辑的基本概念与表示
2.1.3谓词的语言翻译
设G (x)是关于x的一元谓词，D是其个体域， 任取x0∈D，则G (x0)是一个命题。
(x)G(x)是这样的一个命题:“对任意x， x∈D，G(x)都成立”其真值规定如下：
1对所 x 有 D ，的 都 G( 有 x 1) ( x)G (x) 0否则。
任意的n个项，则f(t1, t2, …, tn)是项； (3).所有的项都是有限次使用(1)，(2)得到的。
25/86
2.2 谓词的合式公式及解释
我们定义的项，包括了常量，变量及函数。 例如，x，a，f(x, a)，f(g(x, a),b)，h(x)均是项。
函数的使用，能给谓词表示带来很大的方便。
5/86
2.2--谓词逻辑表示法
注意：
谓词逻辑可以由原子和 5 种逻辑连接词，再加 上量词来构造复杂的符号表达式。这就是所谓的谓 词逻辑中的公式。
2014-3-2
中国矿业大学 计算机科学与技术学院
19
人工智能
一阶谓词逻辑的合式公式（可简称公式）可递 归定义如下：
(1)原子谓词公式是合式公式 (也称为原子公式)。
(2) 若 P、Q 是合式公式，则(┐ P)、(P∧Q)、(P∨Q)、 (P→Q)、(P←→ Q)也是合式公式。ຫໍສະໝຸດ 2014-3-28
人工智能
注意:
在命题逻辑中，每个表达式都是句 子，表示事实。 在谓词逻辑中，有句子，但是也有 项，表示对象。常量符号、变量和 函数符号用于表示项，量词和谓词 符号用于构造句子。
中国矿业大学 计算机科学与技术学院
2014-3-2
9
人工智能
4.语法
命题逻辑的符号包括以下几种：
值得注意的是：
一个谓词公式在其个体域上的解释不是唯一的。 例如，对公式G，若给出另一组真值指派如下：
中国矿业大学 计算机科学与技术学院
2014-3-2
24
人工智能
P(1,1)
P(1,2)
P(2,1)
P(2,2)
T
T
F
F
这也是公式G在D上的一个解释。从这个解释可以看出： 当x=1,y=1时,P(x,y)的真值为T; 当x=2,y=1时,P(x,y)的真值也为F; 同样 当x=1,y=2时,P(x,y)的真值为T; 当x=2,y=2时,P(x,y)的真值也为F;
2014-3-2
中国矿业大学 计算机科学与技术学院
7
人工智能
谓词逻辑
谓词逻辑：根据对象和对象上的谓词 （即对象的属性和对象之间的关系），通过 使用连接词和量词来表示世界。
第2章 谓词逻辑-2
例3：那位戴眼镜的用功的大学生在看这本大而 ： 厚的巨著. 厚的巨著 是大学生. A(x): x戴眼镜 戴眼镜. 解: (1)设：S(x): x是大学生 设 是大学生 戴眼镜 B(x): x用功 用功. D(x): x是巨著 是巨著. 用功 是巨著 F(x,y): x看y. 看 E(y): y是大的 是大的. G(y): y是厚的 是厚的. 是大的 是厚的 a: 那位 b: 这本 符号化为: 符号化为 A(a)∧B(a)∧S(a)∧D(b)∧E(b)∧G(b)∧F(a,b)
把一个文字叙述的命题， 把一个文字叙述的命题，用谓词公式表示出 称为谓词逻辑的翻译或符号化；反之亦然。 来，称为谓词逻辑的翻译或符号化；反之亦然。一 般说来，符号化的步骤如下： 般说来，符号化的步骤如下： 正确理解给定命题。必要时把命题改叙， ①正确理解给定命题。必要时把命题改叙，使其中 每个原子命题、 每个原子命题、原子命题之间的关系能明显表达出 来。 把每个原子命题分解成个体、谓词和量词； ②把每个原子命题分解成个体、谓词和量词；在 全总论域讨论时，要给出特性谓词。 全总论域讨论时，要给出特性谓词。 找出恰当量词。应注意全称量词(∀ 后跟条件 ③找出恰当量词。应注意全称量词 ∀x)后跟条件 存在量词(∃ 后跟合取式 后跟合取式。 式，存在量词 ∃x)后跟合取式。 用恰当的联结词把给定命题表示出来。 ④用恰当的联结词把给定命题表示出来。
2.2谓词公式与翻译 谓词公式与翻译
n元谓词A(x1, x2, ... , xn) 称为谓词演算的原子公式。 元谓词 称为谓词演算的原子公式 原子公式。 定义2.2.1谓词演算的合式公式 可由下述各条组成 谓词演算的合式公式 可由下述各条组成: 定义 谓词演算的合式公式,可由下述各条组成 （1）原子公式是合式公式。 ）原子公式是合式公式。 是合式公式， 也是合式公式。 （2）若A 是合式公式，则(┐A)也是合式公式。 ） 也是合式公式 是合式公式， （3）若A，B是合式公式，则(A∧ B)，(A∨B)， ） ， 是合式公式 ∧ ， ∨ ， (A→ B)，(A↔B)也是合式公式。 也是合式公式。 → ， ↔ 也是合式公式 是合式公式， 是 中出现的任何变元 中出现的任何变元,则 （4）若A是合式公式，x是A中出现的任何变元 则 ） 是合式公式 (∀x) A, (∃x) A，也是合式公式。 ∀ ∃ ，也是合式公式。 (5)只有有限次应用 只有有限次应用(1)~(4)得到的公式是合式公式 得到的公式是合式公式 只有有限次应用 得到的公式是合式公式.
2.2 谓词表示
pushthru(BOX1,D1,R2,R1)
条件：
划
应 用
的
条
INROOM(BOX1,R2)∧INROOM(ROBOT,R2)∧CONNECTS(D1,R1,R2) 件
删除：INROOM(ROBOT， R2 ) ∧ INROOM(BOX1,R2)
添加：INROOM(ROBOT，R1) ∧ INROOM(BOX1，R1)
C
状态6： AT(ROBOT,C) ∧ TABLE(A) ∧ CLEAR(A) ∧
ON(BOX,B) ∧ TABLE(B) ∧ HANDEMPTY(ROBOT )
A
B
SETDOWN(B)
条件：AT(ROBOT,B) ∧ TABLE(B) ∧ CLEAR(B) ∧ HOLD(ROBOT,BOX )
删除： HOLD(ROBOT,BOX ) 添加：HANDEMPTY(ROBOT )
C
状态2： AT(ROBOT,A) ∧ TABLE(A) ∧ ON(BOX,A) ∧
TABLE(B) ∧ CLEAR(B) ∧ HANDEMPTY(ROBOT )
操作：PICKUP(BOX)
A
B
条件：AT(ROBOT,A) ∧ TABLE(A) ∧ ON(BOX,A) ∧ HANDEMPTY(ROBOT )
机
gothru(D1,R1,R2)
器
条件：INROOM(ROBOT，R1)∧CONNECTS(D1,R1,R2)。 人
删除：INROOM(ROBOT，R1) (以前状态) 添加：INROOM(ROBOT，R2) (当前状态)
状态M1： INROOM(ROBOT，R2)
搬
运
计
操 作
∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)
条件：
划
应 用
的
条
INROOM(BOX1,R2)∧INROOM(ROBOT,R2)∧CONNECTS(D1,R1,R2) 件
删除：INROOM(ROBOT， R2 ) ∧ INROOM(BOX1,R2)
添加：INROOM(ROBOT，R1) ∧ INROOM(BOX1，R1)
C
状态6： AT(ROBOT,C) ∧ TABLE(A) ∧ CLEAR(A) ∧
ON(BOX,B) ∧ TABLE(B) ∧ HANDEMPTY(ROBOT )
A
B
SETDOWN(B)
条件：AT(ROBOT,B) ∧ TABLE(B) ∧ CLEAR(B) ∧ HOLD(ROBOT,BOX )
删除： HOLD(ROBOT,BOX ) 添加：HANDEMPTY(ROBOT )
C
状态2： AT(ROBOT,A) ∧ TABLE(A) ∧ ON(BOX,A) ∧
TABLE(B) ∧ CLEAR(B) ∧ HANDEMPTY(ROBOT )
操作：PICKUP(BOX)
A
B
条件：AT(ROBOT,A) ∧ TABLE(A) ∧ ON(BOX,A) ∧ HANDEMPTY(ROBOT )
机
gothru(D1,R1,R2)
器
条件：INROOM(ROBOT，R1)∧CONNECTS(D1,R1,R2)。 人
删除：INROOM(ROBOT，R1) (以前状态) 添加：INROOM(ROBOT，R2) (当前状态)
状态M1： INROOM(ROBOT，R2)
搬
运
计
操 作
∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)
离散数学23谓词公式与翻译
(A→B)和(A↔B)是合式公式。 ⑷ 如果A是合式公式，x是A中出现的任意个体变
元，则(x)A，(x)A是合式公式。 ⑸ 只有有限次地应用⑴、⑵、⑶、⑷所得的公式 是合式公式。
2
二、命题翻译
谓词公式也有以下约定： ⑴ 最外层的括号可以省略。 ⑵ 如果按¬、∧、∨、→、↔在运算中的优先级 别，省略括号后不改变原来的运算次序，可以 省略括号，但量词后面括号不能省略。
A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)
7
二、命题翻译
由例题4可知，由命题翻译成谓词演算公式， 机动性很大，对个体刻划尝试的不同就可 翻译成不同的谓词公式。 一般的，对日常语言，我们可以有一个大 体的准则，根据这些准则可以进行命题的 翻译。
名词：专用名词（如南京、刘翔等）是客体
一谓词公式简单命题函数与逻辑联结词可以组合成一些命题表达式与命题公式概念类似不是所有谓词表达式都可以成为谓词公式并进行谓词演算下面介绍谓词的合式公式的概念
一、谓词公式
简单命题函数与逻辑联结词可以组合成一些命题 表达式 与命题公式概念类似，不是所有谓词表达式都可 以成为谓词公式并进行谓词演算，下面介绍谓词 的合式公式的概念。
以上只是一般准则，具体应用时会有例外
9
10
11
12
13
14
本课小结
谓词公式 命题翻译
15
课后作业
补充:用谓词写出下列各断言 (1)长江比黄河长,金陵饭店比北京饭店高. (2)南京位于武汉和上海之间. (3)不是所有男人都比女人高. (4)有而且仅有一个素数是偶数. (5)凡是资本家都会剥削人,但剥削人者未必都
该命题符号化为： ¬(x) (y) (F(x)∧G(y)→H(x,y))
元，则(x)A，(x)A是合式公式。 ⑸ 只有有限次地应用⑴、⑵、⑶、⑷所得的公式 是合式公式。
2
二、命题翻译
谓词公式也有以下约定： ⑴ 最外层的括号可以省略。 ⑵ 如果按¬、∧、∨、→、↔在运算中的优先级 别，省略括号后不改变原来的运算次序，可以 省略括号，但量词后面括号不能省略。
A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)
7
二、命题翻译
由例题4可知，由命题翻译成谓词演算公式， 机动性很大，对个体刻划尝试的不同就可 翻译成不同的谓词公式。 一般的，对日常语言，我们可以有一个大 体的准则，根据这些准则可以进行命题的 翻译。
名词：专用名词（如南京、刘翔等）是客体
一谓词公式简单命题函数与逻辑联结词可以组合成一些命题表达式与命题公式概念类似不是所有谓词表达式都可以成为谓词公式并进行谓词演算下面介绍谓词的合式公式的概念
一、谓词公式
简单命题函数与逻辑联结词可以组合成一些命题 表达式 与命题公式概念类似，不是所有谓词表达式都可 以成为谓词公式并进行谓词演算，下面介绍谓词 的合式公式的概念。
以上只是一般准则，具体应用时会有例外
9
10
11
12
13
14
本课小结
谓词公式 命题翻译
15
课后作业
补充:用谓词写出下列各断言 (1)长江比黄河长,金陵饭店比北京饭店高. (2)南京位于武汉和上海之间. (3)不是所有男人都比女人高. (4)有而且仅有一个素数是偶数. (5)凡是资本家都会剥削人,但剥削人者未必都
该命题符号化为： ¬(x) (y) (F(x)∧G(y)→H(x,y))
2.2谓词逻辑
RUNS (Liuhua，faster)→WINS (Liuhua ，champion)
（5） ：“等价”（equivalence）或“双条件”
（bicondition）。
P Q: “P当且仅当Q”。172.2.3 谓词公式
1. 连接词（连词）
谓词逻辑真值表
18
2.2.3 谓词公式
2. 量词（quantifier） （1）全称量词（universal quantifier）（ x）：“对个体
公式中的所有y都是自由变元。
23
2.2.3 谓词公式
1. 连接词（连词）
“机器人不在2号房间”：﹁ Inroom (robot, r2)
（1）﹁： “否定” （ negation ）或 “非”。
（2）∨： “析取”（disjunction）——或。
“李明打篮球或踢足球”：
Plays (Liming, basketball) ∨ Plays (Liming, football)
（3）∧： “合取”（conjunction）——与。
“我喜欢音乐和绘画”： Like (I, music) ∧ Like (I, painting)
16
2.2.3 谓词公式
1. 连接词（连词） （4）→：“蕴含”(implication)或 “条
件”(“如co果nd刘iti华on跑)。得最快，那么他取得冠军。” ：
连接词的优先级别从高到低排列： ﹁， ∧， ∨， →，
22
2.2.3 谓词公式
4．量词的辖域
量词的辖域：位于量词后面的单个谓词或者用括弧括起 来的谓词公式。 约束变元与自由变元：辖域内与量词中同名的变元称为 约束变元，不同名的变元称为自由变元。
（5） ：“等价”（equivalence）或“双条件”
（bicondition）。
P Q: “P当且仅当Q”。172.2.3 谓词公式
1. 连接词（连词）
谓词逻辑真值表
18
2.2.3 谓词公式
2. 量词（quantifier） （1）全称量词（universal quantifier）（ x）：“对个体
公式中的所有y都是自由变元。
23
2.2.3 谓词公式
1. 连接词（连词）
“机器人不在2号房间”：﹁ Inroom (robot, r2)
（1）﹁： “否定” （ negation ）或 “非”。
（2）∨： “析取”（disjunction）——或。
“李明打篮球或踢足球”：
Plays (Liming, basketball) ∨ Plays (Liming, football)
（3）∧： “合取”（conjunction）——与。
“我喜欢音乐和绘画”： Like (I, music) ∧ Like (I, painting)
16
2.2.3 谓词公式
1. 连接词（连词） （4）→：“蕴含”(implication)或 “条
件”(“如co果nd刘iti华on跑)。得最快，那么他取得冠军。” ：
连接词的优先级别从高到低排列： ﹁， ∧， ∨， →，
22
2.2.3 谓词公式
4．量词的辖域
量词的辖域：位于量词后面的单个谓词或者用括弧括起 来的谓词公式。 约束变元与自由变元：辖域内与量词中同名的变元称为 约束变元，不同名的变元称为自由变元。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
对x (F(x,y)∧y G(x,y)) F(x,y) 改为： x (F(x,t)∧y G(x,y)) F(s,t) 或者为：t (F(t,y)∧y G(t,y)) F(x,y)
谓词公式的解释
西 谓词逻辑中的解释(赋值)
华
大 在命题逻辑对每个命题符号作个真值指定可以得一个
学
公式的一个指派,又称赋值,又称解释。如公式中共出 现n个不同的命题符号,则共有2n个解释,因而可以列 出公式的真值表。而谓词逻辑中公式的赋值解释是 怎样的呢？
项，则 f (t1, t2 , , tn ) 是原子公式；
西 合式公式的归纳定义：
华 大
1、任意的原子公式是公式
学 2、若A是公式，则xA、xA是公式；
3、若A、B是公式，则 A、A∧ B、A∨B、A → B、A B是 公式；
有限次地应用前三条，得到公式。
判断下列符号串是否为合式公式： 1. x(P(x) ∧ Q(x)) 2. xy(P(x) Q(y)) 3. yx∧ P(x) 4. x f(x) → x(g(x,y) ∨f(x) )
四、谓词公式的类型
西
设A是公式。如果A在任何的解释下都
华
大 是真的，则A是永真式；如果A在任何的
学 解释下都是假的，则A是永假式；如果A
在一些解释下为假，一些解释下为真，
则A是非永真的可满足式。
例如： x A(x) x A(x)是永真式； x A(x)∧x A(x）是永假式。
代换实例
西华设A0是含命题变元p1, p2, …, pn的命题逻辑公式，
2） x F(x) 为假，x F(x) x F(x)为真。
从而，在蕴涵式的前件x F(x) 为1或0的情况， 蕴涵式都为真。
又由解释I的任意性，知公式x F(x) x F(x)永真。
3) x y F(x,y) y x F(x,y)
西 1）取解释I1为：D=R,F(x,y):x>y
华 大
二、约束部分
在谓词公式中，形如xP(x)或xP(x)以及
xP(x，y)的部分中x称为指导变元，在辖
西 域中,x的所有出现称为约束变元（约束出
华 大
现）；y是自由变元（自由出现）。
学 量词的辖域
(x)P(x)或(x)P(x)中的公式P(x)，通
称为量词的辖域。换言之，量词的辖域是
邻接其后的公式，除非辖域是原子公式，
2、 代替规则：对自由变元进行代入。
整个谓词公式中同一个字母的自由变元是指同一个个体 名词。因此可以用整个公式中没有的变元符号来代替， 且要求整个公式中该变元同时用同一个符号代替。
换名规则举例
西x F(x,y)∧x G(x,y) 华大改为：x F(x,y)∧u G(u,y) 学或者为： z F(z,y)∧x G(x,y)
大 学
A1,
A2,
…,
An是一阶逻辑公式，用Ai(1
i
n)
替换A0中的pi的处处出现所得到的一阶逻辑公式
A称为命题逻辑公式A0的替换实例。
定理：命题逻辑中的永真式的任意替换实例在一
阶逻辑中都是永真式；命题逻辑中的矛盾式的任
意替换实例在一阶逻辑中都是矛盾式 。
1、永真式和永假式的代入实例是永真、永假式；
则x (x ≥0) ∧x (3x=0) 假命题。
解释举例1
给定解释I如下：
西 华 大 学
•x(F(x) ∧ G(x,2))
• (F(2) ∧ G(2,2)) ∧ (F(3) ∧ G(3,2))
•y L(2,y) ∧ y L(3,y)
0∧ 11
(L(2,2)∨L(2,3)) ∧(L(3,2) ∨ L(3,3)) ( 1 ∨0 ) ∧(0 ∨ 1) 1
否则应在所辖公式的两侧插入圆括号。
量词辖域举例
西 华
例如：x F(x)G(x,y)
大 学
解：x的辖域仅F(x),x是指导变元，变
元x第一次出现是约束出现，第二次出
现是自由出现，y的出现是自由出现。
所以第一个x是约束变元，第二个x是
自由变元，本质上这两个x的含义是不
同的；而y仅是自由变元。
换名规则
大
学 解：1、F(a) x F(x)是非永真的可满足式；
①设D={2}，a=2，F(x):x=2，显然此时为 真；
②设D=R，a=2，F(x):x=2，显然此时为假；
2、F(a) x F(x)是永真式。
§2.2 一阶逻辑合式公式及解释
• 符号体系：
1. 西华2.
个体常元符号：a,b,c,……a1,a2,a3,…… 个体变元:x,y,z,……,x1,x2,x3,……
大3. 学
4.
函数符号:f,g,h,……f1,f2,f3,…… 谓词符号:F,G,H,……
5. 量词符号: 6. 联结词: ∧∨ →
解释的说明
(1) 一个谓词公式如果不含自由变元,则在一个解释下, 可以得到确定的真值,不同的解释下可能得到不同的 真值。
(2) 公式的解释并不对变元进行指定,如果公式中含有自 由变元,即使对公式进行了一个指派,也得不到确定的 真值,其仅是个命题函数,但约束变元不受此限制。
3）有公式的解释定义可以看出,公式的解释有许多的解 释,当D为无限集时,公式有无限多个解释,根本不可能 将其一一列出,因而谓词逻辑的公式不可能有真值表 可列。
例如公式：x F(x,a)∧x G(f(x),a)
三、谓词公式的赋值(解释)
一个解释由4部分组成：
（1） 非空个体域D；
西 华
（2）D中特定元素；
大 （3）D上特定函数； 学 （4）D上特定谓词。
公式x F(x,a)∧x G(f(x),a)
指定：D=实数集合；a=0；f(x):3x;F(x,y):x≥y； G(x,y):x=y。
替换实例。容易知道P (Q P )
是永真式，从而x F(x) (x
yG(x,y) x F(x) )是永真式。
2) x F(x) x F(x)
设在任意的解释I下，
西 1） x F(x) 为真，则 a，使得 F(a)为真，使
华 大
得 x F(x)为真， 在这种情况下，x F(x)
学 x F(x)为真；
• 项的定义
1. 个体变元、个体常元是项；
2. 若 f (x1, x2 , , xn ) 是任意n元函数，t1,t2,…,tn 是项，
则 f (t1, t2 , , tn ) 是项； 3. 有限次的应用1，2得到项。
一、合式公式的定义：
原子公式： f (x1, x2 , , xn ) 为n元谓词符号，t1,t2,…,tn 是
解释举例2
例2：已知指定一个解释N如下： (1)个体域为自然数集合DN (2)指定常项a=0 (3)DN上的指定函数f(x,y)=x+y,g(x,y)=x*y (4)指定谓词F(x,y)为x=y 在以上指定的解释N下,说明下列公式的真值
(1)xF(g(x,a),x) 即x(x*0=x)该命题假的
(2)xy(F(f(x,a),y)F(f(y,a),x)) 在解释N下此公式：xy(x+0=yy+0=x)此命题为真 (3)F(f(x,y),f(y,z))在解释N下该公式x+y=y+z 此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而该 公式是命题函数,不是命题,真值不能确定。
可以看出,在谓词公式中一个变元可能既是约束出现,同
时又有自由出现,则该变元既是自由变元又是约束变元,
西 本质上这两种出现,用的是一个符号,实质上是不同的
华 大 学
含义。为避免混淆,需要改名。改名要采用以下规则, 使谓词公式的含义不改变。
1、 换名规则：对约束变元进行换名。
将量词辖域内出现的某个约束变元及其相应量词中的指 导变元，可以换成一个其他变元，改变元不能与本辖 域内的其他变元同名，公式中的其他部分不改变。
则公式为： x y (x>y) y x(x>y)
学 =10=0，从而公式不是永真式；
2) 取解释I2为：D=R,F(x,y):x.y=0 则公式为：xy(x•y=0)yx(x•y=0) =11=1从而公式不是永假式；
可知，公式是非永真的可满足式。
思考题：
1、F(a) x F(x)
西 华
2、F(a) x F(x)
公式类型举例
西 判断下列公式的类型：
华
大 学
1)
xห้องสมุดไป่ตู้
F(x)
(x
yG(x,y)
x
F(x)
)
2) x F(x) x F(x)
3) x y F(x,y) y x F(x,y)
1) x F(x) (x yG(x,y) x F(x) )
西 华
解：显然该公式是：P (Q P ) 的
大 学
2. 对于某些简单的公式，特别对于简单的闭式，
西 华
可在假定给定任意解释的前提下该公式的真值
大 学
都为真（或者为假）来证明该公式是永真式
（或矛盾式）。
3. 要证明一个公式是可满足式，只要找到一个 解释，使得该公式的真值为真即可。同时为了 证明它不是永真式，只要找一个解释，使得该 公式的真值为假即可。
谓词公式的解释
西 谓词逻辑中的解释(赋值)
华
大 在命题逻辑对每个命题符号作个真值指定可以得一个
学
公式的一个指派,又称赋值,又称解释。如公式中共出 现n个不同的命题符号,则共有2n个解释,因而可以列 出公式的真值表。而谓词逻辑中公式的赋值解释是 怎样的呢？
项，则 f (t1, t2 , , tn ) 是原子公式；
西 合式公式的归纳定义：
华 大
1、任意的原子公式是公式
学 2、若A是公式，则xA、xA是公式；
3、若A、B是公式，则 A、A∧ B、A∨B、A → B、A B是 公式；
有限次地应用前三条，得到公式。
判断下列符号串是否为合式公式： 1. x(P(x) ∧ Q(x)) 2. xy(P(x) Q(y)) 3. yx∧ P(x) 4. x f(x) → x(g(x,y) ∨f(x) )
四、谓词公式的类型
西
设A是公式。如果A在任何的解释下都
华
大 是真的，则A是永真式；如果A在任何的
学 解释下都是假的，则A是永假式；如果A
在一些解释下为假，一些解释下为真，
则A是非永真的可满足式。
例如： x A(x) x A(x)是永真式； x A(x)∧x A(x）是永假式。
代换实例
西华设A0是含命题变元p1, p2, …, pn的命题逻辑公式，
2） x F(x) 为假，x F(x) x F(x)为真。
从而，在蕴涵式的前件x F(x) 为1或0的情况， 蕴涵式都为真。
又由解释I的任意性，知公式x F(x) x F(x)永真。
3) x y F(x,y) y x F(x,y)
西 1）取解释I1为：D=R,F(x,y):x>y
华 大
二、约束部分
在谓词公式中，形如xP(x)或xP(x)以及
xP(x，y)的部分中x称为指导变元，在辖
西 域中,x的所有出现称为约束变元（约束出
华 大
现）；y是自由变元（自由出现）。
学 量词的辖域
(x)P(x)或(x)P(x)中的公式P(x)，通
称为量词的辖域。换言之，量词的辖域是
邻接其后的公式，除非辖域是原子公式，
2、 代替规则：对自由变元进行代入。
整个谓词公式中同一个字母的自由变元是指同一个个体 名词。因此可以用整个公式中没有的变元符号来代替， 且要求整个公式中该变元同时用同一个符号代替。
换名规则举例
西x F(x,y)∧x G(x,y) 华大改为：x F(x,y)∧u G(u,y) 学或者为： z F(z,y)∧x G(x,y)
大 学
A1,
A2,
…,
An是一阶逻辑公式，用Ai(1
i
n)
替换A0中的pi的处处出现所得到的一阶逻辑公式
A称为命题逻辑公式A0的替换实例。
定理：命题逻辑中的永真式的任意替换实例在一
阶逻辑中都是永真式；命题逻辑中的矛盾式的任
意替换实例在一阶逻辑中都是矛盾式 。
1、永真式和永假式的代入实例是永真、永假式；
则x (x ≥0) ∧x (3x=0) 假命题。
解释举例1
给定解释I如下：
西 华 大 学
•x(F(x) ∧ G(x,2))
• (F(2) ∧ G(2,2)) ∧ (F(3) ∧ G(3,2))
•y L(2,y) ∧ y L(3,y)
0∧ 11
(L(2,2)∨L(2,3)) ∧(L(3,2) ∨ L(3,3)) ( 1 ∨0 ) ∧(0 ∨ 1) 1
否则应在所辖公式的两侧插入圆括号。
量词辖域举例
西 华
例如：x F(x)G(x,y)
大 学
解：x的辖域仅F(x),x是指导变元，变
元x第一次出现是约束出现，第二次出
现是自由出现，y的出现是自由出现。
所以第一个x是约束变元，第二个x是
自由变元，本质上这两个x的含义是不
同的；而y仅是自由变元。
换名规则
大
学 解：1、F(a) x F(x)是非永真的可满足式；
①设D={2}，a=2，F(x):x=2，显然此时为 真；
②设D=R，a=2，F(x):x=2，显然此时为假；
2、F(a) x F(x)是永真式。
§2.2 一阶逻辑合式公式及解释
• 符号体系：
1. 西华2.
个体常元符号：a,b,c,……a1,a2,a3,…… 个体变元:x,y,z,……,x1,x2,x3,……
大3. 学
4.
函数符号:f,g,h,……f1,f2,f3,…… 谓词符号:F,G,H,……
5. 量词符号: 6. 联结词: ∧∨ →
解释的说明
(1) 一个谓词公式如果不含自由变元,则在一个解释下, 可以得到确定的真值,不同的解释下可能得到不同的 真值。
(2) 公式的解释并不对变元进行指定,如果公式中含有自 由变元,即使对公式进行了一个指派,也得不到确定的 真值,其仅是个命题函数,但约束变元不受此限制。
3）有公式的解释定义可以看出,公式的解释有许多的解 释,当D为无限集时,公式有无限多个解释,根本不可能 将其一一列出,因而谓词逻辑的公式不可能有真值表 可列。
例如公式：x F(x,a)∧x G(f(x),a)
三、谓词公式的赋值(解释)
一个解释由4部分组成：
（1） 非空个体域D；
西 华
（2）D中特定元素；
大 （3）D上特定函数； 学 （4）D上特定谓词。
公式x F(x,a)∧x G(f(x),a)
指定：D=实数集合；a=0；f(x):3x;F(x,y):x≥y； G(x,y):x=y。
替换实例。容易知道P (Q P )
是永真式，从而x F(x) (x
yG(x,y) x F(x) )是永真式。
2) x F(x) x F(x)
设在任意的解释I下，
西 1） x F(x) 为真，则 a，使得 F(a)为真，使
华 大
得 x F(x)为真， 在这种情况下，x F(x)
学 x F(x)为真；
• 项的定义
1. 个体变元、个体常元是项；
2. 若 f (x1, x2 , , xn ) 是任意n元函数，t1,t2,…,tn 是项，
则 f (t1, t2 , , tn ) 是项； 3. 有限次的应用1，2得到项。
一、合式公式的定义：
原子公式： f (x1, x2 , , xn ) 为n元谓词符号，t1,t2,…,tn 是
解释举例2
例2：已知指定一个解释N如下： (1)个体域为自然数集合DN (2)指定常项a=0 (3)DN上的指定函数f(x,y)=x+y,g(x,y)=x*y (4)指定谓词F(x,y)为x=y 在以上指定的解释N下,说明下列公式的真值
(1)xF(g(x,a),x) 即x(x*0=x)该命题假的
(2)xy(F(f(x,a),y)F(f(y,a),x)) 在解释N下此公式：xy(x+0=yy+0=x)此命题为真 (3)F(f(x,y),f(y,z))在解释N下该公式x+y=y+z 此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而该 公式是命题函数,不是命题,真值不能确定。
可以看出,在谓词公式中一个变元可能既是约束出现,同
时又有自由出现,则该变元既是自由变元又是约束变元,
西 本质上这两种出现,用的是一个符号,实质上是不同的
华 大 学
含义。为避免混淆,需要改名。改名要采用以下规则, 使谓词公式的含义不改变。
1、 换名规则：对约束变元进行换名。
将量词辖域内出现的某个约束变元及其相应量词中的指 导变元，可以换成一个其他变元，改变元不能与本辖 域内的其他变元同名，公式中的其他部分不改变。
则公式为： x y (x>y) y x(x>y)
学 =10=0，从而公式不是永真式；
2) 取解释I2为：D=R,F(x,y):x.y=0 则公式为：xy(x•y=0)yx(x•y=0) =11=1从而公式不是永假式；
可知，公式是非永真的可满足式。
思考题：
1、F(a) x F(x)
西 华
2、F(a) x F(x)
公式类型举例
西 判断下列公式的类型：
华
大 学
1)
xห้องสมุดไป่ตู้
F(x)
(x
yG(x,y)
x
F(x)
)
2) x F(x) x F(x)
3) x y F(x,y) y x F(x,y)
1) x F(x) (x yG(x,y) x F(x) )
西 华
解：显然该公式是：P (Q P ) 的
大 学
2. 对于某些简单的公式，特别对于简单的闭式，
西 华
可在假定给定任意解释的前提下该公式的真值
大 学
都为真（或者为假）来证明该公式是永真式
（或矛盾式）。
3. 要证明一个公式是可满足式，只要找到一个 解释，使得该公式的真值为真即可。同时为了 证明它不是永真式，只要找一个解释，使得该 公式的真值为假即可。