《离散数学》第二章 一阶逻辑 讲稿文档格式.docx

1、 考虑L（2,3）和L（3,2） L（x1, x2, xn）是命题：只有当L是常项， x1, x2, xn是个体常项0元谓词: 不含个体变项的谓词, 如L（a, b） 如L的意义明确，则0元谓词都是命题一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化 （1） 墨西哥位于南美洲 在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F（x）：x位于南美洲 符号化为F（a）例1（续） （2） 是无理数仅当 是有理数 在命题逻辑中, 设 p： 是无理数，q： 是有理数. 符号化为 p q, 这

2、是假命题 在一阶逻辑中, 设F（x）: x是无理数, G（x）: x是有理 数符号化为 （3） 如果23，则33，q：3y，G（x,y）：xy x（F（x）y（G（y）L（x,y） 或 xy（F（x）G（y）L（x,y） 两者等值 （2） 令F（x）: x是无理数, G（y）: y是有理数, L（x,y）：y x（F（x）y（G（y）L（x,y） 或 xy（F（x）G（y）L（x,y） 两者等值几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不要随便颠倒 例：对任意x，存在着y，使得x+y=5. 个体域为实数集. 符号化为： x y H（x,y）, 其中H（x,y）

3、:x+y=5 考虑 y x H（x,y） 否定式的使用例：在一界逻辑中命题符号化 没有不呼吸的人 不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快 x（ F（x） G（x） 其中F（x）：x是人， G（x）：x呼吸 或者： x（ F（x） G（x） x（ F（x） G（x）x喜欢吃糖 x（ F（x） G（x） x（ F（x） y （G（y） H（x,y） ） x（ F（x） y （G（y） H（x,y） ） 一切人都不一样高 每个自然数都有后继数 有的自然数无先驱数 x y（ F（x） F（y） G（x,y） H（x,y） x是人， G（x,y） :x和y不是同一个人， H（x,y）：

4、x和y一样高 x y（ F（x） F（y） G（x,y） H（x,y） x（ F（x） y（G（y） H（x,y）x是自然数， H（x,y） ：y是x的后继数 x（ F（x） L（x） ， L（x） ：x有后继数 x（ F（x） y（G（y） H（x,y） x（ F（x） L（x） ） ，L（x） ：x有先驱数2.2 一阶逻辑公式及解释字母表合式公式（简称公式）个体变项的自由出现和约束出现解释永真式（逻辑有效式）矛盾式（永假式）可满足式 字母表 定义 字母表包含下述符号： （1） 个体常项：a, b, c, , ai, bi, ci, , i 1 （2） 个体变项：x, y, z, , xi,

5、 yi, zi, , i 1 （3） 函数符号：f, g, h, , fi, gi, hi, , i 1 （4） 谓词符号：F, G, H, , Fi, Gi, Hi, , i 1 （5） 量词符号：, （6） 联结词符号：, , , , （7） 括号与逗号：（ , ）, ， 项 定义 项的定义如下： （1） 个体常项和个体变项是项. （2） 若（x1, x2, , xn）是任意的n元函数，t1,t2,tn是任意的n个项，则（t1, t2, , tn） 是项. （3） 所有的项都是有限次使用 （1）, （2） 得到的.a，b，x，y，f（x,y）=x+y， g（x,y）=x-y都是项 f（a,

6、 g（x,y）=a+ （x-y）是项其实, 个体常项、变项是项，由它们构成的n元函数和复合函数还是项原子公式 定义 设R（x1, x2, , xn）是任意的n元谓词，t1,t2, tn是任意的n个项，则称R（t1, t2, , tn）是原子公式. 其实，原子公式是由项组成的n元谓词. 例如，F（x,y）, F（f（x1,x2）,g（x3,x4）等均为原子公式 合式公式 定义 合式公式（简称公式）定义如下： （1） 原子公式是合式公式. （2） 若A是合式公式，则 （A）也是合式公式 （3） 若A, B是合式公式，则（AB）, （AB）, （AB）, （AB）也是合式公式 （4） 若A是合式公式

7、，则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均为自由出现. 闭式: 不含自由出现的个体变项的公式.例1：x（F（x） y H（x,y） ） y H（x,y）中， y 为指导变项， 的辖域为H（x,y），

