1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射.2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ).3. 设X 是非空集合，则X 的幂集P (X )关于集合的⋃运算的单位元是( )，零元是( )，P (X )关于集合的⋂运算的单位元是( ).4. 6阶非Abel 群的2阶子群共有( )个，3阶子群共有( )个，4阶子群共有( )个.5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图. 二、单选题1. 幂集P (P (P (∅))) 为( )(A){{∅}, {∅, {∅}}}. (B){∅, {∅, {∅}}, {∅}}. (C){ ∅, {∅, {∅}}, {{∅}}, {∅}} (D){ ∅, {∅, {∅}}}. 2. 设R 是集合A 上的偏序关系，则1-⋃RR 是( ).(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的.(A))(B A →⌝与B A ⌝∧. (B) )(B A ↔⌝与)()(B A B A ∧⌝∨⌝∧. (C))(C B A ∨→与C B A →⌝∧)(. (D))(C B A ∨→与)(C B A ∨∧⌝. 4.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图4K 中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2三、设A 和B 是集合，使B B A =-成立的充要条件是什么，并给出理由.四、设R 和S 是集合A 上的对称关系，证明S R 对称的充要条件是R S S R =. 五、分别利用(1)等值演算法和(2)真值表求命题公式))(())((r q p p q r A ∨→→→∨⌝=的主析取范式和主合取范式.六、设G 是(n , m )无向图，若n m ≥，证明G 中必存在圈.1.设A = {2, {3}, 4, a }, B = {1, 3, 4, {a }}, 则{3}( )A ，{a }( )B ，{{a }}( )B .2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则=S R { }, =R S { }, =R R { }.3. 在同构意义下，3阶群有( )个，4阶群有( )个，5阶群有( )个.4.任意有限布尔代数)1,0,,,,(⋅+B 均与集合代数( )同构，其元素个数为( ), 其中( )是B 的所有原子组成的集合.5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵. 二、单选题1. 在有理数集合Q 上定义运算“*”如下：对于任意x , y ∈ Q ，y x * = x + y – xy ，则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.2. 设A = {1, 2, 3}, 下图分别给出了A 上的两个关系R 和S ，则S R 是( )关系.(A)自反. (B)对称. (C)传递. (D)等价.3.令T (x ): x 是火车，B (x ): x 是汽车，F (x , y ): x 比y 快，则“某些汽车比所有的火车慢”符号化为( ). (A)()()),()()(y x H x T x y B y →∀∧∃. (B)()()),()()(y x H x T x y B y ∧∀→∃. (C)()()),()()(y x H x T y B y x ∧→∃∀. (D)()()),()()(y x H x T x y B y →∀→∃.4. 整数集合Z 关于数的加法“+”和数的乘法“⋅”构成的代数结构(Z, +, ⋅)是( ). (A)域 (B)域和整环 (C)整环 (D) 有零因子环5.设G 是简单图，G 是G 的补图，若G G ≅，则称G 为自补图. 5阶不同构的自补图个数为( ). (A)0. (B)1. (C)2. (D)3.三、设C B g B A f →→:,:, 若g f 是单射，证明f 是单射，并举例说明g 不一定是单射. 四、设A = {a , b , c , d }上的关系R = {(a , b ), (b , d ), (c , c ), (a , c )}, 画出R 的关系图，并求出R 的自反闭包r (R )、对称闭包s (R )和传递闭包t (R ).五、设G 是(6，12) 的简单连通平面图，则G 的面由多少条边围成，为什么？ 六、任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.G SG R1. 设A = {1, 2, 3, {1, 2}, {3}}, B = {2, {2,3}, {1}} , 则A – B = { }, B – A = { }, A ⊕ B = { }.2. 实数集合R 关于加法运算“+”的单位元为( ), 关于乘法运算“⋅”的单位元为( ), 关于乘法运算“⋅”的零元为( ).3. 令Z (x ): x 是整数，O (x ): x 是奇数，则“不是所有整数都是奇数”符号化为( ).4. 有限域的元素个数为( ), 其中( )且( ).5. 设G 是(7, 15)简单平面图，则G 一定 ( )连通图，其每个面恰由( )条边围成，G 的面数为( ). 二、单选题1. 函数的复合运算“ ”满足( )(A)交换律. (B)结合律. (C)幂等律. (D)消去律. 2. 设集合A 中有4个元素，则A 上的等价关系共有( )个. (A)13 (B)14 (C)15 (D)16 3.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 4. 下列偏序集，( )是格.5. 不同构的(5, 3)简单图有( )个.(A)4 (B)5 (C)3 (D)2三、设C B g B A f →→:,:, 若g f 是满射，证明g 是满射，并举例说明f 不一定是满射. 四、在整数集合Z 上定义关系R 如下：对于任意∈y x , Z ，y yx xR y x +=+⇔∈22),(.判断R 是否具有自反性、反自反性、对称性、反对称性及传递性. 五、利用真值表求命题公式)())(q p q p A ⌝→↔→⌝=的主析取范式和主合取范式.六、将6阶完全无向图K 6的边随意地涂上红色或蓝色，证明：无论如何涂法，总存在红色的K 3或蓝色的K 3.1. 集合A 上的等价关系R 必满足( 、 、 ).2. 任意6阶群的平凡子群一定是( )群.3. 设集合A = {1, 2, 3}，则A 上的置换共有( )个.4. 设集合A 关于*满足( 、 )，则(A , *)构成独异点.5. ( )无向图称为无向树. 二、单选题1. 设集合A 中有99个元素，则A 的子集有( )个. (A)299. (B)99. (C) 2100. (D)100.2. 设集合A 中有4个元素，则A 上的划分共有( )个. (A)13 (B)14 (C)15 (D)163.设集合A = {1, 2, 3, 4, 5}上的关系R = {(x , y )|x , y ∈ A 且x + y = 6}，则R 的性质是( ). (A) 自反的. (B) 对称的. (C) 对称的、传递的. (D) 反自反的、传递的.4.下列联结词中，不满足交换律的是( ).(A)∧. (B)∨. (C)⊕. (D) →.5.谓词公式)())()((x R y yQ x P x →∃∨∀中，x ∀的辖域为( ).(A)))()((y yQ x P x ∃∨∀. (B))(x P . (C))()(y yQ x P ∃∨. (D))(x P 和)(x R . 三、设),(≤A 是偏序集，定义函数)(:A P A f →如下：对于任意A a ∈，},|{)(a x A x x a f ≤∈=.证明f 是单射，且当b a ≤时有)()(b f a f ⊆.四、(1)列出与非联结词“↑”的运算表.(2)仅使用与非联结词“↑”分别表示∨∧⌝,,.五、求))),(),((),,((v y vQ u x uQ z y x zP y x ∃→∃∧∃∀∀的前束范式. 六、 (1)给出(n , m )连通平面图的面数r 计算公式.(2)若(n , m )连通平面图的每个面至少由5条边围成，给出n 和m 所满足的关系式. (3)证明：Petersen 图不是平面图.1. 对于任意集合A , 若|A | = n , 则A 的幂集合P (A )有( )个元素.2. 整数集合Z 上的小于关系“<”具有( ).3. 联结词集合},{→⌝( )功能完备的.4. 设Q 是有理数集合，Q 关于数的乘法运算“⋅”能构成( ).5. 设≤是非空集合L 上的偏序，若L 中的任意两个元素均存在( )，则称(L ,≤)是格. 二、单选题1. 设A = ∅，B = {∅, {∅}}，则B – A 为( ).(A){{∅}}. (B){∅}. (C) {∅, {∅}}. (D) ∅. 2. 设R 和S 是集合A 上的关系，则下述命题成立的有( ). (A)若R 和S 是自反的，则S R ⋂是自反的. (B)若R 和S 是对称的，则S R 是对称的. (C)若R 和S 是反对称的，则S R 是反对称的. (D)若R 和S 是传递的，则S R ⋃是传递的. 3.设R 是集合A 上的偏序关系，则1-⋃RR 是( )关系.(A) 偏序. (B) 等价. (C) 相容. (D) 线性序.4.令A (x ): x 是人，B (x ): x 犯错误，则“没有不犯错误的人”符号化为( ). (A)))()((x B x A x ∧∀. (B)))()((x B x A x ⌝→⌝∃. (C)))()((x B x A x ∧⌝∃. (D)))()((x B x A x ⌝∧⌝∃.5.在任意n 阶连通图中，其边数( ).(A)至多n – 1条. (B)至少n – 1条. (C)至多n 条. (D) 至少n 条. 三、设R 为实数集合，定义f : R ⨯ R → R ⨯ R 为),()),((y x y x y x f -+=.(1)证明f 是双射. (2)求f 的逆函数1-f .(3)计算f f1-及f f .四、设集合},,{c b a A =，在A 上的关系)},(),,(),,{(c b b a a a R =，求)(),(),(R t R s R r . 五、用构造法证明：)))()(()((x R y Q x P x ∧→∀，⇒∀)(x xP ))()(()(x R x P x y Q ∧∀∧.六、证明：阶数2≥的任意无向树中的最长路径的端点都是树叶，即度数为1.一、填空题1. 设全集为整数集合Z ，且}30|{2<=xx A ，}20,|{<=x x x B 是素数，}5,3,1{=C ，则=⋃-C A B )({ }.2. 设集合A 为同一平面内的所有直线组成的集合，R 表示两直线的垂直关系，则R 2表示( )关系.3. 命题公式)(r q p ⌝∧∨的成真赋值(p , q , r )为( ).4. 设G = {1, 5, 7, 11}, “12⋅”为模12的乘法运算，则群),(12⋅G 中元素5的阶为( ).5. 图1所示的图G 的色数=)(G χ().二、单选题1. 设集合X ≠ ∅，则P (X )关于集合的⋃运算的单位元为( ). (A)X . (B) ∅. (C) P (X ). (D)以上答案均不成立.2. 令Z (x ): x 是整数，N (x ): x 是负数，S (x , y ): y 是x 的平方，则“任何整数的平方均非负”可符号化为( ).(A)())(),()(y N y x S x Z y x ⌝→∧∀∀.(B)())(),()(y N y x S x Z y x ⌝→∧∃∀.(C)())(),()(y N y x S x Z y x ⌝∧→∀∀ . (D)())(),()(y N y x S x Z x ⌝→∧∀. 3.设),(≤L 是格，G 为),(≤L 到自身的格同态映射组成的集合，则G 关于映射的复合“ ”运算构成( ).(A) 群. (B) 环. (C) 格. (D) 独异点. 4.给定下列序列，可构成简单无向图的节点度数序列的为( ). (A)(1, 3, 4, 4, 5). (B)(0, 1, 3, 3, 3). (C)(1, 1, 2, 2, 2). (D) (1, 1, 2, 2, 3). 5.设G 是n 阶简单无向图，则其最大度)(G ∆( ). (A) < n . (B) ≤ n . (C) > n . (D) ≥ n .三、设R 是实数集合，f : R ×R → R ×R , f (x , y ) = (x + y , x - y ).(1) 证明f 是双射. (2) 求出f 的逆函数f -1、f f1-和f f .四、图2给出的是集合A = {1，2，3，4，5，6}上关系R 的关系图，试画出R 的传递闭包t (R )的关系图,并用集合表示.五、利用真值表求命题公式()())()(p q r r q p →→↔→→的主析取范式和主合取范式.六、求赋权分别为2, 3, 5, 7, 8的最优2叉树.图2一、1. 32，0，30.2.))()(())()((x G x F x x F x G x ⌝∧∃∧→∀.3.∅，X ，X .4. 3，1，0.5.n 为奇数，3，4≤n .二、1(C); 2(B); 3(D); 4(D); 5(A). 三、证 ==⇔=-B A B B A ∅. (⇐)显然.(⇒)因为B A B A ⋂=-，根据B B A =-得B B B B A ⋂=⋂⋂)(，于是B = ∅，进而A = ∅. 四、解 由于R 和S 是对称的，所以S SR R==--11,.(⇐)因为R S S R =，两边取逆得11)()(--=R S S R ，而S R SRR S ==---111)(.所以S R S R =-1)(，因此S R 是对称关系.(⇒)由于S R 对称，所以S R S R =-1)(. 而R S RSS R ==---111)(，因而R S S R =. 五、解 (1)等值演算法 A 的主合取范式:))(())((r q p p q r A ∨→→→∨⌝= = ))(())((r q p p q r ∨∨⌝→∨⌝∨⌝= )())((r q p p q r ∨∨⌝∨∨⌝∨⌝⌝ = )()(r q p p q r ∨∨⌝∨⌝∧∧ = r q p ∨∨⌝(由吸收律得到). 于是，A 的主析取范式为))(())((r q p p q r A ∨→→→∨⌝== ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p )()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.(2)真值表法由表可知，))(())((r q p p q r A ∨→→→∨⌝=的主合取范式为r q p A ∨∨⌝=.A 的主析取范式为A = ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p )()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.七、证(反证)假设G 中不含圈. 设G 有k (k ≥ 1)个连通分支k G G G ,...,,21，其节点个数分别为k n n n ,...,,21，其边数分别为k m m m ,...,,21. 这时，iG为树，根据树的基本性质有1-=i i n m )1(k i i ≤≤. 进而n k n n m m ki i ki i <-=-==∑∑==)1(11，与已知n m ≥矛盾. 证毕.一、1. ∈，∈，⊆.2.{(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}.3. 1, 2, 1.4. ,,,),((⋂⋃X P ∅, X ), 2n , n .5. 3, 9.二、1(D); 2(B); 3(A); 4(C); 5(C).三、证 对于任意A x x ∈21,，若)()(21x f x f =，则))(())((21x f g x f g =，于是))(())((21x f g x g f =. 由于g f 是单射，所以21x x =，因此f 是单射.例如，A = {a , b }, B = {1, 2, 3}, C = {α, β, γ}, f = {(a , 1), (b , 2)}, g = {(a , α), (b , β), (c , β)}, 这时)},2(),,1{(βα=g f ，它是A 到C 的单射，但g 不是单射.四、解 R 的关系图如下：}),(),,(),,(),,(),,(),,(),,{()(d d b b a a c a c c d b b a R r =, }),(),,(),,(),,(),,(),,(),,{()(a c b d a b c a c c d b b a R s =. }),(),,(),,(),,(),,{()(d a c a c c d b b a R t =.五、证 根据Euler 公式，G 的面数为r = 12 – 6 +2 = 8. 由握手定理知，∑=⋅=vv 24122)deg(，而简单连通平面图的每个面至少由3条边围成，所以G 的每个面恰由3条边围成.六、证 用6个节点分别表示这6个人，可得6阶完全无向图6K . 若两个人认识，则在相应的两个节点所在的边上涂上红色，若两个人不认识，则在相应的两个节点所在的边上涂上蓝色.对于任意的6K 的节点v ，因为5)deg(=v ，与v 邻接的边有5条，当用红、蓝颜色去涂时，至少3条边涂的是同一种颜色，不妨设321,,vv vv vv 是红色. 若3条边21v v ，32v v ，31v v 是红色，则存在红色3K，这意味着有3个人相互认识; 若21v v ，32v v ，31v v 都是蓝色，则存在蓝色3K，这意味着有3个人相互不认识. 结论成立.abd一、1.{1, 3, {1, 2}, {3}}；{{2, 3}, {1}}；{1, 3, {1, 2}, {3}, {2, 3}, {1}}.2.0，1，0.3. ))()((x O x Z x →⌝∀.4. p n , p 为素数，n 为正整数.5. 是，3，10.二、1(B); 2(C); 3(D); 4(C); 5(A).三、证 对于任意C z ∈，由于g f 是满射，必存在A x ∈，使得z x f g x g f ==))(())(( . 令B x f y ∈=)(，有z y g =)(，因此，g 是满射.设},,{c b a A =，}3,2,1{=B ，},{βα=C ，令B A f →:，,:C B g → 3)(,3)(,2)(===c f b f a f ,βαβ===)3(,)2(,)1(g g g .这时，α==))(())((a f g a g f ，β==))(())((b f g b g f ，显然有},{)(ran βα=g f ，g f 是满射. 而ran f = {2, 3}，f 不是满射. 四、证 (1)对于任意x ∈ Z , 由于x xx x+=+22, 所以(x , x ) ∈ R , 即R 是自反的.(2)因为(0, 0) ∈ R , 因此R 不是反自反的. (3)对于任意x , y ∈ Z , 若(x , y ) ∈ R , 则y yx x +=+22, 于是x xy y+=+22, 进而(y , x ) ∈ R , 即R是对称的.(4)因为(2, -3) ∈ R 且(-3, 2) ∈ R ，因此R 不是反对称的. (5)对于任意x , y , z ∈ Z , 若(x , y ) ∈ R 且(y , z ) ∈ R , 则y yx x +=+22且z zy y+=+22，于是z zx x+=+22，所以(x , z ) ∈ R , 即R 是传递的.综上所述，知R 是自反的、对称的和传递的.五、解 命题公式)())(q p q p A ⌝→↔→⌝=的真值表如下：A 的主析取范式为：)()(q p q p A ⌝∧∨∧=.A 的主合取范式为：)()(q p q p A ∨∧⌝∨=.六、证 对于任意的6K 的节点v ，因为5)deg(=v ，与v 邻接的边有5条，当用红、蓝颜色去涂时，至少3条边涂的是同一种颜色，不妨设321,,vv vv vv 是红色. 若3条边21v v ，32v v ，31v v 是红色，则存在红色3K ; 若21v v ，32v v ，31v v 都是蓝色，则存在蓝色.一、1.自反性、对称性和传递性.2. Abel.3. 6.4. 封闭性和结合性.5. 不含圈的连通.二、1(A); 2(C); 3(B); 4(D); 5(C).三、证 对于任意A b a ∈,，假定)()(b f a f =. 由于≤是偏序，于是a a ≤，所以)(a f a ∈，进而)(b f a ∈，根据定义知b a ≤. 同理可证，a b ≤. 根据偏序的反对称性有b a =，因此f 是单射.当b a ≤时，对于任意)(a f x ∈，于是a x ≤. 根据偏序的传递性有b x ≤，即)(b f x ∈，故)()(b f a f ⊆.四、证 (1) 与非联结词“↑”的运算表如下：(2)p p p p p ↑=∧⌝=⌝)(.)()()())((q p q p q p q p q p ↑↑↑=↑⌝=∧⌝⌝=∧. )()()()()(q q p p q p q p q p ↑↑↑=⌝↑⌝=⌝∧⌝⌝=∨.五、解 ))),(),((),,((v y vQ u x uQ z y x zP y x ∃→∃∧∃∀∀=))),(),((),,((v y vQ u x uQ z y x zP y x ∃∨⌝∃∧∃∀∀ =))),(),((),,((v y vQ u x Q u z y x zP y x ∃∨⌝∀∧∃∀∀ =))),(),((),,((v y Q u x Q v u z y x zP y x ∨⌝∃∀∧∃∀∀ =))),(),((),,((v y Q u x Q z y x P v u z y x ∨⌝∧∃∀∃∀∀ 六、证 (1)根据Euler 公式，有2+-=n m r . (2)31052)2(5-≤⇒≤+-n m m n m .(3) 若Petersen 图是平面图，由于其每个面至少5条边围成，于是由(2)知3105-≤n m . 因为在Petersen图中，m = 15, n = 10, 于是31010515-⋅≤，矛盾.一、1. 2n 2. 反自反、反对称、传递 3. 是 4. 独异点 5. 上确界和下确界.二、1(C); 2(A); 3(B); 4 (D); 5(B).三、(1)证 对于任意∈),(),,(2211y x y x R ⨯ R ，若)),(()),((2211y x f y x f =，于是),(),(22221111y x y x y x y x -+=-+，进而2211y x y x +=+且2211y x y x -=-. 由此可得，2121,y y x x ==，因而),(),(2211y x y x =，故f 是单射.对于任意∈),(q p R ⨯ R ，取2,2q p y q p x -=+=，容易得知),(),()),((q p y x y x y x f =-+=.由上可知，f 是双射. (2)解 由上的证明过程知，⎪⎭⎫⎝⎛-+=-2,2)),((1y x y x y x f.(3)解 很显然If f=- 1R ⨯R ，即),()),)(((1y x y x f f=- .)2,2())()(),()(()),(()),)(((y x y x y x y x y x y x y x f y x f f =--+-++=-+= .四、解 }),(),,(),,(),,(),,{()(c c b b c b b a a a I R R r A=⋃=.}),(),,(),,(),,(),,{()(1b c a b c b b a a a RR R s =⋃=-.}),(),,(),,(),,{()(c a c b b a a a R t =. 五、证(1))(x xP ∀ P (2)P (c ) US(1) (3))))()(()((x R y Q x P x ∧→∀ P (4)))()(()(c R y Q c P ∧→ US(3) (5))()(c R y Q ∧ T(2)(4)I (6)Q (y ) T(5)I (7)R (c ) T(5)I (8))()(c R c P ∧ T(2)(7)I (9)))()((x R x P x ∧∀ UG(8) (10)))()(()(x R x P x y Q ∧∀∧ T(6)(9)I六、证 设G 是一棵阶数2≥的无向树，k k v v v v L 121...:-是G 中的最长路径. `若1v 和k v 至少有一个不是树叶，不妨设k v 不是树叶，即2)deg(≥k v ，则k v 除与1-k v 邻接外，还存在1+k v 与k v 邻接. 若1+k v 在L 上，则G 中存在圈，不可能. 若1+k v 不在L 上，则G 中存在一条比L 长1的路径1121...+-k k k v v v v v ，与L 是G 中最长路径矛盾.一、1. 1,3,5,7,11,13,17,19.2. 平行.3. 010, 100, 101, 110, 111.4. 2.5. 3.二、1(B); 2(A); 3(D); 4(C); 5(A). 三、(1)证任意∈),(),,(2211y x y x R ×R , 若),(),(2211y x f y x f =，则),(),(22221111y x y x y x y x -+=-+，进而2211y x y x +=+且2211y x y x -=-，于是21x x =且21y y =，从而f 是单射.任意∈),(q p R ×R , 取⎪⎩⎪⎨⎧-=+=22qp y q p x , 通过计算易知),(),(q p y x f =，因此f 是满射. 故f 是双射.(2) 解 由上面的证明知，f 存在逆函数且⎪⎭⎫⎝⎛-+=-2,2),(1y x y x y x f.又()()),(2,2,1y x y x y x f y x ff=⎪⎭⎫⎝⎛-+=- ，即If f=- 1R ×R ,而()()())2,2())()(),()((,,y x y x y x y x y x y x y x f y x ff=--+-++=++= .四、解 R 的传递闭包t (R )的关系图如下：于是，有t (R ) = {(1, 3), (3, 1), (2, 3), (4, 3), (4, 5), (6, 5), (1, 1), (3, 3)，(2,1)，(4,1)}. 五、解 首先写出命题公式()())()(p q rr q p A →→↔→→=的真值表如下：从真值表可得命题公式A 的主析取范式为：∨⌝∧⌝∧∨∧⌝∧∨∧∧=)()()(r q p r q p r q p A)()()(r q p r q p r q p ⌝∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝.命题公式A 的主合取范式为：)()(r q p r q p A ∨⌝∨⌝∧⌝∨⌝∨=.七、解 对于2, 3, 5, 7, 8，先组合两个最小的权2+3 = 5, 得5, 5, 7, 8；在所得到的序列中再组合5+5 = 10, 重新排列后为7, 8, 10；再组合7+8 =15, 得10, 15；最后组合10+15 = 25.2515108710875587532所求的最优2叉树树如下：。
