当前位置：文档之家 › 离散第13讲 谓词演算基本概念

离散第13讲 谓词演算基本概念

  • 格式：ppt
  • 大小：988.00 KB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

离散数学的谓词逻辑详解

离散数学的谓词逻辑详解
两种量词: 全称量词和存在量词.
全称量词:
1.全称量词 ： （任意，所有） x: “对一切x”，“对所有的x”， “对任一x”
如： x P(x) ┐ x P(x) x ┐ P(x)
“对一切x，P(x)是真” “并非对一切x，P(x)是真” “对一切x， ┐ P(x) 是真”
如: “ 所有人都是要死的”
于是令 M（x）：x是人。 （1） x（M(x)→D(x)) （2） x (M（x）∧ ┐G（x））
命题符号化(翻译)：
将汉语(或其他自然语言)语句翻译成逻辑表 达式，这在数学、逻辑编程、人工智能、软 件工程以及许多其他学科中都是一项重要的 任务。翻译的目的是生成简单而有用的逻辑 表达式。
命题符号化：
1.谓词与个体词
将简单命题分解成个体与谓词这样两个组成部分。谓词，通 常是用来描述个体的性质或特征，或者个体之间的关系。谓 词逻辑，是命题逻辑的扩充与发展 。
例1：下面两个命题 1. 张华是学生 2. 李明是学生
a: 张华 b:李明 H：是学生 ，则 H（x）:x是学生
1，2可分别表示成 H(a) ，H(b). 这样表示就揭示了两命题间有相同的谓语这一特征。
变元的约束
例1 ： 令 P（x， y）：“ x<y ”， Q（x）：x是有理数； F（x）：x可以表示为分数。
判断下列式子那些是命题函数，那些是命题？
P(x， y)
P(x， y)∧Q(x)
Q(x) → F(x) x（Q(x)→ F(x)) x Q(x)→ F(x)
自由变元与约束变元
[定义] 紧接于量词之后最小的子公式称为量词的辖 域．(量词的辖域是紧接其后的公式，除非辖域是个 原子公式，否则应在公式的两侧插入圆括号。)

离散数学的谓词逻辑详解

离散数学的谓词逻辑详解

“存在x， ┐ P(x)是真”
如: “有些有理数是整数。” 令Ｉ(x）：x是整数， 设x的个体域为有理数集合，则命题可表示为： x I(x）
2016/6/10 15
4. 论 域
含有量词的命题的表达式的形式，与论域有关。用量词量化 后的命题，其值也与论域有关。 例 1 x（x=0) 若论域为整数集，则此命题值为真， 若论域为正整数集，则命题的值为假。
2016/6/10
28
变元的约束
令 P（x， y）：“ x<y ”， Q（x）：x是有理数； F（x）：x可以表示为分数。 判断下列式子那些是命题函数，那些是命题？ 例1 ：
P(x， y) P(x， y)∧Q(x) Q(x) → F(x) x（Q(x)→ F(x)) x Q(x)→ F(x)
为了方便，引入全总个体域，记为：U，简称全域: 定义:宇宙间所有的个体聚集在一起所构成的集合称为全域。
2016/6/10
16
特性谓词
后面的讨论中，除特殊说明外，均使用全域。而对个 体变化的真正取值范围，用特性谓词加以限制。
一般地，对全称量词，特性谓词作蕴含的前件引入；而 对存在量词，特性谓词常作为合取项引入。
2016/6/10 12
3. 量词
使用前面介绍的概念，还不足以表达日常生活中的 各种命题。 例如： “ 所有的正整数都是素数 ” “ 有些正整数是素数 ” 两种量词: 全称量词和存在量词.
2016/6/10
13
全称量词:
1.全称量词 ： （任意，所有） x: “对一切x”，“对所有的x”， “对任一x”
定义：一个n元函词即是一个论域Ｄ上的一个n元函数．
2016/6/10
10
概念的讨论

离散数学教程ch2谓词演算(A13信息)

离散数学教程ch2谓词演算(A13信息)
第2章
逻辑代数(下)： 谓词演算
1
重点:量词及谓词演算永真式
掌握谓词的概念； 掌握两种量词及其用法； 掌握谓词公式的定义； 掌握基本的谓词演算的等价式和 蕴涵式；
2
谓词演算引入的必要性
命题逻辑以由原子命题通过联结 词构成的命题公式为讨论对象，不 再对原子命题作进一步的分析，即 命题逻辑只讨论以原子命题为基本 元素的命题公式之间的推理关系， 这种逻辑体表达能力很弱。
导变元同时填在谓词D(x) 中。
17 20
2.1.3
量词
（2）存在量词 “ ” 如 “有些有理数是整数。” 令I(x)：x是整数； 于是命题可表示为 xI(x) 其中x的个体域为有理数集合。
xI(x)： 读作“有（存在，至少有一个）x满足I(x)”。
表示个体域中至少有一个体满足谓词I(x)。
37
例2.3 ：
（7）x y(x+y=0) （8）y x (x+y=0)
（9）y x (xy=0) （10）x y(xy=0)
38
例：
对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”： （1）x(E(x)→┐x=1)
解：（1）x(E(x)→┐x=1) 真 x(E(x)→┐x=1) 可表示成命题公式 (E(0)→┐0=1)∧(E(1)→┐1=1) 其中E(0)→┐0=1真，E(1)→┐1=1也真， 故(E(0)→┐0=1)∧(E(1)→┐1=1)真。
3
谓词演算引入的必要性
例如：考虑下面的语句：
p：n是一个奇数。 数学中的常用判断无法用命题逻辑的形式准确 描述。
4
谓词演算引入的必要性
再例： 在命题演算中 ，对下述论断无法判断 其正确性。 “苏格拉底三段论” ： P 所有的人都是要死的， q 苏格拉底是人， 所以苏格拉底是要死的。 r 命题演算不足的原因——忽略了命题内部的细 节。

