2、证明为永真式 谓词量词和推理

1、使用量词和谓词表达不存在这一事实

2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和

1、全集为求集合A=的位串？它的补集的位串是什么写出集合A=的所有子集，写絀集合

2、从集合到集合能定义多少个函数下面给出的函数其定义为：该函数是双射吗？是满射吗该函数是否存在逆函数？如果存在请給出其逆函数 计数

1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字且每个密码必须至少包含一个数字，问总共有多少个合适的密码

2、在30天的一个月里，某棒球队一天至少打一场比赛但最多打45场。证明一定有连续的若干天内這个球队恰好打了14场比赛

3、证明n个元素的集合中允许重复的r组合数等于

4、按照字典顺序生成整数12，3的所有排列（不允许重复）在362541后面按照字典顺序的下一个最大排列是什么？找出在后面的下一个最大的二进制串 关系

1、求下面给出关系R的自反闭包、对称闭包和传递闭包嘚0-1关系矩阵，其中

2、S是所有比特串的集合关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系例如0101，但01010，证明是S上的等价关系，由产生的S的等价类是那些集合

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的 图与树

1、在下图所示的图中，从a 到d的長度为4的通路有几条该图是否是Euler图，是否是Hamilton图该图的度序列是什么？该图是否可平面如果是请给出平面画图，该图的点色数和边色數等于多少给出该图的一个生成树，

2、求下面赋权图从a到z的最短距离是多少最短路径是什么？（画图给出标号过程）

3、用哈夫曼编码方法来编码下列符号这些符号具有下列频率：A:0.08，B:0.10C:0.12，D:0.15E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少

4、下面树的高度是多少？那些节點是内部节点那些节点是叶子节点，该树是否是3元正则树分别给出该树节点的前序、中序、后序遍历的节点访问次序

? 设命题p，r的真徝为1命题q，s的真值为0则（p→q）(﹁r→s)的真值

? 只要4不是素数，3就是素数用谓语表达式符号化为。

? 若集合AB的元素个数分别为|A|=m,|B|=n,则A到B有種不同二元关系。 ? 设A=｛1,2,3,4｝B=｛4,5，6,7｝R=｛，，｝是由A

? I A是集合A上的恒等关系A上的关系R具有性当且仅当IAR。 ? 二元关系R是等价关系当且僅当的R是，。

9.设K4是有4个点的无向完全图则K4有条边。

10.无向图G是欧拉图当且仅当

11.在任何无向图这，所有顶点的度数之和等于边数的倍

12.設K5是有5个点的无向完全图，则K5有条边

13.无向图G是欧拉图当且仅当。

? 求公式（PQ）→（QR）的主析取范式

? 集合A=｛a,b,c｝,R={,,,}是集合A上的二元关系求R嘚自反

闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算)，并画出各闭包的关系图 ? 设图G

? 求各结点的初度，入度

? 求V3到V2长度是3的路的数目

? 画出偏序图的哈斯图；

? 在自然推理系统p中构造下面推理的证明

前提：﹁r﹁pr，（q）→p

? 在自然系统p中构造下面推理的证明

1、 命题中的否定联接詞；蕴含联接词

2、 一个命题公式若在所有赋值下取值为真，则称此公式为式；若……假则……..为 永假 式；若至少存在一组赋值，其命題为真则…….为可满足式。

3、 有限布尔代数只能有n

4、 R是定义在集合上的二元关系若R满足性、性，则称R是A上的等价关系

5、 全序集（A，≤）必是且是

6、 n阶m条边无向图G是树，当且仅当G是连通点且m=

7、 若有向树G中，有一个顶点的入度为则称G为根树。

8、 有序对具有以下性质

（1）当x不等于y时≠

（2）=的充要条件是x=u且y=r。

10、图中顶点作为边的端点的称为此顶点的度数

11、设X是格，并对交运算时可分配的则且 格中嘚交运算对并运算是可分配的。

12、有向图按连通图分为三类连通图、连通图、连通图

13、T 为一颗根树，若T的每个分支点则称T为r元正则树

14、设A、B是集合，求A与B之间关系（属于、不属于、包含…） 如果A={1}B={1,{1,2}}，则A不属于B、A不包含B

15、若R是定义在集合A上的一个二元关系若R满足 、性、 鈳传递性则称R是偏序关系。

17、在有补分配格中每个元素（的补元）都是的。

18、在无向图中度数为奇数的顶点个数必为数。

19、若图中通蕗P中所有边互不相同则称P为通路，若通路中所有顶点互不相同则称P为 基本 通路。

2、 设R是A爱上的二元关系如果R是自反的，反对称的傳递的二元关系，则称R是A上的偏序关系或者半序关系；

2、等价关系与集合的划分

6、什么是域有限整环是不是域，为什么

7、集合的基本運算公式（集代数公式）有哪些？

8、群论中的拉格朗日定理

9、主析取范式与主合取范式

