慕课 离散数学 电子科技大学 课后习题八

《离散数学》考试题库及答案(三)

《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；

离散数学第三版课后习题答案

离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论

离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；

7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}

离散数学课后习题答案

习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ →

（4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）

离散数学习题

第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);

离散数学习题解答

习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.

（2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表：

《离散数学》试题和答案及解析

一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 2 2n. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 . 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是(P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝{4} ; A?B＝{1,2,3,4}; A－B＝{1,2} . 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0) 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1?R2 ={(1,3),(2,2),(3,1)} , R2?R1 = {(2,4),(3,3),(4,2)} _ R12 ={(2,2),(3,3). 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = . 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} , A∩B ={x | 0≤x≤1, x∈R} , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是?x(?P(x)∨Q(x)) . 15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。(完全图的边 数 2)1 (- n n ，树的边数为n-1) 16.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _. 17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则

屈婉玲版离散数学课后习题答案【1】

第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.

(1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p)

离散数学例题整理

第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)

【离散数学】知识点及典型例题整理

【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，

离散数学题目大汇总

离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若是群，H 是G 的非空子集，则是的子群对任意的a 、b ∈H 有 a * b －1∈H 。 八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗 离散数学试题一（B 卷答案） 一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w

离散数学习题答案

离散数学习题答案 习题二及答案：（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。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ? ∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下：

由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：

离散数学课后答案

离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q

离散数学练习题

离散数学练习题 一、填空题 1. 命题Q →P 的真值为0，当且仅当 。 2. 构造公式S R S R →∨∧)(的真值表 。 3. 仅用∧和┐写出下列表达式的等价形式 a) R Q P ?→∨?? b) P Q ∨? 4. 仅用∨和┐写出下列表达式的等价形式 a) )()(D C B A ∨→∨? 。 b) )(E D A ?→→?? 5. 公式A 有三个命题变元P 、Q 、R 组成，其主析取范式为A 6531m m m m ∨∨∨?，则其主合取 范式为： 6. 公式A 有三个命题变元P 、Q 、R 组成，其主合取范式为A ?65310M M M M M ∧∧∧∧，则 其主析取范式为： 。 7. 设解释I 如下： D={n ，m} P(n ，n) P(n ，m) P(m ，n) P(m ，m) 1 1 0 0 8. 确定下列各式的真值： ),(m x xP ? ___ ___; ),(y n yP ? __ ___; ),(y x yP x ??) __ ___。 ),(n x xP ? ___ ___; ),(y m yP ? __ ___; ),(y x yP x ??) __ ___。 9. 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。 10. 某集合有101个元素，则有 个子集的元素为奇数。 11. 某班有32个学生，其中14个人选择艺术，7个人选择生物，6个人选择音乐，三门课都选的有 2人，问这三门课都没选的至少有 人？ 12. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,3,5,6}, B={2,4,6,8,9}, 则：A ∩B= , B ⊕A= , B A ?= ; (A ∪B)-B = , (A ∪B)-(B ∩C)= 13. =Φ=)(},,a {A A ρ 。 14. B A b a B A ×==2},,{},1{= =×B A )(ρ

离散数学第四版课后标准答案

离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命

题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q

离散数学试题与答案

试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式x ??真值为 。 3设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则 R= （列举法）。 R 的关系矩阵M R = 。 4、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系R= 。 5、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。

8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生 的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、反对称性； C ．反自反性、反对称性、传递性； D ．自反性 。

最新离散数学习题答案

离散数学习题答案 习题一及答案：（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 →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值：

（4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p 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。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：

离散数学题库及答案

数理逻辑部分 选择、填空及判断 ?下列语句不是命题的（ A ）。 (A) 你打算考硕士研究生吗？(B) 太阳系以外的星球上有生物。 (C) 离散数学是计算机系的一门必修课。(D) 雪是黑色的。 ?命题公式P(P P)的类型是（ A ） (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A是重言式，那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 ?以下命题公式中，为永假式的是( C ) A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 ?谓词公式) x R xP∧ ?中，变元x是( B ) ) x ( , (y A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 ?命题公式P(Q Q)的类型是( A )。 (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?设B不含变元x，) x→ ?等值于( A ) A (B ) ( x

A. B x xA →?)( B. ))((B x A x ∨? C. B x xA →?)( D. B x A x ∧?)(( ? 下列语句中是真命题的是( D )。 A ．你是杰克吗？ B ．凡石头都可练成金。 C ．如果2+2=4，那么雪是黑的。 D ．如果1+2=4，那么雪是黑的。 ? 从集合分类的角度看，命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 ? 命题公式﹁p ∨﹁q 等价于( D )。 A. ﹁p ∨q B. ﹁(p ∨q) C. ﹁p ∧q D. p →﹁q ? 一个公式在等价意义下，下面写法唯一的是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ? 下列含有命题p ，q ，r 的公式中，是主析取范式的是 ( D )。 (A) (p q r) (p q) (B) (p q r) (p q) (C) (p q r) (p q r) (D) (p q r) (p q r) ? 设个体域是整数集合，P 代表x y ((x y )(x y x ))，下面描述正确的是 （ C ）。 (A) P 是真命题 (B) P 是假命题 (C) P 是一阶逻辑公式，但不是命题 (D) P 不是一阶逻辑公式 ? 对一阶逻辑公式((,)(,))(,)x y P x y Q y z xP x y ??∧∧?的说法正确的是( B ). (A) x 是约束的，y 是约束的，z 是自由的； (B) x 是约束的，y 既是约束的又是自由的，z 是自由的； (C) x 是约束的，y 既是约束的又是自由的，z 是约束的；