谓词公式
-
2023年2月27日发(作者：国际商务英语)1/4
20XX年复习资料
大
学
复
习
资
料
专业：
班级：
科目老师：
日期：
2/4
§2.2谓词公式及其解释
习题2.2
1.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）
))()((yxQxPx，
（2）
)()(yxyQyxxP，，
（3）
)())()((zyxxRzyQyxPyx，，，，
解（1）
x
中的x是指导变元；量词
x
的辖域是
),()(yxQxP
；x是约束变元，
y是自由变元。
（2）
x
中的x，
y
中的y都是指导变元；
x
的辖域是
)(yxP，
，
y
的辖域是
)(yxQ，
；
)(yxP，
中的x是
x
的约束变元，y是自由变元；
)(yxQ，
中的x是自由
变元，y是
y
的约束变元。
（3）
x
中的x，
y
中的y以及
x
中的x都是指导变元；
x
的辖域是
))()((zyQyxPy，，
，
y
的辖域是
)()(zyQyxP，，
，
x
的辖域是
)(zyxR，，
；
)(yxP，
中的x，y都是约束变元；
)(zyQ，
中的y是约束变元；z是自由变元，
)(zyxR，，
中的x为约束变元，y，z是自由变元。
2.设个体域
}21{，D
，请给出两种不同的解释1
I
和2
I
，使得下面谓词公式在1
I
下都是真命题，而在2
I
下都是假命题。
（1）
))()((xQxPx
（2）
))()((xQxPx
解（1）解释1
I
：个体域
}21{，D
，
0:)(,0:)(xxQxxP
。
（2）解释2
I
：个体域
}21{，D
，
2:)(,0:)(xxQxxP
。
3.对下面的谓词公式，分别给出一个使其为真和为假的解释。
（1）
)))()(()((yxRyQyxPx，
（2）
)),()()((yxRyQxPyx
解（1）成真解释：个体域D＝
{1,2,3},
0:)(xxP
,
2:)(yyQ
,
3:),(yxyxR
。
成假解释：个体域D＝{1,2,3},
0:)(xxP
，
2:)(yyQ
，
1:),(yxyxR
。
（2）成真解释：个体域D＝{1,2,3}，
0:)(xxP
，
2:)(yyQ
，
3:),(yxyxR
。
成假解释：个体域D＝{1,2,3},
0:)(xxP
，
0:)(yyQ
，
1:),(yxyxR
。
4.给定解释
I
如下：
个体域
RD
（这里
R
为实数集合）。
3/4
个体常元
0a
。
二元函数
yxyxf)(，
。
二元谓词
yxyxP：，)(
，
yxyxQ：，)(
。
在解释
I
下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其
真值又如何？
（1）
))()((yxPyxQyx，，
（2）
))())(((yxQayxfPyx，，，
（3）
)))(()((ayxfPyxQyx，，，
（4）
))())(((yxPayxfQyx，，，
解（1）公式被解释成“
)(yxyxyx
”，为真命题。
（2）公式被解释成“
)0(yxyxyx
”，为假命题。
（3）公式被解释成“
)0(yxyxyx
”，为真命题。
（4）公式被解释成“
)0(yxyxyx
”，为假命题。
5.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理
由。
（1）
)()(xxPxP
（2）
)()(xPxxP
（3）
)()(xxPxP
（4）
)()(xPxxP
（5）
))()((xPxPx
（6）
)()(yxxPyyxyPx，，
（7）
)()(xyyPxyxyPx，，
（8）
)()(yxyPxyxyPx，，
（9）
)()(yxxPyyxyPx，，
（20XXXX）
))()((xyPyxPyx，，
解（1）因为当存在某个
x
使
)(xP
取1时
)(xxP
一定取1，所以公式是为永真式。
（3）取解释1
I
：个体域为自然数集合，
0)(2xxP：
。在1
I
下公式的前件与后件
均为真，所以公式为真，即不是永假式。取解释2
I
：个体域仍为自然数集合，但
)(xP
取为
0x
。在2
I
下公式不成为命题，即不是永真式。综合知公式为可满足式。
（5）取解释1
I
：个体域为自然数集合，
0)(2xxP：
。在1
I
下，对任意的
x
，
)(xP
为真而
)(xP
为假，所以公式为假，即不是永真式。取解释2
I
：个体域仍为自然数集
合，但
)(xP
取为
02x
。在2
I
下，对任意的
x
，
)(xP
为假而
)(xP
为真，所以公式为
真，即不是永假式。综合知公式为可满足式。
（7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个
解释，使得
)(yxyPx，
取1而
)(xyyPx，
取0。
)(xyyPx，
取0表明存在某对
00
,yx
使得
)(
00
xyP，
取0，从而
)(yxyPx，
也应取0。这与前面说
)(yxyPx，
取
1矛盾。故公式是永真式。
4/4
（9）设
I
为任意一个解释，个体域为
D
。若
)(yxyPx，
取1，即存在
Dx
0，
使得
)(
0
yxyP，
为真，从而
)(yxxPy，
为真，故
)()(yxxPyyxyPx，，
为真。
所以在解释
I
下公式为真，由
I
的任意性可知，公式为永真式。
（2）、（4）、（6）、（8）、（20XXXX）略。
6.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理
由。
（1）
))()(())()((yyQxxPxQxPx
（2）
))()(())()((yyQxxPxQxPx
（3）
)())()((yyQyyQxxP
（4）
))()(())()((xxQyPxQyPx
（5）
))()(())()((xxQxPxQxPx
（6）
)))()(()((xPyxyQxP，
（7）
))()(()(yxPyxQyxP，，，
解略
7.给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满
足式。
解略