离散数学题库

试题总汇数理逻辑部分、判断下列句子中哪些是命题素数血是黑色的明年10月是晴天被2整这朵花多好看呀！明天下午有会吗？请关上门！X+y>5地球外的星球上也有人、将下列命题符号化是偶数素数和偶数李芳学过英语或日语如果角A和B是对顶角，则角A等角B（5李平虽然聪明，但不用功李平不但聪明，而且用功小王是游泳冠军或者百米赛跑冠军小王现在在宿舍或者在图书馆选小王或者小李中的一人当班长如果我上街，我就去书店看看，除非我很累（）如果明天天气好，我们去郊游。否则，不去郊游（）你爱我，我就嫁给你、判断下列命题公式是否等值

（∨）（∨）

p∨p∧

qq、验证下列等值式→（q→）（p∧）→（p∧）∨（∧）、用等值演算法解决下面问题：A、B、、D人米竞赛。观众甲、乙、丙预报比赛的名次为，（1甲C一B第）乙C第D第）A第，第。比赛结束后发现甲、乙、丙每人报告的情况都是给对一半。试问，实际名次如何？、求下面命题公式的主析取范式和主合取范式（1p∨）→）→、利用真值表求主析取范式和主合取范式（1∧q）∨r、逻辑推理证明（1前提→r，→，∨。论r∨。（2前提p∨qp→，→t，→，。结论（3前提p→（→r→p。结论：→r。（4前提p→（

（r∧）

，

s。结论：

、给定语句如下：是素数能被2除，是数你下午有会吗？2x+3>0素数或是合数这个男孩真勇敢呀！如果，则5是数只有4是偶数，3才被2除明年5月1日是晴天圆的面积等于半径的平方与的乘积以上10个句中，是简单命题的为A是复合命题的为B，是真命题为C，是假命题的为D，真值待定（真值客观存在只是现在不知道）的命题为E：①（1：①（）②（2：①（27（（）：①（11：①（②9）③10判断公式类型（1∧q）→（∨）（2

）

→）∧（q）（3

（p→）∧q（∧）→（p∨）（p∨）→（q∧q）∧）（7→q）→）

（8∧q）∨（∧

）（9

（∨q∨）

（

∧

q

）（∧q）r11、定命题公式如下→）→（∨q该命题公式的主析取范式中含极小项的个数为，主合取范式中含极大项的个数为B，成真赋值个数为C，成假赋值个数为DA、、、）（）1,(3)2,(4)3,(5)412、公安人员审查一件盗窃案已知的事实如下：甲或乙盗窃了录音机若甲盗窃了录音机，则作案时间不能发生在午夜前若乙的证词正确，则午夜时屋里灯光未灭若乙的证词不正确，则作案时间发生在午夜前午夜时屋里灯光灭了推理证明，谁盗窃了录音机。nn13、p=1，q=0，，，下列命题公式（∧）→（∧）（∧

∧r∧

s）∨→

q（∧∧r）

（

∨

s）那么）真值为）真值为）真值为；14对于下面的语句，只要4＜，就有3＞只要4＜，就有3≤只有4＜，才有3＞只有4＜，才有3≤除非4＜，否则3＞4≥仅当3≤4＜当且当3＞则，他们的真值是（）（2）（）（）（5（6（）。15设A是n命题变项的公式，下面4个结论中，哪个是错误的？（1若A的析取范式中含2

n

个极小项，则A是重言式若A的合取范式中含2个大项，则A是矛盾式若A的析取范式中不含任何极小项，则A主析取范式为若A的合取范式中不含任何极大项，则A主合取范式为16已知命题公式A含有3个题变项其成真赋值为000，，，。则A的析取范式为，合取范式为。17判断下列语句是否为命题，如是命题请指出是简单命题还是复合命题，并讨论真值（1是理数被2整现在开会吗？＞0这朵花真好看呀！素数当且仅当三角形有3边血是黑色的当且仅当太阳从东方升起年月1日天气晴朗太阳系以外的星球上有生物小李在宿舍里全体起立2的倍数或是3的数偶数且是奇数李明与王华是同学蓝色和黄色可以调配成绿色18将下列命题符号化，并讨论其真值如果今天是号，则明天是2号如果今天是号，则明天是3号19设AB、为意的命题公式（1已知A∨