离散数学教学大纲精选全文

离散数学教学大纲精选全文

精选全文完整版可编辑修改离散数学教学大纲一、教学目标本课程的教学目标是：1．学习和掌握离散型关系结构的构成及分析方法，包括：集合论的主要内容：集合的基本概念、二元关系、函数、自然数和基数等；图论的主要内容：图的基本概念、欧拉图与哈密尔顿图、树、图的矩阵表示、平面图、图的着色、支配集、覆盖集、独立集与匹配、带权图及其应用等；2. 学习和掌握离散型代数结构的构成、性质和分析方法，熟悉半群、群、环、域、格、布尔代数等有着重要应用背景的代数模型；3. 学习和掌握组合配置的存在性证明和计数方法，并用于离散结构的性质分析。

4. 学习和掌握命题逻辑、一阶谓词逻辑的基本概念和推理方法。

5. 能够理论联系实际，用上述离散数学的描述工具和分析方法对实践中的离散系统进行建模和分析。

6. 通过严谨证明及正确逻辑推理的训练，进一步培养学生的抽象思维、计算思维能力和专业素质。

二、教学内容1．集合（教材第一章）●引言●预备知识（命题逻辑）●预备知识（一阶谓词逻辑）●集合的概念和集合之间的关系●集合的运算●基本的集合恒等式2．二元关系（教材第二章）●有序对与卡氏积●二元关系●关系的表示和关系的性质●关系的幂运算和闭包●等价关系和划分●序关系3．函数（教材第三章）●函数的基本概念、性质、合成、反函数4．自然数（教材第四章）●自然数的定义●自然数的性质5．基数（教材第五章）●集合的等势、有穷集合与无穷集合●基数和基数的比较与运算6．图（教材第七章）●图的基本概念●通路与回路●无向图和有向图的连通性●无向图的连通度7．欧拉图与哈密顿图（教材第八章）●欧拉图●哈密顿图8．树（教材第九章）●树9．图的矩阵表示（教材第十章）●图的矩阵表示10．平面图（教材第十一章）●平面图的基本概念●欧拉公式与平面图的判断●平面图的对偶图与外平面图●平面图与哈密顿图11．图的着色（教材第十二章）●点着色和色多项式●平面图着色和边着色12．支配集、覆盖集、独立集与匹配（教材第十三章）●支配集、点覆盖集、点独立集●边覆盖数与匹配●二部图中的匹配13．带权图及其应用（教材第十四章）●中国邮递员问题和货郎问题14. 代数系统（教材第十五章）●二元运算及其性质●代数系统、子代数和积代数●代数系统的同态与同构●同余关系与商代数15. 半群与独异点（教材第十六章）●半群与独异点16 . 群（教材第十七章）●群的定义和性质、子群●循环群、变换群与置换群●群的分解、正规子群与商群、群的同态与同构17. 环与域（教材第十八章）●环与域18. 格与布尔代数（教材第十九章）●格的定义和性质、子格、格同态与直积●模格、分配格、有补格与布尔代数19. 组合存在性定理（教材第二十章）●鸽巢原理和Ramsey定理20. 基本的计数公式（教材第二十一章）●两个计数原则、排列组合●二项式定理与组合恒等式●多项式定理21. 组合计数方法（教材第二十二章）●递推方程的公式解法●递推方程的其他求解方法●生成函数的定义和性质●生成函数、指数生成函数及应用●Catalan数与Stirling数22. 组合计数定理（教材第二十三章）●包含排斥原理与对称筛公式●Burnside引理与Polya定理23. 命题逻辑（教材第二十六章）●引言●命题和联结词●命题形式和真值表●联结词的完全集●推理形式●命题演算自然推理形式系统N●命题演算形式系统P●N与P的等价性●赋值与等值演算●命题范式●可靠性、和谐性与完备性24. 一阶谓词逻辑（教材第二十七章）●一阶谓词演算的符号化●一阶语言●一阶谓词演算形式系统NL●一阶谓词演算形式系统KL●NL与KL的等价性●KL的解释与赋值●KL的可靠性与和谐性●KL的和谐公式集三、教学方式以课堂讲授为主，辅以作业和练习，并配备助教对作业进行批改。

谓词演算与消解(归结)原理_图文

