谓词逻辑永真公式

P(1,1): T； P(1,2): F； P(2,1):F； P(2,2): T – 则xyP(x,y)和yxP(x,y) 在解释I下的真值分
别为?
xyP(x,y) 关于x的一元函数
x y P(x,y) yP(x,y) xyP(x,y)
1
T
1
T
2
F
T
1
F
2
T
2
T
yxP(x,y) 关于y的一元函数
– 例：I(x)：x是整数，论域E为自然数集合
• I(x)在E上是永真式 • I(x) ∨ I(x)是与论域无关的永真式
• 谓词公式的永假式 • 谓词公式的可满足式
例：试说明以下公式的类型
1. xA(x)→A(y)
永真式
2. xA(x)→A(y)
可满足式
3. A(x) (A(x) ：x+6=5) 可满足式
x(A(x)∨B(x)) F
B(1) B(2) F
因此
xA(x) F
所以 xB(x) T
从而 A(1) A(2) B(1) B(2)
F
FT
结论：所给公式不是永真式
例(续前)：试判断xA(x)∨xB(x) → x(A(x)∨B(x)) 是否是永真式，并说明理由。
解：所给公式不是永真式，理由如下。
体函数常量
3. 对A中出现的每一个n元谓词，指定一个D上的n元谓词 常量
4. 对A中出现的每一个个体常量及自由变元，指定D中的 一个个体常量
5. 对A中出现的每一个命题变元P，指派一个真值T或F
由此得到一个命题AI，称AI的真值为公式A在 解释I 下的真值
例
• 取解释I如下：
– D={1,2}, – 定义D上的二元谓词P真值为
– 联词与量词的关系 – 问题与否问题的关系 – 构造证法的一种典型情形 – 公式形成规则、联词、量词、变元约束等知识点 – 逐步推演思想 – 完整地自顶向下逐步求精思想
问题与否问题
• 问题：所给公式是永真式吗？ • 否问题：所给公式不是永真式吗？ • 这两个问题有不同的难度
– 是永真式：在任何论域的任何解释下皆为真 – 不是永真式：存在一个使该公式为假的特定
• 注意：以前进行运算都是根据形成过程由里往外 逐次进行的，但这里的过程正好相反：自顶向下 逐步推演。
• 在推演过程中，首先考虑以下事实：
A→B F
AB TF
A∨B F
A B A∧B FF T
AB TT
xA(x) A(1) A(2)
xA(x) A(1) A(2)
T
TT
F
FF
• 若是上述五种情况之外的情况，则利用D中元素 的对称性避免讨论。
P(1)→Q(f(1),1)
P(2)→Q(f(2),1)
T
T
x(P(x)→Q(f(x),a))在解释I下的真值为T
谓词公式的永真式
• 定义
– 给定谓词公式A，E是其论域，如果在任何解释 下公式A的真值都为真，则称公式A在论域E上 是永真式。如果不论对什么论域E，都使得公 式A为永真式，则称A为永真式。
考虑D={1,2}上的解释I：
A(1) A(2) B(1) B(2)
FFFT
在I下： xB(x) A(1)∨B(1)
T
F
此处取T亦可
所以 xA(x)∨xB(x) x(A(x)∨B(x))
T
F
xA(x)∨xB(x) → x(A(x)∨B(x))
F
总结
• 总的思路：试图在D={1,2}上找到一个使所给公式 为假的解释。
11.6 谓词逻辑的永真公式
• 在谓词逻辑中，公式是一个符号串，必须 给以具体的解释后才能分辨其真假的可能。
• 解释：给公式中的个体变元指定一个具体 的个体域D
• 一个公式经解释后才具有具体的意义。
• 谓词公式的解释I包括：
1. 指定一个论域D(称I为D上的解释) 2. 对A中出现的每一个n元函数，指定一个D上的 n元个
y x P(x,y) xP(x,y) yx P(x,y)
1
T
1
F
2
F
F
1
F
2
F
2
T
例
• 取解释I如下：
– D={1,2}, – 令 a:1, f(1)=2, f(2)=1 – 定义D上的谓词P和Q为
P(1): F； P(2): T； Q(1,1):T； Q(1,2):T； Q(2,1):F； Q(2,2): F 求谓词公式x(P(x)→Q(f(x),a))在解释I下的真值
• I(x)与N(x)在E上是等价的 • N(x)→I(x) N(x)∨I(x)
4. x( A(x) ∧ ¬A(x)) 永假式
5. 6.
x (A(x)∨B(x)) → x (A(x)∧B(x))
xA(x)∨xB(x) xA(x) ∧ xB(x)
永真吗?
永真式的判定
• 命题逻辑的永真式问题是可判定的。
– 至少可用真值表
• 谓词逻辑的永真式问题是不可判定的。 • 研究谓词逻辑永真式判定问题非常有意义：
谓词公式的等价
• 定义
– 两个任意谓词公式A和B, E是它们共有的论域, 若在任何解释下，A与B作的真值都相同(或者 说AB是永真式)，则称公式A与B在论域E上是 等价的。如果不论对什么论域E，都使得公式A 与B等价，则称A与B等价，记作AB。
– 例：I(x)：x是整数，N(x)：x是自然数，论域E 是自然数集合
目的(约束条件)是 xA(x)∨xB(x) → x(A(x)∨B(x)) F
所以
xA(x)∨xB(x) T
x(A(x)∨B(x)) F
xA(x)为T或xB(x)为T
A(1)∨B(1)为F或A(2)∨B(2)为F
xA(x)∨xB(x)
T
不妨取
A(1)∨B(1) F
这样 A(1) A(2) F
解释
问题证明的一般方法
直接证明法 反证法 数学归纳法
Px(Q(x)→R(x)) What描述方式决定
(两种方式)
找出实例
2.转换形式结构 3.引用已知条件P
x：Q(x)
(问题具体描述)
PxA(x)
构造证法 给出算法
(问题抽象描述)
Q1(x)
P R1(x)
R(x)
递归或递推的 形式给出算法
例：试判断xA(x)∨xB(x) → x(A(x)∨B(x))是否是 永真式，并说明理由。
分析：试图找到一个使该公式为假的解释，首先考虑论域。 论域大了，过程会复杂，论域小了，无法区分全称与存在，
所以取D={1,2}。
现在要确定 A(1) A(2) B(1) B(2) ?? ??