当前位置：文档之家 › 2015离散数学谓词演算与前束范式

2015离散数学谓词演算与前束范式

  • 格式：ppt
  • 大小：890.50 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

离散数学 前束范式

离散数学 前束范式
第二步换名
D (x)[ P( x) (z)Q( z, y) (w) R( x, w)]
第三步消去条件联结词
D (x)[( P( x) (z)Q( z, y)) (w) R( x, w)]
第四步将否定深入
D (x)[P( x) (z)Q( z, y)) (w)R( x, w)]
离散数学
Discrete Mathematics
第5讲 §2—6 前束范式 要求：理解前束范式、前束合取范式和前束 析取范式的定义，会将一个谓词公式wffA化 为前束范式、前束合取范式和前束析取范式。 学习本节的目的是掌握谓词公式的标准化形 式。 重点：化谓词公式为前束范式。
复习：
（1）量词与联结词¬之间的关系
(x)(y)(z)(u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u))
例题3 把公式
(x){(y) A( x, y) (x)(y)[ B( x, y) (y)( A( y, x) B( x, y))]}
化为前束范式
解 第一步否定深入
原式
(x){(y) A( x, y) (x)(y)[ B( x, y) (y)( A( y, x) B( x, y))]} (x){(y) A( x, y) (x)(y)[B( x, y) (y)(A( y, x) B( x, y))]}
例如，(x)(y)(z)(P(x,y)Q(y,z))，R(x,y)等
都是前束范式，而(x)P(x)(y)Q(y)， (x)(P(x)(y)Q(x,y))不是前束范式。
定理2.6.1 (前束范式存在定理) Lp中任意公式A都有与之等价 的前束范式。 斯柯林范式 前束范式的优点是全部量词集中在公式前面，其缺点是各量词 的排列无一定规则，这样当把一个公式化归为前束范式时， 其表达形式会显现多种情形，不便应用。1920年斯柯林 (Skolem)提出对前束范式首标中量词出现的次序给出规定： 每个存在量词均在全称量词之前。按此规定得到的范式形式， 称为斯柯林范式。显然，任一公式均可化为斯柯林范式。它 的优点是：全公式按顺序可分为三部分，公式的所有存在量 词、所有全称量词和辖域。这给Lp的研究提供了一定的方 便。

《离散数学》谓词逻辑

《离散数学》谓词逻辑

§3.5 前束范式
§3.6 谓词逻辑的推理
4
谓词与量词
个体词（individual）是一个命题里表示思维
对象的词，表示独立存在的具体或抽象的客体
具体的、确定的个体词称为个体常项，一般用
a, b, c 表示
抽象的、不确定的个体词称为个体变项，一般
用 x, y, z 表示
个体变项的取值范围称作个体域或论域
那么在解释2下该命题是真命题。

24
谓词公式及分类
类似于命题逻辑，也可以对谓词逻辑
公式进行分类：
设 A 为一个谓词公式，若 A 在任何解
释下真值均为真，则称 A 为普遍有效
的公式或逻辑有效式（logically valid
formula）
例
(x)
(P(x)∨P(x))
(x) P(x) P(y)
第三章 谓词逻辑
《离散数学及应用》
第三章 谓词逻辑
苏格拉底三段论：
凡是人都是要死的。
苏格拉底是人。
所以苏格拉底是要死的。
p∧q r
重言式？正确的推理？
2
第三章 谓词逻辑
为了克服命题逻辑的局限性，引入了
3
谓词和量词对原子命题和命题间的相
互关系做进一步的剖析，从而产生了
为谓词。这是一元（目）谓词，以
P(x), Q(x), …表示。
例
Human
(Socrates)
Mortal (Socrates)
7
谓词与量词
如果在命题里的个体词多于一个，那
么表示这几个个体词间的关系的词称
作谓词。这是多元（目）谓词，有 n
个个体的谓词 P(x1, …, xn) 称 n 元（目）

离散数学第二章谓词逻辑2-6前束范式

离散数学第二章谓词逻辑2-6前束范式

离散数学第⼆章谓词逻辑2-6前束范式在命题演算中，常常要将公式化成规范形式，对于谓词演算，也有类似情况，⼀个谓词演算公式，可以化为与它等价的范式。

定义2-6。

1 ⼀个公式，如果量词均在全式的开头，它们的作⽤域，延伸到整个公式的末尾，则该公式叫做前束范式。

前束范式可记为下述形式：（□v1）（□v2）…（□v4）a，其中□可能是量词或量词ヨ，v i（i=1，2，3，…，n）是客体变元，a是没有量词的谓词公式。

例如（"x）（"y）（$z）（q（x，y）®r（z）），（"y）（"x）（øp（x，y）®q（y））等都是前束范式。