8、其中y 为约束出现的， x为自由出现的.在整个合式公式中， x为指导变项， 的辖域为（F（x） y H（x,y） ），其中x与y 都是约束出现的， x约束出现2次， y约束出现1次.例2：x y（R（x,y） L（y,z） ） x H（x,y） x y（R（x,y） L（y,z） ）中， x,y都是指导变项，辖域为（R（x,y） L（y,z） ）， x与y 都是约束出现的， z为自由出现的. x H（x,y）中， x 为指导变项， 的辖域为H（x,y），其中x 为约束出现的， y为自由出现的在此公式中， x 为约束出现的，y为约束出现的，又为自由出现的. z为自由出现的.换名规则 将量词辖域中

9、出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部分不变。xF（x） G（x,y） 换名规则：zF（z） G（x,y）代替规则 将某个自由出现的个体变项及对应的指导变项，改成公式中未出现过的个体变项符号，处处代替。 代替规则：xF（x） G（z,y）用处：不存在既是约束出现，又是自由出现的个体变项公式的解释与分类 给定公式 A=x（F（x）G（x）成真解释: 个体域N, F（x）:2, G（x）:1 代入得A=x（x2x1） 真命题成假解释:1, G（x）:21x2） 假命题问: xF（x）xF（x） 有成真解释吗？ xF（x）xF（x） 有成

10、假解释吗？解释 定义 解释I由下面4部分组成： （a）非空个体域DI （b）DI中一些特定元素 （c）DI上特定函数集合 （d）DI上特定谓词的集合 说明：1 将公式的个体常项用I的特定常项代替，函数和谓词用I的特定函数和 谓词代替2 被解释的公式不一定全部包含解释中的4部分. 3 闭式在任何解释下都是命题，4 不是闭式的公式在某些解释下也可能是命题.例 给定解释I：DI2,3DI中特定元素a=2DI上特定函数f（x） :f（2）=3, f（3）=2 （d） DI上特定谓词F（x） :F（2）=0, F（3）=1， G（x,y）为G（i,j）=1, 其中i,j=2,3 1） x（F（x） G（

11、x,a） （F（2） G（2,2） （F（3） G（3,2） （01） （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 真命题例 给定解释：个体域为自然数集合DNDN中特定元素a=0DN上特定函数f（x,y）= x+y , g（x,y）= x.y （d） DN上特定谓词F（x,y） 为xy 1） xF（g（x,a）, x） xF（x.0 , x） x（x.0= x） 假命题2） x y

12、（ F（f（x,a）,y） F（f（y,a）,x） ） x y（ F（0+x,y） F（y+0,x） ） x y （ （0+x=y） （y+0=x） ） 真命题 3） x y F（f（x,y）, g（x,y） x y F（x+y, x.y） x y （x+y= x.y）假命题 4） F（f（x,y）, f（y,z） F（x+y, y+z） x+y= y+z 不是命题例1 给定解释I 如下: （a） 个体域 D=N （b） （c） （d） 谓词说明下列公式在 I 下的涵义,并讨论真值 公式的分类 永真式（逻辑有效式）：公式在任何解释下都是真的，即无成假赋值矛盾式（永假式）：公式在任何解释下都是假

13、的，即无成真赋值可满足式：至少存在一个解释使公式成真永真式为可满足式，但反之不真某些代换实例可判公式类型 代换实例 定义 设A0是含命题变项p1, p2, ,pn的命题公式， A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi （1in） ，所得公式A称为A0的代换实例. 例如: F（x）G（x）, xF（x）yG（y） 等都是pq的换实例， x（F（x）G（x） 等不是 pq 的代换实例. 定理 命题公式中的重言式的代换实例，在谓词公 式中都是永真式， 命题公式中的矛盾式的代换实例，在谓词公 式中都是矛盾式. 代换实例（续）例2 判断下面公式的类型 （1） xF（x） x F（x）

14、解：设任意解释Ia）如果存在a 使得F（a ） 为假，则xF（x）为假，所以xF（x） x F（x） 为真b）如果对任意 x使得F（x ） 为真，则xF（x）为真，而且x F（x） 也为真，所以xF（x） x F（x） 为真因此，公式为永真式. （2） xF（x） （x y G （x,y） xF（x） ） （3） xF（x） （xF（x） y G （y） （4） （F（x,y） R（x,y） R（x,y） （5） xy F（x,y） x y F（x,y） 解释I1,个体域为自然数集合N， F（x,y） : x等于y 此时，前件为真，后件为假 解释I2,个体域为自然数集合N， F（x,y） :

