离散数学题目及答案

数理逻辑习题

判断题

1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式p?(?p?q)是永真式 （ √ ） 3．命题公式(p?q)?p是永真式 （ √ ） 4．命题公式p??q?r的成真赋值为010 （ × ） 5．?xA(x)?B??x(A(x)?B) （ √ ）

6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p?(p?q)?p （ √ ）

8．?x(F(x)?G(x))是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． ?xF(x)??xG(x)是永真式（ √ ）

11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p?(p?q)?p （ √ ）

13．?x(F(x)?G(x))是永假式 （ × ）

14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若p:雪是黑色的，则公式p?q是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．公式p?q的特异（主）析取式为?p?q （ × ） 18．命题公式 ?p?(q?r)的成假赋值是110 （ √ ） 19．一阶逻辑公式?x(F(x)?G(x,y))是闭式（ × ）

单项选择题

1． 下述不是命题的是（ A ）

A． 花儿真美啊! B． 明天是阴天。 C． 2是偶数。 D． 铅球是方的。

2．谓词公式（?y）（?x）（P（x）→R（x,y））∧?yQ（x,y）中变元y （ B ） A． 是自由变元但不是约束变元 C． 既是自由变元又是约束变元

B． 是约束变元但不是自由变元 D． 既不是自由变元又不是约束变元

3．下列命题公式为重言式的是（ A ） A．p→ （p∨q） C．q∧┐q

4． 下列语句中不是命题的只有（ A ） ．．A．花儿为什么这样红？ C．飞碟来自地球外的星球。

B．2+2=0

D．凡石头都可练成金。 B．（p∨┐p）→q D．p→┐q

5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ B ） A．自由变元 B．约束变元

C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元 6．下列命题公式为重言式的是（ A ） A．p→ （p∨q） C．q∧┐q

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） B．（p∨┐p）→q D．q→┐p

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． x?3

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． 是自由变元但不是约束变元 C． 既是自由变元又是约束变元

B． 是约束变元但不是自由变元 D． 既不是自由变元又不是约束变元

13．下列命题公式为永假式的是（ C ）

A．p→ （p∨q） B．p∧q→q C．q∧┐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

D．p→q

14．谓词公式（?y）（?x）（P（x）→R（x,y））∧?yQ（x,y）中变元y （ B ） A． 是自由变元但不是约束变元 C． 既是自由变元又是约束变元

B． 是约束变元但不是自由变元 D． 既不是自由变元又不是约束变元

15． 设p:开关A开，q：开关B开,则“开且只开A、B中一个开关”的命题公式是（ C ） A． p??q B． ?p?q

C． （p??q）?（?p?q） D． （p??q）?（?p?q） 16．下列等价式正确的是（ C ）

A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A

C．┐(?x)A?(?x)┐A D．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) 17．在论域D={a,b}中与公式（?x）A（x）等价的不含存在量词的公式是（ B ） A．A(a)?A(b) C． A(a)?A(b)

B． A(a)?A(b) D． A(b)?A(a)

18．下列命题公式为重言式的是（ C ） A．p→ （p∧q） C．p∨┐p

B．（p∨┐p）→q 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．谓词公式?x(M(x)??y(E(y)?L(x,y))中变元x （ C ） A． 是自由变元但不是约束变元 C． 既是自由变元又是约束变元

B． 是约束变元但不是自由变元 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．设p:2?2?0,q:3是奇数，则p?q的真值是 1 。 3．含n个命题变项的重言式的特异（主）合取范式为 1 4．设个体域为整数集合Z，命题?x?y(x?y?3）的真值为 1 5．公式?xP（x）??xQ（x）的前束范式为 ?x(P(x) Q(x)) 6．设p：我很累，q：我去学习，命题：“我很累，但我还去学习”的符号化为 p?q 7．设P表示：天下大雨；Q表示：他乘公共汽车上班，则命题“如果天下大雨，他就乘公共

汽车上班。”的符号化是 p?q

8．设P：2+2＝4，Q：3是奇数,则命题“2+2＝4，当且仅当3是奇数．”的符号化为 P?Q 9． 含n个命题变项的矛盾式的特异（主）析取范式为 0 10．命题公式p?q成假的解释是 01,10 11．p?q的成假解释为 01,10

计算题

1．求?xF(x)???xG(x)的前束范式。 解：

?xF?xG?x????x?xF?xG?x?3分? ?????x????x?F?x???G??x??3分?2．求?(p?q)?r的真值表，并写出它的特异（主）析取范式和特异（主）合取范式。 解：真值表如下：

故主析取范式为

??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?q)?r)?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．将公式(?xP(x)??yR(y))??xF(x)化为前束范式。 解： ?xP?x xF???y?R?y???? x????x?y?P?x??R?y????xF?x?

