离散数学---谓词逻辑推理 PPT课件

∀ xA( x) ∴ A( y )
应用US规则的条件是: A(x)对于y必须是自由的。 设 A( x) = ∃y( x > y) 则 ∀xA( x) = ∀x∃y( x > y) , x,y的 的 个体域为R， 是一真命题. 个体域为 ， 是一真命题 若应用US得 则是错误的。 若应用 得 ∃y( y > y) ，则是错误的。 正确的做法是换成 ∃y( z > y) ( z ∈ R)
用变元x取代 ， 则要求在 原公式中y不 用变元 取代y， 则要求 在 原公式中 不 取代 能出现在量词(∀ 或 ∃ 的辖域之内 的辖域之内。 能出现在量词 ∀x)或(∃x)的辖域之内。
16
第一章 数理逻辑
推理规则的正确使用（4）
推导4： （1）G(x, c) （2）(∃x)G(x, x) P EG,(2)
17
第一章 数理逻辑 1.8.3 推理举例 例1 根据前提集合：同事之间总是有工作矛盾的，张平和李 明没有工作矛盾, 能得出什么结论? ; 解 设P(x, y): x和y是同事关系, Q(x, y): a: 张平, x和y有工作矛盾, b: 李明,
则前提是:∀x∀y(P(x,y) → Q(x,y)) ， ┐Q(a,b) ∀ ∀
6
第一章 数理逻辑 这一规则也可写为:
∀ xA( x)推得A( x) 或
它的意义是, 全称量词可以删除。
∀ xA( x) ⇒ A( x).
7
第一章 数理逻辑 (2) 存在指定规则 存在特定规则 存在量词消去规则 ) 存在指定规则(存在特定规则 存在特定规则/存在量词消去规则 (Existential Specification)简记为ES。
15
第一章 数理逻辑

解法1 这只大红书柜摆满了那些古书。 解法2 x y 设 A(x)：x是书柜 设 F(x,y)：x摆满了y
解法1中R(x)表示x是大红书柜, 解法2中A(x) ∧B(x) ∧C(x)也 可表示大红书柜,但用A(x) ∧B(x) ∧C(x)将更方便于对 书柜的大小颜色进行讨论
B(x)：x是大的 D(y)：y是古老的 F(x,y)：x摆满了y
例题1 并非每个实数都是有理数。
设 R(x)：x是实数。 Q（x）：X是有理数。
每个实数都是有理数表示为： (x)( R( x) Q( x))
(x)( R( x) Q( x)) 并非每个实数都是有理数表示为：
例题2 没有不犯错误的人
解 本语句即为“不存在不犯错误的人”。 设 M(x)：x 是人。 F(x)：x犯错误。 “存在不犯错误的人”表示为： “不存在不犯错误的人”表示为：(x(M ( x) F ( x)) 等价于“任何人都要犯错误”或“所有人都要犯错误”。 所以此命题也可符号化为： (x)(M ( x) F ( x))
2.7谓词演算的推理理论
2
2.3谓词公式与翻译
一、谓词公式
• 定义1：n元谓词A(x1，x2...xn) 称为谓词演算的原子公式。 • 定义2：谓词演算的合式公式,可由下述各条组成: ① 原子公式是合式公式。 ② 若A 是合式公式，则(A)也是合式公式。 ③ 若A，B是合式公式，则(A ∧ B)，(A ∨ B)，(A B)， (A B)也是合式公式。 ④ 若A是合式公式，x是A中出现的任何变元 ,则(x)A , (x)A，也是合式公式。 ⑤ 只有有限次应用(1)~(4)得到的公式是合式公式.
练习1
（3）没有不能表示成分数的有理数。
解：令D(x): x是有理数。F(x):x能表示成分数。 则符号化为： (x)(D(x) F(x)) 或 (x)(D(x)∧ F(x)) 真值为１。

离散数学之谓词逻辑
1、合法而稳定的权力在使用得当时很 少遇到 抵抗。 ——塞 ·约翰 逊 2、权力会使人渐渐失去温厚善良的美 德。— —伯克
3、最大限度地行使权力总是令人反感 ；权力 不易确 定之处 始终存 在着危 险。— —塞·约翰逊 4、权力会奴化一切。——塔西佗
5、虽然权力是一头固执的熊，可是金 子可以 拉着它 的鼻子 走。— —莎士 比
6、最大的骄傲于最大的自卑都表示心灵的最软弱无力。——斯宾诺莎 7、自知之明是最难得的知识。——西班牙 8、勇气通往天堂，怯懦通往地狱。——塞内加 9、有时候读书是一种巧妙地避开思考的方法。——赫尔普斯 10、阅读一切好书如同和过去最杰出的人谈话。——笛卡儿
Thank you

A(a, H(b)) →F(a,b)
非一阶谓词 26/44
例3 符号化：我送他这本书。
解：令 A(e1，e2，e3)表示“e1送e3给e2”； B(e)表示“e为书”； a表示“我”； b表示“他”； c表示“这”；
则原句译为： A(a，b，c) B(c)
27/44
例4 符号化：这只大红书柜摆满了那些古书。
32/66
例 计算机学院的有些老师是青年教师
解： 设 C(e)表示e为计算机学院的人； T(e)表示e为教师; Y(e)表示e为青年.
则原句译为：
x(C(x)T(x) Y(x))
此例中：x就取值于全总个体域U， 谓词C(x)限定x取值范围。
33/66
例 个体域I为人类集合,将下列命题符号化:
(1) 凡人都呼吸。 (2) 有的人用左手写字。
21/44
一元谓词变元
A(x)
其中x为变量符号项、A为谓词变元。 此式表示x具有性质A。 注意：x，A分别在两个域上变化。
22/44
二元谓词变元
A(x，y)
其中x, y为变量符号项、A为谓词变元。 此式表示x和y具有关系A。 注意：x，y，A分别在三个域上变化。
23/44
二、谓词语句的符号化
例1 将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶
1A(e)如下图所示: e A1 A2 a TF
2 谓词数目：
14/44
个体域{a，b}上的一元谓词
A(e)如下图所示: e A1 A2 A3 A4 a TFTF b TTFF
22
谓词数目：
15/44
个体域{a，b，c}上的一元谓词
A(e)如下图所示:
e A1 A2 A3 A4 A5 A6 A7 A8

证明: (1). (x(P(x)S(x)))
(2). (3). 西 华 (4). 大 (5). 学 (6). (7). (8). (9). (10). (11). (12). (13). (14). (15). (16).
P规则
(1)E P(c)S(c) 全称量词消除规则 P(c) (3)I S(c) (3)I x(P(x)(Q(x)R(x))) P规则 P(c)(Q(c)R(c)) (6)全称量词消除规则，使用(3)中个体c Q(c)R(c) (4) (7)I x(P(x)(Q(x)S(x))) P规则 P(c)(Q(c)S(c)) 全称量词消除规则，使用(3)中个体c Q(c)S(c) (4) (11)I Q(c)S(c) (11)I Q(c) (12) (5)I R(c) (13) (8)I P(c) R(c) (4)和(14)的合取 x(P(x)R(x)) (15) 存在量词的引入
// 前提
(2). P(a)Q(a) // 全称量词消除规则
举例：全称量词消除规则
西 华 B 大 学
指出下列推导中的错误，并加以改正： (1). x P(x)Q(x) // 前提 (2). P(y)Q(y) // 全称量词消除规则
量词 x 的辖域为 P(x) ，而非 P(x)Q(x) ，所以不 能直接使用全称量词消除规则。
x(P(x)S(x))
前提：x(P(x)(Q(x)R(x)))、 x(P(x)(Q(x)S(x)))、 x(P(x)S(x))、 (x(P(x)S(x))) 结论：x(P(x)R(x))
一阶逻辑的永真蕴涵式
西 华 大 学
推理定律是一阶逻辑的一些永真蕴涵式，重要 的推理定律有： [1]. 附加律：A(AB) // 或称为析取的引入 [2]. 化简律： (AB)A, (AB)B // 或称为合取的消除 [3]. 假言推理： (AB)AB // 或称为分离规则 [4]. 拒取式： (AB)BA [5]. 析取三段论：(AB)BA [6]. 假言三段论：(AB)(BC)(AC) // 或称为传递规则

第二章谓词逻辑
第二章 小结
本章重点掌握内容： 1.各基本概念清楚。 2.会命题符号化。 3.熟练掌握等价公式和永真蕴涵式。 4.会写前束范式。 5.熟练3)b)P:2>1,Q(x):x≤3, R(x):x>5,a:5,{-2,3,6} x(P→Q(x))∨R(a)(P→xQ(x))∨R(a) (P→(Q(-2)∧Q(3)∧Q(6)))∨R(5) (T→(T ∧T ∧F ))∨F (T→F)∨FF∨F F (4)b)对约束变元换名 x(P(x)→(R(x)∨Q(x)))∧ xR(x)→zS(x,z) y(P(y)→(R(y)∨Q(y)))∧ tR(t)→uS(x,u) (5)a)对自由变元代入 (yA(x,y)→xB(x,z))∧ xzC(x,y,z) (yA(u,y)→xB(x,v))∧ xzC(x,w,z)
第二章谓词逻辑
(6)判断下面推证是否正确。 x(A(x)→B(x)) ⑴ x(A(x)∨B(x)) ⑵ x(A(x)∧B(x) ⑶ x(A(x)∧B(x)) ⑷ (xA(x)∧xB(x)) ⑸ xA(x)∨xB(x) ⑹ xA(x)∨xB(x) ⑺ xA(x)→xB(x) 第⑷步错，由⑶到⑷用的是公式： x(A(x)∧B(x))(xA(x)∧xB(x)) 无此公式，而是 x(A(x)∧B(x)) xA(x)∧xB(x)，应将⑷中的换成 即：
第二章谓词逻辑
例2.7.1 所有金属都导电。铜是金属。故铜导电。 令 M(x):x是金属。C(x):x导电。a:铜。 符号化为： x(M(x)→C(x)),M(a) C(a) ⑴ x(M(x)→C(x)) P ⑵ M(a)→C(a) US ⑴ ⑶ M(a) P ⑷ C(a) T ⑵⑶ I11
2-7 谓词演算的推理理论
第二章谓词逻辑

练习
5)并不是每个人都会来参加这次会议。
解：设N(x)：x是人，G(x)：x参加这次会议。
¬∀(() → ())
45
2.辖域
(1)∀(() → ∃()) ∧ ∃(, )
(2)∀() → ()
(3)∀∃((() → ()) ∧ ¬(, ))
x(M(x)→y(W(y)→H(x,y)))
x(M(x)∧y(W(y)∧H(y,x)))
29
11.2 谓词
几点说明：
1)不含量词的谓词公式，不是命题，是命题函数，其真
值依赖于x从个体域中取出的个体词的不同而不同。
如 D表示7班全体学生。
G(x)表示x是男生
xG(x)
真值
30
11.2 谓词
第11章 谓词逻辑
1
三段论
所有人都是要。
Q
R
谓词逻辑
2
谓词逻辑
§11.1 谓词与个体§11.2 量词
§11.4 谓词逻辑公式
§11.5 自由变元与约束变元
§11.6 谓词逻辑的永真公式
§11.7 谓词演算的推理理论
3
§11.1 谓词与个体
4
11.1 谓词与个体
真命题
假命题
简单命题函数：不含联结词的谓词
复合命题函数：由原子谓词及联结词组成的表达式
13
11.1 谓词与个体
例3. 张华是大学生，李明也是大学生。
令： P(x)：x是大学生。 a：张华 b：李明
P(a)∧P(b)
14
11.1 谓词与个体
所有人都是要死的。
?
苏格拉底是人。
苏格拉底要死。
15
§11.2 量词
如：设x,y的个体域是I，

