18秋北大08281004-离散数学（资料）

同学情

          ***********2018秋课件作业***********

                            第一部分 集合论
第一章  集合的基本概念和运算  
1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是       （选择题）       [   ]
A．1 ∈A；       B．2 ∈ A；   C．3 ∈A；   D．{3，2,1}   A。

1-2 A,B,C　为任意集合，则他们的共同子集是              （选择题）     [   ]
A．C；             B．A；               C．B；          D．  Ø    。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确         （是非题）
（1） N   Q，Q ∈S，则 N   S，　　　　　　　　　　　　　　　　　 ［    ］
（2）-1 ∈Z，Z ∈S， 则 -1 ∈S 。　　　　　　　　　　　　　　　　　［　  ］

1-4 设集合 B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，
E = {x│x ∈R 并且 x2 - 7x + 12 = 0}，F = { 4，Ø ，3，3}，
试问：集合 B 与那个集合之间可用等号表示              （选择题）     [   ]
A. C;             B. D;               C. E;              D.  F.

1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题）   [    ]
A. N;             B. Z;           C. Q;                 D. Z+

1-6 为何说集合的确定具有任意性 ?                       (谋学网（www.mouxue.com）)

第二章   二元关系   
2-1 设 A = {1，2，3}，A 上的关系 R = {〈1，2〉，〈2，1〉}∪IA，
    试求：                                            （综合题）
    (1)domR =?;           (2)ranR =?;           (3)R 的性质。
      （4）商集 A/R =？     （5）A 的划分∏=？    （6）合成运算（R 。R）=？                  
2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即
    R = {〈x，y〉│x，y  ∈Z+ 且 x + 3y  = 12}，
试给出 dom（R 。R）。                                 （选择题） [   ]
A. 3；     B. {3}；      C. 〈3，3〉；     D.{〈3，3〉}。

2-3 判断下列映射 f 是否是 A 到 B 的函数； 以及函数的性质。最后指出 f：A→B
中的双射函数。                                   （选择题）   [   ]
（1）A = {1，2，3}，B = {4，5}，        f = {〈1，4〉〈2，4〉〈3，5〉}。
（2）A = {1，2，3} = B，                f = {〈1，1〉〈2，2〉〈3，3〉}。
（3）A = B = R，                        f  =  x 。
（4）A = B = N，                        f  =  x2 。
（5）A = B = N，                        f = x + 1 。
A.（1）和（2）；      B.（2）和（3）；      C.（3）和（4）； D.（4）和（5）

2-4 设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝     [   ]　　　　　　
A．x+1；       B．x-1；          C．x；           D．x2。
   
2-5 关系型数据库与《关系与函数》一章内容有何联系 ？   （谋学网（www.mouxue.com））

第三章 结构代数(群论初步)                (3-1)，(3-2)为选择题
3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？
（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *  是普通乘法。          [   ]     
A．不构成代数系统；  B．只是代数系统。；   C． 半群；           D．群。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；
二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。  [   ]
A．不构成代数系统；  B．只是代数系统。；   C． 半群；           D．群。

（3）S3 = {0，1}，二元运算 * 是普通乘法。                             [   ]
A．不能构成代数系统；     B．半群；       C．独异点；           D．群。

3-2 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z  都有
       x 。y  =  x - y
试问？在 Z 上二元运算 。能否构成代数系统，何种代数系统？为什麽 ？（综合题）

                      第二部分   图论方法
第四章 图 以下三题分别为：                    选择题  是非题  谋学网（www.mouxue.com）
4-1 10 个顶点的简单图G中有4个奇度顶点，问 G 的补图中有 r 个偶数度顶点。[   ]
A．r =10 ；        B．r = 6；         C．r = 4；            D．r = 9。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点。[   ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为　                            。

第五章  树                           
5-1 概述无向图与无向树的关系。                                  （谋学网（www.mouxue.com））

5-2 握手定理的应用（指无向树）                                  （计算题）
（1）在一棵树中有 7 片树叶，3个3 度顶点，其余都是4 度顶点，共几个顶点  [   ]
（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶     [   ]

5-3 用 Huffman 算法求带权为 1，2，3，5，7，8 的树叶的最优 2 元树 T。（谋学网（www.mouxue.com））
试问：T 的权 W（T）= (        )；
树高 (                  ) 层。

5-4  以下给出的符号串集合中，那些是前缀码                         （是非题）
         B1 = {0，10，110，1111}；                                    [   ]
         B2 = {1，01，001，000}；                                     [   ]
         B3 = {a，b，c，aa，ac，aba，abb，abc}                        [   ]
         B4 = {1，11，101，001，0011}                                 [   ]

5-5  11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有6条树枝   [   ]

5-6 二元正则树有奇数个顶点。                                          [   ]

5-7 通信中 a，b，c，d，e 出现的频率均为 20%;  试完成下列要求。   （综合题）   
1、        最优二元树 T；







        2、二元树的权 W（T）=;
        

        3、每个字母的码字；a(      )，b(      )，c(       )，d(      )，e(      )
        
        4、若用等长码共多少位?
                          
                        第三部分   逻辑推理理论
第六章 命题逻辑
6-1 判断下列语句是否命题，简单命题或复合命题。                （谋学网（www.mouxue.com））

（1）2月 17 号新学期开始。                     （        ）命题

（2）离散数学很重要。                          （        ）命题

（3）离散数学难学吗 ？                         （        ）命题

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性（      ）命题

（5）x + 5 > 2 。                              （        ）命题

（6）今天没有下雨，也没有太阳，是阴天。        （       ）命题

6-2 将下列命题符号化.                                      （谋学网（www.mouxue.com））

（1）2 是偶素数。                                            
   
（2）小李不是不聪明，而是不好学。                              

（3）明天考试英语或考数学。（兼容或）                           

6-3  用等值演算法求下列命题公式的主析取范式，并由此指出该公式的类型
（1）﹃（p→q）∧ q                                      （计算题）
   
（2）（（p→q）∧ p）→q                                 （计算题）
     
（3）（p→q）∧ q                                        （计算题）

6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为 　[    ]
A． p→q；       B．  q→p；     C．  p∧q；    D．  ﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为 ［    ］
A． p→q；       B．  q→p；     C．  p∧q；    D．  ﹁q→p

6-6  将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题）
如果今天不下雨，则明天上体育课。今天没有下雨。所以，明天上体育课。

题解与分析：首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不
同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。
方法 1：等值演算法(略)
方法 2: 主范式法(略);
方法 3: 真值表法(略);
方法 4：构造证明法,如下:
        （1）将原子命题符号化：
        （2）按题意构成前提：
        （3）按题意构成结论：
        （4）证明：




               
第七章  谓词逻辑
7-1 在谓词逻辑中用 0 元谓词将下列命题符号化            （谋学网（www.mouxue.com））

（1）1 不是素数。                                                    。  

（2）如果 2 ＞ 3，则 2 ＞ 5。                                        。

7-2 谋学网（www.mouxue.com）：设域为整数集合 Z，命题 x y彐z（x-y = z）的真值为　         

7-3  在谓词逻辑中将下列命题符号化                      （谋学网（www.mouxue.com））

人固有一死。                                                     。

7-4 一阶逻辑与命题逻辑有何联系？ 举例说明。            （谋学网（www.mouxue.com））

《附录》习题符号集
Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 ,
－ 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非， 量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”，∏划分。
   
                                                2018 年 8 月 25 号.