??x?yP?x??R?y???zF?z? ??x?y?zP?x??R?y??F?z?

????5．求公式 （p∨（q∧r））→（p∧q∧r） 的特异（主）析取范式，并求成真赋值。

解：?p??q?r????p?q?r?

???p??q?r????p?q?r????p???q??r????p?q?r????p??q????p??r???p?q?r????p??q??r????p??q?r????p?q??r???p?q?r? 成真赋值为：000，001，010，111

6．用谓词公式表示“有人喜欢吃所有的食物”。 解：M?x?:x是人，N?y?:y是食物

H?x,y?:x喜欢吃y 符号化：?x?M?x???y?N?y??H?x,y???

7． 用作真值表方法确定下列命题公式的类型： ((p?q)?(q?p))?(?p?q). 解： 设原式=A，真值表如下：

pq(p?q)?(q?p)?p?q0011010110011101A11 11则原式为永真式。

8．用逻辑式表示“某些计算机与某些外部设备之间不能相联”。 解：C?x?：x是计算机，D?x?：x为外部设备，

P?x,y?：x与y相联

符号化为?x?y(C(x)?D(y)??P(x,y))

9．在个体域D?{a,b}，消去公式?x(F(x)??yG(y))的量词。 解：原式＝(F(a)??yG(y))?(F(b)??yG(y))

＝(F(a)?(G(a)?G(b)))?(F(a)?(G(a)?G(b))) ＝(F(a)?F(b))?(G(a)?G(b))

10． 给定一阶逻辑公式?xP(x,y)??yQ(y)，求该公式的前束范式。 解：原式??xP?x,y???zQ?z? ??x?zP?x,y??Q?z?

11．用逻辑式表示“某些计算机与某些外部设备之间能相联”。 解： C?x?：x是计算机，D?x?：x为外部设备，

??P?x,y?：x与y相联

符号化为?x?y(C(x)?D(y)?P(x,y))

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化成与其等价的前束范式。

解：G??x(?y?P(x,y)?(?zQ(z)?R(x)))

＝?x?y(?P(x,y)??z(Q(z)?R(x))) ＝?x?y?z(?P(x,y)?(Q(z)?R(x)))

14． 设公式G的真值表如下，试求出G的特异（主）析取范式和特异（主）合取范式。

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 解：

主析取范式 (?p??q??r)?(?p?q??r)?(?p?q?r)?(p??q?r) 主析取范式(p?q??r)?(?p?q?r)?(?p??q?r)?(?p??q??r)

G 1 0 1 1 0 1 0 0

15．求公式?xF(x)??yG(x,y)的前束范式。 解：原式＝?xF(x)??yG(z,y) ＝?x?y(F(x)?G(z,y))

证明题

1．用等值演算证明等值式(p?r)?(q?r)?(p?q)?r。 证明：

2．设P,Q,R是三个命题，构造下列推理证明：

前提：P?Q,Q?R,?P 结论：R 证明：

左边?(?pv)r?(?q?r)?(?p??q)?r??(p?q)?r?(p?q)?r?右边

?1??2??3??4??5?

?PP?QQQ?RR前提引入前提引入?1??2?析取三段论前提引入?4分? ?4分??3??4?假言推理3．证明下列推断

前提：p?(q?s)，q，r?p 结论：r?s

证明：（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．用构造证明法证明下列推理：

前提：p?q,(?q?r)??r,?(?p?s) 结论：?s

证明：

?1??2?s 否定结论引入

???p?s? 前提引入

?3?p??s ?2?置换 ?4?p ?1??3?析取三段论 ?5???p?r???r 前提引入 ?6??p?r ?5?简化 ?7??r ?5?简化 ?8?r ?4??6?析取三段论 ?9?r??r ?7??8?合取

5．证明：p?(q?r)?(p??r)??q。 证明：左边??p???q?r? ??p?q?r??? ??? p?r???q???p??r???q ??p??r???q

＝右边

6．证明公式G＝（（P→Q） ∧（Q→P）∧P） →P是永真式。 证明： G?((?P?Q)?(?Q?P)?P)?P ＝((?P?Q)?P)?P

＝((?P?P)?(P?Q))?P ＝(P?Q)?P ＝?P??Q?P ＝1??Q

＝1 G为永真式

6．证明公式G＝（（P→Q） ∧（Q→P）∧P） →P是永真式。 证明： G?((?P?Q)?(?Q?P)?P)?P ＝((?P?Q)?P)?P

＝((?P?P)?(P?Q))?P ＝(P?Q)?P ＝?P??Q?P ＝1??Q

＝1 G为永真式

本文来源：https://www.bwwdw.com/article/7knp.html