B∨，

B吗已知A∧B∧，B吗？已知B问B吗？20设一个符合如下要求的室内照明控制线路房的门外门及床头分别装有控制同一个电灯的个关A、C。当且仅当一个开关的键向上或3个关的键都向上时电灯亮。则F逻辑关系式可化简为。（1∨∨（2A∨∨∨（A∧B）（）∨∨（AC（4）C∨（∧）21将下列语句用谓词表达式符号化素数且是偶数如果2大于3，则2大于凡是有理数均可表成分数有的有理数是整数没有不吃饭的人素数不全是奇数一切人都不一样高有的自然数无先驱数有些人喜欢所有的花任何金属都可以溶解在某种液体中凡是对顶角都相等22指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现（1（F（x）→

yH（x，yF（x）∧（x，y）xy（R（，）∨L（x，y∧Hx，y）23给定解释I下：），3}I）中特定元素I函数f）为f），f3）=2谓词（x）为F2）=0，F（3；（x，y）为（ij）=1，i，j=2，；Lx，y为L22）L（3，）=1；L（23=L3，）=0在解释I下求下列各式的值。（1（F（x）∧（x，（2

x（（fx）∧（，f））（3

yLx，）24求下列公式的前束范式（1（x）∧G）（2（x）∨G）（3（x）→G）（4

xF（x）→G（x）25设（x是Gx爱糖。有人给出语句“不是所有人都爱吃糖”的谓词表达式：x（（x）∧G（x）x（（x）→G（x）（3

x（（x）∧Gx）（4F（x）∧G（x）正确的答案是。26给出解释I，使下面两个公式在释I下为假，从而说明这两个公式都不是永真式（1（F（x）∨Gx）→（（x）∨（x）（2

xF（x）∧

xG（x）→

x（（x）∧Gx）27取个体域为整数集，给定下列公式（1（2

y（x*y=0）y（x*y=1）（3（x*y=2（4x–=）（5x–yy+x（6xy（x*y=y）（7（x*y=x）（8

xy（x+y=2y）在上面的公式中，真命题的为A，假命题的为B。A①1③（1B①③（1集合部分、下列命题（1正确的是；误的是。、计算一下幂集（1）（

、证明（1）∪B=A∪、化简ABC）∩（A∪B）-（A（）∩A已知：AC，证明A=B求在到1000之不能被5和6也不能被8整的数的个数某班有个学生，其中人打篮球，12会打排球人会打篮球和排球5人打篮球和网球还2人打三种球而个会打网球的人都会打另一种指球或排球不会打这三种球的人数。设表一年级大学生的集合表二年级大学生的集合表示计算机科学系学生的集合M表数学系学生的集合T表示选修离散数学的学生的集合L表爱好文学的学生的集合表爱好体运动的学生的集合列各句子所对应的集合表达式分别是：（1所有计算机科学系二年级的学生都选修离散数学A数学系的学生或者爱好文学或者爱好体育运动B数学系一年级的学生都没有选修离散数学只有一、二年级的学生才爱好体育运动D除去数学系和计算机科学系二年级的学生外都不选修离散数学A、B、、D：①M∪）∩；②R∩ST；③（∩）∩T=④M∪；⑤F∪；-（∪R）、设S1=｛12，…，，9｛2，4，，S3=｛，3，7，9｛3，，5｛3定在以下条件下X可与S1,中哪个集合相等（1若X∩S5=

，则A（2若XX∩S2=则B（3若XX，则（4若X-S3=

，则D（5若X

但X

，A、B、、D：①或S3②X=或者；X=S1，S2或；④X与其中何集合都不等；X=S2⑥；X=S3或；⑧或S410设ABC任意集合，判断下述命题是否恒真，如果恒真给出证明，否则举出反例。（1）A∪

