离散数学期末复习习题.doc

离散数学期末复习习题一、 选择题 $离散数学期末复习习题“张三或李四都可以做这件事”的符号化为（）A、PQ B、PQC、PQD、2. 谓词公式x(P(x)yR(y)Q(x)中量词x 的作用域是（）A. x(P(x)yR(y) B.P(x)C. (P(x)yR(y) D.P(x),Q(x)3. 若个体域为整体域,下列公式中哪个值为真？（）A. x y(x+y=0) B. y x(x+y=0)C. x y(x+y=0) D. x y(x+y=0)4. 空集的幂集P（）的基数是（）A1B.2C.3D.45. 设R、S是集合A上的任意关系,则下面命题是真命题的是( )。A若R、S是自反的,则RS是自反的B若R、S是反自反的,则RS是反自反的C若R、S是对称的,则RS是对称的D若R、S是传递的,则RS是传递的6. 集合A=1,2,10上的关系R=(x,y)|x+y=10且x,yA,则R的性质为 ()A自反的B对称的 C传递的,对称的D非自反的,传递的7.含有5个结点,3条边的不同构的简单图有（ ）A.2个B.3个C.4个D.5个8.设G（n,m）,且G中每个结点的度数不是K就是K+1,则G中度数为K的结点数（）A.2/nB.n(n+1)C.nkD.n(k+1)-2m9. 设谓词P(x) :x是奇数,Q(x):x是偶数,谓词公式$(x) (P(x) Q(x)在下面哪个论域中是可满足的。( )A自然数集B整数集C实数集D以上均不成立10. 设C(x)：x 是运动员,G(x)：x 是强壮的。命题“没有一个运动员不是强壮的”可符号化为（ ）A. x(C(x)G(x) B. x(C(x)G(x)C. x(C(x)G(x) D. x(C(x)G(x)11. 设集合M=x|f（x）=0,N=x|g（x）=0,则方程f（x）g（x）=0的解集是（ ）A.MNB.MNC.MN D.M-N12. 设A=a,a,下列选项错误的是（ ）Aap(A)Bap(A) Cap(A) Dap(A)13.设A=1,2,3,4,5,p|ij,i,jA则p逆的性质是（ ）A.对称的B.自反的C.反对称的D.反自反,反对称,传递的14.设R和S是集合A上的等级关系,则RUS的对称性（ ）A.一定成立B.一定不成立C.不一定成立D.不可能成立15. K4中含有3条边的不同构生成子图有（ ）A.1个 B.3个 C.4个D.2个16. 设G=为无向图,u,v V ,若u,v 连通,则（ ） A.d(u,v)0 B.d(u,v)=0 C.d(u,v)0D.d(u,v)012345678910111213141516ACAA ABCDDCBBDABD二、填空题1. 命题公式(PQ)的主析取范式为（）,主合取式的编码表示为（）.2. 设Q(x)：x 是奇数,Z(x)：x 是整数,则语句“不是所有整数都是奇数”所对应的谓词公式为（）。3. 设个体域为全总个体域,R(x)：x 是实数,Q(x)：x 是有理数,Z(x)：x 是整数,则命题“所有的有理数是实数”,“有些有理数是整数”,“有些有理数是实数但不是整数”符号化（）、（）、（）。4.设A=（1,2,3）上的关系R=,关系具备（）,不具备（）。5.设无向图G 有12条边,有6个3度结点,其余结点度数均小于3,则G 中至少有（）个结点。6. 任意两个不同的极小项的合取式为（）。全体极小项的析取式必为（）。7. x y(P(x,y)Q(y,z)xP(x,y)中x 的作用域为（）,y 的作用域为（）,x 的作用域为（）8. 设A=（1,2,3,4）上的关系R=,则r(R)=( ) s(R)=( )1PQM0 M2 M32x(Z(x) Q(x)3x( Q(x) R(x) )$x( Q(x) Z(x) )$x( Q(x)R(x)Z(x) )4反对称、传递自反、反自反、对称596永假式永真式7y(P(x,y)Q(y,z)(P(x,y)Q(y,z)P(x,y)8,三、判断题1.在谓词公式中,一个变量只能是自由变量或约束变量中的一种。（）2.公式x(P(x)Q(x)R(y)中x 的作用域为P(x)。（）3.AB=AC,则B=C（）4.A,B是集合。则命题AB和AB可能同时成立（）5.若R是集合A上的传递关系,则R2也是集合A上的传递关系。（）6.若R和S是集合A上的任意两个自反关系,则ROS也是自反的（）。7.任一图G的（G）必小于其结点数。（）8.在有向图中,结点间的可达关系是等价关系。（）9.同一谓词公式,指定不同的论域,其真值不一定相同。（）10.任意一个谓词公式都与一个前束范式等价。（）11.若PQ=Q,PQ= ,则P= （）12.若A-BB,则BA（）13.一个不是自反关系,一定是反自反关系。（）14.若R和S是集合A上的任意两个对称关系,则ROS也是对称的（）15.若无向图中恰有2个度为奇数的结点,则这两个结点必连通。（）16.在有向图中有2个奇度结点,则它们一个可达另一个或互相可达。（）12345678910111213141516四、计算题1.对下列谓词公式中的自由变元进行替换 ($y)A(x,y)(x)B(x,z) ($x)(z)C(x,y,z)解：在A(x,y)中,x是自由变元；在B(x,z)中,x是约束变元；用字母t来替代自由变元x($y)A(t,y)(x)B(x,z) ($x)(z)C(x,y,z)2.求下列公式的真值x(P(x)Q(x),其中P(x):x=1,Q(x):x=2,且论域是1,2解：x(P(x)Q(x)(P(1)Q(1) (P(2)Q(2)TTT3. 对下列谓词公式中的自由变元进行替换($x)P(x,y) (z)Q(x,z) (x)R(x,y)解：在P(x,y)和Q(x,z)中x是自由变元；在R(x,y)中x是约束变元；用字母u替代自由变元x($x)P(u,y) (z)Q(u,z) (x)R(x,y)4. 求下列公式的真值x(P(x)Q(x) R(a),其中P：21,Q(x):x5,a:5且论域-2,3,6解：x(PQ(x) R(a)(PQ(-2) (PQ(3) (PQ(6) R(a)(TT) (TT) (TF) F TTFF F5、设N表示非负整数集,R:NN,xRy定义为x+2y=10确定Dom(R)和Ran(R)。解：y=0,x=10y=1,x=8y=2,x=6y=3,x=4y=4,x=2y=5,x=0R=,Dom(R)=0,2,4,6,8,10Ran(R)=5,4,3,2,1,06、设有向图D