价格（元）
装订：其它
开本：32开
装订：平装
开本：32开
装订：其它
开本：16开
装订：其它
装订：平装
开本：16开
装订：其它
开本：16开
装订：平装
开本：16开
装订：平装
开本：16开
版次：第1版第1次印刷
装订：平装
开本：大16开
装订：平装
开本：16开
装订：硬精装
开本：16开
装订：平装
开本：大32开
装订：平装
开本：32开
装订：平装
开本：32开
装订：硬精装
开本：16开
装订：硬精装
开本：16开
装订：平装
开本：大32开
装订：平装
开本：16开
装订：平装
开本：大32开
版次：一版一印
装订：平装
开本：大32开
版次：一版一印
装订：平装
开本：32开
装订：平装
开本：32开
装订：平装
开本：大32开
版次：一版一印
装订：平装
开本：大16开
装订：平装
装订：平装
开本：16开
版次：2010一版一印
装订：平装
开本：16开
装订：平装
开本：16开
装订：平装
开本：16开
装订：平装
开本：32开
装订：平装
开本：16开
装订：平装
开本：16开
装订：平装
开本：32开
装订：平装
开本：大16开
装订：平装
开本：大32开
装订：平装
开本：16开
装订：硬精装
开本：16开
装订：平装
开本：大16开
装订：平装
开本：16开
装订：平装
装订：平装
开本：16开
装订：平装
装订：平装
开本：16开
装订：平装
开本：16开
装订：平装
开本：16开
装订：平装
开本：16开
版次：1版1印
装订：其它
装订：平装
开本：16开
装订：平装
开本：32开
装订：平装
开本：16开
应用离散数学…到页第二章 谓词逻辑（Predicate Logic） Logic）2.1谓词的概念与表示(Predicate and its expression) 谓词的概念与表示 Predicate 2.2谓词公式与翻译(Predicate formulae) ) 谓词公式与翻译 2.3变元的约束(Bound of variable) ) 变元的约束 2.4谓词演算的等价式与蕴含式(Equiv
alences & 谓词演算的等价式与蕴含式implications of predicate calculus) 2.5前束范式(Prenex normal form) ) 前束范式2.6谓词演算的推理理论(Inference theory of 谓词演算的推理理论predicate calculus)计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate命题逻辑的局限性： 命题逻辑的局限性： 在命题逻辑中， 在命题逻辑中，命题是命题演算的基本 单位，不再对原子命题进行分解， 单位，不再对原子命题进行分解，因而无法 研究命题的内部结构、 研究命题的内部结构、成分及命题之间的内 在联系， 在联系，甚至无法处理一些简单而又常见的 推理过程。 推理过程。计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate例如，下列推理： 例如，下列推理： 所有的人都是要死的。 所有的人都是要死的。 苏格拉底是人。 苏格拉底是人。 苏格拉底是要死的。 苏格拉底是要死的。 众所周知,这是真命题 但在命题逻辑中,如 这是真命题。 众所周知 这是真命题。但在命题逻辑中 如 果用P,Q,R表示以上三个命题，则上述推理过 表示以上三个命题， 果用 表示以上三个命题 程为： 程为：（P∧Q）→R。借助命题演算的推理理 ∧ ） 。 论不能证明其为重言式 证明其为重言式。 论不能证明其为重言式。 计算机科学与技术学院更多精彩请关注 更多精彩请关注 更多精彩请关注 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate原因： 原因：命题逻辑不能将命题之间的内在联系 和数量关系反映出来。 和数量关系反映出来。 解决办法：将命题进行分解。 解决办法：将命题进行分解。计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate2.1 谓 词 的 概 念 与 表 示 (Predicate Predicate and its expression) 客体和 2.1.1 客体和谓词 在谓词逻辑中，可将原子命题划分为客体 原子命题划分为 在谓词逻辑中，可将原子命题划分为客体 和谓词两部分。 谓词两部分。 两部分 客体： 客体：可以独立存在的具体事物的或抽象的概 电子计算机、李明、玫瑰花、 念。例如，电子计算机、李明、玫瑰花、黑 实数、中国、思想、唯物主义等， 板、实数、中国、思想、唯物主义等，客体也 可称之为主语。 可称之为主语。 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate 谓词：用来刻划客体的性质或客体之间的相互关系的词。 谓词：用来刻划客体的性质或客体之间的相互关系的词。 例如在下面命题中： 例如在下面命题中： （1）张明是个劳动模范。 ）张明是个劳动模范。 （2）李华是个劳动模范。 ? 刻划客体的性质 ）李华是个劳动模范。 ? ? 是个大学生。 （3）王红是个大学生。 ? ）王红是个大学生 ? （4）小李比小赵高 ）小李比小赵高2cm。 。 ? 之间。 （5）点a在b与c之间。 ? 刻划客体之间的相互关系 ） 在 与 之间 ? （6）阿杜与阿寺同岁。 ? ）阿杜与阿寺同岁。 ? 是个劳动模范” 是个大学生” “是个劳动模范”、“是个大学生”、“…比…高2cm”、 比 高 、 “… 之间” 谓词。 在…与…之间”都是谓词。 与 之间 都是谓词 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate 刻划一个客体性质 的词称之为 一元谓词,刻划 刻划 一个客体性质的词称之为 一元谓词 刻划 个客体 一个客体性质 的词称之为一元谓词 刻划n个客体 之间关系的词称之为 元谓词. 之间关系的词称之为n元谓词 的词称之为 元谓词 一般我们用大写英文字母表示谓词 谓词， 一般我们用大写英文字母表示谓词，用小写英文字母 表示客体名称，例如，将上述谓词分别记作大写字母F、 表示客体名称，例如，将上述谓词分别记作大写字母 、 G、H、R，S则上述命题可表示为： 则上述命题可表示为： 、 、 ， 则上述命题可表示为 (1) F(a) a：张明 (2) F(b) b：李华 ： ： (3) G(c) c：王红 (4) H(s,t) s：小李 t：小赵 ： ： ： (5) R(a,b,c) (6) S(a,b) a:阿杜。b:阿寺。 阿杜。 阿寺 阿寺。 阿杜 其中(1)、 、 为一元谓词 为一元谓词， 为二元谓词， 其中 、(2)、 (3)为一元谓词， (4) 、 (6)为二元谓词， 为二元谓词 (5)为三元谓词。 为三元谓词。 为三元谓词 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate注: (1)单独一个谓词并不是命题，在谓词字母 单独一个谓词并不是命题， 单独一个谓词并不是命题 后填上客体所得到的式子称之为谓词填式。 后填上客体所得到的式子称之为谓词填式。 (2)在谓词填式中，若客体确定，则A(a1， 在谓词填式中， 在谓词填式中 若客体确定， ， a2...an)就变成了命题 就变成了命题 (3)在多元谓词表达式中，客体字母出现的 在多元谓词表达式中， 在多元谓词表达式中 先后次序与事先约定有关,一般不可以随意交 先后次序与事先约定有关 一般不可以随意交 换位置(如 上例中 上例中H(s,t) 与H(t, s)代表两个不 换位置 如,上例中 代表两个不 同的命题) 。 同的命题 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate设谓词H表示“是劳动模范” 表示客体名称 设谓词 表示“是劳动模范”, a表示客体名称 表示 张明, 表示客体名称李华,c表示客体名称这只老 表示客体名称李华 张明 b表示客体名称李华 表示客体名称这只老 那么H(a) 、 H(b)、 H(c)表示三个不同的命 虎，那么 、 表示三个不同的命 但它们有一个共同的形式,即 一般地， 题,但它们有一个共同的形式 即H(x).一般地， 但它们有一个共同的形式 一般地 H(x)表示客体 具有性质H。这里x表示抽象的或 表示客体x具有性质 。这里 表示抽象的或 表示客体 具有性质 泛指的客体，称为客体变元 客体变元， 泛指的客体，称为客体变元，常用小写英文字母 x, y, z, …表示。相应地，表示具体或特定的客体 表示。 表示 相应地， 客体常项， 的词称为客体常项 常用小写英文字母a,b,c, …表 的词称为客体常项，常用小写英文字母 表 示。 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate同理，客体变元 ， 具有关系 具有关系L，记作L(x,y); 同理，客体变元x，y具有关系 ，记作 客体变元x, 具有关系A，记作A(x,y,z). 客体变元 y, z具有关系 ，记作 具有关系 H(x)、L(x,y) 、A(x,y,z)本身并不是一个命题 只 、 本身并不是一个命题.只 本身并不是一个命题 有用特定的客体取代客体变元x,y,z后，它们才成为 有用特定的客体取代客体变元 后 命题。我们称H(x)、L(x,y) 、A(x,y,z)为命题函数。 命题。我们称 、 为命题函数。 一般地我们有计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate定义2.1.1:由一个谓词 和n个客体变元组成的表 由一个谓词H和 个客体变元组成的表 定义 由一个谓词 称为n元简单命题函数. 达式H(x1, x2 , …, xn)称为 元简单命题函数 达式 称为 由定义可知, 元谓词就是有 个客体变元的命题 元谓词就是有n个客体变元的 由定义可知 n元谓词就是有 个客体变元的命题 函数.当 称为0元谓词 因此,一般情况下 函数 当n=0时,称为 元谓词 因此 一般情况下 命题 时 称为 元谓词.因此 一般情况下,命题 函数不是命题;特殊情况 元谓词就变成一个命题. 特殊情况0元谓词就变成一个命题 函数不是命题 特殊情况 元谓词就变成一个命题 复合命题函数:由一个或几个简单命题函数以及 复合命题函数 由一个或几个简单命题函数以及 逻辑联结词组合而成的表达式. 逻辑联结词组合而成的表达式 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate的学习好,则 的工作好 例1:若x的学习好 则x的工作好 若 的学习好 学习好； 设S(x):x学习好；W(x):x工作好 学习好 工作好 则有S(x) → W(x) 则有 将下列命题用0元谓词符号化 例2:将下列命题用 元谓词符号化 将下列命题用 元谓词符号化. (1) 2是素数且是偶数 是素数且是偶数. 是素数且是偶数 (2) 如果 大于 则2大于 如果2大于 大于3,则 大于 大于4. (3) 如果张明比李民高 李民比赵亮高 则张明比赵亮 如果张明比李民高 李民比赵亮高,则张明比赵亮 张明比李民高, 高. 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate是素数. 是偶数. 解:(1) 设F(x): x是素数 G(x): x是偶数 是素数 是偶数 则命题符号化为： 则命题符号化为： F(2)∧G(2) ∧ (2) 设L(x,y) ：x大于 大于y. 大于 则命题符号化为： L(2,3) → L(2,4) 则命题符号化为： (3) 设 H(x,y): x比y高. a:张明 b:李民 c：赵亮 比 高 张明 李民 ： 则命题符号化为： 则命题符号化为： H(a,b)∧H(b ,c)→H(a,c) ∧ → 注意:命题函数中 命题函数中,客体变元在哪些范围内取特定的 注意 命题函数中 客体变元在哪些范围内取特定的 对命题的真值极有影响. 值,对命题的真值极有影响 对命题的真值极有影响 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate 例如: H(x,y)∧H(y ,z)→H(x,z) 例如 ∧ → 解释为: 大于y,当 都在实数中取值时, 若H(x,y)解释为 x大于 当x,y,z都在实数中取值时 解释为 大于 都在实数中取值时 则这个式子表示“ 大于y 大于z， 则这个式子表示“若x大于 且y 大于 ，则x大于 大于 大于 z” 。这是一个永真式。 这是一个永真式。 如果H(x,y)解释为 “x是y的儿子”, 当x,y,z都指人时， 解释为: 是 的儿子 的儿子” 都指人时， 如果 解释为 都指人时 则这个式子表示“ 的儿子， 则这个式子表示“若x为y的儿子 且y 是z的儿子， 为 的儿子 的儿子 的儿子” 这是一个永假式。 则x是z的儿子” 。这是一个永假式。 是 的儿子 如果H(x,y)解释为 “x距y10米”, 当x,y,z为平面上的 解释为: 距 如果 解释为 米 为平面上的 则这个式子表示“ 米且y距 米 点，则这个式子表示“若x距y10米且 距z10米，则 距 米且 x距z10米” 。这个命题的真值将由 这个命题的真值将由x,y,z的具体位 距 米 的具体位 置而定，它可能是1，也可能是0。 置而定，它可能是 ，也可能是 。 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate在命题函数中，客体变元的取值范围称为个体 在命题函数中，客体变元的取值范围称为个体 又称之为论域。 域，又称之为论域。个体域可以是有限事物的 集合，也可以是无限事物的集合。 集合，也可以是无限事物的集合。 全总个体域： 全总个体域：宇宙间一切事物组成的个体域称 为全总个体域。 全总个体域。计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate2.1.2 量词(Quantifiers)量词：分为全称量词( 和存在量词( 量词：分为全称量词(?)和存在量词(?) 1.全称量词 全称量词(The Universal Quantifiers) 全称量词 对日常语言中的“一切” 所有” 对日常语言中的“一切”、“所有”、“凡”、 “每一 个”、“任意”等词，用符号“?” 表示， ?ｘ 任意”等词，用符号“ 表示 对个体域里的所有个体， ｘＦ( 对个体域里的所有个体， ?ｘＦ(ｘ)表示个体域 里的所有个体具有性质F.符号 符号“ 称为全称量 里的所有个体具有性质 符号“?”称为全称量
计算机科学与技术学院 词.第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate例3：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）凡是人都呼吸。 ）凡是人都呼吸。 （2）每个学生都要参加考试。 ）每个学生都要参加考试。 (3) 任何整数或是正的或是负的。 任何整数或是正的或是负的。 当个体域为人类集合 人类集合时 解: (1) 当个体域为人类集合时： 呼吸。 令F(x): x呼吸。则（1）符号化为?xF(x) 呼吸 ）符号化为? 当个体域为全总个体域 全总个体域时 当个体域为全总个体域时： 是人。 令M(x): x是人。则（1）符号化为 是人 ） F(x)). ?x(M(x) →F(x)). 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate(2) 当个体域为全体学生的集合时： 当个体域为全体学生的集合 全体学生的集合时 要参加考试。 令P(x): x要参加考试。则（2）符号化为 要参加考试 ） ?xP(x) 当个体域为全总个体域时： 当个体域为全总个体域时 全总个体域 是学生。 令S(x): x是学生。则（2）符号化为 是学生 ） P(x)). ?x(S(x) →P(x)).计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate(3) 当个体域为全体整数的集合时： 当个体域为全体整数的集合 全体整数的集合时 是正的。 是负的。 令P(x): x是正的。N(x): x是负的。则（3）符 是正的 是负的 ） 号化为 x(P(x)∨ ?x(P(x)∨N(x)) 当个体域为全总个体域 全总个体域时 当个体域为全总个体域时： 令I(x): x是整数。则（3）符号化为 是整数。 ） x(I(x)→(P(x)∨ )). ?x(I(x)→(P(x)∨N(x))). ))计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate2.存在量词 存在量词(The Existential Quantifiers) 存在量词 对日常语言中的“有一个” 有的” 对日常语言中的“有一个”、“有的”、“存在 着”、 至少有一个” 存在一些” “至少有一个”、 “存在一些”等词，用符号 “? ” 表示， 表示存在个体域里的个体， 表示 ?ｘ表示存在个体域里的个体， ｘＦ( 表示存在个体域里的个体具有性质F. ?ｘＦ(ｘ)表示存在个体域里的个体具有性质 符号“ 称为存在量词. 存在量词 符号“?”称为存在量词 例4：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）一些数是有理数。 ）一些数是有理数。
计算机科学与技术学院 （2）有些人活百岁以上。 ）有些人活百岁以上。第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate是有理数。 解: (1)令Q(x): x是有理数。则（1）符号化为 令 是有理数 ） ?ｘQ(x) （2）当个体域为人类集合时： ）当个体域为人类集合时 人类集合 活百岁以上。 令G(x): x活百岁以上。则（2）符号化为 活百岁以上 ） ?xG(x) 当个体域为全总个体域 全总个体域时 当个体域为全总个体域时： 是人。 令M(x): x是人。则（2）符号化为 是人 ） ?x(M(x) ∧ G(x))计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate有时需要同时使用多个量词。 有时需要同时使用多个量词。 命题“对任意的x,存在 使得x+y=5”, 取 存在y, 例5. 命题“对任意的 存在 使得 个 体域为实数集合 则该命题符号化为: 体域为实数集合,则该命题符号化为 集合 则该命题符号化为 ?x ?y H(x,y). 其中H(x,y): x+y=5. 这是个真命题 这是个真命题. 其中计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate3. 使用量词时应注意的问题 使用量词时应注意的问题 （ 1） 在不同的个体域 ， 同一命题的符号化形式 ） 在不同的个体域， 可能相同也可能不同。 可能相同也可能不同。 （ 2） 在不同的个体域 ， 同一命题的真值可能相 ） 在不同的个体域， 同也可能不同。 如 （ ）表示x为大学生 为大学生。 同也可能不同。(如,R（x）表示 为大学生。如 果个体域为大学里的某个班级的学生， 果个体域为大学里的某个班级的学生，则 ?x R（x）为真 ； 若个体域为中学里的某个班 （ ）为真； 级的学生， 级的学生，则?x R（x）为假 （ ）为假.). 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate（3）约定以后如不指定个体域，默认为全总个体 ）约定以后如不指定个体域， 对每个客体变元的变化范围,用特性谓词加 域 。 对每个客体变元的变化范围 用特性谓词加 以限制. 以限制 特性谓词:限定客体变元变化范围的谓词 如例3中 限定客体变元变化范围的谓词(如例 特性谓词 限定客体变元变化范围的谓词 如例 中 的M（x）). （ ） 一般而言，对全称量词， 一般而言，对全称量词，特性谓词常作蕴含的前 件，如（?x）(M(x) →F(x))；对存在量词，特性 ） ；对存在量词， 谓词常作合取项，如（? x）(M(x)∧ G(x)). 谓词常作合取项， ） ∧ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate(4)一般来说，当多个量词同时出现时，它们的顺 一般来说，当多个量词同时出现时，序不能随意调换。 序不能随意调换。如： 在实数域上用H(x,y)表示 表示x+y=5,则命题“对于任 则命题“ 在实数域上用 表示 则命题 意 的 x, 都 存 在 y 使 得 x+y=5” 可 符 号 化 为 ： 其真值为1.若调换量词顺序后为 ? x?yH(x,y) ,其真值为 若调换量词顺序后为： ? 其真值为 若调换量词顺序后为： 其真值为0。 ?y?xH(x,y) , 其真值为 。 ? (5) 当个体域为有限集合时 如D={a1, a2 …, an},对任 当个体域为有限集合时,如 对任 意谓词A(x),有 意谓词 有 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate (?x) A(x)?A(a1)∧A(a2)∧…∧A(an ) ? ? ∧ ∧ ∧ （?x）A(x)?A(a1)∨A(a2)∨…∨A(an ) ） ? ∨ ∨ ∨ 例6：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）所有的人都长头发。 ）所有的人都长头发。 （2）有的人吸烟。 ）有的人吸烟。 （3）没有人登上过木星。 ）没有人登上过木星。 （4）清华大学的学生未必都是高素质的。 ）清华大学的学生未必都是高素质的。 是人。 特性谓词） 解：令 M(x): x是人。（特性谓词） 是人 长头发。 （1） 令F(x): x长头发。则符号化为： ） 长头发 则符号化为：（?x）(M(x) →F(x)) ） 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate吸烟。 （2） 令S(x): x吸烟。则符号化为： ） 吸烟 则符号化为： (M(x)∧S(x)) （?x）(M(x)∧ (x)) 登上过木星。 （3） 令D(x): x登上过木星。则符号化为： ） 登上过木星 则符号化为： ┐(?x)(M(x)∧D(x)) 是清华大学的学生。 （ 4） 令 Q(x):x是清华大学的学生 。 H(x):x是高素 ） 是清华大学的学生 是高素 质的。则符号化为： 质的。则符号化为： ┐(?x)(Q(x) →H(x)) (x)) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.1 谓词的概念与表示 Predicate and Its Expression) 谓词的概念与表示(Predicate小结:本节将原子命题进行分解 分为客体和谓词 小结 本节将原子命题进行分解,分为客体和谓词 本节将原子命题进行分解 两部分.进而介绍了客体和谓词 一元谓词和n元 进而介绍了客体和谓词、 两部分 进而介绍了客体和谓词、一元谓词和 元 谓词、命题函数、全称量词和存在量词等概念。 谓词、命题函数、全称量词和存在量词等概念。 重点掌握一元谓词和 元谓词的概念、 一元谓词和n元谓词的概念 重点掌握一元谓词和 元谓词的概念、全称量词 和存在量词及量化命题的符号化。 和存在量词及量化命题的符号化。 作业: 预习第二章 预习第二章§ 作业 1.预习第二章§2.2, §2.3 2 . 习题 .1 习题2计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 )2.2谓词公式与翻译 谓词公式与翻译(Predicate formulae) ) 谓词公式与翻译n元谓词A(x1，x2...xn) 称为谓词演算的原子公式。 元谓词 称为谓词演算的原子公式 原子公式。 ， 定义2.2.1谓词演算的合式公式 可由下述各条组成 谓词演算的合式公式 可由下述各条组成: 定义 谓词演算的合式公式,可由下述各条组成 （1）原子公式是合式公式。 ）原子公式是合式公式。 是合式公式， ┐ 也是合式公式 也是合式公式。 （2）若A 是合式公式，则(┐A)也是合式公式。 ） 是合式公式， （3）若A，B是合式公式，则(A ∧ B)，(A ∨ B)， ） ， 是合式公式 ， ， (A → B)，(A ? B)也是合式公式。 也是合式公式。 ， 也是合式公式 （4）若A是合式公式，x是A中出现的任何变元,则 (?x)A , (?x) ，也是合式公式。 ?x)A，也是合式公式。 (5)只有有限次应用 只有有限次应用(1)~(4)得到的公式是合式公式 得到的公式是合式公式 只有有限次应用 得到的公式是合式公式. 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 )例1：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）凡正数都大于零。 ）凡正数都大于零。 的素数。 （2）存在小于 的素数。 ）存在小于2的素数 （3）没有不能表示成分数的有理数。 ）没有不能表示成分数的有理数。 （4）并不是所有参加考试的人都能取得好成绩。 ）并不是所有参加考试的人都能取得好成绩。 是正数。 大于零。 解：（1） 令F(x): x是正数。M(x):x大于零。则 ） 是正数 大于零 符号化为： 符号化为： （?x）(F(x)→M(x)) ） → 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 ) 小于2。 是素数。 （2）令E(x): x小于 。S(x):x是素数。则符号化为： ） 小于 是素数 则符号化为： 真值为0。 （?x)(E(x)∧S(x)) ∧ 真值为 。 是有理数。 能表示成分数。 （ 3） 令 D(x): x是有理数 。 F(x):x能表示成分数 。 ） 是有理数 能表示成分数 则符号化为： ? 则符号化为： (?x)(D(x) →F(x)) 或 真值为１ ┐(?x)(D(x)∧ ┐F(x)) ? ∧ 真值为１。 是人.Q(x):x参加考试。H(x):x取得 参加考试。 （4）令M(x)：x是人 ） ： 是人 参加考试 取得 好成绩。则符号化为： 好成绩。则符号化为： ┐(?x)(M(x)∧Q(x)→H(x)) 或 ? ∧ (?x)(M(x)∧Q(x)∧┐H(x)) ? ∧ ∧ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 )例2：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）所有运动员都钦佩某些教练 ）所有运动员都钦佩某些教练. （2）有些运动员不钦佩教练 ）有些运动员不钦佩教练. 设：L(x):x是运动员 J(y):y是教练 是运动员 是教练 A(x,y):x钦佩 钦佩y 钦佩 (?x)( y)( (x,y)) (1) (?x)(L(x) →（?y)(J(y)∧A(x,y))) (2)（ x)( ∧(?y)( (x,y)) (2)（?x)(L(x) ∧(?y)(J(y)→ ┐A(x,y))) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 ) 例3：在谓词逻辑中将下列命题符号化 ：在谓词逻辑中将下列命题符号化. （1）那位戴眼镜的用功的大学生在看这本大而厚的巨著 ）那位戴眼镜的用功的大学生在看这本大而厚的巨著. 2） （2）P63 (7) 是大学生. 戴眼镜. 解: (1)设：S(x):x是大学生 A(x):x戴眼镜 设 是大学生 戴眼镜 B(x):x用功 D(x):x是巨著 F(x,y):x看y. 用功. 是巨著. 用功 是巨著 看 E(y):y是大的 G(y):y是厚的 a:那位 b:这本 是大的. 是厚的. 那位 是大的 是厚的 这本 (1)符号化为 符号化为: (1)符号化为 A(a)∧B(a)∧S(a)∧D(b)∧E(b)∧G(b)∧F(a,b) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 )连续. 大于y. （2）设：P(x,y):x在y连续 Q(x,y):x大于 ） 在 连续 大于 (2)符号化为 符号化为: P(f,a)?(?ε)(Q(ε,0)→((?δ) Q(δ,0)∧ ?? ∧ (?x) (Q(δ, ?x ? a →Q(ε, ) x ? →Q(ε, )a f ( x) ? f ()))) a)?P(f,a)?(?ε)(?δ)(?x)(Q(ε,0)→ ?? ?(Q(δ,0)∧(Q(δ, ∧f ( x) ? f)))). (a)计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.2 谓词公式与翻译(Predicate formulae) 谓词公式与翻译 )小结：本节介绍了谓词合式公式的概念， 小结：本节介绍了谓词合式公式的概念， 谓词合式公式的概念 重点掌握谓词公式的翻译 谓词公式的翻译. 重点掌握谓词公式的翻译. 作业: 1， 作业: P41 1 ，2计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )2.3 变元的约束 变元的约束(Bound of variable) ) 2.3.1 变元的约束 2.3.2 约束变元的换名与自由变元的代入 约束变元的换名与自由变元的代入 换名与自由变元的计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )2.3.1变元的约束 (Bound of variable) 变元的约束 ) 定义2.3.1:在谓词公式中,形如 ?x)P(x)和(?x)P(x) 公式中 形如(? 定义 在谓词公式 形如 和? 的部分,称为谓词公式的x约束部分 的部分 称为谓词公式的 约束部分 (?x)P(x)或 称为谓词公式的 约束部分.(?x)P(x)中的 叫做量词的指导变元或作用变 ? 中的x叫做量词的指导变元 指导变元或称为相应量词的作用域或 元，P(x)称为相应量词的作用域或辖域。 称为相应量词的作用域 辖域。计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )的辖域中， 的所有出现都称为 的所有出现都称为约束出 在?x和?x的辖域中，x的所有出现都称为约束出 和 的辖域中 相应的x称为约束变元; 称为约束变元 现，相应的 称为约束变元 P(x)中除约束变元以 中除约束变元以 外出现的变元称为是自由变元 自由变元。 外出现的变元称为是自由变元。 →?y(W(y) ∧ L(x,y,z))) 例1： 1、?x( H(x,y)→? ： 、 →? 2、 ?x( H(x)→W(y)) → ?y( F(x) ∧L(x,y,z)) 、 →计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )说明: 说明(1)n元谓词公式 元谓词公式A(x1，x2...xn) 中有n个自由变元 若 中有 个自由变元,若 元谓词公式 个自由变元 ， 对其中的k(k≤n)个进行约束 则构成了 元谓词 个进行约束,则构成了 元谓词; 对其中的 个进行约束 则构成了n-k元谓词 如果一个公式中没有自由变元出现,则该公式就 如果一个公式中没有自由变元出现 则该公式就 变成了一个命题 (2)一个公式的约束变元所使用的名称符号是无关 一个公式的约束变元所使用的名称符号是无关 紧要的,如 ? 意义相同. 紧要的 如(?x)M(x)与(?y)M(y)意义相同 与? 意义相同计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 ) 2.3.2 约束变元的换名与自由变元的代入规则 约束变元的换名与自由变元的代入规则 换名与自由变元的在例1中 一个变元在同一个公式中既是自由 在例 中,一个变元在同一个公式中既是自由 出现又是约束出现, 这样在理解上容易发生混淆.为 出现又是约束出现 这样在理解上容易发生混淆 为 了避免这种混乱,可对约束变元进行换名. 可对约束变元进行换名 了避免这种混乱 可对约束变元进行换名 换名规则: 对约束变元而言 对约束变元而言） 换名规则 (对约束变元而言） 对约束变元进行换名,使得一个变元在一个公式中 对约束变元进行换名 使得一个变元在一个公式中 只呈一种形式出现. 只呈一种形式出现计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )(1)约束变元可以换名 其更改的变元名称范围是量 约束变元可以换名,其更改的变元名称范围是量 约束变元可以换名 词中的指导变元以及该量词作用域中所出现的 该变元,公式的其余部分不变 公式的其余部分不变. 该变元 公式的其余部分不变 (2)换名时一定要更改为作用域中没有出现的变元 换名时一定要更改为作用域中没有出现的变元 名称. 名称计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )例1: ?x( P(x)→R(x,y))∧ L(x,y) → ∧ 换名为? 换名为?t( P(t)→R(t,y))∧ L(x,y) → ∧ ?x( H(x,y)→? →?y(W(y) ∧ L(x,y,z))) →? 换名为? →?s(W(s) ∧ L(x,s,z))) 换名为?x( H(x,y)→? →?计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )代入规则（对自由变元而言） 代入规则（对自由变元而言） 对公式中自由变元的更改称为代入 (1)对于谓词公式中的自由变元可以作代入 代入时 对于谓词公式中的自由变元可以作代入,代入时 对于谓词公式中的自由变元可以作代入 需要对公式中出现该自由变元的每一处进行; 每一处进行 需要对公式中出现该自由变元的每一处进行 (2)用以代入的变元与原公式中所有变元的名称不 用以代入的变元与原公式中所有变元的名称不 能相同. 能相同 例如对例1中的公式 例如对例 中的公式?x( P(x)→R(x,y))∧ L(x,y) → ∧ 自由变元y用 来代入 来代入,得 自由变元 用z来代入 得 ?x( P(x)→R(x,z))∧ L(x,z) → ∧ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.3 变元的约束(Bound of variable) 变元的约束 )小结： 本节介绍了约束变元 自由变元的概念 约束变元、 的概念， 小结 ： 本节介绍了 约束变元 、 自由变元 的概念 ， 重点掌握约束变元的换名与自由变元的代入. 约束变元的换名与自由变元的代入 重点掌握约束变元的换名与自由变元的代入. 作业: 作业: P43: 2，3 ，计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式2.4谓词演算的等价式与蕴含式(Equivalences &implications of predicate calculus) 2.4.1谓词的等价和永真的概念 2.4.2谓词演算的等价式与蕴含式计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式2.4.1谓词的等价和永真的概念 谓词的等价和永真的概念 定义2.4.1:给定任意的谓词公式 其个体域为 对于 的 给定任意的谓词公式A,其个体域为 对于A的 定义 给定任意的谓词公式 其个体域为E,对于 所有赋值,公式 都为真,则称 公式A都为真 则称A在 上是永真的(或有效 上是永真的 所有赋值 公式 都为真 则称 在E上是永真的 或有效 若对于A的所有赋值 公式A都为假 则称A在 上是 的);若对于 的所有赋值 公式 都为假 则称 在E上是 若对于 的所有赋值,公式 都为假,则称 永假的(或不可满足的 或不可满足的);若至少存在着一种赋值使得公 永假的(或不可满足的);若至少存在着一种赋值使得公 为真,则称 上是可满足的 式A为真 则称 在E上是可满足的 为真 则称A在 上是可满足的. 定义2.4.2:给定任何两个谓词公式 、B，设它们有共 给定任何两个谓词公式A、 ， 定义 给定任何两个谓词公式 同的个体域E，若对A和 的任一组变元进行赋值 的任一组变元进行赋值， 同的个体域 ，若对 和B的任一组变元进行赋值，所 得命题的真值相同，则称谓词公式 谓词公式A和 在 上等价 上等价， 得命题的真值相同，则称谓词公式 和B在E上等价， 并记为A B 并记为 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式 1、命题公式的推广 、 在命题公式中成立的式子， 在命题公式中成立的式子，用谓词公式去代换其 中相应的命题变元， 中相应的命题变元，得到的公式依然成立 P(x)→Q(x))? 如： ?x( P(x)→Q(x))??x(┐P(x) ∨ Q(x)) ┐ Q(x)? Q(x)） ┐P(x)∨┐Q(x)?┐（P(x) ∧ Q(x)）等 2、量词与┐之间的关系 、 x)P(x)? x)┐ ┐(?x)P(x)?(?x)┐P(x) x)P(x)? x)┐ ┐(?x)P(x)?(?x)┐P(x) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式 3、量词辖域的扩张与收缩 量词辖域中如果有合取或析取项， 量词辖域中如果有合取或析取项，且其中有一个 是命题，则可将该命题移至量词辖域之外。 是命题，则可将该命题移至量词辖域之外。如： （?x）（A(x)∨B）?（?x）A(x)∨B ） ∨ ） ） ∨ （?x）（A(x)∧B）?（?x）A(x)∧ B ） ∧ ） ） ∧ （?x）（A(x)∨B）?（?x）A(x)∨B ） ∨ ） ） ∨ （?x）（A(x)∧B）?（?x）A(x)∧B ） ∧ ） ） ∧ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式量词辖域的扩张（?xA(x)→B）?（?x) (A(x)→ B） → ） → ） (（?x)A(x)→ B)?(?x) (A(x)→B） （ → ?? → ） (B→ (?x)A(x)）?（?x)(B→ A(x)） → ? ） → ） (B→ (?x)A(x))?(?x)(B→ A(x)) → ? ?? → 另有多个公式见课本70页 另有多个公式见课本 页计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式4、量词分配等值式 、是任意的含自由出现个体变元x的 设A(x)、B(x)是任意的含自由出现个体变元 的 、 是任意的含自由出现个体变元 公式， 公式，则 (1) ?x(A(x)∧B(x))?? x A(x) ∧ ?x B(x) ∧ ?? (2)?x(A(x)∨B(x))?? x A(x) ∨ ? x B(x) ? ∨ ?? (3)?x(A(x)∨B(x)) ? ?x A(x)∨ ?x B(x) ? ∨ ∨ (4) ? x(A(x)∧B(x))?? A(x)∧ ?x B(x) ∧ ??x ∧ ?? 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式 5.谓词演算蕴含式 谓词演算蕴含式 xA(x)∨? ?xA(x)∨?xB(x) ? ?x(A(x)∨B(x)) ? x(A(x)∧B(x)) ? ?x A(x)∧ ?x B(x) 6.多个量词的使用 多个量词同时出现时,其顺序是至关重要的. 多个量词同时出现时,其顺序是至关重要的.计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式?x?y P(x,y) ? ?y?x P(x,y) ? ?y?x P(x,y) ? ?x?y P(x,y) ? ?y?x P(x,y) ?? ?x?y P(x,y) ? ?y?x P(x,y) ? ?x?y P(x,y)计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.4 谓词演算的等价式与蕴含式 小结： 小结 ： 本节介绍了谓词公式的概念及谓词演算 等价式与蕴涵式， 重点掌握谓词演算的等价 的 等价式与蕴涵式 ， 重点掌握谓词演算的 等价 式与蕴涵式 作业:P50: 1(1),(3)；2,3(1)；4 作业 ； ；计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )2.5 前束范式 前束范式(Prenex normal form) )2.5.1 前束范式 前束范式(Prenex normal form) ) 2.5.2 前束析取范式和前束合取范式 前束析取范式和前束合取范式(Prenexdisjunctive normal form & Prenex conjunctive normal form) )计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )2.5.1前束范式 前束范式(Prenex normal form) )定义2.5.1:任何一个谓词公式 ，如果具有如下形式： 任何一个谓词公式A，如果具有如下形式： 定义 任何一个谓词公式 (□x1) (□x2)… (□xn)B □ □ □ 其中□可能是量词?或量词? 其中□可能是量词?或量词?， xi（i=1，… n）是客体变 ， ） 是不含量词的谓词公式 是前束范式。 元，B是不含量词的谓词公式，则称 是前束范式。 是不含量词的谓词公式，则称A是前束范式 说明:前束范式 的量词均在全式的开头,它们的作用域 前束范式的量词均在全式的开头 说明 前束范式 的量词均在全式的开头 它们的作用域 延伸到整个公式的末尾。 延伸到整个公式的末尾。 （（F(x)∧G(y)）∧┐H(x,y)） √ 例1: ?x?y（（ ? （（ ∧ ） ） ?x?y(F(x,y)∧G(y,z))∨ ?x H(x,y,z) × ? ∧ ∨ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 定理2.5.1:任何一个谓词公式 均和一个前束范 定理 任何一个谓词公式,均和一个前束范 任何一个谓词公式 式等价。 式等价。前束范式的求法： 前束范式的求法： 第一步：否定深入。即利用量词转化公式， 第一步：否定深入。即利用量词转化公式，把否定联结 词深入到命题变元和谓词填式的前面。 谓词填式的前面 词深入到命题变元和谓词填式的前面。 第二步：改名。即利用换名规则、 第二步：改名。即利用换名规则、代入规则更换一些变 元的名称，以便消除混乱。 元的名称，以便消除混乱。 第三步：量词前移。 第三步：量词前移。即利用量词辖域的收缩与扩张把量 词移到前面。这样便可求出与公式等价的前束范式。 词移到前面。这样便可求出与公式等价的前束范式。 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 例2:求下列公式的前束范式。 求下列公式的前束范式。(1) (?x) F ( x) ∧ ?(?x)G ( x) (2) (?x) F ( x) ∨ ?(?x)G ( x) (3) (?x) F ( x) → ?(?x)G ( x) (4) (?x) F ( x) → ?(?x)G ( x) (5) ((?x) F ( x, y ) → (?y )G ( y )) → (?x) H ( x, y ) (6) ?(?x){(?y ) A( x, y ) → (?x)(?y )[ B( x, y ) ∧ (?y )( A( y, x) → B( x, y ))]} 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 解: (1) (?x) F ( x) ∧ ?(?x)G ( x)? (?x) F ( x) ∧ (?x)?G ( x)(量词转换律) ? (?x)( F ( x) ∧ ?G ( x))(量词分配)(2) (?x) F ( x) ∨ ?(?x)G ( x) ? (?x) F ( x) ∨ (?x)?G ( x)(量词转换律) ? (?x) F ( x) ∨ (?y )?G ( y )(换名) ? (?x)( F ( x) ∨ (?y )?G ( y ))(辖域扩张) ? (?x)(?y )( F ( x) ∨ ?G ( y ))(辖域扩张) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )(5) ((?x) F ( x, y ) → (?y )G ( y )) → (?x) H ( x, y ) ? ?(?(?x) F ( x, y ) ∨ (?y )G ( y )) ∨ (?x) H ( x, y ) ? ((?x) F ( x, y ) ∧ ?(?y )G ( y )) ∨ (?x) H ( x, y ) ? ((?x) F ( x, y ) ∧ (?y )?G ( y )) ∨ (?x) H ( x, y ) ? ((?x) F ( x, z ) ∧ (?y )?G ( y )) ∨ (?x) H ( x, z )(代入) ? ((?x) F ( x, z ) ∧ (?y )?G ( y )) ∨ (?t ) H (t , z )(换名) ? (?x)(?y )( F ( x, z ) ∧ ?G ( y )) ∨ (?t ) H (t , z )(辖域扩张) ? (?x)(?y )(( F ( x, z ) ∧ ?G ( y )) ∨ (?t ) H (t , z ))(辖域扩张) ? (?x)(?y )(?t )(( F ( x, z ) ∧ ?G ( y )) ∨ H (t , z ))(辖域扩张) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )(6) ?(?x){(?y ) A( x, y ) → (?x)(?y )[ B ( x, y ) ∧ (?y )( A( y, x) → B ( x, y ))]} ? (?x)?{?(?y ) A( x, y ) ∨ (?x)(?y )[ B ( x, y ) ∧ (?y )(?A( y, x) ∨ B ( x, y ))]} ? (?x){(?y ) A( x, y ) ∧ (?x)(?y )[?B ( x, y ) ∨ (?y )( A( y, x) ∧ ?B( x, y ))]}计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )(6)续 ? (?x){(?y ) A( x, y ) ∧ (?x)(?y )[?B( x, y ) ∨ (?y )( A( y, x) ∧ ?B( x, y ))]} ? (?x){(?y ) A( x, y ) ∧ (?u )(?v)[?B(u , v) ∨ (?z )( A( z , u ) ∧ ?B(u , z ))]}(换名) ? (?x)(?y )(?u )(?v)(?z ){ A( x, y ) ∧ [?B(u , v) ∨ ( A( z , u ) ∧ ?B(u , z ))]} 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) )2.5.2前束析取范式和前束合取范式 前束析取范式和前束合取范式(Prenex disjunctivenormal form & Prenex conjunctive normal form) ) 在前束范式的基础上,可以定义前束析 合)取范式 在前束范式的基础上 可以定义前束析(合 取范式. 可以定义前束析 取范式 定义2.6.2:任何一个谓词公式 ， 如果具有如下形式则 任何一个谓词公式A， 定义 任何一个谓词公式 称为前束合取范式： 称为前束合取范式： (□x1) (□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧ □ □ □ ∨ ∧ (A21∨A22∨…∨A2k2 )∧…∧(Am1∨Am2∨…∨Amkm)] 其 ∨ ∧ ∧ ∨ 大于等于1,A 中n大于等于 ij(j=1, …,ki ,i=1,2,3,…,m)为原子谓词公 大于等于 为原子谓词公 式或其否定,□ 量词?或量词? ， ） 式或其否定 □为量词?或量词?， xi（i=1，… n）为客 体变元. 体变元 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 任何一个谓词公式A， 任何一个谓词公式 ，如果具有如下形式则称为 前束析取范式： 前束析取范式：(□x1) (□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨ □ □ □ ∧ ∨ (A21∧A22∧…∧A2k2 )∨…∨(Am1∧Am2∧…∧Amkm)] ∧ ∨ ∨ ∧其中n大于等于 其中 大于等于1,Aij(j=1, …,ki ,i=1,2,3,…,m)为原子 大于等于 为原子 谓词公式或其否定,□ 量词?或量词? 谓词公式或其否定 □为量词?或量词?，xi （i=1，… n）为客体变元. ， ） 客体变元 定理2.6.2:每一个谓词公式都可以转化为与其等 定理 每一个谓词公式都可以转化为与其等 价的前束析(合 取范式 取范式. 价的前束析 合)取范式 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 例2:求下列公式的前束析取范式和前束合取范式. 2:求下列公式的前束析取范式和前束合取范式. 求下列公式的前束析取范式和前束合取范式(1) ((?x) F ( x, y ) → (?y )G ( y )) → (?x) H ( x, y ) (2) ?(?x){(?y ) A( x, y ) → (?x)(?y )[ B( x, y ) ∧ (?y )( A( y, x) → B ( x, y ))]}解:计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2. 5 前束范式(Prenex Normal Form) ) 小结：本节介绍了谓词公式的前束范式、 小结：本节介绍了谓词公式的前束范式、前束 谓词公式的前束范式 析取范式和前束合取范式 重点掌握前束 范式和前束合取范式. 前束析取 析取范式和前束合取范式.重点掌握前束析取 范式和前束合取范式求法。 合取范式求法 范式和前束合取范式求法。 作业: 作业: P53 (2),(4)计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 2.6 谓词演算的推理理论(Inference theory of predicate calculus) 2.6.1 推理规则 推理规则(Rules of inference) ) 2.6.2 证明举例 (Examples of proof) )计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论2.6.1推理规则 推理规则(Rules of inference) )在谓词演算中， 在谓词演算中，推理的形式结构仍为 H1∧H2∧H3∧....∧Hn?C ∧若 H1∧H2∧H3∧....∧Hn→C是永真式，则称由前提 是永真式， ∧H1,H2,H3,.…,Hn逻辑的推出结论 ，但在谓词逻 逻辑的推出结论C， 辑中, 均为谓词公式。 辑中 H1,H2,H3,.…,Hn , C均为谓词公式。 均为谓词公式命题演算中的推理规则，可在谓词推理理论中应用。 命题演算中的推理规则，可在谓词推理理论中应用。 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 与量词有关的四条重要推理规则： 与量词有关的四条重要推理规则： 四条重要推理规则 1、全称指定规则（US规则） 规则） 、全称指定规则（ 规则 2、全称推广规则（UG规则） 规则） 、全称推广规则（ 规则 3、存在指定规则（ES规则） 规则） 、存在指定规则（ 规则 4、存在推广规则（EG规则） 规则） 、存在推广规则（ 规则 注意：只能对前束范式适用上述规则。 注意：只能对前束范式适用上述规则。计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 1. 全称指定规则（ US ）： 全称指定规则（ ?x P(x) ∴P(c) 使用此规则时要注意： 使用此规则时要注意： 中的自由变元； （1）x是P(x)中的自由变元； ） 是 中的自由变元 是论域中的某个任意的客体. （2）c是论域中的某个任意的客体 ） 是论域中的某个任意的客体计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 2.全称推广规则（UG）： 全称推广规则（ ） 全称推广规则 P(y) P(x) ∴ ?x P使用此规则时注意: 使用此规则时注意 (1) y在P(y)中自由出现，且y取任何值时 均为真。 中自由出现， 取任何值时P均为真 在 中自由出现 取任何值时 均为真。 (2) x不在 不在P(y)中约束出现 中约束出现. 不在 中约束出现计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 3.存在指定规则 存在指定规则(ES): 存在指定规则?x P(x)∴ P(c) 是论域中的某些客体,c ,c并不是任意的 注:c是论域中的某些客体,c并不是任意的 使用此规则时应注意： 使用此规则时应注意： c是使 为真的特定客体； 是使P为真的特定客体 是使 为真的特定客体；计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 (4)存在推广规则(EG): (4)存在推广规则(EG): 存在推广规则 P(c) ∴ ?x P(x) 使用此规则时注意: 使用此规则时注意 (1) (2)C是个体域中某个确定的个体。 是个体域中某个确定的个体。 是个体域中某个确定的个体 代替C的 不能已在 不能已在P(c)中出现。 中出现。 代替 的x不能已在 中出现计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 2.6.2证明举例 (Examples of proof) ) 证明举例 证明苏格拉底三段论:凡是人都是要死的 例 1证明苏格拉底三段论 凡是人都是要死的 。 苏 证明苏格拉底三段论 凡是人都是要死的。 格拉底是人。苏格拉底是要死的。 格拉底是人。苏格拉底是要死的。 是人。 是要死的。 苏格拉底 苏格拉底。 设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。 是人 前提： 则 前提：?x(M(x)→D(x))，M(a）. → ， ） 结论： 结论： D(a) . 证明： 证明：① ?x (M(x)→D(x)) P → US ① ② M(a)→D(a) → P ③ M(a) T② ③ I11 ④ D(a) ② (直接证法 直接证法) 直接证法 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 例2:前提：?x(F(x)∨G(x))， ┐?x G(x). 前提： ∨ ， 前提 结论： 结论： ?x F(x) . 证明： P 证明：① ┐?x G(x) T① 置换规则 ② ?x ┐G(x) ① US ② ③ ┐G(a) ④ ?x(F(x)∨G(x)) P ∨ US ④ ⑤ F(a)∨G(a) ∨ T③ ⑤ ⑥ F(a) ③ EG ⑥ ⑦ ?x F(x) 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论前提： 例3:前提： ?x (A(x)→B(x))， ?x A(x) 前提 → ， 结论： 结论： ?x B(x) P前提引入 证明：① ?x A(x) 前提引入② A(c) ③ ?x (A(x)→B(x)) → ④ A(c)→B(c) → ⑤ B(c) ES ①P前提引入 US ③T② ④ ②EG ⑤ ⑥ ?x B(x) 注意： 引入的顺序不可更改！ 注意： ① ③引入的顺序不可更改！ 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论x(┐R(x)∨┐ 例 4: 前 提 ： ? x(F(x)∨G(x)), ?x(┐R(x)∨┐G(x)), R(x). ?x R(x). 归谬法) 结论： 结论： ?x F(x) .(归谬法) 证明： 证明：① ┐?x F(x) P结论否定引入 ② ?x ┐F(x) T① ③ ┐F(a) ES ② ④ ?x(F(x)∨G(x)) P ⑤ F(a)∨G(a) US ④ ⑥ G(a) (a) T ③⑤计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 ⑦ ?x(┐R(x)∨┐G(x)) ∨ ⑧ ┐R(a)∨┐G(a)) ∨ ⑨ ┐R(a) ⑩?x R(x) (11) R(a) (12) ┐R(a)∧R(a) ∧ P US ⑦ T⑥ ⑧ ⑥ P US ⑩ 矛盾式计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论例5:证明 ?x(P(x)∨Q(x))=&┐(?x)P(x)→(?x)Q(x) 证明: ∨ ? → 证明 (附加前提法 附加前提法) 附加前提法证明：(1) ┐(?x)P(x) 证明： ? (2) (?x)┐P(x)(3) ┐P(c) (4) ?x(P(x)∨Q(x)) ∨ (5) P(c)∨Q(c) ∨P(附加前提 附加前提) 附加前提 T(1)ES(2) P US(4)计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）2.6 谓词演算的推理理论 (6) Q(c) (7)(?x)Q(x) (8) ?(?x)P(x) →(?x)Q(x) ? T(3)(5) EG(6) CP小结：本节介绍了谓词演算的推理规则 并举例说 小结：本节介绍了谓词演算的推理规则,并举例说 明了它们的应用. 重点:深刻理解四个推理规则 明了它们的应用 重点 深刻理解四个推理规则, 深刻理解四个推理规则 会应用它们推理证明. 会应用它们推理证明 作业: 作业 P58 2(1),(4)；3 ； 计算机科学与技术学院第二章 谓词逻辑（Predicate Logic） Logic）结束谢 谢! 计算机科学与技术学院
《离散数学及其应用》魏雪丽第2章 谓词逻辑——为大家提供各种日常写作指导，同时提供范文参考。主要栏目有：范文大全、个人简历、教案下载、课件中心、 优秀作文、考试辅导、试题库、诗词鉴赏。
相关文档：
下载文档：
搜索更多：
All rights reserved Powered by
copyright &copyright 。甜梦文库内容来自网络，如有侵犯请联系客服。|}