离散数学教案 编号：C401 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主）： Ch4一阶逻辑基本概念 §4.1一阶逻辑命题符号化 教学目的要求（分掌握、熟悉、了解三个层次）： 1.理解掌握个体词、谓词、全称量词、存在量词的概念， 2。掌握一阶逻辑命题符号化能正确选择适当的谓词、量词和连结词： 教学重点、难点： 1)重点：掌握个体词、谓词、全称量词、存在量词的概念 2)难点：一阶罗组命题符号化 教学方法 利用黑板，CA课件等教学 教学用具： 黑板，CAI课件及其辅助设备 教学内容（注明：幸重点 #难点 ?疑点)： 基本要素(45分钟) 1.个体词研究对象中可以独立存在的具体的或抽象的客体。 个体常项表示具体的或特定的客体。用a,b,C,表示 个体变项表示不确定的或泛指的客体。用xy,2表示 个体域（论域）个体变项的取值范围 全总个体域宇宙间的一切事物组成的个体域。 。 ·2谓词刻划个体词的性质或个体词之间关系的词。 谓词常项表示具体性质和关系的谓词：表示特定的谓词。用下，G,H,.表示 谓词变项 表示抽象或泛指的谓词：表示不确定的谓词。也用F,G,H,表示 0元谓词：无个体变项。F(a),F(ab),F(al,a2.,an) n元谓词：含n个个体变项。F(x1,x2,Xn), 特性谓词：限制客体个体)变项变化范围的谓词。 3量词 表示个体常项或变项之间数量关系的词 全称量词“所有的"，“每一个”，“凡”，“一切”，“任意的”xP(x,yP(xy) 存在量词3“存在若”，有一个”，至少有一个”，“存在一些”，“某个”xP(x),yP(Xy) 一阶逻辑命题符号化(40分钟) 1.谓词的记法 设论域A中元素a,b,c∈A,满足关系PQ.R,记作P(a).Qab)R(a,b.c. 401
401 离 散 数 学 教 案 编号：C401 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch4 一阶逻辑基本概念 §4.1 一阶逻辑命题符号化 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解掌握个体词、谓词、全称量词、存在量词的概念， 2. 掌握一阶逻辑命题符号化能正确选择适当的谓词、量词和连结词； 。 教学重点、难点： 1） 重点：掌握个体词、谓词、全称量词、存在量词的概念 2） 难点：一阶逻辑命题符号化 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、 基本要素（45 分钟） 1. 个体词 研究对象中可以独立存在的具体的或抽象的客体。 个体常项 表示具体的或特定的客体。用 a, b, c,.表示 个体变项 表示不确定的或泛指的客体。用 x ,y ,z .表示 • 个体域(论域) 个体变项的取值范围. • 全总个体域 宇宙间的一切事物组成的个体域。 • • 2.谓词 刻划个体词的性质或个体词之间关系的词 。 谓词常项 表示具体性质和关系的谓词；表示特定的谓词。 用 F，G，H，.表示； 谓词变项 表示抽象或泛指的谓词；表示不确定的谓词。也用 F，G，H，.表示 0 元谓词 : 无个体变项。 F(a) , F(a,b) , F(a1,a2,.,an ) n 元谓词 : 含 n 个个体变项。 F(x1,x2,.,xn ) ， 特性谓词：限制客体(个体)变项变化范围的谓词。 3. 量词 表示个体常项或变项之间数量关系的词 全称量词 “所有的”，“每一个”，“凡”，“一切”，“任意的” xP(x), yP(x,y) 存在量词 “存在着”，有一个”，至少有一个”，“存在一些”，“某个” xP(x), yP(x,y) 二、一阶逻辑命题符号化 （40 分钟） 1.谓词的记法 设论域 A 中元素 a ,b , c ∈A, 满足关系 P,Q,R，记作 P(a),Q(a,b),R(a,b,c)
不满足关系记作一Pa,一Q(ab,一Ra,b,c. 例1将下列命趣符号化：李明是位大学生 2.个体变元在哪些论域取特定的值，对命题的真值极有影响。 续例1若x的论域为某大学的全体学生，则S)为真 若x的论域为某中学的全体学生，则$(x)为假： 若x的论域为某刷场中的观众，则S(x)真值不确定： 3.个体变项的顺序影响命题真值，不能随意调换 例3将下列命题符号化 ()小李比小赵高. (2)武汉位于北京和广州之间 4.如果事先没有给出个体域，都应以全总个体域为个体域。 5.在不同的个体域中，命题符号化的形式可能不一样 例4：将命题符号化：凡有理数均可表成分数 ()个体域是有理数集合 (2)个体域是实数集合 6.在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。 例5将命题符号化：()每个自然数都是实数 (2)有的自然数是实数 7,多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义 例6：将命题符号化，对任意的x,存在者y,使得x+y=5,个体域为实数集，其中H心y:xy=5, 课堂小结（约5分钟）
402 不满足关系记作 P(a), Q(a,b), R(a,b,c). 例 1 将下列命题符号化 : 李明是位大学生. 2. 个体变元在哪些论域取特定的值，对命题的真值极有影响。 续例 1 :若 x 的论域为某大学的全体学生，则 S(x)为真； 若 x 的论域为某中学的全体学生，则 S(x)为假； 若 x 的论域为某剧场中的观众，则 S(x)真值不确定； 3. 个体变项的顺序影响命题真值，不能随意调换. 例 3 将下列命题符号化 : (1)小李比小赵高. (2)武汉位于北京和广州之间 4. 如果事先没有给出个体域，都应以全总个体域为个体域。 5. 在不同的个体域中,命题符号化的形式可能不一样 。 例 4：将命题符号化: 凡有理数均可表成分数, (1) 个体域是有理数集合. (2) 个体域是实数集合 6. 在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。 例 5 将命题符号化:(1) 每个自然数都是实数. (2) 有的自然数是实数. 7. 多个量词同时出现时,不能随意颠倒它们的顺序，颠倒后会改变原命题的含义. 例 6：将命题符号化，对任意的 x，存在着 y,使得 x+y=5,个体域为实数集，其中 H(x,y)：x+y=5， 三、课堂小结（约 5 分钟）
离散数学教案 编号：C402 课时安排：2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学意、节或主题）： Ch4一阶逻辑基本概念 §4.2一阶逻辑公式及解释 教学目的要求（分掌握、熟悉、了解三个层次）： 1.理解一阶逻辑公式概念 2.掌据一阶逻辑公式的解释 教学重点、难点： 1)重点： 一阶逻辑公式解释的概念 2)难点：一阶逻辑公式解释 教学方法： 利用黑板.，CAI课件等教学 教学用具： 黑板，CAI课件及其辅助设备 教学内容（注明：·重点#难点？疑点： *一、一阶逻辑公式(45分钟) 1.一阶语言的字母表 个体常项 ab,c.a,bi,cig 个体变项：y.i,，孔 函数符号：￡ghfi,g1hi, 谓词符号：EG,.Fi,Gi,Hi 量词符号：，3 联结词符： 括号()和逗号， 字母表中的函数是广义的函数，它是一个从个体到个体的映射。 例1.fxy)表示x-y,7,4)表示个体自然数3： 例2.函数x):x的母亲c张明 P(x:x是教师，则P(⊙)：张明的母亲是教师 2。一阶语言的项
403 离 散 数 学 教 案 编号：C402 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch4 一阶逻辑基本概念 §4.2 一阶逻辑公式及解释 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解一阶逻辑公式概念 2. 掌握一阶逻辑公式的解释 教学重点、难点： 1） 重点：一阶逻辑公式解释的概念 2） 难点：一阶逻辑公式解释 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、一阶逻辑公式（45 分钟） 1. 一阶语言 的字母表 个体常项： a, b, c,.ai, bi, ci,.; 个体变项： x, y, z,.xi, yi, zi,.; 函数符号： f, g, h,.fi, gi, hi,.; 谓词符号： F, G, H,.Fi, Gi, Hi,., 量词符号 ： ∀，∃ 联结词符 ： ，∨，∧，→， ; 括号(）和逗号 ， • 字母表中的函数 是广义的函数，它是一个从个体到个体的映射。 • 例 1. f(x,y)表示 x - y, f(7,4)表示个体自然数 3； 例 2. 函数 f(x)：x 的母亲,c:张明 ； P(x)：x 是教师，则 P( f(c) )：张明的母亲是教师。 2．一阶语言 的项
1)个体常项和个体变项是项： ·2)若xl,x2,Xm)是任意n元函数，t山，2，tm是项，则，2tm)是项 3)所有的项都是有限次地使用1)2).得到的 ·3.一阶语言的合式公式 设x1,x2,m)是任意n元谓词，山，2，m是项，则称山，2，m)是原子公式。 ·)原子公式是合式公式， ·2)设A,B是合式公式，则(-A),(A八B),(AVB),(A→B),(AB)是公式 ·3)设A是合式公式，x是A中的个体变项 则xA，3xA也是合式公式。 4)只有有限次地应用1少3)所得到的公式是合式公式 4。辖域、约束变元和自由变元 ·xA,3xA中的x称为指导变项，A为相应量词的辖域， 在辖域A中，x的所有出现称为约束出现，x称为约束变元 ·A中不是约束出现的其他变项的出现称为自由出现，这些变项称为自由变元。 例13x(x+10)量词的辖域是全公式。x是约束变元 xx+y+1<0)量词的辖域是全公式。x是约束变元，y是自由变元 x(x+y+1=0一3y(x+y+1<0)3的辖域是(x+y+1<0) 寸的辖域是全公式，x是约 束变元，第二个y是约束变元，第一个y是自由变元. 5.闭式 ·没有自由变元的公式称为封闭的合式公式，简称闭式。 二、一阶语言的解释1(40分钟) 1由下面4部分组成 非空个体域D 3.DI上一些特定的函数： 4.DI上一些特定的谓词。 404
404 • 1）个体常项和个体变项 是项 ； • 2） 若 (x1, x2, ., xn)是任意 n 元函数, t1, t2, ., tn 是项， 则 (t1, t2, ., tn)是项； • 3） 所有的项都是有限次地使用 1）,2）.得到的. • 3.一阶语言 的合式公式 • 设 R(x1, x2, ., xn )是任意 n 元谓词, t1, t2, ., tn 是项，则称 R(t1, t2, ., tn )是原子公式。 • 1) 原子公式是合式公式, • 2) 设 A， B 是合式公式，则（A），（A∧B），（A∨B），（A→B），（AB）是公式, • 3) 设 A 是合式公式，x 是 A 中的个体变项 • 则 ∀xA ， ∃xA 也是合式公式。 • 4) 只有有限次地应用 1)-3)所得到的公式是合式公式. • 4. 辖域、约束变元和自由变元 • ∀xA，∃xA 中的 x 称为 指导变项 ，A 为相应量词的 辖域， • 在辖域 A 中, x 的所有出现称为 约束出现， x 称为 约束变元， • A 中不是约束出现的其他变项的出现称为 自由出现， 这些变项称为 自由变元。 • 例 1 ∃x (x +1=0) 量词的辖域是全公式。x 是约束变元 • ∀x(x+ y +1<0) 量词的辖域是全公式。x 是约束变元, y 是自由变元 • ∀x (x+ y+1=0 →∃y (x+ y +1<0)) ∃的辖域是(x+ y +1<0); ∀的辖域是全公式，x 是约 束变元，第二个 y 是约束变元，第一个 y 是自由变元. • 5. 闭式 • 没有自由变元的公式称为封闭的合式公式，简称闭式。 二、一阶语言的解释 I（40 分钟） 1. 由下面 4 部分组成 1. 非空个体域 DI ； 2. DI 中一部分特定元素； 3. DI 上一些特定的函数； 4. DI 上一些特定的谓词
例2：给定解释1如下： 1.DI={2,3: 2.D1中特定的元素a=2: 3.函数fx)为f2=3,f3)=2 4. 谓词Fx)为F(20,F(3 Gxy)为x+yl,ij=2,3 Uxy)为(2,2=L3,3)=l L2,3=L(3,2)=0 说明下列公式的含义x3y(xy) x(F(f(x))AG(x,f(x)));Vx(F(x)AG(x,a)). 定理4.1：闭式在任何解释下都变成命题 2.公式的分类 如果公式A在任何解释下均为真的，则称4为运辑有效式（或称永真式） 如果公式A在任何解释下均为假的，则称A为矛盾式（或称永假式） 若至少存在一个解释使A为真，则称A为可满足式。 3.代换实例 A0是命题公式， Pl,p2 ,m是命题变项，用n个谓词公式A1,A2,.,An分别代换pl,p2,pm 所得公式A称为A0的代换实例。 定理4.2：命题公式中的重言式的代换实例都是永真式：矛盾式的的代换实例都是矛盾式 例3：哪些是逻辑有效式，哪些是矛盾式？ (I)xPx一3xP() (2)xP(x)→(VxJyQ(x.y)→xPx) (3)x P(x)-(VxP(x)V3yG(y)) (4)-(Px,y)→Qxy)ΛQxy) (5)xyQ(x.y)-3xVyQ(x.y 三、课堂小结（约5分钟）
405 例 2：给定解释 I 如下： 1. DI={2，3}； 2. DI 中特定的元素 a=2; 3. 函数 f(x)为 f(2)=3，f(3)=2； 4. 谓词 F(x)为 F(2)=0，F(3)=1; G(x,y)为 x+y>1,i,j=2,3; L(x,y)为 L(2,2)= L(3,3)=1; L(2,3)= L(3,2)=0. 说明下列公式的含义 ∀x∃y L(x,y) ; ∃x(F(f(x)) ∧G (x, f(x))) ; ∀x(F(x) ∧G (x,a))。 定理 4.1 :闭式在任何解释下都变成命题. 2．公式的分类 如果公式 A 在任何解释下均为真的，则 称 A 为逻辑有效式（或称永真式） 如果公式 A 在任何解释下均为假的，则称 A 为矛盾式（或称永假式） 若至少存在一个解释使 A 为真，则称 A 为可满足式。 3．代换实例 A0 是命题公式， p1, p2, ., pn 是命题变项，用 n 个谓词公式 A1 ,A2,.,An 分别代换 p1, p2, ., pn ， 所得公式 A 称为 A0 的代换实例。 定理 4.2 : 命题公式中的重言式的代换实例都是永真式； 矛盾式的的代换实例都是矛盾式. 例 3:哪些是逻辑有效式，哪些是矛盾式？ （1）∀x P(x) →∃x P (x) （2）∀x P(x) →(∀x∃yQ(x,y) →∀x P(x)) （3）∀x P(x) →(∀x P(x) ∨∃yG(y)) （4）(P(x,y) →Q(x,y)) ∧ Q(x,y) （5）∀x∃yQ(x,y) →∃x∀y Q(x,y) 三、课堂小结（约 5 分钟）