AB=AB=A（C）（AB-（∩C（AB）∪（BA）B、设AB为合，试确定下列各式立的充分必要条件：（1）A=BA=B-AAB=AB12求使得以下集合等式成立时，，，c，d应该满足的条件：（1，｝｛，，｝｛，b，｝=｛a，｝｛，｝=｛a，b｛b｝｛a，13计算A∩BAB、、A

B，bB=，d｝A={{a{b}}cb｝}｛a，（3）｛x|x∈∧B=｛x∈∧≥｝｛x|x∈∧x<1｛|x∈∧｝｛x|x∈∧x<0｛|x∈∧≥｝-1-114设A|，P（A）|，P（A∪）=256，求：||A∩B，A-B，AB设｛，：P（A）×设A、B、、D为意集合，判断以下等式是否成立，若成立给与证明，否则，举出反例。（AB）×C∩D=（A∩C）×（B∩D）（AB）×C∪D=（A∪C）×（B∪D）（A-）×）A-）×（D（AB）×C=AC）×BD17设、G是N上关系，其定义为：F=<x，y>|x，y∈N∧=x｛<x，y>x，∈∧y=x+1求：G、

GG

F、↑，2｛，2]设F=>，｛F，↑｛a｝]。设A=｛a，b，R=<a，b>，<b，，<bc>，<c，出R、（R（（）关系图。设｛，，3出A上所有的等价关系设｛，，3，，11，12为A上整除关系，画出哈斯图。画，，c哈斯图。RX上二元关，对于x∈义集合：（）={y|xRy}显然R（）。果X={-4，-3-2，-101，，，4}且令｛，y>，∈∧<y｛，y>，∈∧-1<<｛，y>，∈∧≤y则下列集合满足R1）=AR2）=BR3）R1）=DR2-1）A、B、、D：①；｛，-3-2，｛，-1｛，0，⑤｛，｛1，23，，｛0，2，⑨｛，2，34以上结果都不对24设｛1，，3义S×上等价关系，

<a，b><c，∈有<a，b><c，d>

a+d=b+c则由产了S×S的一个划分。在该划分中共有A个划分块，其中最大的块有B个素，并且含有元素C。小的划分块有有E个元素。A、B、D、：①1②；③3；④4；⑤；⑥；⑦9C：

块，每块含+2++++2+++⑧1⑨，；⑩<2，2>25设｛0，1是中字符构成的长度不超过的串的集合，即F=

，0，1，，01…，1111中

表示空串。在F上义偏序关系R

x，y∈F，有x，y>∈

x是y的前缀。例如，是的前缀，但不是001前缀。（1偏序<F的哈斯图是A；<FR>的小元是B；<FR>的大元是（4）G

F，｛101的小上界是D，最大下届是E

。A①链；②树；③既不是链，也不是树；B、C、：④⑤0；⑥0、⑦不存在；⑧10⑨1；⑩26设｛1，2S上定义A个不同的二元关系，其中B

个等价关系，C

个偏序关系，Is是

，

是E

。A、B、：①1②；③3；④4；⑤；⑥16D、E：⑦等价关系但不是偏序关系；⑧偏序关系但不是等价关系；⑨等价关系和偏序关系；⑩既不是等价关系也不是偏序关系；27下面给定个函数，其中单射而非满射的有A，射而非单射的有B双射的有，既不单射，又不满射的有。

，设R为数集合Z为数集合

+

、

分别表示正实数和正整数集合。①f：RR，f（）-x+2x-1②f：R→，fx）=lnx；③f：R→，f（x）=

，

表示不大于x最大整数；④f：RR，f（）=2x+1；⑤f：→

，f（）

x

x28对于给定集合A和B构造从A到B的射函数。B=N其中，分表示整数集和自然数；A=[，2]，B=[-11]实数区间29）S=2为S上的二元关系，且。如果R=Is，则A的小于等于关系，则B；果R=Es则C。（2设有序对，4>与序<，2x+y>等，则x=D，A、B、：①x与y可意选择或；②x=1，；③x=1y=12x=y=2④，；⑤x=y=1或；x=1，；，y=1D、E：⑧3⑨；⑩30设，2，，，为上关系，其关系矩阵是

