北京大学2017秋课件作业离散数学及答案

2017秋课件作业第一部分集合论第一章集合的基本概念和运算11设集合A2，3,4，5，1，下面命题为真是（选择题）AA1A；B2A；C3A；D3，2,1A。12A,B,C为任意集合，则他们的共同子集是（选择题）DAC；BA；CB；D。13设SN，Z，Q，R，判断下列命题是否正确（是非题）（1）NQ，QS，则NS，错（2）1Z，ZS，则1S。错14设集合B4，3，C4，3，D3，4，EXXR并且X27X120，F4，3，3，试问集合B与那个集合之间可用等号表示（选择题）AACBDCEDF15用列元法表示下列集合AXXN且3X3（选择题）DANBZCQDZ16为何说集合的确定具有任意性简答题答按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。第二章二元关系21设A1，2，3，A上的关系R1，2，2，1IA，试求（综合题）1DOMR2RANR3R的性质。（4）商集A/R（5）A的划分（6）合成运算（R。R）答R,，；1DOMRR中所有有序对的X3,2,12RANRR中所有有序对的Y2,1,3；3R的性质自反,反对称,传递性质这时，R不是等价关系。（4）商集A/R1，2，3，2，3，3。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。（5）A的划分1，2，3，2，3，3；也由于R不是等价关系，造成划分的荒谬结果出现交集。试问让“3”即参加第一组，又参加第二组，她该如何分配呢所以，关系R必须是等价关系。至于作业中，此两题应说因为R不是等价关系，此题无解。22设R是正整数集合上的关系，由方程X3Y12决定，即RX，YX，YZ且X3Y12，试给出DOM（R。R）。（选择题）BA3；B3；C3，3；D3，3。23判断下列映射F是否是A到B的函数；以及函数的性质。最后指出FAB中的双射函数。（选择题）B（1）A1，2，3，B4，5，F1，42，43，5。（2）A1，2，3B，F1，12，23，3。（3）ABR，FX。（4）ABN，FX2。（5）ABN，FX1。A（1）和（2）；B（2）和（3）；C（3）和（4）；D（4）和（5）24设XX1，XX1都是从实数集合到的函数，则。CAX1；BX1；CX；DX2。25关系型数据库与关系与函数一章内容有何联系（简答题）答关系与函数一章的内容是关系型数据库的理论基础第三章结构代数群论初步31，32为选择题31给出集合及二元运算，判断是否代数系统，何种代数系统（1）S11，1/4,1/3,1/2,2，3，4，二元运算是普通乘法。AA不构成代数系统；B只是代数系统。；C半群；D群。（2）S2A1，A2，AN，AIR，I1，2，N；二元运算。定义如下对于所有AI，AJS2，都有AI。AJAI。CA不构成代数系统；B只是代数系统。；C半群；D群。（3）S30，1，二元运算是普通乘法。CA不能构成代数系统；B半群；C独异点；D群。32设Z为整数集合，在Z上定义二元运算。，对于所有X，YZ都有X。YXY试问在Z上二元运算。能否构成代数系统，何种代数系统为什麽（综合题）答判定和讨论特殊元素及其对代数结构的作用，整数上的减法运算满足封闭性，才能构成代数系统，当然要满足群的定义条件，整数上的减法运算只构成一般代数系统，而不构成半群，更不构成群。第二部分图论方法第四章图以下三题分别为选择题是非题填空题4110个顶点的简单图G中有4个奇度顶点，问G的补图中有R个偶数度顶点。CAR10；BR6；CR4；DR9。42是非判断无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点。是43填空补缺1条边的图G中，所有顶点的度数之和为2。第五章树51概述无向图与无向树的关系。（简答题）答（1）生成树的定义生成子图概念；（2）生成子图与母图的关系顶点数相同；（3）何种图才有生成树连通图；（4）连通图中的那种边永远不会进入任何一颗生成树中环。（5）连通图中的那种边必然会进入其生成树中桥。52握手定理的应用（指无向树）（计算题）（1）在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，共几个顶点11（2）一棵树有两个4度顶点，3个3度顶点，其余都是树叶，问有几片叶953用HUFFMAN算法求带权为1，2，3，5，7，8的树叶的最优2元树T。（填空题）试问T的权W（T）61；树高4层。54以下给出的符号串集合中，那些是前缀码（是非题）B10，10，110，1111；是B21，01，001，000；是B3A，B，C，AA，AC，ABA，ABB，ABC非B41，11，101，001，0011非5511阶无向连通图G中有17条边，其任一棵生成树T中必有6条树枝非56二元正则树有奇数个顶点。是57通信中A，B，C，D，E，F,G,H出现的频率分别为25202015,10,5,3,2试完成下列要求。（综合题）1、最优二元树T；2、二元树的权W（T）；3、每个字母的码字；第三部分逻辑推理理论第六章命题逻辑61判断下列语句是否命题，简单命题或复合命题。（填空题）（1）2月17号新学期开始。（是简单）命题（2）离散数学很重要。（是简单）命题（3）离散数学难学吗（不是）命题（4）C语言具有高级语言的简洁性和汇编语言的灵活性（是复合）命题（5）X52。（不是）命题（6）今天没有下雨，也没有太阳，是阴天。（是复合）命题62将下列命题符号化（填空题）（1）2是偶素数。PQ（2）小李不是不聪明，而是不好学。PQ（3）明天考试英语或考数学。（兼容或）PQ63用等值演算法求下列命题公式的主析取范式，并由此指出该公式的类型（1）（PQ）Q0，永假式（计算题）（2）（PQ）P）Q（0，1，2，3）永真式（计算题）（3）（PQ）Q（1，3）可满足式（计算题）64令P经一堑；Q长一智。命题只有经一堑，才能长一智符号化为BAPQ；BQP；CPQ；DQP65P天气好；Q我去游玩命题”如果天气好，则我去游玩”符号化为AAPQ；BQP；CPQ；DQP66将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题）如果今天不下雨，则明天上体育课。今天没有下雨。所以，明天上体育课。题解与分析首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。方法1等值演算法略方法2主范式法略方法3真值表法略方法4构造证明法,如下（1）将原子命题符号化（2）按题意构成前提（3）按题意构成结论（4）证明答如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。题解与分析首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。方法1等值演算法（PQ）P）Q1；方法2主范式法略方法3真值表法略方法4构造证明法,如下将公式分成前提及结论。前提（PQ），P；结论Q；证明（1）（PQ）前提引入（2）P前提引入（3）（PQ）P（1）（2）假言推理（4）Q扣题要证明的结论与证明结果一致，所以推理正确第七章谓词逻辑71在谓词逻辑中用0元谓词将下列命题符号化（填空题）（1）1不是素数。F（A）。（2）如果23，则25。L（A，B）H（A，C）。72填空题设域为整数集合Z，命题XY彐Z（XYZ）的真值为173在谓词逻辑中将下列命题符号化（填空题）人固有一死。X（M（X）F（X）。74一阶逻辑与命题逻辑有何联系举例说明。（简答题）答把命题逻辑中的符号化的命题，把句子成分展示出来，并按句子成分符号化，就变成一阶逻辑中的公式了。例如每个人都会死。命题逻辑中的P变成一阶逻辑中的X（M（X）F（X）。附录习题符号集空集,并,交,对称差,绝对补,累加或主析取范式表达