离散数学教案 编号.C501 课时安排： 2学时教学课型：理论课 实验课口习题课口实践课口其它口 题目（教学章、 节或主题)： Ch5一阶逻辑等值演算与推理 §5.1一阶逻辑等值式与置换规则 §5.2一阶逻组前束范式。 教学目的要求（分掌握、热悉、了解三个层次） 1.掌握一阶逻辑等值式的概念，以及基本的等值式，特别是有关量词的4个基本等值式： 2。基本学握置换规则、换名规则和代替规则的概念和使用，了解一阶逻辑命题公式前束范式的概念，并 能够求一些简单公式的前束范式： 数学重点、难点： 1)重点： 阶逻辑等值式以及基本的等值式，置换规则 2)难点：置换规则 教学方法： 利用黑板，CAI课件等教学 教学用具： 黑板，CA课件及其辅助设备 教学内容（注明：·重点 #难点 ?疑点)： 幸一、一阶逻辑等值式与置换规则(30分钟) 1.设A,B是一阶逻辑中任意的两公式，若A一B为逻辑有效式，则称A与B是等值的，记作A一B 称AB为等值式。 命题逻辑中的24个等值式及其代换实例都 是一阶逻辑中的等值式。 命题逻辑的等价形式也是一阶逻辑的等价形式xP()台VxP(x)AxP(x) ·消去量词等值式设个体域为有限集D-{a,a2,an}则有 (1)VxA(x)A(aA(az).A(a) (2)3xA(x)A(a )vA(dz )v.v.A(a) ·量词否定等值式 Vx P(x)3x-P(x) 一3xP(x)Vx-Px) ·量词辖域收缩与扩张等值式 Ax)是含x自由出现的任意公式，而B中不含x的出现 Vx(A(x)VB)÷VxA(x)VB 2. Vx(A(x)AB)台VXA(x)AB 3. Hx(B→A(x)台B→xAx) 3x(A(x)VB)3xA(x)VB x(A(x)AB)JxA(x)AB 6. 3X(B→A(x)台B→3XA(x) 501
501 离 散 数 学 教 案 编号：C501 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch5 一阶逻辑等值演算与推理 §5.1 一阶逻辑等值式与置换规则 §5.2 一阶逻辑前束范式。 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 掌握一阶逻辑等值式的概念，以及基本的等值式，特别是有关量词的 4 个基本等值式； 2。基本掌握置换规则、换名规则和代替规则的概念和使用，了解一阶逻辑命题公式前束范式的概念，并 能够求一些简单公式的前束范式； 教学重点、难点： 1） 重点：一阶逻辑等值式以及基本的等值式，置换规则 2） 难点：置换规则 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、一阶逻辑等值式与置换规则（30 分钟） 1. 设 A，B 是一阶逻辑中任意的两公式，若 A↔B 为逻辑有效式，则称 A 与 B 是等值的，记作 AB, 称 AB 为等值式。 ⚫ 命题逻辑中的 24 个等值式及其代换实例都是一阶逻辑中的等值式。 命题逻辑的等价形式也是一阶逻辑的等价形式 ∀x P(x) ∀x P(x) ∧∀x P(x) ⚫ 消去量词等值式 设个体域为有限集 D={ a1 , a2 , ., n a }则有 （1）x A(x) A( a1 )A( 2 a )..A( n a ) (2) x A(x) A( a1 )A( 2 a )..A( n a ) ⚫ 量词否定等值式 ∀x P(x)∃x P(x) ∃x P(x)∀xP(x) ⚫ 量词辖域收缩与扩张等值式 A(x)是含 x 自由出现的任意公式,而 B 中不含 x 的出现 1. ∀x (A(x)∨B)∀x A(x)∨B 2. ∀x (A(x)∧B)∀x A(x)∧B 3. ∀x (B→A(x)) B→∀x A(x) 4. ∃x (A(x)∨B)∃x A(x)∨B 5. ∃x (A(x)∧B)∃x A(x)∧B 6. ∃x (B→A(x)) B→∃x A(x)
7.Vx (A(x)-BxA(x)-B 8. 3x(A(x)-B)eVxA(x)→B ·量词分配等值式 1.Vx(A(x)AB(x)xA(x)AVxB(x): 1. VxA(x)VVxB(x)Vx(A(x)VB(x)) 2 3x(A(x)AB(x)3x(x)A3xB(x) ●其它 xyQ(xy)台VyxQ(xy) 3x3yQx,y)÷3y3xQy) ,三条规则(25分钟) 1.置换规则设p(A)是含公式A的公式，p(B)是用公式B置换了p(A)中的A之后得到的公式。如果 A与B.则D(A)5DB)。 2.换名规则将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未曾 出现过的个体变项符号 公式中其余 部分不变，称为换名规则 3.代替规则 将量词辖域中出现的某个自由出现的个体变项，改成另一个辖域中未曾出现过的个体变项 符号，公式中其余部分不变，称为代替规则 三、前束范式(30分钟) 1.设A为一谓词公式，如果A具有如下形式：QxQx2.Qx:B 则称A是前束范式。其中每个Q,(≤≤)为或3，B为不含量词的谓词公式 前束范式标准型：所有量词都在公式最前面，辖域为整个公式。 定理任何一个一阶公式都等价于一个前束标准型公式。 例1：求下列公式的前束范式 (1)x F(x)A-3xG(x) (2)xFx)→3xGx) (3)3xFx)+可xGx} HxFx→3G》一xx (5)xPxy)→3 yQ(x.y)-VzR(xz 四、课堂小结（约5分钟） 502
502 7. ∀x (A(x)→B)∃x A(x)→B 8. ∃x (A(x)→B)∀x A(x)→B ⚫ 量词分配等值式 1. ∀x (A(x)∧B(x))∀x A(x)∧∀x B(x) ; 2. ∃x (A(x)∨B(x)) ∃x A(x)∨∃x B(x) ⚫ 两个蕴涵式 1. ∀x A(x)∨∀xB(x) ∀x (A(x)∨B(x)) 2. ∃x (A(x)∧B(x)) ∃x A(x)∧∃xB(x) ⚫ 其它 ∀x∀yQ(x,y) ∀y∀xQ(x,y) ∃x∃yQ(x,y)∃y∃xQ(x,y) 二、三条规则（25 分钟） 1．置换规则 设 (A)是含公式 A 的公式， (B)是用公式 B 置换了 (A)中的 A 之后得到的公式。如果 AB，则 (A) (B)。 2．换名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未曾 出现过的个体变项符号，公式中其余部分不变，称为换名规则 3.代替规则 将量词辖域中出现的某个自由出现的个体变项，改成另一个辖域中未曾出现过的个体变项 符号，公式中其余部分不变，称为代替规则 三、前束范式 （30 分钟） 1．设 A 为一谓词公式，如果 A 具有如下形式： Q1 1 x Q2 2 x .Qk k x B, 则称 A 是前束范式。其中每个 Qi (1≤i≤k)为∀或∃，B 为不含量词的谓词公式。 前束范式标准型：所有量词都在公式最前面，辖域为整个公式。 定理 任何一个一阶公式都等价于一个前束标准型公式。 例 1：求下列公式的前束范式 (1) ∀x F(x)∧∃x G(x) (2) ∀x F(x) →∃x G(x) (3) ∃xF(x) →∀xG(x) (4) (∀x F(x,y) →∃yG(y)) →∀x H(x,y) （5）∀x P(x,y) →∃yQ(x,y)→∀zR(x,z) 四、课堂小结（约 5 分钟）
离散数学教案 编号.C502 课时安排： 2学时 教学课型：理论课 实验课口习题课口实践课口其它 题目（教学章、 节或主题)： Ch5一阶逻辑等值演算与推理 §5.3一阶逻辑的推理 教学目的要求（分掌握、熟悉、了解三个层次）： 1.理解一阶逻辑自然推理系统F,以及该系统中的推理规则，特别是4个有关量词的推理规则，能够在 推理证明中正确使用这些推理规则，可以进行一些简单的推理证明。 2.掌握一阶逻辑的推理 教学重点、难点： 1)重点：一阶逻辑自然推理系统℉ 2)难点：一阶逻辑自然推理系统℉ 教学方法 利用黑板，CAI课件等教学 教学用具： 黑板.CAI课件及其辅助设各 教学内容（注明：重点 #难点 ?疑点) ,一阶逻辑的推理规则(50分钟) 1. 前提引入规则：在证明的任何步骤上都可以引用前提。 2. 结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。 置换想则：在证明的任何先豪上，公式的子公式郑可以用与之等价的其他公式置换 代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒 的公式. 5. 全称量词消去规则(UID):xA(x)=Ay方 VxA(x)=A(c) @ 两式成立的条件是： ().x是A(x)中自由出现的个体变项 (②在①式中，y为任意的不在Ax)中约束出现的个体变项。 (3)在②式中，c为任意的个体变项。 6 全称量词引入规则(UG:A(y)=VxA(x) 要求满足以下多件： ()y在A(x)中自由出现，且y取任何值时A均为真： (②取代y的x不能在Ay)中约束出现，否则也会产生错误： 7 存在量词消去规则(EI):xA(x)→A(C) 这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域 中必有某一元素c具有性质A。 但是，如果xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c 503
503 离 散 数 学 教 案 编号：C502 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch5 一阶逻辑等值演算与推理 §5.3 一阶逻辑的推理 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解一阶逻辑自然推理系统 F，以及该系统中的推理规则，特别是 4 个有关量词的推理规则，能够在 推理证明中正确使用这些推理规则，可以进行一些简单的推理证明。 2. 掌握一阶逻辑的推理 教学重点、难点： 1） 重点：一阶逻辑自然推理系统 F 2） 难点：一阶逻辑自然推理系统 F 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、一阶逻辑的推理规则（50 分钟） 1. 前提引入规则：在证明的任何步骤上都可以引用前提。 2. 结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。 3. 置换规则：在证明的任何步骤上，公式的子公式都可以用与之等价的其他公式置换。 4. 代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真 的公式。 5. 全称量词消去规则(UI)：xA(x)A(y); ① xA(x)A(c) ② 两式成立的条件是： ⑴. x 是 A(x)中自由出现的个体变项； ⑵ 在①式中，y 为任意的不在 A(x)中约束出现的个体变项。 ⑶ 在②式中，c 为任意的个体变项。 6. 全称量词引入规则(UG)：A(y)xA(x) 要求满足以下条件： ⑴ y 在 A(x)中自由出现，且 y 取任何值时 A 均为真； ⑵ 取代 y 的 x 不能在 A(y)中约束出现，否则也会产生错误； 7. 存在量词消去规则(EI)：xA(x) A(c) 这里 c 是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质 A 的元素，则个体域 中必有某一元素 c 具有性质 A。 但是，如果xA(x)中有其它自由变量出现，且 x 是随其它自由变量的值而变，那么就不存在唯一的 c
使得A(©)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。 例1,3xxy)中，X、y的论域是实数集合。若使用ES规则，则得cy,即在实数集中有一实数C, 等于任意实数y。结论显然不成立，这是因为AMx):xy中的x依赖于自由变量y,此时不能使用ES 8. 存在量词引入规则(EG):A(c归→yAy) 这个规则是说，如果个体域中某一元素c具有性质A,则个体域中存在着具有性质A的元素。这里 要求v不在A(C)中出现。 二、自然推理系统F(35分钟 1. 定义 2.实例 例2.证明：xP(x)→Q(x)APc→Qc) 例3证明：x(P(xvQx),xP(x)→3xQx) 三、课堂小结（约5分钟） 504
504 使得 A(c)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。 例 1，x(x=y)中，x、y 的论域是实数集合。若使用 ES 规则，则得 c=y，即在实数集中有一实数 c， 等于任意实数 y。结论显然不成立，这是因为 A(x)：x=y 中的 x 依赖于自由变量 y，此时不能使用 ES 规则。另外，要注意的是，如果xP(x)和xQ(x)都真，则对于某个 c 和某个 d，可以断定 P(c) Q(d) 必真，但不能断定 P(c) Q(c)为真。 8. 存在量词引入规则(EG)：A(c)yA(y) 这个规则是说，如果个体域中某一元素 c 具有性质 A，则个体域中存在着具有性质 A 的元素。这里 要求 y 不在 A(c)中出现。 二、自然推理系统 F（35 分钟） 1．定义 2．实例 例 2. 证明: x(P(x)→Q(x))P(c)Q(c) 例 3 证明：x(P(x)Q(x)), xP(x) xQ(x) 三、课堂小结（约 5 分钟）