；如果R是。AA+++AA+++

，则（）的系表达式是AdomR=B；；R中D个有序对；的关系图中有E个。A①<1，，<1，，<1，，，，<4，②｛<1，1><1，，<2，1>，<4，，，4>B、C③｛，2，34｛，2，｛，｛，，4D、E：⑦1⑧；⑨6；⑩31设S=｛，2，…，10上的整除关系，哈斯图是A最大元是B，最小元是，最小上界是D，大下界是E。A①一棵树；②一条链；③以上都不对；B、C、：

，其中④

；⑤1；；⑦，7，，10⑧6⑨0⑩不存在32设R的系如所示，试给出（（（）的关系图。bc33画出下列集合关于整除关系的哈斯图。｛1，2，，4，6，8，12｝｛1，2，，8，｝34设｛，｛，1求（）和；构造一个从（A）到B的射函数。代数系统部分、设Z=｛|x∈∧x>0*表示求两个数的最小公数的运算，则（14*6=A；*Z上B；对于*算的幺元是C，零元是D；（4在

中；A24；②12B③只满足交换率；④只满足结合律；⑤满足交换率、结合律和幂等律；C、：0⑦1；⑧不存在；E：⑨不存在逆元；⑩只有唯一的逆元、在有理数集合上义二元运*x*y=x+y-xy

x，y∈Q有则（）（）=A，=B。*Q上C；关于*幺元是D；Q中足E；A、B：①；②；③；：④可结合的；⑤不可结合的；：⑥；⑦；：⑧所有的元素都有逆元；⑨只有唯一的逆元；⑩x∈，x1时，有元、设V1=<S1>*>，其中S1=，，c，d，12，3}。和*由运算表1和出。

定义同态1→，

（）=0，

（b，

（c）=0，

（d，则（）中运算A，幺元是B

，中运算*

；（2

是，V1在

下的同态像是E

；A、：满足交律，不满足结合律；②不满足交换律，满足结合律；③满足交换律，满足结合律；Ba；⑤；：⑥单同态；⑦满同态；⑧以上两者都不是；：⑨，*>；⑩<｛，、设V1=<｛，21>，其中xy表取x和y之较大的数V2=<56*，6>其中x*y表取x和之较小的数。（1）含A个代数，其中凡的真子代数有B个；含个平凡的子代数。（2积代数V1×有D个素，其幺元是E。A、B、、D①0②；③2；④3；⑤；⑥；⑦6E：⑧，5>；⑨，；⑩<36>、设S=｛a，S上以定义A个二元运算，其中有4个算f1f2，f4，其运算表如下：

aaa

baa

a

bbaf1

f2

a

baa

aaa

bbbf3

f4则只有满足交换律，C满足幂等律D有幺元E有零元A；②；③162；B、C、：⑤和；、；f3f4⑧；；；、设S=｛，2，，9，10下面定义的二元运算*否为上的二元运算？（1x*y=（，x与y的大公约数；x*y=lcmx，y与最小公倍数；x*y大于等于xy最小整数；x*y=maxx，x*y质数P的数，其中x≤py、设V<R*

>是代数系统，其中为非零实数集合。分别对下述小题讨论

运算是否可交换、可结合，并求幺元和所有可逆元素的逆元。、某二进制通信编码由个据位、x2、x3、和校验位、x6、x7构，它们的关系如下：；x2；x7=x1x3x4；其中为或算。（1设S为所有满足上述关系的码字的集合，且x，y∈S，有x

y=(x1

y1,x2

y2，…

y7)，那么<S，

>是一个。（2设x，y∈S，定义H（，）

7

(xi)

，那么当x≠时，（，）≥。i（3使用该种码可查出接收码中包含的所有kC位错误。（4使用该种码可纠正接收码中包含的所有kD位错误。（5如果接收到，知有一位出错，那么出错位是第

