安工大离散数学试卷

20082009学年第一学期期末考试离散数学B试卷（A）一单项选择题（112=12分）1下列选项中（ ）是命题变元P，Q的极小项(A) PP Q (B) P Q (C) PQ (D) PP Q 2以下命题公式为永真式的是( ) (A) P （P QR) (B)（PP）P (C) (PQ) Q (D) P(QR)3. 设R为实数集，R+=xxRx0, *是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）(A) R+中的有理数 (B) R+中的无理数 (C) R+中的自然数 (D) 1,2,34若P：今天下雪了；Q：路滑；则“虽然今天下雪了，但路不滑”，可符号化为( ) （A）P Q （B）PQ （C）PQ （4）P Q5. 下列式子正确的是 ( )(A) (B) ， (C) (D) 6. 设集合Aa,b,c,A上的二元关系R,，,则s(R)=( ) (A) RIA (B)R (C) R (D) RIA 7设Aa,b,c,d ,A上的等价关系R=,IA,则对应于A的划分是（ ）(A) a,b,c,d (B) a,b,c,d (C) a,b,c,d (D) a,b,c,d 8. 设集合A1,2,3,10,在集合A上定义的运算*，不是封闭的为( )(A) a,bA, a*b=lcma,b(最小公倍数) (B) a,bA, a*b=gcda,b(最大公约数)(C)a,bA, a*b=maxa,b (D) a,bA, a*b=mina,b9. 在自然数N上定义的二元运算，不满足结合律的是( )(A) ab=min(a,b ) (B) ab=a+b (C) ab=GCDa,b(a,b的最大公约数) (D) ab=a(mod)b10在图G中，结点总度数与边数的关系是( )(A) deg(vi)=2E (B) deg(vi)= E （C） (D) 11由集合A的一个覆盖确定A的元素间关系为（ ） （A）全序关系 （B）等价关系 （C）偏序关系 （D）相容关系12下列论述中，错误的为（ ） （A）循环群必为阿贝尔群 （B）循环群的生成元唯一 （C）循环群的子群为循环群 （D）阶数为3的群必为阿贝尔群二填空题（218=36分） 1设L(x)：x是人，J(x)：x犯错误，. 那么命题“没有不犯错误的人”符号化 为 ，量词辖域是 2设R1，R2是集合A1,2,3,4，5上的二元关系,其中 R1, R2=, 则R1R2 ；3设论域为a,b,c，则（x）S(x)等价于命题公式 ， （x）S(x) 等价于命题公式 ; 4设A是非空集合，集合代数(P(A)，)中，P(A)对运算的幺元是 ， P(A)对运算的幺元 是 .5设G为连通简单平面图，且有11个顶点，5个面，则边 ；6设R是A上的二元关系，则r(R)= ,s（R）= ；7. 设R是A上的二元关系，且具有对称性，反对称性，自反性和传递性，则R是 ，其关系矩阵是 ；8.设是一个偏序集，若S中任意两个元素都有 和 则称是一个格；9.设I是整数集，在I上定义二元运算*为a*b=a+b+a.b,其中+和*是数的加法和乘法，则的幺元是 ，零元是 ；10.在一棵根树中，仅有一个结点的入度为 ，称为树根，其余结点的入度均为 ；三（10分）符号化下列命题，并用推理规则推证其结论如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DEIPHI语言或者C+语言，那么他就会编程序。因 此如果他是计算机系本科生，那么他就会编程序。 四（10分） 求P（Q R）的主合取范式和主析取范式； 五（8分）设A，B，C为任意集合，试证明 A（BC）=（AB）（AC） 六（10分）设A1, 2, 3, 4, 6，8，12，14,R是A上的整除关系 （1）证明R是A上的偏序关系，并求COVA，然后画出哈斯图,并判断此偏序集是否为格； （2）令B=2，3，4，6，求B的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。 七（6分）设是独异点，且对G中每个元素x有x*x=e(e为幺元)，证明是一个交换群. 八（10分）设T 是无向树，T中度数最大的顶点有2个，它们的度数为K（K不小2），证明T中至少2K2片树叶。 20082009学年第一学期期末考试离散数学BA答案一单项选择题(121=12分)1（C）；2（B）；3.(A)；4(B)；5(B) ；6.(C)；7.(D)；8.(A);9.(D)；10. (C)；11.(D) 12.(B)二填空题(182=36分) 1x（L（x）J（x）;或者（x）(L(x) J（x）, L（x）J（x） 2,;3S(a)S(b)S(c); S(a)S(b)S(c)4；A.; 514 ;6RIA,RRC7.恒等关系（IA） 单位矩阵8.上确界 下确界9.0，-1； 10.0，1三(10分)其中符号化命题10分，利用推理规则证明5分设P：他是计算机系本科生。 Q：他是计算机系研究生。 R：他学过DELPHI语言。 S：他学过C+语言。 T：他会编程序 故本题符号化为：前提：（PQ）（RS），（RS）T，结论：PT证明：（1）P P（附加前提） （2）PQ T（1），I （3）（PQ）（RS） P （4）RS T （2），（3），I （5）R T（4），I （6）RS T（5），I （7）（RS）T P （8）T T（6），（7），I （9）PT CP规则四（10分）其中主析取范式和主合取范式各占分 主析取范式：P（Q R） P （Q R) (P Q)(P R) (P Q(RR)(P(QQ) R) ( P QR) ( P QR) (PQ R) (PQ R)（ P QR) ( P QR) (PQ R)主合取范式：（PQR）(PQR)(PQR)(PQR)( PQR) 五(6分) 证明：左边=A(BC)=A(B)(C)右边=(A(B)(A(C) =A(B)(C)故左边=右边六(12分) 解 （1）不难验证R具有自反性；反对称性；传递性； 故R是偏序关系. COVA=,，,作的哈斯图如下所示,8,12没有上确界，故不是格 （2）B的最大元：无，最小元：无； 极大元：4，6，极小元：2，3 下界：1， 下确界：1 上界：12， 上确界：12 七(6分)证明:xG,由题意知：x-1=x,即G中每个元素都有逆元，因此是群。 x,yG,x*y=(x*y)-1=y-1*x-1=y*x于是 所以是一个交换群.八(10分) 证明 设T中有x片树叶，y个分支点，于是T中有x+ y个结点，有x+ y-1条边， 由握手定理知：T中所有结点度数的和为：2（x+ y-1） 因为树叶的度数为1，任一分支点的度数大于等于2， 则T中所有结点度数的和大于等于x*1+2(y-2)+k+k=x+2y+2k-4, 故有: 2（x+ y-1）x+2y+2k-4, 即:x2k-2