当前位置：文档之家 › ch05一阶逻辑等值演算与推理 - 副本

ch05一阶逻辑等值演算与推理 - 副本

  • 格式：ppt
  • 大小：481.50 KB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

05 一阶逻辑等值演算与推理

05 一阶逻辑等值演算与推理

例
4
(3) C = xyL(x, y) (L(2, 2) L(2, 3)) (L(3, 2) L(3, 3)) (10) (01) 1.
例
4
(4) D = yxL(x, y) y(L(2, y)L(3, y)) (L(2, 2)L(3, 2)) (L(2, 3)L(3, 3)) (10) (01) 0. 一般地：y x L (x, y) x y L (x, y) 在实变函数上的应用举例
提 前 讲
证 只要证明在某个解释下两边的式子不等值.
(1)取解释 I: 个体域为 ; A(x) 为 x 是奇数; B(x) 为 x 是 偶数. 则 x(A(x) A(x)) 为真, 而 xA(x) xB(x) 为假.
(2)取解释 I 同(1), 则 x(A(x) B(x)) 为假, 而 xA(x) xB(x) 为真.
/quantifier elimination
3. 量词辖域收缩与扩张等值式
设 A(x) 含 x 的自由出现, 而 B 不含 x 的自由出现, 则
(1)
x(A(x)B) xA(x) B
x(A(x)B) xA(x) B x(A(x)B) xA(x) B x(BA(x)) B xA(x) (5.3)
/quantifier distribution
例 2
例2 证明 对 无分配律, 而 对 无分配律. (1) x(A(x)B(x)) xA(x) xB(x);
(2) x(A(x)B(x)) xA(x) xB(x),
其中 A(x), B(x) 含自由变元 x.
2、一阶逻辑中的基本等值式
第一组 代换实例 命题逻辑中的重言式的代换实例都是一阶逻辑中的 永真式, 因而命题逻辑中的等值式†给出的代换实例 都是一阶逻辑的等值式.

离散数学第二章一阶逻辑知识点总结

离散数学第二章一阶逻辑知识点总结

