数理逻辑试题

离散数学——数理逻辑试题

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

1. 若P，Q为二命题，P?Q真值为F 当且仅当 。

2. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，L(x,y)：x>y，则命题的逻辑谓词公式为 。

3. n个命题变元的 式称为极大项，其中每个变元与它的否定不能同时出现，但两者必须 。

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)； D、(?P∨Q)( 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, ?,A n和B为命题公式，且A1∧A2∧ ?∧A n?B，则（ ）。 A、称A1∧A2∧ ?∧A n为B的前件； B、称B为A1∧A2∧ ?∧A n的后件 C、当且仅当A1∧A2∧ ?∧A n∧B ?F； D、当且仅当A1∧A2∧ ?∧A n∧?B?F。 6.A，B为二合式公式，且A?B，考虑下列结论：

① A?B为重言式； ② A??B?； ③ A?B； ④ A?B为重言式。

则正确结论个数是（ ）。

A、1； B、2； C、3； D、4。 7. “人总是要死的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；D(x)：x是要死的。)

1

A、M(x)?D(x)； B、M(x)∧D(x) C、?x(M(x) ?D(x))； D、?x(M(x)∧D(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.下列推理步骤错在（ ）。 ① ?x(F(x)?G(x)) P ② F(y)?G(y) T, ①, US ③ ?xF(x) P ④ F(y)

T, ③, ES

⑤ G(y) T, ②, ④, 假言推理 ⑥ ?xG(x) T，⑤，EG

A、②； B、④； C、⑤； D、⑥ 三、逻辑判断下列各题，并给出证明 30%

1. 用等值演算法和真值表法判断公式A= ((P?Q)∧(Q?P)) ? (P?Q)的类型。（10分） 2. 下列问题，若成立请证明，若不成立请举出反例：（10分） 已知A∨C?B∨C，问A?B成立吗？ 已知?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))。

2

答 案

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

1、P真值为1，Q的真值为0；2、?x(F(x)?L(x,0)??y(F(y)?L(y,x))；3、析取式, 出现且出现一次；4、约束变元；5、?xA(x)?A(y)，y为D的某些元素。 二、选择 25%（每小题2.5分）

题目 答案 1 A 2 A 3 C 4 D 5 C 6 D 7 C 8 A 9 B 10 B 三、逻辑判断 30% 1、（1）等值演算法

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

（2）真值表法

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

若取C?TP?Q 1 0 1 1 Q?P 1 1 0 1 (P?Q)?(Q?P) 1 0 0 1 P?Q 1 0 0 1 A 1 1 1 1 则A?T?TB?T?T有A?C?B?C?T

但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。

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

P,?R 结论：?Q

P P

3

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

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

T, ①, ②, 假言推理 P

T, ④, 加法式 T, ⑤, 置换 T, ③, ⑥, 假言推理

1、解：(1?(1?0?0)))?(1?1)?(1?(1?0)?1

?(1?0)?1?1?1?1. 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))

证明：

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

P

(2) M(a)??y(F(y)?H(a,y)) T, ⑴, ES (3) M(a)

T, ⑵, 简化式

(4) ?y(F(y)?H(a,y)) T, ⑵, 简化式 (5) ?x(M(x)??y(G(y)??H(x,y))) P (6) M(a)??y(G(y)??H(a,y)) T, ⑸, US

(7) ?y(G(y)??H(a,y)) T, ⑶, ⑹, 假言推理 (8) ?y(H(a,y)??G(y)) T, ⑺, 置换 (9) F(z)?H(a,z) T, ⑷, US

4

(10) H(a,z)??G(z) T, ⑻, US (11) F(z)??G(z)

T, ⑼, ⑽, 前提三段论

(12) ?x(F(x)??G(x)) T, ⑾, UG 六、证明10%

?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))

5