离散数学作业答案

离散数学作业答案01一、单项选择题（共8 道试题，共80 分。

）1. 本课程的教学内容分为三个单元，其中第三单元的名称是（）．A.数理逻辑B. 集合论C. 图论D. 谓词逻辑满分：10 分2. 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（）．A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系满分：10 分3. 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（）讲．A. 18B. 20C. 19D. 17满分：10 分4. 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（）．A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答满分：10 分5. 课程学习平台左侧第1个版块名称是：（）．A. 课程导学B. 课程公告C. 课程信息D. 使用帮助满分：10 分6. 课程学习平台右侧第5个版块名称是：（）．A.典型例题B. 视频课堂C. VOD点播D. 常见问题满分：10 分7. “教学活动资料”版块是课程学习平台右侧的第（）个版块．A. 6B. 7C. 8D. 9满分：10 分8. 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（）．A. 复习指导B. 视频C. 课件D. 自测满分：10 分二、作品题（共 1 道试题，共20 分。

）1. 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．提示：答题框内不能输入超过2000个字符。

如果超过2000字符，请使用附件上传功能。

学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培训自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。

离散数学作业一、选择题1、下列语句中哪个就是真命题(C )。

A.我正在说谎。

B.如果1+2=3,那么雪就是黑色的。

C.如果1+2=5,那么雪就是白色的。

D.严禁吸烟！2、设命题公式))((r q p p G →∧→=,则G 就是( C )。

A 、 恒假的B 、 恒真的C 、 可满足的D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ∃∀→中的变元x ( C )。

A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}C.R={<1,1>,<2,2>,<3,3>,<1,4>}D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。

A.单射而非满射B.满射而非单射C.双射D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D )b b b a a a b a * a b b b a a b a *8( A )A B C D 9、下列各组数中,能构成无向图的度数列就是( D ) A.1,1,1,2,4 B.1,2,3,4,5 C.0,1,0,2,4 D.1,2,3,3,510、一棵树有2个4度顶点,3个3度顶点,其余都就是树叶,则该树中树叶的个数就是( B )A 、8B 、9C 、 10D 、 11 11、“所有的人都就是要死的。

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。

离散数学练习题(含答案)题目1. 对于集合 $A={1,2,3,...,10}$ 和 $B={n|n是偶数，2<n<8}$，求 $A \cap B$ 的元素。

2. 存在三个可识别的状态A,B,C。

置换群 $S_3$ 作用在状态集上。

定义四个动作：$α: A → C, β: A → B, γ: C→ A, δ: B→ C$。

确定式子，描述 $\{α,β,γ,δ\}$ 的乘法表。

3. 证明 $\forall n \in \mathbb{N}$，合数的个数不小于$n$。

4. 给定一个无向带权图，图中每个节点编号分别是$1,2,...,n$，证明下列结论：a. 如果从节点$i$到$j$只有一条权值最小的路径，则这条路径的任意子路径都是最短路径。

b. 如果从节点$i$到$j$有两条或两条以上权值相等的路径，则从$i$到$j$的最短路径可能不唯一。

答案1. $A \cap B = \{2,4,6\}$。

2. 乘法表：3. 对于任意$n$，我们可以选择$n+1$个连续的自然数$k+1,k+2,...,k+n,k+n+1$中的$n$个数，其中$k \in \mathbb{Z}$。

这$n$个数构成的$n$个正整数均为合数，因为它们都至少有一个小于它自身的因子，所以不是质数。

所以合数的个数不小于任意$n$。

4.a. 根据题意，从$i$到$j$只有一条权值最小的路径，即这条最短路径已被确定。

如果从这条路径中任意取出一段子路径，假设这段子路径不是这个节点到$j$的最短路径，那么存在其他从$i$到$j$的路径比这段子路径更优，又因为这条路径是最短路径，所以这段子路径也一定不优于最短路径，矛盾。

所以从这条路径中任意取出的子路径都是最短路径。

b. 如果从节点$i$到$j$有多条权值相等的路径，则这些路径权值都是最短路径的权值。

因为所有最短路径的权值相等，所以这些路径的权值就是最短路径的权值。

所以从$i$到$j$的最短路径可能不唯一。

