离散数学第三章一阶逻辑.pptVIP

一阶逻辑基本概念 一阶逻辑命题符号化 一阶逻辑公式、解释 谓词逻辑（一阶逻辑）的引入 著名的三段论论证： 所有的人都将死去。 苏格拉底是人。 所以：苏格拉底将死去。 从人们的实践经验可知，这是一个有效的推论。 但在命题逻辑中却无法判断它的正确性。 因为在命题逻辑中只能将推理中的三个简单命题符号化为p, q, r，那么由p, q这两个命题无论如何不可能得出r为有效结论。 §3.1 一阶逻辑基本概念 基本概念——个体词、谓词、量词 个体词（个体）: 所研究对象中可以独立存在的具 体或抽象的客体 个体常项：具体的事务，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域（论域）: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 如果事先没有给出个体域，都应以全总个体域为个体域。 基本概念 (续) 谓词: 刻划个体词性质或相互之间关系的词 ???? 谓词常项：表示具体性质和关系的谓词， 用F, G, H…表示； ???? 谓词变项：表示抽象或泛指的谓词， 也用F, G, H…表示； ???? 一元谓词: 表示事物的性质 多元谓词(n元谓词, n?2): 表示事物之间的关系 如 L(x,y)：x与y有关系L，L(x,y)：x?y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命 题变项 实例 (1) 4是偶数 4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁 小王, 小李是个体常项, 同岁是谓词常项. 记a:小王, b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b) (3) x y x,y是命题变项, 是谓词常项, 符号化为: L(x,y) (4) x具有某种性质P x是命题变项, P是谓词变项, 符号化为: P(x) 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化,并讨论它们的真值. 要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例1(续) 将下列命题符号化, 并讨论其真值: (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 (a) (1) ?x F(x) 真值为1 (2) ?x G(x) 真值为0 (b) (1) ?x F(x) 真值为1 (2) ?x G(x) 真值为1 基本概念(续) 量词: 表示数量的词 ???? 全称量词?: 表示任意的, 所有的, 一切的等 如 ?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如 ?x 表示在个体域中存在x 一阶逻辑中命题符号化(续) 例2 在一阶逻辑中将下面命题符号化 (1)?人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为 ?x G(x) (2) 设G(x)：x用左手写字, 符号化为 ?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 (1) ?x (F(x)?G(x)) (2) ? x (F(x)?G(x)) 这是两个基本公式, 注意这两个基本公式的使用. 在这里是F(x)特性谓词 例 将下列命题符号化 : (1)小李比小赵高. (2)武汉位于北京和广州之间 例：将命题符号化: 凡有理数均可表成分数, (1) 个体域是有理数集合. (2) 个体域是实数集合 5. 在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。 例：对任意的x，存在着y,使得x+y=5, 个体域为实数集，其中H(x,y)：x+y=5，