2.1 谓词的概念与表示
▪ 谓词 在反映判断的句子中，用以刻划客体
的性质或关系的即是谓词。 例：(1)3是有理数。 (2)x是无理数。
(3)阿杜与阿寺同岁。 (4)x与yL。 其中，“是有理数”、“是无理数”、 “与…同岁”、“…与…有关系L”均为谓词。 前两个是指明客体性质的谓词，后两个是指 明两个客体之间关系的谓词。
▪ 原子公式 元谓词，t1,
t2若, …A,(xtn1是, xF2,的…任, x意n)是n个F 项的，任则意称n
A(t1, t2, …, tn)为谓词演算的原子公式。
2.3 谓词公式与翻译
▪ 谓词演算的合式公式/谓词公式
(1)原子公式是合式公式。 (2)若A 是合式公式，则 (A) 也是合式公式。 (3)若A和B是合式公式，则(A∧B)，(A∨B)，
▪ 但客体变元在哪些范围内取特定的值，对是 否成为命题及命题的真值极有影响。
例：R(x)表示“x是大学生”，如果x的讨论范 围是某大学里班级中的学生，则R(x)是永真式。 如果x的讨论范围是某中学里班级中的学生， 则R(x)是永假式。如果x的讨论范围为一剧场 中的观众，那么对某些观众，R(x)为真，对另 一些观众，R(x)为假。
2.2 命题函数与量词
▪ 简单命题函数 由一个谓词，一些客体变
元组成的表达式称为简单命题函数。 n元谓词就是有n个客体变元的命题函数。 不带任何客体变元的谓词称为0元谓词。
▪ 复合命题函数 由一个或n个简单命题函数
以及逻辑联结词组合而成的表达式称复合命 题函数。
2.2 命题函数与量词
▪ 命题函数不是一个命题，只有客体变元取特 定名称时，才能成为一个命题。
比y 跑得快。则 xy(T(x)∧S(y) F(x,y))