习题二谓词逻辑一、选择题1、下列哪个式子不是谓词演算的合式公式( )A. (x)(A(x,2)∧B(y))B. (x)(A(x)∧B(x,y))C. ((x)∧(y))→(A(x,y)∧B(x,y))D. (x)(A(x)→B(y))2、设个体域是整数集，则下列命题的真值为真的是（）A.∀x∃y (xy=1)B. ∃x∀y(x+y=y)C.∃x∀y(x+y=x)D. ∀x∃y(y=2x)3、设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )A.(x)A(x)→BB. (x)A(x)→BC. A(x)→BD.(x)A(x)→(x)B4、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中的x( ).A.只是约束变元B.只是自由变元C.既非约束变元又非自由变元D.既是约束变元又是自由变元5、谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z))中量词x的辖域是（）.A．(x)Q(x,z)→(x)(y)R(x,y,z))B．Q(x,z)→(y)R(x,y,z)C．Q(x,z)→(x)(y)R(x,y,z)D．Q(x,z)6、在论域D={a,b}中与公式（）A（x）等价的不含存在量词的公式是（）A. B.C. D.7、设M（x）：x是人；F（x）：x要吃饭.用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）.A．B．C．D．8、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（）.A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)9、按照约束变元的改名规则，∀xP(x) →∃yR(x,y)不可改写成（）. A．∀mP(m) →∃yR(x,y) B．∀xP(x) →∃zR(x,z)C．∀xP(x) →∃xR(x,x) D．∀xP(x) →∃nR(x,n)10、∀ x∀y(P(x,y)∧Q(y,z))∧(∃x)p(x,y),下面的描述中错误的是（）A.(∀ x)的辖域是（∀ y）（P（x,y）∧Q(y,z)）B．z是该谓词公式的约束变元C.(∃ x）的辖域是P（x,y）D. x是该谓词公式的约束变元二、填空题1、设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______.2、使公式(x)( y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x.3、公式(x)A(x)→B(y)的前束范式为______.4、公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元为________________.5、令R(x):x是实数，Q(x):x是有理数。

离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中，含有3个元素的子集有多少个？A. 4B. 8C. 16D. 32答案：B解析：含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算，其中n为集合的元素个数，k为子集中的元素个数。

在本题中，n=4，k=3，所以C(4, 3) = 4! / [3!(4-3)!] = 4。

2. 下列哪个命题是真命题？A. 所有偶数都是整数。

B. 所有整数都是偶数。

C. 所有整数都是奇数。

D. 所有奇数都是整数。

答案：A解析：偶数是指能被2整除的整数，因此所有偶数都是整数，选项A是真命题。

选项B、C和D都是错误的，因为并非所有整数都是偶数或奇数。

二、填空题1. 逻辑运算符“非”（NOT）的真值表是：当输入为真时，输出为______；当输入为假时，输出为真。

答案：假解析：逻辑运算符“非”（NOT）是一元运算符，它将输入的真值取反。

如果输入为真，则输出为假；如果输入为假，则输出为真。

2. 命题逻辑中，合取词“与”（AND）的真值表是：当两个命题都为真时，输出为真；否则输出为______。

答案：假解析：合取词“与”（AND）是二元运算符，只有当两个命题都为真时，输出才为真；如果其中一个或两个命题为假，则输出为假。

三、简答题1. 解释什么是等价关系，并给出一个例子。

答案：等价关系是定义在集合上的一个二元关系，它满足自反性、对称性和传递性。

例如，考虑整数集合上的“同余”关系。

对于任意整数a，b，如果a和b除以同一个正整数n后余数相同，则称a和b模n同余。

这个关系是自反的（a同余a），对称的（如果a同余b，则b同余a），并且是传递的（如果a同余b且b同余c，则a同余c）。

2. 什么是图的连通性？一个图是连通的需要满足什么条件？答案：图的连通性是指在无向图中，任意两个顶点之间都存在一条路径。

一个图是连通的需要满足以下条件：图中的任意两个顶点v和w，都可以通过图中的边相互到达。

《离散数学》练习题和参考答案《离散数学》练习题和参考答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P 答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P↔（4）QP→⌝P⌝⌝（2）QQ→P⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y 对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( ) (3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散数学试题答案一、选择题1. 命题逻辑中，若命题P为“今天是周末”，命题Q为“我去野餐”，那么复合命题“今天是周末或我去野餐”在逻辑上的表示为：A. P∨QB. P∧QC. ¬P∨QD. ¬P∧Q答案：A2. 在集合论中，集合A和集合B的并集表示为：A. A - BB. B - AC. A ∪ BD. A ∩ B答案：C3. 有限自动机中，确定一个状态为接受状态的条件是：A. 有从该状态出发的ε-转移B. 所有从该状态出发的转移都能到达另一个接受状态C. 该状态不在任何闭包中D. 该状态在至少一个闭包中答案：D4. 哈希表中，解决冲突的常用方法不包括：A. 开放定址法B. 链地址法C. 再散列法D. 树形查找法答案：D5. 图的邻接矩阵表示法中，若顶点u到顶点v有一条边，则矩阵中的元素M[u][v]为：A. 0B. 1C. -1D. ∞答案：B二、填空题1. 在命题逻辑中，德摩根定律表明了________和________的对偶关系，即(¬(P∧Q))等价于________，而(¬(P∨Q))等价于________。

答案：合取；析取；¬P∨¬Q；¬P∧¬Q2. 集合的幂集是指该集合的所有________的集合，记作P(A)。

答案：子集3. 一个有向图G，若对于任意顶点u和v，都存在从u到v以及从v到u的路径，则称图G是________的。

答案：强连通4. 在图的遍历算法中，深度优先搜索(DFS)使用________数据结构进行遍历，而广度优先搜索(BFS)使用________数据结构进行遍历。

答案：栈；队列5. 哈密顿回路是指在一个图中，通过所有顶点恰好一次且最后回到起点的闭合路径，而欧拉回路是指通过图中每条边恰好一次并且回到起点的闭合路径，若一个图存在欧拉回路，则该图必须是________的。

答案：连通三、简答题1. 请简述命题逻辑中的四种标准形式及其真值表。

第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。

教学目的：1. 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。

2. 熟练掌握常用的基本等价式及其应用。

3. 熟练掌握（主）析/合取范式的求法及其应用。

4. 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。

5. 熟练掌握形式演绎的方法。

教学重点：1 .命题的概念及判断2 .联结词，命题的翻译3. 主析（合）取范式的求法4. 逻辑推理教学难点：1. 主析（合）取范式的求法2. 逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母 A , B,…，Z或带下标的大写字母或数字表示,如A i, [10], R等，例如A1：我是一名大学生。

A1：我是一名大学生.[10]:我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1否定联结词「P1.2.2合取联结词A1.2.3 析取联结词V1.2.4 条件联结词—125126 与非联结词T性质：(1)P T P=「( PAP)二「P；(2)(P T Q)T( P T Q) -「( P T Q) - PAQ；(3)( P T P)T( Q TQ) -「P T「Q= P V Q。

127 或非联结词J性质:(1) P J P=「( P V Q) =「P;(2)( P J Q )；( P J Q) =「( P J Q) = P V Q;(3)( P J P)J( Q J Q) =「P Q=P V-Q) = PAQ1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2 ）如果P是公式，则「P是公式；（3）如果P、Q是公式,则PAQ、PVQ、P > Q、P Q都是公式；（4）当且仅当能够有限次的应用（1）、（2）、（3）所得到的包括命题变元、联结词和括号的符号串是公式。

可编辑修改精选全文完整版离散数学习题答案习题一：P121.判断下列句子哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？(1)中国有四大发明。

(2)5是无理数。

(3)3是素数或4是素数。

(4)x2+3<5，其中x是任意实数。

(5)你去图书馆吗？(6)2与3都是偶数。

(7)刘红与魏新是同学。

(8)这朵玫瑰花多美丽呀！(9)吸烟请到吸烟室去！(10)圆的面积等于半径的平方乘π。

(11)只有6是偶数，3才能是2的倍数。

(12)8是偶数的充分必要条件是8能被3整除。

(13)2025年元旦下大雪。

1、2、3、6、7、10、11、12、13是命题。

在上面的命题中，1、2、7、10、13是简单命题；1、2、10是真命题；7的真值现在还不知道。

2.将上题中是简单命题的命题符号化。

(1)p：中国有四大发明。

(2)q：5是无理数。

(7)r：刘红与魏新是同学。

(10)s：圆的面积等于半径的平方乘π。

(1)t：2025年元旦下大雪。

3.写出下列各命题的否定式，并将原命题及其否定式都符号化，最后指出各否定式的真值。

“5是有理数”的否定式是“5不是有理数”。

解：原命题可符号化为：p：5是有理数。

其否定式为：非p。

非p的真值为1。

4.将下列命题符号化，并指出真值。

(1)2与5都是素数。

(2)不但π是无理数，而且自然对数的底e也是无理数。

(3)虽然2是最小的素数，但2不是最小的自然数。

(4)3是偶素数。

(5)4既不是素数，也不是偶数。

a：2是素数。

b：5是素数。

c：π是无理数。

d：e是无理数。

f：2是最小的素数。

g：2是最小的自然数。

h：3是偶数。

i：3是素数。

j：4是素数。

k：4是偶数。

解：（1）到（5）的符号化形式分别为a∧b，c∧d，f∧非g，h∧i，非j∧非k。

这五个复合命题的真值分别为1，1，1，0，0。

5.将下列命题符号化，并指出真值。

a：2是偶数。

b：3是偶数。

c：4是偶数。

习题六格与布尔代数
一、填空题
1、设是偏序集,如果_________, 则称<A, ≤>是(偏序)格.
2、设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______.
3、一个格称为布尔代数，如果它是______格和______格.
4、设<>是有界格，a,b L,若a b=0,则a=b=_____；若a b=1,则a=b=____.
二、证明题
1、设<L, ≤>是格，a,b,c,d∈L。

试证：若a≤b且c≤d，则
a∧c≤b∧d
2、证明：在有补分配格中，每个元素的补元一定唯一。

3、设<S,⊕,⊙,′,0,1>是一布尔代数，则
R={<a,b> | a⊕b=b}是S上的偏序关系
4、若<A，≤>是一个格，则对任意a、b 、c∈A，有若a≤c且b≤c，则a∨b ≤c。

5、若<A，≤>是一个格，则对于任意a，b∈A，证明以下两个公式等价；（1）a≤b
（2）a∨b =b
6、证明：如果格中交对并是分配的，那么并对交也是分配的，反之亦然。

7、如果<A,≤>是有界格，全上界和全下界分别是1和0，则对任意元素a∈A，证明：
a∨1=1∨a=1 ，a∨0=0∨a=a。

离散数学习题答案习题一及答案：（P14-15） 14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q ∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→15、设p ：2+3=5.q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→ 解：p=1，q=1，r=0，()(110)1p q r ∧∧⌝⇔∧∧⌝⇔，(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔ ()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型： （2）()p p q →⌝→⌝解：列出公式的真值表，如下所示：由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值： （4）()p q q ⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p q ⇔⎧⎨⇔⎩ 所以公式的成真赋值有：01，10，11。

习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式， 所以成真赋值为011，111。

*6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式，所以成假赋值为100。

离散数学习题及答案一、选择题：1、下列命题正确的是（ A ）。

A ．φ⋂{φ}=φB ．φ⋃{φ}=φC ．{a}∈{a ，b ，c}D ．φ∈{a ，b ，c}2、设集合},{y x X =，则=)(x ρ（ C ）。

}}.,{},{},{{.}};,{},{},{,{.}};{},{,{.}};{},{{.y x y x D y x y x C y x B y x A φφ3、下列式子中正确的有（ B ）。

..};,{.};{.;0.φφφφφφ∈∈∈=D b a C B A4、某个集合的元数为10，可以构成（ D ）个子集。

A 、10B 、20C 、210D 、1025、下列命题正确的有（ A ）A 、}},{,,{},{b a b a b a ⊆B 、}},,{,,{},{c b a b a b a ∈C 、}}},{{,{},{b a a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6、集合A={a ，b ，c}，A 上的关系R={（a ，b ），（a ，c ），（b ，a ），（b ，c ），（c ，a ），（c ，b ），（c ，c ）}，则R 具有关系的（ B ）性质。

A 、自反性B 、对称性C 、反对称性D 、传递性7、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ D ）。

A ．单射而非满射B ．满射而非单射C ．双射D ．既不是单射，也不是满射8、下列语句中，（ C ）是命题。

A ．下午有会吗？B ．这朵花多好看呀！C ．2是常数。

D ．请把门关上。

9、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。

A ．析取范式B ．合取范式C ．主析取范式D ．以上答案都不对10、通过约束变元的换名规则，可以将 ∀x(P(x)→R(x, y))∧Q(x, y) 改写为（ C ）A 、∀x(P(x)→R(u, y)∧Q(x, y)B 、∀x(P(y)→R(y, y)∧Q(x, y)C 、∀z(P(z)→R(z, y))∧Q(x, y)D 、∀z(P(z)→R(z, y))∧Q(z, y)11、∃x(P(x)∨(∀y)R(y))→Q(x)中∃x 的辖域是（ C ）。

答题：答题：答题：答题：已提交参考答案：A问题解析：5.单选题下面的表述与众不一致的一个是A．P ：广州是一个大城市 B．P ：广州是一个不大的城市C．P ：广州是一个很不小的城市 D．P ：广州不是一个大城市答题：已提交参考答案：C问题解析：6.单选题设,P：他聪明；Q：他用功.在命题逻辑中,命题：“他既聪明又用功.” 可符号化为：A．P ù Q B．P QC．P ú Q D．P ùQ答题：已提交参考答案：A问题解析：7.单选题设：P ：刘平聪明.Q：刘平用功.在命题逻辑中,命题：“刘平不但聪明,而且用功” 可符号化为：A．P ù Q B．P ú QC．P ú Q D．P ùQ答题：已提交参考答案：A问题解析：8.单选题设：P：他聪明；Q：他用功.则命题“他虽聪明但不用功.”在命题逻辑中可符号化为A．P ù Q B．P QC．P ú Q D．P ùQ答题：已提交参考答案：D问题解析：9.单选题设：P：我们划船.Q：我们跑步.在命题逻辑中,命题：“我们不能既划船又跑步.” 可符号化为：A．P Q B．P ù QC．P ú Q D．P ùQ答题：已提交参考答案：B问题解析：10.单选题设：P：王强身体很好；Q：王强成绩很好.命题“王强身体很好,成绩也很好.”在命题逻辑中可符号化为A．P ú Q B．P QC．P ùQ D．P ù Q答题：已提交参考答案：D问题解析：随堂练习提交截止时间：2017-12-15 23:59:59当前页有10题,你已做10题,已提交10题,其中答对10题.11.单选题设：P：你努力；Q：你失败.则命题“除非你努力,否则你将失败.”在命题逻辑中可符号化为A．QP B．P QC． P Q D．Q úP答题：已提交参考答案：C问题解析：12.单选题设：p：派小王去开会.q：派小李去开会.则命题：“派小王或小李中的一人去开会” 可符号化为：答题：已提交参考答案：B问题解析：13.单选题设：P：天下雪.Q：他走路上班.则命题“只有天下雪,他才走路上班.”可符号化为 .A．PQ B．Q PC．Q úP D． Q P答题：已提交参考答案：B问题解析：14.单选题设：P：天下大雨,Q：他才乘班车上班.则命题“只有天下大雨,他才乘班车上班.”可符号化为 .A．PQ B．Q PC．Q úP D． Q P答题：已提交参考答案：B问题解析：15.单选题设：P：天下大雨,Q：他才乘班车上班.则命题“除非天下大雨,否则他不乘班车上班.”可符号化为 .A．PQ B．Q PC．Q úP D． P Q答题：已提交参考答案：D问题解析：16.单选题设：P：天下大雨.Q：他乘公共汽车上班.则命题“如果天下大雨,他就乘公共汽车上班.”可符号化为A．P Q B．QP C． P Q D．Q úP答题：已提交参考答案：A问题解析：17.单选题设：P：天气好.Q：他去郊游.则命题“如果天气好,他就去郊游.”可符号化为A．PQ B．Q PC． Q P D．Q úP答题：已提交参考答案：B问题解析：18.单选题 P：下雪路滑,Q：他迟到了.下雪路滑,他迟到了.可符号化为 A．P ú Q B．P QC．P ùQ D．P ù Q答题：已提交参考答案：D问题解析：19.单选题设,p：经一事；q：长一智.在命题逻辑中,命题：“不经一事,不长一智.” 可符号化为：A．pq B．q pC．pq D．pq答题：已提交参考答案：C问题解析：20.单选题下面“”的等价说法中,不正确的为A．p是q的充分条件 B． q是p的必要条件C．q仅当p D．只有q才p答题：已提交参考答案：C问题解析：21.单选题下列式子是合式公式的是A．P ú Q B．P Q ú RC．P Q D．ù Q R答题：已提交参考答案：B问题解析：22.单选题下列式子是合式公式的是A．P ú Q B．P ùQ ú RC．P Q D．ù Q ù R答题：已提交参考答案：B问题解析：23.单选题公式pqùq p与的共同成真赋值为 A．01,10 B．10,01 C．11,00 D．01,11答题：已提交参考答案：A问题解析：24.单选题 p,q都是命题,则pq的真值为假当且仅当A．p为假,q为真 B．p为假,q也为假C．p为真,q也为真 D．p为真,q为假答题：已提交参考答案：D问题解析：25.单选题 n个命题变元组成的命题公式,有种真值情况A．n B．C．D．2n答题：已提交参考答案：C问题解析：26.单选题设A , B 代表任意的命题公式,则德摩根律为A ù BA．A ù B B．A ú BC． A ù B D．AúB答题：已提交参考答案：B问题解析：27.单选题设P , Q 是命题公式,德摩根律为：P ú QA．P ù Q B．P ú QC．P ù Q D．PúQ答题：已提交参考答案：A问题解析：28.单选题命题公式A与B是等值的,是指 .A．A与B有相同的命题变元 B．AB是可满足式C．AB为重言式 D．AB为重言式答题：已提交参考答案：D问题解析：29.单选题设A , B 代表任意的命题公式,则逆反律为A BA． B A B． B AC． A B D． B A答题：已提交参考答案：A问题解析：30.单选题 P为任意合式公式,Q：为重言式.则P ú Q是A．矛盾式 B．可满足式C．蕴含式 D．重言式答题：已提交参考答案：D问题解析：当前页有10题,你已做10题,已提交10题,其中答对8题.A．矛盾式 B．可满足式C．蕴含式 D．重言式答题：已提交参考答案：A问题解析：32.单选题下列式子是永真式A．QPù Q B．P Pù QC．Pù Q P D．PúQ Q答题：已提交参考答案：C问题解析：33.单选题Pù QúT的对偶式是A．Pù QúT B．PúQù TC．PúQù T D．PúQù F答题：已提交参考答案：D问题解析：34.单选题下列命题为假的是A．任意两个不同小项的合取式永假,全体小项的析取式永真B．任意两个不同大项的合取式永假,全体大项的析取式永真C．n个命题变元的矛盾式, 主合取范式有个极大项,而主析取范式为0D．每一个小项当其真值与编码相同时,其真值为真答题：已提交参考答案：B问题解析：35.单选题下列命题为假的是A．P ùP Q的合取范式是Pù QB．P ùP Q的析取范式是Pù QC．P ùP Q的合取范式是P ùPú QD．P ùP Q的析取范式是P ùPú Q答题：已提交参考答案：D问题解析：36.单选题命题P QùP R的主析取范式中包含A．Pù Qù R B．Pù Qù RC．Pù Qù R D．Pù Qù R答题：已提交参考答案：A问题解析：37.单选题给定命题公式,该公式在全功能集中的形式为A．ｐｑr B．ｐｑrC．ｐｑr D．ｐｑr答题：已提交参考答案：A38.单选题设A,C为两个命题公式,当且仅当为一重言式时,称C可由A逻辑地推出.A．A C B．C AC．A ù C D．Aú C答题：已提交参考答案：A问题解析：39.单选题下列推理定律表述不正确的是为A．P Qù Q拒取式推理定律B．P ú Qù Q析取三段论推理定律C．P QùQ R假言三段论推理定律D．P Qù P假言三段论推理定律答题：已提交参考答案：D问题解析：40.单选题下列推理定律, 不正确A．Q P ú Q B． Q QC．QùP Q D． P Q答题：已提交参考答案：C当前页有10题,你已做10题,已提交10题,其中答对8题.41.单选题设Fx：x是人,Gx：x早晨吃米饭.命题“有些人早晨吃米饭”在谓词逻辑中的符号化公式是A．"xFx Gx B．"xFxù GxC．$xFx Gx D．$ xFxù Gx答题：已提交参考答案：D问题解析：42.单选题设Fx：x是火车,Gx：x是汽车,Hx,y：x比y快.命题“某些汽车比所有火车慢”的符号化公式是A．$yGy"xFxùHx,yB．$yGyù"xFxHx,yC．"x $yGyFxùHx,yD．$yGy"xFxHx,y答题：已提交参考答案：B问题解析：43.单选题设Fx：x是火车,Gx：x是汽车,Hx,y：x比y快.命题“说有的火车比所有汽车都快是正确的”的符号化公式是A．$yFy"xGxùHx,yB．$yFyù"xGxHx,yC．"x $yFyGxùHx,yD．$xFxù"y GyHx,y答题：已提交参考答案：D问题解析：44.单选题设Qx：x 是有理数,Rx：x是实数.命题“每一个有理数是实数”在谓词逻辑中的符号化公式是A．"xQx Rx B．"xQxùRxC．$xQx Rx D．$ xQxù Rx答题：已提交参考答案：A问题解析：45.单选题设Sx：x是运动员,Jy：y是教练员,Lx,y：x钦佩y.命题“所有运动员都钦佩一些教练员”的符号化公式是A．"xSxù " yJyù Lx,yB．"x $ySxJy Lx,yC．"xSx $yJyù Lx,yD．$y"xSxJyù Lx,y答题：已提交参考答案：C问题解析：46.单选题设Sx：x是大学生,Ly：y是运动员,Ax,y：x钦佩y.命题“有些大学生不佩服运动员”的符号化公式是A．$xSxù " yLy Ax,yB．"x $ySxLy Ax,yC．"xSx $yLyù Ax,yD．$y"xSxLyù Ax,y答题：已提交参考答案：A问题解析：47.单选题设Cx：x是国家选手,Ly：y是运动员,Ox：x是老的.命题“所有老的国家选手都是运动员”的符号化公式是A．$xCxù Oxù LxB．"xCxù Ox LxC．"xCxù Oxù LxD．$y"xCx Oxù Lx答题：已提交参考答案：B问题解析：48.单选题设Jy：y是教练员,j：金教练,Ox：x是老的,Vy：y是健壮的.命题“金教练既不老,但也不健壮”的符号化公式是A．Jjù Oj VjB．Jjù Ojù VjC．JjOjù VjD．Jjù Oj Vj答题：已提交参考答案：B问题解析：49.单选题设Rx：x是实数,By,x：x大于y.命题“对于每一个实数x,存在一个更大的实数”利用谓词公式翻译这个命题A．"xRx$yRyù By,xB．"xRxù$yRyù By,xC．$xRxù$yRyù By,xD．$ xRx$yRyù By,x答题：已提交参考答案：A问题解析：50.单选题设Lx：x是有限个数的乘积,Nx:x为零,Ex,y：x是y的因子.命题“如果有限个数的乘积为零,那么至少有一个因子等于零”利用谓词公式翻译这个命题A．"xLxùNxù$yEx,yùNxB．"xLxùNx$yEx,yùNxC．$xLxùNx$yEx,yùNxD．$xLxùNxù$yEx,yùNx答题：已提交参考答案：B当前页有10题,你已做10题,已提交10题,其中答对9题.51.单选题下面哪个公式没有自由变元A．"xRx$yRzù By,xB．"xRxù$yRyù By,xC．$xRxù$yRyù Bu,xD．$ xRx$yRyù By,tx答题：已提交参考答案：B问题解析：52.单选题设个体域为整数集,下列真值为真的公式是A．$y"x x y =2 B．"x"yx y =2C．"x$yx y =2 D．$x"yx y =2答题：已提交参考答案：C问题解析：53.单选题设个体域为整数集,下列公式中不是命题A．"x$yx y =1 B．"x"yx y =yC．"x x y =x D．$x"yx y =2答题：已提交参考答案：C问题解析：54.单选题 下面 不是命题A ．"xPxB ．$xPxC ．" x Px,yD ．" x $ yPx,y答题：已提交 参考答案：C问题解析：55.单选题 论域,, , 则下列个公式赋值后肯定为真的是A ．B ．C ．D ．答题：已提交 参考答案：A问题解析：56.单选题 下列式子中正确的是A ．"xPx$xPxB ．"xPx"x PxC ．$xPx$x PxD ．$xPx"x Px答题：已提交 参考答案：D问题解析：57.单选题 下面谓词公式是永真式的是A ．Px QxB ．"xPx$xPxC ．Pa"xPxD ． Pa$xPx答题：已提交参考答案：B问题解析：58.单选题下列式子中正确的是A．"xPx$xPx B．"xPx"x PxC．$xPx$x Px D．$xPx"x Px答题：已提交参考答案：D问题解析：59.单选题请选择$x "yPx,y的前束合取范式为A．" x "yPx,y B．$ x "yPx,yC．" x "yPx,y D．" x $ yPx,y答题：已提交参考答案：D问题解析：60.单选题的前束合取范式为答题：已提交参考答案：D问题解析：当前页有10题,你已做10题,已提交10题,其中答对8题.61.单选题的前束析取范式为答题：已提交参考答案：C问题解析：62.单选题"xPxQx,y$ yPy∧$zQy,z的前束合取范式为A．$xPx∨Qx,y∨$ yPy∧$zQy,zB．$xPx∧Qx,y∨$ uPu∧$zQy,zC．$x$ u$zPx∧Qx,y∨Pu∧Qy,zD．$x$ u$zPx∨Pu∧Qx,y ∨Pu∧Px∨Qy,z∧ Qx,y∨Qy,z答题：已提交参考答案：D问题解析：63.单选题"xPxQx,y$ yPy∧$zQy,z的前束析取范式A．$xPx∨Qx,y∨$ yPy∧$zQy,zB．$xPx∧Qx,y∨$ uPu∧$zQy,zC．$x$ u$zPx∧Qx,y∨Pu∧Qy,zD．$x$ u$zPx∨Pu∧Qx,y ∨Pu∧Px∨Qy,z∧ Qx,y∨Qy,z答题：已提交参考答案：C问题解析：64.单选题,当客体域为 ,公式$x$yLx,y不是有效的A．自然数集B．整数集 C．有理数集 D．实数集答题：已提交参考答案：A问题解析：65.单选题下列推导第步出错$x Px∧Qx$ xPx∧$xQx$ xPx∨$xQx"x Px∨"x Qx"xPx∨Qx"xPxQx,yA．第一步和第二步 B．第一步和第四步C．第二步和第四步 D．第一步和第五步答题：已提交参考答案：B问题解析：66.单选题判断选项错误的是A． B．∈ C．∈{} D{a,b}{a,b,c,{a,b,c}}．答题：已提交参考答案：B问题解析：67.单选题下列命题是真的是A．如果AB及B∈C,则AC B．如果AB及B∈C,则A∈C C．如果A∈B及BC,则AC D．如果A∈B及BC,则A∈C答题：已提交参考答案：D问题解析：68.单选题设S={F,{1},{1,2}},则S的幂集PS有个元素A．3 B．6 C．7 D．8答题：已提交参考答案：D问题解析：69.单选题设A={a,b,c},B={a,b},则下列命题不正确的是A．A－B={a,b} B．A∩B={ a,b }C．AB={c} D．BíA答题：已提交参考答案：A问题解析：70.单选题设S,T,M为任意集合,下列命题正确的是 .A．如果S∪T = S∪M,则T = M B．如果S-T = F,则S = T C．S-T í S D．S S = S答题：已提交参考答案：C问题解析：当前页有10题,你已做10题,已提交10题,其中答对9题.71.单选题设S,T,M为任意集合,S T ={1,2,3},S M={2,3,4},若,则一定有A．B．C．D．答题：已提交参考答案：B问题解析：72.单选题设0,1和0,1分别表示实数集上的闭区间和开区间,则下列命题中为假的是A．0,1í0,1 B．{0,1} íZC．{0,1} í0,1 D．0,1 íQ答题：已提交参考答案：D问题解析：73.单选题设a,b和c,d分别表示实数集上的闭区间和开区间,则0,4 ∩2,6-1,3= A．3,4 B．3,4 C．{3,4} D．0,1 ∪3,6答题：已提交参考答案：A问题解析：74.单选题设A={1,2,3},B={a,b},则A×B=A．{<1,a >,<2,a >,<3,a >,<1,b >,<2,b >,<3,b >}B．{< a ,1 >,< a ,2 >,< a ,3 >,< b, 1 >,< b, 2 >,< b ,3 >} C．{<1,a >,< a, 2 >,<3,a >,<1,b >,<2,b >,<3,b >}D．{< a ,1 >,<2,a >,<3,a >,<1,b >,<2,b >,<3,b >}答题：已提交参考答案：A问题解析：75.单选题设A={0,1},B={1,2},则A×{1}×B= A．{<0,1,1 >,<1,1,1 >,<0,1,2 >,<1,1,2 >} B．{<0,1 >,<1,1 >,<0,2 >,<1,2 >}C．{<1,0, 1 >,<1,1,1 >,<1,0, 2 >,<1,1,2 >} D．{<0,1,1 >,<1,1,1 >,<0,2, 1 >,<1,2,1 >}答题：已提交参考答案：A问题解析：76.单选题下述命题为假的是A．A×B∩C=A×B∩A×CB．A×B∪C=A×B∪A×CC．B∪C×A=B×A∪C×AD．A×B×C=A×B×C答题：已提交参考答案：D问题解析：77.单选题设R是X到Y上的关系,则一定有A．domRíX, ranRíY B．domR=X, ranRíYC．domR=X, ranR=Y D．FLD R=domR∪ranR=X∪Y答题：已提交参考答案：A问题解析：78.单选题设到的关系为,则domR和ranR为A．和B．和C．和D．和答题：已提交参考答案：C问题解析：79.单选题设,则的恒等关系为A．B．C．D．答题：已提交参考答案：D问题解析：80.单选题设A为非空集合,则A上的空关系不具有A．反自反性 B．自反性 C．对称性 D．传递性答题：已提交参考答案：B问题解析：当前页有10题,你已做10题,已提交10题,其中答对10题.81.单选题 A．R在A上反自反B．R在A上反对称C．R在A上对称D．R在A上传递答题：已提交参考答案：C问题解析：82.单选题下述说法不正确的是A．关系矩阵主对角线元素全是1,则该关系具有自反性质B．关系矩阵主对角线元素全是0,则该关系具有反自反性质C．关系矩阵是对称阵,则该关系具有对称性质D．关系矩阵主对角线元素有些是0,则该关系具有反自反性质答题：已提交参考答案：D问题解析：83.单选题下述说法不正确的是A．关系图每个顶点都有环,则该关系具有自反性质B．关系图每个顶点都没有环,则该关系具有反自反性质C．关系图没有单向边,则该关系具有对称性质D．关系图有些单向边,则该关系具有反对称性质答题：已提交参考答案：D问题解析：84.单选题设 A = {a, b, c},要使关系{<a, b>, <b, c>, <c,c>, <b, a>}∪R 具有对称性,则A．R = {<c, a>} B．R = {<c, b>}C．R = { <b, a>} D．R = { <a, c>}答题：已提交参考答案：B问题解析：85.单选题 A = {a, b, c},要使关系{<a, b>, <b, c>, <c, a>, <b, a>}∪R 具有对称性,则A．R = {<c, a>, <a, c>} B．R = {<c, b>, <b, a>}C．R = {<c, a>, <b, a>} D．R = {<c, b>, <a, c>}答题：已提交参考答案：D问题解析：86.单选题 A = {a, b, c, d}, A 上的关系R = {<a, b>, <b, a>, <b, c>, <c, d>},则它的对称闭包为A．R = {<a, a>, <a, b>, <b, b>, <b, a>, <b, c>, <c, c>, <c, d>}B ．R = {<a, b>, <b, a>, <b, c>, <c, b>, <c, d>}C ．R = {<a, b>, <b, a>, <b, c>, <c, d>, <c, b>, <d, c>}D ．R = {<a, a>, <a, b>, <b, a>, <b, c>, <c, d>, <d, c>}答题：已提交参考答案：C问题解析：87.单选题 下列关系运算原有五个性质保留情况的说法错误的是A ．逆关系与关系的交保持全部五个性质不变B ．关系的并不保持反对称性和传递的C ．关系的差不保持自反性和传递性D ．复合关系仅仅不保持自反性答题：已提交 参考答案：D问题解析：88.单选题 设R 为定义在集合A 上的一个关系,若R 是 ,则R 为偏序关系 .A ．反自反的,对称的和传递的B ．自反的,对称的和传递的C ．自反的,反对称的和传递的D ．对称的,反对称的和传递的答题：已提交 参考答案：C问题解析：89.单选题 设R1和R2是集合X 上的任意关系,则下列命题为真的是A ．若R1和R2是反自反的,则也是反自反的B ．若R1和R2是自反的,则也是自反的 C ．若R1和R2是传递的,则也是传递的 D ．若R1和R2是对称的,则也是对称的答题：已提交 参考答案：B 问题解析： 90.单选题 对于集合{1, 2, 3, 4}上的关系是偏序关系的是A ．R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,3>,<2,4>,<3,3>,<3,4>,<4,4>}B ．R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<2,4>,<3,1>,<3,4>,<4,4>}C ．R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<3,1>,<3,3>,<4,1>,<4,4>}D ．R={<2,1>,<1,2>,<1,3>,<1,4>,<2,2>, <4,3>,<2,4>,<3,3>,<3,4>,<4,4>}答题：已提交参考答案：A问题解析：当前页有10题,你已做10题,已提交10题,其中答对8题.91.单选题 已知偏序集A,,其中A={a,b,c,d,e},“”为{a,b,a,c,a,d,c,e,b,e,d,e,a,e}∪IA .则如下的表述中 是错的.A ．极大元为e, 极小元aB ．最大元e,最小元aC ．极大元为a, 极小元eD ．最大元b,最小元a答题：已提交 参考答案：D问题解析：92.单选题设R是集合A = {1, 2, 3, 4, 6, 9,24,54}上的整除关系.则如下的表述中是错的.A．极大元为24,54 B．最大元54C．集合B= { 4, 6, 9}没有上确界 D．集合B= { 4, 6, 9}有下确界答题：已提交参考答案：B问题解析：93.单选题下列说法错误的是A．有穷偏序集一定存在极大元值和极小元,但不一定存在最大元B．极大元可能存在多个,但最大值如果存在,一定唯一C．孤立点不存在极大元和极小元D．最大元一定是最小上界,最小元一定是最大下界,反之不对.答题：已提交参考答案：C问题解析：94.单选题设为偏序集,B是A的子集.则如下命题为假的是A．B的极大元B．R的极小元C．R的最大元D．R的下界,下确界是下界中的最大元.答题：已提交参考答案：D问题解析：95.单选题对于集合{1, 2, 3},下列关系中不等价的是A．R={<1,1>,<2,2>, <3,3>}B．R={<1,1>,<2,2>,<3,3>,<1,4>}C．R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}D．R={<1,1>,<2,2>,<1,2>,<2,1>,<1,3>, <3,1>,,<3,3>,<2,3>,<3,2>}答题：已提交参考答案：B问题解析：96.单选题设R为定义在集合A上的一个关系,若R是 ,则R为等价关系 . A．反自反的,对称的和传递的 B．自反的,对称的和传递的C．自反的,反对称的和传递的 D．对称的,反对称的和传递的答题：已提交参考答案：B问题解析：97.单选题设R1和R2是非空集合X上的等价关系,则下列为等价关系的是A．B．C．D．答题：已提交参考答案：D问题解析：98.单选题设R为定义在集合A上的一个关系,若R是 ,则R为相容关系 .A．反自反的,对称的和传递的 B．自反的,对称的C．自反的,反对称的和传递的 D．对称的,反对称的和传递的答题：已提交参考答案：B问题解析：99.单选题在集合族上的等势关系是A．偏序关系 B．拟序关系 C．全序关系 D．等价关系答题：已提交参考答案：D问题解析：100.单选题在集合A为一个划分,则A的元素间的关系是A．偏序关系 B．拟序关系 C．全序关系 D．等价关系答题：已提交参考答案：D问题解析：答题：已提交参考答案：B问题解析：102.单选题设A={1,2,3,4,5, 6},B={a,b,c,d,e},以下哪个函数是从A到B的满射函数A．F ={<1,b>,<2,a>,<3,c>,<1,d>,<5,e>, <6,e>}B．F={<1,c>,<2,a>,<3,b>,<4,e>,<5,d>, <6,e>}C．F ={<1,b>,<2,a>,<3,d>,<4,a>, <6,e>}D．F={<1,e>,<2,a>,<3,b>,<4,c>,<5,e>, <6,e>}答题：已提交参考答案：B问题解析：103.单选题设A={1,2,3,4,5},B={a,b,c,d,e,f},以下哪个函数是从A到B的入射函数A．F ={<1,b>,<2,a>,<3,c>,<1,d>,<5,e>}B．F={<1,c>,<2,a>,<3,b>,<4,e>,<5,d>}C．F ={<1,b>,<2,a>,<3,d>,<4,a>}D．F={<1,e>,<2,a>,<3,b>,<4,c>,<5,e>}答题：已提交参考答案：B问题解析：104.单选题设A={1,2,3,4,5},B={a,b,c,d,e},以下哪个函数是从A到B的双射函数A．F ={<1,b>,<2,a>,<3,c>,<1,d>,<5,e>}B．F={<1,c>,<2,a>,<3,b>,<4,e>,<5,d>}C．F ={<1,b>,<2,a>,<3,d>,<4,a>}D．F={<1,e>,<2,a>,<3,b>,<4,c>,<5,e>}答题：已提交参考答案：B问题解析：105.单选题设B ={1,2}, A={a,b,c},则从A到B的函数个数为A．5 B．8 C．6 D．32答题：已提交参考答案：B问题解析：106.单选题 52张扑克牌分配给四个比赛者,则从扑克牌的集合到比赛者集合的函数为A．单射函数 B．双射函数 C．满射函数 D．仅为映射不是函数答题：已提交参考答案：C问题解析：107.单选题下列说法不对的是 A．简单图不含平行边和环B．每个图中,度数为奇数的节点数为偶数C．有向图中节点的入度等于出度D．完全图的边数为参考答案：C问题解析：108.单选题设G是n有个结点,m条边的简单有向图.若G是连通的,则的下界是A．n B．n-1 C．nn-1 D．答题：已提交参考答案：B问题解析：109.单选题下列说法不对的是A．每个图中节点的度数之和等于边数的两倍B．有向图的所有节点入度之和等于所有节点的出度之和C．每一个环,度数增加2D．一个图的图形表示是唯一的答题：已提交参考答案：D问题解析：110.单选题下列说法不对的是A．两个图同构要求他们的节点和边分别存在一一对应的关系,且保持关联B．图同构的充分条件是节点数目相同、边数相等,度数相同的节点数相等C．补图是相对同阶完全图而言的图,阶数一样但变为补充进来的新边.D．一个完全图的任何两个顶点都有边连接参考答案：B问题解析：当前页有10题,你已做10题,已提交10题,其中答对9题.111.单选题下列说法不对的是A．零图含零个节点B．边数为零的图为零图C．平凡图只有一个节点D．环或自回路可以作为有向边,也可以作为无向边答题：已提交参考答案：A问题解析：112.单选题下列各图是简单图的是 .答题：已提交参考答案：C问题解析：113.单选题设无向图G有12条边,已知G中3度顶点有6个,其余顶点的度数都小于3,则该图至少有个顶点.A．6 B．8 C．9 D．12答题：已提交参考答案：C问题解析：114.单选题设阶图G中有条边,每个结点的度不是就是.若G中有个度结点,个度结点,则=A．B．C．D．答题：已提交参考答案：C问题解析：115.单选题称图G′=<V′,E′>为图G = <V,E>的生成子图是指A．V′í V B．V′í V且E′í EC．V′= V且E′í E D．V′ì V且E′ì E答题：已提交参考答案：C问题解析：116.单选题下列说法不对的是A．路是各边首尾相连的通道,可由节点与边来交替表达B．迹是没有重边的路C．通路除首尾节点以外不会有重复的节点D．圈是通路,有很多重复的节点答题：已提交参考答案：D问题解析：117.单选题下列说法不对的是A．不连通图得连通度为0B．存在割点的连通图的连通度为1C．个节点的图,若存在路则一定存在长度少于的路D．完全图的连通度为答题：已提交参考答案：C问题解析：118.单选题下列四个有6个结点的图是连通图.答题：已提交参考答案：C问题解析：119.单选题下列说法不对的是A．零图的矩阵表示为零矩阵B．个节点的连通图的完全关联矩阵的秩为C．无向简单图的邻接矩阵图是对称的,连通矩阵也是对称的D．有向简单图的邻接矩阵图也是对称的答题：已提交参考答案：D问题解析：120.单选题下列说法不对的是A．强分图可能是一个孤立点B．强连通图当且仅当有一条至少包含每一个节点一次的通路 C．图的可达性不是等价关系D．图的最小度不少于边连通度,边连通度不少于点连通度答题：已提交参考答案：B问题解析：答题：D．当且仅当简单图的闭包是汉密顿图时,这个简单图是汉密顿图答题：已提交参考答案：A问题解析：123.单选题下列说法不对的是A．无向图为欧拉路则其奇数度节点可以是一个B．一个图是欧拉图当且仅当它连通且均为偶数度节点C．当一个图每一对节点的度数之和都大于或等于节点数减一,就有汉密尔顿路D．若一个图,G含有汉密尔顿路,则答题：已提交参考答案：A问题解析：124.单选题下列为欧拉图的是A B C D答题：已提交参考答案：D问题解析：125.单选题在下列关于图论的命题中,为真的命题是A．完全二部图Kn, m n 31, m 31是欧拉图B．欧拉图一定是哈密尔顿图C．无向完全图Knn33都是欧拉图D．无向完全图Knn33都是哈密尔顿图答题：已提交参考答案：D问题解析：126.单选题在下列关于图论的命题中,为假的命题是A．完全二部图Kn, m n , m为非零正偶数是欧拉图B．哈密尔顿图一定是欧拉图C．有向完全图Knn32都是欧拉图D．无向完全图Knn33且为奇数都是欧拉图答题：已提交参考答案：B问题解析：127.单选题在下列关于图论的命题中,为假的命题是A．n =m且大于1时,完全二部图Kn, m 是哈密尔顿图B．强连通的有向图都是哈密尔顿图C．完全二部图Kn, m n , m为非零正偶数的欧拉回路含mn条边D．无向完全图n32至少加n条边才能成为欧拉图答题：已提交参考答案：B问题解析：128.单选题下列说法不对的是 A．一个有限平面图的次数之和等于边数的两倍B．平面图G的节点数为v,面数为r,边数为e,则有v-e+r=2C．G是一个v个节点,e 条边的连通简单平面图,则答题：已提交参考答案：B问题解析：129.单选题 D．一个图是平面图,当且仅当他不含有与或在2度节点内同构子图下列各图为平面图的是答题：已提交参考答案：C问题解析：130.单选题设G为任意的连通的平面图,且G有n个顶点,m条边,r个面,则平面图的欧拉公式为A．n m + r = 2 B．m n + r = 2C．n + m r =2 D．r + n + m = 2答题：已提交参考答案：A问题解析：当前页有10题,你已做10题,已提交10题,其中答对9题.131.单选题下列不能作为一棵树的度数列的一组数是A．1,1,2,2,3,3,4,4 B．1,1,1,1,2,2,3,3C．1,1,1,2,2,2,2,3 D．1,1,1,1,2,2,2,3,3答题：已提交参考答案：A问题解析：132.单选题在下列关于图论的命题中,为假的命题是A．6阶连通无向图至少有6棵生成树B．n阶m条边的无向连通图,对应它的生成树,至少有m-n+1条基本回路C．高为h的正则二叉树至少有h+1片树叶D．波兰符号法的运算规则是每个运算符与它前面紧邻的两个数进行运算答题：已提交参考答案：D问题解析：133.单选题下列四个图中与其余三个图不同构的图是A B C D答题：已提交参考答案：C问题解析：134.单选题给定无孤立点无向图G的边集：{1,2,1,3,2,3,2,4,2,5,3,4,3,5},找出图G的一棵生成树为。

一、简要回答下列问题：（每小题3分，共30分）1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)x∈(AUB)UC，即 x∈AUB 或 x∈C即 x∈A 或 x∈B 或 x∈C 即 x∈A 或 x∈B∪C即 x∈AU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？答：不同的对称关系有：8种R = ΦR = {<1,1>}R = {<2,2>}R = {<1,1>,<2,2>}R = {<1,2>,<2,1>}R = {<1,1>,<1,2>,<2,1>}R = {<1,2>,<2,1>,<2,2>}R = {<1,1>,<1,2>,<2,1>,<2,2>}4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。

