应用离散数学第三章第1讲.ppt

第三章一阶逻辑基础
郑征
******@buaa.
软件与控制研究室
应用离散数学第三章第1讲
第1讲一阶逻辑基础
内容提要
1. 量词、谓词、个体词、命题符号化
2. 合式公式、解释、永真式
3. 一阶逻辑等值式
4. 一阶逻辑推理规则
应用离散数学第三章第1讲
命题逻辑的优缺点
命题逻辑是陈述性的,推理和表示分开
对比:程序本身只表示计算过程
命题逻辑可以采用析取式和否定式来处理不完全信息
对比:程序以及数据库中的数据结构
命题逻辑具有合成性,
例如B1,1  P1,2 的含义从 B1,1和 P1,2得到。
命题逻辑的含义与上下文无关
命题逻辑缺乏足够的表达能力
应用离散数学第三章第1讲
一阶逻辑
采用命题逻辑的基础—陈述式、上下文无关和合成语义,并借用自然语言的思想。
一阶逻辑假设世界包含
对象:人们、房子、数字…
关系:红色的、比…大…
函数:是…的父亲…
例子:1+2=3
应用离散数学第三章第1讲

基本区别在于本体论的约定
命题逻辑假设世界中的事实要么成立,要么不成立
一阶逻辑则假设更多,即世界由对象组成,对象之间的某些关系要么成立,要么不成立。
应用离散数学第三章第1讲
一阶逻辑 vs. 命题逻辑
引进一阶逻辑的背景:命题逻辑无法用简明的形式表示复杂环境的知识。
一阶逻辑是通过允许在给定论域的个体上的量化而扩展命题逻辑的演绎系统。
命题逻辑处理简单的陈述性命题,一阶逻辑补充覆盖了谓词和量化。
应用离散数学第三章第1讲
例如下列句子:
“苏格拉底是男人”,“柏拉图是男人”。
在命题逻辑中,它们是两个无关的命题,比如指示为 p 和 q。但是在一阶逻辑中,这两个句子将由同一个性质联系起来:Man(x),这里的 Man(x) 意味着 x 是个男人。
应用离散数学第三章第1讲
在 x = 苏格拉底时我们得到了第一个命题 p,而在 x = 柏拉图时我们得到了第二个命题 q。
这种构造在介入了量词的时候允许更加强力的逻辑,比如“对于所有 x...”。例如,“对于所有 x,如果 Man(x) 则...”。
应用离散数学第三章第1讲
一阶逻辑的字母表
个体常项: a, b, c, …, a1, b1, c1,…
个体变项: x, y, z, …, x1, y1, z1,…
函数符号: f, g, h, …, f1, g1, h1,…
谓词符号: F, G, H, …, F1, G1, H1, …
量词符号: , 
联结词符号: , , , , 
括号与逗号: (, ), ,
应用离散数学第三章第1讲
谓词(predicate)
谓词:表示性质、关系等;相当于句子中的谓语。
用大写英文字母F, G, H,…,后跟括号与变元来表示。例如:
F(x): x是人。
G(x, y): x与y是兄弟。
n元谓词:含有n个变元。例如:
F(x)是一元谓词, G(x, y)是二元谓词
应用离散数学第三章第1讲