离散数学第二章一阶逻辑知识点总结数理逻辑部分第2章一阶逻辑2.1 一阶逻辑基本概念个体词（个体）: 所研究对象中能够独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示个体变项：抽象的事物，用x, y, z表示个体域: 个体变项的取值范围有限个体域，如{a, b, c}, {1, 2}无限个体域，如N, Z, R, …全总个体域: 宇宙间一切事物组成谓词: 表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词: 表示事物的性质多元谓词(n元谓词, n2): 表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：x y，…0元谓词: 别含个体变项的谓词, 即命题常项或命题变项量词: 表示数量的词全称量词: 表示任意的, 所有的, 一切的等如x 表示对个体域中所有的x存在量词: 表示存在, 有的, 至少有一具等如x表示在个体域中存在x一阶逻辑中命题符号化例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲在命题逻辑中, 设p:墨西哥位于南美洲符号化为p, 这是真命题在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2 在一阶逻辑中将下面命题符号化(1) 人都爱美; (2) 有人用左手写字分不取(a) D为人类集合, (b) D为全总个体域.解：(a) (1) 设G(x)：x爱美, 符号化为x G(x)(2) 设G(x)：x用左手写字, 符号化为x G(x)(b) 设F(x)：x为人，G(x)：同(a)中(1) x (F(x)G(x))(2) x (F(x)G(x))这是两个基本公式, 注意这两个基本公式的使用.例3 在一阶逻辑中将下面命题符号化(1) 正数都大于负数(2) 有的无理数大于有的有理数解注意: 题目中没给个体域, 一律用全总个体域(1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值(2) 令F(x): x是无理数, G(y): y是有理数,L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或x y(F(x)G(y)L(x,y)) 两者等值几点注意：1元谓词与多元谓词的区分无特殊要求，用全总个体域量词顺序普通别能随便颠倒否定式的使用考虑：①没有别呼吸的人②别是所有的人都喜爱吃糖③别是所有的火车都比所有的汽车快以上命题应怎么符号化？2.2 一阶逻辑合式公式及解释字母表定义字母表包含下述符号：(1) 个体常项：a, b, c, …, a i, b i, c i, …, i1(2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1(3) 函数符号：f, g, h, …, f i, g i, h i, …, i1(4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1(5) 量词符号：,(6) 联结词符号：, , , ,(7) 括号与逗号：(, ), ，定义项的定义如下：(1) 个体常项和个体变项是项.(2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n是任意的n个项，则(t1, t2, …, t n) 是项.(3) 所有的项基本上有限次使用(1), (2) 得到的.个体常项、变项是项，由它们构成的n元函数和复合函数依然项定义设R(x1, x2, …, x n)是任意的n元谓词，t1,t2,…, t n 是任意的n个项，则称R(t1, t2, …, t n)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y), F(f(x1,x2),g(x3,x4))等均为原子公式定义合式公式（简称公式）定义如下：(1) 原子公式是合式公式.(2) 若A是合式公式，则(A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B),(A B)也是合式公式(4) 若A是合式公式，则xA, xA也是合式公式(5) 惟独有限次地应用(1)~(4)形成的符号串是合式公式.请举出几个合式公式的例子.定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域. 在x和x的辖域中，x的所有浮现都称为约束浮现，A中别是约束浮现的其他变项均称为是自由浮现的.例如, 在公式x(F(x,y)G(x,z)) 中,A=(F(x,y)G(x,z))为x的辖域，x为指导变元, A中x的两次浮现均为约束浮现，y与z均为自由浮现.闭式: 别含自由浮现的个体变项的公式.给定公式A=x(F(x)G(x))成真解释: 个体域N, F(x): x>2, G(x): x>1代入得A=x(x>2x>1) 真命题成假解释: 个体域N, F(x): x>1, G(x): x>2 代入得A=x(x>1x>2) 假命题咨询: xF(x)x F(x) 有成真解释吗？xF(x)x F(x) 有成假解释吗？被解释的公式别一定全部包含解释中的4部分.闭式在任何解释下基本上命题，注意别是闭式的公式在某些解释下也也许是命题.永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满脚式：至少有一具成真赋值几点讲明：永真式为可满脚式，但反之别真谓词公式的可满脚性（永真性,永假性)是别可判定的利用代换实例可判某些公式的类型定义设A0是含命题变项p1, p2, …,p n的命题公式，A1,A2,…,A n是n个谓词公式，用A i处处代替A0中的p i (1i n)，所得公式A称为A0的代换实例.例如:F(x)G(x), xF(x)yG(y) 等基本上p q的换实例，x(F(x)G(x)) 等别是p q 的代换实例.定理重言式的代换实例基本上永真式，矛盾式的代换实例基本上矛盾式.2.3 一阶逻辑等值式等值式定义若A B为逻辑有效式，则称A与B是等值的，记作A B，并称A B 为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y) xF(x)yG(y)(xF(x)yG(y)) xF(x)yG(y) 等消去量词等值式设D={a1,a2,…,a n} xA(x)A(a1)A(a2)…A(a n)xA(x)A(a1)A(a2)…A(a n)量词否定等值式设A(x)是含x自由浮现的公式xA(x)x A(x)xA(x)x A(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律例将下面命题用两种形式符号化(1) 没有别犯错误的人(2) 别是所有的人都爱看电影解(1) 令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x))x(F(x)G(x))请给出演算过程，并讲明理由.(2) 令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x))x(F(x)G(x))给出演算过程，并讲明理由.前束范式定义设A为一具一阶逻辑公式, 若A具有如下形式Q1x1Q2x2…Q k x k B, 则称A为前束范式, 其中Q i(1i k)为或，B为别含量词的公式.例如，x y(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式, 而x(F(x)y(G(y)H(x,y)))x(F(x)G(x))别是前束范式.定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式别惟一求公式的前束范式的办法: 利用重要等值式、置换规则、换名规则、代替规则举行等值演算.换名规则: 将量词辖域中浮现的某个约束浮现的个体变项及对应的指导变项，改成其他辖域中未曾浮现过的个体变项符号，公式中其余部分别变，则所得公式与原来的公式等值.代替规则: 对某自由浮现的个体变项用与原公式中所有个体变项符号别同的符号去代替，则所得公式与原来的公式等值.例求下列公式的前束范式(1) x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x)) （量词否定等值式）x(M(x)F(x))两步结果基本上前束范式，讲明前束范式别惟一.(2) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x) （量词否定等值式）x(F(x)G(x)) （量词分配等值式）另有一种形式xF(x)xG(x)xF(x)x G(x)xF(x)y G(y) ( 换名规则) x y(F(x)G(y)) ( 量词辖域扩张) 两种形式是等值的(3) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)) （为啥？）或x y(F(x)G(y)) （为啥？）(4) xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y)) （换名规则）z y(F(z)(G(x,y)H(y))) （为啥？）或xF(x)y(G(z,y)H(y)) （代替规则）x y(F(x)(G(z,y)H(y)))(5) x(F(x,y)y(G(x,y)H(x,z)))解用换名规则, 也可用代替规则, 这个地方用代替规则 x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))x y(F(x,u)G(x,y)H(x,z)))注意：x与y别能颠倒。

