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 。
- 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. 要证明一个公式是可满足式，只要找到一个 解释，使得该公式的真值为真即可。同时为了 证明它不是永真式，只要找一个解释，使得该 公式的真值为假即可。