15、x小于等于y 此时，前件为真，后件为真 因此，公式为非永真式的可满足式2.3 一阶逻辑等值式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式 等值式与基本等值式基本等值式:命题逻辑中16组基本等值式的代换实例如， xF（x） xF（x） xF（x） xF（x）yG（y） xF（x）yG（y） （xF（x）yG（y） xF（x）yG（y） 消去量词等值式 设D=a1,a2,an （1） xA（x）A（a1）A（a2）A（an） （2） xA（x）A（a1）A（a2）A（an） （1） xA（x） x A（x） （2） xA（x） x A（x） 基本等值式（续）量词辖域

16、收缩与扩张等值式 设A（x）是含x自由出现的公式，B中不含x的出现关于全称量词的： x（A（x）B）xA（x）B x（BA（x）BxA（x） 基本的等值式（续）量词分配等值式 x（A（x）B（x）xA（x）xB（x）注意：对无分配律，对无分配律 量词等值式 x y A（x,y） y x A（x,y） x y y x A（x,y）其中A（x,y） 是x,y自由出现的谓词公式例 将下面命题用两种形式符号化 （1） 没有不犯错误的人 （2） 不是所有的人都爱看电影解 （1） 令F（x）：x是人，G（x）：x犯错误. x（F（x）G（x） 请给出演算过程，并说明理由. （2） 令F（x）：爱看电影.

17、给出演算过程，并说明理由. 例如，xy（F（x）（G（y）H（x,y） 是前束范式, 而 x（F（x）y（G（y）H（x,y）不是前束范式，公式的前束范式 定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置换规则、换名规则、代替规则进行等值演算. 换名规则与代替规则 换名规则: 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.代替规则: 对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替

18、，则所得公式与原来的公式等值. 公式的前束范式（续）例 求下列公式的前束范式 （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）xG（x） （量词否定等值式） x（F（x）G（x） （量词分配等值式）另有一种形式 xF（x）xG（x） xF（x）yG（y） （ 代替规则 ） xy（F（x）G（y） （ 量词辖域扩张 ）两种形式是等值的 （3） xF（x）xG（x） 解 xF（x）xG（x） x（F（x）G（x）

19、（为什么？） 或 xy（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） （换名规则） zy（F（z）（G（x,y）H（y） （为什么？或 xF（x）y（G（z,y）H（y） （代替规则） xy（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） xy（F（x,u）G（x,y）H（x,z）x与y不能颠倒 2.4 一阶逻辑推

20、理理论推理的形式结构判断推理是否正确的方法重要的推理定律推理规则构造证明附加前提证明法 推理 推理的形式结构有两种： 第一种 A1A2AkB （*） 第二种 前提：A1，A2，Ak 结论： B其中 A1,A2,Ak,B为一阶逻辑公式. 若（*）为永真式, 则称推理正确, 否则称推理不正确.判断方法: 真值表法, 等值演算法, 主析取范式法及构造证明法. 前3种方法采用第一种形式结构, 构造证明法采用第二种形式结构.重要的推理定律 第一组 命题逻辑推理定律代换实例 如 xF（x）yG（y）xF（x）为化简律代换实例. 第二组 由基本等值式生成 如 由 xA（x）xA（x） 生成 xA（x）xA（

21、x）, xA（x）xA（x）, 第三组 xA（x）xB（x）x（A（x）B（x） x（A（x）B（x）xA（x）xB（x） x（A（x） B（x） xA（x） x B（x） x（A（x） B（x） xA（x） x B（x）推理规则 （1）前提引入规则 （2）结论引入规则（3）置换规则 （4）假言推理规则（5）附加规则 （6）化简规则（7）拒取式规则 （8）假言三段论规则（9）析取三段论规则 （10）构造性二难推理规则（11）合取引入规则 推理规则（续）（12） 全称量词消去规则（简记为UI规则或UI）两式成立的条件是： x是A（x）中的自由出现的个体变项 在第一式中，取代x的y应为任意的不在A

22、（x）中约束出现的个体变项. 在第二式中，c为任意个体常项. 用y或c去取代A（x）中的自由出现的x时，一定要在x自由出现的一切地方进行取代.（13） 全称量词引入规则（简记为UG规则或UG） 该式成立的条件是： y是A（y）中自由出现的个体变项； 无论y取何值，A（y）应该均为真； 取代自由出现的y的x，也不能在A（y）中约束出现. （14） 存在量词引入规则（简记为EG规则或EG） c是使A为真的特定个体常项. 取代c的x不能在A（c）中出现过. （15） 存在量词消去规则（简记为EI规则或EI） c是使A为真的特定的个体常项. c不在A（x）中出现. 若A（x）中除自由出现的x外，还有其他自由出现的