离散件3-谓词逻辑

离散数学全部课件

第二章 谓词逻辑首先看看著名的“苏格拉底三段论式”:

Every man is mortal.Socrates is a man. Socrates is mortal. 按命题形式化方法，可翻译为 P,Q R 这个形式化结果无法利用命题逻辑推理证明。

离散数学全部课件

又如 x+y >6 不是命题，但是对任何具体的 实数x和y,它都有确定的真值。 命题逻辑的局限性

----难以表达命题之间的内在联系；----难以表达局部和全局的概念； ----没有考虑命题与“范围”之间的联系。

离散数学全部课件

第一节 量词化逻辑一、谓词：描述客观对象的性质或客观对象之间关系的断语。 例：梨花是白的，桃花是红的。 小张长得比小刘更结实。 1。谓词的形式化 1)个体域： 又叫论域，由客体构成的集合， 可表示为 ={a1,a2, ,an}。

离散数学全部课件

2)客体：一般用 x,y,z等表示客体变元，用 a,b,c或具体的客体符号等表示客

体常元。3)谓词标识符：表达谓语的符号串，常用

大写字母串表示，如A,B等表示。4)谓词：由谓词标识符和客体等构成的符

号串。如 A(a,x,f(x) )

离散数学全部课件

例：令W(x):x是白的；

p:梨花，则“梨花是白的”的谓词表示为：

W( p)。令 H( x,y): x比 y 结实，

a:小张， b:小刘，则“小张长得比小刘更结实”的

谓词表示为：H( a,b)。

离散数学全部课件

2。注意事项：1)谓词中客体的位置不能随意交换。一般， A(x,y)不等价 于A( y,x)。 2)谓词的真值与论域相关。 例如用谓词 A(x,0)表示 x > 0,在由正数构成的论域中， 其值为真; 而在由 0或负数构成的论域中，其值为假。 3) 一般情况下，使用全总个体域构造谓词，而用特性谓词来 限制或说明客体。 4)谓词中客体变元的个数称为谓词的元数。如 H(x,y)是一 个二元谓词。A(x, y , z)是一个三元谓词。把命题作为谓词 的特殊形式，即 0 元谓词。例如 P,H(a, b) 等等。

离散数学全部课件

二、量词 1。全称量词：表达“任意的”、“一切的”等 限定概念。用符号“ ”表示。 常用法: ( x)A(x) 2。存在量词：表达“存在”、“有”、“某个” 等限定概念。用“ ”表示。 常用法: ( x)A(x)

离散数学全部课件

注意：在表达式 ( x)A(x)中，如果谓词A(x)是一个 一元谓词，那么在确定的论域中 ( x)A(x)就是一个 命题。同理( x)A(x)也一样。例：设论域 1={1,2,3,4}, 2={2,3,7},

令 PRIME(x):x是素数。那么， ( x) PRIME(x) 在论域 1上取值 0,而 在 2上取值 1。 ( x) PRIME(x) 在论域 1上取值 1,而在 2上 也取值 1。

离散数学全部课件

一般情况下，使用全总个体域构造谓词，而用特性 谓词来限制或说明客体。 例：把“并非每个正整数都是素数”翻译成谓词表 达式。解：令N( x):x是正整数， P( x):x是素数， 则可译为： ( x) [ N( x

) P(x)]

也可译为：

( x) [ N( x) P(x)]

对全称量词，特性谓词作条件式的前件加入 对于存在量词、特性谓词作合取项加入

离散数学全部课件

例：把“苏格拉第三段论式”翻译成谓词表达式： 解：令M(x):x是人， D(x):x是要死的， s:苏格拉底。

则可把“苏格拉底三段论式”翻译为：(( x) [ M(x) D(x)] M(s)) D(s)

离散数学全部课件

例：把“每个实数的平方不小于 0”译成谓词表达式。 解：令R(x):x 是实数， L(x,y):x < y, f(x) = x2 ,

这个命题可以有两种翻译形式：当设定论域为实数集合时，可译为 ( x) [ L(f(x),0)]

当设定论域为全总个体域时，可译为( x) [ R(x) L(f(x),0)]

离散数学全部课件

3。量词的辖域和指导变元 在表达式 ( x) A(x) (或 ( x) A(x))中，紧 接量词后的变元 x 称为指导变元，A(x)称为量 词的辖域。 4。约束变元和自由变元 量词辖域中与指导变元同名的变元称为约束 变元，其它变元称为自由变元。

离散数学全部课件

例：在表达式

( x) [ A(x) ( y) [ B(y) C(x,y)]]中，对于全称量词 而言，辖域中变 量 x 是受约束的，对于存在量词 而 言，其辖域中变量y是受约束的，而 x 是自由的。

离散数学全部课件

注意：当对公式中的指导变元和约 束变元换用另一个符号表示时，不 改变公式的实际意义。

也就是说， ( x) A(x)与 ( t) A(t)无本质区别， ( y)B(y)与 ( x)B(x) 也是相同的.

离散数学全部课件

5。 在有限论域上量词公式的等价表示 设论域 ={a1,a2, ,an},则 ( x) R(x) R(a1) R(a2) R(an) ( x) R(x) R(a1) R(a2) R(an)

离散数学全部课件

作业：习题2. 1

1, 2(3), 3(2), 4(2) (吴子华) or

习题2.1

1, 2(3), 3(2), 4(2) (冯伟森)

离散数学全部课件

第二节、谓词合适公式(WFF)一、定义 1. 项：个体域上的常元、变元、函数称为项。 例：a,b,x,y,f(x,y),g(h(x),x) 等都是论域上的项。 2。原子公式：当P是n元谓词标识符，t1,t2,

,tn 都是论域中的项时，称P( t1,t2,tn)为n元原子谓词公式。 例：A(x),L(f(x),a)都是论域上的原子公式。

,

离散数学全部课件

3。谓词合适公式(WFF)的递归定义 1)原子公式是WFF; 2)当A和B是WFF时， A 、 B、(A B)、 (A B)、(A B)和(A B)都是WFF;

3)当A是WFF,x是A中变元时， ( x) A(x) 和( x) A(x)都是WFF;

4)只有按照1) 至 3)生成的公式才是WFF。

离散数学全部课件

二、WFF的解释

1。指定论域；2。常元符代以具体的客体；

3。函数标识符代以论域中的具体函数；4。谓词标识符代以具体的谓词；

5。求出公式在解释下的值。

本文来源：https://www.bwwdw.com/article/a6pi.html