![北邮离散数学期末复习题[1]1](https://img.doczj.com/imgf5/07cpqsjhiuccgy0gmuji-51.webp)
![北邮离散数学期末复习题[1]1](https://img.doczj.com/imgf5/07cpqsjhiuccgy0gmuji-12.webp)
离散数学期末复习题
第一章集合论
一、判断题
（1）空集是任何集合的真子集． （ 错 ）
（2）{}φ是空集． （ 错 ）
（3）{}{}a a a },{∈ （ 对 ）
（4）设集合{}
{}{}{}A A 22,1,2,1,2,1?=则. ( 对 ） （5）如果B A a ??，则A a ?或B a ?． （ 错 ）
解 B A a ??则B A B A a ?=?∈，即A a ∈且B a ∈，所以A a ?且B a ?
（6）如果A ∪.,B A B B ?=则 （ 对 ）
（7）设集合},,{321a a a A =，},,{321b b b B =，则
},,,,,{332211><><><=?b a b a b a B A （ 错 ）
（8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A 2到A 的关
系． （ 对 ）
解 A
2}},1{},0{,{A φ=， =?A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><> （9）关系的复合运算满足交换律． （ 错 ） （10）.条件具有传递性的充分必要上的关系是集合ρρρρA = （ 错 ） （11）设.~,上的传递关系也是则上的传递关系是集合A A ρρ ( 对 ) （12）集合A 上的对称关系必不是反对称的. （ 错 ） （13）设21,ρρ为集合A 上的等价关系, 则21ρρ?也是集合A 上的等价关系( 对 ) （14）设ρ是集合A 上的等价关系, 则当ρ>∈ （15）设21,ρρ为集合 A 上的等价关系, 则 ( 错 ) 二、单项选择题 （1）设R 为实数集合，下列集合中哪一个不是空集 （ A ） A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2 C. {}R x x x x ∈+=且,1| D. {} R x x x ∈-=且,1|2 （2）设B A ,为集合，若φ=B A \，则一定有 （ C ） A. φ=B B ．φ≠B C. B A ? D. B A ? （3）下列各式中不正确的是 （ C ） A. φφ? B ．{}φφ∈ C. φφ? D. {}}{,φφφ∈ （4）设{}}{,a a A =，则下列各式中错误的是 （ B ） A. {}A a 2∈ B ．{}A a 2? C. {}A a 2}{∈ D. {}A a 2}{? （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A ?为 （ B ） A. {}><> C. {}><><2,,,1c c D. {}><><2,,1,c c （6）设{}b A ,0=，{}3,,1b B =，则B A 的恒等关系为 （ A ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0 C. {}><><><3,3,,,0,0b b D. {}><><><><0,3,3,,,1,1,0b b （7）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ D ） A. {}><><><><=a b b a a c c a ,,,,,,,1ρ B ． {}><><=a c c a ,,,2ρ C. {}><><><><=c b a b c c b a ,,,,,,,3ρ D. {}><=a a ,4ρ （8）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （ B ） A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈. （9）映射的复合运算满足 （ B ） A. 交换律 B ．结合律 C. 幂等律 D. 分配律 （10）设A ，B 是集合，则下列说法中（ C ）是正确的. A ．A 到 B 的关系都是A 到B 的映射 B ．A 到B 的映射都是可逆的 C ．A 到B 的双射都是可逆的 D ．B A ?时必不存在A 到B 的双射 （11）设A 是集合，则（ B ）成立. A ．A A #2 2#= B ．A X X A ??∈2 C ．{}A 2∈φ D ．{}A A 2∈ （12）设A 是有限集（n A =#），则A 上既是≤又是～的关系共有（ B ）. A ．0个 B ．1个 C ．2个 D ．n 个 三、填空题 1. 设}}2,1{,2,1{=A ，则=A 2____________. 填}}},2,1{,2{}},2,1{,1{},2,1{}},2,1{{},2{},1{,{2A A φ= 2.设}}{,{φφ=A ，则A 2= . 填}}},{{},{,{2A A φφφ= 3.设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=?B A ， 则集合B A ?中元素的个数=?)(#B A .3 4.设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是， }5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A 中元素的个数为 .40 5.设 },{b a A =, ρ 是 A 2 上的包含于关系，,则有 ρ= . },,},{,}{},{,},{,}{},{,,,}{,,}{,,,{><><><><><><><><> 6.设21,ρρ为集合 A 上的二元关系, 则=21ρρ .~1~2ρρ 7.集合A 上的二元关系ρ为传递的充分必要条件是 ．ρρρ? 8. 设集合{}{}><><==0,2,2,02,1,01ρ上的关系A 及集合A 到集合{}4,2,0=B 的关系=2ρ｛><><><>< 四、解答题 1. 设 A d c b a A },,,,{=上的关系 },,,,,,,,,,,,,,,{><><><><><><><><=c d d c a b b a d d c c b b a a ρ （1）写出ρ的关系矩阵； （2）验证ρ是A 上的等价关系； （3）求出A 的各元素的等价类。 解 （1）ρ的关系矩阵为 ??????? ? ?=1100110000110011ρM （2）从ρ的关系矩阵可知：ρ是自反的和对称的。 又由于 ρρρM M M ≤?????? ? ??=??????? ????????? ??=110011000011001111001100001100111100110000110011 或ρρρ= 满足ρρρ? 所以ρ是传递的。 因为ρ是自反的、对称的和传递的，所以ρ是A 上的等价关系。 （3） },{][][b a b a ==，},{][][d c d c == 2. 设集合}36,24,12,8,6,3,2,1{=A ，ρ是A 上的整除关系， （1） 写出ρ的关系矩阵ρM ； （2） 画出偏序集><ρ,A 的哈斯图； （3） 求出A 的子集}6,3,2{=B 的最小上界和最大下界。 解：（1）???????????? ? ? ?=1000000001000000 1110000001010000 111010001110110011111010 11111111ρM （2） （3）lubB=6, glbB=1 五、证明题 1. 设21,ρρ为集合A 上的等价关系, 试证21ρρ?也是集合A 上的等价关系。 证明：由于21,ρρ是自反的，所以对任意A a ∈,21,,,ρρ>∈<>∈ 21,ρρ?>∈ 若21,ρρ?>∈∈<>∈ 以21,,,ρρ>∈<>∈∈ 若2 1,,,ρρ?>∈<> 21,,,ρρ>∈<>∈ 由于21ρρ?是自反的、对称的和传递的，所以21ρρ?是等价关系。 第二章 代数系统 一、判断题 （1）集合A 上的任一运算对A 是封闭的． （ 对 ） （2）代数系统的零元是可逆元. （ 错 ） （3）设A 是集合，A A A →?: ，b b a = ，则 是可结合的． （ 对 ） （4）设b a ,是代数系统?? ,A 的元素，如果e e a b b a (== 是该代数系统的单位元），则.1b a =- ( 对 ) （5）设.)(,,,111---?=????b a b a G b a 则的元素是群 （ 错 ） （6）设>?<,G 是群．如果对于任意G b a ∈,，有 2 22)(b a b a ?=?，则>?<,G 是阿贝尔群． （ 对 ） （7）设.,,,满足幂等律 则运算是格∨∧?∨?L （ 对 ） （8）设集合},{b a A =，则>??<,},},{},{,{A b a φ是格． （ 对 ） （9）设>∧∨<,,,B 是布尔代数，则>∧∨<,,B 是格． （ 对 ） 二、单项选择题 （1）在整数集Z 上，下列哪种运算是可结合的 （ B ） A. b a b a -= B ．},max{ b a b a = C. b a b a 2+= D. ||b a b a -= （2）下列定义的实数集R 上的运算 * 中可结合的是. （ C ） A ．b a a b a ?+=* B ．b a a b a ?+=*2 C ．b b a =* D ．b a b a +=* 其中，+，·，︱ ︱分别为实数的加法、乘法和取绝对值运算. （3）设集合{}10,,4,3,2,1 =A ，下面定义的哪种运算关于集合A 不是封闭的 （ D ） A. },max{y x y x = B ． },min{y x y x = C. },{GCD y x y x = ，即y x ,的最大公约数 D. },{LCM y x y x = ，即y x ,的最小公倍数 （4）下列哪个集关于减法运算是封闭的 （ B ） A. N （自然数集）； B ．)}(|2{整数集Z x x ∈； C. }|12{Z x x ∈+； D. }|{是质数x x . （5）设Q 是有理数集，在Q 定义运算*为ab b a b a -+=*，则*,Q 的单位元 为 （ D ） A. a ； B ．b ； C. 1； D. 0 （6）设代数系统?A ，·?，则下面结论成立的是. （ C ） A ．如果?A ，·?是群，则?A ，·?是阿贝尔群 B ．如果?A ，·?是阿贝尔群，则?A ，·?是循环群 C ．如果?A ，·?是循环群，则?A ，·?是阿贝尔群 D ．如果?A ，·?是阿贝尔群，则?A ，·?必不是循环群 （7）循环群+,Z 的所有生成元为 （ D ） A. 1，0 B ．-1，2 C. 1，2 D. 1，-1 三、填空题 1. 设A 为非空有限集，代数系统>< ,2A 中，A 2对运算 的单位元为 ，零元 为 .填A ,φ 2.代数系统>+<,Z 中（其中Z 为整数集合，+为普通加法），对任意的I x ∈，其=-1x .填x - 3.在整数集合Z 上定义 运算为b a b a ++=2 ，则>< ,Z 的单位元为 . 解 设单位元为e ，a e a e a =++=2 ，所以2-=e ， 又a a a a a a =++-=-=-++=-2)2()2(,)2(2)2( ，所以单位元为2-=e 4.在整数集合Z 上定义 运算为ab b a b a -+= ，则>< ,Z 的单位元为 . 解设单位元为e ，a ae e a e a =-+= ，0)1(=-e a ，所以0=e 5.设?,G 是群，对任意G c b a ∈,,，如果,c a b a ?=?，则 .填c b = 6.设?,G 是群，e 为单位元，若G 元素a 满足a a =2 ，则=a .填e 四、解答题 1.设 为实数集R 上的二元运算，其定义为 ab b a b a R R 2,:2++=→ ，对于任意R b a ∈, 求运算 的单位元和零元。 解：设单位元为e ，则对任意R a ∈，有a ae e a e a =++=2 ， 即 0)21(=+a e ，由a 的任意性知 0=e ， 又对任意R a ∈，a a a =++=000 ；a a a =++=000 所以单位元为0 设零元为θ，则对任意R a ∈，有θθθθ=++=a a a 2 ， 即 0)21(=+θa ，由a 的任意性知 21- =θ 又对任意R a ∈，2121)21(-=-- =-a a a ，2121)21(-=-+-=-a a a 所以零元为 2 1- 2. 设 为集合}4,3,2,1,0{5=I 上的二元运算，其定义为 5mod )(,:52 5ab b a I I =→ ，对于任意5,I b a ∈ （1） 写出运算 的运算表； （2） 说明运算 是否满足交换律、结合律，是否有单位元和零元、如果有请指出； （3） 写出所有可逆元的逆元 解：（1）运算表为 （2）运算 满足交换律、结合律，有单位元，单位元为1，有零元，零元为0； （3）1的逆元为1，2的逆元为3，3的逆元为2，4的逆元4，0没有逆元 五、证明题 1. 设 >< ,G 是一个群，试证 G 是交换群 当且仅当对任意的G b a ∈, ,有 222)(b a b a = . 证明：充分性 若在群>< ,G 中，对任意的G b a ∈, ,有222)(b a b a = . 则 )()()()(b a b a b b a a = b a b a b b a a )()(= a b b a = 从而 >< ,G 是一个交换群。 必要性 若>< ,G 是一个交换群，对任意的G b a ∈, ,有a b b a =，则 b a b a b b a a )()(= )()()()(b a b a b b a a = 即2 22)(b a b a =. 2. 证明代数系统>< ,Z 是群，其中二元运算 定义如下： ：Z Z →2，3-+=y x y x （这里，+，－分别是整数的加法与减法运算.） 证明 （1）运算满足交换律 对任意∈z y x ,,Z ，由 ,6)3()(-++=-+=z y x z y x z y x 6)3()(-++=-+=z y x z y x z y x 即得),()(z y x z y x =满足结合律； （2）有单位元 3是单位元； （3）任意元素有逆元 对任意∈x Z ，?-=-,.61所以x x Z ，? 是群. 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 第三章 图论 一、判断题 （1）n 阶完全图的任意两个不同结点的距离都为1. （ 对 ） （2）图G 的两个不同结点j i v v ,连接时一定邻接. （ 错 ） （3）图G 中连接结点.,,之间的短程的初级通路为j i j i v v v v （ 错 ） （4）在有向图中，结点i v 到结点j v 的有向短程即为j v 到i v 的有向短程． （ 错 ） （5）强连通有向图一定是单向连通的． （ 对 ） （6）不论无向图或有向图，初级回路一定是简单回路． （ 对 ） （7）设图G 是连通的，则任意指定G 的各边方向后所得的有向图是弱连通的． （ 对 ） （8）有生成树的无向图是连通的． （对） （9）下图所示的图是欧拉图. （ 错 ） （10）下图所示的图有哈密尔顿回路. （ 对 ） 二、单项选择题 （1）仅由孤立点组成的图称为 （ A ） A. 零图； B ．平凡图； C. 完全图； D. 多重图. （2）仅由一个孤立点组成的图称为 （ B ） A. 零图； B ．平凡图； C.多重图； D. 子图. （3）在任何图G 中必有偶数个 （ B ） A. 度数为偶数的结点； B ．度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点. （4）设G 为有n 个结点的无向完全图，则G 的边数为 （ C ） A. )1(-n n B ．)1(+n n C. 2)1(-n n D. 2)1(-n （5）在有n 个结点的连通图G 中，其边数 （ B ） A. 最多1-n 条； B ．至少1-n 条； C. 最多n 条； D. 至少n 条. （6）任何无向图G 中结点间的连通关系是 （ B ） A. 偏序关系； B ．等价关系； C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系. （7）对于无向图，下列说法中正确的是. （ B ） A ．不含平行边及环的图称为完全图 B ．任何两个不同结点都有边相连且无平行边及环的图称为完全图 C ．具有经过每条边一次且仅一次回路的图称为哈密尔顿图 D ．具有经过每个结点一次且仅一次回路的图称为欧拉图 （8）设D 是有向图，则D 强连通的充分必要条件为. ( C ) A ．略去D 中各边方向后所得到的无向图是连通的 B ．D 是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图 C ． D 的任意两个不同的结点都可以相互到达 D ．D 是完全图 （9）对于无向图G ，以下结论中不正确的是. （ A ） A ．如果G 的两个不同结点是连接的，则这两个结点之间有初级回路 B ．如果G 的两个不同结点是连接的，则这两个结点之间至少有一条短程 C ．如果G 是树，则任何两个不同结点之间有且仅有一条初级通路 D ．如果G 是欧拉图，则G 有欧拉回路 三、填空题 1. 设树T 中有7片树叶，3个3度结点，其余都是4度结点，则T 中有 个4度结点. 解 用握手定理和树的性质列出方程求解，设有x 个4度结点， )137(2497-++=++x x ，1=x 2.设>= 3.n 阶完全图的任意两个不同结点的距离都为 ．1 4.图G 为n 阶无向完全图，则G 共有 条边。2/)1(-n n 5.设G 为),(m n 图，则图中结点度数的总和为 。m 2 6. 图G 为欧拉图的充分必要条件是_____________________. G 为无奇度结点的连通图 四、解答题 1. 对下图所示的图G ，求 （1）G 的邻接矩阵A ； （2）G 的结点31,v v 之间长度为3的通路； （3）G 的连接矩阵C ； （4）G 的关联矩阵M 。 解 （1） A =.000011100111011 1010101110543215 4321?? ?? ? ?? ? ??v v v v v v v v v v （2） 因为 A 2=,2112111221114221223121213???????? ?? A 3=,7???????? ???? ?? ?????? ?? ??? ?? ????? ?? 所以，结点31,v v 之间长度为3的通路共有7条，它们是 . ,,,, ,,3431323135313141312135213131v v v v v v v v v v v v v v v v v v v v v v v v v v v v （3）由于图G 是连通的，所以 54321v v v v v C =.111111111111111111111111154321?? ??? ?? ? ??v v v v v （4） 7654321e e e e e e e M =.110000000110000110110 1000011000110154321?? ?? ? ?? ? ??v v v v v 2. 在下面的有向图D 中，回答下列问题 （1）写出图D 的邻接矩阵A ； （2）写出结点1v 到结点3v 的长度为3的所有有向通路； （3）写出结点5v 到自身的长度为3的所有有向回路； 解：（1）???????? ? ?=01010100000110000101 10000A （2）???????? ??=10101010101110011100 010102A ??????? ? ??=12110101011211012110101013A 所以结点1v 到结点3v 的长度为3的所有有向通路只有一条: 3251v v v v （3）结点5v 到自身的长度为3的所有有向回路只有一条：5125v v v v 3.在下面的无向图G 中，回答下列问题 a e d b c （1）写出d a ,之间的所有初级通路； （2）写出d a ,之间的所有短程，并求),(d a d ； （3）判断无向图G 是否为欧拉图并说明理由。 解（1）d a ,之间的所有初级通路共有7条，分别为 aed ，aecd ，aebcd ，abed ，abcd ，abecd ，abced （2）d a ,之间的长度最短的通路只有1条，即aed ，因而它是d a ,之间 唯一的短程，2),(=d a d （3）由于无向图G 中有两个奇度顶点3)deg(,3)deg(==c b ，所以无向图G 没有欧 拉回路，因而不是欧拉图。 第四章 数理逻辑 一、判断题 （1）“如果8＋7＞2，则三角形有四条边”是命题． （ 对 ） （2）设Q P ,都是命题公式，则Q P ?也是命题公式． （ 错 ） （3）命题公式Q P ,的真值分别为0，1，则Q P →的真值为0 （以上是在对Q P ,所包含的命题变元的某个赋值下）． （ 错 ） （4）设:,1963:q p 年他生于他生于1964年，则命题“他生于1963年或1964年”可以符号化为.q p ∨ （ 对 ） （5）设P ，Q 都是命题公式，则.1?→?Q P Q P 的充分必要条件为（ 对 ） （6）逻辑结论是正确结论． （ 错 ） （9）设C B A ,,都是命题公式，则 )()(C A C B A →→?∨∨ 也是命题公式． （ 对 ） （10）命题公式Q P ,的真值分别为0，1，则Q P ?的真值为0 （以上是在对Q P ,所包含的命题变元的某个赋值下）． （ 对 ） 二、单项选择题 （1）下面哪个联结词不可交换 （ B ） A. ∧； B ．→； C.∨； D.? . （2）命题公式q q p p →→∧))((是 （ C ） A. 永假式； B ．非永真式的可满足式； C. 永真式； D. 等价式. （3）记:p 他懂法律，:q 他犯法，则命题“他只有懂法律，才不会犯法”可符号化为（ B ）. A ．q p ?→ B ．p q →? C ．p q ?→ D ．q p → （4）下列命题中假命题是（ B ）. A ．如果雪不是白的，则太阳从西边出来 B ．如果雪是白的，则太阳从西边出来 C ．如果雪不是白的，则太阳从东边出来 D ．只要雪不是白的，太阳就从西边出来 （5）设A ，B 都是命题公式，则A →B 为可满足式是B A ?的（ B ）. A ．充分而非必要条件 B ．必要而非充分条件 C ．充分必要条件 D ．既非充分又非必要条件 三、填空题 1.设:p 天气很冷，:q 老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .q p ∧ 2.设:p 天下雨，:q 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .q p →? 3. 设q p ,的真值为0，s r ,的真值为1，则命题公式)()(s q r p ∨?∧?的真值为 .0 4.设q p ,的真值为0，r 的真值为1，则命题公式)(r q p ∧∨的真值为 .0 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分） 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式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、设代数系统 二、选择 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.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 北京工业大学经管学院期末试卷 《离散数学》（A） 学号姓名：成绩 一、单项选择题（每题2分，共18分） 1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A．P→Q B．P∨Q C．P∧Q D．P∧Q p→q，蕴涵式，表示假设、条件、“如果，就”。 “→”与此题无关 2. 关于命题变元P和Q的极大项M1表示( C )。书P1520，此题换作p、q更容易理解 A.┐P∧Q B.┐P∨Q p∨┐q 01 1 M1 ∨┐Q∧┐Q 3.设R（x）：x是实数；S（）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D） 4.在论域{}中与公式（x?）A（x）等价的不含存在量词的公式是（B） A.)b( )a( A∨ A A )a( A∧ B. )b( C. )b( )b( A→ A A )a( A→ D. )a( 5．下列命题公式为重言式的是（C） A．Q→（P∧Q）B．P→（P∧Q） C．（P∧Q）→P D．（P∨Q）→Q 牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况 6. 设｛1，2，3｝，｛｝，下列二元关系R为A到B的函数的是( A ) A. ｛<1>,<2>,<3>｝ B. ｛<1>,<2>｝ C. ｛<1>,<1>,<2>,<3>｝ D. ｛<1>,<2>,<3>,<1>｝ 7.偏序关系具有性质（D）背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合，映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B （1）若，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】 （2）若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】 （3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】 二、填空题（每空2分，共22分） １.设Q 为有理数集，笛卡尔集×Q ，*是S 上的二元运算，? 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P离散数学期末试题
离散数学考试题详细答案
离散数学期末试题及答案
(完整版)离散数学试卷及答案
离散数学期末试题及答案完整版
离散数学题库
离散数学期末试卷A卷及答案
离散数学试题与答案
离散数学期末测验试题(有几套带答案1)
离散数学期末试卷及答案
最新离散数学期末考试试题配答案
离散数学期末考试试题及答案
离散数学全部试卷
离散数学期末试卷
《离散数学》期末考试试题
离散数学期末考试试题及答案
相关主题
文本预览