离散数学题目及标准答案
————————————————————————————————作者：————————————————————————————————日期：
数理逻辑习题
判断题
1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →?→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧?∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →?=→? （ √ ）
6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）
8．))()((x G x F x →?是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ?→?是永真式（ √ ）
11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）
13．))()((x G x F x →?是永假式 （ × ）
14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨? （ × ） 18．命题公式 )(r q p →∨?的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →?是闭式（ × ）
单项选择题
1． 下述不是命题的是（ A ）
A．花儿真美啊! B．明天是阴天。
C．2是偶数。D．铅球是方的。
2．谓词公式（?y）（?x）（P（x）→R（x,y））∧?yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元
C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）
A．p→ （p∨q）B．（p∨┐p）→q
C．q∧┐q D．p→┐q
4．下列语句中不是
．．命题的只有（A ）
A．花儿为什么这样红？B．2+2=0
C．飞碟来自地球外的星球。D．凡石头都可练成金。
5．在公式)
y
x
Q
P
y
P
y
?
∧
→
x?
?中变元y是（ B ）
z
(
))
)
(
,
y
(
)(
(z
)
)(
(
,
A．自由变元B．约束变元
C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6．下列命题公式为重言式的是（ A ）
A．p→ （p∨q）B．（p∨┐p）→q
C．q∧┐q D．q→┐p
7．给定如下4个语句:
（1）我不会唱歌。（2）如果天不下雨,我就上街。
（3）我每天都要上课。（4）火星上有人吗?
其中不是复合命题的是（ B ）
A．（1）（4）B．（3）（4）
C．（1）（3）D．（1）（3）（4）
8．下列含有命题p，q，r的公式中，是特异（主）析取范式的是（D）A．（p ∧ q ∧ r）∨（?p ∧ q）B．（p ∨ q ∨ r）∧（?p ∧ q）
C．（p ∨ q ∨ r）∧（?p ∨ q ∨ r）D．（p ∧ q ∧ r）∨（?p ∧ q ∧ r）9．设个体域为整数集,则下列公式中值为真的是（ A ）。
A．（?y）（?x）（x·y=2）B．（?x）（?y）（x·y=2）
C．（?x）（x－y=x）D．（?x）（?y）（x+y=2y）
10．下述不是命题的是（D ）
A ． 花儿是红色的
B ． 月亮上有水
C ． 3是偶数
D ． 3>x
11． 用P 表示：天下大雨；Q 表示：他乘公共汽车上班。将“如果天下大雨，他就乘公共汽车上班。”符号化正确的是（ A ）
A ．P →Q
B ．Q →P
C ．P ∧Q
D ．P ∨Q
12．谓词公式（?y ）（?x ）（P （x ）→R （x,y ））∧?xQ （x,y ）中变元y （ C ） A ． 是自由变元但不是约束变元 B ． 是约束变元但不是自由变元 C ． 既是自由变元又是约束变元
D ． 既不是自由变元又不是约束变元
13．下列命题公式为永假式的是（ C ）
A ．p → （p ∨q ）
B ．p ∧q →q
C ．q ∧┐q
D ．p →q
14．下列语句中，不是命题的是（ C ） A ． 铅球不是球。
B ． 要是他不上场，我们就不会输。
C ． 刘翔跨110米栏用了不到13秒钟，你说他是不是运动健将呢?
D ． 刘翔跨110米栏用了不到13秒钟，他是一个真正的运动健将。 13．关于命题变元P 和Q 的成假赋值为01对应的极大项是（ C ）
A ．┐P ∧Q
B ．┐P ∨Q
C ．P ∨┐Q
D ．P ∧┐Q
14．谓词公式（?y ）（?x ）（P （x ）→R （x,y ））∧?yQ （x,y ）中变元y （ B ） A ． 是自由变元但不是约束变元 B ． 是约束变元但不是自由变元 C ． 既是自由变元又是约束变元
D ． 既不是自由变元又不是约束变元
15． 设:p 开关A 开，q ：开关B 开,则“开且只开A 、B 中一个开关”的命题公式是（ C ） A ． q p ?∧ B ． q p ∧?
C ． （q p ?∧）∨（q p ∧?）
D ． （q p ?∧）∧（q p ∧?） 16．下列等价式正确的是（ C ）
A ．┐)()(x A x ???┐A
B ．A y x A y x ))(())((?????
C ．┐)()(x A x ???┐A
D ．)()()()())()()((x B x x A x x B x A x ?∨??∧? 17．在论域D={a,b}中与公式（x ?）A （x ）等价的不含存在量词的公式是（ B ） A ．)b (A )a (A ∧ B ． )b (A )a (A ∨ C ． )b (A )a (A →
D ． )a (A )b (A →
18．下列命题公式为重言式的是（ C ）
A ．p→ （p ∧q ）
B ．（p ∨┐p ）→q
C ．p ∨┐p
D ．p→┐q
19．下列命题中真值为1的是（ B ）
A ．若2+2=4, 则3+3≠6
B ．若2+2=4, 则3+3=6
C ．2+2=4, 当且仅当3+3≠6
D ．2+2≠4, 当且仅当3+3=6 20．设个体域为整数，下列公式中真值为1的是（ B ） A ． ?x ?y （x + y = 1） B ． ?x ?y （x + y = 1） C ． ?x ?y （x + y = 1） D ． ? ?x ?y （x + y = 1 21． 下列命题中真值为0的是（ C ）
A ．若2+2=5, 则3+3≠6
B ．若2+2=4, 则3+3=6
C ．2+2=5, 当且仅当3+3≠6
D ．2+2≠4, 当且仅当3+3=6 22．谓词公式)),()(()((y x L y
E y x M x →?∧?中变元x （ C ） A ． 是自由变元但不是约束变元 B ． 是约束变元但不是自由变元 C ． 既是自由变元又是约束变元
D ． 既不是自由变元又不是约束变元
23．设个体域为整数，下列公式中真值为1的是（ B ） A ． ?x ?y （x + y = 1）
B ．?x ?y （x + y = 1）
C ． ?x ?y （x + y = 1）
D ．? ?x ?y （x + y = 1
填空题
1．n 个命题变元的极小项有 2n 个。
2．设3:,022:q p =+是奇数，则q p →的真值是 1 。 3．含n 个命题变项的重言式的特异（主）合取范式为 1 4．设个体域为整数集合Z ，命题3(=+??y x y x ）的真值为 1 5．公式?xP （x ）∨?xQ （x ）的前束范式为 ?x(P(x) Q(x))
6．设p ：我很累，q ：我去学习，命题：“我很累，但我还去学习”的符号化为 q p ∧ 7．设P 表示：天下大雨；Q 表示：他乘公共汽车上班，则命题“如果天下大雨，他就乘公共
汽车上班。”的符号化是 q p →
8．设P ：2+2＝4，Q ：3是奇数,则命题“2+2＝4，当且仅当3是奇数．”的符号化为 Q P ?
9． 含n 个命题变项的矛盾式的特异（主）析取范式为 0 10．命题公式q p ?成假的解释是 01,10
11．q
p?的成假解释为01,10
计算题
1．求)
(
)
(x
xG
x
xF??
∧
?的前束范式。
解：
()()
()()()
()()
()()
3
xF x xG x
xF x x G x
x F x G x
?∧??
??∧??
??∧?
分
3分
2．求r
q
p→
∧
?)
(的真值表，并写出它的特异（主）析取范式和特异（主）合取范式。解：真值表如下：
故主析取范式为
()()()()() p q r p q r p q r p q r p q r
?∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧
主合取范式为
()()()
p q r p q r p q r
∨∨∧∨?∨∧?∨∨
3．求命题公式的p
r
q
p→
→
∨)
)
((成真赋值。
解：()
()
p q r
∨→p
→
=()
()
p q r p
?∧?∨→
=()
()
p q r p
??∧?∨∨
=
()()p q r p ∨∧?∨
=()()p r q r p ∧?∨∧?∨ 成真赋值 100，010，101，110，111
4．将公式)())()((x xF y yR x xP ?→?∨?化为前束范式。 解： ()()()
()xP x yR y xF x ?∨?→?
()()()()x y P x R y xF x ???∨→?
()()()
()x y P x R y zF z ???∨→? ()()()
()x y z P x R y F z ????∨→
5．求公式 （p ∨（q ∧r ））→（p ∧q ∧r ） 的特异（主）析取范式，并求成真赋值。
解：()()()r q p r q p ∧∧→∧∨
()()()()()()()()()
()()()()
r q p r q p r q p r q p r q p r p q p r q p r q p r q p r q p ∧∧∨?∧∧?∨∧?∧?∨?∧?∧??∧∧∨?∧?∨?∧??∧∧∨?∨?∧??∧∧∨∧∨??
成真赋值为：000，001，010，111
6．用谓词公式表示“有人喜欢吃所有的食物”。 解：()x x M :是人，()y y N :是食物
()x y x H :,喜欢吃y 符号化：()()()()()y x H y N y x M x ,→?∧?
7． 用作真值表方法确定下列命题公式的类型： ).())()((q p p q q p ∨?→→∧→ 解： 设原式=A ，真值表如下：
()()00111
010********
1
1
1
1
p q p q q p p q A →∧→?∨ 则原式为永真式。
8．用逻辑式表示“某些计算机与某些外部设备之间不能相联”。 解：()C x ：x 是计算机，()D x ：x 为外部设备，
(),P x y ：x 与y 相联
符号化为)),()()((y x P y D x C y x ?∧∧??
9．在个体域},{b a D =，消去公式))()((y yG x F x ?∧?的量词。 解：原式＝))()(())()((y yG b F y yG a F ?∧∧?∧
＝)))()(()(()))()(()((b G a G a F b G a G a F ∨∧∧∨∧ ＝))()(())()((b G a G b F a F ∨∧∧
10． 给定一阶逻辑公式)(),(y yQ y x xP ?→?，求该公式的前束范式。 解：原式()(),xP x y zQ z ??→? ()()()
,x z P x y Q z ???→
11．用逻辑式表示“某些计算机与某些外部设备之间能相联”。 解： ()C x ：x 是计算机，()D x ：x 为外部设备，
(),P x y ：x 与y 相联
符号化为)),()()((y x P y D x C y x ∧∧??
12．用等值演算求命题公式┐（p ∨q ）∧（q→r ）的特异（主）析取范式，并判断该公式的
类型。
解：原式()()p q q r ??∧?∧?∨ ()()p q q p q r ??∧?∧?∨?∧?∧ ()()p q p q r ??∧?∨?∧?∧ ()()p q r p q r ??∧?∧∨?∧?∧? 公式类型为非永真的可满足式。
13．设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→，试将G 化成与其等价的前束范式。
解：)))()((),((x R z zQ y x P y x G →?→???=
＝)))()((),((x R z Q z y x P y x →?→??? ＝)))()((),((x R z Q y x P z y x →→????
14． 设公式G 的真值表如下，试求出G 的特异（主）析取范式和特异（主）合取范式。
p q r G 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1
解：
主析取范式 )()()()(r q p r q p r q p r q p ∧?∧∨∧∧?∨?∧∧?∨?∧?∧? 主析取范式)()()()(r q p r q p r q p r q p ?∨?∨?∧∨?∨?∧∨∨?∧?∨∨
15．求公式),()(y x yG x xF ?→?的前束范式。 解：原式＝),()(y z yG x xF ?→? ＝)),()((y z G x F y x →??
证明题
1．用等值演算证明等值式r q p r q r p →∨=→∧→)()()(。 证明： 右边
左边=→∨?∨∨??∨?∧??∨?∧??r q p r q p r q p r q pvr )()()()()(
2．设R Q P ,,是三个命题，构造下列推理证明：
前提：P R Q Q P ?→∨,, 结论：R 证明：
()()()()()()()()
()()()
12312445344P P Q Q Q R R
?∨→前提引入前提引入
析取三段论
分前提引入
假言推理
分
3．证明下列推断
前提：)(s q p →→，q ，p r → 结论：s r →
证明：（1）r 附加前提引入 （2）p r →? 前提引入 （3）p (1)（2）拒取 （4）()p q s →→ 前提引入
（5）q s → (3)(4)假言推理 （6）q 前提引入 （7）s (5)(6) 假言推理
4．用构造证明法证明下列推理：
前提：)(,)(,s p r r q q p ∧???∧∨?→ 结论：s ?
证明：
()s
1 否定结论引入
()
()s p ∧??2 前提引入
()s p ?∨3 ()2置换 ()p 4 ()1()3析取三段论 ()()r r p ?∧∨?5 前提引入 ()r p ∨?6 ()5简化 ()r ?7 ()5简化 ()r 8 ()4()6析取三段论 ()r r ?∧9 ()7()8合取
5．证明：q r p r q p ?→?∧=→→)()(。 证明：左边()p q r =?∨?∨ ()p r q =?∨∨? ()p r q =?∨∨?
()p r q =?∧?∨? ()p r q =∧?→?
＝右边
6．证明公式G ＝（（P→Q ） ∧（Q→P ）∧P ） →P 是永真式。 证明： P P P Q Q P G →∧∨?∧∨?=))()(( ＝P P Q P →∧∨?))((
＝P Q P P P →∧∨∧?))()(( ＝P Q P →∧)( ＝P Q P ∨?∨? ＝Q ?∨1
＝1 G 为永真式