为无向图，u,v ∈V ，若u,v 连通，则（ ）A.d(u,v)>0 1 A
二、填空题
1. 命题公式┐(P→Q)的主析取范式为（），主合取式的编码表示为（）. 2. 设Q(x)：x 是奇数，Z(x)：x 是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为（）。
3. 设个体域为全总个体域，R(x)：x 是实数，Q(x)：x 是有理数，Z(x)：x 是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数但不是整数”符号化（）、（）、（）。
4.设A=（1，2，3）上的关系R={<1,1>,<1,2>,<1,3>,<3,3>},关系具备（）,不具备（）。
5.设无向图G 有12条边，有6个3度结点，其余结点度数均小于3，则G 中至少有（）个结点。
6. 任意两个不同的极小项的合取式为（）。全体极小项的析取式必为（）。 7. ∀x ∀y(P(x,y)∧Q(y,z))∧∃xP(x,y)中∀x 的作用域为（），∀y 的作用域为（），∃x 的作用域为（）
8. 设A=（1，2，3，4）上的关系R={<1,2>,<2,4>,<3,3>,<1,3>}则 r(R)=( )
;.'
B.d(u,v)=0 5 6 B 7 C C.d(u,v)<0 8 D 9 D D.d(u,v)≥0
2 C 3 A 4 10 11 12 13 14 15 16 C B B D A B D A A ;.
s(R)=( )
1 2 3 4 5 6 7 8 P∧┐Q ┐∀x(Z(x) →Q(x)) ∀x( Q(x) ∧ R(x) ) 反对称、传递 9 永假式 ∀y(P(x,y)∧Q(y,z)) {<1,2>,<2,4>,<3,3>,<1,3>,<1,1>,<2,2>,<4,4>} M0 ∧M2 ∧M3 x( Q(x) ∧ Z(x) ) 自反、反自反、对称 永真式 (P(x,y)∧Q(y,z)) {<1,2>,<2,1>,<2,4>,<4,2>,<3,3>,<3,1>,<1,3>} x( Q(x)∧R(x)∧┐Z(x) ) P(x,y)
;.'
;.
三、判断题
1.在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（×） 2.公式∀x(P(x)→Q(x))∨R(y)中∀x 的作用域为P(x)。（×） 3.A⊕B=A⊕C，则B=C（√）
4.A，B是集合。则命题A⊆B和A∈B可能同时成立（√）
5.若R是集合A上的传递关系，则R2也是集合A上的传递关系。（√） 6.若R和S是集合A上的任意两个自反关系，则ROS也是自反的（√）。 7.任一图G的△（G）必小于其结点数。（×） 8.在有向图中，结点间的可达关系是等价关系。（×）
9.同一谓词公式，指定不同的论域，其真值不一定相同。（√） 10.任意一个谓词公式都与一个前束范式等价。（√） 11.若P∪Q=Q，P∩Q= φ，则P= φ（√）
;.'
;.
12.若A-B⊆B，则B⊆A（×）
13.一个不是自反关系，一定是反自反关系。（×）
14.若R和S是集合A上的任意两个对称关系，则ROS也是对称的（×） 15.若无向图中恰有2个度为奇数的结点，则这两个结点必连通。（√） 16.在有向图中有2个奇度结点，则它们一个可达另一个或互相可达。（×） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 × × √ √ √ √ × × √ √ √ × × × √ ×
四、计算题
1.对下列谓词公式中的自由变元进行替换
((y)A(x,y)→(∀x)B(x,z) ∧ (x)(∀z)C(x,y,z) 解：
在A(x,y)中，x是自由变元； 在B(x,z)中，x是约束变元； 用字母t来替代自由变元x
((y)A(t,y)→(∀x)B(x,z) ∧ (x)(∀z)C(x,y,z)
2.求下列公式的真值
∀x(P(x)∨Q(x))，其中P(x):x=1，Q(x):x=2，且论域是{1,2} 解：
∀x(P(x)∨Q(x))
⇔(P(1)∨Q(1)) ∧ (P(2)∨Q(2)) ⇔T∧T ⇔T
3. 对下列谓词公式中的自由变元进行替换
(x)P(x,y) ∧ (∀z)Q(x,z) ∧ (∀x)R(x,y) 解：
在P(x,y)和Q(x,z)中x是自由变元； 在R(x,y)中x是约束变元； 用字母u替代自由变元x
(x)P(u,y) ∧ (∀z)Q(u,z) ∧ (∀x)R(x,y)
;.'
;.
4. 求下列公式的真值
∀x(P(x)→Q(x)) ∨ R(a),其中P：2>1,Q(x):x<=3,R(x):x>5,a:5且论域{-2,3,6} 解：
∀x(P→Q(x)) ∨ R(a)
⇔(P→Q(-2))∧ (P→Q(3)) ∧ (P→Q(6)) ∨ R(a) ⇔(T→T) ∧ (T→T) ∧ (T→F) ∨ F ⇔ T∧T∧F∨F ⇔ F
5、设N表示非负整数集，R:N→N,xRy定义为x+2y=10确定Dom(R)和Ran(R)。 解：
y=0,x=10 y=1,x=8 y=2,x=6 y=3,x=4 y=4,x=2 y=5,x=0
R={<0,5>,<2,4>,<4,3>,<6,2>,<8,1>,<10,0>} Dom(R)={0,2,4,6,8,10} Ran(R)={5,4,3,2,1,0}
6、设有向图D=其中E= (v1,v2,v3,v4)。其邻接矩阵为试求D中各顶点的入度与出度。 解：v1,v2,v3,v4的出度为3，1，1，2 v1,v2,v3,v4的入度为0，2，3，2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ;.'
;.
B C C A A C B B A B A B D A C B A C B D
;.'