答：m0= ┐p∧┐q∧┐r m4= p∧┐q∧┐r6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。

如〈I，+〉是交换群。

8．什么是群中右模H合同关系？答：设G是群，H是G的子群，a,b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），记为a≡b（右mod H）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

离散数学 习题 参考答案2、构造公式¬(p ∨q)与¬p ∧¬q 的真值表。

3、构造公式 p 、p ∧p 、p ∨p 的真值表。

4、构造公式 p ∨(q ∧r)、(p ∨q)∧(p ∨r)的真值表。

5、构造公式 p ∨(p ∧r)、p 的真值表。

6、构造公式 p ∧(p ∨r)、p 的真值表。

7、构造公式 p↔q 、¬q↔¬p 的真值表。

8、构造公式(p→q)∧(p→¬q)、¬p 的真值表。

9、构造公式 p 、¬¬p 的真值表。

10、构造公式 p ∨¬p 、p ∧¬p 的真值表 略一、分别用等算演算与真值表法，判断下列公式是否存在主析取范式或主合取范式，若有，请写出来。

(1)(¬p→q)→(¬q ∨p) (2)(¬p→q)→(q ∧r)(3)(p ∨(q ∧r))→(p ∨q ∨r) (4) ¬(q→¬p)∧¬p (5)(p ∧q)∨(¬p ∨r) (6)(p→(p ∨q))∨r (7)(p ∧q)∨r(8) (p→q)∧(q→r) (9) (p ∧q)→q(10) ¬(r↔p)∧p ∧q存在主析取范式=成真赋值对应的小项的析取 =m 00∨m 10∨m 11=(¬p ∧¬q)∨(p ∧¬q)∨(p ∧q)主析取范式=成假赋值对应的大项的合取 =M 01=p ∨¬q等值演算：(¬p→q)→(¬q ∨p) ⇔¬ (¬¬p ∨q)∨(p ∨¬q) ⇔¬ (p ∨q)∨(p ∨¬q) ⇔ (¬p ∧¬q)∨(p ∨¬q) ⇔ (¬p ∨(p ∨¬q))∧(¬q ∨(p ∨¬q)) ⇔ (¬p ∨p ∨¬q)∧(¬q ∨p ∨¬q) ⇔ (1∨¬q)∧(p ∨¬q) ⇔ (p ∨¬q)这是大项，故为大项的合取，称为主合取范式(¬p→q)→(¬q ∨p) ⇔ (p ∨¬q) ⇔ (p)∨(¬q) ⇔ (p ∧1)∨( 1∧¬q) ⇔ (p ∧(q ∨¬q))∨( (p ∨¬p)∧¬q) ⇔ (p ∧q)∨ (p ∧¬q)∨(p ∧¬q)∨(¬p ∧¬q) ⇔ (p ∧q)∨ (p ∧¬q)∨(¬p ∧¬q)因为一个公式的值不是真，就是假，因此当我们得到一个公的取值为真的情况时，剩下的组合是取值为假， 因此当得到小项的析取组成的主析取范式后，可以针对剩下的组合写出主合取范式。