春季学期离散数学语音答疑提纲下文档格式.docx

春季学期离散数学语音答疑提纲下文档格式.docx

《春季学期离散数学语音答疑提纲下文档格式.docx》由会员分享，可在线阅读，更多相关《春季学期离散数学语音答疑提纲下文档格式.docx（10页珍藏版）》请在冰点文库上搜索。

例题1:

设集合A={1，{2}，a，4，3}，则有2∈A[非];

单项选择题：

例题2:

A,B，C为任意集合，则他们的共同子集是　　[D]

A．A；

B．B；

C．C；

D．。

例题3：

设集合A={1，{2}，a，4，3}，下面命题为真是[B]

A．2∈A；

B．1∈A；

C．5∈A；

D．{2}

A。

例题4:

设集合A={1，{2}，a，4，3}，则有2（）A。

此题为填空题,把2与集合A的关系填在（）内.

*****请比较例题1，3，4，那个最容易；

那个最难！

*****

2.集合的基本运算重点掌握：

五大基本运算定义的表达式。

例如,并运算的”或”,交运算的”且”字的意义.

例题：

N,Z+分别是自然数集合,正整数集合,则[C]

A．N=Z++{0}B．N=Z++0C．N=Z+∪{0}D．N=Z+.∪0.

（

第四章关系及函数

1.关系的基本概念

重点掌握：

关系的定义，关系来自有序对，有序对来自集合的笛卡儿积；

A到B的二元关系以及A上的二元关系的条件；

2.关系的五大性质及其判断—难点在于传递性的判断。

五大性质的判别方式；

当然，难点在于传递性的判断。

量变引起质变的示例：

等价关系—同时具备自反、对称、传递性质；

等价类，商集与划分的对应性。

例题1、设A={1，2，3}，A上的关系R={〈1，3〉，〈3，1〉}∪IA，试求：

1）

给出R的关系图。

1。

。

2说明：

每个顶点都有圈；

1到3

。

及3到1各有一条有向

3线。

2）由关系图说明R的性质。

自反，对称，传递。

3）给出合成（R。

R）={〈1，3〉，〈3，1〉}∪IA。

4）给出商集A/R的表达式及所有元素。

A/R={{1，3}，{2}}。

5）给出商集A/R所对应的划分∏。

∏={{1，3}，{2}}。

试问：

你能悟出等价关系或商集与划分的关系吗！

例题2、设A={a，b}，B={1，2}，A到B的双射函数的数目是4个[非]。

例题3、设函数ｆ：

Ｎ→Ｎ，ｆ（ｎ）＝２ｎ＋１，Ｎ为自然数集合，则函数性质为［Ａ］

A．只为单射B．只为满射C．双射D．Ａ,Ｂ,Ｃ都不是．.

例题4、集合A={1，2，3}，关系R={〈2，3〉，〈3，2〉}具有[D]***

A．自反性；

B．反对称性；

C．传递性；

D．反自反性。

3.关系及函数的运算

求域；

求逆；

合成运算是难点-请看专题讨论。

设ｆ（x）＝ｘ+１，ｇ（x）＝ｘ-１都是从实数集合Ｒ到Ｒ的函数，则ｆ。

ｇ＝[D]

A．x+1；

B．x-1；

C．x2；

D．x。

第九章群论初步

1.代数系统的基本概念

二元运算必须是函数；

定义了二元运算的集合既是代数系统，代数系

统的封闭性；

代数系统中二元运算满足结合律算律的重要意义；

2.代数系统中的特殊元素与半群、独异点及群的联系

代数系统中结合律算律与半群的关系—半群的判别；

半群中的幺元—独异点，每个元素都有其逆元的独异点为群。

自然数N与其上的普通加法+构成的代数系统〈N，+〉是[C]

A．只是代数系统；

B．半群；

C．含幺半群；

　D．群.

例题2、设Z为整数集合，在Z上定义二元运算*，对于所有x，y∈Z都有

x*y=x+y；

验证〈Z，*〉

能否构成代数系统何种代数系统为什麽

要求有根据地回答：

1、满足封闭性，构成代数系统。

2、经验证满足结合律，所以为半群。

3、幺元为0，所以为幺半群。

（经解联立方程组）.

4、设y是x的逆，所以有y=–x。

（解联立方程组得到）

5、结论：

构成群。

例题3、设Z为整数集合，在Z上定义二元运算*，对于所有x，y∈Z都有

x*y=x+y-2；

3、幺元为2，所以为幺半群。

4、设y是x的逆，所以有y=4–x。

5、结论：

例题4、设Z为整数集合，在Z上定义二元运算*，对于所有x，y∈Z都有

x*y=x+y+2；

3、幺元为-2，所以为幺半群。

4、设y是x的逆，所以有y=-4–x。

－4的逆为何你能说明白吗！

另，x*y=x+y改成x*y=x–y你会解码！

第五章图论

1.图的基本概念

阶的概念；

度的概念：

完全图，补图概念；

母图与子图—引出生成图与导出图概念的差别；

握手定理—度数之和=2倍边；