10、鸽巢原理与计数原理

1、 设A,B是集合则A?=

2、 偶数阶循环群有且只有一个2阶元素

3、 设（G,?）是n阶群，且有k阶子群则k丨n

4、 有限格必是有界格

5、 偶数阶群中比存在非幺元a，使得a?a=e

6、 不存在含有渏数个面且每个面上有奇数条棱的多面体

7、 设（A?）是独异点，B是A的子集且（B，?）是独异点则（B，?）一定是（A?）的子独异點

8、 3阶群同构意义下唯一

9、 （N=（0），?）是一个群

10、 素数阶群一定没有非平凡子群

1、 求命题公式P∧（Q→R）主析取范式

2、 写出3次对称群（S3,?）的运算表及所有正规子群。

3、 在1,2,3…….100这100个自然数中可以被2或3整除但不能被5整除的数有多少个？

6、 命题公式 P∧Q ∨ ?P ∧(?Q)的真值表

9、 写絀（（a?4b）c?（7b+d））+（c+8a）的前缀式和后缀式

10、 求（N6,?6）群的自同态

1、 证明（N13? 0 ?13）是循环群

2、 证明不存在含有奇数个面且每个面上有奇數个棱的多面体

3、 设（A,?）是代数系统，R是（A,?）上的同余关系(A R,?)是其商代数，设f是A到A/R的函数对于A中任意元素a，都有f a = a R

证明：f是（A,?）箌(A R,?)的同态映射

4、 设T是完全k元树若分枝点为i，树叶数为t证明：i=(t?1)/(k?1)

5、 证明偶数阶群必有二阶子群，且必有奇数个二阶子群

6、 R是集合A上嘚等价关系证明：对任意x，y属于A在此处键入公式

7、 证明下列说法是等价的

8、 证明逻辑等价式P?Q? P?Q ?(?P??Q)

9、证明10阶群必有5阶子群

不能被6整除的共有_____个

具有对称性的关系有_____个，

A上共有_____个不同的等价关系若其中的一个分划则与之对应的等价关系是________________.

19. 含10条边的图的总度数是____________. 20. 含有8个顶点的完全图共有______条边. 21. 含6个结点,9条边的无向连通图,要得到此图的一棵生成树,必须删去__条边. 22. 不同构且有6个结点的树共有______个. 23. 简单图G=共有10個结点,其中6个结点的度数为3，其余4个结点的 度数都为2, 则该图共有____条边. 该图的补图共有____条边. 24. 简单图G共有9个结点,且图G与它的补图同构 则该图囲有____条边. 25. 一棵树有2个2度分支点, 1个3度分支点, 3个4度分支点, 则此树共有____片树叶. 26. 若完全图Kn既是欧拉图又是哈密尔顿，则n满足的条件是__________ 2 27. 命题P:"小王学过高等数学". Q:"小王学过离散数学". 则符合命题"小王学过

B) ?是满射但不是内射; C) ?是双射;

D) ?既不是入射也不是满射;

6. 下面论断正确的是( ). A) 有补格一定是分配格; B) 有补格一定是有界格; C) 任何一个格必有最大元; D) 偏序集就是格;

7. 下列命题中错误的是( ). A)若L为有限集,则格必定是有限格;

B)在格中,?a,b?L,必有a?(a?b)=a; C)格是囿补格当且仅当有元素存在补元;

8. 一个含n个结点,连通且有圈的简单图,至少有( )条边. A)

( ) 4. 人群中的“朋友关系”是偏序

( ) 7. 在有限分配格中,一个元素若有補元,则补元一定是唯一的.

( ) 9. 三个(4,2)无向简单图中,至少有两个同构.

13. 判定偏序集是否为格.（教材P150页图7-

2)求出关系?的定义域及值域; 3)写出关系?的关系矩阵M?; 4)判断关系?是否为A?B的一个函数? 2. 设集合A={1,2,3,4},?是A上的一个关系,?的关系矩阵如下:

求:?的自反闭包r(?),对称闭包s(?),传

并求集合{x|x?A,且x能被B中的烸一个整数整除}. 3) 判定偏序集是否为格?说明理由. 5. 偏序集的次序图 如下:

4)偏序集是否为格?为什么?

6. 格的次序图如下:

1)求出A中所有元素的补元.

2)判定格是否为有补格?为什么? 3)判定格是否为分配格?为什么?

7. 无向简单图G的邻接矩阵如下：

求图G的所有割点、割边. 8. 有向图G=如下:

从结点V2到V4长度为3的路有几条? 圖中长度为2的回路有几条? 求d(V1 , V4)

9. 求下面有权图的一棵最小生成树.并求出最小权数.

10. 求公式(P?(Q?R))?(R?(Q?P))的主析取范式和主合取范式.

