范围：第1～5章（其中2.3，2.4不考 ），第14～16章（其中14.4，14.5不考）

填空题（2*12=24 )

1．什么是命题？ 下列句子是命题的是( )

A. 下午开会吗? B. 我正在说谎

C. 再过500年，人们可以在月球上居住了。 D. y+3>1.5 2. 设P: 太阳从东方升起， Q: 西安是中国的首都。 下列命题中，真值为1的命题有（ ） 3.设I是如下一个解释：D＝{a,b},

P(a,a) P(a,b) P(b,a) P(b,b)1 0 1 0

则在解释I下取真值为1的公式是( ). 或则使命题公式为真的解释有（ ）

(A)?x?yP(x,y) (B)?x?yP(x,y) (C)?x?yP(x,y)

(D)?x?yP(x,y). （E)?xP(x,x)

4.已知公式A含有3个命题变项，p，q，r，并且它的成真（假）赋值为XXX，XXX，XXX，则A的主合取范式和主析取范式分别为：（ ），（ ）

5. 设个体域为全总个体域，又令M(x)： x是人，L(x,y)：x喜欢y，a：范冰冰。将命题符号化：所有人都喜欢范冰冰（ ）

6.下面四组数能构成无向简单图的度数列的有（ ）。 A（XXXX） B.(YYYY) C.（xxyyy）

7.设谓词的定义域为{a, b,c },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是

在个体域D={1, 2, 3}中，与公式?x?y(R(x)→S(y))等价又不含量词的公式 是 _（R(1)∨R(2)∨R(3)） →(S(1)∧S(2)∧S(3) )

8. 在下图中，哪些有欧拉回路？哪些有欧拉通路但无欧拉回路？为什么？

或者把“欧拉”,改为“哈密尔顿”, 定理15.1，15.2，15.6及推论

1.设命题公式G＝p∧(q∨┓r)，则使公式G为真的解释有 110，111，100 2. 设P：怕困难，Q战胜困难。将下列命题符号化：

只有不怕困难，才能战胜困难。 Q?? P 或P??Q

3. 在个体域D={1, 2, 3}中，与公式?x?y(R(x)→S(y))等价又不含量词的公式 是

_（R(1)∨R(2)∨R(3)） →(S(1)∧S(2)∧S(3) ) 4、谓词公式?x(P(x)? ?yR(y))?Q(x)中量词?x的辖域是（ P(x)? ?yR(y) ） 5．(?A?B)?(B??C)? (?A??C ) 为假言三段论的推理定律.

6、一个图的哈密尔顿路是一条通过图中( 所有结点一次且恰好一次 )的路。 7、n阶无向完全图Kn 的边数是(

n(n?1) )，每个结点的度数是( n-1 )。 28. 设A为含命题变项p,q,r的重言式，则公式A∨（（p∧q）? r）的类型为 重言式_____，

9．命题“图中极大路径为图中最长的路径”的真值为（ 假 ）。 10．完全二部图Kr,s为哈密顿图，则r,s应满足( r=s≥2 )

其他题：(76=7*7+3*9 )

1.分别用真值表和等值演算法判别公式的类型。 2.利用等值演算法证明： A??

证: (p?r)?(q?r) ?(?p?r)(?p?r) ?(?p??q)?r ??(p?q)?r ? p?q）?r 3. 求公式A 的前束范式

?xF(x,y) ??yG(x,y) 解： ?xF(x,y) ??yG(x,y)

? ?tF(t,y)??wG(x,w) 换名规则 ? ?t?w(F(t,y)?G(x,w)) 或

?xF(x,y)??yG(x,y)

??xF(x,t)??yG(w,y) 代替规则 ? ?x?y(F(x,t)?G(w,y))

4.求命题公式G的主析取范式和主合取范式。

解：?(P∧Q)??(?P?R)

?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)） ?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)） ?(P∧Q)∨(?P∧?R)

?(P∨?R)∧（Q∨?P）∧（Q∨?R）

?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R） ?M1∧M3∧M4∧M5 主合取范式

?m0∨m2∨m6∨m7 主析取范式 5.构造下面推理的证明：

4. 构造下面推理的证明：

前提： ?A∨B，?C→?B，C→D

结论：A→D

(1) A

D(附加) P Q(1)(2) P

(2) ?A∨B (3) B

(4) ?C→?B (5) B→C (6) C

Q(4)

Q(3)(5) P Q(6)(7) D(1)(8)

(7) C→D (8) D

(9) A→D 5.

6. 已知无向树T中有X个4度顶点，y个2度顶点，z个3度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树. P310

7. 已知下列图，求顶点v0到vi的最短距离(课件或P304，三角形表！)。在下表中，填上数及符号表示解的过程。

t 1 2 3 4 5 6 v1 v2 v3 (+?, v1) (7, v1) (5, v2)* v4 (+?, v1) (5, v1) (5, v1) (5, v1)* v5 (+?, v1) (+?, v1) (9, v2) (8, v3) (8, v3) (8, v3)* v6 (+?, v1) (+?, v1) (+?, v1) (+?, v1) (7, v4)* v7 (+?, v1) (+?, v1) (+?, v1) (+?, v1) (13, v4) (9, v6) (0, v1)* (+?, v1) (3, v1)* 7 (9, v6)* v1到v7 的最短路径: v1v4v6v7 , d(v1,v7)=9

v1到v5 的最短路径: v1v2v3v5, d(v1,v5)=8

注：教材中的临时标号无法体现出来，但这一步（这一轮循环）的临时标号可以体现出来。*号为永久标号,最后加上。 8. 在谓词逻辑中构造下面推理的证明：(P77~78)

在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园. 今天是周六，并且颐和园游人太多. 所以, 我们去圆明园或动物园玩. (1) 设 p：今天是周六，q：到颐和园玩，

r：到圆明园玩，s：颐和园游人太多，t：到动物园玩 (2) 写出证明的形式结构

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

结论：r?t (3) 证明：

① p?(q?r) 前提引入 ② p 前提引入

③ q?r ①②假言推理 ④ s??q 前提引入 ⑤ s 前提引入

⑥ ?q ④⑤假言推理 ⑦ r ③⑥析取三段论 ⑧ r?t ⑦附加

习题：第十四章，10，11，第十五章，9 第十六章10,11,12,