谓词演算与消解(归结)原理_图文
否定与全称量词、存在量词之间的关系 。 对于谓词 P, Q, 变元 X, Y有： ~彐X P(X) ＝ X ~P(X) ~ X P(X) ＝ 彐X ~P(X) 彐X P(X) ＝ 彐Y P(Y) X Q(X) ＝ Y Q(Y) X (P(X)∧Q(X) ) ＝ X P(X)∧ Y Q(Y) 彐X (P(X)∨Q(X) ) ＝ 彐X P(X)∨彐Y Q(Y)
2.savings (adequate)∧income (adequate ) => investment (stocks).
3. Savings (adequate)∧income (inadequate) => investment (combination).
4. X amountsaved (X)∧彐Y(dependents (Y)∧ greater (X, minsavings (Y))) => savings (adequate).
3.2 谓词演算
原子命题：是一个n元谓词，后跟n个项，用括号括起来
并用逗号分开。 常元符
例：
号
谓词符号
likes (george, kate). likes (X, george).
likes (george, susie). likes (X, X).
likes (george, sarah, tuesday).
谓词演算的字母表组成： （1）英文字母组合，包括大写与小写 （2）数字集合0,1,…,9 （3）下划线 如：George fires bill xxxx
3.2 谓词演算
谓词演算符号包括： 1.真值符号 true 和 false。 2.常元符号,第一个字符为小写字母的符号表达式。 3.变元符号,第一个字符为大写字母的符号表达式。 4.函词符号,第一个字符为小写字母的符号表达式, 函 词有一个元数, 指出从定义域中映射到值域中的每个元 素。

谓词演算与消解(归结)原理-图文

谓词演算与消解(归结)原理-图文

3.3.3 合一的一个例子
在此基础上又调用: unify (((father bill) (mother bill)), ((father bill) Y )) 导致调用: (1) unify((father bill),(father bill)) unify (father, father) unify (bill, bill) unify (( ), ( )) 所有的调用都成功,返回空代入集 { }。 (2) unify ((mother bill), Y)
与谓词相关的一个正整数称为元数或“参数数目”， 具有相同的名但元数不同的谓词是不同的。
真值true和false也是原子命题。
任何原子命题都能够用逻辑操作符将其变成谓词演 算的命题。用的联结词也和命题演算一样: ∨,∧, ~, => 和＝。
当一个变元在一个命题中作为参数出现时,它代表 的是域中不特定的对象。谓词演算包括两个符号, 量词（全称量词）和彐（存在量词）, 用于限定 包含变元的命题的含义。
3.2.2 谓词演算的语义
谓词演算表达式的真值 设有表达式E和在非空论域D上对E的一个解释I，E的
真值按以下规律决定： 1）一个常元的值是根据I指派给它的D的一个元素。 2）一个变元的值是根据I指派给它的D的一个元素集合
。 3）一个函词的值是根据由I指派给它的参数值计算得
到的D的元素。 4）真值符号true的值是T，false的值是F。 5）原子命题的值或者为T，或者为F，取决于解释I。 6）如果一个命题的值为F，则其否定式为T，否则为F
▪
~ (P∧Q) ＝ (~P∨~Q)
▪分配律：P∨(Q∧R) ＝ (P∨Q)∧(P∨R)
▪ 分配律：P∧(Q∨R)＝(P∧Q)∨(P∧R)

离散数学中,谓词公式和命题公式的区别

离散数学中,谓词公式和命题公式的区别

离散数学是一门研究离散对象及其性质的数学分支，它在计算机科学、信息技术以及工程领域具有重要的应用价值。

在离散数学中，谓词公式和命题公式是两个重要的概念，它们在逻辑推理和证明中起着至关重要的作用。

本文将对谓词公式和命题公式进行详细的比较与分析。

1. 谓词公式谓词公式是一种含有变量的复合命题，它通常用来描述对象之间的关系或者属性。

谓词公式由谓词符号和变量组成，例如P(x)、Q(x, y)等。

在谓词公式中，变量可以取代具体的对象，从而得到一个具体的命题。

谓词公式一般可以表示为∀x(∃yP(x, y))，其中∀表示全称量词，∃表示存在量词，P(x, y)表示谓词公式。

谓词公式的真假取决于变量的取值范围和具体的谓词定义。

谓词公式的真假可以通过逻辑运算和推理来确定，通常需要使用证明方法或者真值表等工具来进行验证。

2. 命题公式命题公式是一个不含变量的简单命题，它通常用来表示一个完整的陈述或者断言。

命题公式可以是一个简单的原子命题，也可以是多个原子命题通过逻辑连接词组合而成的复合命题。

“今天下雨”、“2加2等于4”等都可以看作是命题公式。

命题公式的真假只取决于公式本身的内容，它只有两种取值：真和假。

命题公式可以通过真值表的方法来验证其真假，并且可以使用逻辑等价和逻辑推理来进行推导和证明。

3. 谓词公式和命题公式的区别从上面的比较可以看出，谓词公式和命题公式在以下几个方面有着明显的区别：3.1 变量的使用谓词公式使用变量来表示对象之间的关系，而命题公式不含有变量，它是一个固定的陈述或者断言。

谓词公式可以根据变量的取值范围得到不同的命题，而命题公式的真假只取决于公式本身的内容。

3.2 真假的判断谓词公式的真假取决于变量的取值范围和具体的谓词定义，需要使用证明方法或者真值表来进行验证；而命题公式的真假只取决于公式本身的内容，可以通过真值表的方法来验证其真假，并且可以使用逻辑等价和逻辑推理来进行推导和证明。

