离散数学模拟习题与解析(4)

离散数学试卷（四）

一、 填空 10% （每小题 2分）

1、 若P，Q，为二命题，P?Q真值为0 当且仅当 。 2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，L(x,y):x?y则命题的逻辑谓词公式为 。 3、 谓词合式公式?xP(x)??xQ(x)的前束范式为 。 4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部

分不变，这种方法称为换名规则。

5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则

被称为存在量词消去规则，记为ES。

二、 选择 25% （每小题 2.5分）

1、 下列语句是命题的有（ ）。

A、 明年中秋节的晚上是晴天； B、x?y?0； C、xy?0当且仅当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、P?Q ；B、P?P?Q ；C、(?P?Q)?(P??Q)；D、?(P?Q)。 4、 下列等价式成立的有（ ）。

A、P?Q??Q??P ；B、P?(P?R)?R ；

C、 P?(P?Q)?Q； D、P?(Q?R)?(P?Q)?R。 5、 若A1,A2?An和B为wff，且A1?A2???An?B则（ ）。 A、称A1?A2???An为B的前件； B、称B为A1,A2?An的有效结论

24

离散数学试卷（四）

C、当且仅当A1?A2???An?B?F；D、当且仅当A1?A2???An??B?F。 6、 A，B为二合式公式，且A?B，则（ ）。

A、A?B为重言式； B、A*?B*；

C、A?B； D、A*?B*； E、A?B为重言式。 7、 “人总是要死的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。 A、M(x)?Mortal(x)； B、M(x)?Mortal(x) C、?x(M(x)?Mortal(x))；D、?x(M(x)?Mortal(x))

8、 公式A??x(P(x)?Q(x))的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A的

真值为（ ）。

A、1； B、0； C、可满足式； D、无法判定。 9、 下列等价关系正确的是（ ）。 A、?x(P(x)?Q(x))??xP(x)??xQ(x)； B、?x(P(x)?Q(x))??xP(x)??xQ(x)； C、?x(P(x)?Q)??xP(x)?Q； D、?x(P(x)?Q)??xP(x)?Q。 10、

下列推理步骤错在（ ）。

P US① P ES③ T②④I EG⑤

①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)

A、②；B、④；C、⑤；D、⑥

25

离散数学试卷（四）

三、 逻辑判断30%

1、 用等值演算法和真值表法判断公式A?((P?Q)?(Q?P))?(P?Q)的类型。

（10分）

2、 下列问题，若成立请证明，若不成立请举出反例：（10分）

（1） 已知A?C?B?C，问A?B成立吗？ （2） 已知?A??B，问A?B成立吗？

3、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。

问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）

四、计算10%

1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题

(A1?(A2?(A3??A1)))?(A2??A4)的真值。（5分）

2、 利用主析取范式，求公式?(P?Q)?Q?R的类型。（5分）

五、谓词逻辑推理 15%

符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。

六、证明：（10%）

设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。

26

离散数学试卷（四）

一、 填空 10%（每小题2分）

1、P真值为1，Q的真值为0；2、?x(F(x)?L(x,0)??y(F(y)?L(y,x))；3、

?x(?P(x)?Q(x))；4、约束变元；5、?xA(x)?A(y)，y为D的某些元素。

二、 选择 25%（每小题2.5分） 题目 答案

三、 逻辑判断 30% 1、（1）等值演算法

A?((P?Q)?(Q?P))?(P?Q)?(P?Q)?(P?Q)?T

1 A,C 2 A,D 3 C,D 4 A,D 5 B,C 6 A,B,C,D,E 7 C 8 A 9 B 10 (4) （2）真值表法

P Q 1 1 1 0 0 1 0 0 所以A为重言式。 2、（1）不成立。

若取C?T则A?T?TB?T?T有A?C?B?C?T

P?Q Q?P (P?Q)?(Q?P) P?Q A 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 但A与B不一定等价，可为任意不等价的公式。 （2）成立。 证明：?A??B充要条件?A??B?T

即：

T?(?A??B)?(?B??A)?(A??B)?(B??A)?(?B?A)?(?A?B)?(A?B)?(B?A)?A?B

所以A?B?T 故 A?B。

27

离散数学试卷（四）

3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提：P?(?(R?S)??Q),①P?(?(R?S)??Q) ②P

③?(R?S)??Q ④?R ⑤?R??S ⑥?(R?S) ⑦?Q

罢工不会停止是有效结论。 四、计算 10%

1、 解：

(1?(1?0?0)))?(1?1)?(1?(1?0)?1?(1?0)?1?1?1?1P,?R 结论：?Q

P P T①②I P T④I T⑤E T③⑥I

2、

?(P?Q)?Q?R??(?P?Q)?(Q?R)?(P??Q)?(Q?R)?P??Q?Q?R?F

它无成真赋值，所以为矛盾式。

五、谓词逻辑推理 15%

解：M(x):x是人;F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y

?x(M(x)??y(F(y)?H(x,y))) ?x(M(x)??y(G(y)??H(x,y))) ??x(F(x)??G(x))

证明：

⑴?x(M(x)??y(F(y)?H(x,y))) ⑵M(a)??y(F(y)?H(a,y)) ⑶M(a)

⑷?y(F(y)?H(a,y))

28

P ES⑴ T⑵I T⑵I

离散数学试卷（四）

⑸?x(M(x)??y(G(y)??H(x,y))) ⑹M(a)??y(G(y)??H(a,y)) ⑺?y(G(y)??H(a,y)) ⑻?y(H(a,y)??G(y)) ⑼F(z)?H(a,z) ⑽H(a,z)??G(z) ⑾F(z)??G(z) ⑿?x(F(x)??G(x))

四、 证明10%

P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾

?xA(x)??xB(x)?(A(a)?A(b)?A(c)?(B(a)?B(b)?B(c)?(A(a)?B(a))?(A(a)?B(b))?(A(a)?B(c))

?(A(b)?B(a))?(A(b)?B(b))?(A(b)?B(c))?(A(c)?B(a))?(A(c)?B(b))?(A(c)?B(c))?(A(a)?B(a))?(A(b)?B(b))?(A(c)?B(c)??x(A(x)?B(x))

29

离散数学试卷（四）

⑸?x(M(x)??y(G(y)??H(x,y))) ⑹M(a)??y(G(y)??H(a,y)) ⑺?y(G(y)??H(a,y)) ⑻?y(H(a,y)??G(y)) ⑼F(z)?H(a,z) ⑽H(a,z)??G(z) ⑾F(z)??G(z) ⑿?x(F(x)??G(x))

四、 证明10%

P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾

?xA(x)??xB(x)?(A(a)?A(b)?A(c)?(B(a)?B(b)?B(c)?(A(a)?B(a))?(A(a)?B(b))?(A(a)?B(c))

?(A(b)?B(a))?(A(b)?B(b))?(A(b)?B(c))?(A(c)?B(a))?(A(c)?B(b))?(A(c)?B(c))?(A(a)?B(a))?(A(b)?B(b))?(A(c)?B(c)??x(A(x)?B(x))

29

本文来源：https://www.bwwdw.com/article/3dpt.html