离散数学及其应用-屈婉玲-第四章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 主要内容 一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化 一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式 第四章 一阶逻辑基本概念 * 4.1 一阶逻辑命题符号化 个体词——所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事务，用a, b, c等表示 个体变项：抽象的事物，用x, y, z等表示 个体域(论域)——个体变项的取值范围 有限个体域，如 {a, b, c}, {1, 2} 无限个体域，如 N, Z, R, … 全总个体域——由宇宙间一切事物组成 * 谓词 谓词——表示个体词性质或相互之间关系的词 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F n(n?1)元谓词 一元谓词(n=1)——表示性质 多元谓词(n?2)——表示事物之间的关系 如, L(x,y)：x与 y 有关系 L，L(x,y)：x?y，… 0元谓词——不含个体变项的谓词, 即命题常项 或命题变项 * 量词 量词——表示数量的词 全称量词?: 表示所有的 ?x : 对个体域中所有的x 如, ?xF(x)表示个体域中所有的x具有性质F ?x?yG(x,y)表示个体域中所有的x和y有关系G 存在量词?: 表示存在, 有一个 ?x : 个体域中有一个x 如, ?xF(x)表示个体域中有一个x具有性质F ?x?yG(x,y)表示个体域中存在x和y有关系G ?x?yG(x,y)表示对个体域中每一个x都存在一个y使得 x和y有关系G ?x?yG(x,y)表示个体域中存在一个x使得对每一个y, x和y有关系G * 实例1 例1 用0元谓词将命题符号化 (1) 墨西哥位于南美洲 (2) 是无理数仅当 是有理数 (3) 如果23，则34 解：在命题逻辑中： (1) p, p为墨西哥位于南美洲（真命题） (2) p→q, 其中, p： 是无理数, q： 是有理数. 是假命题 (3) p?q, 其中, p：23, q：34. 是真命题 * 实例1解答 在一阶逻辑中： (1) F(a)，其中，a：墨西哥，F(x)：x位于南美洲. (2) F( )?G( ), 其中，F(x)：x是无理数，G(x)：x是有理数 (3) F(2, 3)?G(3, 4)，其中，F(x, y)：xy，G(x, y)：xy 实例2 例 2 在一阶逻辑中将下面命题符号化 (1) 人都爱美 (2) 有人用左手写字 个体域分别为 (a) D为人类集合 (b) D为全总个体域 解 (a) (1) ?xG(x), G(x)：x爱美 (2) ?xH(x), H(x)：x用左手写字 (b) F(x)：x为人 (1) ?x(F(x)?G(x)) (2) ?x(F(x)?H(x)) 说明: 1. 引入特性谓词F(x) 2. (1),(2)是一阶逻辑中的两个“基本”公式 * 实例3 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解 注意：题目中没给个体域，一律用全总个体域 (1) 令F(x)：x为正数，G(y)：y为负数, L(x,y)：xy ?x(F(x)??y(G(y)?L(x,y))) 或者 ?x?y(F(x)?G(y)?L(x,y)) (2) 令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xy ?