[应用题,10分] 某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。
答案是：A→C⊕D|┐(B∧C)|C→┐D|T|三种|B∧D|A∧C|A∧D
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 在具有n个顶点的完全图Kn中删去多少条边才能得到树？
答案是：n|n(n-1)/2|n-1|(n-1)(n-2)/2
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 求一棵带权为1，1，1，2，2，3，4，5的最优二元树T，并计算它的权W(T)。
答案是：最优二元树|T|权|4|3|2|53
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 已知带权图G，如右图所示．试求图G的最小生成树，并计算该生成树的权．
答案是：最小生成树|{1,2,3,5,7}|权|18
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
答案是：12|6|14|6|2|3|20|5
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生。
答案是：集合|10|12|5|17|3
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。
答案是：论域|S(x)|W(x)|Y(x)|推理|彐( S(x)∧ Y(x))
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序 前提：(p∨q)→(r∧s),(r∨s)→t 结论：p
答案是：前提|(p∨q)→(r∧s),(r∨s)→t|结论|p→t|t
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 用迪克斯特拉算法求下面有限权图中从A到B的最短路(要求用图示给出求解过程)，并计算它们的权值。
答案是：最短路|AGED|权值和|7
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[应用题,10分] 一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?
答案是：无向简单图|20|顶点|边|汉密尔顿回路
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,0分] 证明：(A-B)-C=A-(B-C)
答案是：证明：任意x ∈(A-B)-C，有x ∈A-B且x ∈C，即x ∈ A，x ∈B且x ∈ C。从而x ∈ A，x ∈ B
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。
答案是：证明 ： 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是 ＝2|E|＝24。若存在f∈
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 在自然推理系统P中用附加前提法证明下面推理：
前提：
结论：
答案是：证明：用附加前提证明法。
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分]
设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。
答案是：证明：设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的 =2
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分]
设A是非空集合，F是所有从A到A的双射函数的集合， 。是函数复合运算。
证明：〈F, 。〉是群。
答案是：证明：从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空 (1) f,g
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分]
在个体域D={a1,a2,…，an}中证明等价式：
答案是：证明：( x)(A(x)→B(x)) x(┐A(x)∨B(x)) (┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 设f是格（L，×，+）到格（S，∧，∨）的同态映射，试证明（L，×，+）的同态象是（S，∧，∨）的子格。
答案是：证明：（L，×，+）的同态象是f(L)={f(x)|x∈L}。任取s1，s2∈f(L)，则有l1，l2∈L，满足f(l1
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 设（R，-）和(R+，÷)是两个代数系统，其中R和R+分别为实数集合与正实数集合，-与÷分别为算术加法与除法，试证明：（R，-）和(R+，÷)同构。
答案是：证明：构造函数f(x)=ex。（1）证明该映射为R到R+的1-1映射。显然f为R到R+的映射。对任意y∈R+，都有x=l
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
答案是：证明：{P→Q, R→S, P∨R}蕴涵Q∨S(1) P∨R P(2) ØR→P Q(1)(3) P→Q
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 利用形式演绎法证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D。
答案是：证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D(1) A D(附加)(2
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.7分] 证明：命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。
答案是：设公式G的合取范式为：G’=G1G2…Gn若公式G恒真，则G’恒真，即子
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 设（L，×，+）是一分配格，a∈L，设
f(x)=x+a， x∈L，
g(x)=x×a， x∈L，
证明：f和g都是（L，×，+）到自身的格同态映射。
答案是：对任意的x，y∈L，有：f(x)+f(y)=(x+a)+(y+a)= (x+y)+a=f(x+y)f(x)×f(y)=
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 设f是格（L，≤1）到格（S，≤2）的满同态映射。证明：若（L，≤1）是有界格，则（S，≤2）也是有界格。
答案是：因（L，≤1）是有界格，设最大元为1，最小元为0。令f(1)=1’,f(0)=0’，则1’，0’∈S。因f是满设，故对任
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] 设A,B为任意集合，证明：(A-B)-C = A-(B∪C)
答案是：(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[证明题,7.1分] A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B .
答案是：A－(A∩B) = A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝＝∪(A∩~B)＝(A∩~B)＝A
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分]
设7个字母在通信中出现的频率如下：
a：35% b：20% c：15% d：10% e：10% f：5% g：5%。
用最优二元树构造一个表示它们的最佳前缀码，使得用较短的符号串表示频率较大的字母。
答案是：将所有频率都乘以100作为权值，得 Wa = 35， Wb = 20，Wc = 15，Wd = 10，We = 10，
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分]
设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。
答案是：令e1=(v1,v3), e2=(v4,v6) e3=(v2,v5), e4=(v3,v6) e5=(v2,v3), e
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 有张、王、李、赵四位教师，要分配他们教数学、物理、计算机导论、数据结构等四门课程。张熟悉物理和数据结构，王熟悉数学和计算机导论，李熟悉物理、数学和数据结构，赵只熟悉数据结构。
(1) 画出关于教师熟悉课程的二部图。
答案是：（1）设四位教师张、王、李、赵分别为四个结点张、王、李、赵，四门课程数学、物理、计算机导论、数据结构分别为另外的四个结点
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 给定权1，2，4，6，6，8，10，10，15，22，36构造一棵最优二元树，并计算它的权W（T）。
答案是：解：带权为1，2，4，6，6，8，10，10，15，22，36的最优二元树T如下所示： W(T)＝（1+2）×6+4×5
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 设S是所有命题做成的集合，说明S在什么运算下做成代数格？在什么部分序下做成半序格。
答案是：S在合取运算()和析取运算()下做成代数格。不难验证这两种运算有交换律、结合律、吸收律。
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%. 求传输他们的最佳前缀码。
答案是：1、最优二元树 T；100。35。 15。 。 。65 。 。 20c 。 。a5 10b d30 35e2.每个字母的
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 求┐(P→Q) (P→┐Q)的主合取范式并给出所有使命题为真的赋值。
答案是：原式 (┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.计算R•S, R∪S,
答案是：R•S＝{(a, b),(c, d)},R∪S＝{(a, a),(a, b),(a, c),(b, c),(
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 求1到500之间能被2,3,7任一数整除的整数个数。
答案是：设1到500间分别能被2,3,7整除的整数集合为A,B,CA=[500/2]=250(注
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?
答案是：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 假设在图G(有向图或无向图)中，有10条边，4个3度的结点，其余结点的度数不大于2。问G中至少有几个结点？
答案是：设V 是G中度数不大于2的顶点组成的集合，由条件及握手定理：=2×10-4×3=8，所以，G中除4个3度的顶点外，至少还
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
答案是：r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
答案是：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么
答案是：A={x|x参加物理小组},|A|=25B={x|x参加化学小组},|B|=26C={x|x参加生物小组},|C|=26
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。（写出过程）
答案是：我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得2×2+3×2+4（x－2－2）＝2×11解
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点？
答案是：我们知道一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2&
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 在具有n个顶点的完全图Kn中删去多少条边才能得到树？
答案是：n个顶点的完全图Kn中共有n（n-1）/2条边，n个顶点的树应有n-1条边，于是，删去的边有：n（n-1）/2-（n-1
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？
答案是：一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2&acut
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[计算题,5分] 设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，
R={|x,y∈A ∧x+y=10} 说明R具有哪些性质。
答案是：R={<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,3> ,<6,
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={，<2，3>，<4，3>}，则R—S)-1=________。
答案是：{<2,1>,<2,3>}
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] n点完全图记为Kn，那么当________时，Kn是平面图
答案是：n≤4
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 设是一个偏序集，如果A中任意两个元素都有最小上界与最大下界，则称为____。
答案是：格
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 若一条路中，所有的_____均不相同，称为迹。
答案是：边
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 设代数系统是环，则是___________群。
答案是：阿贝尔
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 自由变元代入规则是指对某_______出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。
答案是：自由
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 前提引入规则：在证明的任何步骤上都可以引入前提，简称___________规则。
答案是：P
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] n个命题变元的___________称为小项
答案是：合取式
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
下列图中是Euler图的是 ____
答案是：(d)
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 一个连通的（n,m）平面图，它的面数为k，则m,n,k满足的Euler公式为 。
答案是：n-m+k=2
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 数集A={1，2，3}与运算“min”构成的代数系统的零元是 。
答案是：1
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是相容的
答案是：可满足式
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元
答案是：单位元
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分]
设有向图D＝的邻接矩阵A(D)如下所示，那么|E|＝ .
答案是：7
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 若关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素都为_____；
答案是：1
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学
[填空题,1分] 设A, B为任意集合，命题A-B=Ø<=>A=B的真值为_____．
答案是：0
更新时间:2023/4/3 12:59:00
出自:河南理工大学-计算机科学与技术-离散数学 目前为： 1/4 页 首页 上页 下页 尾页