《离散数学》题库与答案、选择或填空(数理逻辑部分)

“离散数学”题库及答案

, 选择或填空

（数理部分）

1、以下哪个公式总是真蕴涵？()

(1) Q2>Q>P (2) Q2Q CDP=>P—Q (4) P (PQ)=> P

答：第三章有公式（1)是加法，（4)可以从第二章的蕴涵等价公式得到（注意和吸收律的区别）

2、以下哪个公式是永远正确的？()

(1) ( n PQ)—(Q—R) (2)P—(Q—Q)⑶(PQ)—P (4)P—(PQ) 答案：(< @2), (3), (4) 可以通过蕴涵等价证明

3、有下列公式，哪些是永恒真理的蕴涵公式？( )

(1) P=>PQ ⑵ PQ=>P ⑶ PQ=>PQ

⑷P(P—Q)=>Q(5)(P—Q)=>P(6)P(PQ)=>P

答：(2)是第3章的归约律，(3)类似于加法，(4)是假设推理，(3),(5),(6)可以通过蕴涵等价证明为真蕴涵

4、在公式x((A(x) B(y, x)) z C(y, z)) D(x)中，自由变量为()，约束变量为()。答案：x、y、x、z（检查公式 x A 和 x A 中的定义，称 x 为指导变量，A 为量词

的域。在 x A 和 x A 的域中，所有出现的 x 都称为约束出现，即 x 称为约束变量，而 A 中其他不出现约束的变量称为自由变量。所以在A(x), B(y, x) and z C(y, z)中，y是自由变量，x和z是约束变量，x是D(x)中的自由变量)

5、判断下列语句是否为命题。如果是，请给出命题的真值。()

（1) 北京是中华人民共和国的首都。

（2) 陕西师范大学是一家工厂。

⑶ 你喜欢唱歌吗？(4) 如果 7+8> 18，则三角形有 4 条边。

（5)去吧！（6)给我一杯水！

答案：(1)是，T(2)是，F(3)否(4)是，T(5)否(6)

否（命题必须是陈述句，而不是疑问句或祈使句。）

6、命题“有些人是大学生”的否定是()，命题“所有人都是会死的”的否定是()。

答：所有人都不是大学生，有的人不会死（命题的否定就是把命题前提中的量词换成“存在，替换为”，然后否定命题的结论，“和改变或改变和”）

7、假设P：我生病了，Q：我去上学了，那么下面的命题可以符号化为( )。

（1)除非我生病了，我才去学校（2)如果我生病了，我就不去学校）

（3)当且仅当我生病时我才去学校（4)如果我没有生病自然数是整数的逆命题，那么我就去学校

答案：(1) QP（请注意，“仅当…”和“除非…然后…”都是

形式) (2) PQ (3) PQ (4) PQ

& 设个体域为整数集合，则下式的含义为()。

(1) xy(x+y=O) (2) yx(x+y=O)

答案：(1)对于任何整数 x 都有一个满足 x+y=0 的整数 y

(2) 存在一个整数 y 满足 x+y=0 对任何整数 x

9、假设整个域D是一组正整数，判断下列命题的真值：

(1) xy(xy=y) ( ) (2) xy(x+y=y) ( )

(3) xy(x+y=x) ( ) (4) xy(y=2x) ( )

答案：(1) F (矛盾方法：如果存在自然数是整数的逆命题，则 (x- 1 ) *y=0 对所有 x 都为真，这显然与前提条件相矛盾) (2) F (同理) ( 3) F (类似) (4) T (对于任何整数 x 都有一个满足条件 y=2x 的整数 y 显然为真)

10、假设谓词P(x) : x 是奇数，Q(x) : x 是偶数，其中谓词公式x(P(x) Q(x))

在单个域中是真的吗？（）

(1) 自然数 (2) 实数 (3) 复数 (4) (1)–(3)

答：（1)（在某个体域中，要么奇数要么偶数，在整数域满足条件，自然数子整数的子集，当然满足条件）

11、 命题“2 是偶数或-3 是负数”的否定是( )。

答案：2 不是偶数，-3 不是负数

12、永恒真否定是()

(1)永久真公式(2)永久假公式(3)可以满足公式⑷(1)–(3)所有可能

答案：（2)（记住这一点）

13、公式(PQ)(PQ)可以简化为()，公式Q(P(PQ))可以简化

为了（ ）。

答案：P、QP（考查分配率和对等类型知识的掌握情况）

14、谓词公式x(P(x) yR(y)) Q(x)中量词x的作用域为( )。

答案：P(x) yR(y)（一对括号是一个作用域）

15、令 R(x):x 为实数，Q(x):x 为有理数。那么“不是每个实数都是有理数”这个命题的符号表示是（ ）。

答案：x(R(x) Q(x))

（集合论部分）

16、假设A={a,{a}}，下列哪个命题错误的是()。

(1) {a} P(A)②{a} P(A)⑶{{a}} P(A)⑷{{a}} P(A)

答案：(2) ({a} 是 P(A) 的一个元素)

17、在0()之间写上正确的符号。

(1) = (2) (3) (4)

答：（4)（空集没有元素，是任意集合的子集）

18、如果集合S|S|的基数=5，那么S的动作集的基数|P(S)|=()。

答案：32（2的5次方考察了行为集的定义，即行为集是由集合S的所有子集组成的集合）

19、 令P={x|(x+1) 24 and x R}, Q={x|5 x2+16 and x R}, 那么下列哪个命题为真

