离散数学复习题

离散数学复习题

一． 填空题：

1．P,Q为两个命题，当且仅当____________时，P∧Q的真值为1，当且仅当____________时，P∨Q的真值为0。 2．P,Q为两个命题，当且仅当____________时，P→Q的真值为0。

3．两个重言式的析取为____________，一个重言式与一个矛盾式的析取为____________。

4．给定两个命题公式A,B，若__________，则称A和B是等值的，记作A?B.

5．任意两个不同极小项的合取为_________，全体极小项的析取式必为_________式。

6．命题公式┓(P→Q)的主析取范式为__________，主合取范式的编码表示为________。

7．命题公式┓(P?Q)的主析取范式为__________，主合取范式为________。

8．给定前提┓(P∧┓Q)，┓Q∨R, ┓R，则有效结论为__________。

9．给定前提(P∧Q)→R，┓R∨S，┓S，则有效结论为__________。

10．给定前提┓P∨Q→R，Q∨R，R→S，则有效结论为

__________。

11．通常一元谓词表示__________，多元谓词表示__________。

12．设Q(x):x是偶数，P(x):x是素数，则

(1)命题“存在惟一的偶素数”符号化为__________。 (2)命题“至多有一个偶素数”符号化为__________。 13．命题“任意实数总能比较大小”可符号化为__________。

14．公式?x?y(P(x,y)∧Q(y,z))∧?xP(x,y)中，?x的辖域是__________，?y的辖域是__________，?x的辖域是__________。

15．公式?x(P(x)→Q(x,y))∨?zR(y,z)→S(x)中，自由变元为__________，约束变元为__________。

16．设个体域S={a,b,c}，消去公式?x┓P(x)∨?xP(x)中的量词为__________。

17．设个体域S={a,b,c}，消去公式?xP(x)∨?xQ(x)中的量词为__________。

18．任意一个谓词公式的前束范式在等值意义下是__________，一般地，一个谓词公式的前束范式是__________。

19．谓词公式?xP(x) →?xQ(x)∨?yR(y)的前束范式为

__________。

20．用列举法或描述法表示下列集合： (1)3的算术根组成的集合__________。 (2)函数y?1的定义域集合__________。 2x?x?63直角坐标系中单位圆内外点集__________。 21．填写下列集合之间的关系： (1){1,3,7}_____{1,3}; (2){4,9}_____{9,10,4};

(3){5,7}_____{5,8}; (4)? _____{1,3}; (5){2,3}_____{2,3}.

22．设集合A={1,2,3},B={1,2},则A∪B=________,A∩B=_______, A?B=_______,P(A)?P(B)= _______。 23．由集合运算的吸收律，(A∪B)∩B=________,A∪(A∩B) =_______。

24．由集合运算的基本定律，A∩A=A,满足________律；A∪E=E, 满足________律；A∩E=A,满足________律；A∪~A=E, 满足________律。

25．有序对=的充分必要条件是________。 26．设集合A={1,2},B={a,b,c}，则B?A=________。 27．设集合

A={a,b,c,d}上二元关系

R={,,,}，那么dom(R)=________，

ran(R)=________。

28．集合A={a,b,c}上的恒等关系IA=________，全关系EA=________。

29．设集合A={1,2,3}，R为A上的二元关系，由关系矩阵

?100?MR??110? ????100??得R的集合表达式R=________,关系图为________。 30．设集合A={a,b,c}，R为A上的二元关系，R={,, ,,,},则R的关系矩阵MR=________, 关系图为________。

31．设集合A={a,b,c,d}， A上的二元关系，R={, ,,<3,3>},S={,,,},R?S= ________, R2=________。

32．设集合A={1,2,3,4}， A上的二元关系R={<1,1>, <1,3>,<2,1>,<3,3>,<3,4>,<4,3>},则逆关系R-1的关系矩阵MR-1=________, 关系图为________。

33．设集合A={1,2,3上的二元关系R的关系图如图所示，则R具有的性质是________,t(R)=________。

则

34．设集合B={a,b,c}上的二元关系R的关系矩阵

?110?MR??001? ????000??则R具有的性质是________,MS(R)=________。

35．设集合A={1,2,3,4}上的等价关系R={<1,2>, <2,1>,<3,4>,<4,3>}∪IA，那么A中各元素的等价类为________。

36．设集合A={a,b}，B={1,2}，则从A到B的所有函数是________，其中双射的是________。

37．设集合A={1,2,3}上的函数分别为f={<1,2>,<2,1>, <3,3>},g={<1,3>,<2,2>,<3,2>}，则f?g=____________, f?f=____ ________。

38．图G有15条边，每个结点的度数均为2，则G有________个结点。

39．图G有21条边，3个四度结点其余均为三度结点，则G有________个结点。

40．图G有24条边，每个结点的度数均相同，则G有