1、离散数学数理逻辑2/26第四章 一阶逻辑基本概念n 一阶逻辑命题符号化n 一阶逻辑公式及解释3/26一阶逻辑的引入n 在命题逻辑中 , 命题是最基本的单位 , 对简单命题不再进行分解 , 不关心命题中个体与总体的内在联系和数量关系 . 这就使得它难以描述和证明一些常见的推理 . 因此 , 需要对命题进行细化 , 建立更为精细的逻辑推理体系 .n 例如 : 逻辑学中著名的三段论 :n 凡偶数都能被 2整除 . 6是偶数 . 所以 , 6能被 2整除 .这个推理是数学中的真命题 , 是正确的 , 但在命题逻辑中却无法判断其正确性 , 用 p,q,r分别表示以上三个命题 .则得到推理的形式结构为 :
2、(p q)r由于上式不是重言式 , 因而不能由它判断推理的正确性 . 原因在于各命题的 内在联系 没有表示出来 .n 为了克服命题逻辑的局限性 , 应该将原子命题再细分 , 分析出个体词 , 谓词和量词 , 以便达到表达出命题的内在联系和命题之间的逻辑关系 . 这就是一阶逻辑所研究的内容 .4/264.1 一阶逻辑命题符号化n 谓词逻辑命题符号化的三个基本要素 : 个体词 , 谓词 , 量词 .1. 个体词 : 研究对象中可以独立存在的 具体的或抽象的 客体 .例如 : 小王 , 小张 , 马列主义 , 3, 北京等都可做为个体词 .注 : (1) 表示 具体或特定 客体的个体词称为 个体常项
3、 , 一般用小写字母 a, b, c, 表示 ;(2)表示 抽象或泛指 的个体词称为 个体变项 , 一般用小写字母 x, y, z, 表示 .个体变项的 取值范围 称为 个体域 (或论域 ). 个体域可以是有限集合 , 如 1,2,3或 a,b,c, 也可以是无限集合 , 如自然数集合N或实数集合 R. 由宇宙间一切事物组成的个体域称为 全总个体域 .5/26谓词2. 谓词 : 用来刻划个体词的性质或个体词之间相互关系的词 .例如 : (1) 在命题 “是无理数 ”中 , “ 是无理数 ”是谓词 .(2) 在命题 “x 是有理数 ”中 , “ 是有理数 ”是谓词 .(3) 在命题 “小王与小李
4、同岁 ”中 , “ 与 同岁 ”是谓词 .(4) 在命题 “x与 y具有关系 L”中 , “ 与 具有关系 L”是谓词 .注 常用大写字母 F, G, H 等来表示谓词 . 表示 具体 性质或关系的谓词称为 谓词常项 ;表示 抽象或泛指 的性质或关系的谓词称为 谓词变项 . F(a): 表示个体常项 a具有性质 F (F是谓词常项或变项 ); F(x): 表示个体变项 x具有性质 F (F同上 );F(a,b): 表示个体常项 a, b具有关系 F (同上 );F(x,y): 表示个体变项 x, y具有关系 F (同上 ) .一般地 , 用 P(x1,x2,x n)表示含 n(n1)个个体变项
5、 x1,x2, xn 的 n元谓词 . 它可看成以个体域为定义域 , 以 0,1为值域的 n元函数关系 .当 P取常项 , 且 (x1,x2, xn)取定常项 (a1,a2, an)时 , P(a1,a2, an)是一个命题 .6/26谓词续 不含 个体变项的谓词称为 0元谓词 .例如 F(a), G(a,b), P(a1,a2,a n)等 . 当 F, G, P等为谓词常项时 , 0元谓词即为命题 . 因此 , 命题可看作特殊的谓词 .例 用 0元谓词将下列命题符号化 , 并讨论它们的真值 .(1) 只有当 2是素数时 , 4才是素数 ;(2) 如果 5大于 4, 则 4大于 6.解 (1)
6、 设一元谓词 F(x): x是素数 ; 个体常项 : a: 2； b: 4.则命题可符号化 : F(b) F(a).因为该蕴含式前件为假 , 故命题为真 .(2) 设二元谓词 G(x,y): x大于 y. 个体常项 : a: 4; b: 5; c: 6.则命题可符号化为 : G(b,a) G(a,c).由于 G(b,a)为真 , 而 G(a,c)为假 , 故命题为假 .7/26量词的引入n 有了个体词和谓词的概念之后 , 有些命题还是不能准确地符号化 .以前面所讨论的三段论为例 :令 P(x): x是偶数 . S(x) : x能被 2整除 . a: 6.符号化为 : (1) P(x) S(x)
7、 (2)P(a) (3)S(a)我们知道 , “凡偶数都能被 2整除 .”是一个真命题 , 而 “P(x) S(x)” 不是一个命题 . 原因是 “P(x) S(x)”没有把命题 中 “凡 ”的意思表示出来 .即缺少表示个体常项或变项的数量关系的词 . 所以还要引入量词的概念 .8/26量词量词 : 表示个体常项或变项之间数量关系的词 .量词只有两个 : 全称量词 , 存在量词 .(1) 全称量词 : 表示 “全部 ”含义的词 . 全称量词符号化为 “”.a. 常用语中 “全部 ”, “所有的 ”, “一切 ”, “每一个 ”, “任何 ”, “任意的”, “凡 ”, “都 ”等词都是全称量词
8、 .b. x F(x)表示个体域里所有个体都有性质 F.(2) 存在量词 : 表示 “存在 ”含义的词 . 存在量词符号化为 “”. a. 常用词中 “存在 ”, “有一个 ”, “有的 ”, “至少有一个 ”等词都是存在量词 .b. x F(x)表示个体域中存在个体具有性质 F.例 : 凡偶数都能被 2整除 .可符号化为 : x(P(x)S( x)是真命题 , 其中 x不再起变元的作用 , 它被全称量词 限制住了 , 这时我们称 x 被量化了 .9/26一阶逻辑中命题符号化例 个体域为 人类集合 , 将下面两个命题符号化 :(1) 凡是人都要呼吸 ; (2) 有的人用左手写字 .解 令 F(
9、x): x 呼吸 ; G(x): x 用左手写字 . 则(1) x F(x); (2) x G(x)。例 上例中 , 将个体域改为 全总个体域 , 两命题的符号化形式如何?解 令 F(x): x呼吸 ; G(x): x用左手写字； M(x) : x是人 .则 : (1) x (M(x) F(x); (2) x (M(x) G(x). 特性谓词 : 从全总个体域中分离出一个集合 , 定义的谓词 . 在不同个体域中 , 同一个命题的符号化形式可能不同 .一般地 , 对全称量词 , 特性谓词应作为蕴含式的前件 .一般地 , 对存在量词 , 特性谓词应作为合取式的一项 . 同一个命题 , 在不同个体域
10、中的真值也可能不同 .如果问题中没有指明个体域时 , 默认为 全总体域 .10/26一阶逻辑中命题符号化续 当 F是谓词常项时 , xF(x)是个命题 , 如果把个体域中的任何一个个体 a代入 , F(a)都为真 , 则 xF(x)为真 ; 否则 xF(x)为假 . 当 F是谓词常项时 , xF(x)是个命题 , 如果个体域中存在一个个体 a使 F(a) 为真 , 则 xF(x)为真 ; 否则 xF(x)为假 .例 在个体域限制为 (a)和 (b)条件时 , 将下列命题符号化 , 并给出它们的真值 . (1) 对于任意的 x, 均有 x2-3x+2=(x-1)(x-2)(2) 存在 x, 使得 x+5=3其中 (a)个体域为 D1=N (b)个体域为 D2=R解 令 F(x): x2-3x+2=(x-1)(x-2) , G(x): x+5=3.则可符号化为 (1) xF(x), (2) xG(x) .个体域为 (a)时 , (1)是真命题 , (2)是假命题 ;个体域为 (b)时 , (1)与 (2)都是真命题 .
