离散数学模拟题[川大版].doc

离散数学押题卷 1、下列是真命题的有（　　CD　） A． ； B．； C． ； D． 。 2、下列集合中相等的有（ BC ） A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。 3、设A={1，2，3}，则A上的二元关系有（ C ）个。 A． 23 ； B． 32 ； C． ； D． 。 4、设R，S是集合A上的关系，则下列说法正确的是（ A ） A．若R，S 是自反的， 则是自反的； B．若R，S 是反自反的， 则是反自反的； C．若R，S 是对称的， 则是对称的； D．若R，S 是传递的， 则是传递的。 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 则P（A）/ R=（ D ） A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D．{{}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（ C ） 7、下列函数是双射的为（ A ） A．f : IE , f (x) = 2x ； B．f : NNN, f (n) = n , n+1 ； C．f : RI , f (x) = [x] ； D．f :IN, f (x) = | x | 。 （注：I—整数集，E—偶数集， N—自然数集，R—实数集） 8、图 中 从v1到v3长度为3 的通路有（ D ）条。 A． 0； B． 1； C． 2； D． 3。 9、下图中既不是Eular图，也不是Hamilton图的图是（ B ） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。 A．1； B．2； C．3； D．4 。 11.一个含有5个命题变元公式，该公式相应的主合取范式仅有10项，那么该公式为（D） A．矛盾式 B.永真式 C.不可满足式 D.A,B,C都不正确 12.一个含有4个命题变元公式，该公式相应的主析取范式仅有16项，那么该公式为（B） A．矛盾式 B.永真式 C.不可满足式 D.A,B,C都不正确 by@了不起的曹布斯 18.设 f，g是自然数集N上的函数， 则2(x+1) 。 19.设A={a，b，c}，A上二元关系R={ a, a , a, b , a, c , c, c} , 则s（R）= ； 。 20.A={1，2，3，4，5，6}，A上二元关系，则用列举法T=； T的关系图为 ； T具有反 对称性、反自反性； 性质。 21.集合的幂集= ； 22.P，Q真值为0 ；R，S真值为1。则的真值为 1 。 23.的主合取范式为 。 24.设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 任意x，如果x是素数则存在一个y，y是奇数且y整除x ； 。 25.谓词的前束范式为 。 26.证明：在（n,m）图中 证明： （根据握手定律，总的点度之和2m，为最小点度，为最大点度 ） 成立当且仅当（n,m）为正则图时等号成立） 27.设G是（n,m）简单二部图。证明：m≦ 解：设一个顶点为n1,另一个为n-n1,则m=n1(n-n1)=-(n1-n/2)+ 所以，m≦ by@了不起的曹布斯 28.若u和v是图G中仅有的两个奇数度结点，证明u和v必是连通的。 证：（反证法）设v与u不连通 ∴G={V1，V2} ，v与u分别属于V1，V2二个子图 ∵ v与u是G中仅有的二个奇数度结点 ∴v与u即是V1与V2中仅有的一个奇数度结点，与欧拉定理的 推论相矛盾,故v与u必连通 （反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇数度结点的个数为偶数。而两个连通分支中，奇度点的个数为奇数，矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立。） by@了不起的曹布斯 29. 30.用等值演