离散数学期末考试题及答案

离散数学期末考试题及答案

一、单选题（每题2分，共20分）

1.下列哪个命题是永真式？（）A.\p\land\negp\B.\p\lor\negp\C.\p\rightarrow\negp\D.\\negp\rightarrow\negp\【答案】B【解析】永真式是指在所有可能的解释下都为真的命题选项B表示命题p与其否定\\negp\的和，根据排中律，\p\lor\negp\永远为真

2.集合\A=\{1,2,3\}\和\B=\{3,4\}\，则\A\cupB\为（）A.\{1,2,3,4\}B.\{1,2\}C.\{3,4\}D.\{1,2,4\}【答案】A【解析】集合的并集包含两个集合中的所有元素，不重复

3.下列哪个图是欧拉图？（）A.有一条边的环B.两个不相邻的顶点之间有边C.每个顶点的度数都是偶数D.有一个顶点的度数为1【答案】C【解析】一个图是欧拉图当且仅当它是连通的且所有顶点的度数都是偶数

4.下列哪个命题公式是重言式？（）A.\p\rightarrowq\rightarrowq\rightarrowp\B.\p\rightarrowq\rightarrowp\C.\p\landq\rightarrowp\D.\p\lorq\rightarrowp\landq\【答案】B【解析】重言式是指在所有可能的解释下都为真的命题公式选项B在任何解释下都为真

5.下列哪个关系是偏序关系？（）A.\R=\{a,b\mida\leqb\}\B.\R=\{a,b\midab\}\C.\R=\{a,b\mida=b\}\D.\R=\{a,b\mida\neqb\}\【答案】A【解析】偏序关系是一种满足自反性、反对称性和传递性的关系选项A表示小于或等于关系，是偏序关系

6.下列哪个数是素数？（）A.14B.15C.16D.17【答案】D【解析】素数是指只有1和自身两个因数的自然数17是素数

7.下列哪个命题公式是可满足的？（）A.\p\land\negp\B.\p\lor\negp\C.\p\rightarrow\negp\D.\\negp\rightarrow\negp\【答案】B【解析】可满足的命题公式是指至少存在一种解释使其为真选项B在任何解释下都为真

8.下列哪个图是平面图？（）A.完全图\K_5\B.完全二部图\K_{3,3}\C.圆D.简单环【答案】C【解析】平面图是指可以画在平面上而不使任何两条边交叉的图圆是平面图

9.下列哪个命题公式是等价的于\p\rightarrowq\？（）A.\p\rightarrowq\B.\\negp\lorq\C.\\negq\rightarrow\negp\D.\p\landq\【答案】B【解析】根据蕴涵式的等价定义，\p\rightarrowq\等价于\\negp\lorq\

10.下列哪个集合是可数无限集？（）A.自然数集B.有理数集C.实数集D.无理数集【答案】A【解析】可数无限集是指可以与自然数集建立一一对应关系的集合自然数集是可数无限集

二、多选题（每题4分，共20分）

1.以下哪些是图论中的基本概念？（）A.顶点B.边C.度数D.路径E.连通性【答案】A、B、C、D、E【解析】这些都是图论中的基本概念

2.以下哪些命题公式是重言式？（）A.\p\landq\rightarrowp\B.\p\rightarrowp\lorq\C.\p\rightarrowq\rightarrowq\rightarrowp\D.\p\lor\negp\E.\\negp\landq\rightarrow\negp\lor\negq\【答案】A、B、D、E【解析】这些都是重言式

3.以下哪些关系是等价关系？（）A.数轴上的等于关系B.集合的包含关系C.整数的模2同余关系D.向量的平行关系E.点的共线性【答案】A、C【解析】等价关系需要满足自反性、对称性和传递性数轴上的等于关系和整数的模2同余关系是等价关系

4.以下哪些图是欧拉图？（）A.有一条边的环B.两个不相邻的顶点之间有边C.每个顶点的度数都是偶数D.有一个顶点的度数为1E.连通的且每个顶点的度数都是偶数【答案】A、C、E【解析】欧拉图需要满足连通且每个顶点的度数都是偶数

5.以下哪些集合是可数无限集？（）A.自然数集B.有理数集C.实数集D.无理数集E.整数集【答案】A、B、E【解析】可数无限集是可以与自然数集建立一一对应关系的集合自然数集、有理数集和整数集是可数无限集

三、填空题（每题4分，共32分）

1.在命题逻辑中，\p\landq\的对偶式是______【答案】\\negp\lor\negq\

2.集合\A=\{1,2,3\}\和\B=\{3,4\}\，则\A\capB\为______【答案】\{3\}

3.一个图有6个顶点，每个顶点的度数都是3，则该图有______条边【答案】