3.3 表达的含义谓词公式通常用来描述对象之间的关系或者属性，它具有一定的泛化和普适性；而命题公式通常用来表示一个完整的陈述或者断言，它具有明确的含义和指向性。

谓词公式及解释

谓词公式及解释
好比有2个李勇，一个是正坐在家里看电视的“李勇”，
一个是在马路上散步的“李勇”，
为了避免这种“误会”出现，要对“约束变元”改名。
谓词公式及解释-个体变元的身份 例题 分析x(F(x)G(y))y(H(x)L(x,y,z))变
元身份 解：尽管x在公式x(F(x)G(y))出现，又在
y(H(x)L(x,y,z))出现，但两个x不是一回事， 只是恰巧二个名字相同而矣，
x是量词的指导变元。 (F(x,y)G(x,z))是量词的辖域 在 (F(x,y)G(x,z))中x是约束出现，出现2次。 在(F(x,y)G(x,z))自由出现的变元y/z，各一次。
谓词公式及解释-个体变元的身份 量词指导变元：xA和xA中的x 量词辖域：xA和xA中的A为量词/辖域 变元的约束出现：指导变元的每次出现(称约束变元)。 变元的自由出现：不是约束出现的变元(称自由变元) 。 例题 x(F(x,y)G(x,z)) 例题 x(F(x)G(y))y(H(x)L(x,y,z)) 解：
与变元约束情况
解：x、y的作用域是(P(x,y)Q(y,z))， x的作用域是P(x,y)。
将与自由变元同名约束变元yr， 将与前一个同名约束变元xs，则原公式
xr(P(x,r)Q(r,z))sP(s,y)
谓词公式及解释-个体变元的身份 例题 x(P(x)xQ(x,z)yR(x,y))Q(x,y)
(4)同一样公式在不同的论域下真值不同，究竟 如何确定一个公式的真值呢？
谓词公式及解释
非逻辑符号:个体常元、函数符号、谓词符号 逻辑符号:个体变元、量词符号、联结词、逗号、 括号。
项的定义：个体常元与变元及其函数式为项。
(1)个体常元和个体变元是项。 (则2)若(t1,(tx2,1…,x,2,t…n)是, x项n)是。n元函数,t1,t2,…tn是n个项， (3)有限次使用(2)得到的表达式是项。 原子公式：

谓词逻辑的基本概念

谓词逻辑的基本概念

• 从而(Vx)P(x)＝F成立，当且仅当有一个 x0 D，使P(x。)＝• 这命题中“有的”就是表示个体变元数量的词，“有的”
的等义词有“存在一个”、“有一个”、“有些”．这
句话的意思是说有一事物，它是动物．或有一x，x是动
物．
(x)( x是动物）
可形式描述x为(x 是动物）
4.4.1 “所有的有理数都是实数”的形式化
• 所有的有理数都是实数，其意思是说，对任一 事物而言，如果它是有理数，那么它是实 数．即对任一x而言，如果x是有理数，那么x 是实数．若以P(x)表示x是有理数，Q(x)表示x 是实数，这句话的形式描述应为
(x)(P(x) Q(x))
• 因为x的论域是一切事物的集合，所以x是有理 数是一个条件．
4.2.2 量词
• 用来表示个体数量的词是量词，也可看作是对个体词 所加的限制、约束的词．但主要不是对数量一个、二 个、三十……的具体描述，而是讨论两个最通用的数 量限制词，—个是“所有的”—个是“至少有一个”， 分别称什全称量词和存在量词．在某种意义上说。这 是一对相对立的词。
全称量词
“凡事物都是运动的”
• 从而
＝F．当且仅当对所有的 都有Q(x)＝F
4.2.2 约束变元和自由变元
• 在一个含有量词的命题形式里，区分个体词受 量词的约束还是不受量词的约束是重要的．无 论在定义合式公式以及对个体变元作代入时都 需区分这两种情形．
• 若P(x)表x是有理数，这时的变元x不受任何量 词约束，便称是自由的．而( x)P(x)中的两处 出现的变元x都受量词 的约束，便称作约束变 元，受约束的变元也称被量词量化了的变元．
• 命题逻辑表达问题能力，仅限于联结词的使 用．而谓词逻辑由于变元、谓词、量词和函数的 引入具有强得多的表达问题能力，已成为描述计 算机所处理知识的有力工具，AI将谓词逻辑看作 是一种基本的知识表示方法和推理方法

第2章 谓词演算

第2章 谓词演算

§2.2
谓词演算的关系式
§2.2.1 基本定义
当个体变元和谓词变元用确定的个体和谓词取代，就称作谓词公式赋值，此时就 称为具有真值 T 和 F 的命题。 定义 2.2.1 谓词公式 G 在个体域 D 上的一个解释（指派）I，是对给定个体域（非 空）D，并对公式 G 中谓词变元、自由变元（也叫命题变元、个体变元）做如下 指定组成： 1) 对每个 n 元谓词变元，指定一个定义在 D 上的谓词（常元） 。 2) 对每个个体变元，指定 D 中的一个个体。 定义 2.2.2 设 G 为任意谓词公式，E 是论述域。如果 G 对 E 上的所有解释 I 均取 真值 T，则称 G 在 E 上永真。若 E 是全总个体域，则称 G 永真。 定义 2.2.3 设 G 为任意谓词公式，E 是论述域。如果 G 对 E 上的所有解释 I 均取 真值 F，则称 G 在 E 上永假。若 E 是全总个体域，则称 G 永假。 定义 2.2.4 设 G 为任意谓词公式，E 是论述域。如果 G 对 E 上的所有解释 I 至少 有一个取真值 T，则称 G 在 E 上可满足。若 E 是全总个体域，则称 G 可满足。 定义 2.2.5 设 A 和 B 为任意谓词公式，E 是论述域。如果对 E 上的每一解释 I， A 与 B 真值相同， 则称 A 与 B 在 E 上等价。 若 E 是全总个体域， 则称 A 与 B 等价， 表示为：AB。 类似地，可定义 AB。

