谓词逻辑习题
1. 将下列命题用谓词符号化。
（1）小王学过英语和法语。 （2）2大于3仅当2大于4。
（3）3不是偶数。 （4）2或3是质数。
（5）除非李键是东北人，否则他一定怕冷。
解：
(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧
(2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P →
(3) 令)(x P ：x 是偶数，命题符号化为)3(P ?
(4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨
(5) 令)(x P ：x 是北方人；)(x Q ：
x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。
（1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨??
（3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?，
解：
(1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，
得到
))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧??
（2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对
)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨??
))()((z Q x P z x ∨???
))()((z Q x P z ∨?
（3）略
（4）略
3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。求下列各式的真值。
（1）)3(，x xP ? （2）)1(y yP ，?
（3）)(y x yP x ，?? （4）)(y x yP x ，??
（5）)(y x yP x ，?? （6）)(y x xP y ，??
解：
(2) 当3=x 时可使式子成立，所以为
Ture 。 (3) 当1≠y 时就不成立，所以为
False 。 (4) 任意的x,y 使得y x =，显然有y x ≠的情况出现，所以为False 。
(4)存在x,y 使得y x =，显然当1,1==y x 时是一种情况，所以为Ture 。
(5)存在x ，任意的y 使得y x =成立，显然不成立，所以为False 。
(6)任意的y ，存在x ，使得y x =成立，显然不成立，所以为False 。
4. 令谓词)(x P 表示“x 说德语”，)(x Q 表示“x 了解计算机语言C++”，个体域为杭电全体学生的集合。用)(x P 、)(x Q 、量词和逻辑联接词符号化下列语句。
（1）杭电有个学生既会说德语又了解C++。
（2）杭电有个学生会说德语，但不了解C++。
（3）杭电所有学生或会说德语，或了解C++。
（4）杭电没有学生会说德语或了解C++。
假设个体域为全总个体域，谓词)
(x
Q、
P、)
M表示“x是杭电学生”。用)
(x
(x
M、量词和逻辑联接词再次符号化上面的4条语句。
)
(x
解：（ⅰ）个体域为杭电全体学生的集合时：
（1）))
x
x∧
?
Q
P
(
)
(
(x
（2）))
P
∧
?
x
x?
Q
(
)
(
(x
（3）))
P
x∨
?
x
Q
)
(
(x
(
（4）))
P
x∨
x
?
?
(
Q
)
(
(x
（ⅱ）假设个体域为全总个体域，谓词)
M表示“x是杭电学生”时：
(x
（1）))
P
x
x
M
∧
x∧
?
Q
)
(
(
)
(
(x
（2）))
M
x
x?
∧
?
∧
P
x
(
)
)
(
Q
(x
(
（3）)))
Q
x
x
M
∧
x∨
?
P
)
(
(
(
(
)
(x
（4）)))
x
x
M
x∨
∧
?
?
P
)
(
Q
(
(
(x
(
)
5. 令谓词)
P，表示“x爱y”，其中x和y的个体域都是全世界所有人的
(y
x
集合。用)
P，、量词和逻辑联接词符号化下列语句。
x
(y
（1）每个人都爱王平。（2）每个人都爱某个人。
（3）有个人人都爱的人。（4）没有人爱所有的人。
（5）有个张键不爱的人。（6）有个人人都不爱的人。
（7）恰有一个人人都爱的人。（8）成龙爱的人恰有两个。
（9）每个人都爱自己。（10）有人除自己以外谁都不爱。
解：a：王平b：张键c：张龙
(1) ）
x
yP
x?
?
,
(y
x
xP,
(
? (2))
a
(3))
P
x
y
?
?
(y
x?
x
,
,
(y
xP
? (4))
y?
(5))
P
y
?
(y
?
x?
x
b
(x
P
x，
? (6))
?
,
(7)))
ω
→
x=
yP
y
?
?
?ω
?
∧
x
z
)
((
(
))
,
,
(
P
z
(x
z
(8))))
y
x=
∨
x
x
=
c
P
y
?
≠
P
?，
∧
∧
?
∧
→
z
(
)
,
c
(
(
)
(
(
)
P
(y
z
c
x
z
z
(9))
P
x
y
x
?
?
?
x=
y
)
(y (x
,
xP
x
? (10))
(
,
§谓词公式及其解释
习题
1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）))
P
x，
→
?
x
Q
)
(
(y
x
(
（2）)
xP，
，?
→
?
x
y
)
(y
x
yQ
(
（3）)
x，
y
P
x
，
y
?
∧
∨
，?
?
，
(
(
))
(
Q
(z
)
y
y
xR
z
x
解：（1）x是指导变元，x?的辖域是)
Q
x
x
P→，对于x?的辖域而言，x
,
(
)
(y
是约束变元，y是自由变元。
（2）x,y都为指导变元，x?的辖域是)
x
y
，?
→，y?的辖域是
P，
yQ
)
(
(y
x
x
Q，；对于x?的辖域而言，x,y都为约束变元，对于y?的辖域而言，x是(y
)
自由变元，y是约束变元。
（3）x,y为指导变元，x?的辖域是)
y，
P
x
y
，
Q
∧
∨
，?
，
?，
(z
)
(
))
(
(
y
z
xR
x
y
y ?的辖域是)())()((z y x xR z y Q y x P ，，，，?∨∧，x ?的辖域是)(z y x R ，，；
对于x ?的辖域而言，x,y 为约束变元，z 为自由变元，对于y ?的辖域而言，z 为自由变元，y 为约束变元，x 即为约束变元也为自由变元，对于x ?的辖域而言，x 为约束变元，y,z 是自由变元。在整个公式中，x,y 即为约束变元又为自由变元，z 为自由变元。
2. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（1）))()(())()((y yQ x xP x Q x P x ?∧?→∧?
（2）))()(())()((y yQ x xP x Q x P x ?∨?→∨?
（3）)())()((y yQ y yQ x xP ?∧?→??
（4）))()(())()((x xQ y P x Q y P x ?→→→?
（5）))()(())()((x xQ x P x Q x P x ?→→→?
（6）)))()(()((x P y x yQ x P →?→?，
（7）))()(()(y x P y x Q y x P ，，，→→
解：（1）易知公式是)()(q p q p ∧→∧的代换实例，而
1)()()()(=∧∨∧?=∧→∧q p q p q p q p
是永真式，所以公式是永真式。
（2）易知公式是)()(q p q p ∨→∨的代换实例，而
1)()()()(=∨∨∨?=∨→∨q p q p q p q p
是永真式，所以公式是永真式。
（3）易知公式是q q p ∧→?)(的代换实例，而
0)()(=∧?∧=∧∨??=∧→?q q p q q p q q p
是永假式，所以公式是永假式。
（4）易知公式是)
→
→的代换实例，而
q
p→
p
)
(
(q
→q
→
=
q
→
?
p
q
p
q
p
p
)
)
(
)
→
(
(
→
(=
)
∨
1
是永真式，所以公式是永真式。
（5）易知公式是)
p→
q
→
→的代换实例，而
(q
p
(
)
p
→q
→
=
q
→
q
?
p
q
p
p
1
→
)
(
)
)
(
(
→
∨
)
(=
是永真式，所以公式是永真式。
（6）易知公式是))
→
?的代换实例，而
p→
q
(
(p
→
?p
?
=
?
q
→
p
q
p
p
p
q
p
=
(
))
(
))
(
(=
∨
?
∨
∧
∧
?
是永假式，所以公式是永假式。
（7）易知公式是p
q
→的代换实例，而
p→
?
?
∨
=
∨
(
(
)
=
→)
→
p
q
p
q
p
∧
p
?
p
p∨
q
是可满足式，所以公式是可满足式。
§谓词公式的等价演算与范式
习题
1. 将下列命题符号化，要求用两种不同的等价形式。
（1）没有小于负数的正数。（2）相等的两个角未必都是对顶角。
解：（1）)
(y
x
,
R：x小于y，命题可符P：x为负数，)
(x
(x
Q：x是正数，)
号化为：)))
Q
x
(y
(
(
P
),
?
?
x?
y
R
?
x
(
(y
(
),
(
(
Q
?或)))
x?
y
P
R
（2）略
2.设)(x P 、)(x Q 和)(y x R ，都是谓词，证明下列各等价式
（1）))()(())()((x Q x P x x Q x P x ?→?=∧??
（2）))()(())()((x Q x P x x Q x P x ?∧?=→??
（3）))()()(())()()((y x R y Q x P y x y x R y Q x P y x ，，?∧∧??=→∧???
（4）))()()(())()()((y x R y Q x P y x y x R y Q x P y x ，，?→∧??=∧∧???
证明：（1）左边＝))()((x Q x P x ∧??
＝))()((x Q x P x ?∨??
＝))()((x Q x P x ?→?＝右边
（2）左边 ＝))()((x Q x P x →??
＝))()((x Q x P x ∨???
＝))()((x Q x P x ?∧?＝右边
（3）左边＝)),()()((y x R y Q x P y x →∧???
＝)),())()(((y x R y Q x P y x ∨∧????
＝))()()((y x R y Q x P y x ，?∧∧??＝右边
（4）左边＝),()()((y x R y Q x P y x ∧∧???
＝),())()((y x R y Q x P y x ?∨∧???
＝))()()((y x R y Q x P y x ，?→∧??＝右边
3. 求下列谓词公式的前束析取范式和前束合取范式。
（1）)()(y x yQ x xP ，?→?
（2）))()((z y x yQ y x P x ，，，?→?
（3）))()(()(x R z zQ y x yP x →?→???，
（4）))()((())()((z y zS y R y y x Q x P x ，，?→?→→?
解：（1）)),()((),()(y z Q x P y x y z Q x yP x ∨????→???原式 前束析取范式
)),()((y z Q x P y x ?∧???? 前束合取
范式
（2）原式),,(),((z t x Q y x P t x →???),,(),((z t x Q y x P t x ∨????前束析取范式 ),,(),((z t x Q y x P t x ?∧???? 前束合取范式
（3）原式))()((),((t R z Q y x P z y x →→?????
))()(),((t R z Q y x P z y x ∨?∨???? 前束析取范式
))()(),((t R z Q y x P z y x ?∧∧?????? 前束合取范式
（4）原式))()((())()((z t zS t R t y x Q x P x ，，?→?→→??
))),()(()),()(((z t S t R y x Q x P z t x →→→????
))),()(()),()(((z t S t R y x Q x P z t x ∨?∨∨??????
))),(),()(())(),()(((z t S y x Q x P t R y x Q x P z t x ∨∧∨?∨∧????
),()(),(()),()(()(((z t S t R y x Q z t S t R x P z t x ∨?∨∧∨?∨????
§ 谓词公式的推理演算
习题
1.证明：))()(())()((x B x A x x B x A x →??→?
证明：（1）左边))()(())()((x B x A x x B x A x →????→????
))()((x B x A x →????＝))()((x B x A x →?
2. 指出下面演绎推理中的错误，并给出正确的推导过程。
（1）①)
xP→
Q
?P规则
x
)
(x
(
②)
y
P→US规则：①
Q
(
)
(y
（2）①))
P
x→
Q
?P规则
x
(
(
)
(x
②)
a
Q
P→US规则：①
(
)
(b
（3）①)
(
→P规则
x
P?
)
(x
xQ
②)
a
P→ES规则：①
Q
(
)
(a
（4）①)
a
G
P→P规则
)
(
(a
②))
P
x→
?UG规则：①
x
G
)
(
(x
(
（5）①)
a
(
G
P∧P规则
(b
)
②))
P
?EG规则：①
x
x∧
(
G
)
(
(x
（6）①)
y
P→P规则
Q
)
(
(y
②))
c
P
?EG规则：①
Q
x→
)
(x
(
(
解：（1）②错，使用US,UG,ES,EG规则应对前束范式，而①中公式不是前束范式，所以不能用US规则。
(2)②错，①中公式为)
x
Q
P
x
=，因而使用US
A∨
(x
?，这时，)
)
(x
(
xA
)
(
规则时，应得A(a)(或A(y)),故应有)
(b
)
P∨。
(
Q
a
)
(
(a
Q
a
P∨，而不能为)
3.用演绎法证明下列推理式
P
y
y
Q
R
y
x
→
?
→
?，
∨
y
?
?
xP?
xP
x
(
(
)
)
(
))
))
(x
(
)
xR
((
)
(
证明：①)
?前提引入
(x
xP
②)
P ES①
(a
③ ))())()((()(y R y Q y P y x xP →∨?→? 前提引入 ④ ))())()(((y R y Q y P y →∨? T ①③
⑤ )())()((a R a Q a P →∨ US ④
⑥ )()(a Q a P ∨ T ②
⑦ )(a R T ⑤⑥
⑧ )(x xR ? EG ⑦
4. 将下列命题符号化，并用演绎推理法证明其结论是有效的。
（1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域）
（2）所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。（个体域取人类全体组成的集合）
（3）每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域取人类全体组成的集合）
（4）每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。（个体域取全体旅客组成的集合）
解：(2)证明：设P(x)：x 是个舞蹈者； Q(x) ：x 很有风度； S(x)：x 是个学生； a ：王华
上述句子符号化为：
前提：))()((x Q x P x →?、)()(a P a S ∧ 结论：))()((x Q x S x ∧?
（1）)()(a P a S ∧ P
（2）))()((x Q x P x →? P
（3）)()(a Q a P → US （2）
（4）)(a P T （1）I
（5）).(a Q T （3）（4）I
（6）)(a S T （1）I
（7）)()(a Q a S ∧ T （5）（6）I
（8）)()((x Q x S x ∧? EG （7）
]（3）命题符号化为：F(x)：x 喜欢步行,G(x)：x 喜欢骑自行车，H(x)：x 喜欢坐汽车。
前提：))()((x G x F x ?→?，))()((x H x G x ∨?，))((x H x ??
结论：))((x F x ??.
证明：(1) ))((x H x ?? P
(2) )(c H ? ES(1)
(3) ))()((x H x G x ∨? P
(4) )()(c H c G ∨ US(3)
(5) )(c G T(2)(4) I
(6) ))()((x G x F x ?→? P
(7) )()(c G c F → US(6)
(8) )(c F ? T(5)(7) I
(9) ))((x F x ?? EG(8)
（4）命题符号化为：F(x)：x 坐头等舱, G(x)：x 坐经济舱，H(x)：x 富裕。 前提：))()((x G x F x ∨?，))()((x H x F x ??，))((x H x ?，))((x H x ?? 结论：))((x G x ?.
证明：(1) ))((x H x ?? P
(2) )(c H ? ES(1)
(3) ))()((x H x F x ?? P
(4) )()(c H c F ? US(3)
(5) )(c F ? T(2)(4)I
(6) ))()((x G x F x ∨? P
(7) )()(c G c F ∨ US(6)
(8) )(c G T(5)(7)I
(9) ))((x G x ? EG(8)
5. 令谓词)(x P 、)(x Q 、)(x R 和)(x S 分别表示“x 是婴儿”，表示“x 的行为
符合逻辑”、“x能管理鳄鱼”和“x被人轻视”，个体域为所有人的集合。用)
P、
(x R、)(x
S、量词和逻辑联接词符号化下列语句。
Q、)(x
)
(x
（1）婴儿行为不合逻辑。
（2）能管理鳄鱼的人不被人轻视。
（3）行为不合逻辑的人被人轻视。
（4）婴儿不能管理鳄鱼。
请问，能从（1）、（2）和（3）推出（4）吗若不能，请写出（1）、（2）和（3）的一个有效结论，并用演绎推理法证明之。
解：（1）))
x?
P
→
?
x
(x
(
)
(
Q
（2）))
R
→
?
(
x
x?
(
(x
)
S
（3）))
Q
x→
?
x
?
)
(
(
(x
S
（4）))
P
x?
→
x
?
(
)
(
(x
R
能从（1）（2）（3）推出（4）。
证明：（1） P(x) 前提假设
（2）))
x?
→
P
?前提引入
x
(
)
(
Q
(x
（3）))
? T 规则：(1)，(2)
(x
Q
（4）))
Q
x
? P规则
?
x→
S
(
)
(x
(
（5）)
S T 规则：(3)，(4)
(x
（6）))
R
x
→
? P规则
x?
S
)
(
(x
(
（7）)
?拒取式
R
(x
（8）))
P
x?
→
? UG规则
x
R
)
(
(x
(
#include
} } j=count; if(k==j)return; count=k; for(int i=1;i
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，， =，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? （5）)(y x yP x ， ?? （6）)(y x xP y ， ?? 解：
命题逻辑和谓词逻辑习题课的题目及参考 答案 说明：红色标注题目可以暂且不做 命题逻辑和谓词逻辑习题课的题目 一、填空 1、若P，Q，为二命题，Q P→真值为0 当且仅当。2、命题“对于任意给定的正实数，都存 在比它大的实数”令F(x)：x为实数，:) , (则命题的逻辑谓词公式y L> x x y 为 。
3、谓词合式公式)( xP? ?的前束范式 x → ) (x xQ 为。 4、将量词辖域中出现的 和指导变元交换为另一变元符号，公式 其余的部分不变，这种方法称为换名规 则。 5、设x是谓词合式公式A的一个客体变 元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为ES。 6．设P，Q 的真值为0，R，S的真值为1，则 → ∨ Q P? ∨ ?的真值 → ∧ ? (S ))) ( R ( ) P R ( = 。 7．公式P ∧) ( ) (的主合取范式为 ∨ R S R P? ∨ ∧
。 8．若解释I的论域D仅包含一个元素，则)( xP? → ?在I下真值为 xP ) (x x 。 9. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 10. 论域D={1，2}，指定谓词P 则公式),(x y ?真值 x? yP 为。 11.P，Q真值为0 ；R，S真值为1。则
∧ wff∧ R ∨ → )) ∧的真值∨ S P )) P ) ( ( (( Q R (S 为 。 12. R ?) ) ((的主合取范式 ∧ R Q ∨ P wff→ 为 。 13.设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词))) x y O P y ?的自然语言是 → ? wff∧ x ( ) ( N ( , y ( (x ) 。 14.谓词)),,( x y z P x z ?的前束 ? P ? ∧ → wff? y ) , ( , )) y ( z ( uQ x (u 范式为 。
谓词演算的 推理理论
在谓词逻辑中，除了命题逻辑中的推理规则继续有效外，还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则（全称量词消去规则）US ： 例1 取个体域为实数域，F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号，c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c )
2 . 全称推广规则（全称量词引入规则） UG： P(x) ∴ (?x)P(x) 其中x是个体变项符号，且不在前提的任何公式中 自由出现. 3. 存在指定规则（存在量词消去规则） ES： (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量，不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现， 换句话说，此c是在该推导之前从未使用过的.
4. 存在推广规则（存在量词引入规则) EG： P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号.
谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则： (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则
1)在推导的过程中，可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词，可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时，此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中，对消去量词的公式或公式中没含量词的子公 式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中，对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式.
离散数学作业 作业11——第3章谓词逻辑 1. 符号化下列命题并推证其结论。 每个大学生不是文科学生就是理工科学生，小张不是理工科学生，因此如果小张是大学生，则他就是文科生。 解：a：小张；M(x):x是大学生；F(x): x是文科生；G(x): x是理工科学生，则符号化为 (x)(M(x)F(x)∨G(x))，┐G(a)M(a) F(a) (1) M(a) P（附加前提） (2) (x)(M(x)F(x)∨G(x)) P (3) M(a)F(a)∨G(a) (2),US (4) ┐M(a)∨F(a)∨G(a) (3),等值演算 (5) F(a)∨G(a) (1),(4),析取三段论 (6) ┐G(a) P (7) F(a) (5),(6),析取三段论 (8) M(a) F(a) (1),(7),CP规则 注：也可采用直接证法。 2. 符号化下列命题并推证其结论。 所有的主持人都是有风度的，黎明既是学生又是主持人，所以有一些学生是有风度的。 解：S(x): x是学生；Z(x): x是主持人；F（x）：x是有风度的；a：黎明。
(x)(Z(x)F(x))，S(a)Z(a)(x) (S(x)F(x)) (1) (x)(Z(x)F(x)) P (2) Z(a)F(a) (1),US (3) S(a)Z(a) P (4) S(a) (3),化简 (5) Z(a) (3),化简 (6) F(a) (2),(5),假言推理 (7) S(a)F(a) (4),(6),合取引入 (8) (x) (S(x)F(x)) （7），EG 3．在一阶谓词逻辑中构造下面推理的证明。 前提：(x)(F(x)∨G(x))，(x)(F(x)→H(x))， 结论：(x)(H(x)→G(x))。 证明：反证法 (1)(x)(H(x)→G(x)) 附加前提 (2)(x)(H(x)→G(x)) (1),量词否定等值式 (3)(H(c)→G(c)) (2), ES (4)(H(c) ∨G(c)) (3), 等值演算 (5)H(c)G(c) (4), 等值演算 (6)H(c) （5），化简 (7)G(c) （5），化简 (8)(x)(F(x)∨G(x)) P (9)F(c)∨G(c) （8），US
2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-）
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词: 表示任意的, 所有的, 一切的等 如x 表示对个体域中所有的x 存在量词: 表示存在, 有的, 至少有一个等 如x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a)
例2 在一阶逻辑中将下面命题符号化 (1) 人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域. 解：(a) (1) 设G(x)：x爱美, 符号化为x G(x) (2) 设G(x)：x用左手写字, 符号化为x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 (1) x (F(x)G(x)) (2) x (F(x)G(x)) 这是两个基本公式, 注意这两个基本公式的使用. 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解注意: 题目中没给个体域, 一律用全总个体域 (1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或 x y(F(x)G(y)L(x,y)) 两者等值 (2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值 几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不能随便颠倒 否定式的使用 思考： ①没有不呼吸的人 ②不是所有的人都喜欢吃糖 ③不是所有的火车都比所有的汽车快 以上命题应如何符号化？ 2.2 一阶逻辑合式公式及解释字母表 定义字母表包含下述符号： (1) 个体常项：a, b, c, …, a i, b i, c i, …, i1 (2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1 (3) 函数符号：f, g, h, …, f i, g i, h i, …, i1 (4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1 (5) 量词符号：, (6) 联结词符号：, , , , (7) 括号与逗号：(, ), ， 定义项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n
2.4 归结原理 本节在上节的基础上，进一步具体介绍谓词逻辑的归结方法。谓词逻辑的归结法是以命题逻辑的归结法为基础，在Skolem 标准性的子句集上，通过置换和合一进行归结的。 下面先介绍一些本节中用到的必要概念： 一阶逻辑：谓词中不再含有谓词的逻辑关系式。 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 量词符号：, 归结原理正确性的根本在于，如果在子句集中找到矛盾可以肯定命题是不可满足的。 2.4.1 合一和置换 置换：置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义： 置换是形如{t1/x1, t2/x2, …, t n/x n}的有限集合。其中，x1, x2, …, x n是互不相同的变量，t1, t2, …, t n是不同于x i的项（常量、变量、函数）；t i/x i表示用t i置换x i，并且要求t i与x i不能相同，而且x i
不能循环地出现在另一个t i中。 例如 {a/x，c/y，f(b)/z}是一个置换。 {g(y)/x，f(x)/y}不是一个置换，原因是它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。但在{g(y)/x，f(x)/y}中，它用g(y)置换x，用f(g(y))置换y，既没有消去x，也没有消去y。若改为{g(a)/x，f(x)/y}就可以了。 通常，置换用希腊字母θ、σ、α、λ来表示的。 定义：置换的合成 设θ＝{t1/x1, t2/x2, …, t n/x n}，λ＝{u1/y1, u2/y2, …, u n/y n}，是两个置换。则θ与λ的合成也是一个置换，记作θ·λ。它是从集合{t1·λ/x1, t2·l/x2, …, t n·λ/x n, u1/y1, u2/y2, …, u n/y n} 即对ti先做λ置换然后再做θ置换，置换xi 中删去以下两种元素： i. 当t iλ＝x i时，删去t iλ/x i(i = 1, 2, …, n); ii. 当y i∈{x1,x2, …, x n}时，删去u j/y j(j = 1, 2, …, m) 最后剩下的元素所构成的集合。 例： 设θ＝{f(y)/x, z/y}，λ＝{a/x, b/y, y/z}，求θ与λ的合成。 解： 先求出集合
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ， ?? （4）)(y x yP x ，??
河南城建学院 《人工智能》实验报告 实验名称：实现基于谓词逻辑的归结原理 成绩：____ 专业班级： 学号： 姓名： 实验日期：20 14 年 05 月 13日 实验器材：一台装PC机。 一、实验目的 熟练掌握使用归结原理进行定理证明的过程，掌握基于谓词逻辑的归结过程中，子句变换过程、替换与合一算法、归结过程及简单归结策略等重要环节，进一步了解机器自动定理证明的实现过程。 二、实验要求 对于任意给定的一阶谓词逻辑所描述的定理，要求实现如下过程： (1) 谓词公式到子句集变换； (2) 替换与合一算法； (3) 在某简单归结策略下的归结。 三、实验步骤 步1 设计谓词公式及自居的存储结构，即内部表示。注意对全称量词?x和存在量词?x可采用其他符号代替； 步2 实现谓词公式到子句集变换过程； 步3 实现替换与合一算法； 步4 实现某简单归结策略；
步5 设计输出，动态演示归结过程，可以以归结树的形式给出； 步6 实现谓词逻辑中的归结过程，其中要调用替换与合一算法和归结策略。 四、代码 谓词公式到子句集变换的源代码： #include ●镇江的夏天既炎热又潮湿 解：定义谓词 hot(X,Summer)：X地的夏天很炎热 wet(X,summer)：X地的夏天很潮湿 该知识可以表示为 hot(Zhenjiang,summer)∧wet(Zhenjiang,summer) ●有人每天下午都去打篮球。 解：定义谓词 P(x)：x是人 B(x)：x打篮球 ? A(y)：y是下午 将知识用谓词表示为： (?x)(?y) (A(y)→B(x)∧P(x)) ●新型计算机速度又快，存储容量又大 解：定义谓词 NC(x)：x是新型计算机 F(x)：x速度快 B(x)：x容量大 将知识用谓词表示为： (?x) (NC(x)→F(x)∧B(x)) ●不是每个信息系的学生都喜欢在计算机上编程序。解：定义谓词 S(x)：x是信息系学生 L(x, pragramming)：x喜欢编程序 U(x,computer)：x使用计算机 将知识用谓词表示为： ?(?x) (S(x)→L(x, pragramming)∧U(x,computer)) ●所有的消防车都是红色的 解: 定义谓词 Fireengine(x) : x是消防车 Color(x, y) : x的颜色是y red:表示红色 该知识可以表示为： (?x)( Fireengine(x))→Color(x, red) 对于所有的x, 如果x是消防车，那么x的颜色是红色的●所有的自然数，不是奇数就是偶数 解：定义谓词 N(x) : 表示x是自然数 O(x) : 表示x是奇数 E(x) : 表示x是偶数 该知识可表示为： (?x)( N(x))→(O(x) ∨E(x)) ●305房间有个物体 解：定义谓词 In（x，y）：x在y里面 Room（x）：x是房间 r305：305房间 （?x）In（x，Room（r305）） ●每个车间都有一个人负责 有一个人是所有车间的负责人 解：定义谓词： Workshop（x）：x是个车间 Head（y,x）: y是x的负责人 以上知识可表示为： (?x)(?y)( Workshop（x）→Head（y,x）) (?y)(?x)( Workshop（x）→Head（y,x）) 1. 将下列命题用谓词符号化。 4) 2 或 3 是质数。 5)除非李键是东北人，否则他一定怕冷。 解： (1) 令 P( x) ：x 学过英语， Q(x) ：x 学过法语， c ：小王，命题符号化为 P(c) Q(c) (2) 令P(x,y)：x 大于 y, 命题符号化为 P(2,4) P(2,3) (3) 令 P(x)：x 是偶数，命题符号化为 P(3) (4) 令 P(x)：x 是质数，命题符号化为 P(2) P(3) (5) 令 P(x)：x 是北方人； Q(x)：x 怕冷； c ：李键；命题符号化为 Q(c) P(x) 2. 设个体域 D {a ，b ，c} ，消去下列各式的量词。 (1) x y(P(x) Q(y)) (2) x y(P(x) Q(y)) (3) xP(x) yQ(y) (4) x(P(x ，y) yQ(y)) 解： (1) 中 A(x) y(P(x) Q( y)) ，显然 A(x)对y 是自由的，故可使用 UE 规则，得到 A(y) y(P(y) Q(y)) ， 因此 x y(P(x) Q(y)) y(P(y) Q( y)) ，再用 ES 规则， y( P( y) Q(y)) P(z) Q(z)，z D ，所以 x y(P(x) Q(y)) P(z) Q(z) (2)中 A(x) y(P(x) Q( y)) ，它对 y 不是自由的，故不能用 UI 规则，然而，对 A( x)中约束变元 y 改名z ，得到 z(P(x) Q( z)) ，这时用 UI 规则，可得： x y(P(x) Q(y)) x z(P(x) Q(z)) z(P(x) Q(z)) 3) 略 4) 略 3. 设谓词 P(x ，y)表示“x 等于 y ”，个体变元 x 和y 的个体域都是 D {1，2，3} 。求下列各式 的真值。 (1) xP( x ，3) (2) yP(1，y) (3) x yP(x ，y) (4) x yP( x ，y) (5) x yP(x ，y) (6) y xP(x ，y) 解： (2) 当 x 3时可使式子成立，所以为 Ture 。 (3) 当 y 1 时就不成立，所以为 False 。 谓词逻辑习题 1) 小王学过英语和法语。 2) 2大于3仅当 2大于 4。 3) 3 不是偶数。 1、设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个布尔表达式，试写出),,(321x x x E 的析取范式和合取范式。 答： 析取范式：)()() ()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧= 合取范式：)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨∨= 2．设P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比y 重，则命题“大象比老鼠重”的符号化为 答： ?x ?y ( (P(x) ∧ Q(x)) → R(x,y)) 3．设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老 师”符号化为（ B ）。 A 、)),()((y x A x L x →?； B 、))),()(()((y x A y J y x L x ∧?→? ； C 、)),()()((y x A y J x L y x ∧∧??； D 、)),()()((y x A y J x L y x →∧?? 。 4．下列各式中哪个不成立（ A ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 5．用推理规则证明)()(a G a P ∧?是 ))()((,)(,))()((, )))()(()((x G x S x a S a R a Q x R x Q x P x ??∧?∧→?的有效 结论。 证明：（1） ))()(()(x P x Q x xP ∧→? P （2） ))()(()(a P a Q a P ∧→ US(1) (3) ))()((a R a Q ∧? P 谓词逻辑-归结原理例题 习题3.5, 1. (1) ()P x ：x 是大学生 ()Q x ：x 是诚实的 则命题可表示为： 已知：1:(()())G x P x Q x ?→， 2:()G Q a ? 证明：()P a ? 习题3.5, 1. (2) 将下面的命题符号化，并证明之：已知每一个运动员都是强壮的，而每一个既强壮又聪明的人在他所从事的事业中都能获得成功，彼得是运动员并且是聪明的，证明彼得在他的事业中将会成功。 提示：定义谓词 ()P x ：x 是运动员 ()Q x ：x 是强壮的 ()R x ：x 是聪明的 ()S x ：x 在他所从事的事业中获得成功。 则命题可表示为： 已知：1:(()())G x P x Q x ?→， 2:(()()())G x Q x R x S x ?∧→，()P a ，()R a 证明：()S a 提示：可用归结原理证明：（1）先把公式都化成Skolem 范式，（2）然后利用US ，ES 将公式中的量词除去，（3）化成合取范式，（4）化成蕴涵式，（5）化成子句集（结论用否定加入）， （6）进行归结，直至引出矛盾。 可化成如下子句集： {()()P x Q x →，()()()Q x R x S x ∧→，()P a →，()R a →，}()S a → 归结： （1）()()P x Q x → （2）()P a → （3）()Q a → 由（1）（2） （4）()()()Q x R x S x ∧→ （5）()()R a S a → 由（3）（4） （6）()R a → （7）()S a → 由（5）（6） （8）()S a → （9） 由（7）（8） 习题3.5, 1. (3) ()E x ：x 进入国境 ()V x ：x 是重要人物 ()C x ：x 是海关人员 ()P x ：x 是走私者 (,)S x y ：y 检查x 已知： 1:((()())(()(,)))G x E x V x y C y S x y ?∧?→?∧， 2:(()()((,)()))G x P x E x y S x y P y ?∧∧?→ 3:(()())G x P x V x ?→? 证明：(()())x P x C x ?∧ 先化成子句集： {} 1((()())(()(,))) ((()())(()(,))) ((()()())(()()(,))) ()()(()),()()(,())G x E x V x y C y S x y x y E x V x C y S x y x y E x V x C y E x V x S x y E x V x C f x E x V x S x f x =??∧?∨?∧=???∨∨∧=???∨∨∧?∨∨?→∨→∨ {}2(()()((,)()))(),(),(,)()G x y P x E x S x y P y P a E a S a y P y =??∧∧→?→→→ 注意G2，如果理解成(()()(,)())x y P x E x S x y P y ??∧∧→，则还需有条件(()())x P x E x ?∧，最后同样能得到如上的子句集{}(),(),(,)()P a E a S a y P y →→→。不 谓词逻辑习题及答案 收集于网络，如有侵权请联系管理员删除 谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4） ))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧??α，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧?α，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧??α （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨?α （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? 2.2命题逻辑的归结 2.2.1命题逻辑基础 逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。 本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。 描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。 命题：非真即假的简单陈述句 在命题逻辑里，单元命题是基本的单元或作为不可再分的原子。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。 －数理逻辑的基本定义 下面所列的是一些数理逻辑中重要的定义，在后面的分 析中要用到： ·合取式：p与q，记做p∧q ·析取式：p或q，记做p∨q ·蕴含式：如果p则q，记做p→q ·等价式：p当且仅当q，记做p q ·若A无成假赋值，则称A为重言式或永真式； ·若A无成真赋值，则称A为矛盾式或永假式； ·若A至少有一个成真赋值，则称A为可满足的； ·析取范式：仅由有限个简单合取式组成的析取式 ·合取范式：仅由有限个简单析取式组成的合取式 －数理逻辑的基本等值式 下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。 ·交换律：p∨q q∨p； p∧q q∧p ·结合律：(p∨q)∨r p∨(q∨r); (p∧q)∧r p∧(q∧r) ·分配律：p∨(q∧r)(p∨q)∧(p∨r)； p∧(q∨r)(p∧q)∨(p∧r)·双重否定律：p～～p ·等幂律：p p∨p；p p∧p 说明：红色标注题目可以暂且不做 命题逻辑和谓词逻辑习题课的题目 一、填空 1、若P，Q，为二命题，真值为0 当且仅 当。2、命题“对于任意给定的正实数，都存 在比它大的实数”令F(x)：x为实数，则命题的逻辑谓词公式为 。 3、谓词合式公式的前束范式 为。 4、将量词辖域中出现的 和指导变元交换为另一变元符号，公式 其余的部分不变，这种方法称为换名规 则。 5、设x是谓词合式公式A的一个客体变 元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为ES。 6．设P，Q 的真值为0，R，S的真值为1，则 的真值= 。 7．公式的主合取范式为 。 8．若解释I的论域D仅包含一个元素，则在I下真值为 。 9. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 10. 论域D={1，2}，指定谓词P 则公式真值为。 11.P，Q真值为0 ；R，S真值为1。则的 真值为 。 12. 的主合取范式 为 。 13.设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 。 14.谓词的前束范式为 。 二、选择 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； B、； C、当且仅当x和y都大于0； D、我 正在说谎。 2、下列各命题中真值为真的命题有 （）。 A、2+2=4当且仅当3是奇数； B、 2+2=4当且仅当3不是奇数； C、2+2≠4当且仅当3是奇数； D、 2+2≠4当且仅当3不是奇数； 3、下列符号串是合式公式的有（） A、； B、； C、； D、。 4、下列等价式成立的有（）。 A、； B、； C、； D、。 5、若和B为wff，且则（）。 A、称为B的前件； B、称B为的有效结论 ? 离散数学基础 2017-11-19?定义：谓词逻辑的推理结构 ?设有谓词公式 A、B，若在令 A 为真的任一解释下，B 亦为真，则说 B 是 A 的逻辑推论，或称推理结构 A├ B 是正确的（或者有效的），记为 A ? B。 ?例1：所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实 数。 ?解：设 P(x)：x 是整数。 Q(x)：x 是有理数。 R(x)：x 是实数。 形式化： ① (?x)(P(x) →Q(x)) ②(?x)(Q(x) →R(x)) ③(?x)(P(x) →R(x)) 推理结构： ①, ② ├ ③ ?例2：人总是要死的，苏格拉底是人，所以苏格拉底也是要死的。 ?解：设 P(x)：x 总是要死的。 Q(x)：x 是人。 形式化： ① (?x)(Q(x) →P(x)) ②Q(苏格拉底) ③P(苏格拉底) 推理结构： ①, ② ├ ③ ?例3：有一个人又高又胖，所以必有一个高个子和一个胖子。 ?解：设论域为人的集合 P(x)：x 是高的。 Q(x)：x 是胖的。 推理结构： (?x)(P(x)∧Q(x)) ├ (?x)P(x)∧(?x)Q(x) ?定理：演绎定理 ?设谓词公式 A、B，如果从 A 应用推理规则得到 B，并且在推出过程中，A 中 的自由变量保持不变，则A→B 是普遍有效的。 ?由于普遍有效性的不可判定性，在谓词逻辑中应用推理规则更为重要。 ?推理定理 ?若干常用的正确的推理形式： (1)(?x)P(x)∨(?x)Q(x) ? (?x)(P(x)∨Q(x)) (2)(?x)(P(x)∧Q(x)) ? (?x)P(x)∧(?x)Q(x) (3)(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) (4)(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) (5)(?x)(?y)P(x, y) ? (?y)(?x)P(x, y) (6)(?x)(?y)P(x, y) ? (?y)(?x)P(x, y) (7)(?x)(?y)P(x, y) ? (?x)(?y)P(x, y) ?推理定理 ?(3) 证：(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) ?设 (?x)(P(x)→Q(x))=T ?当 (?x)P(x)=T时，对任意 x0，有P(x0)=T。 ?对此 x0，由假设知，P(x0)→Q(x0)=T ?故此时只能 Q(x0)=T ?从 x0 的任意性得 (?x)Q(x)=T ?即 (?x)P(x)→(?x)Q(x)=T ?故上述推理形式是有效的。 ?推理定理 ?(5) 证： (?x)(?y)P(x, y) ? (?y)(?x)P(x, y) ?设 (?x)(?y)P(x, y)=T ?即任意的 x 与所有的 y 都有 P(x, y)=T ?则对任意的 x 与某一固定的 y0，都有 P(x, y0)=T ?即 (?x)P(x, y0)=T ?故 (?y)(?x)P(x, y)=T ?即上述推理形式是有效的。 ?推理规则 ?在谓词逻辑的推理中，可以直接引用命题逻辑的推理规则。我们还需要建立一些新的推理规则处理与个体和量词相关的推理过程。 ?(1) 全称量词消去 US ?① (?x)A(x) ? A(y) –假设 y 不在 A(x) 中约束出现 ?② (?x)A(x) ? A(c) –假设 c 是个体域中的任一常量 ?(2) 全称量词引入 UG一阶谓词逻辑题目
谓词逻辑习题及答案
谓词逻辑-习题与答案
谓词逻辑_归结原理习题
谓词逻辑习题及答案教学内容
人工智能原理教案02章 归结推理方法2.2 命题逻辑的归结
命题逻辑和谓词逻辑习题课的题目及参考答案
05-L.01 谓词逻辑的推理结构
相关主题
文本预览