位。A①半群，但不是群；②群；③环，但不是域；④域；⑤前都不对；B、C、：①1②；③3；④4；⑤；⑥；⑦7⑧；、对以下定义的集合和运算判断它们是不是代数系统。如果是，是哪一种？（1）｛1，，1/3，，，为普通乘法，则S1是A；（2）｛，a2，，an2，aiR，i=1，…，n，

ai，aj∈，aiaj=ai则S2是B；｛，1为普通乘法，则是C；｛，2，，6为整除关系，则S4是D；｛，1、*别为模2加和乘法，则是E。A、B、、D：①半群，但不是独异点；②是独异点，但不是群；③群；④环，但不是域；⑤域；⑥格，但不是布尔代数；⑦布尔代数；⑧代数系统，但不是以上7种⑨不是代数系统；10图给一个格L，则L是A元；L是B；补元是C，a的元是D，的元是。：①；②；：③分配格；④有补格；⑤布尔格；⑥以上都不对；C、、E：⑦不存在；和；⑨；⑩c；、设B，∧，∨，′，01>布尔代数，，bB，公式f为b∧（a∨（′∧（∨′）在B中化简f；在B中式a∧′∨a′b）=0成立条件是什么？12以定义的集合和运算判断它们能否构成代数系统？如果能说是构成哪一种代数系统？｛，，，…，+为通加法，则是A；｛1/20为普通乘法，则S2是B；｛，1，，，为意给定的正整数，且≥，*为模乘，加法，则S3是；｛，1，，3为于等于关系，则是D；S5=Mn（R为阵加法，则S5是；A、B、、D：①半群，不是独异点；②独异点，不是群；③群；④环，不一定是域；⑤域；⑥格，不是布尔代数；⑦布尔代数；⑧代数系统，不是以上7种⑨不是代数系统；

为模13）G=｛0，，2

为模乘法，则<，

>构成A；（2若

为模加法，则<G，

是阶群，且是。G中2阶是D，4阶是。A①群；②半群，不是群；：③有限；④无限；：⑤Klein群⑥置换群；循环群；D、E：⑧；⑨1和；⑩；2n2n14）L，∧，∨′，01>是布尔代数，则L的运算∧和A，运算∨的幺元是，零元是C，小的子布尔代数是由集合D构；（2在布尔代数L中表达式（∧）∨（∧∧c）∨（b∧c）的等价式是E；A适合德摩律、幂等律、消去律和结合律；适合德摩律、幂等律、分配律和结合律；适合结合律、交换律、消去律和分配律；B、C④0⑤；：⑥｛1｛0，：⑧b（∨c（∧）∨（∧′（∨）∧（∨∨c）∧（∨c15下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格？｛1，2，4，｛1，2，6，｛1，2，4，6，9，18｛1，2，，216设｛，2，3，，A

>构成群，其中

为集合的对称差。（1求解方程｛1｝

