1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 (1)画出半序集(A,R)的哈斯图；
(2)写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3)写出A的最大元，最小元，极大元，极小元。
2.设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y) | x, y∈A 且x ≥ y}, 求
(1)画出R的关系图；
(2)写出R的关系矩阵.
3.设R是实数集合，σ,τ,ϕ是R上的三个映射，σ(x) = x+3, τ(x) = 2x, ϕ(x) ＝x/4，试求复合
映射σ•τ，σ•σ, σ•ϕ, ϕ•τ，σ•ϕ•τ.
4. 设I是如下一个解释：D = {2, 3},
a b f (2) f (3) P(2, 2) P(2, 3) P(3, 2) P(3, 3)
3 2 3 2 0 0 1 1
试求(1) P(a, f (a))∧P(b, f (b));
(2) ∀x∃y P (y, x).
5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
(1)画出半序集(A,R)的哈斯图；
(2)写出A的最大元，最小元，极大元，极小元；
(3)写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
6. 设命题公式G = ⌝(P→Q)∨(Q∧(⌝P→R)), 求G的主析取范式。 7. (9分)设一阶逻辑公式：G = (∀xP(x)∨∃yQ(y))→∀xR(x)，把G化成前束范式.
8. 对于下面二叉树的点，求先根遍历次序、中根遍历次序、后根遍历次序。 9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},
(1)求出r(R), s(R), t(R)；
(2)画出r(R), s(R), t(R)的关系图.
10. 试用克鲁斯卡尔算法求出如下权图的最优支撑树。
(1) G = (P ∧Q)∨(⌝P ∧Q ∧R)
(2) H = (P ∨(Q ∧R))∧(Q ∨(⌝P ∧R))
12. 用迪克斯特拉算法求下面有限权图中从A 到B 的最短路(要求用图示给出求解过程)，并计算它们的权值。
A 1D
23451467
2
98G B C
E F
13. 设R 和S 是集合A ＝{a , b , c , d }上的关系，其中R ＝{(a , a ),(a , c ),(b , c ),(c , d )},
S ＝{(a , b ),(b , c ),(b , d ),(d , d )}. (1) 试写出R 和S 的关系矩阵； (2) 计算R •S , R ∪S , R －
1, S －
1•R －
1. 四、证明题
1. 利用形式演绎法证明：{
P →Q , R →S , P ∨R }蕴涵Q ∨S 。 2. 设A,B 为任意集合，证明：(A-B)-C = A-(B ∪C).
3. (本题10分)利用形式演绎法证明：{⌝A ∨B, ⌝C →⌝B, C →D}蕴涵A →D 。
4. (本题10分)A, B 为两个任意集合，求证：
A －(A ∩B) = (A ∪B)－
B .
参考答案
三、计算证明题 1. (1)
(2) B 无上界，也无最小上界。下界1, 3; 最大下界是3. (3) A 无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.
2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.
(1)
(2)10001
10011101111R M ⎡⎤⎢⎥
⎢
⎥=⎢⎥
⎢⎥
⎣⎦
3. (1)σ•τ＝σ(τ(x))＝τ(x)+3＝
2x+3＝2x+3.
(2)σ•σ＝σ(σ(x))＝σ(x)+3＝(x+3)+3＝x+6, (3)σ•ϕ＝σ(ϕ(x))＝ϕ(x)+3＝x/4+3, (4)ϕ•τ＝ϕ(τ(x))＝τ(x)/4＝2x/4 = x/2,
(5)σ•ϕ•τ＝σ•(ϕ•τ)＝ϕ•τ+3＝2x/4+3＝x/2+3. 4. (1) P (a , f (a ))∧P (b , f (b )) = P (3, f (3))∧P (2, f (2)) = P (3, 2)∧P (2, 3) = 1∧0
= 0.
(2) ∀x ∃y P (y , x ) = ∀x (P (2, x )∨P (3, x )) = (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3)) = (0∨1)∧(0∨1) = 1∧1
= 1.
5. (1)
(2) 无最大元，最小元1，极大元8, 12; 极小元是1.
(3) B无上界，无最小上界。下界1, 2; 最大下界2.
6. G = ⌝(P→Q)∨(Q∧(⌝P→R))
= ⌝(⌝P∨Q)∨(Q∧(P∨R))
= (P∧⌝Q)∨(Q∧(P∨R))
= (P∧⌝Q)∨(Q∧P)∨(Q∧R)
= (P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧Q∧R)∨(P∧Q∧⌝R)∨(P∧Q∧R)∨(⌝P∧Q∧R) = (P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧Q∧R)∨(P∧Q∧⌝R)∨(⌝P∧Q∧R)
= m3∨m4∨m5∨m6∨m7 = ∑(3, 4, 5, 6, 7).
7. G = (∀xP(x)∨∃yQ(y))→∀xR(x)
= ⌝(∀xP(x)∨∃yQ(y))∨∀xR(x)
= (⌝∀xP(x)∧⌝∃yQ(y))∨∀xR(x)
= (∃x⌝P(x)∧∀y⌝Q(y))∨∀zR(z)
= ∃x∀y∀z((⌝P(x)∧⌝Q(y))∨R(z))
8. 先根遍历次序：ABDFIJGKMCEHL；
中根遍历次序：IFJDGKMBACEHL;
后根遍历次序：IJFMKGDBLHECA.
9. (1) r(R)＝R∪I A＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)},
s(R)＝R∪R－1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},
t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}；
(2)关系图:
10、
权为19.
11. G ＝(P ∧Q)∨(⌝P ∧Q ∧R)
＝(P ∧Q ∧⌝R)∨(P ∧Q ∧R)∨(⌝P ∧Q ∧R) ＝m 6∨m 7∨m 3 ＝∑ (3, 6, 7)
H = (P ∨(Q ∧R))∧(Q ∨(⌝P ∧R)) ＝(P ∧Q)∨(Q ∧R))∨(⌝P ∧Q ∧R)
＝(P ∧Q ∧⌝R)∨(P ∧Q ∧R)∨(⌝P ∧Q ∧R)∨(P ∧Q ∧R)∨(⌝P ∧Q ∧R) ＝(P ∧Q ∧⌝R)∨(⌝P ∧Q ∧R)∨(P ∧Q ∧R) ＝m 6∨m 3∨m 7 ＝∑ (3, 6, 7)
G ,H 的主析取范式相同，所以G = H. 12. 最短路:AGED, 最短路的权值和为7.
A
D
4
1
2 G
E
13. (1)⎥⎥⎥⎥
⎦⎤⎢⎢⎢
⎢⎣⎡=000010000100
0101R M ⎥
⎥
⎥⎥
⎦
⎤
⎢
⎢⎢
⎢⎣⎡=10000000
11000010
S M
(2)R •S ＝{(a , b ),(c , d )},
R ∪S ＝{(a , a ),(a , b ),(a , c ),(b , c ),(b , d ),(c , d ),(d , d )}, R －
1＝{(a , a ),(c , a ),(c , b ),(d , c )}, S －
1•R －
1＝{(b , a ),(d , c )}. 四 证明题
1. 证明：{P →Q , R →S , P ∨R }蕴涵Q ∨S
(1) P ∨R P (2) ⌝R →P Q(1) (3) P →Q
P
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议