离散数学第二章练习题

第二章作业

1. 设{1,2,3,4}A，A上的关系{(2,1)(3,2)(4,3)}，求234,,.

ρ²={(3,1),(4,2)} ρ³={(4,1)} ρ4=∅

2. 实数集上的小于关系“<”是不是偏序关系？请说明理由.

是偏序；实数集上存在一个关系ρ，对所有的实数元素都属于实数，且反对称和可传递的

3. 设{1,2,3,4,5,6}A，关系{(,)|}ijij是的倍数，写出的值域。

ρ={(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(2,2),(4,2),(6,2),(3,3),(4,4),(5,5),(6,6)}

ρ 的值域Rρ=(1,2,3,4,5,6)

离散数学练习题

一、填空题

1. 命题Q→P的真值为0，当且仅当 。

2. 构造公式SRSR→∨∧)(的真值表 。

3. 仅用∧和┐写出下列表达式的等价形式

a) RQP¬→∨¬⇔

b) PQ∨⇔

4. 仅用∨和┐写出下列表达式的等价形式

a) )()(DCBA∨→∨⇔ 。

b) )(EDA¬→→¬⇔

5. 公式A有三个命题变元P、Q、R组成，其主析取范式为A6531mmmm∨∨∨⇔，则其主合取

范式为：

6. 公式A有三个命题变元P、Q、R组成，其主合取范式为A⇔65310MMMMM∧∧∧∧，则

其主析取范式为： 。

7. 设解释I如下： D={n，m} P(n，n) P(n，m) P(m，n) P(m，m)

1 1 0 0

8. 确定下列各式的真值：

),(mxxP∃ ___ ___; ),(ynyP∀ __ ___; ),(yxyPx∀∀) __ ___。

),(nxxP∃ ___ ___; ),(ymyP∀ __ ___; ),(yxyPx∃∀) __ ___。

9. 谓词合式公式)()(xxQxxP∃→∀的前束范式为 。

10. 某集合有101个元素，则有 个子集的元素为奇数。

11. 某班有32个学生，其中14个人选择艺术，7个人选择生物，6个人选择音乐，三门课都选的有

2人，问这三门课都没选的至少有 人？

12. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,3,5,6}, B={2,4,6,8,9},

则：A∩B= , B⊕A= ,

BA⊗= ; (A∪B)-B = ,

(A∪B)-(B∩C)=

13. =Φ=)(},,a{AAρ 。

14. BAbaBA×==2},,{},1{=

=×BA)(ρ

15. 请说出以下三个二元关系是否满足自反性、反自反性、对称性、反对称性和传递性。

C

BA

CBA

A B C

a b c d

(a)：

(b)：

(c)：

计算机离散数学练习题

一、填空题

1、量词辖域中出现的（）和指导变元交换为另一变元符

号，公式其余的部分不变，这种方法称为换名规则。

2、集合A={,{}}的幂集P(A)=（）

3、Q：我将去上海，R：我有时间，公式(QR)(RQ)的

自然语言为（）

4、AB=（）

5、设F(某):某是人，G(某):某用右手写字，命题“有的人并不用右手写字”用谓词公式

表示为（）

6、设A是n个(n≥1)元集的集合，则A的幂集有（）个元素，有

（）种不同的二元关系

7、命题公式PQPQ可化简为（）

二、选择题

1、下列各命题中真值为真的命题有（）。

A．2+2=4当且仅当3是奇数；B.2+2=4当且仅当3不是奇数；

C.2+2≠4当且仅当3是奇数；D.2+2=4仅当3不是奇数；

2、下列等价式成立的有（）。 A.PQQP；B.P(PR)R；

C.P(PQ)Q；D.P(QR)(PQ)R。

3、命题“尽管有人聪明，但未必一切人都聪明”的符号化

（P(某)：某是聪明的，M(某)：某是人）（）

A.某(M(某)P(某))(某(M(某)P(某)))

B.某(M(某)P(某))(某(M(某)P(某)))

C.某(M(某)P(某))(某(M(某)P(某)))

D.某(M(某)P(某))(某(M(某)P(某)))

4、下列语句中哪一个是真命题？（）

A、我正在说谎B、严禁吸烟C、如果1+2=3，则雪是黑的D、如果1+2=5，则雪是黑的

5、若公式(PQ)(PR)的主析取范式为m001m011m110m111则它的主合取范

式为（）

A.m001m011m110m111；B.M000M010M100M101；

C.M001M011M110M111；D.m000m010m100m101

6、谓词公式某yP(某,y)否定式为（）

A、某yP(某,y)B、某yP(某,y)C、某yP(某,y)D、某yP(某,y)

7、在集合运算中，（）对可分配 A、B、C、—D、

一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．上！）

1、设集合X={0，1，2}，R是X上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R的关系矩阵MR= 。

2、66,Z为模6整数加群， 则由2生成的子群<2>= ，右陪集<2>⊕65= 。

3、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数。

4、无向图G如下图所示，G的点连通度κ为 ，边连通度λ为 。

5、在上面无向图中，已给出了一棵生成树T（粗边所示），则树枝d对应的基本割集是 ，弦b对应的基本回路是 。

6、令F(x)： x是整数，G(x)：x是奇数，则“不存在不是奇数的整数”符号化为 。

7、含有三个命题变项P，Q，R的命题公式PQ的主析取范式是

（用mi形式表示最小项）。

二、单选题（20分，每题1分，请将本题答案写在下方表格．．．．中！）

1、下面给出的符号串集合中，（ ）不是前缀码。

A、1111,110,10,0 B、01,001,000,10

C、1101,1001,101,110, D、abcabaacaacb,,,,,

2、下列( )组赋值不是命题公式C()AB的成真赋值。