离散数学-谓词逻辑-1-

第2章 谓词逻辑 ¾ 谓词的概念与 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 ¾ 命题函数与量词 ¾ 谓词公式与翻译 ¾ 变元的约束 ¾ 谓词演算的等价式和蕴含式 ¾ 前束范式 ¾ 谓词演算的推理理论 2-1 谓词的概念与表示 例1 考察如下推理： 凡有理数都是实数。 2/7是有理数， 所以，2/7是实数。 直观上看这样的推理应该是正确的。然而在命题逻辑里 就不能描述这种推理，设这三个命题分别以p, q, r表示，相 应的推理形式为： (p∧q)→r 由于对任意的p,q,r来说这推理形式并非重言式,也就是 说这个推理形式不是正确的。对这样的人们熟知的推理关系 在命题逻辑中得不到正确的描述,自然是命题逻辑的局限性。 2-1 谓词的概念与表示 例2 张三是学生。 李四是学生。 ¾ 在命题逻辑里，这是两个不同的命题，只能分别以两个 不同的符号如p、q表示了。 ¾ 这两个命题的共同点，它们都有主词（客体）和谓词， 不同的是主词“张三”和“李四”，而谓词“是学生” 是相同的。 ¾ 若以大写符号P表示“是学生”，这样两个命题的共同 性就可由P来体现出来了，这两个命题可以分别写成 P(张三)和 P(李四) 2-1 谓词的概念与表示 ¾ 一般地可引入变量x来表示主词，于是符号P(x) 就表示“x是学生”。通常把P(x)称作谓词。 ¾ 在一个命题里，如果主词只有一个，这时表示该 主词性质或属性的词便称为谓词。这是一元(目) 谓词，以P(x), Q(x)…表示。 ¾ 在一个命题里，如果主词多于一个，那么表示这 几个主词间的关系的词称作谓词。这是多元谓 词，以P(x,y),Q(x,y),R(x,y,z),…表示。 2-1 谓词的概念与表示 例3 “张三和李四是兄弟”。 其中“是兄弟”是谓词。 “5大于3”。 其中“大于”是谓词。 “张三比李四高”。 其中“比…高”是谓词。 “天津位于北京的东南”。其中“位于…东南”是谓词。 “A在B上”。 其中“在…上”是谓词。 2-2 命题函数（变项）、函数与量词 ¾ 在数理逻辑中，不使用主词（客体）这个词， 习惯称为个体词。 ¾ P（张三）中的张三是个体词或称个体常项。而 谓词P(x)中的变量x为个体变项或个体变元。 ¾ 有n个个体的谓词P(x1, …, xn)称n项（目、元） 谓词。 ¾ 如果P是已赋有确定含义的谓词，就称为谓词常 项，而P表任一谓词时，就称为谓词变项。 2-2 命题函数（变项）、函数与量词 ¾ 将个体变项的变化范围称为个体域或论域，以D 表示。并约定谓词逻辑的个体域除明确指明 外，都认为是包括一切事物的一个最广的集 合，称为全总论域 。 论域是重要的概念，同一谓词在不同论域 下的描述形式可能不同，所取的真假值也可能 不同。 命题函数（变项） ¾ 一般说来，谓词P(x),Q(x,y)是命题形式而不是命题。 因为这里没有指定谓词符号P,Q的含义，即它们是谓词 变项，再者，个体词x,y也是个体变项。从而不可能确 定P(x),Q(x,y)的真值是取真还是取假。仅当谓词变项 取定为某个谓词常项，并且个体词取定为个体常项时， 命题形式才化为命题。如P(x)表示x是有理数，那么P(3) 是命题，真值为T，Q(x,y)表示x大于y，那么Q(2,3)是 命题，真值为F。 ¾ 谓词的真值依赖于个体变元的论域。 函数 ¾在谓词逻辑中出现变量, 自然也会考虑引入函 数。表示某个体域（不必是实数）到另一个体 域的映射。 例1 函数father(x)表x的父亲，若P(x)表x是教 师， 则P(father(x))就表示x的父亲是教师。 当x的取值确定后，P(father (x))的值或为真 或为假。 函数 例2 “张三的父亲和母亲是夫妻”可描述成: MARRIED(father (张三), mother(张三)) 其中谓词MARRIED(x, y)表示x和y是夫妻, 而 father(x)、mother(x)是函数。 ¾约定函数符号用小写字母表示，如f, g, father, …。这不会与以小写字母表示的命题 相混的。 量词 ¾ 全称量词：符号 ∀ 称为全称量词符，∀x称为全称量 词，称x为指导变元，用来表达“对所有的”、“每一 个”、“对任何一个”、“一切”等词语。 ¾ 存在量词：符号 ∃ 称为存在量词符，∃x称为存在量 词，x称为指导变元，用来表达“存在一些”、 至少有 一个”、“对于一些”、“某个”等词语。 ¾ 存在惟一量词：符号 ∃! 称为存在惟一量词符， ∃!x称 为存在惟一量词，称x为指导变元，用来表达“恰有一 个”、“存在惟一”等词语。 用量词、谓词表示下列命题 例3 ① 所有大学生都热爱祖国；② 每个自然数都是实数； ③ 一些大学生有远大理想；④ 有的自然数是素数。 解：令 S(x):x是大学生；L(x):x热爱祖国； N(x):x是自然数； R(x):x是实数； I(x):x有远大理想；P(x):x是素数。 则 ① (∀x)L(x)//论域为大学生集合；(∀x)(S(x)→L(x))//全总论域 采用一个谓词如P(x)来限制个体变元x的取值范围，并把P(x)称 为特性谓词。 ② (∀x)R(x)//论域为实数集合； (∀x)(N(x)→R(x))//全总论域 ③ (∃x)I(x)//论域为大学生集合；(∃x)(S(x)∧I(x))//全总论域 ④ (∃x)P(x)//论域为自然数集合；(∃x)(N(x)∧P(x))//全总论域 谓词与量词的关系 ¾量词与特性谓词的搭配还有一定规律，即全称量词 后跟一个条件式，而特性谓词作为其前件出现；存 在量词后跟一个合取式，特性谓词作为一个合取项 出现。 ¾谓词前加上了量词，称为谓词的量化。若一个谓词 中所有个体变元都量化了，则该谓词就变成了命题。 这是因为在谓词被量化后，可以在整个个体域 中考 中考数学全套课件中考心理辅导讲座中考语文病句辨析修改中考语文古诗文必背中考单选题精选 虑命题的真值了。 2-3 谓词公式 ¾ 项的定义：项由下列规则形成： ①个体常元和个体变元是项； ②若f是n元函数，且t1,…,tn是项，则f(t1,…,tn)是 项； ③所有项都是有限次的使用①和②生成。 有了项的定义，函数就可用来表示个体常元和个体变元。 ¾ 原子公式的定义：若P(x1,…,xn)是n元谓词，t1,…,tn是 项，则称P(t1,…,tn)为原子谓词公式，简称原子公式。 合式谓词公式的归纳定义 合式谓词公式当且仅当由下列规则形成的符号串： ① 原子公式是合式谓词公式； ② 若A是合式谓词公式，则(┐A)是合式谓词公式； ③ 若A，B是合式谓词公式，则(A∧B)，(A∨B)，(A→B)和 (A ↔ B)都是合式谓词公式； ④ 若A是合式谓词公式，x是个体变元，则(∀x)A、(∃x)A 都是合式谓词公式； ⑤ 仅有有限项次使用①、②、③和④形成的才是合式谓词 公式。 说明 ¾ 由定义可知，合式谓词公式是按上述规则由原子公式、 联结词、量词、圆括号和逗号所组成的符号串，而且命 题公式是它的一个特例。 ¾ 以后为使用方便，称合式谓词公式为谓词公式；在不引 起混淆时，甚至可将合式谓词公式的括号同样省略，其 规则与命题公式的括号省略相同，即最外层括号可省略。 但是，量词后面的括号是不能省略的。 2-4 约束变元与自由变元 ¾ 给定一个谓词公式A，其中有一部分公式形如(∀x)B(x)或 (∃x)B(x)，则称它为A的x约束部分，称B(x)为相应量词的作用 域或辖域。在辖域中，x的所有出现称为约束出现，x称为约束 变元；B中不是约束出现的其它个体变元的出现称为自由出 现，这些个体变元称自由变元。 ¾ 确定一个量词的辖域即是找出位于该量词之后的相邻接的子公 式，具体地讲： ① 若量词后有括号,则括号内的子公式就是该量词的辖域； ② 若量词后无括号,则与量词邻接的子公式为该量词的辖域。 ¾ 判定给定公式A中个体变元是约束变元还是自由变元，就是要 看它在A中是约束出现，还是自由出现。 实例 例1 指出下列公式中的量词辖域、个体变元的约束出现和自 由出现。 ① (∀x)(P(x)→(∃y)Q(x,y)) ② (∃x)H(x)∧L(x,y) ③ (∀x)(∀y)(P(x,y)∨Q(y,z))∧(∃x)R(x,y) 解:① x的辖域为:(P(x)→(∃y)Q(x,y)),y的辖域 为:Q(x,y),x和y都是约束出现。 ② x是约束出现,又是自由出现,约束出现的x辖域 为:H(x),y是约束出现。 ③ x是约束出现,(∀x)的辖域 为:(∀y)(P(x,y)∨Q(y,z)),(∃x)的辖域为:R(x,y),y是 约束出现,又是自由出现,y的辖域为: (P(x,y)∨Q(y,z)) 闭式 ¾ 设A为任意一个公式，若A中无自由出现的个体变元，则 称A为封闭的合式公式，简称闭式。若A中没有约束变元 出现，则称A为开放公式，简称开式。 由闭式定义可知，闭式中所有个体变元均为约束出现。 例2 (∀x)(P(x)→Q(x))和(∃x)(∀y)(P(x)∨Q(x,y))是闭式。 公式P(x)→Q(x,y)和L(x,y,z)是开式。 而公式(∀x)(P(x)→Q(x,y))既不是闭式，也不是开式。 改名规则、代入规则 ¾ 在一公式中，有的个体变元既可以是约束出现，又可以 是自由出现，这就容易产生混淆。为了避免混淆，采用 下面两个规则： ① 约束变元改名规则，将量词辖域中某个约束出现的个体 变元及相应指导变元，改成本辖域中未曾出现过的个体 变元，其余不变。改名后的公式与原公式等价。 ② 自由变元代入规则，对某自由出现的个体变元可用个体 常元或用与原子公式中所有个体变元不同的个体变元去 代入，且处处代入。 改名规则、代入规则 例3 将公式(∀x)(P(x)→Q(x，y))∧R(x，y)中的 约束变元改名。 解： (∀z)(P(z)→Q(z，y))∧R(x，y) 例4 对公式(∀x)(P(y)→Q(x，y))∧R(x，y)中的 自由变元代入。 解： (∀x)(P(y)→Q(x，y))∧R(c，y) 改名与代入规则的异同 ¾ 改名规则与代入规则的共同点都是不能改变约束关系,而不 同点是： ①施行的对象不同。改名是对约束变元施行,代入是对自由变 元施行。 ②施行的范围不同。改名可以只对公式中一个量词及其辖域 内施行,即只对公式的一个子公式施行；而代入必须对整个 公式同一个自由变元的所有自由出现同时施行,即必须对整 个公式施行。 ③施行后的结果不同。改名后,公式含义不变,因为约束变元 只改名为另一个个体变元,约束关系不改变。约束变元不能 改名为个体常元；代入,不仅可用另一个个体变元进行代入, 并且也可用个体常元去代入,从而使公式由具有普遍意义变 为仅对该个体常元有意义,即公式的含义改变了。 自然语句的形式化（翻译） ¾ 使用计算机来处理由自然语句或非形式化陈述的问题，首 要的是工作是问题本身的形式描述。 ¾ 命题逻辑的表达问题的能力,仅限于联结词的使用。而谓 词逻辑由于变元、谓词、量词和函数的引入具有强得多的 表达问题的能力,已成为描述计算机所处理的知识的有力 工具。人工智能学科将谓词逻辑看作是一种基本的知识表 示方法和推理方法。 ¾ 使用谓词逻辑描述以自然语句表达的问题，首先要将问题 分解成一些原子谓词，引入谓词符号，进而使用量词、函 数、联结词来构成合式公式。这种形式描述是进行推理的 先决条件，所以十分重要。 自然语句的形式化 例1 “所有的有理数都是实数”的形式化。 其意思是说，对任一事物而言，如果它是有理数，那么它是 实数。即对任一x而言，如果x是有理数，那么x是实数。设， P(x)：x是有理数，Q(x)：x是实数， 这句话的形式描述应为：(∀x)(P(x)→Q(x)) 因为x的论域是一切事物的集合, 所以x是有理数是一个条件。 ¾ 需注意的是这句话不能形式化为：(∀x)(P(x)∧Q(x)) 这公式的意思是说，对所有的x，x是有理数而且又是实数。 P(x) Q(x) 论域 P(x) Q(x) 论域 自然语句的形式化 例2 “有的实数是有理数”的形式化 意思是说，存在一事物它是实数，而且是有理数。即有 一个x，x是实数并且是有理数。设： P(x)：x是有理数，Q(x)：x是实数， 这句话的形式描述应为 (∃x)(P(x)∧Q(x)) P(x) Q(x) 论域 自然语句的形式化 例3 “没有无理数是有理数”的形式化 这句话有否定词，意思是不存在无理数是有理数，即不 存在x，x是无理数，又是有理数。设： A(x)：x是无理数，B(x)：x是有理数。 这句话的形式描述为： ┐(∃x)(A(x)∧B(x)) 这句话还可以表述为，对任一x而言，如果x是无理数， 那么x不是有理数。即可以形式描述为： (∀x)(A(x) → ┐B(x)) 同理有：(∀x)(B(x) → ┐A(x)) 自然语句的形式化 例4 “有的实数不是有理数”的形式化 意思是有的x，它是实数而且不是有理数。 A(x)：x是实数，B(x)：x是有理数， 那么这句话可形式描述为： (∃x)(A(x)∧┐B(x)) 自然语句的形式化 例5 论域是自然数集，来形式化下列语句： ① 对每个数, 有且仅有一个相继后元。 ② 没有这样的数, 0是其相继后元。 ③ 对除0而外的数, 有且仅有一个相继前元。 解：设谓词E(x,y)：x=y, 函数f(x):个体x的相继后元, 即f(x)=x+1。 函数g(x):个体x的相继前元，即g(x)=x-1。 则 ① (∀x)(∃!y)E(y,f(x)) ② ┐(∃x)E(0,f(x)) ③ (∀x)(┐E(x,0) → (∃!y)E(y,g(x))) 存在唯一 注： ① (∀x)(∃!y)E(y,f(x)) ③ (∀x)(┐E(x,0) → (∃!y)E(y,g(x))) 因为，(∃!x)P(x)⇔(∃x)(P(x)∧(∀y)(P(y) → x=y)) 所以， ①和③又可以表示为: ①(∀x)(∃y)(E(y,f(x))∧(∀z)(E(z,f(x))→E(y,z))) ③(∀x)(┐E(x,0)→(∃y)(E(y,g(x))∧(∀z)(E(z,g(x)) →E(y,z)))) 自然语句的形式化 例6 “存在最小的自然数”。 解1: 设: F(x):x是自然数; G(x,y):x≤y; 原命题符号化成: (∃x)(F(x)∧∀y(F(y)→G(x,y))) 解2: 采用全体自然数作为个体域. 设: G(x,y):x