量词后面若有括号不能省略。 命题演算公式是谓词演算公式的一个特例。
§2.1.4 自由变元与约束变元
量词(x)、( x)中，、后面紧跟的变元是量词的指导变元或作用变元。 紧跟量词后面的最小公式是量词的作用域或辖域。 定义 2.1.3 在谓词公式中若出现量词，则与前面量词的指导变元相同且出现在量 词作用域内的变元叫约束变元，否则叫自由变元。 例 9 说明以下公式的作用域和变元的约束情况。 1) (x)[P(x)Q(x)] 2) (x)[P(x) ( y)R(x，y)] 3) (x) (y)[P(x，y)Q(x，y)](x)P(x，y) 4) (x)[P(x)(z)Q(x，z)(y)R(x，y)]Q(x，y) 对于 P(x1 ，x2 ， … ，xn )，若有 k 个变元进行约束，则成为 n-k 元谓词，如果 没有自由变元，就是一个命题。 为了避免由于变元的约束与自由同时出现引起概念混乱，可对约束变元改名， 改名规则如下：

数学离散数学PPT课件

数学离散数学PPT课件
(b) 对公式 A: F(x, y)∧M→F(u, x)中的 F, 欲代以 B: G(x1)∨H(x2, s)→H(t, x2), 则只需x , y , u不是B内的约 束变元, 而且s , t不是A内的约束变元。 代入结果为 (G(x)∨H(y, s)→H(t, y))∧M→(G(u)∨H(x, s)→H(t, x))
第22页/共41页
表 1.7 -1 含有量词的永真公式概要表
第23页/共41页
谓词演算规则
1、代入规则 2、替换规则 3、对偶原理
第24页/共41页
1. 代入规则
(i)自由个体变元的代入：在一公式中, 任一自由个体变元 可代以另一个体变元, 只需该个体变元出现的各处都同样代入, 且代入的变元不允许在原来公式中以约束变元出现。 例: 在公式xP(x, y)∨Q(w, y)中, 将y代以z, 则得xP(x, z)∨Q(w, z)， 将y代以w, 则得xP(x, w)∨Q(w, w)。 所得公式称为原公式的代入实例。
1.后边的r个自由变元 不允许在原公式中以约束变元出现; 2. F(x1,x2, …, xn)中的变元也不允许在代入的公式中以约束变元 出现。
第26页/共41页
例: (a) 对公式(P→Q) (P∨Q)中的P代以xP(x), Q代以S(x), 得
(xP(x)→S(x)) (xP(x)∨S(x))
Q4
xP(x) xQ(x)
E14
第31页/共41页
(b) 证明
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
证： 根据CP规则, 上式等价于
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
而 x(P(x) Q(x)) x(R(x) Q(x))

5.谓词演算5.15.5

5.谓词演算5.15.5
（2）必要性：设S’是不可满足的，讨论如下：
① 设C为真，则C1,C2, …Cn中至少有一个Ci为假， ∵ Ci ∈ S ∴ S是不可满足的
② 设C为假，则由 ~ C ~（Ci Cj） 可知： Ci，Cj中至少有一个为假
且Ci，Cj∈S ∴ S是不可满足的 证闭
(2) 命题逻辑归结 归结过程：给定公理集F（前提）和命题P（结论） ① 用子句形式表示公理集F，得到子句集S0 ② 将P的否定式～ P用子句表示，构成子句集S= S0 ∪{~P} ③ 反复利用归结方法，直到得出空子句（即矛盾式），证明结束 例：已知公理集如下
归结树：
~P∨~Q∨R
P
~Q∨R ~Q ~T
~R ~T∨Q
T
NIL
5.2.3 谓词逻辑归结 合一：寻找项对变量的置换，使表达式达到一致的过程称为合一。 项：由常量、变量和函数组成。 表达式的例：在表达式中，用置换项置换变量后得到的特定表达式。 例如：表达式 P(x, f(y), B) , 用z置换x，用w置换y，得到一个置换例
9 更换变元名称： （变元分离标准化）
（1）~ P(x1) ~ P( y) P( f (x1, y)) （2）~ P(x2) Q(x2, g(x2)) （3）~ P(x3) ~ P(g(x3))
关于公式标准化的讨论： （1）利用斯托林函数标准化得前束范式称为S_标准形。 （2） S_标准形不唯一。选择不同的斯托林函数可以得到不同的S_标准形。 （3）公式F与其S_标准形Fs在F非永假时不等价。
证毕
一个重要结论： P Q ~ Q ~ P
同理，可以得到：（C1C2） C ~ C ~（C1C2）
推论： 设C是子句Ci和Cj的归结式， 则子句集S={C1,C2, …Cn}与子句S’={C,C1,C2, …Cn} 的不可满足性是等价的 其中： Ci，Cj∈S

