当前位置：文档之家 › 大连理工大学软件学院 离散数学 第二章 谓词逻辑-2nd

大连理工大学软件学院 离散数学 第二章 谓词逻辑-2nd

  • 格式：ppt
  • 大小：561.00 KB
  • 文档页数：45

下载文档原格式

  / 45

合集下载

离散数学谓词逻辑课后总结

离散数学谓词逻辑课后总结

第二章谓词逻辑2—1基本概念例题1. 所有的自然数都是整数。

设N(x):x是自然数。

I(x):x是整数。

此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。

设E(x):x是偶数。

此命题可以写成?x(N(x)∧E(x))例题3. 每个人都有一个生母。

设P(x):x是个人。

M(x,y):y是x的生母。

此命题可以写成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化例题1. 如果x是奇数,则2x是偶数。

其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x,谓词O(x):x是奇数,E(x):x是偶数,则此命题可以表示为:?x(O(x)→E(g(x)))例题2 小王的父亲是个医生。

设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。

例题3 如果x和y都是奇数,则x+y是偶数。

设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y))命题的符号表达式与论域有关系两个公式:一般地,设论域为{a1,a2,....,an},则有(1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an)(2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an)1.每个自然数都是整数。

该命题的真值是真的。

表达式?x(N(x)→I(x))在全总个体域的真值是真的,因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。

例如(N(0.1)→I(0.1))也为真。

而?x(N(x)∧I(x))在全总个体域却不是永真式。

?x(N(x)∧I(x))?(N(a1)∧I(a1))∧(N(a2)∧I(a2)) ∧…∧(N(an)∧I(an)) 比如x用0.2代入(N(0.2)∧I(0.2))就为假。

离散数学2_谓词逻辑

离散数学2_谓词逻辑

• 在一个谓词公式中，如果某个客体变元既 以约束变元形式出现，又以自由变元形式 出现，就容易产生混淆。为了避免此现象 发生，可以对客体变元更改名称。 如 x(F(x,y)→yP(y))∧Q(z) • 约束变元的改名规则： (1).对约束变元可以更改名称，改名的范围 是：量词后的指导变元以及该量词的辖域 内此客体变元出现的各处同时换名。 (2).改名后用的客体变元名称，不能与该量 词的辖域内的其它变元名称相同。
z的辖域
y的辖域
x的辖域
一般地， • 如果量词后边只是一个原子谓词公式时， 该量词的辖域就是此原子谓词公式。 • 如果量词后边是括号，则此括号所表示 的区域就是该量词的辖域。 • 如果多个量词紧挨着出现，则后边的量 词及其辖域就是前边量词的辖域。
2-2.5 自由变元与约束变元
• 在谓词公式中的客体变元可以分成两种， 一种是受到量词约束的，一种是不受量词 约束的。请看下面公式： • x(F(x,y)→yP(y))∧Q(z) Ｆ(x,y)中的x在x的辖域内，受到x的 约束，而其中的y不受x的约束。 P(y)中的y在y的辖域内，受y的约束。 Q(z)中的z不受量词约束。
第二章 谓词逻辑
问题的提出：(即命题逻辑的局限性)
在第一章, 一个原子命题只用一个字母表示， 而不再对命题中的句子成分细分。这样有一些逻 辑问题无法解决。请看下面的例子。 例1.令Ｐ：小张是大学生。 Ｑ：小李是大学生。 从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共 性。我们希望从所使用的符号那里带给我们更多 的信息，比如可以看出他们的共性。这种想法在 第一章是无法实现的。
2-1.5 量词
• 例如：有些人是大学生。 所有事物都是发展变化的。 “有些”,“所有的”,就是对客体量化的词。 • 定义：在命题中表示对客体数量化的词，称之 为量词。 • 定义了两种量词： (1).存在量词：记作，表示“有些”、“一 些”、 “某些”、“至少一个”等。 (2).全称量词：记作，表示“每个”、“任 何 一个”、“一切”、“所有的”、“凡是”、

精品文档-离散数学(第二版)(武波)-第2章

精品文档-离散数学(第二版)(武波)-第2章