三、量词和全总个体域 1.量词
使用前面介绍的概念，还不足以表达日常生活中 的各种命题。
例如：对于命题 “ 所有的正整数都是素数 ”
和 “ 有些正整数是素数 ” 仅用个体词和谓词是很难表达的。 量词 在命题里表示数量的词。
（1） 全称量词
“ x”
x D（x）， 如“所有人都是要死的。”可表示为
三、换名规则和代入规则 1.换名规则
对约束变元进行换名，使得一个变元在一个 公式中只呈一种形式出现。 （1）约束变元换名时，该变元在量词及其辖域 中的所有出现均须同时更改，公式的其余部分不 变； （2）换名时，一定要更改为该量词辖域中没有 出现过的符号，最好是公式中未出现过的符号。
例8
对公式 进 x(P(x, y) yz (u, v, z) ) S(x, z)
x或 x的辖域。x在公式的x约束部分的任一出现都称为
x的约束出现。 公式中约束出现的变元是约束变元 当x的出现不是约束出现时，称x的出现是自由出 现 。 自由出现的变元是自由变元。
例7
指出下列各公式中的量词辖域及自
由变元和约束变元。
( 1 ) x y (( P ( x ) Q ( y )) zR ( z ))
行换名，使各变元只呈一种形式出现。
解 需对x，y换名
u(P(u, y) v Q(u, v, z)) S(x, z)
错误法： u(P(u, v) vQ(u, v, z)) S(x, z)
u(P(u, y) zQ(u, z , z)) S(x, z)
2.
代入规则
谓词、个体词和量词 谓词演算公式 谓词演算的永真公式 谓词演算的推理理论
谓词、个体词和量词 例

