离散数学题库-资料大全.doc

|试题总汇数理逻辑部分1、判断下列句子中哪些是命题（1）2 是素数（2）血是黑色的（3）2+3=5（4）明年 10 月 1 日是晴天（5）3 能被 2 整除（6）这朵花多好看呀！（7）明天下午有会吗？（8）请关上门！（9）X + y > 5（10）地球外的星球上也有人2、将下列命题符号化（1）3 不是偶数（2）2 是素数和偶数（3）李芳学过英语或日语（4）如果角 A 和角 B 是对顶角，则角 A 等于角 B（5）李平虽然聪明，但不用功（6）李平不但聪明，而且用功（7）小王是游泳冠军或者百米赛跑冠军（8）小王现在在宿舍或者在图书馆（9）选小王或者小李中的一人当班长（10）如果我上街，我就去书店看看，除非我很累（11）如果明天天气好，我们去郊游。否则，不去郊游（12）你爱我，我就嫁给你3、判断下列命题公式是否等值（1） （pq）与 p q（2） （pq）与 p q4、验证下列等值式（1）p（qr） （ pq ）r（2）p （ pq）（p q）5、用等值演算法解决下面问题：A、B、C 、D 4 人百米竞赛。观众甲、乙、丙预报比赛的名次为，（1）甲：C 第一，B 第二。 （2）乙：C 第二，D 第三。 （ 3）丙：A 第二，D 第四。比赛结束后发现甲、乙、丙每人报告的情况都是给对一半。试问，实际名次如何？6、求下面命题公式的主析取范式和主合取范式（1） （pq）r）p7、利用真值表求主析取范式和主合取范式（1） （pq）r8、逻辑推理证明（1）前提：pr，qs，p q。结论：rs 。|（2）前提：pq，p r， st， sr， t。结论：q（3）前提：p（qr） ， sp，q。结论：s r。（4）前提：p（ （rs） q） ，p， s。结论： q9、给定语句如下：（1）15 是素数（2）10 能被 2 整除，3 是偶数（3）你下午有会吗？（4）2x+3> 0（5）2 是素数或是合数（6）这个男孩真勇敢呀！（7）如果 2+2=6，则 5 是奇数（8）只有 4 是偶数，3 才能被 2 整除（9）明年 5 月 1 日是晴天（10）圆的面积等于半径的平方与 的乘积以上 10 个语句中，是简单命题的为 A，是复合命题的为 B，是真命题的为 C，是假命题的为 D，真值待定（真值客观存在，只是现在不知道）的命题为 E。A：（1） 、 （4） 、 （8）（ 4） 、 （6） 、 （9） 、 （10）（1） 、 （9） 、 （10）B：（3） 、 （10）（2） 、 （ 5） 、 （7） 、 （8）（7） 、 （8）C：（2） 、 （5） 、 （9） 、 （10） （7） 、 （8） 、 （10）（2） 、 （9） 、 （10）（5） 、 （7） 、 （8） 、（10）D：（1） 、 （2） 、 （8）（ 1） 、 （2）（1） 、 （5）E：（4） 、 （9）（9）（7） 、 （8）10、判断公式类型（1） （pq）（pq）（2） （p q） （pq）（qp） ）（3） （pq）q（4） （p p） q（5）p（pq）（6） （p p）（q q）r）（7） （pq）p） p（8） （pq）（p q）（9） （pq r） （ p q r）（10） （pq）r11、给定命题公式如下：（ pq）（p q）该命题公式的主析取范式中含极小项的个数为 A，主合取范式中含极大项的个数为 B，成真赋值个数为 C，成假赋值个数为 D。A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)412、一公安人员审查一件盗窃案，已知的事实如下：（1）甲或乙盗窃了录音机（2）若甲盗窃了录音机，则作案时间不能发生在午夜前（3）若乙的证词正确，则午夜时屋里灯光未灭（4）若乙的证词不正确，则作案时间发生在午夜前（5）午夜时屋里灯光灭了推理证明，谁盗窃了录音机。|13、设 p=1，q=0，r=1，s=0，有下列命题公式（1） （pq）（s r）（2） （p qr s）(s q)（3） （pqr） （ p s）那么， （1）的真值为 ；（2）的真值为 ；（3）的真值为 ；14、对于下面的语句，（1）只要 43，就有 32（2）只要 43，就有 32（3）只有 43，才有 32（4）只有 43，才有 32（5）除非 43，否则 32（6）43 仅当 32（7）43 当且仅当 32则，他们的真值是（1） （2） （3） （4） （5） （6） （7） 。15、设 A 是含 n 个命题变项的公式，下面 4 个结论中，哪个是错误的？（1）若 A 的主析取范式中含 2n 个极小项，则 A 是重言式（2）若 A 的主合取范式中含 2n 个极大项，则 A 是矛盾式（3）若 A 的主析取范式中不含任何极小项，则 A 的主析取范式为 0（4）若 A 的主合取范式中不含任何极大项，则 A 的主合取范式为 016、已知命题公式 A 含有 3 个命题变项，其成真赋值为 000，010，100，110。则 A 的主析取范式为 ，主合取范式为 。17、判断下列语句是否为命题，如是命题请指出是简单命题还是复合命题，并讨论真值（1） 是无理数2（2）5 能被 2 整除（3）现在开会吗？（4）x+50（5）这朵花真好看呀！（6）2 是素数当且仅当三角形有 3 条边（7）血是黑色的当且仅当太阳从东方升起（8）2008 年 10 月 1 日天气晴朗（9）太阳系以外的星球上有生物（10）小李在宿舍里（11）全体起立（12）4 是 2 的倍数或是 3 的倍数（13）4 是偶数且是奇数（14）李明与王华是同学（15）蓝色和黄色可以调配成绿色18、将下列命题符号化，并讨论其真值（1）如果今天是 1 号，则明天是 2 号（2）如果今天是 1 号，则明天是 3 号19、设 A、B、C 为任意的命题公式（1）已知 AC BC ，问 A B 吗？|（2）已知 AC BC ，问 A B 吗？（3）已知 A B，问 A B 吗？20、设计一个符合如下要求的室内照明控制线路：在房间的门外、门内及床头分别装有控制同一个电灯 F 的 3 个开关 A、B 、C。当且仅当一个开关的键向上或 3 个开关的键都向上时电灯亮。则 F 的逻辑关系式可化简为 。（1）ABC （2）AB C （ABC） （3）AB（AC）（4）C（AB）21、将下列语句用谓词表达式符号化（1）2 是素数且是偶数（2）如果 2 大于 3，则 2 大于 4（3）凡是有理数均可表成分数（4）有的有理数是整数（5）没有不吃饭的人（6）素数不全是奇数（7）一切人都不一样高（8）有的自然数无先驱数（9）有些人喜欢所有的花（10）任何金属都可以溶解在某种液体中（11）凡是对顶角都相等22、指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现（1） x（F（x） yH（x，y） ）（2） x F（x）G（x，y）（3） x y（R（x，y）L （x，y） ） x H（x，y）23、给定解释 I 如下：1）D I=2，32）D I 中特定元素 a=23）函数 f（x）为 f（2）=3，f（3）=24）谓词 F（x）为 F（2）=0， F（3）=1；G（x，y）为 G（ i，j）=1，i，j=2 ，3；L（x，y）为 L（ 2，2）= L（ 3，3）=1；L（ 2，3）= L（ 3，2）=0在解释 I 下，求下列各式的值。（1） x（F（x）G（x，a） ）（2） x（F（f（x） ）G（x，f（x） ） ）（3） x y L（x，y）24、求下列公式的前束范式（1） xF（x） x G（x）（2） xF（x） x G（x）（3） xF（x） x G（x）（4） xF（x） x G（x）25、设 F（x）：x 是人，G（x）：x 爱吃糖。有人给出语句“不是所有人都爱吃糖”的 4种谓词表达式：（1） x（F（x）G（x） ）（2） x（F（x）G（x） ）（3） x（F（x）G（x） ）|（4） x（F（x） G（x） ）正确的答案是 。26、给出解释 I，使下面两个公式在解释 I 下均为假，从而说明这两个公式都不是永真式（1） x（F（x）G（x） ）（ xF（x） x G（x） ）（2） （ xF（x） x G（x） ） x（F（x）G（x） ）27、取个体域为整数集，给定下列公式（1） x y（x*y=0）（2） x y（x*y=1）（3） y x（x*y=2）（4） x y z（x y = z ）（5）x y = - y + x（6） x y（x *y = y）（7） x（x*y = x）（8） x y（x + y = 2y）在上面的公式中，真命题的为 A，假命题的为 B。A：（1） 、 （3） 、 （4） 、 （6） ；（3） 、 （4） 、 （5） ；（1） 、 （3） 、 （4） 、 （5） ；（3） 、 （4） 、 （6） 、 （7）B：（2） 、 （3） 、 （6） ；（ 2） 、 （6） 、 （8） ；（1） 、 （2） 、 （6） 、 （7） ；（2） 、 （6） 、 （8） 、 （7）集合部分1、下列命题（1） ；（2） ；（3） ；（4） 正确的是 ；错误的是 。2、计算一下幂集（1）P（ ） ；（2）P （ ） ；（3）P （ ， ） ；（4）P（1， 2，3 ）3、证明（1） （A-B）B=AB；4、化简（ABC）（AB） ）- （A（B - C） ）A5、已知：A B=A C，证明：A = B6、求在 1 到 1000 之间不能被 5 和 6，也不能被 8 整除的数的个数7、某班有 25 个学生，其中 14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5 人会打篮球和网球，还有 2 人会打这三种球。而 6 个会打网球的人都会打另一种球（指篮球或排球） ，求不会打这三种球的人数。8、设 F 表示一年级大学生的集合，S 表示二年级大学生的集合，R 表示计算机科学系学生的集合，M 表示数学系学生的集合，T 表示选修离散数学的学生的集合，L 表示爱好文学的学生的集合，P 表示爱好体育运动的学生的集合，则下列各句子所对应的集合表达式分别是：（1）所有计算机科学系二年级的学生都选修离散数学。A（2）数学系的学生或者爱好文学或者爱好体育运动。B（3）数学系一年级的学生都没有选修离散数学。C|（4）只有一、二年级的学生才爱好体育运动。D（5）除去数学系和计算机科学系二年级的学生外都不选修离散数学。EA、B、C 、D、E：T （MR）S；R S T；（MF）T = ；M LP；P FS；S - （MR ） P9、设 S1=1，2，8，9 ，S2=2，4，6，8 ，S3=1，3，5，7，9 ，S4=3，4，5 ，S5=3，5 。确定在以下条件下 X 可能与 S1,S5 中哪个集合相等。（1）若 XS5 = ，则 A（2）若 X S4 但 XS2 = ，则 B（3）若 X S1 但 X S3，则 C（4）若 X - S3= ，则 D（5）若 X S3 但 X S1，则 EA、B、C 、D、E：X=S2 或者 S3；X= S4 或者 S5；X=S1 ，S2 或者 S4；X 与其中任何集合都不等； X=S2 ；X=S5；X=S3 或者 S5；X=S2 或者 S4；10、设 A、B、C 为任意集合，判断下述命题是否恒真，如果恒真给出证明，否则举出反例。（1）AB=AC B=C（2）A B=A B=（3）A（B - C）= （AB ）- （A C）（4） （AB）（B - A）= B11、设 A、B 为集合，试确定下列各式成立的充分必要条件：（1）A B = B（2）A B = B - A（3）AB = AB12、求使得以下集合等式成立时，a，b，c，d 应该满足的条件：（1） a，b=a ，b，c （2） a，b，a=a ，b（3） a， b，c =a ， d （4） a，b ， c =b （5） a， ，b， c = 13、计算 AB、AB、A - B、A B（1）A= a，b ，c ，B=c，d（2）A=a，b ，c ， c ， a，b，B=a，b ， c， b （3）A= x|xNx|x ，yNy =x 2 ；G=|x，yNy =x+1 ；求：G -1、F G、G F、F 1，2 、F1，218、设 F= ， ，求：F F，Fa ，Fa。19、设 A=a，b，c ，d ，R= ， 。给出 R、r（R） 、s（R） 、t（R）的关系图。20、设 A=1，2，3 ，求出 A 上的所有的等价关系21、设 A=1，2，3，11，12 ，R 为 A 上整除关系，画出哈斯图。22、画出的哈斯图。23、R 是 X 上的二元关系，对于 xX 定义集合：R（x）=y|xRy显然 R（x） X。如果 X=-4，-3，-2，-1，0，1，2，3，4，且令R1=|x，yXx|x，yXy -1|x，yXx 2 y ，则下列集合满足（1）R1（0）=A（2）R2（0）=B（3）R3（3）=C（4）R1（1）=D（5）R2（-1）=EA、B、C 、D、E： ；-4，-3，-2 ，-1 ；-2，-1 ；-1 ，0，1 ；-1，0 ；1，2，3 ； 2，3，4 ；0，1，2，3 ；1，2，3，4 ；以上结果都不对24、设 S=1，2，3 ，定义 S×S 上的等价关系 R， S×S 有： a + d = b + c则由 R 产生了 S×S 的一个划分。在该划分中共有 A 个划分块，其中最大的块有 B 个元素，并且含有元素 C 。最小的划分块有 D 块，每块含有 E 个元素。A、B、D、E：|1；2；3；4；5；6；9；C：1；25、设 S=0，1 ，F 是 S 中的字符构成的长度不超过 4 的串的集合，即F= ，0，1，00，01， ，1111 ，其中 表示空串。在 F 上定义偏序关系 R： x，yF，有R x 是 y 的前缀。例如，00 是 001 的前缀，但 01 不是 001 的前缀。（1）偏序集 的哈斯图是 A；（2）的极小元是 B；（3）的最大元是 C；（4）G F，G=101，1001 ，则 G 的最小上界是 D ，最大下届是 E 。A：链；树；既不是链，也不是树；B、C、D、E ： ；0；0、1 和 ；不存在；10；1；111126、设 S=1，2 ，则 S 上可定义 A 个不同的二元关系，其中 B 个等价关系，C 个偏序关系，Is 是 D ， 是 E 。A、B、C ：1；2；3；4；8；16；D、E：等价关系但不是偏序关系；偏序关系但不是等价关系；等价关系和偏序关系；既不是等价关系也不是偏序关系；27、下面给定 5 个函数，其中单射而非满射的有 A ，满射而非单射的有 B ，双射的有 C ，既不单射，又不满射的有 D 。设 R 为实数集合，Z 为整数集合， R+、Z +分别表示正实数和正整数集合。f：RR，f（x）= -x 2+2x-1；f：RZ +，f（x）=lnx；f：RZ，f （ x）= ， 表示不大于 x 的最大整数；xf：RR，f（x）=2 x+1 ；f：R +R +，f（x）= 1228、对于给定集合 A 和 B，构造从 A 到 B 的双射函数。（1）A=Z，B=N ，其中 Z，N 分别表示整数集和自然数集；（2）A= ，2 ，B=-1，1的实数区间29、 （1）设 S=1，2 ，R 为 S 上的二元关系，且 xRy。如果 R=Is，则 A ；如果 R 是数的小于等于关系，则 B ；如果 R=Es，则 C 。（2）设有序对 与有序对 相等，则 x=D ，y= E 。A、B、C ：x 与 y 可任意选择 1 或 2；x=1，y=1；x=1 ，y=1 或 2；x=y=2 ；x=2，y=2；x=y=1 或 x=y=2；x=1，y=2；x=2 ， y=1；D、E：|3；9； -230、设 S= ，R 为 S 上的关系，其关系矩阵是，01则（1）R 的关系表达式是 A；（2）domR=B ；ranR=C ；（3）R R 中有 D 个有序对；（4）R-1 的关系图中有 E 个环。A：， ， ， ；， ， ， ；B、C：1，2，3，4 ；1，2，4 ；1，4 ；1，3，4 ；D、E：1；3；6；731、设 S=1，2，9，10 ， 是 S 上的整除关系，则的哈斯图是 A ，其中最大元是 B ，最小元是 C ，最小上界是 D ，最大下界是 E 。A：一棵树；一条链； 以上都不对；B、C、D、E ： ；1；10；6，7，8，9，10；6；0；不存在32、设 R 的关系图如所示，试给出 r（R） 、s（R ） 、t（R）的关系图。a b c d e 33、画出下列集合关于整除关系的哈斯图。（1） 1，2，3，4，6，8，12，24（2） 1，2，8，934、设 A=a，b ，B= 0， 1 ，（1）求 P（A）和 BA；（2）构造一个从 P（A）到 BA 的双射函数。代数系统部分1、设 Z+=x|xZx>0 ，*表示求两个数的最小公倍数的运算，则（1）4*6=A ；（2）*在 Z+上 B；（3）对于*运算的幺元是 C ，零元是 D ；|（4）在 Z+中 E；A：24；12；B：只满足交换率；只满足结合律；满足交换率、结合律和幂等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元2、在有理数集合 Q 上定义二元运算 *， x，yQ 有x * y = x + y - xy则（1）2*（-5）=A ，7*1/2 = B 。（2）*在 Q 上是 C；（3）关于*的幺元是 D；（4）Q 中满足 E；A、B：4；7；-13；C：可结合的；不可结合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元； xQ，x 1 时，有逆元 x-1。3、设 V1=，V2= ，其中 S1=a，b，c，d ，S2=0，1，2，3。 和*由 运算表 1 和表 2 给出。a b c da a b c db b b d dc c d c dd d d d d表 1* 0 1 2 30 0 1 1 01 1 1 2 12 1 2 3 23 0 1 2 3表 2定义同态 ：S1S2 ，且（a）=0， （b）=1， （c）=0， （d）=1，则（1）V1 中的运算 A ，其幺元是 B ，V2 中的运算*C ；（2） 是 D ，V1 在 下的同态像是 E ；A、C：满足交换律，不满足结合律；不满足交换律，满足结合律；满足交换律，满足结合律；B：a ；d；D：单同态；满同态； 以上两者都不是；E：；4、设 V1= ，其中 x y 表示取 x 和 y 之中较大的数，V2=<5，6 ，