第2章 谓词逻辑
例如， “x是偶数”可以用谓词P(x)表示， P(2)、 P(3) 分别表示“2是偶数”、 “3是偶数”。 “x小于y”可以用 谓词Q(x， y)表示， Q(5， 7)、 Q(6， 5)分别表示“5小于 7”、 “6小于5”。 “x在y和z之间”可以用谓词R(x, y, z)表示， R(a, b, c)表示“a在b和c之间”。
第2章 谓词逻辑
定义2.3.3 设A是谓词公式， 如果对于任何赋值， A的 真值都为真， 则称谓词公式A是永真式； 如果对于任何赋值， A的真值都为假， 则称谓词公式A是永假式； 若存在一种赋 值， 使得A的真值为真， 则称谓词公式A是可满足式。
由定义可知， 对于任意谓词公式A， 若A是永真式， 则 A在特定论域E上永真； 若A是永假式， 则A在特定论域E上永 假； 若A在特定论域E上可满足， 则A是可满足式。
…… n元谓词用于刻画n个个体之间的关系， 由一个表示n个 个体关系的大写字母(称为n元谓词符、 n元关系符)和n个个 体常元或变元组成的表达式表示， 如R(a1, a2, …, an)、 R(x1, x2, …, xn )等。 根据以上约定， 谓词就可以简单地描述为是由一个谓词 符和若干具有有固定次序的个体常元或变元组成的表达式。 带有 n(n≥0)个个体的谓词称为n 元谓词。
所有命题， 如“所有的人都要呼吸”、 “有些有理数是自然
数”等。 为了刻画这类表示全称判断或特称判断的命题， 需
要引入量词( quantifier )。
1.
x表示“对于所有的x”、 “对于任一x”或“对于每
一个x”，
(universal
quantifier)，x是量词 的作用变元(指导变元)。
第2章 谓词逻辑

大连理工大学软件学院 离散数学 数理逻辑总结

大连理工大学软件学院 离散数学 数理逻辑总结