真的 （ ）

(1) QP (2) QP (3) PQ ⑷ P=Q

答案：（3)（Q是集合R，P只是R的一部分，所以P是Q的真子集）

20、以下哪个集合相等（

）。

(1) Aren{a,b} (2)A2two{b,a} (3)A3two{a,b,a} (4)A4two{ a,b, C}

(5) A5={x|(xa)(xb)(xc)=0} (6) A6={x|x 2-(a+b)x+ab=0}

答案：A1=A2=A3=A，A4=A5（集合是无序的、确定的、互斥的）

21、如果AB=①，下列哪个结论不能成立？()

(1) A=①(2) B= ①(3) AB ⑷ BA

答案：（4)（差异的定义）

22、判断下列哪个命题是正确的？()

(1) AB=BA => A=B (2) 空集是任何集合的真子集

（3）空集只是非空集的子集（4)如果A的一个元素属于B，那么A=B

答：(1)(查空集和差集的相关知识)

23、判断下列哪个命题是正确的？()

(1) {①} € {①,{{①}}} (2) { ①} {①,{{①}}} (3) X {{①}}

(4)①{①} (5) {a,b} € {a,b,{a},{b}}

答案：(2), (4)

24、判断下列哪个命题是正确的？()

(1)所有空集都不等②{①}①(4)如果A是非空集，则AA成立。答案：(2)25、令 AAB =AHC, AAB=AAC,BeiSB( )C。

答案：=（等于）

26、下列哪个命题是正确的？( )

(1)如果 AUB = AUC，则 B = C (2) {a,b}={b,a}

(3) P(AAB) P(A) AP(B) (P(S) 表示 S 的行为集) (4) 如果 A 是非空集，则 AAUA 成立。

答案：(2)

27、A,E,C 是三个集合，下列哪个推理是正确的： (1) AB , BC=> AC (2) AB , BC=> A € B ( 3) A € B , B € C=> A €

C

答：（1)（（3)的反例C是{{0, 1}, 0} B是{0, 1}，A是1，显然结论是错误的）

（二元关系部分）

28、

设 person = { 123, 4, 5, 6 }, B 两个 {1, 2, 3}，从 A 到 UB 的关系

R=＜x,y＞|x=y

查找 (1)R (2) R -1

答案：(1) R={,} (2) R 1={,}(查看二元关系的定义，R 1 是R的逆关系，即R 1

=

{ } |

欧元）

29、 举一个关于集合 A 的等价关系的例子，它既是等价关系又是偏序关系。(

)

答案：A 上的恒等关系

30、集合A上的等价关系的三个性质是什么？(

) 答案：自反性、对称性和及物性

31、集合A上的偏序关系的三个性质是什么？(

)

答案：自反性、反对称性和及物性（问题 29、30、31 都是测试定义）

32、 假设 S={ 1 , 2 ,3 , 4 } , A 上的关系只有 = <1,2>,<2,1>,<2,3>,<3,4 >}找到 (1)RR (2)R -1.

答案：RR={< 1,1 >, < 1,3 >, < 2,2 >, < 2,4 > }(检查 FG ={| t( € F

欧元 G)})

■1

R = {}

33、

认为

A= {1, 2, 3, 4, 5, 6}，R是A上的整除关系，求R={( )} R={,,,,,,,,,,,,,

4>,,}

34、设A= {1,2,3,4,5,6}，B={1,2,3}，A到UB的关系R= {<x,y>|x= 2y},

查找 (1)R (2) R -1.

答案：(1) R={,,} (2) R 1 ={,,(36>}

35、设A={1,2,3,4,5,6}，B={1,2,3}，A到UB的关系R={

|x=y2},

求 R 和 R1 之间的关系矩阵。

100000

R 1 = 0 0 0 1 0 0 010 的关系矩阵

000000 000

000

36、集合 A={1,2,…,10} 上的关系 R={|x+y=10,x,y 为 ( )

(1） 自反 (2） 对称 (3） 传递 (4） 传递)

答：（2）（检查自反对称传递性的定义）

（代数系统部分）

37、 令 A={2,4,6} ，对 A 的二元运算*定义为： a*b=max{a,b} ，单位元为 () ，零元为( )。

答案：2、6（单位元和零元的定义，单位元：e.x=x 零元：B.x=0）

38、 令 A={3,6,9} ，对 A 的二元运算*定义为： a*b=min{a,b} ，单位元为 () ，零元为();

答案：9、3

（半组和组部分）

39、 令 <G,*> 为一个群，则 (1） if a,b,x € G, ax=b , then x=(); (2） if a ,b,x € G, ax=ab , 湾 U x=()。

答案：(1） a 1 b (2） b (考察群的性质，即群满足消除律)

40、 设a为12阶群的生成元，则a 2 为( )阶元素，a 3 为( )阶元素。

答案：6,4

41、

代数系统是

群，则 G 的等元素为 (

）。

答案：单元元素（由 A

2=a，可以归纳证明 aM=a*a^(n-1）=a*a=a ，所以等价元素一定是等价元素，否则如果 aAn=a 对所有都成立N, 那么对于n = 2也是成立的，所以行为等价元素必须是行为等价元素，并且在群中，除了酉元素，单位元素e）之外，不能有其他幂等元素

42、设a为10阶群的生成器，则a 4为order()的元素，a 3为order()的元素

00

00