离散第13讲 谓词演算基本概念

离散第13讲 谓词演算基本概念
F(x): x怕死
当x的个体域是人类时
x ┐F(x)
当x的个体域是所有对象(全总域)时
H(x)：x是人（限定谓词,特性谓词） x(H(x)∧┐F(x))
x(H(x)→┐F(x)) ×
第13讲 谓词演算基本概念
-19-
存在量词(existential quantifier)
如果x的个体域是整数，P(x)表示“x=x+1”， 求xP(x)的真值 如果x的个体域是实数集合，求x(x2<0)的真 值；
词公式成为关于个体域的一个命题，可判定其真值 存在量词： ；指导变元：x，作用域：S(x) ，其中x为约束变元 对确定的个体域和谓词S， xS(x)是一个命题：个体域中有一个 对象，具有谓词S定义的性质 S(x1) ∨S(x2) ∨ … ∨ S(xn)
第13讲 谓词演算基本概念
对T(x) ：x没有任何量词约束，且x是个体变元，称为自由变元
如果个体域是复数集合，求x(x2<0)的真值
第13讲 谓词演算基本概念
-20-
谓词公式（predicate formula）
定义：以下条款规定的符号串称谓词公式，简称公式
(1)谓词填充式是公式，命题常元是公式(看作零元谓词)；
(2)如果A，B是公式，x为任一变元，那么(┐A)，(A→B)， (xA)，(x A)
否定
每个同学都学过高等数学 P(x)：x学过高等数学；xP(x) 不是每个同学都学过高等数学 ┐xP(x) 有的同学学过法语 P(x)：x学过法语； xP(x) 并没有同学学过法语 ┐ xP(x)
有的同学没有学过高等数学
x ┐P(x)
语句 xP(x) 等价语句 ┐ x ┐P(x)
所有的人都是要死的 D(x): x是要死的 当x的个体域是人类时

离散谓词