10
7.符号化下列命题并推证其结论的有效性。 １、明天是晴天，或者是下雨；如果是晴天， 我就去看电影；如果我去看电影，我就不看 书。结论：如果我在看书，则天在下雨。 解：首先符号化，并令 Ｐ：明天是晴天。 Ｑ：明天下雨。 Ｒ：明天我去看电影。 Ｓ：明天我看书。于是问题可描述成：
11
PQ,PR,RSSQ 1.S P规则(附加前提) 2.RS P规则 3.R T规则及１和２ 4.PR P规则 5.P T规则及3和4 6. PQ P规则 7.Q T规则及5和6 8. SQ CP规则及１和７
9
(2) A(A(AB))(AB)(AB)
解： 左A(A(AB)) A(BB)(A(BB)(AB)) (AB)(AB)(AB)(AB)(AB) (AB)(AB)(AB)(AB) m00,m01 ,m10,m11 右(AB)(AB)(AB)(AB) (AB)(AB) (A(BB)B(AA))(AB) (AB)(AB)(AB)(AB)(AB) (AB)(AB)(AB)(AB) m00,m01 ,m10,m11 问题得证。
总结
第二章
1. 基本概念 (1)个体词、谓词和量词： (2)个体常元、个体变元、约束变元、自由变元； (3)命题函数，个体域，全总个体域。 2. 谓词公式 (1)原子公式，谓词公式： (2)谓词公式的解释； (3)谓词公式的分类：永真公式，永假公式，可满足公式。
27 谓词逻辑
总结
第二章
3. 谓词公式间的关系 (1)谓词公式间的等价关系( (2)谓词公式间的蕴含关系( (3)基本的等价式； (4)基本的蕴含式；
E11
E1，E2 E7
∴（P → （Q → R）） （P → Q）∨（P → R）
5、求出下式的主析取范式 1）（PQ）（RP） 2）（PQ）（RP） 解：1）（PQ）（RP）=（PQ）（RP） =（PQ）（RP） =（PQR） （PQ） =（PQR） （PQ R）（PQ R） 2）（PQ）（RP）=（PQ）（RP） =（PQ）（RP） =（PQ）（RP） =（PR） （PQ R） =（PQR） （PQ R） =M0M2 =m1,m3,m4,m5,m6,m7 =(PQ R) (PQ R) (PQR) (PQR)

离散数学第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)
返回章目录

离散数学____第二章_谓词逻辑(很清晰)

离散数学____第二章_谓词逻辑(很清晰)
所以苏格拉底是要死的。 R 逻辑学中著名的三段论方法，是由一个 大前提，一个小前提推出结论的方法。
例如：著名的苏格拉底三段论： 苏格拉底（前469-前 显然这是正确的推理，但在命题逻辑中 399） 古希腊唯心主义 却无法(wúfǎ)得到证明。
哲学家。
P∧Q R
判断P∧Q→R是否重言式？ P∧Q R
关系P。 0元谓词：不含客体变元的谓词。如F(x) 为一元谓词、
P(x,y)为二元谓词，而F(a)、G(a,b)为0元谓词，即一 般的命题。
精品资料
例
设有如下命题，并用谓词进行表示(biǎoshì)。 P：王童是一个三好学生； Q：李新华是李兰的父亲；
SR：：是张一强个与(谢yī莉是ɡè好)三朋好友学；生 aFS：：：王武是童汉的位父于亲北京和广州之间。 命 Tb：题：李P新可与华表示是为好：朋S友(a)
精品资料
将命题(mìng tí)函数→命题(mìng tí) 的两种方法
1）将变元取定具体(jùtǐ)的值，如P(a),P(b)。 2）将谓词量化。如( x)P(x), ( x)P(x)。
精品资料
命题函数(hánshù)举例
例.设S(x)表示(biǎoshì)“x学习很好”, W(x)表示 (biǎoshì)“x工作很
好”, A(x)表示(biǎoshì)“ x身体好”
S(x) 表示(biǎoshì)“x学习不是很好”, S(x) ∧W(x) 表示(biǎoshì)“x学习和工作都很好”。
A(x)→( S(x)∧ W(x)) 表示(biǎoshì)“如果x身体不好，则x的学习与工作都不 会好”。 S(x), W(x)是简单命题函数, 而 S(x), S(x) W(x), A(x)→( S(x)∧ W(x))是复 合命题函数。

离散数学第二章谓词逻辑2-1谓词的概念与表示

离散数学第⼆章谓词逻辑2-1谓词的概念与表⽰命题是反映判断的句⼦，不反映判断的句⼦不是命题。

⼀般地说，反映判断的句⼦是由主语和谓语两部分组成。

例如，电⼦计算机是科学技术的⼯具。

其中“电⼦计算机”是主语，“是科学技术的⼯具”是谓语。

主语⼀般是客体，客体可以独⽴存在，它可以是具体的，也可以是抽象的。

例如：⼩王、⽼师、3、4、**代表团、唯物主义等。

⽤以刻划客体的性质或关系的即是谓词。

例如：张三是个⼤学⽣，李四是个⼤学⽣，这两个命题可能⽤不同的符号p、q表⽰，但是p和q的谓语有同样的属性：“是个⼤学⽣”。

因此引⼊⼀个符号表⽰“是个⼤学⽣”，再引⼊⼀种⽅法表⽰客体的名称，这样就能把“**是个⼤学⽣”这个命题的本质属性刻划出来。

⼜例如：(a)他是三好学⽣。

(b) 7是质数。

(c) 每天早晨做⼴播操是好习惯。

(d) 5⼤于3。

(e) 哥⽩尼指出地球绕着太阳转。

在上述语句中“是三好学⽣”、“是质数”、“是好习惯”、“⼤于”、“指出”都是谓词。

前三个是指明客体性质的谓词，后两个是指明两个客体之间关系的谓词。

我们将⽤⼤写字母表⽰谓词，⽤⼩写字母表⽰客体名称，例如a表⽰“是个⼤学⽣”，c表⽰张三，e表⽰李四，则a（c），a（e）分别表⽰“张三是个⼤学⽣”，“李四是个⼤学⽣”。

⽤谓词表达命题，必须包括客体和谓词字母两个部分，⼀般地说，“b是a”类型的命题可⽤a（b）表达。

对于“a是⼩于b”这种两个客体之间关系的命题，可表达为b（a，b），这⾥b表⽰“是⼩于”。

⼜如命题“点a在b与c之中”可以表⽰为l：…在…和…之中，故可记为l（a，b，c）。

我们把a（b）称作⼀元谓词，b（a，b）称作⼆元谓词，l（a，b，c）称作三元谓词，依次类推。

注意，代表客体名称的字母，它在多元谓词表⽰式中出现的次序与事先约定有关，因此未经约定前，上例记作l（a，b，c）或l（b，c，a）等都可以，但⼀经约定，l（a，b，c）与l（b，c，a）就代表两个不同的命题。

离散数学第二章谓词逻辑

一般来说，当多个量词同时出现时， 它们的顺序不能随意调换。
*
第二章 谓 词 逻 辑 命题函数与量词
当个体域为有限集合时，如D={a1, a2 …, an}，对任意谓词A(x)，有 xA(x)A(a1)∧A(a2)∧…∧A(an ) xA(x)A(a1)∨A(a2)∨…∨A(an )
特性谓词常作合取项，如x(M(x)∧ G(x))。
第二章 谓 词 逻 辑
命题函数与量词
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
例如：在实数域上用H(x,y)表示x+y=5，则命题“对于任意的x，都存在y使得x+y=5”可符号化为：xyH(x,y)，其真值为1。若调换量词顺序后为： yxH(x,y) , 其真值为0。
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
令S(x): x吸烟。则符号化为：
（x）(M(x)∧S(x))
令D(x): x登上过木星。则符号化为：
令Q(x):x是清华大学的学生。H(x):x是高
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
小结:本节介绍了n元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。
添加标题
x(M(x) F(x)).
添加标题
第二章 谓 词 逻 辑
添加标题
命题函数与量词
*
当个体域为全体学生的集合时：
01
令P(x): x要参加考试。则（2）符号化为
02
xP(x).
03
当个体域为全总个体域时：
04
令S(x): x是学生。则（2）符号化为
05
x(S(x) P(x)).

离散数学第2章 谓词逻辑

例4：某些人对某些食物过敏。 设F(x,y)：x对y过敏。 M(x)：x是人。 G(y)：y是食物。 (x) (y) (M(x) ∧ G(y) ∧ F(x,y))
33
§3 谓词公式与翻译
例5：凡是实数不是大于0，就是等于0或者小于0。 设R(x)：x是实数。 P(x,0)：x大于0。 Q(x,0)：x等于0。 S(x,0)：x小于0。 (x) (R(x) → ( P(x,0) Q(x,0) S(x,0) ) )
例：所有的人都是会死的。
设M(x)：x是人。S(x)：x是会死的。
个体域约定为{人类}：(x) (S(x))
全总个体域：
(x) ( M(x) → S(x) )
例：有一些人是不怕死的。
设M(x)：x是人。F(x)：x是不怕死的。
个体域约定为{人类}：(x) (F(x))
全总个体域：
(x) ( M(x) ∧ F(x) )
定义：在反映判断的句子中，用以刻划客体的性质或 关系的即是谓词。
5
§1 谓词的概念与表示法
客体，是指可以独立存在的事物，它可以是具体 的，也可以是抽象的，如张明，计算机，精神等。
表示特定的个体，称为客体常元，以a，b，c… 或带下标的ai，bi，ci…表示；
表示不确定的个体，称为客体变元，以x，y， z…或xi，yi，zi…表示。
4. 谓词中通常只写客体变元，因此不是命题，仅当 所有客体变元做出具体指定时，谓词才成为命题， 才有真值。
12
第二章 谓词逻辑
§1 谓词的概念与表示法 §2 命题函数与量词 §3 谓词公式与翻译 §4 变元的约束 §5 谓词演算的等价式与蕴含式 §6 前束范式 §7 谓词演算的推理理论
13
§2 命题函数与量词

大连理工大学软件学院离散数学习题答案

目录第一章命题逻辑 (2)第二章谓词逻辑 (9)第三章集合论习题答案 (13)第四章二元关系习题答案 (21)第五章函数习题答案 (42)第六章代数系统习题答案 (51)第七章群与环习题答案 (57)第八章格与布尔代数习题答案 (66)第九章图的基本概念及其矩阵表示 (71)第十章几种图的介绍 (82)第十一章树 (90)第一章命题逻辑1.（1）不是命题；（2）不是命题；（3）不是命题；（4）是命题；（5）是命题；2.（1）并非大连的每条街都临海；（2）2不是一个偶数或者8不是一个奇数；（3）2不是偶数并且-3不是负数；3.（1）逆命题：如果我去公园，那么天不下雨。

否命题：如果天下雨，我将不去公园。

逆否命题：如果我不去公园，那么天下雨。

（2）逆命题：如果我逗留，那么你去。

否命题：如果你不去，那么我不逗留。

逆否命题：如果我不逗留，那么你不去。

（3）逆命题：如果方程无整数解，那么n是大于2的正整数。

否命题：如果n不是大于2的正整数，那么方程有整数解。

逆否命题：如果方程有整数解，那么n不是大于2的正整数。

（4）逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。

否命题：如果我获得更多的帮助，则我能完成这项任务。

逆否命题：如果我能完成这项任务，则我获得更多的帮助。

4.（1）T；（2）T；（3）T；（4）F；5.6.（1）P:他聪明；Q:他用功；命题：P∧Q。

（2）P:天气好；Q:我骑车上班；命题：Q→P。

（3）P:老李是球迷；Q:小李是球迷；命题：P∨Q。

（4）P:休息好；Q:身体好；命题：Q→P。

7.8.9.（1）（P∧Q）→R；（2）┓P；（3）（┓P∧┓Q）→┓R10.不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。

本题可用真值表求解：（4）得真值表如下：1，故为重言式。

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

设D(x,y)表示“x可被y 整除” ,个体域 为 { 5,7 ,10 ,11 }.
因为D(5，5)和D(10,5)为真，所以 因为D(7，5)和D(11,5)为假，所以 xD(x,5)为真. xD(x,5)为假.
但有下面的推理过程：
(1) xD(x,5) 前提
(2) 错！ (3)
D(z,5)
xD(x,5)
离散数学
第二章 谓词逻辑
2/44
回顾
• 谓词、个体、量词
– 一元、多元、域、全称、存在
• 合式谓词公式
– 定义： 5条
• 自由变元和约束变元 • 含有量词的等价式和永真蕴含式 • 谓词公式的解释
2/43
记忆规律
(x)(y)
(y)(x)
B1
B2
(y )(x)
B3
(x)(y )
B4
(x)(y )
(x)( R ( x) (y )( D( y ) L( x, y ))) ( R(a ) (y )( D( y ) L( a, y ))) R(a) (y )( D( y ) L( a, y )) D(u ) L(a, u ) (x)( R ( x) (y )( S ( y ) L( x, y ))) R(a ) (y )( S ( y ) L( a, y )) (y )( S ( y ) L(a, y )) P ES , (1) T , (2) T , (2) US , (4) P US , (6) T , (3), (7)
5/43
规则1：约束变元的改名规则
• 例：对公式x(P(x, y) yQ(x, y, z)) S ( x, z)进 行换名，使各变元只呈一种形式出现。 解：
需要对约束变元x，y进行换名
u(P(u, y) vQ(u, v, z)) S(x, z)
不对的：
u(P(u, v) vQ(u, v, z)) S(x, z)
证明 (x)(y)(P( x) Q( y)) (x) P( x) (y)Q( y)
(1) (2) (3) (4) (5) (6) (7) (8) (x) P( x) P( a) (x)(y)(P( x) Q( y)) (y)(P( a) Q( y )) P ( a ) Q (b) Q (b ) (y)Q( y) (x) P( x) (y )Q(y) P(附加前提) ES , (1) P US , (3) US , (4) T , (2), (5) UG, (6) CP, (1), (7)
谓词逻辑中的推理
试证明(x)M ( x)是前提(x)( H ( x) M ( x)) 例1： 和(x) H ( x)的逻辑结果。
证明：
(1) (2) (3) (4) (5) (6) (x) H ( x) H ( y) (x)( H ( x) M ( x)) H ( y) M ( y) M ( y) (x) M ( x) P ES , (1) P US , (3) T , (2), (4) EG, (5)
26/43
谓词逻辑求解实际问题
24/43
谓词逻辑求解实际问题
• 步骤：
– 根据问题的需要定义一组谓词 – 将实际问题符号化 – 使用推理规则有效推理
• 注意：
– 符号化的原则：全称量词对应逻辑联结词→， 存在量词对应逻辑联结词Λ – 推理时首先引入带存在量词的前提，以保证 “ES”规则的有效性
25/43
谓词逻辑求解实际问题
例8：证明苏格拉底的三段论。
由于 证明： (x)P( x) (y)(Qy) (x) P( x) (y)Q( y) (x) P( x) (y)Q( y)
因此原来的证明转化为证明下式：
(x)(y)(P( x) Q( y)) (x) P( x) (y)Q( y)
22/43
谓词逻辑中的推理
接上页 (9) S (u ) L(a, u)
(10) L(a, u) S (u) (11) D(u ) S (u ) (12) (x)( D( x) S ( x))
US , (8) T , (9) T , (5), (10) UG, (11)
18/43
例4
指出下面推理的错误.
(1);ES
(2);UG xD(x,5).
19/43
因此， xD(x,5)
反证法举例
给定前提(x)( A( x) B( x)),(x)( B( x) C( x)),(x)C( x) 例5： 试推出结论： x) A( x) ((6) (7) (8) (9) (10)
12/43
规则5：量词的增加和删除规则
存在推广规则EG：从A(x) 可得出结论(y) A( y) ， 其中x是个体域中的某一个个体，即：
A( x) (y) A( y) 注意：y不和A(x)中其他自由变元或指导变元同名。
全称推广规则UG：从A(x) 可得出结论(y) A( y) ， 其中x是个体域中的任意个体，即：
– 注意：y不能和A(x)中其它指导变元重名。
• 存在特指规则ES：从 (x) A( x) 可得出结论A(a) ， 其中 a是 (x) A( x) 和在此之前不曾出现过的个体 常量，即： (x) A( x) A(a)
– 注意：a不能和指定前提中任一自由变元同名， 也不能和使用本规则以前任一推导步骤上得到的 公式的自由变元同名。
x(P(x, t) yQ(x, y, z) ) S(w, z)
7/43
例如
(
对公式 ( x) (P(x) →Q(x))∨(
x) (P(x) →R(x))
为清楚起见，可对第二个约束变元x进行换名
x) (P(x) →Q(x))∨( y) (P(y) →R(y)) 又例如 对公式 ( x) (P(x) →R(x,y)) ∧Q(x,y) 可对约束变元x进行换名，得 ( 错误： ( ( z) (P(z) →R(z,y)) ∧Q(x,y) z) (P(z) →R(x,y)) ∧Q(x,y)
A( x) (y) A( y) 使用条件: (1)x不是给定前提中任一公式的自由变元； (2)x不是在前面推导步骤中使用ES规则引入 的变元； (3)若在前面推导过程中使用ES规则引入新变 元u时，x是自由变元，那么在A(x)中，u应 约束出现。
13/43
• UG-------Universal Generalization • EG-------Existential Generalization • UI-------Universal Instantiation • EI-------Existential Instantiation • US-------Universal Specialisation • ES------- Existential Specialisation
1 2 n 1 2 n
10/43
谓词逻辑的推理
在谓词逻辑中，推理的形式结构仍为
若
则称由前提
是永真式，
逻辑的推出结论C，
在此
, C均为谓词公式。
11/43
规则5：量词的增加和删除规则
(x) A( x) A( y)
• 全称特指规则US：从 (x) A( x) 可得出结论A(y) ， 其中y是个体域中任一个体，即：
23/43
例7 对多个量词的使用情况，观察下列推理过程.
证明（1） （2） （3） 错！ （4） 错！ 前提 （1）；US （2）；ES （3）；UG
（5）
推出错误结论： 与
注意：公式(2)中z有两种可能
（4）；EG
可交换.
1)若z是自由个体变元，则此时y的值是随z的变化而变 化的，因此不能用ES规则将y改为个体常元d。 2)若z是个体常元，则公式(3)没错，但此时不能用UG规 则得到(4) 。
17/43
证明：
(1) (2) (3) (4) (5) (6) (7) (8)
谓词逻辑中的推理
已知前提(x)( R( x) (y)( D( y) L( x, y)))， (x)( R( x) (y)( S ( y) L( x, y))) 试推出结论： x)( D( x) S ( x)) (
(x) A( x) (x)A( x) A(a) (x)( A( x) B( x)) A(a) B(a) B(a) (x)(B(x) C(x)) B(a) C (a) C ( a ) (x)C(x)
P (假设前提 T , (1) ES , (2) P US , (4) T , (3), (5) P US , (7) T , (6), (8) P
15/43
谓词逻辑中的推理
例2：试证明
(x)( P( x) Q( x))，x)(Q( x) R( x)) (x)( P( x) R( x)) (
证明： (1) (2) (3) (4) (5) (6)
(x)( P ( x) Q ( x)) P ( x) Q( x) (x)(Q ( x) R( x)) Q ( x) R( x) P ( x) R( x) (x)( P ( x) R( x))
P US , (1) P US , (3) T , (2), (4) UG, (5)
16/43
谓词逻辑中的推理
已知前提(x)( R( x) (y)( D( y) L( x, y)))， 例3： (x)( R( x) (y)( S ( y) L( x, y))) 试推出结论： x)( D( x) S ( x)) (
B5
(y )(x)
B6
(y )(x)
B7 B 8 (x)(y)
3/43
2.2谓词逻辑中的推理规则
• 推理规则
4/43
规则1：约束变元的改名规则