第五章+一阶逻辑等值演算与推理3

第五章+一阶逻辑等值演算与推理3

15
第五章 一阶逻辑等值演算与推理
练习:在自然推理系统F中，构造下列推理的证明。
前提：∀x(F(x) ∨ G(x))， ⎤ ∃x G(x). 结论： ∃x F(x) . 证明：① ⎤ ∃x G(x) 前提引入 ② ∀x ⎤ G(x) ① 置换规则 ③ ⎤ G(a) ②UI ④ ∀x(F(x) ∨ G(x)) 前提引入 ⑤ F(a) ∨ G(a) ④UI ⑥ F(a) ③ ⑤析取三段论 ⑦ ∃x F(x) ⑥EG
3
第五章 一阶逻辑等值演算与推理
(2) 由基本等值式生成的推理定律。例如： ∀x F(x) => ⎤ ⎤ ∀x F(x) ⎤ ⎤ ∀x F(x) => ∀x F(x) ⎤ ∀x A(x) => ∃x ⎤ A(x)
∃x ⎤ A(x) => ⎤ ∀x A(x) ……
4
第五章 一阶逻辑等值演算与推理
(3) ∀x A(x)∨∀x B(x)=> ∀x (A(x)∨ B(x))① ③引入的顺序不可更改！
13
第五章 一阶逻辑等值演算与推理
练习：试指出下面证明中的错误。
证明： ① ∀x (A(x)→B(x))
前提引入
① UI ② A(y)→B(y) 前提引入 ③ ∃x A(x) ④ A(y) ③EI ⑤ B(y) ②④假言推理 ⑥ ∀xB(x) ⑤UG 对∃x A(x)消去量词时，要求用特定的个体常项取代 x，而不能用变项y取代x，所以③到④有错。
证明：只要说明∃x A(x)→∃x B(x)为1时， ∃ x(A(x)→B(x))不为0即可。 （1）若有x使得A(x)为0，则∃ x(A(x)→B(x))为 1。 （2）若所有的x都使得A(x)为1，由∃x A(x)→∃x B(x为1得∃x B(x)为1，即有一个c使得B(c)为 1。因此A(c)→B(c)为1， ∃ x(A(x)→B(x))为 1。

第二章一阶逻辑

第二章一阶逻辑
本命题符号化为 ┐ x(W(x)→B(x))。
练习2 在一阶逻辑中将下列命题符号化。 ⑴ 兔子比乌龟跑得快。 ⑵ 每个人都有自己喜欢的职业。 ⑶ 不存在同样高的两个人。 ⑷ 存在最小的自然数。 解 ⑴兔子比乌龟跑得快。 令F(x)：x是兔子， G(x)：x是乌龟， H(x,y)：x比y跑得快。 本命题符号化为 x(F(x)→ y(G(y)→H(x,y)))， 或 x y(F(x)∧G(y)→H(x,y))。
⑷ 存在着偶素数。
⑸ 在北京工作的人未必都是北京人。
解 ⑴有的有理数是整数。
令Q(x)：x是有理数。 P(x)：x是整数。 本命题符号化为 x (Q(x)∧P(x))。
⑵每个计算机系的学生都学离散数学。
令P(x)：x是计算机系的学生。
R(x)：x学离散数学。
本命题符号化为x (P(x)→R(x))。
⑶ 每个人都会犯错误。
令 R(x)：x是人。 P(x)：x会犯错误。 本命题符号化为 x (R(x)→P(x))。
⑷ 存在着偶素数。
令E(x)：x是偶数。
P(x)：x是素数。
本命题符号化为 x(E(x)∧P(x))。
⑸在北京工作的人未必都是北京人。
令W(x)：x在北京工作。
B(x)：x是北京人。
母a, b, c, d 等表示常元。
个体变项（也称个体变元，简称变元）：泛指
个体域中个体的符号。一般用小写英文字母x, y,
z 等表示变元。
例
2是有理数。 这是一个简单命题。 “2”是个体词 “…是有理数”是谓词，它表示个体的性 质。 个体词：是表示个体的符号。 谓词：用来刻画个体的性质或个体之间的关 系。一般用大写英文字母表示谓词。 例 张三比李四高。 有两个个体词：张三，李四 “…比…高”是谓词，表示两个体之间的关 系。

一阶逻辑公式及解释

一阶逻辑公式及解释
(6)联结词符号: ┐，∧，∨，→，
(7)括号和逗号:（） ，
.
2
定义4.2（项）
项的递归定义如下： （1）个体常项和个体变项是项。 （2）如果(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任
意的n个项，则(t1,t2,…,tn)仍然是项。 （3）只有有限次使用(1)，(2)生成的符号串才是项。
.
15
定义4.8（一阶公式的分类）
设A为一公式，若A在任何解释下均为真，则称A 是永真式（或称逻辑有效式）。若A在任何解释下均 为假，则称A是矛盾式（或永假式）。若至少存在一 个解释使A为真，则称A是可满足式。
说明：（1）永真式是可满足式，反之不然。
（2）由于公式的复杂性和解释的多样性，到 目前为止，还没有一个可行的算法判断某一公式 是否是可满足的。
（3）但可以利用代换实例的相关性质来判断 某些特殊的公式。而对于一般的公式只能通过构 造解释的方法来判断。
.
16
定义4.9（代换实例） 设A0是含命题变项p1，p2，…，pn的命题公式，
A1，A2，…，An是n个谓词公式，用Ai（1≤i≤n）处处 代替A0中的pi ，所得公式A称为A0的代换实例。
词公式
简单起见，谓词公式简称为公式。
.
5
定义4.5（量词的辖域） 在公式xA和xA中，称x是指导变元，A为
相应量词的辖域。 在x和x的辖域中，x的所有出现都称为约束
出现 A中不是约束出现的变项均称为是自由出现的
说明：量词的辖域以量词后第一个括号的范围为准
.
6
例4.6 指出下列公式中的指导变元，各量词的 辖域，自由出现以及约束出现的个体变项：
（1）x（ F（x，y）→G（x，z）） （2） x（ F（x）→G（y））→

离散数学 第四章 一阶逻辑基本概念

离散数学 第四章 一阶逻辑基本概念

18
§4.1 一阶逻辑命题符号化
（3）没有人登上过木星。 令H(x):x登上过木星， M(x):x是人。命题符号化为 ┐x(M(x)∧H(x))。 命题真值为真。 （4）在美国留学的学生未必都是亚洲人。 令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化 ┐x(F(x)→G(x)) 命题真值为真。
个体词、谓词和量词，以期达到表达出个体与总体的内在 联系和数量关系。
4
§4.1 一阶逻辑命题符号化
一阶逻辑命题符号化的三个基本要素


个体词
谓词
量词
5
个体词及相关概念
个体词：指所研究对象中可以独立存在的具体的 或抽象的客体。
举例

命题：电子计算机是科学技术的工具。 个体词：电子计算机。 命题：他是三好学生。 个体词：他。
个体域为全总个体域
令 M(x):x是人 , F(x):x呼吸 , G(x):x用左手写字

能否将”凡人都呼吸”符号化为 (∀x) (M(x)∧F(x) ) ？ 不可以。 (∀x) (M(x)∧F(x) )表示宇宙中的万物都是人并 且会呼吸 能否将”有的人用左手写字”符号化为 (x)( M(x)→G(x) ) ？ 不可以。(x)( M(x)→G(x) ) 表示在宇宙万物中存在某个 个体x,”如果x是人则x会用左手写字”

6
个体词及相关概念
个体常项：表示具体或特定的客体的个体词，用小写字母 a, b, c,…表示。 个体变项：表示抽象或泛指的客体的个体词，用x, y, z,… 表示。 个体域（或称论域）：指个体变项的取值范围。 可以是有穷集合，如{a, b, c}, {1, 2}。 可以是无穷集合，如N，Z，R，…。 全总个体域（universe）——宇宙间一切事物组成 。

一阶逻辑等值式与置换规则

1置换规则设a是含公式a的公式b是用公式b置换了a中所有的a后得到的公式若ab则a2换名规则设a为一公式将a中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号公式中其余部分不变设所得3代替规则设a为一公式将a中某个自由出现的个体变项的所有出现用a中未曾出现过的个体变项符号代替公式中其余部分不变设所得公式为a则aa
4
4、量词分配等值式 对于任意的公式A（x）和B（x）： （1）x（A（x）∧B（x））xA（x）∧x B（x） （2）x（A（x）∨B（x）） xA（x）∨x B（x）
说明：量词分配等值式中，只有对∧的分配和对∨ 的分配的等值式。而对∨和任意的公式A（x，y）
10
解： （1）x（F（x）∧G（x，a）） （F（2）∧G（2，a））∧（F（3）∧G（3，a）） （F（2）∧G（2，2））∧（F（3）∧G（3，2）） （0∧1）∧（1∧1） 0 （2）x（F（f（x））∧G（x，f（x））） （F（f（2））∧G（2，f（2）））∨
（F（f（3））∧G（3，f（3））） （F（3）∧G（2，3））∨（F（2）∧G（3，2）） （1∧1）∨（0∧1） 1
L（x，y）为：L（2，2）= L（3，3）=1， L（2，3）= L（3，2）=0。
F（x）为：F（2）=0，F（3）=1。 在I下求下列各式的真值。 （1）x（ F（x）∧ G（x，a）） （2）x（ F（f（x））∧ G（x，f（x））） （3）x y L（x，y） （4）y x L（x，y）
x F（x）→y G（y） x (F（x）→y G（y）) xy (F（x）→G（y）) 方法二： yx(F（y）→G（x）) 方法三：
┐x F（x）∨ x G（x） x┐F（x）∨ x G（x） x┐F（x）∨ y G（y） xy(┐F（x）∨ G（y）) xy (F（x）→G（y）)

离散数学一阶逻辑等值演算

推理系统通常由一组公理和推理规则组成，公理是 不需要证明的基本命题，而推理规则则指导如何从 已知命题推导出新命题。
在一阶逻辑中，推理系统还包括量词和谓词，量词 用于描述个体的数量，谓词则用于描述个体的性质 。
推理系统的构造
构造推理系统需要确定系统的 公理和推理规则。
公理的选择应确保系统的一致 性和完备性，即从公理推导出 的结论不与已知事实相矛盾， 并且所有需要的结论都能从公 理推导出来。
离散数学一阶逻辑等值演算的展望
形式化方法的普及和应用
随着计算机科学的不断发展，离散数学一阶逻辑等值演算的形式化方法将更加普及和应 用，成为解决复杂问题的关键工具之一。
人工智能与离散数学的深度融合
未来的人工智能系统将更加依赖于离散数学一阶逻辑等值演算的形式化方法，以实现更 加智能化的推理和决策。
新兴领域的应用拓展
离散数学一阶逻辑等值演算
目
CONTENCT
录
• 离散数学概述 • 一阶逻辑基础 • 等值演算 • 推理系统 • 应用实例 • 离散数学一阶逻辑等值演算的发展
趋势与展望
01
离散数学概述
定义与特点
定义
离散数学是研究离散对象（如集合、图、树、逻辑等）的数学分 支的总称。
特点
离散数学主要关注离散对象的结构、性质和关系，通常不涉及连 续的量或函数。
离散概率论是研究离散随机事件的数学分支，例如扔骰子、抽签等。一阶逻辑等值演算在离散概率论 中也有着重要的应用。
利用一阶逻辑等值演算，可以描述随机事件之间的关系和性质，例如计算事件的概率、推导事件的独 立性等。这些描述方法有助于深入理解随机事件和概率分布，为解决实际问题提供有力支持。
06
离散数学一阶逻辑等值演算的发展趋势与展望

离散数学 第二章：一阶逻辑

(1) xF(x) yH(x, y);
(2) xF(x) G(x, y);
(3) xyR(x, y) L(y, z) xH(x, y).
2.闭式
定义6. 设A为任一公式,若A中无自由出现的个体变项,则称A是 封闭的合式公式,简记闭式.
例: xF(x) G(x),xyF(x) G(x, y) 闭式, 但 xF(x) G(x, y),zyL(x, y, z) 不是闭式.
(1)所有的人都要死的. (2)有的人活百岁以上.
全称量词:一切,所有,任意. 用 表示.
1.量词
x：表示对个体域中的所有个
xF(x)体：表. 示个体域中的所有个体都具有性质F.
存在量词:存在着,有一个,至少有一个. 用 表示.
x：表示存在个体域里的个体.
xF ( x)：表示存在着个体域中的个体具有性质F.
（2）xR(x) G(x), 其中 G(x): x是整数.
3) 同2).
例3. 将下面命题符号化. (1)对所有的x ,均有 x2-1=(x+1)(x-1). (2)存在x,使得 x+5=2.
要求: 1)个体域为自然数集合. 2)个体域为实数集合.
解：1) 不用引入特性谓词.
（1）xF(x), 其中 F(x): x2-1=(x+1)(x-1). 真命题
（3） xF(x) yF(y) L(x, y),
其中 F(x): x是自然数, L(x,y): y是 x的先驱数.
§2.2 一阶逻辑合式公式及解释
一、合式公式
1.字母表 定义1.字母表如下: (1)个体常项: a,b,c,… (2)个体变项: x,y,z,… (3)函数符号: f,g,h,… (4)谓词符号: F,G,H,…