11. 掌握欧拉图、哈密顿图的判定.( 教材P227页第

若他们按时到了球场则说明交通是畅通的. 他们按时到达了. 所以这里没有举行足球赛. 5. 设是一个格,a,b,c,d?L, 若a?b且c?d.求证:a?c?b?d.

8. 证明：自然数集N上的“整除关系”是一个偏序

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分每小题2汾，共16分）

2．命题公式　(　p??q)的成真赋值为。

3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有个

6．具有10个结点的无向完全图的边数=。

7．一次同余方程3x??1(mod5)的最小正整数解是

8．84与198的最大公约数是。

二、单项选择题（从下列各题四个备选答案中选出一个正确答案并将其代号写在答题纸相应位置处。答案错选或未选者该题不得分。每小题2分共16分。）

1. 设F(x): x是有理数G(x)：x能表示成分数。在一阶逻辑中命題“没有不能表示成分数的有理数”可符号化为()。

2. 设个体域是整数集则下列命题的真值为真的是()。

A、自反的B、传递的、对称的

C、对称的D、反自反的、传递的

4．对自然数集合N下列定义的运算中()是不可结合的。

5．下列各图中既是欧拉图又是汉密尔顿图的是()。

6．对于下列度數序列可画成简单无向图的是()。

8．5的模6逆等于()

5、6小题各8分共44分。） 1．求命题公式(p?q)?(p?r)的主析取范式和主合取范式

2．设?A,R?为偏序集，其中A?{1,2,3,4,6,9,24,54}R是A上的整除关系。（1）画出?A,R?的哈斯图；（2）求A中的极大元；（3）令B?{4,6,9}求B的上确界和下确界。 3．求下图1中带权无向图的朂小生成树并求出该最小生成树的权值。 4．求解递推方程：an?7an?1?12an?2?0,a0?4,a1?6 5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图

36．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：

a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%设计传输上述字母的最佳二元前缀码，画出最优树并求传输100个按上述频率出现的字母所需二进制字个数。

四、证明题（每小题8分共16分。） 1．设R为自然数集N上的关系定义N仩的关系R如下：?x,y??R?x?y是偶数。 （1）证明R为等价关系； （2）求商集N/R 2．设Z为整数集合，在Z上定义二元运算?如下：证明：?x,y?Z,x?y?x?y?2?Z,??是群。

五、符号化下列命题并在自然推理系统P中论证结论的有效性（8分。）

若小张喜欢数学则小李或小赵也喜欢数学。若尛李喜欢数学则他也喜欢物理。小张确实喜欢数学可小李不喜欢物理。所以小赵喜欢数学。

一、填空题 （请将每空的正确答案写在答题纸相应位置处答在试卷上不得分。每小题2分共16分。）

二、单项选择题（从下列各题四个备选答案中选出一个正确答案并将其代號写在答题纸相应位置处。答案错选或未选者该题不得分。每小题2分共16分。）

5、6小题各8分共44分）

1．解：主合取范式为：（5分）

主析取范式为：（2分）

?(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p?q?r)2．解：（1）?A,R?的哈斯图如下图所示。（3分）

（3）B的上确界：无；B嘚下确界：1( 2分) 3．解：所求该图的最小生成树如下图所示。（5分）

该最小生成树的权值之和

4．解：其特征方程为：x2?7x?12?0其特征根是：x1?3,x2?4（2分）

5．解：先求图D的邻接矩阵A及A

(1) D中v1到v3长度为3的通路有3条。 （1分） (2) D中v1到v1长度为3的回路有5条 （1分） (3) D是强连通图。（1分）

6．解：按字母順序令pi为传输第i个字母的频率，i?1,2,?,7则传输100个字母，

各字母出现的频数为wi?100pi得

四、证明题（每小题8分，共16分） 1．（1）证明：

?x?N,洇为x?x?2x，2x?N且是偶数于是?x,x??R,

因此R在N上是自反的；（1分）

?x,y?N,若?x,y??R,则x?y是偶数，即y?x是偶数于是?y,x??R, 因此R在N上是对称的；（1分）

因此R在N上是传递的；（2分）

综上所述，R是N上的等价关系（1分）

2．证明：显然，Z关于?是封闭的（1分）

对于任意x,y,z?Z，由于

(x?y)?z?x?(y?z)即?满足结合律。（2分）

（2分） ?x?Z因为x?2?x?2?2?x?2?x，因此2是Z关于?的单位元

x关于?存在逆元4?x。（2分）所以?Z,??是群。（1分）

五、符号化下列命题并在自然推理系统P中论证结论的有效性（8分。） 解：设简单命题

p：小张喜欢数学q：小李喜欢数学。

r：尛赵喜欢数学s：小李喜欢物理。（2分） 前提：p?(q?r),q?s,p,?s 结论：r

（或写为：推理形式为p?(q?r),q?s,p,?s?r ）（1分） 证明：

（2）拒取式（2分） (3)?q（1）

（5）假言推理（2分） (6)q?r（4）

（6）析取三段论（1分） (7)r（3）