2024年4月12日发(作者：图门蕴秀)
数理逻辑复习题
1.
将下列命题符号化
(1)
刘晓月跑得快，跳得高。
pAq,
其中，
p：
刘晓月跑得快，
q：
刘晓月跳得高。
(2)
老王是山东人或河北人。
pVq,
其中，
p：
老王是山东人，
q：
老王是河北人。
(3)
因为天气冷，所以我穿了羽绒服。
p-q，
其中，
p：
天气冷，
q：
我穿了羽绒服。
(4)
王欢与李乐组成一个小组。
P，
其中，
p：
王欢与李乐组成一个小组，是简单命题。
(5)
如果天下大雨，他就乘班车上班。
p
一
q，
其中，
p：
天下大雨，
q：
他乘班车上班。
(6)
只有天下大雨，他才乘班车上班。
p—q,
其中，
p：
他乘班车上班，
q：
天下大雨。
(7)
除非天下大雨，他才乘班车上班。
p
一
q，
其中，
p：
他乘班车上班，
q：
天下大雨。
2.
判断下列公式的类型：
(1) p—(pqVr)
(2) (p—iqfq
(3) q (q
一
r)/r
(4) (p—q)—(iq—ip)
(5) (p/r)7ip/iq)
(6) ((p—q)A(q—r))r(p—r)
(7) (p
一
q)—(r—'S)
答案：
(1)
、
(4)
、
(6)
为重言式。
(3)
为矛盾式。
(2)
、
(5)
、
(7)
为可满足式。
3.
用等值演算法证明下面等值式：
(1) -'(p <->q) O(p V q) A -'(p A q)
(2) (pA
_,
q)V(
_,
pAq)'ii
>
(pVq)A
_,
(pAq)
答案：
(1) ](p"q)
=1 ((P—q)A(q—p))
((-]pVq)A(-| qVp))
<=>(pA-|q)V(qA-| p)
<=>(pVq)A(pV-|P)A(-] qVq)A(-| pVq q)
<=>(pVq)A-| (pAq)
(2) (pA-]q)V(-|pAq)
<=>(pV-|P)A(pVq)A(-| qV-|P)A(q qVq)
O(pVq)A-j (pAq)
4.
求下列公式的主析取范式，再用主析取范式求合取范式:
(1) (p A q) V r
⑵(p—q)A(q—r)
答案：
(1)
miVm
3
Vm
5
Vm
6
Vm7<^4>MoAM2AM4
(2) m
0
Vm
1
Vm
3
Vm
7
O
,
M2AM4AM5AM
6
5.
用附加前提法证明下面各推理：
(1)
前提：
p
一
(q—r), s
一
p, q
结论：
s
一
r
证明：
附加前提引入
前提引入
①②假言推理
前提引入
③④假言推理
前提引入
⑤⑥假言推理
①s
②s—p
③p
④ P—(q—r)
⑤q—r
⑥q
⑦r
(2)
前提：
(pVq)^(rAs), (sVt)^u
结论：
p—u
证明：
附加前提引入
①附加
前提引入
②③假言推理
④化简
⑤附加
前提引入
⑥⑦假言推理
®p
②pVq
③(pVq)—(rAs)
④rAs
⑤s
⑥s Vt
⑦(sVt)—u
6.
®u
用归谬法证明下面推理：
(1
)
前提：
p—1 q,-| rVq, r/-| s
结论：
1 p
(1)
证明:
①p
结论否定引入
前提引入
①②假言推理
前提引入
③④析取三段论
前提引入
⑥化简
⑤⑦合取
②
P
—
-i q
③q
@-| rVq
⑤-]r
⑥r A~| s
⑦r
⑧rAr
⑧为矛盾式，由归谬法可知，推理正确。
(2)
前提：
pVq, p—r, q—s
结论：
rVs
证明：
1 (rVs)
pVq
p—r
q—s
rVs
@q (rVs)A(rVs)
⑥为矛盾式，所以推理正确。
结论否定引入
前提引入
前提引入
前提引入
②③④构造性二难
①合取
7.
给定解释
I
如下：
(a)
个体域
D ={3,4} o
(b) f(x)
为
f(3)=4, /(4)=3o
(c)
F(x,y)为
F(3,3)=F(4,4)=0, F(3,4)=F(4,3)=1
。
试求下列公式在
I
下的真值：
(1) Vx3yF(x,y)
(2) 3xVyF(x,y)
⑶ VxVy(F(x,y)
一
F(f(x),f(y)))
答案：⑴
Vx3yF(x,y) e>(F(3,3)VF(3,4)) A (F(4,3)VF(4,4))
=(OV1)
八
(lVO)e>l
(2) 3xVyF(x,y)
O (F(3,3) A F(3,4))V(F(4,3)A F(4,4)) O(0Al)V(lA0)O0
(3) VxVy(F(x,y)TF(f(x),f(y)))
O(F(3,3)
一
F(f(3),f(3)))
A(F(4,3)-F(f(4),f(3)))
A(F(3,4)—F(f(3),f(4)))
/(F(4,4)
一
F(f(4),f(4)))
0(0
一
O)A(1
一
1)A(1
一
1)A(O
一
0)G
8.
给定解释
I
如下：
(a)
个体域
Z)=N (N
为自然数)。
(b)
£>中特定元素
a=2
。
(c)
。上函数
f(x, y)=x+y,
g(x, y)=ry
。
(d)
£> 上谓词
F(x, y)- x=y«
说明下列公式在
I
下的含义，并指出各公式的真值:
(1) VxF(g(x,a),x)
(2) VxWy(FMS
力一
F(fW))
(3)
VxVy3z(F(/(xj),z)
(4)
2xF(f(x^c),g(x,
x))
(1) Vx(x-2=x),
真值为
Oo
(2) VxVy((x+2=y)—>(y+2=x)),
真值为
0
。
(3) Vx Vy 3 z(x+y=z),
真值为
1
。
(4) 3 x(x+x=x-x),M
值为
1
。
2024年4月12日发(作者：图门蕴秀)
数理逻辑复习题
1.
将下列命题符号化
(1)
刘晓月跑得快，跳得高。
pAq,
其中，
p：
刘晓月跑得快，
q：
刘晓月跳得高。
(2)
老王是山东人或河北人。
pVq,
其中，
p：
老王是山东人，
q：
老王是河北人。
(3)
因为天气冷，所以我穿了羽绒服。
p-q，
其中，
p：
天气冷，
q：
我穿了羽绒服。
(4)
王欢与李乐组成一个小组。
P，
其中，
p：
王欢与李乐组成一个小组，是简单命题。
(5)
如果天下大雨，他就乘班车上班。
p
一
q，
其中，
p：
天下大雨，
q：
他乘班车上班。
(6)
只有天下大雨，他才乘班车上班。
p—q,
其中，
p：
他乘班车上班，
q：
天下大雨。
(7)
除非天下大雨，他才乘班车上班。
p
一
q，
其中，
p：
他乘班车上班，
q：
天下大雨。
2.
判断下列公式的类型：
(1) p—(pqVr)
(2) (p—iqfq
(3) q (q
一
r)/r
(4) (p—q)—(iq—ip)
(5) (p/r)7ip/iq)
(6) ((p—q)A(q—r))r(p—r)
(7) (p
一
q)—(r—'S)
答案：
(1)
、
(4)
、
(6)
为重言式。
(3)
为矛盾式。
(2)
、
(5)
、
(7)
为可满足式。
3.
用等值演算法证明下面等值式：
(1) -'(p <->q) O(p V q) A -'(p A q)
(2) (pA
_,
q)V(
_,
pAq)'ii
>
(pVq)A
_,
(pAq)
答案：
(1) ](p"q)
=1 ((P—q)A(q—p))
((-]pVq)A(-| qVp))
<=>(pA-|q)V(qA-| p)
<=>(pVq)A(pV-|P)A(-] qVq)A(-| pVq q)
<=>(pVq)A-| (pAq)
(2) (pA-]q)V(-|pAq)
<=>(pV-|P)A(pVq)A(-| qV-|P)A(q qVq)
O(pVq)A-j (pAq)
4.
求下列公式的主析取范式，再用主析取范式求合取范式:
(1) (p A q) V r
⑵(p—q)A(q—r)
答案：
(1)
miVm
3
Vm
5
Vm
6
Vm7<^4>MoAM2AM4
(2) m
0
Vm
1
Vm
3
Vm
7
O
,
M2AM4AM5AM
6
5.
用附加前提法证明下面各推理：
(1)
前提：
p
一
(q—r), s
一
p, q
结论：
s
一
r
证明：
附加前提引入
前提引入
①②假言推理
前提引入
③④假言推理
前提引入
⑤⑥假言推理
①s
②s—p
③p
④ P—(q—r)
⑤q—r
⑥q
⑦r
(2)
前提：
(pVq)^(rAs), (sVt)^u
结论：
p—u
证明：
附加前提引入
①附加
前提引入
②③假言推理
④化简
⑤附加
前提引入
⑥⑦假言推理
®p
②pVq
③(pVq)—(rAs)
④rAs
⑤s
⑥s Vt
⑦(sVt)—u
6.
®u
用归谬法证明下面推理：
(1
)
前提：
p—1 q,-| rVq, r/-| s
结论：
1 p
(1)
证明:
①p
结论否定引入
前提引入
①②假言推理
前提引入
③④析取三段论
前提引入
⑥化简
⑤⑦合取
②
P
—
-i q
③q
@-| rVq
⑤-]r
⑥r A~| s
⑦r
⑧rAr
⑧为矛盾式，由归谬法可知，推理正确。
(2)
前提：
pVq, p—r, q—s
结论：
rVs
证明：
1 (rVs)
pVq
p—r
q—s
rVs
@q (rVs)A(rVs)
⑥为矛盾式，所以推理正确。
结论否定引入
前提引入
前提引入
前提引入
②③④构造性二难
①合取
7.
给定解释
I
如下：
(a)
个体域
D ={3,4} o
(b) f(x)
为
f(3)=4, /(4)=3o
(c)
F(x,y)为
F(3,3)=F(4,4)=0, F(3,4)=F(4,3)=1
。
试求下列公式在
I
下的真值：
(1) Vx3yF(x,y)
(2) 3xVyF(x,y)
⑶ VxVy(F(x,y)
一
F(f(x),f(y)))
答案：⑴
Vx3yF(x,y) e>(F(3,3)VF(3,4)) A (F(4,3)VF(4,4))
=(OV1)
八
(lVO)e>l
(2) 3xVyF(x,y)
O (F(3,3) A F(3,4))V(F(4,3)A F(4,4)) O(0Al)V(lA0)O0
(3) VxVy(F(x,y)TF(f(x),f(y)))
O(F(3,3)
一
F(f(3),f(3)))
A(F(4,3)-F(f(4),f(3)))
A(F(3,4)—F(f(3),f(4)))
/(F(4,4)
一
F(f(4),f(4)))
0(0
一
O)A(1
一
1)A(1
一
1)A(O
一
0)G
8.
给定解释
I
如下：
(a)
个体域
Z)=N (N
为自然数)。
(b)
£>中特定元素
a=2
。
(c)
。上函数
f(x, y)=x+y,
g(x, y)=ry
。
(d)
£> 上谓词
F(x, y)- x=y«
说明下列公式在
I
下的含义，并指出各公式的真值:
(1) VxF(g(x,a),x)
(2) VxWy(FMS
力一
F(fW))
(3)
VxVy3z(F(/(xj),z)
(4)
2xF(f(x^c),g(x,
x))
(1) Vx(x-2=x),
真值为
Oo
(2) VxVy((x+2=y)—>(y+2=x)),
真值为
0
。
(3) Vx Vy 3 z(x+y=z),
真值为
1
。
(4) 3 x(x+x=x-x),M
值为
1
。