北京大学：《离散数学》系列课程之三《数理逻辑》第27章（27.1）一阶谓词演算

数理逻辑 第27章 阶谓词演算 王捍贫 北京大学信息科学技术学院软件研究所

27 ￾ ✁✂✄ ☎✆✝✞✟✠✡✞☛☞✞✌✍✎✏✑✒

复习一命题演算 命题演算形式系统: 命题公式 语法 形式公理 形式规则 形式推理 指派 语义:{公式的值 永真式 可靠性:凡是推出来的都是正确的. 完全性:凡是正确的都可以推出来

— : • ✓    • ✓    : . : . 1

问题的提出 命题演算不能表达所有正确的推理.例 所有实数的平方都是非负的 丌是一个实数 丌的平方是非负的 如用命题演算推理形式来表示:由p,q推出r 非有效推理形式

. : ✔. π ✕ . π ✔. : ✖p, q ✗r. — 2

1一阶价谓词演算的符号亿 ●需要进一步分析推理结构. 上述推理中,各命题之间的关系在于简单命题的成分之间 需要进一步分解简单命题. ●简单命题的符号化

§1✘ • ✙ . ✚✛✜✢✣, ✤✥✦✧★✩✪✫✬✭✮✯✥✦✩✰✧✱★. • ✙ . • . 3

简单命题的结构 主语 宾语 讨论对象对象的性质或关系讨论对象 个体词(组) 谓词 个体词(组) 个体词,谓词

↑ ↑ ↑ ↓ ↓ ↓ ( ) ( ) , 4

例1 分析下列各命题中的个体和谓词 (1)π是无理数 (2)张三与李四同在计算机系 (3)x与y的和等于z(x,y,z是确定的数) (4)丌的平方是非负的 (5)所有实数的平方都是非负的 (6)有一个比200的素数

1 (1) π . (2) . (3) x y z (x, y, z ). (4) π . (5) . (6) ✙ 21000 . 5

例1(1) (1)π是无理数 解: 个体:π(代表园周率) 谓词:…是无理数,表示“π”的性质

1(1) (1) π . : : π ( ) :✲ , ✳ π✴ . 6

例1(2) (2)张三与李四同在计算机系 解 个体:张三,李四 谓词:…与…同在计算机系, 表示张三与”李四”之间的关系

1(2) (2) . : ✵✶: ✷✸, ✹✺ ✻✼:✽✽ ✾✿✬❀❁❂✫, ❃❄”✷✸”✾”✹✺✧” ★✩✪✫. 7

例1(2) (2)张三与李四同在计算机系 解 个体:张三,李四 谓词:…与…同在计算机系, 表示”张三”与”李四之间的关系 个体:张三 谓词:…与李四同在计算机系, 表示”张三”的性质 7-a

1(2) (2) . : ✵✶: ✷✸, ✹✺ ✻✼:✽✽ ✾✿✬❀❁❂✫, ❃❄”✷✸”✾”✹✺✧” ★✩✪✫. ✵✶: ✷✸ ✻✼:✽ ✾✹✺✿✬❀❁❂✫, ❃❄”✷✸✩” ❅❆. 7-a

例1(2) (2)张三与李四同在计算机系 解 个体:张三,李四 谓词:…与…同在计算机系, 表示张三与”李四”之间的关系 个体:张三 谓词:…与李四同在计算机系, 表示张三”的性质 个体:李四 谓词:张三与…同在计算机系, 表示”李四”的性质 7-b

1(2) (2) . : ✵✶: ✷✸, ✹✺ ✻✼:✽✽ ✾✿✬❀❁❂✫, ❃❄”✷✸”✾”✹✺✧” ★✩✪✫. ✵✶: ✷✸ ✻✼:✽ ✾✹✺✿✬❀❁❂✫, ❃❄”✷✸✩” ❅❆. ✵✶: ✹✺ ✻✼: ✷✸✽ ✾✿✬❀❁❂✫, ❃❄”✹✺✩” ❅❆. 7-b