《离散数学期末复习习题试题》由会员分享，可在线阅读，更多相关《离散数学期末复习习题试题（7页珍藏版）》请在金锄头文库上搜索。
1、(R)=();.;.三、判断题1.在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（）2（）,不具备（）。5.设无向图G有12条边，有6个3度结点，其余结点度数均小于3，则G中至少有（）个命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数但不是整数”符号化（）、（）、（A，则R的性质为()A自反的B对称的C传递的，对称的D非自反的，传递的7.含有5个结点，;.离散数学一、 选择题 1. 设： P：张三可以作这件事， Q：李四可以作这件事，命题“张三或李四都可以 做这件事”的符号化为（）A、 P Q B 、P Q C、 P Q D、 2. 谓词公式 x(P(x) yR(
2、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（ ）的基数是（）A 1 B.2 C.3 D.45. 设 R、 S 是集合 A上的任意关系，则下面命题是真命题的是( ) 。A若 R、 S 是自反的，则 R S 是自反的B若 R、 S 是反自反的，则 R S 是反自反的C若 R、 S 是对称的，则 R S 是对称的D若 R、 S
3、 是传递的，则 R S 是传递的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/n B.n(n+1) C.nk D.n(k+1)-2m9. 设谓词 P(x) :x 是奇数， Q(x):x 是偶数，谓词公式 (x) (P(x) Q(x) 在下面哪个论域中是可满足
4、的。 ( )A 自然数集 B整数集 C实数集 D以上均不成立10. 设 C(x) ：x 是运动员， G(x) ：x 是强壮的。命题“没有一个运动员不是强 壮的”可符号化为（ ）A. x(C(x) G(x) B. x(C(x) G(x);.Q(6)R(a)(TT)(TT)(TF)FTTFFF设N表示非负整数集，R:是自由变元；在B(x,z)中，x是约束变元；用字母t来替代自由变元x(y)A(t,y)(x)B(的（G）必小于其结点数。（）8.在有向图中，结点间的可达关系是等价关系。（）9.同一谓词公式，式为（）。3.设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数
5、，则;.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.MN B.MN C.M N D.M-N12. 设 A=a,a ，下列选项错误的是（ ）A a p(A) B a p(A) Ca p(A) D a p(A)13. 设 A=1,2,3,4,5,p|ij,i,j A则 p 逆的性质是（ ）A.对称的 B. 自反的 C.反对称的 D.反自反，反对称，传递的14. 设 R和 S 是集合 A上的等级关系，则 RUS的对称性（ ）A.一定成立 B.一定不成立 C.不一定
6、成立 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)0 D.d(u,v) 01 2 3 4 5 6A C A A A B7C8 9 10 11 12 13 14 15 16D D C B B D A B D二、填空题1. 命题公式(P Q)的主析取范式为（），主合取式的编码表示为（） .2. 设 Q(x) ：x 是奇数， Z(x) ：x 是整数，则语句“不是所有整数都是奇数”所 对应的谓词公式为（）。
7、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、作用域为（）8. 设 A=（ 1，2，3，4 ）上的关系 R=, 则r(R)=( );.传递的，则RS是传递的6.集合A=1，2，10上的关系R=(x，y)|x+y=10且x，yQ(6)R(a)(TT)(TT)(TF)FTTFFF设N表示非负整数集，R:命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数但不是整数”符号化（）、（）、（|ij,i,jA则p逆的性质是（）A.对称的B.自反的C.反对称的D.反自反，反对称，传递的;.s(R)=( )12345678P Q x(Z(x) Q(x)x( Q(x) R(x) )反对称、传递9永假式y(P(x,y) Q(y,z),M M
9、Mx( Q(x) Z(x) ) x( Q(x) R(x) Z(x) )自反、反自反、对称永真式(P(x,y) Q(y,z) P(x,y),0 2 3;.式为（）。3.设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则无向图中恰有2个度为奇数的结点，则这两个结点必连通。（）四、计算题1.对下列谓词公式中的自由变元进式的真值x(P(x)Q(x)R(a),其中P：21,Q(x):x5,a，3，4）上的关系R=,则r(R)=();.;.s;.三、判断题1. 在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（ ）2. 公式 x(P(x) Q(x) R(y) 中
10、 x 的作用域为 P(x) 。（ ）3.A B=A C，则 B=C（ ）4.A，B是集合。则命题 A B和 AB可能同时成立（ ）5. 若 R是集合 A上的传递关系，则 R2 也是集合 A上的传递关系。（ ）6. 若 R和 S 是集合 A上的任意两个自反关系，则 ROS也是自反的（ ）。7. 任一图 G的（ G）必小于其结点数。（ ）8. 在有向图中，结点间的可达关系是等价关系。（ ）9. 同一谓词公式，指定不同的论域，其真值不一定相同。（ ）10. 任意一个谓词公式都与一个前束范式等价。（ ）11. 若 P Q=Q， P Q= ，则 P= （ ）;.）。4.设A=（1，2，3）上的关系R=,
11、关系具备的（G）必小于其结点数。（）8.在有向图中，结点间的可达关系是等价关系。（）9.同一谓词公式，14.设R和S是集合A上的等级关系，则RUS的对称性（）A.一定成立B.一定不成立C.不一定成立D.S是自反的B若R、S是反自反的，则RS是反自反的C若R、S是对称的，则RS是对称的D若R、S是;.12. 若 A-B B，则 B A（ ）13. 一个不是自反关系， 一定是反自反关系。（ ）14. 若 R和 S 是集合 A上的任意两个对称关系，则 ROS也是对称的（ ）15. 若无向图中恰有 2 个度为奇数的结点，则这两个结点必连通。（ ）16. 在有向图中有 2 个奇度结点，则它们一个可达另一
12、个或互相可达。（ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 四、计算题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)T TT3. 对下列谓词公式中的自由变元进行替换 ( x) P(x,y) ( z) Q(x,z) ( x) R(x,y)解：在 P(x,y) 和 Q(x,z) 中 x 是自由变