一阶逻辑等值式


例
（1） ┐x(M(x)∧F(x)) x(M(x)→┐F(x)) ┐x(M(x)∧F(x)) x┐(M(x)∧F(x)) x(┐M(x)∨┐F(x))
x(M(x)→┐F(x))
（2） ┐x(F(x)→G(x)) x(F(x)∧┐G(x)) ┐x(F(x)→G(x)) x┐(F(x)→G(x)) x┐(┐F(x)∨G(x))
说 明
我们称(1)和(2)是等值的。
等值式的定义
定义5.1 设A，B是一阶逻辑中任意两个公式，若 AB是永 真式，则称A与B是等值的。 记做AB，称 AB 是等值式。
例如： x(F(x) G(x)) x(F(x) G(x))
说 明
判断公式A与B是否等值，等价于判断公式 AB是否为永真式，即在任何解释下都是真的。 谓词逻辑中关于联结词的等值式与命题逻辑中相关 等值式类似。
由(1)式推导(2)式 x(A(x)∧B(x)) xA(x)∧xB(x) x(┐A(x)∧┐B(x)) x┐A(x)∧x┐B(x)
┐x(A(x)∨B(x)) ┐(xA(x)∨xB(x))
例 证明 （1） x(A(x)∨B(x)) <≠> xA(x)∨xB(x) （2） x(A(x)∧B(x)) <≠> xA(x)∧xB(x) 其中A(x)，B(x)为含x自由出现的公式。
┐x(F(x)→G(y))∨zH(z)
（蕴涵等值式）
消去量词等值式
设个体域为有限集D={a1,a2,…,an},则有 （1）xA(x) A(a1)∧A(a2)∧…∧A(an) （2）xA(x) A(a1)∨A(a2)∨…∨A(an) （5.1）
Байду номын сангаас
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2011-4-6
计算机科学与技术系
11
第五章 一阶逻辑等值演算与推理
例5.2：证明： ：证明：
(1) ∀x(A(x)∨B(x)) <≠> ∀x A(x)∨ ∀x B(x) (2) ∃ x(A(x)∧B(x)) <≠> ∃x A(x)∧ ∃x B(x) 其中，A(x)、B(x)为含 自由出现的公式。 为含x 其中，A(x)、B(x)为含x自由出现的公式。 只需证明∀x(A(x)∨B(x))↔∀ ↔∀x B(x)不 证:（1）只需证明∀x(A(x)∨B(x))↔∀x A(x)∨ ∀x B(x)不 是永真式。 是永真式。 设个体域为人集合，A(x): 是男人。 B(x): 是女人。 设个体域为人集合，A(x):x是男人。 B(x):x是女人。 x(A(x)∧B(x))↔ B(x)不是 （2）只需证明 ∃x(A(x)∧B(x))↔ ∃x A(x)∧ ∃x B(x)不是 永真式。 永真式。 设个体域为全总个体域， A(x): 是人。 B(x): 有尾巴。 设个体域为全总个体域 ， A(x):x 是人 。 B(x):x 有尾巴 。 此例说明， 此例说明，“∀”对“∨”无分配律，“∃”对“∧”无分配律 无分配律，
2011-4-6
计算机科学与技术系
4
第五章 一阶逻辑等值演算与推理
第二组： 第二组： 1、消去量词等值式 、 设个体域为有限集D={a1，a2，… ，an}，则 设个体域为有限集 ， (1) ∀x A(x) A(a1)∧A(a2)∧… ∧A(an) A(a )∧A(a )∧… ∧A(a (2) ∃x A(x) A( 1)∨A( 2)∨ ∨ A( n) A(a )∨A(a )∨… A(a 2、量词否定等值式 、 A(x)是任意的含自由出现个体变项 的公式， 是任意的含自由出现个体变项x的公式 设A(x)是任意的含自由出现个体变项 的公式，则 (1) ∀x A(x) ∃x A(x) (2) ∃x A(x) ∀x A(x)
在一阶逻辑中， 在一阶逻辑中，有些命题可以有不同的符号 化形式。 化形式。如： 没有不能表示为分数的有理数。 没有不能表示为分数的有理数。
是有理数。 能表示成分数。 令 H(x): x是有理数。W(x):x能表示成分数。 则： 是有理数 能表示成分数 （1）∀x (H(x) → W(x)) （2） ∃x(H(x)∧ W(x)) 均正确。 均正确。 同命题逻辑一样，我们称（1）、（2）是等值的。 同命题逻辑一样，我们称（ 是等值的。
14
第五章 一阶逻辑等值演算与推理
如下： 例5.4：给定解释 如下： ：给定解释I如下 (a)个体域 个体域D={2,3} 个体域 (b)D中特定元素 中特定元素a=2 中特定元素 (c) D上特定函数 上特定函数f(x):f(2)=3,f(3)=2 上特定函数 (d) D上特定谓词 上特定谓词G(x,y):G(2,2)= G(2,3)= G(3,2)=1,G(3,3)=0. 上特定谓词 L(x,y):L(2 L(3 )=1 L(2 L(3 )=0 L(x,y):L(2,2)= L(3,3)=1, L(2,3)= L(3,2)=0. F(x):F(2)=0,F(3)=1 F(x):F(2)=0,F(3)=1. 下求下列各式的真值。 在I下求下列各式的真值。 (1)∀x(F(x) ∧ G(x,a)) (3)∀x∃y L(x,y)
2011-4-6
(2)∃ x(F(f(x))∧G(x,f(x))) F(f(x)) (4)∃y∀x L(x,y)
计算机科学与技术系 15
第五章 一阶逻辑等值演算与推理
解: (1) (2) (F(2 G(2 (F(3 G(3 (F(2)∧G(2,2))∧(F(3)∧G(3,2)) (0∧1)∧(1∧1)
2011-4-6 计算机科学与技术系 12
第五章 一阶逻辑等值演算与推理
将下列各公式的量词去掉。 例5.3：设个体域为 ：设个体域为D={a,b,c},将下列各公式的量词去掉。 将下列各公式的量词去掉 (1) ∀x(F(x)→G(x)) (2) ∀x(F(x)∨∃y G(y)) x(F(x)∨∃ (3) ∃ x∀y F(x,y) ∀ 解: (1) (2) (F(a)→G(a)) ∧(F(b)→G(b))∧(F(c)→G(c)) 公式5 公式5.3 F(x)∨∃ ∀x F(x)∨∃y G(y)
∀x(A(x)→B) x(A(x)→
∀x(B→ A(x))
2011-4-6
∃ x A(x) → B
B → ∀ x A(x)
计算机科学与技术系 6
第五章 一阶逻辑等值演算与推理
3、量词辖域收缩与扩张等值式 、 A(x)是任意的含自由出现个体变项 的公式， 中 是任意的含自由出现个体变项x的公式 设 A(x) 是任意的含自由出现个体变项 的公式 ， B中 不含x的出现 的出现， 不含 的出现，则 (2) ∃ x(A(x)∨B) ∃ x A(x)∨B ∃ x(A(x)∧B) ∃ x A(x)∧B
2011-4-6 计算机科学与技术系 8
第五章 一阶逻辑等值演算与推理
2、换名规则 是一公式， 中某个辖域中约束变项 约束变项的所有出 设 A 是一公式 ， 将 A 中某个辖域中 约束变项 的所有出 现及相应的指导变元，改成该量词辖域中未曾出 现及相应的指导变元，改成该量词辖域中未曾出 的某个个体变项符号，公式中其它部分不变， 现的某个个体变项符号，公式中其它部分不变， 设所得公式为A`, A`,则 A`。 设所得公式为A`,则 A A`。 3、代替规则 是一公式， 中某个自由出现 自由出现的个体变项所有 设 A 是一公式 ， 将 A 中某个 自由出现 的个体变项所有 出现用A 未曾出现的个体变项符号代替 的个体变项符号代替， 出现用A中未曾出现的个体变项符号代替，A中其 它部分不变，设所得公式为A`, A`,则 A`。 它部分不变，设所得公式为A`,则 A A`。
2011-4-6 计算机科学与技术系 13
第五章 一阶逻辑等值演算与推理
设个体域为D={a,b,c},将下列各公式的量词去掉。 练习：设个体域为 将下列各公式的量词去掉 (1) ∀x ∀y(F(x) ∨ G(y)) (2) ∀x(F(x,y) → ∃y G(y))
2011-4-6
计算机科学与技术系
0
F(f(2 G(2,f(2 F(f(3 G(3,f(3 ( F(f(2))∧G(2,f(2)))∨ ( F(f(3))∧G(3,f(3))) F(3 G(2 F(2 G(3 ( F(3)∧G(2,3))∨ ( F(2)∧G(3,2)) (1∧1)∧(0∧1)
1 L(2 )∨L(2 L(3 )∨L(3 (3) ( L(2,2)∨L(2,3))∧ ( L(3,2)∨L(3,3)) (1∨0)∧(0∨1) 1 (4) ∃y( L(2,y) ∧ L(3,y) ) L(2 L(3 L(2 L(3 L(2 L(3 ( L(2,2)∧L(3,2))∨(( L(2,3) ∧ L(3,3)) )∨(0 (1∧0)∨(0∧1) 0
(F(a)∧F(b)∧F(c))∨(G(a)∨ G(b)∨ G(c)) (3) ∃ x( F(x,a)∧F(x,b)∧F(x,c)) (F(a,a)∧F(a,b)∧F(a,c))∨ F(a,a) (F(b,a)∧F(b,b)∧F(b,c))∨ F(b,a) (F(c,a)∧F(c,b)∧F(c,c)) F(c,a)
2011-4-6
计算机科学与技术系
3
第五章 一阶逻辑等值演算与推理
定义ห้องสมุดไป่ตู้.1 定义
是一阶逻辑中任意两个公式， 为重言式， 设A，B是一阶逻辑中任意两个公式， ， 是一阶逻辑中任意两个公式 若A ↔ B为重言式， 为重言式 则称A与 是等值的 记作A 是等值的， B。 称A B是等值式。 是等值式。 则称 与B是等值的，记作 。 是等值式 已经得证的重要等值式： 已经得证的重要等值式： 第一组： 等值式给出的代换实例， 第一组：由P21-22等值式给出的代换实例，如： (1) ∀x F(x) ∀x F(x) (2) ∀x ∃y(F(x,y)→G(x,y)) ∀x ∃y(F(x,y)→G(x,y)) (3) F(x)→G(y) F(x) ∨ G(y) (4) ∀ x(F(x)→G(y))→∃z L(z) ∀ x(F(x)→G(y))∨∃z L(z) F(x) G(y))∨∃ F(x)
(1) ∀x ∃y F(x,y) (2) ∃y∀x F(x,y) (3) ∀x ∀y( F(x,y) →F(f(x),f(y)))
2011-4-6 计算机科学与技术系 5
第五章 一阶逻辑等值演算与推理
3、量词辖域收缩与扩张等值式 、 A(x)是任意的含自由出现个体变项x的公式 是任意的含自由出现个体变项 的公式， 设A(x)是任意的含自由出现个体变项 的公式， B中不含 的出现，则: 中不含x的出现 中不含 的出现， (1) ∀x(A(x)∨B) ∀x(A(x)∧B) ∀x A(x)∨B ∀x A(x)∧B
2011-4-6 计算机科学与技术系
(换名规则) 换名规则) 换名规则) (换名规则)
(代替规则) 代替规则) 代替规则) (代替规则)
10
第五章 一阶逻辑等值演算与推理
练习：将下列公式等值化， 练习：将下列公式等值化，使其不含既是约束出现
又是自由出现的个体变项。 又是自由出现的个体变项。
∀x∃y(F(x,y)∧G(y,z))∨ ∃x H(x,y,z)
2011-4-6 计算机科学与技术系 16
第五章 一阶逻辑等值演算与推理 练习：给定解释I如下 如下： 练习：给定解释 如下：
(a)个体域 个体域D={3,4} 个体域 (b) D上特定函数 上特定函数f(x):f(3)=4,f(4)=3 上特定函数 (c)D上特定谓词 上特定谓词F(x,y):F(3,3)= F(4,4)=0, F(3,4)=F(4,3)=1. 上特定谓词 下求下列各式的真值。 在I下求下列各式的真值。