2-2 命题函数与量词
这里有一些人，Exist x,用反写 — 存在变量词， 用于表示个体域中的某些客体 （1）（x）（N（x） P（x））
（2）（x）（M（x） R（x）） （3）（x）（M（x） E（x）） 全称量词与存在量词统称为量词，每个由量词确定的表达式， 都与个体域有关，如： （x）（M（x） H（x）） M（x）是用于限定H（x）中的个体域， M (x）称为特性谓词，限定客体变元变化范围的谓词 当限定范围为M（x）中时，可简写为：（x）（H（x）） 此命题对于论域为人类时，是正确的，而对于自然数则是FALSE， 因为我们是讨论带有量词的命题函数时，必须确定其个体域，把 特性谓词写出来。并且，为了方便，我们将所有命题函数的个体域 全都统一，使用全总个体域。对变化范围用特性谓词加以限制。 一般地，对全称量词，将特性谓词作为前提条件，命题通常写成 条件式，对存在量词，常将之作为合取项。
定义：H是n元谓词，a1,a2,a3……an是n个客体，H(a1,a2……an)所代 表的式子是一个命题，称为谓词填式。（当ai是客体时，A(a1…an) 才是命题。）
3 除了谓词，我们今后还要用到函数这一概念 例：老张是小张的父亲。 小张的父亲=老张
f:….的父亲； a:小张； b:老张； 则b=f(a)
所以 (x)(M (x) F(x))也就是(x)(M (x) F(x))
(5)肖阳的爸爸到北京去了。 “…到…去了”是谓词。F(x,y): x到y去了。a:肖阳, f(x):x的爸爸， b:北京 所以F(f(a),b) (6)谢世平和他的父亲及祖父三人一起去看演出。
F(x,y,z): x,y和z一起去看演出
H(1,c) H(c,1) :张三、李四一样高
例3：P(x): x是大学生 x的个体域：某大学中某班 P(x)永真 x的个体域：某中学中某班 P(x)永假 x的个体域：某剧场中观众 P(x)有真有假

20
谓词演算的基本等价式
2024年11月24日
❖ 定理2-3.４：（量词分配侓）
❖ Ｅ35:(x)(P(x)∧Q(x))（x）P(x)∧（x）Q(x)
❖ Ｅ36:(x)(y)(P(x)∨Q(ｙ))(x)P(x)∨(x)Q(x)
❖ Ｅ37:(x)(ｙ)(P(x)∧Q(ｙ))（x）P(x)∧（x）Q(x)
❖ 4）仅仅由1)-3)产生的表达式才是合适公式。
6
谓词公式
2024年11月24日
❖ 例2.2 (P(x)→(Q(x,y)∨┐R(x,a,f(z))))
❖
(P(x)∨R(y))
❖
(x)(P(x))
❖ 等都是公式。
❖而
❖
(x)(P(x)→R(x)
❖
(x)∨P(x)(y)
❖ 等则不是公式，前者括号不匹配，后者量词无辖域。
❖ ❖
ＥＥ3389：：（（xx））((PP((xx))∨QQ((xx)))) （（xx））同词顺Pp一，序((xx类可而))∨型以不（（的交影量换响xx））QQ((xx))
❖ 定理2-3.５：（双量词公式的等价性其）等价性。
❖ Ｅ40：(x)(ｙ)Ａ(x，ｙ)（ｙ）（x）Ａ(x，ｙ) ❖ Ｅ41：(x)(ｙ)Ａ(x，ｙ)（ｙ）（x）Ａ(x，ｙ)
❖ 3)、解释I为： (x)(y)(P(x,y)→Q(x,y))。
❖
①.个体域为N；
❖
②.P(x,y)指定为：“x+y＝0”；
❖
③.Q(x,y)指定为：“x>y”。
❖ 则原公式的真值为“真”。
❖ 因对任意的x≠0,任意y∈N，有"x+y＝0"为“假”，所以 无论后件如何，都有 P(x,y)→Q(x,y)为“真”，

