离散数学习题 下载本文

范围:第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,