离散数学题目及答案

数理逻辑习题

判断题

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