定理2-6.1 任意⼀个谓词公式，均和⼀个前束范式等价。

证明⾸先利⽤量词转化公式，把否定深⼊到命题变元和谓词填式的前⾯，其次利⽤（"x）（aúb（x））ûaú（"x）b（x）和（$x）（aùb（x））ûaù（$x）b（x）把量词移到全式的最前⾯，这样便得到前束范式。

例题1 把公式（"x）p（x）®（$x）q（x）转化为前束范式。

解（"x）p（x）®（$x）q（x）û（$x）øp（x）ú（$x）q（x）û（$x）（øp（x）úq（x））例题2 化公式（"x）("y)(($z)(p(x,y)ùp(y,z))®($u)q(x,y,u))为前束范式。

解原式û（"x）（"y）（ø（$z）（p（x，z）ùp（y，z））ú（$u）q（x，y，u））û（"x）（"y）（（"z）（øp（x，z）úøp（x，z））ú（$u）q（x，y，u））û（"x）（"y）（"z）（$u）（øp（x，z）úøp（x，y）úq（x，y，u））例题3 把公式ø（"x）{（$y）a（x，y）®（$x）（"y）[b（x，y）ù（"y）（a（y，x）®b（x，y））]}化为前束范式。

自考离散数学第2章

自考离散数学第2章

定义2.1.1 由一个谓词，一些个体变元组成的表达式简称为谓词变项或
命题函数。
谓词变项中，个体变元的数目称为谓词变项的元数。 如F(x)为一元谓词，L(x,y)为二元谓词。F(a)（a为常量）为0元谓词
2.1 谓词的概念与表示
例：以谓词表达下述命题。 某人大于18岁，身体健康，无色盲，大学毕业，则他可参加飞行员考
R(x):x是资深专家。
前提 结论
(x)(M ( x) H ( x) G(s)) (x)(M ( x) R( x)) (x)(M ( x) R( x) G( x))
域E，若对 A和B的任一组变元进行赋值，所得命题的真值相同，则称 谓词公式A和B在E上是等价的，并记作 A B
定义2.3.2 给定任意谓词公式WffA，其个体域为E，对于A的所有赋值
WffA都为真，则称WffA在E上有效的（或永真的）
定义2.3.3 一个谓词公式WffA，如果在所有赋值下都为假，则称WffA
式称为复合命题函数。
定义2.2.2 谓词演算的合式公式，可由下述各条组成（合式公式A记为
WffA）：
（1）原子谓词公式是合式公式。 （2）若A是合式公式，则¬A是一个合式公式。 （ 3 ）若 A 和 B 都是合式公式，则（ A ˅B ），（ A ˅B ），（ A → B ），
（A↔B）是合式公式。
等词。用符号“ x ”表示。 表示个体域里所有个体，都有性质F。 等词。用符号“ x ”表示。 表示存在个体域中的个体具有性质F。
表示对个体域里所有的 x，而 xF ( x)
2. 存在量词：对应日常语言中的“存在的”“有一个”“至少有一个”

表示存在个体域中的个体，而 xF ( x)

离散数学(第四章)解读.

离散数学(第四章)解读.

§2.1 一阶逻辑命题符号化
例如，下列推理： 所有的人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 众所周知,这是真命题。但在命题逻辑中,如 果用P,Q,R表示以上三个命题，则上述推理过 程为：（P∧Q）R。借助命题演算的推理理 论不能证明其为重言式。

§2.1 一阶逻辑命题符号化
原因：命题逻辑不能将命题之间的内在联系 和数量关系反映出来。 解决办法：将命题进行分解。
§2.1 一阶逻辑命题符号化
设谓词H表示“是劳动模范”, a表示个体名称 张明, b表示个体名称李华,c表示个体名称这只老 虎，那么H(a) 、 H(b)、 H(c)表示三个不同的命 题,但它们有一个共同的形式,即H(x).一般地， H(x)表示客体x具有性质H。这里x表示抽象的或 泛指的客体，称为个体变元，常用小写英文字 母x, y, z, …表示。相应地，表示具体或特定的客 体的词称为个体常项，常用小写英文字母a,b,c, …表示。
§2.1 一阶逻辑命题符号化
刻划一个个体性质的词称之为一元谓词 ,刻划 n 个个 体之间关系的词称之为n元谓词. 一般我们用大写英文字母表示谓词，用小写英文字 母表示客体名称，例如，将上述谓词分别记作大写 字母F、G、H、R，S则上述命题可表示为： (1) F(a) a：张明 (2) F(b) b：李华 (3) G(c) c：王红 (4) H(s,t) s：小李 t：小赵 (5) R(a,b,c) (6) S(a,b) a:阿杜 b:阿寺 其中(1)、(2)、 (3)为一元谓词， (4) 、 (6)为二元谓词 ， (5)为三元谓词。
2.5谓词演算的推理理论(Inference theory of
predicate calculus)
§2.1 一阶逻辑命题符号化

离散数学第2章 谓词逻辑

离散数学第2章 谓词逻辑
命题“凡人要死。”符号化为：(x)F (x) ⑵ 令G(x)：x是研究生。 命题“有的人是研究生。”符号化为：(x)G(x)
在命题函数前加上量词(x)和(x)分别叫做个体变元x 被全称量化和存在量化。一般地说，命题函数不是命题， 如果对命题函数中所有命题变元进行全称量化或存在量化， 该函数就变成了命题。这一结论在例2.3中得到验证。
为假。 ⑵ 如果5大于3，则2大于6。 解：设G(x,y)： x大于y a：5，b：3，c：2，d：6 该命题符号化为：G(a,b)→G(c,d) G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，
ห้องสมุดไป่ตู้这是个假命题。所以G(a,b)→G(c,d)为假。
(3) 2 是无理数, 而 3 是有理数 解 ：设F(x): x是无理数, G(x): x是有理数 符号化为 F( 2) G( 3) 真值为 0 (4) 如果2>3，则3<4 解：设 F(x,y): x>y, G(x,y): x<y, 符号化为 F(2,3)G(3,4) 真值为1
谓词：刻划个体性质或个体之间相互关系的模式叫做谓词。谓 词常用大写英文字母表示，叫做谓词标识符。
例如可以用F，G，H表示上面三个命题中谓词： F：„是优秀共产党员。 G：„比„高。 H：„坐在„和„的中间。
第2章 谓词逻辑
一元谓词：与一个个体相关联的谓词。如上例中的F。 二元谓词：与两个个体相关联的谓词。如上例中的G。 三元谓词：与三个个体相关联的谓词。如上例中的H。
返回章目录
第2章 谓词逻辑
课外作业
• 教材P59-60页: 练习题（需要做在练习本上） （1） （2） a)、c) 、d)、e)、 f)、i)、k)、l)
返回章目录

