离散数学教学课件02-谓词逻辑-2.4.pptVIP

第二章 谓词逻辑 Predicate Logic 补充：公式解释与类型 一、公式解释 一般情况下，谓词公式中包含： 个体常元、个体变元、函数变元、谓词变元等。 对各种变元用指定的特殊常元去代替就构成了一个公式的解释。 在给定的解释下，可以对多个公式进行解释 公式解释 定义：一个解释I由下面4部分组成 非空个体域DI DI中特定元素： a’, b’, …… DI上的特定的函数：f’, g’, …… DI上的特定的谓词：P’, Q’, …… 公式解释 在一个具体的解释中，个体常元、函数、谓词的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域DI内变化，量词符 ? 和 ? 仅作用于DI中的元素 公式解释 例2.5 有给定的解释I： DI ＝{3, 6} DI中特定的元素： a’=3 DI中特定函数： f’(x) : f’(3)=6, f’(6)=3 DI中特定谓词： P’(x) : P’(3)=F, P’(6)=T Q’(x,y) : Q’(i, j)=T(i, j=3,6) R’(x, y) : R’(3,3)=R’(6,6) =T R’(3,6)=R’(6,3) =F 公式解释 求下列公式的真值： (?x)( P(x)∧Q(x, a) ) 解：在解释I下： 公式 ? (P’(3) ∧ Q’(3, 3)) ∧ (P’(6) ∧ Q’(6, 3)) ? ( F ∧ T ) ∧ ( T ∧ T ) ? F 公式解释 (?x)( P(f(x)) ∧Q(x, f(x)) ) 解：在解释I下： 公式 ? (P’(f ’(3))∧Q’(3,f’(3))) ∨ (P’(f’(6))∧Q’(6, f’(6))) ? (P’(6)∧Q’(3, 6)) ∨ (P’(3)∧Q’(6, 3)) ? (T∧T) ∨ (F∧T) ? T 公式解释 (?x)(?y) R (x, y) 解：在解释I下： 公式 ? (?x)(R (x, 3) ∨ R (x, 6)) ? (R (3, 3) ∨ R (3, 6)) ∧ (R (6, 3) ∨ R (6, 6)) ? (T ∨ F) ∧ (F ∨ T) ? T 公式解释 (?x)(?y) R (x, y) 解：在解释I下： 公式 ? (?y) R (3, y) ∧ (?y) R (6, y) ? (R (3, 3) ∨ R (3, 6)) ∧ (R (6, 3) ∨ R (6, 6)) ? (T ∨ F) ∧ (F ∨ T) ? T 公式解释 例2.6 有给定的解释I： DI ＝整数集合 DI中特定的元素： a’=0 DI中特定函数： f’(x,y) : x+y, g’(x, y)=x·y DI中特定谓词： E’(x, y) : x=y, B’(x,y) : x y 求下列公式哪个为真，哪个为假？ 公式解释 (?x) E ( g(x, a), x ) 解：在解释I下： 公式 ? (?x) E ( g (x, 0), x ) ? (?x) (x·0 = x ) ? (?x) ( 0 = x ) ? F 公式解释 (?x) (?y) (E ( f (x, a), y ) ? E( f (y, a), x )) 解：在解释I下： 公式 ? (?x) (?y)( (x+0=y) ? (y+0=x) ) ? (?x) (?y)( (x=y) ? (y=x) ) ? T 公式解释 (?x) (?y) (?z) E ( f (x, y), z ) 解：在解释I下： 公式 ? (?x) (?y) (?z) (x+y=z) ? T E ( f (x, y), g (x,y) ) 解：公式 ? (x+y=x·y ) 变元没有量化，真值不确定，不是命题 公式解释 (?x) (?y) B ( x, y ) 解：在解释I下： 公式 ? (?x) (?y) ( x y ) ? T (?x) (?y) B ( x, y ) 解：在解释I下： 公式 ? (?x) (?y) ( x y ) ? F 公式类型 二、公式类型 定义： 若一个公式在任何解释下都是真的称该公式为逻辑有效式，也叫作永真式或重言式 若一个公式在任何解释下都是假的称该公式为矛盾式，也叫作永假式 若一个公式至少存在一个解释使其为真称该公式为可满足式 公式类型 例2.7 判断下列公式是否为重言式 (?x)P(x) ? (?x) P(x) 解：设I为任意解释，个体域为DI，若存在a ∈DI ，使P(a)为假，则公式的前件(?x)P(x)为假，则公式为真 否则，对于?x ∈DI ，