12
例题
在个体域分别为：(a):自然数集合，(b):实数集合时，将下列命题符号化， 并给出它们的真值。 1. 对于任意的x，均有x2−3x+2=(x−1)(x−2); 2. 存在x，使得x+5=2。
解 假设F(x)：x2−3x+2=(x−1)(x−2)，G(x)：x+5=2。 (a) 个体域为自然数集合。 1. 符号化为：xF(x)，真值为1。 2. 符号化为：xG(x)，真值为0。 (b) 个体域为实数集合。 1. 符号化为：xF(x)，真值为1。 2. 符号化为：xG(x)，真值为1。
注意：除非所有量词都是全称量词或存在量词，否则，多 个量词同时出现时，不能随意颠倒量词的顺序，颠倒后会改变 原命题的含义。
19
离散数学及其应用
1
第2章 谓词逻辑
2.1 谓词逻辑的基本概念 2.2 谓词合式公式 2.3 谓词公式的解释和分类 2.4 谓词演算的关系式 2.5 前束范式 2.6 谓词演算的推理
2
2.1谓词逻辑的基本概念
2.1.1 个体词和谓词 定义2.1.1 个体词是指可以独立存在的客体，可以是一个 具体的事物或抽象的概念，是原子命题所描述的对象。
17
例题
若P(x)是语句“x2>10”，论述域为不超过4的正整数， xP(x)和x P(x)的真值是什么？
解 由于论述域为{1，2，3，4}，命题xP(x)为 x P(x) P(1) P(2) P(3) P(4)
而P(1)即“12>10”为假，所以x P(x)为假。 命题xP(x)为
x P(x) P(1) P(2) P(3) P(4) 而P(4)即“42>10”为真，所以x P(x)为真。
11
例题

21
本课小结
US规则 UG规则 ES规则 EG规则
22
课后作业
P79 (1) 补充: 符号化下列命题并推证其结论。 所有的人或者是吃素的或者是吃荤的，吃素 的常吃豆制品，因而不吃豆制品的人是吃 荤的。（个体域为人的集合） 令 F(x)：x 是 吃 素 的 ， G(x)：x 是 吃 荤 的 ， H(x)：x吃豆制品。
15
六、例题
例：给定下面2个推理,找出错误. （1） 1．x (F(x) G(x)) P 2．F(y) G(y) US(1) 3．x F(x) P 4．F(y) ES(3) 5．G(y) T(2)(3) I 6．xG(x) UG(5) （2） 1．xy F(x, y) P 2．y F(z, y) US(1) 3．F(z, c) ES(2) 4．x F(x, c) UG 5．yx F(x, y) EG *在上面推理中（1）中从3到4有错，（2）中从2到3有错
6
三、全称推广规则
2．全称推广规则（简称UG规则）
P(x) ∴(x)P(x) P（y） xP(x)
上式成立，要求以下条件： （1）y在P（y）中自由出现，且y取任何值时P（y）均为真； （2）取代y的x不能在P（y）中约束出现，否则产生错误。
7
三、全称推广规则
例 在实数集中F（x，y）：x>y， 取P（y）= x F(x, y)对给定y都成立。 若应用上式时，以x取代y 得x(x(x>x))，这是假命题 *出错原因是违背了（2）。
第二章谓词逻辑
2-7 谓词演算的推理理论 授课人：李朔 Email:chn.nj.ls@
1
一、谓词演算推理规则
谓词演算的推理方法,可以看作是命题演算 推理方法的扩张。