离散数学教程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 命题演算不足的原因——忽略了命题内部的细 节。

2015离散数学谓词演算与前束范式


prenex normal form
Any expression can be converted into prenex normal form. To
do this, the following steps are needed:
1. Eliminate all occurrences of and from the formula in
消去下列公式的量词
设个体域D ={a,b}
a) xF ( x) yG( y) b) xy( F ( x) G( y)) c) xy( F ( x) G( x, y)) d) x( F ( x, y) yG( y))
量词否定等值式
Negation:
¬ ∀xP(x) ∃x ¬ P(x). ¬ ∃xQ(x) ∀x ¬ Q(x).
Predicates and Quantifiers
谓词和量词
将下列命题符号化
（1）兔子比乌龟跑得快 （2）有的兔子比乌龟跑得快 （3）并不是所有的兔子都比乌龟跑得快 （4）不存在跑得同样快的两只兔子
将下列命题符号化
（1）有的汽车比有的火车跑得快 （2）有的火车比所有的汽车跑得快 （3）说所有的火车比所有汽车都跑得快是不对的 （4）说有的飞机比有的汽车慢也是不对的
斯柯伦范式skolem
每个存在量词均在全称量词之前
AI型斯柯伦范式
e) xF ( x) xG( x) f ) xF ( x) xG( x) g) xF ( x) xG( x) L( x, y) h) (xF ( x) xG( x))
Basic Rules about Quantification
US: xP(x)P(c)

离散数学23.前束范式

1.定义：如果一个谓词公式符合下面条件，它就是前束范式：所有量词都在公式的开头；所有量词的辖域都延伸到公式的末尾.
例如(y)(x)(z)(A(x)→(B(x,y)∨C(x,y,z))) ,
(x)(A(x)→B(x)),就是前束范式.
而(x)A(x)∧(y)B(y),
(x)(y)(A(x)→(B(x,y)∧(z)C(z))),
学情分析
学生已经学习了变元的约束，能够利用谓词演算的等价公式进行演算。
教学评价
师生互动，启发式教学引导学生思考并进而解决问题；深入分析，用例题加深学生对知识点的理解。
课程资源
参考书目，网上教学视频，网络微课。
教学过程：
与命题公式的范式类似，谓词公式也有规范形式。这里主要介绍前束范式--所有量词都在公式前边约束变元.
(x)(P(x)∨R(x))∨((y)P(y)∧Q(z)) (换变元)
(x)(P(x)∨R(x))∨(y)(P(y)∧Q(z)) (扩量词辖域)
(x)(y)((P(x)∨R(x))∨(P(y)∧Q(z))) (扩量词辖域)
定义2.6.2一个谓词公式A，如果具有形式：
(v1)(v2)…(vn)((A11A12…A1l1)(A21A22…A2l2)…(Am1Am2…Amlm))
将一个谓词公式化为前束合取范式或前束析取范式时，只需在前面求前束范式的（1）～（4）四个步骤基础上再增加一个步骤：
（5）利用分配律将公式化为前束合取范式或前束析取范式.
补充说明
4)用量词辖域扩张公式提取量词，使之成为前束范式形式.
例1. (x)A(x)→(x)B(x)
(x)A(x)∨(x)B(x)
(x)A(x)∨(x)B(x)
(x)A(x)∨(y)B(y) (换元)