离散谓词
– – – – – 只要p，就q 因为p，所以q p仅当q 只有q才p 除非q才p
– 除非q，否则非p
5
等值词 ↔
P Q 0 0 1 1 0 1 0 1 P↔Q 1 0 0 1
• 若 P,Q 表示命题，则 ‘P 等值于Q’ 也是命题,记为 P↔Q, 读为 ‘P等值于Q’. • P↔Q 的真值表如右表所示. 由真值表可知 P↔Q 为真, 当且仅当P与Q有相同的真 值.
基本等值式
1.双重否定律 A ┐┐A 2.幂等律A A∨A, A A∧A 3.交换律A∨B B∨A， A∧B B∧A 4.结合律 (A∨B)∨C A∨(B∨C) (A∧B)∧C A∧(B∧C) • 5.分配律 A∨(B∧C) (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) (A∧B)∨(A∧C) （∧对∨的分配律） • 6.德· 摩根律 ┐(A∨B) ┐A∧┐B ┐(A∧B) ┐A∨┐B • 7.吸收律 A∨(A∧B) A，A∧(A∨B) A • • • •
(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的 真值。
说 明
公式A与B具有相同的或不同的真值表，是指真值表的最 后一列是否相同，而不考虑构造真值表的中间过程。
• 求下列公式的真值表 • ┐(p→q)∧q∧r
重言式、永真式、可满足式
• 设A为任一命题公式 • (1)若A在它的各种赋值下取值均为真,则称A是 重言式(tautology)或永真式。 • (2)若A在它的各种赋值下取值均为假,则称A是 矛盾式(contradiction)或永假式。 • (3)若A不是矛盾式,则称A是可满足式 （satisfactable formula）。
定义：在仅含有联结词 , ，，的命令题公式 A中，将换成，将换成，同时T和F（既0和1） 互相替代，所得公式A*称为A的对偶式。 写出下列命题公式的对偶式 A：（PQ）R 则A*为（PQ）R A：（PQ）（P（QS） 则A*为（PQ）（P（QS）） A：（（PQ）0）（1（RP）） 则A*为（（PQ）1）（0（RP））

第2章 逻辑代数(下)：谓词演算

第2章 逻辑代数(下)：谓词演算

第2章逻辑代数（下）：谓词演算2.1 谓词演算基本概念2.1.1 个体谓词演算中把一切讨论对象都称为个体(individuals)，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。

确定的个体常用a，b，c等小写字母或字母串表示。

a，b，c等小写字母或字母串称为个体常元(constants)。

不确定的个体常用字母x，y，z，u，v，w等来表示。

它们被称为个体变元，或变元(variables)。

谓词演算中把讨论对象——个体的全体称为个体域(domain of individuals)，常用字母D表示，并约定个体域都是非空的集合。

当讨论对象未作具体指定，而是泛指一切客体时，个体域特称为全总域(universe)，用字母U表示。

当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。

表示D上运算的运算符与常元、变元可组成所谓个体项(terms)。

例如，数学中的代数式a2+b，x2c等。

由于在我们讨论的谓词演算中，其变元只能取值个体对象，不能取值函数、命题或谓词，因此，它又常被叫做一阶谓词演算。

2.1.2 谓词2.1.3 量词谓词演算中的量词(quantifiers)指数学中常用的数量词“所有的”（或“每一个”）和“有”（或“存在”），用符号∀和∃来表示，分别称为全称量词和存在量词。

为了用全称量词∀表示个体域中所有（每一个）个体满足一元谓词P，用存在量词∃表示有（存在）个体满足一元谓词P，还需使用变元：∀xP(x) 读作“所有（任意，每一个）x满足P(x)”，表示个体域中所有的个体满足谓词P(x)。

∃x P(x) 读作“有（存在，至少有一个）x满足P(x)”，表示个体域中至少有一个体满足谓词P(x)。

当量词用于一谓词填式或复合的谓词表达式时，该谓词或复合的谓词表达式称为量词的辖域(domains of quantifiers)。

因此，量词的辖域或者是紧邻其右侧的那个谓词；或者是其右侧第一对括号内的表达式。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

讨论对象——个体的全体称为个体域（domain of i ndividuals），常用字母D表示。约定任何D都至少 含有一个成员 当讨论对象遍及一切客体时，个体域特称为全总域 （universe），用字母U表示 表示个体域上个体间运算的运算符与个体常元、变 元组成个体项（terms），例如a+b、x2+2、f(x)等
第13讲 谓词演算基本概念
-26-
谓词的自然语句形式化
由于确定了个体域，语句的形式化相对简单 当语句涉及不同类的个体时，给语句的形式化带来 一点复杂性
涉及全总个体域的某个局部的所有个体或某些个体时，要 使用限定谓词限定该局部 限定谓词与其他谓词之间应使用适当的联接词
━ 当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件 ━ 当限定谓词用于限定存在量词时，它必须作为合取词的合取 项
p: 2是偶数，可以表示成：O（2） q: 4是偶数，可以表示成：O（4）
第13讲 谓词演算基本概念
-5-
示例
6大于4 5大于3 2大于5 三个独立的原子命题，在命题演算中不能再分解 模式是：（ ）大于（ ）,大于是两个数之间的关系 L（x，y）：“x大于y”
6大于4 ，可以表示成：L（6，4）
如果个体域是复数集合，求x(x2<0)的真值
第13讲 谓词演算基本概念
-20-
谓词公式（predicate formula）
定义：以下条款规定的符号串称谓词公式，简称公式
(1)谓词填充式是公式，命题常元是公式(看作零元谓词)；
(2)如果A，B是公式，x为任一变元，那么(┐A)，(A→B)， (xA)，(x A)
命题推理能 力的局限性
第13讲 谓词演算基本概念 -3-
命题演算的局限
p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的
(所有人都)是要死的 (苏格拉底)是人 (苏格拉底)是要死的
1、命题演算将对确定对象进行判断的具有明确真值的陈述句 作为一个整体进行分析和处理，忽略了陈述句内部的结构
F(x): x怕死
当x的个体域是人类时
x ┐F(x)
当x的个体域是所有对象(全总域)时
H(x)：x是人（限定谓词,特性谓词） x(H(x)∧┐F(x))
x(H(x)→┐F(x)) ×
第13讲 谓词演算基本概念
-19-
存在量词(existential quantifier)
如果x的个体域是整数，P(x)表示“x=x+1”， 求xP(x)的真值 如果x的个体域是实数集合，求x(x2<0)的真 值；
x(P(x) ∧Q(x)) ∧ xS(x) →T(x) 对x(P(x) ∧Q(x)) ： 全称量词：；指导变元：x，作用域：P(x)∧Q(x)，其中x为约束 变元 对确定的个体域和谓词P、Q， x(P(x) ∧Q(x))是一个命题：个体 域中的任一对象，都具有谓词 P和Q定义的性质 1、给定了个体域和谓词的意义，那么谓词公式的真值只 取决于自由变元的取值，与约束变元无关。 (P(x 1) ∧Q(x1)) ∧ (P(x2) ∧Q(x2)) ∧ … ∧ (P(xn) ∧Q(xn)) 、给谓词公式中每一自由变元都指定具体的个体时，谓 对2 xS(x) ：
第13讲 谓词演算基本概念
-25-
谓词的自然语句形式化
例5.4
设个体域是人类
有人勇敢，但不是所有的人都勇敢
B(x)：x是勇敢的 x B(x) ∧ ┐ x B(x)
我为人人， 人人为我
H(x,y)：x为(帮助)y x H(我,x) ∧ x H(x,我)
勇敢者未必都是成功者
B(x)：x是勇敢的 ┐x (B(x) →S(x)) S(x)：x是成功的
━ P(0)∧P(1)∧P(2)∧P(3) ∧ …
第13讲 谓词演算基本概念
-14-
问题 P(x): x2 >= 6 P(0)、P(1)、P(2)为假，P(3)为真 存在不超过3的自然数x，使x2 >= 6 ━ P(0)∨P(1)∨P(2)∨P(3) 存在自然数x，使x2 >= 6 ━ P(0)∨P(1)∨P(2)∨P(3) ∨ …
-24-
第13讲 谓词演算基本概念
谓词公式的表述
P(x)：x每天花2小时学习英语，x的个 体域是学生的集合
xP(x) x┐P(x) xP(x) x┐P(x) ┐xP(x) ┐xP(x)
有的学生每天花2小时学习英语
有的学生每天不花2小时学习英语
所有学生每天都花2小时学习英语 所有学生每天都不花2小时学习英语 没有学生每天花2小时学习英语 不是所有的学生每天花2小时学习英语
词公式成为关于个体域的一个命题，可判定其真值 存在量词： ；指导变元：x，作用域：S(x) ，其中x为约束变元 对确定的个体域和谓词S， xS(x)是一个命题：个体域中有一个 对象，具有谓词S定义的性质 S(x1) ∨S(x2) ∨ … ∨ S(xn)
第13讲 谓词演算基本概念
对T(x) ：x没有任何量词约束，且x是个体变元，称为自由变元
2+x+1,0) yE(y2+y+1,0) yE(y （3） 表示：有一个实数x，满足x2+x+1=0 真值：假
xE(x2+x+1,0)
yE(y2,y) （4） xE(x2,y) zE(z2,y) 表示：有一个实数x，满足x2=y 真值：当y大于等于0时，为真；当y小于0时，为假；
第13讲 谓词演算基本概念 -23-
S(x)：x聪明 M(x)：x是人 x (M(x) ∧S(x)) ∧ ┐x (M(x) → S(x))
第13讲 谓词演算基本概念
-28-
谓词的自然语句形式化
所有步行的、骑马的或乘车的人，凡是口渴的，都 喝泉水
2+4=8 ，可以表示成： S（2，4，8）
第13讲 谓词演算基本概念
-7-
《离散数学》第13讲
谓词演算基本概念
Textbook Page 79 to 85
内容提要
谓词演算基本概念
个体、个体域 谓词 全称量词、存在量词 约束变元、自由变元
谓词公式 自然语句的形式化
第13讲 谓词演算基本概念
谓词命名式中的变元仅仅是谓词形式表示的一部分，没有 独立意义
第13讲 谓词演算基本概念
-12-
谓词填式
在谓词的空位处填入具体的个体常元或变元后得到 一个关于该个体的语句，这时它被称为谓词填式， 如M(scorates)，R(x)等 当谓词填式中所填个体都是常元时，得到一个命题， 有确定的真值
第13讲 谓词演算基本概念
-11-
谓词 （predicate）
刻画个体（或客体）的性质，或个体之间的关系的 模式称之为谓词
谓词是由谓语和空位所组成的，一个空位是一元谓 词，两个空位是二元谓词，三个空位是三元谓词 为增强可读性，常用变元来代替空位，如H(x)，L （x，y），S（x，y，z）等，这些式子叫做谓词命 名式，简称谓词
2、上述句子讨论事物的性质，并涉及所讨论的对象在全体和 个体上的联系
性质1：……是要死的：所有人都具有“要死的”性质
性质2：……是人： 苏格拉底 “是人”
两种主体：苏格拉底是所有人的组成部分 (元素)，因此也具有“要死 的”性质
第13讲 谓词演算基本概念 -4-
示例
2是偶数 4是偶数 p: 2是偶数;q:4是偶数 p、q是两个独立的原子命题 模式是：（ ）是偶数 O(x)：x是偶数
-22-
谓词公式的真值
设D为实数域，E(x，y)表示D上的关系“x=y”，L (x，y)表示“x < y”，则有
2+1) yL(0, y （1）xL(0, 表示：所有的实数x，满足0<x2+1
x2+1)
真值：真
xE(y2-2y-1,0) yE(y2-2y-1,0) （2） xE(x2-2x-1,0) 表示：有一个实数x，满足x2-2x-1=0 真值：真
如果x的个体域包含超过4的正整数，P(x)表示 “x2<10”， 求xP(x)的真值 如果x的个体域是实数集合， 求x(x2>=0)的真 值；
如果个体域是复数集合，求x(x2>=0)的真值
第13讲 谓词演算基本概念
-18-
存在量词(existential quantifier)
有的人不怕死
否定
每个同学都学过高等数学 P(x)：x学过高等数学；xP(x) 不是每个同学都学过高等数学 ┐xP(x) 有的同学学过法语 P(x)：x学过法语； xP(x) 并没有同学学过法语 ┐ xP(x)
有的同学没有学过高等数学
x ┐P(x)
语句 xP(x) 等价语句 ┐ x ┐P(x)
计算机专业基础课程
1.
授课人：张桂芸 dyxy1999@
PowerPoint Template_Sub
1
谓词演算基本概念
谓词演算永真式
2 3
谓词公式的前束范式
-2-
第13讲 谓词演算基本概念
命题演算的局限
所有人都是要死的，苏格拉底是人，那么苏格 拉底也是要死的。
p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的 p∧q┝r：p∧q→r为永真式吗？
所有的人都是要死的 D(x): x是要死的 当x的个体域是人类时
xD(x)
当x的个体域是所有对象的集合(全总域)时
H(x)：x是人（限定谓词,特性谓词） x(H(x)→D(x)) x(H(x)∧D(x)) ×
第13讲 谓词演算基本概念
-17-
全称量词(universal quantifier)
5大于3 ，可以表示成： L（5，3） 2大于5 ，可以表示成： L（2，5）
第13讲 谓词演算基本概念 -6-