握手定理应用—图这一章的所有计算题的理论依据。

2.图的分割

割集概念—注意割点或桥的特点。

请留心割集与基本割集的联系。

例题1、９阶无向简单连通图Ｇ中，顶点间的最大距离为　[A]

A．8；

B．9；

C．10；

D．11。

第七章树

1.树的基本概念

定义—连通而无回路，m=n-1；

生成树—引出树枝、弦、基本回路、基本割集概念。

2.根树

根树的来源及特点定义；

最优二元树及最佳前缀码。

特别要求:

必须掌握图----树关系.

每条边都是桥的无向连通图必是树。

[是]

例题2、n阶无向连通图G有m条边，T为G的一棵生成树，则G对应T的基本回路数目为[D]

A．n；

B．n-1；

C．m-n；

D．m-n+1。

例题3、非平凡无向树T是连通图[是]。

例题4、根树中的树叶都在树的最高层。

[非]

例题5、填空题：

（1）n阶非平凡无向树至少两片树叶。

（2）、图G（m，n）的阶数n为10，则其生成树的边数为9。

例题6、在网上传输GOODBYE的最佳前缀码。

每个字母出现频率分别为：

G、D、B、E、Y：

14%，O：

28%；

（可以对符号出现频率归一,如下图右;

也可以不归一,某符号出现次数即为权,下图左）.

100（近似）7.

42。

563..4

28。

282..1.2.2

14。

....

141414141111

所以，得到编码如下：

G（000），D（001），B（100），E（101），Y（01），O（11）。

你能算出传递　ＧＯＯＤＢＹＥ共用多少位二进制码字

为了说明白这个问题,让我分两方面下手:

先说由没有归一的树叶的权得到的结果:

G,D,B,E分别用3位二进制码，共12位。

加上Y=用2位。

再加上两个O的4位。

总共18位。

用树的权W（T）=累加wixhi（即每片树叶的权x树叶的高度，加在一起）=1x3+1x3+1x3+1x3+1x2+2x2=18.还有一个办法，即把所有分支点的权加起来，也是18.请看：

要回答传递一组符号所需二进制码总数设个问题，可以的把每个符号的码字数加起来；

或从树的权的办法得到。

二者相同。

再说归一后得到的结果：

把每个符号所用码字数，加起来，共18位。

但是，若用树的权W（T）=4个14x3加起来，再加上1个14x2，再加上28x2,等于252。

这个权与没有归一化得到的结果是如何不同呀！

归一化的概念是：

传输100个按某种频率（即14，14,14,14,14,28）出现一组符号所用二进制码数。

我讲这些，是为了让大家得到一个计算传递一组符号总共用二进制码数的简单方法。

第一章命题逻辑

1.基本概念

命题—命题定义及简单命题；

5个基本联结词+简单命题=复合命题；

简单命题的符号化；

2.命题公式及其规范形式

公式的赋值—成真、成假赋值，真值表—公式的类型；

范式及主范式—析取范式与合取范式；

主范式中极小项与极大项关系。

例题以填空形式给出：

例题1、命题公式﹃ｐ→ｑ的类型是（可满足）　式。

例题2、命题公式﹃q的主合取范式为（∏

（1））。

例题以是非形式给出：

例题3、命题公式﹃ｐ→ｑ的类型是可满足式[是]。

例题4、命题公式﹃q的主合取范式为∏

（1）[是]。

例题以选择形式给出：

例题5、命题公式﹃ｐ→ｑ的类型是[C]

A．永真式；

B．永假式；

C．可满足式；

D．不是公式。

例题6、命题公式﹃q的主合取范式为[B]

A．∏（0）；

B．∏

（1）；

C．0；

D．1。

3.推理理论

定义推理正确—蕴涵式的永真式；

构造证明法—八大推理定律中的第3条；

推理技巧—附加前提法。

例题（证明题）：

请在合适的逻辑中构造下面论题的证明。

例1）给出前提和结论，完成构造法的证明。

（1）前提：

p∧q→r，﹁s∨q，p。

（2）结论：

s→r。

（3）证明：

采用附加前提法。

引入前提﹃s∨q及附加前提s后，利用公式”假言推理”得到q，

再引入前提p，再利用”假言推理”公式，得到结果：

r。

第二章谓词逻辑

命题逻辑的致命缺点；

谓词逻辑的改进—句子成分的展示：

主语（个体词、域）；

定语（量词）；

表达主语的性质—谓词；

谓词逻辑中符号化问题：

特性谓词的引入；

个体域—谓词—量词—联结词的搭配。

2.合式公式及其真值

项中函数形式；

合式公式的原子单元—谓词公式；

谓词公式的解释及其真值：

解释—永真式，矛盾式，可满足式；

代换实例。

3.谓词逻辑中推理理论及其局限性

谓词逻辑中的构造证明法与命题逻辑中的构造证明法的联系与区别；

例题、填空题

将一阶命题“每个人都有一死”符号化，使用特性谓词F（x）：

x是人。

G（x）：

x会死；

最后符号化为：

x（F（x）→G（x））。

2019年5月。