离散第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的个体域是人类时
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
e) xF ( x) xG( x) f ) xF ( x) xG( x) g) xF ( x) xG( x) L( x, y) h) (xF ( x) xG( x))
Basic Rules about Quantification
US: xP(x)P(c)
prenex normal form
Any expression can be converted into prenex normal form. To
do this, the following steps are needed:
1. Eliminate all occurrences of and from the formula in
量词分配等值式
Distributing ∀ through ∧
∀x (P(x) ∧ Q(x)) ⇔ ∀x P(x) ∧ ∀x Q(x) Distributing ∃ through ∨ ∃x (P(x) ∨ Q(x)) ⇔ ∃x P(x) ∨ ∃x Q(x)
Laws of quantifer distribution
前束范式prenex normal form
一个公式如果量词均包含在全式的开头，它 们的作用域延伸到整个公式的末尾，则该公式叫 做前束范式。
设A是一个谓词公式，如果A具有如下形式：
(Q1x1)(Q2x2) …(Qnxn)B， 其中Qi (1≤i≤n）为 或，xi为客体变元，B为不含量词的谓词公式， 则称A是前束范式。
1. (x)A(x)∨(x)B(x) (x)(A(x)∨B(x))
2.(x)(A(x)∧B(x)) (x)A(x)∧(x)B(x)
量词次序蕴含式
1.(x)(A(x)∨B(x)) (x)A(x)∨(x)B(x) 2.(x)(A(x)∧B(x)) (x)A(x)∧(x)B(x)
question. 2. Move all negations inward such that, in the end, negations only appear as part of literals. 3. Standardize the variables apart (when necessary). 4. The prenex normal form can now be obtained by moving all quantiers to the front of the formula.
将下列命题符号化
（1）火车都比汽车快 （2）有的火车比有的汽车快 （3）不存在比所有火车都快的汽车 （4）说凡是汽车就比火车慢是不对的
Two tasks:
(1) 一些等值式 (2) 前束范式
消去量词等值式
设D={a1,a2,…,an}
xA(x)A(a1)A(a2)…A(an) xA(x)A(a1)A(a2)…A(an)
全称指定规则 Universal instantiation UG: P(x)xP(x) 全称推广规则 Universal generalization ES: xP(x)P(c) 存在指定规则 Existential instantiation EG: P(c)xP(x) 存在推广规则 Existential generalization
斯柯伦范式skolem
每个存在量词均在全称量词之前
AI型斯柯Байду номын сангаас范式
消去下列公式的量词
设个体域D ={a,b}
a) xF ( x) yG( y) b) xy( F ( x) G( y)) c) xy( F ( x) G( x, y)) d) x( F ( x, y) yG( y))
量词否定等值式
Negation:
¬ ∀xP(x) ∃x ¬ P(x). ¬ ∃xQ(x) ∀x ¬ Q(x).
量词辖域的收缩与扩张
设A(x)是含x自由出现的公式，B中不含x的出现
关于全称量词的：
x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x))BxA(x) 关于存在量词的: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x))BxA(x)
Predicates and Quantifiers
谓词和量词
将下列命题符号化
（1）兔子比乌龟跑得快 （2）有的兔子比乌龟跑得快 （3）并不是所有的兔子都比乌龟跑得快 （4）不存在跑得同样快的两只兔子
将下列命题符号化
（1）有的汽车比有的火车跑得快 （2）有的火车比所有的汽车跑得快 （3）说所有的火车比所有汽车都跑得快是不对的 （4）说有的飞机比有的汽车慢也是不对的
求下列公式的前束范式
a) xF ( x) yG( x, y) b) xF ( x, y) yG( x, y, z ) c) x1( F ( x1) G( x1, x2 )) (x2 H ( x2 ) x3L( x2 , x3 ))
d) x1F ( x1, x2 ) ( F ( x1) x2G( x1, x2 ))