｛3，5（2令｛1，由B成的循环子群<B>；17设｛，2，510，22，110｝是110的因子集，>构成偏序集，其中≤为整除关系。画出偏序集<A的哈斯图；说明该偏序集是否构成布尔代数，为什么？18在图所的个有界格中哪些元素有补元？如果有，请指出该元素的所有的补元。图论部分，，，323，，4）能成为图的度数序列吗？为什么（2已知图有10条3顶点，其余顶点的度数均小于等于，问中少有多少个顶点？为什么？）出个顶点条边的所有可能非同构的无向简单；（2画出顶点条边的所有可能非同构的有向简单图；、给定下列各图：G1=<V1，，其中V1=（，，c，，E1={（，e}G2=<V2，，其中V2=V1，E2={（，b）}；（3）G3=<V3，E3>，其中，V3=V1E3={（，b）}（，，中，V4=V1，E4={<a，<b，，，，，<d，a>，<de>}；（5）G5=<V5，E5>，其中，V5=V1，b>，<a，，<b，<c，，<d，e>}（6）G6=<V6，E6>，其中，V6=V1，，，b>，，，c>，，d>}在以上图中A为单图B为重图。A①1③（1B①4、给定下列各顶点度数序列：（2，2，，2，2（1，1，，2，3（1，1，，2，2（0，1，，3，3（1，3，，4，5以上5组中A可构成无向简单图的度数序列。A①11、完全图K4的有非同构的生成子图中，0条的有A个；条边的有B个边的有个条边的有个；条的有个；5条的有F个；边的有G个；A、B、、D、、：①0②；③2；④3；⑤；⑥；设G为无向图，每个顶点的度数不是5就，证明中少有5个度顶点或者至少个顶点。画出阶条边的所有非同构的无向单图。下列各组数中哪些能构成无向图的度数列？哪些能成无向简单图的度数列？，1，1，23；，2，2，22；，3，3，3，2，3，45；，3，3，3、设有向简单图D的数列为223，3其中入度列为00，，3，出度列为。设D是有向简单图，度数列为，3，，它的入度列能为11，1吗？（能或者不能）下面各无向图中有几个顶点？条边，每个顶点都是度点；条边，4度点，其余都是度顶点；条边，各顶点的度数是相同的；一个n≥）无向简单图G中为数已知G中有r个数度顶点，的补图G中有几个奇数度顶点？画出K4的所有非同构的字图，其中有几个是生成子图？生成子图中有几个是连通图？14出3阶向完全图所有非构的子图其中有几个是生成子图？生成子图中又有几个是自补图？设G1、均为4阶向简单图，它们有两条边，它们能彼此均非同构吗？为什么？在K6的上涂上红色或蓝色。明对于任意一种随意的涂法，总存在红色或蓝色K3。（1）非同构的无向的自补图有A（2非同构的无向的5阶补图有BA、B：①；②；③2；④；给定有向带权图如图所示P175d

个；个；b

g

f图中b到的最短路径的权为A；b到d的短路径的权为B；到e最短路径的权为；到的短路径的权为D；A、B、、D①4②；③6；④7；⑤；⑥；⑦1019某中学有课外小组：物理组、化学组、生物组。今有张王、李、赵、同。若已知：（1张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；（2张为物理组成员，王、李、赵为化学组成员，王、李、赵、陈为生物组成员；（3张为物理组和化学组成员，王、李、赵、陈为生物组成员；问在以上中情况下能否各选出3名兼职的组长？20在图8-17所的各图中，A为欧拉图，为哈密顿图。A、B：①（a④（b21图所示的各图中二部图的为A二部图中存在完美匹配的是B，它的匹配数是。A、B：①（a（b（（d（（f⑦（acC：①1；2；③；④422图8-19所示的平面嵌入中，面数A，次数最高的面的次数为B，次数最低的面的次数为，次数为。A、B、：①5②；③7；④8；⑤；⑥10⑦；⑧1；D：①；②26③2823画出完全二部图K13，K24，K22。24完全二部图Krs，边数为，配数

。今有工人甲、乙、丙去完成三项任务a、b、。已知甲能胜任a、bc三任；乙能胜任、b两任务；丙能胜任bc两任。你能出一种安排方案，使每个工人各去完成一项他们能胜任的任务吗？画一个无向欧拉图，使它具有：偶数个顶点，偶数条边；奇数个顶点，奇数条边；偶数个顶点，奇数条边；奇数个顶点，偶数条边；27画一个无向图，使它是：是欧拉图，是哈密顿图；是欧拉图，不是哈密顿图；不是欧拉图，是哈密顿图；不是欧拉图，不是哈密顿图；28今有、b、c、、、f、个人，已知如下事实：会讲英语；：会讲英语和汉语；：会讲英语、意大利语和俄语；：会讲日语和汉语；：会讲德语和意大利语；：会讲法语、日语和俄语；：会讲法语和德语；试问人要围成一圈如排座位能每人都能和他身相邻人交谈？29彼得森图如图所。证明它不是二部图，也不是欧拉图，更不是平面图。30证明图所图是密顿图，但不是平面图。31图8-25所示图G为面图，试给出它的一个平面嵌入，它是极大平面图吗？32）全图Kn（≥）都是欧拉图，个命题真值为A；完全图Kn（≥）是哈密顿图，这命题真值为B完全二部图（≥，≥）都是欧拉图