94.关系\R=\{a,b\mida\leqb\}\在集合\\{1,2,3\}\上的自反闭包是______【答案】\\{1,1,1,2,1,3,2,2,2,3,3,3\}\

5.命题公式\p\rightarrowq\rightarrowr\等价于______【答案】\\negp\lor\negq\lorr\

6.下列图中，哪个是平面图？______A.完全图\K_4\B.完全二部图\K_{2,3}\【答案】B

7.离散数学中的五大基本结构是______、______、______、______和______【答案】集合、逻辑、图、树、关系

8.在集合论中，\A\setminusB\表示______【答案】属于A但不属于B的元素构成的集合

四、判断题（每题2分，共20分）

1.两个互不相交的集合的并集是空集（）【答案】（×）【解析】两个互不相交的集合的并集可以是非空集

2.一个图是欧拉图当且仅当它是连通的且所有顶点的度数都是偶数（）【答案】（√）

3.关系\R\的自反闭包一定是\R\本身（）【答案】（×）【解析】关系的自反闭包可能包含更多元素

4.命题公式\p\lor\negp\是重言式（）【答案】（√）

5.可数无限集是指可以与自然数集建立一一对应关系的集合（）【答案】（√）

6.完全图\K_3\是平面图（）【答案】（√）

7.关系\R\的对称闭包一定是\R\本身（）【答案】（×）【解析】关系的对称闭包可能包含更多元素

8.命题公式\p\land\negp\是可满足的（）【答案】（×）

9.无理数集是不可数无限集（）【答案】（√）

10.任何图都可以是平面图（）【答案】（×）

五、简答题（每题5分，共20分）

1.简述命题逻辑中的等价式【答案】等价式是指在所有可能的解释下都为真的命题公式两个命题公式\A\和\B\如果对于所有可能的解释都满足\A\leftrightarrowB\为真，则称\A\和\B\是等价的

2.解释什么是偏序关系【答案】偏序关系是一种满足自反性、反对称性和传递性的关系自反性是指对于任意元素\a\，有\a,a\inR\；反对称性是指对于任意元素\a\和\b\，如果\a,b\inR\且\b,a\inR\，则\a=b\；传递性是指对于任意元素\a\、\b\和\c\，如果\a,b\inR\且\b,c\inR\，则\a,c\inR\

3.描述什么是图论中的欧拉路径和欧拉回路【答案】欧拉路径是指经过图中每条边恰好一次的路径欧拉回路是指经过图中每条边恰好一次且起点和终点相同的路径一个图存在欧拉回路当且仅当它是连通的且所有顶点的度数都是偶数；一个图存在欧拉路径但不存在欧拉回路当且仅当它是连通的且恰好有两个顶点的度数是奇数

4.解释什么是可数无限集【答案】可数无限集是指可以与自然数集建立一一对应关系的集合换句话说，一个集合是可数无限集当且仅当它的元素可以排列成一个无穷序列，使得每个元素对应一个唯一的自然数

六、分析题（每题10分，共30分）

1.分析命题公式\p\rightarrowq\landq\rightarrowr\的逻辑结构【答案】命题公式\p\rightarrowq\landq\rightarrowr\表示\p\蕴含\q\且\q\蕴含\r\这个公式可以解释为如果\p\为真，则\q\也为真；如果\q\为真，则\r\也为真这个公式在逻辑上等价于\p\rightarrowr\

2.分析关系\R\在集合\A\上的自反闭包和对称闭包【答案】设\A\是一个集合，\R\是\A\上的一个关系关系的自反闭包是指在\R\中添加尽可能少的元素使得新的关系满足自反性具体来说，自反闭包\R^r\包含\R\以及所有形式为\a,a\的元素，其中\a\是\A\中的任意元素关系的对称闭包是指在\R\中添加尽可能少的元素使得新的关系满足对称性具体来说，对称闭包\R^s\包含\R\以及所有形式为\b,a\的元素，其中\a,b\是\R\中的任意元素

3.分析图论中的平面图和Kuratowski定理【答案】平面图是指可以画在平面上而不使任何两条边交叉的图Kuratowski定理是图论中的一个重要定理，它指出一个图不是平面图当且仅当它包含一个Kuratowski子图，即\K_5\（完全图\K_5\）或\K_{3,3}\（完全二部图\K_{3,3}\）的细分这个定理为判断一个图是否是平面图提供了一个有效的方法

七、综合应用题（每题25分，共50分）

1.给定集合\A=\{1,2,3\}\，构造一个关系\R\使得\R\是自反的、对称的但不是传递的【答案】设\A=\{1,2,3\}\，定义关系\R\为\R=\{1,1,2,2,3,3,1,2,2,1,2,3,3,2\}\这个关系是自反的，因为每个元素都与自身配对；它是对称的，因为如果\a,b\inR\，则\b,a\inR\；但它不是传递的，因为\1,2\inR\且\2,3\inR\，但\1,3\notinR\

