1、1设 7|) ,5()(| xExxBxNxxA 且且（ N：自然数集， E+ 正偶数） 则 BA 0， 1， 2， 3， 4， 6； 。 2 A， B， C 表示三个集合，文图中 阴影部分的集合表达式为 ACB )( 。 3设 P， Q 的真值为 0， R， S 的真值为 1，则 )()( SRPRQP 的真值 = 1 。 4设 A=1， 2， 3， 4， A 上关系图为 则 R2 = , , , 。 5设 A=a， b， c， d，其上偏序关系 R 的哈斯图为 则 R= , IA 。 6 图 的补图为 。 7.P：你努力， Q：你失败。“除非你努力，否则你将失败”的翻译为 QP ； ；“虽
2、然你努力了，但还是失败了”的翻译为 QP 。 8.设 A=2， 3， 4， 5， 6上的二元关系 |, 是质数xyxyxR ，则 R= （列 举法）。 R 的关系矩阵 MR= A B C 。 9.设 A=1， 2， 3，则 A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系 R= 。 10.n 个结点的无向完全图 Kn 的边数为 )1(21 nn ，欧拉图的充要条件是 :图中无奇度结点且连通 11.设 A=a， b， c， A 上二元关系 R= , , , 则 s（ R） = a, c,a, b,c, c,c, a,b, a,a, a 。 12. 集合 2,2,A
3、的幂集 A2 = 2,2, ,2 ,2, 。 13.若 P， Q，为二命题， QP 真值为 0 当且仅当 P 真值为 1， Q 的真值为 0 。 14.命题“对于任意给定的正实数，都存在比它大的实数”令 F(x)： x 为实数， yxyxL :),(则命题的逻辑谓词公式为 ),()()0,()( xyLyFyxLxFx 。 15. 谓词合式公式 )()( xxQxxP 的前束范式为 )()( xQxPx 。 16.将量词辖域中出现的 约束变元 和指 导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。 17. 1,1A ,则 A 的 幂集 )(AP = 。 20.n 阶完全图结
4、点 v 的度数 d(v) = n-1 。 21.设 n 阶图 G 中有 m 条边，每个结点的度数不是 k 的是 k+1，若 G 中有 Nk 个 k 度顶点，Nk+1 个 k+1 度顶点，则 N k = n(k+1)-2m 。 23.任何 (n,m) 图 G = (V,E) , 边与顶点数的关系是 Vv mvd 2)( 。 24.当 n 为 奇数 时 ,非平凡无向完全图 Kn是欧拉图。 27.n 阶完全图 Kn 的边数为 )1(21 nn 。 28. 右图 的 邻 接 矩 阵 A= 0110001011001010。 30.集合 A= , 的幂集 P(A) = 。 31 设 A=1， 2， 3，
5、 4， A 上二元关系 R=， ， ， 画出 R的关系图 。 32 设 A=, , B=, 则 BA = , , , ， ,、 。 BA = , 。 33.设 |A|=3， 则 AA ， A 上有 29 个二元关系。 34.A=1， 2， 3上关系 R= , , 时， R 既是对称的又是反对称的。 35.偏序集 RA, 的哈斯图为 ， 则 R = ,+IA 。 36.Q：我将去上海， R：我有时间，公式 )()( QRRQ 的 自然语言为 我将去上海当且仅当我有空 。 37 若 , , 21 mSSSS 是集合 A 的一个分划， 则它应满足 。 38.若 P， Q 为二命题， QP 真值为 1
6、，当且仅当 P， Q 的真值相同 。 39. )()( xxGxxF 的前束范式为 )()( xGxFx 。 40. 能够断真假的阵述句 称为命题。 41.命题 P Q 的真值为 0，当且仅当 P 的真值为 1， Q 的真值为 0 。 42 一个命题含有 4 个原子命题，则对其所有可能赋值有 16 种。 43.所有小项的析取式为 永真式 。 44.令 P（ x）： x 是质数， E（ x）： x 是偶数， Q（ x）： x 是奇数， D（ x， y）： x 除尽 y. 则) ) )(),()( yEyxDyxEx 的汉语翻译为 任意两数 x、 y,如果 x 是偶数且能除尽 y，则 y 一定是偶
7、数； 。 45.若 R 是集合 A 上的偏序关系，则 R 满足 自反性、反对称性、传递性 46.设 G 是 n 阶完全图，则 G 的边数 m= )1(21 nn 。 47.设集合 A,B，其中 A 1,2,3, B= 1,2, 则 A - B _ 3; _; (A) - (B) _ 3,1,3,2,3,1,2,3. _ . 48.设有限集合 A, |A| = n, 则 |(AA)| = _ 22n ._. 49. 已知命题公式 G (PQ) R，则 G 的主析取范式是 _(P Q R)._. 51 设 A、 B 为两个集合 , A= 1,2,4, B = 3,4, 则从 AB _4, _; A
8、B_1, 2, 3, 4, _;A B _1, 2._ . 52. 设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是 _自反性；对称性；传递性 ._. 53. 设命题公式 G (P(QR)，则使公式 G 为真的解释有 _(1, 0, 0), (1, 0, 1), (1, 1, 0)._. 54.设集合 A 2, 3, 4, 5, 6， R 是 A 上的整除，则 R 以集合形式 (列举法 )记为 _ _(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6). 55 设一阶逻辑公式 G = xP(x)xQ(x)，则 G 的前
9、束范式是 _x(P(x) Q(x)_. 56.若 2 3, 5 3, 5x ，则 x=_。 57. 设谓词的定义域为 a, b,将表达式 xR(x) xS(x)中量词消除，写成与之对应的命题公式是 _(R(a) R(b) (S(a) S(b)_. 58. 设集合 A 1, 2, 3, 4， A 上的二元关系 R (1,1),(1,2),(2,3)。则 R2 _(1, 1),(1, 2),(1, 3)_. 59. 设 A=1,2,3,4, A 上的 二 元关 系 R=, ，则 0R _ ，R2=_， (R-1)2=_。 60.令 F(x):x 是鸟， G(x):x 会飞翔，则“所有鸟都会飞翔”应
10、该符号化为 _。 二、选择题 1、设 A=1， 2， 3，则 A 上的二元关系有（ C ）个。 A 23 ； B 32 ； C 332 ； D 223 。 2.设 R， S 是集合 A 上的关系，则下列说法正确的是（ A ） A若 R， S 是自反的， 则 SR 是自反的； B若 R， S 是反自反的， 则 SR 是反自反的； C若 R， S 是对称的， 则 SR 是对称的； D若 R， S 是传递的， 则 SR 是传递的。 3、设 A=1， 2， 3， 4， P（ A）（ A 的幂集）上规定二元系如下 |(|)(,|, tsAptstsR 则 P（ A） / R=（ D ） A A ； B
11、P(A) ； C 1， 1， 2， 1， 2， 3， 1， 2， 3， 4； D ， 2， 2， 3， 2， 3， 4， A 4、设 A= ， 1， 1， 3， 1， 2， 3则 A 上包含关系“ ”的哈斯图为（ C ） 5、图 中 从 v1 到 v3 长度为 3 的通路有（ D ）条。 A 0； B 1； C 2； D 3。 6、下图中既不是 Eular 图，也不是 Hamilton 图的图是（ B ） 7、在一棵树中有 7 片树叶， 3 个 3 度结点，其余都是 4 度结点则该树有（ A ）个 4度结点。 A 1； B 2； C 3； D 4 。 8、设 2,1,1,S ，则 S2 有（
12、D ）个元素。 A 3； B 6； C 7； D 8 。 9、 设 3 ,2 ,1 S ，定义 SS 上的等价关系 , | , cbdaSSdcSSbadcbaR 则由 R 产 生的 SS 上一个划分共有（ B ）个分块。 A 4； B 5； C 6； D 9 。 10、设 3 ,2 ,1 S ， S 上关系 R 的关系图为 则 R 具有（ D ）性质。 A自反性、对称性、传递性； B反自反性、反对称性； C反自反性、反对称性、传递性； D自反性 。 11、在如下的有向图中 ，从 V1 到 V4 长度为 3 的道路有（ B ）条。 A 1； B 2； C 3； D 4 。 12、在如下各图中（
13、 B ）欧拉图。 13、 下述命题公式中，是重言式的为（ C ）。 A、 )()( qpqp ； B、 )()()( pqqpqp ； C、 qqp )( ； D、 qpp )( 。 14、 设 S=1， 2， 3， R 为 S 上的关系，其关系图为 则 R 具有（ D ）的性质。 A、 自反、对称、传递； B、什么性质也没有； C、 反自反、反对称、传递； D、自反、对称、反对称、传递。 15、 设 2,1,1,S ，则有（ A ） S 。 A、 1,2 ； B、 1,2 ； C、 1 ； D、 2 。 16、 设 A=1 ,2 ,3 ，则 A 上有（ D ）个二元关系。 A、 23 ； B
14、、 32 ； C、 32 ； D、 232 。 17、全体小项合取式为（ C ）。 A、可满足式； B、矛盾式； C、永真式； D、 A， B， C 都有可能。 18、 下列语句是命题的有（ AC ）。 A、 明年中秋节的晚上是晴天； B、 0yx ； C、 0xy 当且仅当 x 和 y 都大于 0； D、我正在说谎。 19、 下列各命题中 真值为真的命题有（ AD ）。 B、 2+2=4 当且仅当 3 是奇数； B、 2+2=4 当且仅当 3 不是奇数； C、 2+2 4 当且仅当 3 是奇数； D、 2+2 4 当且仅当 3 不是奇数； 20、 下列符号串是合式公式的有（ CD ） A、
15、QP ； B、 QPP ； C、 )()( QPQP ； D、 )( QP 。 21、 下列等价式成立的有（ AD ）。 A、 PQQP ； B、 RRPP )( ； D、 QQPP )( ； D、 RQPRQP )()( 。 22、 若 nAAA 21, 和 B 为 wff，且 BAAA n 21 则（ BC ）。 A、称 nAAA 21 为 B 的前件； B、称 B 为 nAAA 21, 的有效结论 B、 当且仅当 FBAAA n 21 ； D 、当且仅当FBAAA n 21 。 23、 A， B 为二合式公式，且 BA ，则（ ABCDE ）。 A、 BA 为重言式； B、 * BA ；
16、 C、 BA ； D、 * BA ； E、 BA 为重言式。 24、 “人总是要死的”谓词公式表示为（ C ）。 （论域为全总个体域） M(x)： x 是人； Mortal(x)： x 是要死的。 A、 )()( xM orta lxM ； B、 )()( xM ortalxM B、 )()( xMo r ta lxMx ； D、 )()( xM o rta lxMx 25、 公式 )()( xQxPxA 的解释 I 为：个体域 D=2， P(x)： x3, Q(x)： x=4 则 A 的真值为（ A）。 A、 1； B、 0； C、可满足式； D、无法判定。 26、 下列等价关系正确的是（
17、B）。 A、 )()()()( xxQxxPxQxPx ； B、 )()()()( xxQxxPxQxPx ； C、 QxxPQxPx )()( ； C、 QxxPQxPx )()( 。 27、 下面四组数能构成无向简单图的度数列的有（ AB ）。 A、（ 2， 2， 2， 2， 2）； B、（ 1， 1， 2， 2， 3）； B、 （ 1， 1， 2， 2， 2）； D、（ 0， 1， 3， 3， 3）。 28、 下图中是哈密顿图的为（ BD）。 29、 如右图 相对于完全图 K5 的补图为（ A ）。 31、下面四组数能构成无向图的度数列的有 ( B )。 A、 2,3,4,5,6,7；
18、B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 32、图 的邻接矩阵为 ( C )。 A、 0001101110100001； B、 1111111111111111； C、 0001101111000010； D、 0001101110100010。 33、下列几个图是简单图的有 ( B )。 A. G1=(V1,E1), 其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de； B. G2=(V2,E2)其中 V2=V1,E2=,； C. G=(V3,E3), 其中 V3=V1,E3=ab,be,ed,cc； D. G=(V4,E4),其中
19、V4=V1,E4=（ a,a） ,（ a,b） ,（ b,c） ,（ e,c） ,（ e,d） 。 34、下列图中是欧拉图的有 ( A )。 35、 图 相对于完全图的补图为（ A ）。 36、 对图 G 则)(),(),( GGGk 分别为（ A ）。 A、 2、 2、 2； B、 1、 1、 2； C、 2、 1、 2； D、 1、 2、 2 。 37、 一棵无向树 T 有 8 个顶点， 4 度、 3 度、 2 度的分枝点各 1 个，其余顶点均为树叶，则 T 中有（ C）片树叶。 A、 3； B、 4； C、 5； D、 6 38、 下列语句不是命题的有（ AE ）。 A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； C、 太阳系以外的星球上有生物； E、你打算考硕士研究生吗？ 39、 RQP )( 的合取范式为（ BD ）。 A、 RQP )( ； B、 )()( RQRP ； C 、)()()()()()( RQPRQPRQPRQPRQPRQP D、 )()()()( RQPRQPRQPRQP 。 40、 设 |A|=n，则 A 上有（ C）二元关系。 A、 2n ； B、 n2 ； C、 22n ； D、 nn ； E、 n2 。 41、 集合 A=1， 2， 3， 4上的偏序关系图为 则它的哈斯图为（ A ）。
