离散数学题目.docx

20062007学年第一学期期末考试离散数学试卷（A）一单项选择题（210=20分）1设命题公式(P(QP)，记作G，使G的真值指派为0的P，Q的真值是( )(A) (0,0) (B) (0,1) (C) (1,0) (D) (1,1)2与命题公式P（QR）等价的公式是( ) (A) (PQ)R (B)(PQ)R (C) (PQ)R (D) P(QR)3. 命题公式(PQ)P是( )(A) 永真式 (B) 永假式 (C) 可满足式 (D) 合取范式4在谓词演算中，P(a)是的有效结论，根据是 ( ) (A)US规则 (B) UG规则 (C)ES规则 (D)EG规则5. 设S1，S2, S3P(), S4P()，以下命题为假的是( )(A) S2S4 (B) S1 S3， (C) S4 S2 (D) S4 S36. 设集合Aa,b,c,A上的二元关系R,不具备( )性质. (A) 传递性 (B) 反对称性 (C) 对称性 (D) 自反性 7设A0,a,B=1,a,3,则AB的恒等关系是( )(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=ab (B) ab=a+2b (C) ab=maxa,b (D) ab=ab10在图G中，结点总度数与边数的关系是( )(A) deg(vi)=2E (B) deg(vi)= E （C） (D) 二填空题（212=24分） 1设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化 为 2谓词公式中量词x的辖域是 ；3设R1，R2是集合A1,2,3,4上的二元关系,其中 R1, R2=, 则R1R2 ；4设是A上的二元关系， 则R2是R1的 闭包5设A是非空集合，集合代数(P(A)，)中，P(A)对运算的单位元是 ， P(A)对运算的单位元 是 .；6在布尔代数中，有成立. 则该式的对偶式 也一定成立；. 7设为连通平面图且有r个面，则r ；8设G是n个结点的无向完全图，则图G的边数为 ,其点连通度为 ；9. 有限布尔格中有n个原子，则此布尔格中元素个数为 ；104个元素的集合共有 个不同的划分；三（10分）符号化下列命题，并用推理规则推证其结论（1）如果6是偶数，则7被2除不尽；（2）或5不是素数，或7被2除尽；（3）但5是素数； （4）所以6是奇数；四（10分） 求(PQ) (PR)的主和取范式和主析取范式； 五（8分）设A，B为任意集合，试证明六（10分）设A1,2,3,4,5,R是A上的二元关系R,证明R是A上的偏序关系，并画出哈斯图,并判断此偏序集是否为格；七（8分）设群中每个元素的逆元素就是其自身，则G是一个交换群. 八（10分）设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. 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-2200 9-2010 学年第一学期期末考试离散数学B 试卷（A）一单项选择题(每题2分，共30分)1下列命题公式中不是重言式的是（）A. (PQ)(QR) B. P(QQ) C. (PQ)P D. P(PQ)2在0（ ）之间写上正确的符号。A. = B. C. D. 3设个体域是整数集，则下列命题的真值为真的是（）A.x$y (xy=y) B. $xy(x+y=y)C.$xy(x+y=x) D. x$y(y=2x) 4关于谓词公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中错误的是（）A（x）的辖域是（y）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元C（x）的辖域是P（x,y）Dx是该谓词公式的约束变元5设论域D=a,b，与公式(x)A（x）等价的命题公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质（ ）。A.自反的B.对称的 C.传递的，对称的 D. 传递的7设A=a,a，下列命题错误的是（ ）。A. aP(A)B. aP(A)C. aP(A)D. aP(A)8设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f（）A仅是满射B仅是入射C是双射D无逆函数9设A=1，2，3，4，5，A上二元关系R=1，2，3，4，2，2，S=2，4，3，1，4，2，则S-1R-1的运算结果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，410设有代数系统G=A，*，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A矛盾式B重言式C可满足式D公式pq11在自然数集N上，下列哪种运算是可结合的？（ ） A. a*b=a-bB. a*b=maxa,bC.a*b=a+2bD. a*b=|a-b|12、有限布尔代数的元素的个数一定等于（ ）。A . 偶数B. 奇数 C. 4的倍数 D. 2的正整数次幂13设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 A. 10 B.4 C. 8 D. 1214设无向图G的边数为m，结点数为n，则G是树等价于（）AG连通且m=n+1BG连通且n=m+1CG连通且m=2nD每对结点之间至少有一条通路15设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( )A. 自然数B.实数C .复数D . (A)-(C)均成立二、填空题（每题2分，共20分）1公式(PQ)(PQ)化简为 ，公式 Q(P(PQ)可化简为 。2命题“存在一些人是大学生”的否定是_。3公式（x）(A(x)B(y，x) （$z）（ C(m，z)D(n)）中，自由变元是 ，约束变元是 。4若集合S的基数|S|=5，则S的幂集的基数|P(S)|= 。5设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，则R= 。6设A=a,b,c,d, R=a,c，c,b，b,a，a,d，则r(R)= ,s(R)= ,t(R)= 。7设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是 ，零元是 。8有n个结点的树，其结点度数之和是 。9.群的等幂元是 ，有 个。10.n阶无向完全图Kn 的边数是 ，每个结点的度数是 。三（6分）求命题公式(PR)(QR)P的主析取范式和主合取范式。四（6分）证明：A(BC)，C(DE)，F(DE),A=BF五（5分）证明：(AB)(AC)=A(BC)六（10分）设A=1，2，3，P（A）是A的幂集，是集合的包含关系，证明：P（A），偏序集，画出它的哈斯图，并证明该偏序集为格。七（10分）设A=1,2,10。下列哪个是A的划分？若是划分，则写出它们诱导的等价关系。（1）B=1,3,6,2,8,10,4,5,7;（2）C=1,5,7,2,4,8,9,3,5,6,10;（3）D=1,2,7,3,5,10,4,6,8,9八（8分）I上的二元运算*定义为：a,bI，a*b=a+b-2。试证：为群。九（5分）设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？20092010学年第一学期期末考试离散数学B试卷（A）一单项选择题(152=30分)1（A）；2（D）；3.(D)；4(B)；5(A) ；6.(B)；7.(B)；8.(C);9.(A)；10. (B)；11.(B) 12.(D) 13.(D); 14.(B);15.(A) 二填空题(171=17分) 1P QP;2所有人都不是大学生； 3y,m,n x,z;4. 32;5R=, 6r(R)=,a,c，c,b，b,a，a,d S(R)= a,c，c,b，b,a，a,d, t(R)= a,c，c,b，b,a，a,d,.,，72,68.2(n-1)9.e,110n(n-1)/2,(n-1)三(6分)其中主析取范式和主合取范式各占4分 (PR)(QR)P（析取范式）(P(QQ)R)(PP)QR)(P(QQ)(RR)(PQR)(PQR)(PQR)(PQR)( PQR)( PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)（(PR)(QR)P）(PQR)(PQR）（原公式否定的主析取范式）(PR)(QR)P (PQR)(PQR)（主合取范式）四(8分)(1) A P（附加前提）(2) A(BC) P (3) BC T（1），（2）(4) B P(附加前提)(5) C T（3），（4）(6) C(DE) P(7) DE T（5），（6）(8) F(DE) P(9) F T（7），（8）(10) BF CP 证明方法不唯一，只要遵循逻辑规则即可。五(6分)解(A-B)(A-C)=(AB)(AC) =A (B) (C)=A(B C)= A-(BC)六（10分）证明: 验证P（A）中运算满足自反，反对称，传递；从哈斯图中证明任意两个元素都有上确界和下确界即可。 七(10分)（1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关系是I,。八(8分) 证明：（1）a,b I，a+b-2I，*满足封闭律。（2）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。（3）记e=2。对aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。（4）对aI，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 综上所述，为群。九（5分）解：设G中度数小于3的顶点有k个，由握手定理 24=知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。2010-2011学年第一学期期末考试离散数学B试卷（A）一单项选择题(每题2分，共30分)1、设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (3，4，62，3，4)=（ ）.A O/BC，D，2、设有A=a,b,c上的关系R=,，则R具有( ) A. 自反性 B. 对称性 C. 传递性 D. 反对称性3、若A-B=，则下列哪个结论不可能正确？( )(A) A= (B) B=(C) AB (D) BA4、判断下列命题哪个正确？()(A) 若ABAC，则BC (B) a,b=b,a (C) P(AB)P(A)P(B) （P(S)表示S的幂集）(D) 若A为非空集，则AAA成立。5、设A=a,a，下列命题错误的是（ ）。(A) aP(A)(B) aP(A)(C) aP(A)(D) aP(A)6、集合的以下运算律不成立的是( ).A. AB=BAB. AB=BAC. AB=BAD. A-B=B-A7、下述不是命题的是( ). A. 今天天气真好啊! B. 明天下雨. C. 2是偶数. D. 这朵花是红色的8、设P,Q,R是命题公式,则（PR）( ). A. P B. PR C. R D. R9、设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于( )A.(x)A(x)B B. (x)A(x)B C. A(x)B D.(x)A(x)(x)B10、谓词公式(x)(P(x)(y)R(y)Q(x)中的x( ). A.只是约束变元 B.只是自由变元 C.既非约束变元又非自由变元 D.既是约束变元又是自由变元11、设个体域A=a,b，公式xP(x)xS(x)在A中消去量词后应为（）.AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)12、设R为实数集，函数f：RR，f(x)=2x，则f是（ ）.A满射函数B入射函数C双射函数D非入射非满射13、下列运算中关于整数集不能构成半群的是（）.Aab=maxa, bBab=bCab=2abDab=|a-b|14、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）.A2个面B3个面 C4个面D5个面15、给定n个结点的一个图，它还是一个树的下列说法中，（）是不对的。A.无回路的连通图B.无回路但若增加一条新边就会形成回路C.连通且e=v-1，其中e是边数，v是结点数D.所有结点的度数2二、填空题（每空1分，共20分）1、命题P：若3+25，则三角形有3条边。P 的真值为_。2、命题“存在一些人是大学生”的否定是_。3、使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x.4、A=1,2,3,4上二元关系R=2，4，3，3，4，2，R的关系矩阵MR中m14= _5、设A=1，2，3，则A上的二元关系有 个，若R是集合A上的全域关系，则集合A关于R的商集为 。6、设X=1，2，3，函数f：XX，函数g：XX，f=,g=,，则fg=_，gf=_.7、当f:XY是_函数时，f有逆函数，且f -1。f=_。8、设A=1,5,8，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，幺元是_，零元是_。9、设B,，0，1是布尔代数，其中代表补运算，对任意的aB,有aa=_,aa=_.10、设图G1=, G2=,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。11、下图的点连通度为 ，边连通度为_.12、在一棵有2个2度顶点，3个3度顶点，其余顶点都是树叶的无向树中应该有_片树叶。三、计算题（每5分，共20分）1、给定个体域D=a,b,A(a,a)=T,A(a,b)=F,A(b,a)