一阶逻辑基本概念ppt.ppt

第4章一阶逻辑基本概念 离散数学 本章说明 本章的主要内容一阶逻辑基本概念 命题符号化一阶逻辑公式 解释及分类本章与后续各章的关系克服命题逻辑的局限性是第五章的先行准备 命题逻辑的缺陷 把命题看成是一个个孤立的命题 忽略了命题之间的联系 不能反映某些重要的常见的逻辑思维过程 1 繁琐例 表述集合个体性质及相互关系S 1 2 50 表述S中所有元素都大于3这样一个性质 需要1 3 2 3 50 3等50个命题 2 不能描述命题间的逻辑联系例如 逻辑学中著名的苏格拉底三段论 P 所有人必死Q 苏格拉底是人R 苏格拉底必死表示为命题逻辑 应该有 P Q R 也就是公式 P Q R应该是恒真的 显然该公式不是恒真的 解释 P Q R 就能弄假该公式 原因 命题R和命题P Q是有内在关系的 只是这种关系在命题逻辑中无法表示 因此 需要对命题的成分 结构和命题间的共同特性等作进一步的分析 分析出个体词 谓词和量词 以期达到表达出个体与总体的内在联系和数量关系 这正是谓词逻辑所要研究的问题 本章内容 4 1一阶逻辑命题符号化4 2一阶逻辑公式及解释本章小结习题作业 4 1一阶逻辑命题符号化 一阶逻辑命题符号化的三个基本要素个体词谓词量词 个体词及相关概念 个体词一般是充当陈述句主语的名词或代词 说明 个体词 指所研究对象中可以独立存在的具体或抽象的客体 举例命题 电子计算机是科学技术的工具 个体词 电子计算机 命题 他是三好学生 个体词 他 心物一元or心物二元 量子力学中的测不准原理 个体常项 表示具体或特定的客体的个体词 用小写字母a b c 表示 个体变项 表示抽象或泛指的客体的个体词 用x y z 表示 个体域 或称论域 指个体变项的取值范围 可以是有穷集合 如 a b c 1 2 可以是无穷集合 如N Z R 全总个体域 universe 由宇宙间一切事物组成 个体词及相关概念 本教材在论述或推理中 如果没有指明所采用的个体域 都是使用的全总个体域 说明 谓词及相关概念 谓词 predicate 是用来刻画个体词性质及个体词之间相互关系的词 1 是无理数 是个体常项 是无理数 是谓词 记为F 命题符号化为F 2 x是有理数 x是个体变项 是有理数 是谓词 记为G 命题符号化为G x 3 小王与小李同岁 小王 小李都是个体常项 与 同岁 是谓词 记为H 命题符号化为H a b 其中a 小王 b 小李 4 x与y具有关系L x y都是个体变项 谓词为L 命题符号化为L x y 谓词常项 表示具体性质或关系的谓词 用大写字母表示 如 1 2 3 中谓词F G H 谓词变项 表示抽象的 泛指的性质或关系的谓词 用大写字母表示 如 4 中谓词L n n 1 元谓词 P x1 x2 xn 表示含n个个体变项的n元谓词 n 1时 一元谓词 表示x1具有性质P n 2时 多元谓词 表示x1 x2 xn具有关系P 0元谓词 不含个体变项的谓词 如F a G a b P a1 a2 an 若F G P为谓词常项 则上述0元谓词为命题常项 若F G P为谓词变项 则为命题变项 n元谓词是命题吗 不是 只有用谓词常项取代P 用个体常项取代x1 x2 xn时 才能使n元谓词变为命题 思考 谓词及相关概念 谓词的形式化定义 设D是非空个体名称集合 定义在Dn上取值于 0 1 上的n元函数 称为n元命题函数或n元谓词 其中Dn表示集合D的n次笛卡尔乘积 例 令G x y x高于y G x y 是一个二元谓词 将x代以个体 张三 y代以个体 李四 则G 张三 李四 就是命题 张三高于李四 G x y 不是命题 而是一个命题函数即谓词 将x y代以任意确定的个体 由G x y 都能得到一个命题 D 2 3 4 设P x x大于3 则P x 为一元谓词 指定元素 命题 P 2 0 P 3 0 P 4 1设P x y x大于y 则P x y 为二元谓词 指定元素 命题 P 2 3 0 P 4 2 1设P x y z 若x y 1 z 则P x y z 为1 否则为0 则P x y z 为三元谓词 指定元素 命题 P 2 3 4 1 P 4 2 2 0 例题 例题 将命题 这只大红书柜摆满了那些古书 符号化 1 设F x y x摆满了y R x x是大红书柜Q y y是古书 a 这个书柜b 那些书符号化为 R a Q b F a b 2 设A x x是书柜 B x x是大的C x x是红的 D y y是古老的E y y是图书 F x y x摆满了ya 这个东西b 那些东西符号化为 A a B a C a D b E b F a b 用谓词的概念可将苏格拉底三段论做如下的符号化 令H x 表示 x是人 M x 表示 x必死 则三段论的三个命题表示如下 P H x M x Q H 苏格拉底 R M 苏格拉底 现在可以将苏格拉底三段论符号化为 令命题P為 所有人都会死 其否定命題為 P H x M x H x M x H x M x 亦即 命题P 所有人都会死 的否定命题是 所有人都不會死 这和人们对命题 所有人都必死 的否定的理解並不一致 但问题是 原因 命题P的确切意思应该是 对任意x 如果x是人 则x必死 但是H x M x 中并没有确切的表示出 对任意x 这个意思 因此 在谓词逻辑中除引进谓词外 还需要引进 对任意x 这个语句 及其对偶的语句 存在一个x 量词 quantifier 是表示个体常项或个体变项数量屬性的词 1 全称量词 符号化为 All 日常生活和数学中所用的 一切的 所有的 每一个 任意的 凡 都 等词可统称为全称量词 x表示个体域里的某個个体 xF x 表示个体域里所有个体都有性质F 2 存在量词 符号化为 Exist 日常生活和数学中所用的 存在 有一个 有的 至少有一个 等词统称为存在量词 y表示个体域里某個个体 yG y 表示个体域里存在个体y具有性质G 量词及相关概念 引入谓词后 命题P就可确切地符号化如下 x H x M x 命题P的否定命题为 P x H x M x x H x M x 亦即 至少有一个人是不死的 这个命题才是 所有人都要死 的否定 三段论的三个命题 在谓词逻辑中可以如下表示 P x H x M x Q H 苏格拉底 R M 苏格拉底 以后可以证明 在谓词逻辑中 R是P和Q的逻辑结果 例符号化下述命题 1 所有的老虎都要吃人 2 每一个大学生都会说英语 3 所有的人都长着黑头发 4 有一些人登上过月球 5 有一些自然数是素数 解设有如下谓词 P x x会吃人 Q x x会说英语 R x x长着黑头发 S x x登上过月球 T x x是素数 1 x P x x 老虎 2 x Q x x 大学生 3 x R x x 人 4 x S x x 人 5 x T x x 自然数 不便之处 1 从书写上十分不便 总要特别注明个体域 2 在同一个比较复杂的句子中 不同命题函数中的个体可能属于不同的个体域 此时无法清晰表达 如例 1 和 4 的合取 x P x x R x x 人 x 老虎 不便之处 续 3 若个体域的注明不清楚 将造成无法确定命题真值 即对于同一个n元谓词 不同的个体域有可能带来不同的真值 例如对于语句 x x 6 5 可表示为 有一些x 使得x 6 5 该语句在下面两种个体域下有不同的真值 a 在实数范围内时 确有x 1使得x 6 5 因此 x x 6 5 为 真 b 在正整数范围内时 则找不到任何x 使得x 6 5为 真 所以 x x 6 5 为 假 不便之处的根源 因为需要特别标注每个谓词的个体域 特性谓词 新的问题出现了 U x 如何与 x P x x S x 结合才符合逻辑呢 例将下面两个命题符号化 1 所有的老虎都会吃人 2 有些人登上过月球 特性谓词的使用 1 令P x x会吃人U x x是老虎则符号化的正确形式应该是 x U x P x 它的含义