成人教育《离散数学》期末考试复习题及参考答案 .pdf

离散数学复习题二

一、简要回答下列问题：

1．请给出P，PQ，PQ的真值表。

2．请给出公式蕴涵的定义。举一个例子。

3.请给出命题xG(x)的真值规定。

4.什么是谓词逻辑公式的解释？

5.叙述谓词逻辑公式G与它的Skolem范式之间的区别与联系。

6.什么是图的关联矩阵？

7.什么是简单路？举一例。

8.什么是有向树？举一例

9.设G为整数加群，H为5的所有倍数组成的加法群，给出H的所有陪集。

二、判断下列公式是恒真？恒假？可满足？

a)(P(QR))(P(QR))；

b)P(P(QP))；

c)(QP)(PQ)；

d)(PQ)(PQ)。

三、指出下列公式哪些是恒真的哪些是恒假的：

(1)P（PQ）Q

(2)（PQ）（PQ）

(3)（PQ）（QR）（PR）

(4)（PQ）（PQPQ）

四、给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：

a)(P(QR))((PQ)(RS))

b)((PQ)R)(((PQ)R)S)

c)((PQ)R)((QP)(RS))

d)(P(Q(RP)))(QS)

五、证明：连通图中任意两条最长的简单路必有公共点。