2.给定命题公式\p\landq\rightarrowr\，求其真值表并判断其是否为重言式【答案】命题公式\p\landq\rightarrowr\的真值表如下|\p\|\q\|\r\|\p\landq\|\p\landq\rightarrowr\||--------|--------|--------|----------------|----------------------------------||T|T|T|T|T||T|T|F|T|F||T|F|T|F|T||T|F|F|F|T||F|T|T|F|T||F|T|F|F|T||F|F|T|F|T||F|F|F|F|T|从真值表可以看出，命题公式\p\landq\rightarrowr\不是重言式，因为它在某些解释下为假---标准答案

一、单选题

1.B

2.A

3.C

4.B

5.A

6.D

7.B

8.C

9.B

10.A

二、多选题

1.A、B、C、D、E

2.A、B、D、E

3.A、C

4.A、C、E

5.A、B、E

三、填空题

1.\\negp\lor\negq\

2.\{3\}

3.

94.\\{1,1,1,2,1,3,2,2,2,3,3,3\}\

5.\\negp\lor\negq\lorr\

6.B

7.集合、逻辑、图、树、关系

8.属于A但不属于B的元素构成的集合

四、判断题

1.（×）

2.（√）

3.（×）

4.（√）

5.（√）

6.（√）

7.（×）

8.（×）

9.（√）

10.（×）

五、简答题

1.等价式是指在所有可能的解释下都为真的命题公式两个命题公式\A\和\B\如果对于所有可能的解释都满足\A\leftrightarrowB\为真，则称\A\和\B\是等价的

2.偏序关系是一种满足自反性、反对称性和传递性的关系自反性是指对于任意元素\a\，有\a,a\inR\；反对称性是指对于任意元素\a\和\b\，如果\a,b\inR\且\b,a\inR\，则\a=b\；传递性是指对于任意元素\a\、\b\和\c\，如果\a,b\inR\且\b,c\inR\，则\a,c\inR\

3.欧拉路径是指经过图中每条边恰好一次的路径欧拉回路是指经过图中每条边恰好一次且起点和终点相同的路径一个图存在欧拉回路当且仅当它是连通的且所有顶点的度数都是偶数；一个图存在欧拉路径但不存在欧拉回路当且仅当它是连通的且恰好有两个顶点的度数是奇数

4.可数无限集是指可以与自然数集建立一一对应关系的集合换句话说，一个集合是可数无限集当且仅当它的元素可以排列成一个无穷序列，使得每个元素对应一个唯一的自然数

六、分析题

1.命题公式\p\rightarrowq\landq\rightarrowr\表示\p\蕴含\q\且\q\蕴含\r\这个公式可以解释为如果\p\为真，则\q\也为真；如果\q\为真，则\r\也为真这个公式在逻辑上等价于\p\rightarrowr\

2.设\A\是一个集合，\R\是\A\上的一个关系关系的自反闭包是指在\R\中添加尽可能少的元素使得新的关系满足自反性具体来说，自反闭包\R^r\包含\R\以及所有形式为\a,a\的元素，其中\a\是\A\中的任意元素关系的对称闭包是指在\R\中添加尽可能少的元素使得新的关系满足对称性具体来说，对称闭包\R^s\包含\R\以及所有形式为\b,a\的元素，其中\a,b\是\R\中的任意元素

3.平面图是指可以画在平面上而不使任何两条边交叉的图Kuratowski定理是图论中的一个重要定理，它指出一个图不是平面图当且仅当它包含一个Kuratowski子图，即\K_5\（完全图\K_5\）或\K_{3,3}\（完全二部图\K_{3,3}\）的细分这个定理为判断一个图是否是平面图提供了一个有效的方法

七、综合应用题

1.设\A=\{1,2,3\}\，定义关系\R\为\R=\{1,1,2,2,3,3,1,2,2,1,2,3,3,2\}\这个关系是自反的，因为每个元素都与自身配对；它是对称的，因为如果\a,b\inR\，则\b,a\inR\；但它不是传递的，因为\1,2\inR\且\2,3\inR\，但\1,3\notinR\

2.命题公式\p\landq\rightarrowr\的真值表如下|\p\|\q\|\r\|\p\landq\|\p\landq\rightarrowr\||--------|--------|--------|----------------|----------------------------------||T|T|T|T|T||T|T|F|T|F||T|F|T|F|T||T|F|F|F|T||F|T|T|F|T||F|T|F|F|T||F|F|T|F|T||F|F|F|F|T|从真值表可以看出，命题公式\p\landq\rightarrowr\不是重言式，因为它在某些解释下为假。