离散数学期末复习
一、填空20%（每空2分）：
1．若对命题P 赋值1，Q 赋值0，则命题Q P ?的真值为 。
2．命题“如果你不看电影，那么我也不看电影”（P ：你看电影，Q ：我看电影）的符号化为
3．公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为
4．图 的对偶图为
5．若关系R 是等价关系，则R 满足 性质。
6．关系R 的传递闭包t (R) = 。
7．代数系统>*<,A 是群，则它满足
8．设>?⊕<>?+<,,,,B A 和是两代数系统，f 是从>?⊕<>?+<,,,,B A 到的同态映射，则f 具有 性质。
9．树T 的边数e 与点数v 有关系 。
二、选择10%（每小题2分）：
1．如果解释I 使公式A 为真，且使公式B A →也为真，则解释I 使公式B 为（ ）。
A 、真；
B 、假；
C 、可满足；
D 、与解释I 无关。
2．设{}b a A ,=，则P （A ）×A = （ ）。
A 、A ；
B 、P （A ）；
C 、{}><><><><><><>Φ<>Φ
D 、{}><><><><><><>Φ<>Φ 3．设集合A ，B 是有穷集合，且n B m A ==,，则从A 到B 有（ ）个不同的双射函数。 A 、n ； B 、m ； C 、!n ； D 、!m 。 4．设K = {e , a , b , c}，>*<,K 是Klein 四元群，则元素a 的逆元为（ ）。 A 、e ； B 、a ； C 、b ； D 、c 。 5．一个割边集与任何生成树之间（ ）。 A 、没有关系； B 、割边集诱导子图是生成树； C 、有一条公共边； D 、至少有一条公共边。 三、逻辑推理12%： 符号化命题“每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是 青年专家”；并用演绎方法证明上面推理。（F(x)：x 是学术会成员；H(x)：x 是工人；G(x)：x 是专家；R(x)：x 是青年人） 四、8%： 求集合),3,2,1(10 =??????≤ <=n n x x A n 的并与交。 五、12%： 在实数平面上，画出关系，并判定关系的特殊性质。 七、10%： 求图中的一棵最小生成树。 八、10%： 求图 的邻接矩阵和可达矩阵。 九、10%： 证明：如果G 是无向简单图且2≥δ，则G 包含一条长度不小于1+δ的基本回路。 一、填空20%（每空2分） 1．n 个命题变元有 个互不等价的极小项。 2．按De-Morgan 定理，i n i n A A A A ?= ?∨∨?∨?∨=121 = 。 3．公式)(R Q P ∨?→的主析取范式为 。 4．设P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比y 重，则命题“大象比老鼠重”的符号化为 5．设},,{c b a X =，X 上的关系R 的关系矩阵是???? ? ??=111011101R M ，则 =R R M 。 6．在具有n 个结点的有向图中，任何基本通路的长度都不超过 。 7．任何图的点连通度)(G κ，边连通度)(G λ，最小点度)(G δ的关系为 8．结点数n （3≥n ）的简单连通平面图的边数为m ，则m 与n 的关系为 。 9．群G 的非空子集H 是G 的子群当且仅当若x , y ∈H 则 。 10．代数系统>?+<,,A 是环，若对运算“· ”还满足 则>?+<,,A 是整环。 二、选择10%（每小题2分） 1．集合},2{N n x x A n ∈==对（ ）运算封闭。 A 、加法； B 、减法； C 、乘法； D 、y x - 。 2．设I 为整数集合，m 是任意正整数，m Z 是由模m 的同余类组成的同余类集合，在m Z 上定义 运算]mod )[(][][m j i j i ?=?，则代数系统>? A 、封闭的代数系统； B 、半群； C 、独异点； D 、群。 3．设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于” 关系，则 N b a ∈?,有=∨b a （ ）。 A 、a ； B 、b ； C 、max(a ，b) ； D 、min(a ，b)。 4．连通非平凡的无向图G 有一条欧拉回路当且仅当图G ( )。 A 、只有一个奇度结点； B 、只有两个奇度结点； C 、只有三个奇度结点； D 、没有奇度结点。 5．设无向图>= A 、M=N+1 ； B 、n=m+1 ； C 、63-≤n m ； D 、63-≤m n 。 三、12%逻辑推理： 符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（P(x)：x 是病人，D(x)：x 是医生，Q(x)：x 是法轮功练习者，L(x , y)：x 相信y ） 四、序关系8%： 设},,,,{54321x x x x x A =，偏序集> 求 ① A 中最小元与最大元； ② },,{543x x x 的上界和上确界，下界和下确界。 五、函数8% 设Z Y g Y X f →→::和 是映射且使得f g 是满射，若g 是入射，证明f 是满射。 六、图8% 设G 是连通简单平面图，结点数为n （3≥n ），边数为m ，面数为r ，则42-≤n r 。 七、树的应用12% 设7个符号在通讯中使用的频率如下： a ：35% ， b ：20% ， c ：15% ， d ：10% ， e ：10% ， f ：5% ， g ：5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。 九、子群12% 若H 是G 的子群，G b a ∈,，则 Φ≠??∈-bH aH H a b 1 。 一、问答10% 已知定义在集合},,,{d c b a 上的运算*如下表： 试问：1）>*<},,,,{d c b a 是代数系统否？（ ） 2）>*<},,,,{d c b a 是子群否？（ ） 3）>*<},,,,{d c b a 是群否？（ ） 4）>*<},,,,{d c b a 有单位元否？（ ） 5）>*<},,,,{d c b a 满足交换律否？（ ） 二、填空10% 下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足或无该项者不填） 三、有向图的矩阵表示应用15% 已知某有向图的邻接矩阵如下：?????? ? ??=0001 1011110001004321v v v v A 试求：3v 到1v 的长度为4的有向路径的条数。 四、图的同构15% 下面两图是否同构，若是给出点集间的同构映射。 v 1 v 2 v 3 v 4 五、树的性质15% 已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。 六、最小生成树15% 使用普里姆算法求下图的最小生成树 七、自同构映射10% 令},,,2{为普通加法+∈+==Q b a b a m m R ，定义映射g ：R R →为2)2(b a b a g -=+，试证：g 是>+<,R 到>+<,R 的自同构映射。 八、群与子群10% 设>*<,G 是阶为6的群，证明它至多有一个阶为3的子群。 一、单项选择题：（每小题1分，本大题共15分） 1．设A={1，2，3，4，5}，下面（ ）集合等于A 。 A 、{1，2，3，4，5，6}； B 、}25{2 ≤x x x 是整数且； C 、}5{≤x x x 是正整数且； D 、}5{≤x x x 是正有理数且。 2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A 、A ?Φ； B 、{6，7，8}∈A ； C 、{{4，5}}?A ； D 、{1，2，3}?A 。 3．六阶群的子群的阶数可以是（ ）。 A 、1，2，5； B 、2，4； C 、3，6，7； D 、2，3 。 4．设B A S ??，下列各式中（ ）是正确的。 A 、 domS ? B ； B 、domS ?A ； C 、ranS ?A ； D 、domS ? ranS = S 。 5．设集合Φ≠X ，则空关系X Φ不具备的性质是（ ）。 A 、自反性； B 、反自反性； C 、对称性； D 、传递性。 6．下列函数中，（ ）是入射函数。 A 、世界上每个人与其年龄的序偶集； B 、、世界上每个人与其性别的序偶集； B 、 一个作者的专著与其作者的序偶集； D 、每个国家与其国旗的序偶集。 7．><,*G 是群，则对*（ ）。 A 、满足结合律、交换律； B 、有单位元，可结合； C 、有单位元、可交换； D 、每元有逆元，有零元。 8．下面（ ）哈斯图所描述的偏序关系构成分配格。 9．下列（ ）中的运算符都是可交换的。 A 、→∨∧,,； B 、?→,； C 、???,,； D 、∧∨, 。 10．设G 是n 个结点、m 条边和r 个面的连通平面图，则m 等于（ ）。 A 、n+r-2 ； B 、n-r+2 ； C 、n-r-2 ； D 、n+r+2 。 11．n 个结点的无向完全图n K 的边数为（ ）。 A 、)1(+n n ； B 、2)1(+n n ； C 、)1(-n n ； D 、2 )1(-n n 。 12．下列图中（ ）是根树。 A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G ； B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G ； C 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a G ； D 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 。 13．设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，下列（ ）命题的真 值为真。 A 、R Q P ∧→ ； B 、S P R ∧→ ； C 、R Q S ∧→ ； D 、)()(S Q R P ∧∨∧。 14．下面（ ）命题公式是重言式。 A 、R Q P ∨→ ； B 、)()(Q P R P →∧∨ ； C 、)()(R Q Q P ∨?∨ ； D 、))()(())((R P Q P R Q P →→→→→→。 15．设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老师” 符号化为（ ）。 A 、)),()((y x A x L x →?； B 、))),()(()((y x A y J y x L x ∧?→? ； C 、)),()()((y x A y J x L y x ∧∧??； D 、)),()()((y x A y J x L y x →∧?? 。 二、填空题：（每空1分，本大题共15分） 1．设}2,121{Z x x x x M ∈≤≤=整除，被，}3,121{Z x x x x N ∈≤≤=整除，被， 则 =?N M ，=-N M 。 2．在一个有n 个元素的集合上，可以有 种不同的关系，有 种不同的函数。 3．若关系R 是反对称的，当且仅当关系矩阵中 ，在关系图上 。 4．设f g 是一个复合函数，若g 和f 都是满射，则f g 为 ，若g 和f 都是入射，则f g 是 。 5．三阶群有 个（不同构），其运算表为 。 6．设图G = < V ，E >，},,,{4321v v v v V =的邻接矩阵??????? ? ?=0001001111011010A ，则1v 的入度 )(d e g 1v -= ，4v 的出度)(deg 4v += ，从2v 到4v 的长 度为2的路有 条。 7．命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 三、判断改正题：判断下列各题是否正确，正确的划“√”，错误的划“×”，并加以改正。（每小题2分，本大题共20分） 1．A ，B ，C 为任意集合，若C A B A ?=?，则B = C 。 （ ） 2．设R 是实数集，R 上的关系},,2,{R y x y x y x f ∈<-><=，R 是相容关系。（ ） 3．设< A ，≤ >是偏序集，A B ?，则B 的极大元B b ∈且唯一。 （ ） 4．谓词公式)()()(y yR x xQ x xP ?∨?→?的前束范式是))()()((y R z Q x P y z x ∨→???。 （ ） 5．在代数系统< S , *> 中，若一个元素的逆元是唯一的，其运算*必是可结合的。 （ ） 6．每一个有限整环一定是域，反之也对。 （ ） 7．有割点的连通图可能是哈密尔顿图。 （ ） 8．)()())()((x xB x xA x B x A x ?∧??∧?。 （ ） 9．无多重边的图是简单图。 （ ） 10．设>∨∧<,,A 是布尔代数，则>∨∧<,,A 一定为有补分配格。 （ ） 四、简答题：（每小题5分，本大题共20分） 1．设1R 和2R 是A 上的任意二元关系，如果1R 和2R 是自反的，21R R 是否也是自反的，为什么？如果1R 和2R 是对称的，21R R 是对称的吗？ 2．如图给出的赋权图表示六个城市f e d c b a ,,,,,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。 3．设S = R - {-1}（R 为实数集），ab b a b a ++=*。 （1）说明>*<,S 是否构成群； （2）在S 中解方程732=**x 。 4．将公式)()((R P R Q P ∧→∧∨）划为只含有联结词∧?，的等价公式。 五、证明题：（共30分） 1．设}9,,3,2,1{ =A ，在A A ?上定义关系R d c b a R >>∈ <><<,,,:当且仅当c b d a +=+，证明R 是A A ?上的等价关系，并求出?]5,2[=> 2．用CP 规则证明)(C B A ∧→，C F E ?→?→)(，)(S A B ?∧→ E B →。 3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。 5．证明：若T 是有n 个结点的完全二叉树，则T 有 2 1+n 片叶子。 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 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 ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、? ； C 、∈ ； D 、? 。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=* ； B 、),max(b a b a =* ； C 、b a b a 5+=* ； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。 二、填空：（每空1分，本大题共15分） 1．在自然数集中，偶数集为1N 、奇数集为2N ，则21N N ?= ； 21N N ? = 。 2．设}3,34,2,2,1{,}4,3,2,1{><><><==，R X ，则 r (R) = ；s (R) = ；t (R) = 。 3．设R 为集合A 上的等价关系，对A a ∈?，集合R a ][= ， 称为元素a 形成的R 等价类，Φ≠R a ][，因为 。 4．任意两个不同小项的合取为 ，全体小项的析取式为 。 5．设为偶数x x Q :)(，为素数x x P :)(，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ； （2） 。 6．设T 为根树，若 ，则称T 为m 元树； 若 则称T 为完全m 叉树。 7．含5个结点，4条边的无向连通图（不同构）有 个， 它们是 。 三、判断改正题：（每小题2分，本大题共20分） 1．命题公式B B A A →→∧))((是一个矛盾式。 （ ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ ） 3．根树中最长路径的端点都是叶子。 （ ） 4．若集合A 上的关系R 是对称的，则1-R 也是对称的。 （ ） 5．数集合上的不等关系（≠）可确定A 的一个划分。 （ ） 6．设集合A 、B 、C 为任意集合，若A×B = A×C ，则B = C 。 （ ） 7．函数的复合运算“。”满足结合律。 （ ） 8．若G 是欧拉图，则其边数e 合结点数v 的奇偶性不能相反。 （ ） 9．图G 为（n , m ）图，G 的生成树G T 必有n 个结点。 （ ） 10．使命题公式)(R Q P ∨→的真值为F 的真值指派的P 、Q 、R 值分别是T 、F 、F 。 （ ） 四、简答题（每小题5分，本大题共25分） 1．设>< ,H 和>< ,K 都是群>< ,G 的子群，问>?< ,K H 和>?< ,K H 是否是>< ,G 的子并说明理由。 2．设}9432{，，， =A ，}12,10742{，，，=B ，从A 到B 的关系 },,,{b a B b A a b a R 整除且∈∈><=，试给出R 的关系图和关系矩阵，并说明此关系是否为函数？为什么？ 3．设>*<,S 是半群，L O 是左零元，对任L O x S x *∈,是否是左零元？为什么？ 4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由） 5．通过主合取范式，求出使公式R Q P ∨→??)(的值为F 的真值指派。 五、证明题：（共30分） 1．设R 为集合A 上的二元关系，如果R 是反自反的和可传递的，则R 一定是反对称的。 2．试证明若>*<,G 是群，G H ?，且任意的H a ∈，对每一个G x ∈，有a x x a *=*，则>*<,H 是>*<,G 的子群。 ．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。 一、填空题：（每空1分，本大题共15分） 1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号： ?∈,。 （1）}{a B , (2) }}3{,4,{a A 。 2．设}1,0{=A ，N 为自然数集，???=是偶数。，是奇数， ，x x x f 10)( 若A A f →： ，则f 是 射的，若A N f →： ，则f 是 射的。 3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2， 则G 中有 条边，根据 。 4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。 5．设个体域为自然数集，命题“不存在最大自然数”符号化为 。 6．设S 为非空有限集，代数系统>?<,2S 中幺元为 ，零元为 。 7．设P 、Q 为两个命题，其De-Morden 律可表示为 。 8．当8=G 时，群>*<,G 只能有 阶非平凡子群，不能有 阶 子群，平凡子群为 。 二、单项选择题：（每小题1分，本大题共15分） 1．设}16{2<=x x x A 是整数且，下面哪个命题为假（ ） 。 A 、A ?}4,2,1,0{ ； B 、A ?---}1,2,3{ ； C 、A ?Φ ； D 、A x x x ?<}4{是整数且。 2．设}}{,{,ΦΦ=Φ=B A ，则B －A 是（ ）。 A 、}}{{Φ ； B 、}{Φ ； C 、}}{,{ΦΦ ； D 、Φ。 3．下图描述的偏序集中，子集},,{f e b 的上界为 （ ）。 A 、c b , ； B 、b a , ； C 、b ； D 、c b a ,,。 4．设f 和g 都是X 上的双射函数，则1)(-g f 为（ ）。 A 、11--g f ； B 、1)(-f g ； C 、11--f g ； D 、1-f g 。 5．下面集合（ ）关于减法运算是封闭的。 A 、N ； B 、}2{I x x ∈ ； C 、}12{I x x ∈+ ； D 、}{是质数x x 。 6．具有如下定义的代数系统>*<,G ，（ ）不构成群。 A 、}10,1{=G ，*是模11乘 ； B 、}9,5,4,3,1{=G ，*是模11乘 ； C 、Q G =（有理数集），*是普通加法 ； D 、Q G =（有理数集），*是普通乘法。 7．设},32{I n m G n m ∈?=，*为普通乘法。则代数系统>*<,G 的幺元为（ ）。 A 、不存在 ； B 、0032?=e ； C 、32?=e ； D 、1132--?=e 。 8．下面集合（ ）关于整除关系构成格。 A 、{2，3，6，12，24，36} ； B 、{1，2，3，4，6，8，12} ； C 、{1，2，3，5，6，15，30} ； D 、{3，6，9，12}。 9．设},,,,,{f e d c b a V =， },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ，则有向图 >= A 、强连通的 ； B 、单侧连通的 ； C 、弱连通的 ； D 、不连通的。 10．下面那一个图可一笔画出（ ）。 11．在任何图中必定有偶数个（ ）。 A 、度数为偶数的结点 ； B 、入度为奇数的结点 ； C 、度数为奇数的结点 ； D 、出度为奇数的结点 。 12．含有3个命题变元的具有不同真值的命题公式的个数为（ ）。 A 、32 ； B 、23 ； C 、322 ； D 、232 。 13．下列集合中哪个是最小联结词集（ ）。 A 、},{→? ； B 、},{?? ； C 、},{?→ ； D 、},,{∨∧? 。 14．下面哪个命题公式是重言式（ ）。 A 、)()(R Q Q P →∧→ ； B 、P Q P →∧)( ； C 、)()(Q P Q P ?∧?∧∨? ； D 、P Q P ∧∨?)( 。 15．在谓词演算中，下列各式哪个是正确的（ ）。 A 、),(),(y x xA y y x yA x ????? ； B 、),(),(y x xA y y x yA x ????? ； C 、),(),(y x xA y y x yA x ????? ； D 、)()(x xA a A ?? 。 三、判断改正题：（每小题2分，本大题共20分） 1．设}2,1{=A ，}{a B =，则 B A B A ?=?222。（其中A 2为 （A ）） ( ) 2．设}1,0{=A ，}2,1{=B ，则 }2,0,1,1,0,1,2,1,0,1,1,0{2><><><><=?B A 。 （ ） 3．集合A 上的恒等关系是一个双射函数。 （ ） 4．设Q 为有理数集，Q 上运算 * 定义为),max(b a b a =*，则>*<，Q 是半群。（ ） 5．阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。 （ ） 6．在完全二元树中，若有t 片叶子，则边的总数12-=t e 。 （ ） 7．能一笔画出的图不一定是欧拉图。 （ ） 8．设P ，Q 是两个命题，当且仅当P ，Q 的真值均为T 时，Q P ?的值为T 。（ ） 9．命题公式Q Q P P →→∧))((是重言式。 （ ） 10．设，是研究生：x x P )( ，曾读过大学：x x Q )( 命题“所有的研究生都读过大学”符号化 为：))()((x Q x P x ∧?。 （ ） 四、简答题：（25分） 1．设},,{c b a A =，A 上的关系 },,,,,,,{><><><><=b c c b b a a a ρ，求出 )()(,)(ρρρt s r 和。 2．集合}36,24,12,6,3,2{=A 上的偏序关系 为整除关系。设}12,6{=B ， }6,3,2{=C ，试画出 的哈斯图，并求A ，B ，C 的最大元素、极大元素、下界、上确界。 3．图给出的赋权图表示五个城市54321v v v v v ，，，， 及对应两城镇间公路的长度。试给出一个最优化的设计 方案使得各城市间能够有公路连通。 4．已知}654321{，，，，，=G ，7?为模7乘法。试说明>?<7，G 是否构成群？是否为循环群？ 若是，生成元是什么？ 5．给定命题公式)())((W S R Q P ∨?∨∧?∧，试给出相应的二元树。 五、证明题：（25分） 1．如果集合A 上的关系R 和S 是反自反的、对称的和传递的，证明：S R ?是A 上的等价关系。 2．用推理规则证明)()(a G a P ∧?是 ))()((,)(,))()((, )))()(()((x G x S x a S a R a Q x R x Q x P x ??∧?∧→?的有效结论。 3．若有n 个人，每个人都恰有三个朋友，则n 必为偶数。 4．设G 是（11，m ）图，证明G 或其补图G 是非平面图。 一、填空题：（每空1分，本大题共15分） 1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。 2．命题公式)(Q P →?的主析取范式为 ，主合取范式的编 码表示为 。 3．设E 为全集， ，称为A 的绝对补，记作～A ， 且～（～A ）= ，～E = ，～Φ= 。 4．设},,{c b a A =考虑下列子集 }},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =，}},,{{4c b a S = }}{},{},{{5c b a S =，}},{},{{6c a a S = 则A 的覆盖有 ，A 的划分有 。 5．设S 是非空有限集，代数系统＜ （S ），?，?＞中， （S ）对?的幺元为 ， 零元为 。 （S ）对?的幺元为 ，零元为 。 6．若>= W(G-S) S 成立，其中W(G-S)是 。 二、单项选择题：（每小题1分，本大题共10分） 1．下面命题公式（ ）不是重言式。 A 、)(Q P Q ∨→； B 、P Q P →∧)(； C 、)()(Q P Q P ∨?∧?∧?； D 、)()(Q P Q P ∨??→。 2．命题“没有不犯错误的人”符号化为（ ）。 设x x M ： )(是人，x x P ：)(犯错误。 A 、))()((x P x M x ∧?； B 、)))()(((x P x M x ?→??； C 、)))()(((x P x M x ∧??； D 、)))()(((x P x M x ?∧??。 3．设}{Φ=A ，B = ( (A))，下列各式中哪个是错误的（ ）。 A 、 B ?Φ； B 、B ?Φ}{， C 、B ∈Φ}}{{； D 、?ΦΦ}}{,{ (A)。 4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）。 A 、),min(b a b a =*； B 、b a b a 2+=*； C 、3++=*b a b a ； D 、)3(mod ,b a b a =*。 5．设Z 为整数集，下面哪个序偶不够成偏序集（ ）。 A 、)(,小于关系：<> < 6．任意具有多个等幂元的半群，它（ ）。 A 、不能构成群； B 、不一定能构成群； C 、不能构成交换群； D 、能构成交换群。 7．设≤><,A 是一个有界格，它也是有补格，只要满足（ ）。 A 、每个元素都有一个补元； B 、每个元素都至少有一个补元； C 、每个元素都无补元； D 、每个元素都有多个补元。 8．设>= 。 A 、完全图； B 、树； C 、简单图； D 、多重图。 9．给定无向图>= A 、},,,{4341><> B 、},,,{6451><> C 、},,,{8474><> D 、},,,{3221><> 10．有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件（ ）。 A 、63-≥m n ； B 、63-≤m n ； C 、63-≥n m ； D 、63-≤n m 。 三、判断改正题：（每小题2分，本大题共20分） 1．设A ，B 为任意集合，不能B A B A ∈?且。 （ ） 2．设R 是集合A 上的关系，若21,R R 是对称的，则21R R 也是对称的。（ ） 3．群中可以有零元（对阶数大于1的群）。 （ ） 4．循环群一定是Abel 群。 （ ） 5．每一个链都是分配格。 （ ） 6．不可能有偶数个结点，奇数条边的欧拉图。 （ ） 7．图G 中的每条边都是割边，则G 必是树。 （ ） 9．公式)())()((y R x Q x P x ∧→?中x ?的辖域为)(x P 。 （ ） 10．公式),()(y x yQ x xP ?→?的前束范式为 )),()((y x Q x P y x →??。 （ ） 四、简答题（共20分） 1．用等值演算法求下面公式的主析取范式，并求其成真赋值。 R Q P →∨)( 2．集合}4,3,2,1{=A 上的关系 }4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1{><><><><><><><><=R ，写出关系矩阵R M ，画出关系图并讨论R 的性质。 3．有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种 药品？ 4．一棵树T 中，有3个2度结点，一个3度结点，其余结点都是树叶。 （1）T 中有几个结点； （2）画出具有上述度数的所有非同构的无向图。 五、证明题：（35分） 1．符号化下列各题，并说明结论是否有效（用推理规则）。 凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。 2．用推理规则证明： C A F E F D E B D C B A →∧?∨?∧∨?→∧→,)(,)()(,)()(├ A 3．设函数B A f →：，C B g →：，若f g 是满射的，则g 是满射的。 4．当且仅当G 的一条边e 不包含在G 的闭迹中时，e 才是G 的割边。 5．设>∧∨<,,S 是一个分配格，S a ∈，令a x x f ∨=)(，对任意S a ∈，证明：f 是>∧∨<,,S 到自身的格同态映射。 华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x 2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5 离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C） （6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0 （12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A A i(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨A s为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】(p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q) 熟练之后，以上过程可不写在演算过程中。 该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式， 00，01，10，11全为成真赋值。 【例】(p→q)∧┐p = (┐p∨q)∧┐p (消去→) = ┐p∨(┐p∧q) (分配律、幂等律) 已为析取范式 离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。 谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证 二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共72学时，开设一学期．该课程的主要内容包括：集合论、图论、数理逻辑等． 下面按章给出复习要点与重点． 第1章 集合及其运算 复习要点 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法． 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.． 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念． 注意：元素与集合，集合与子集，子集与幂集，∈与?(?),空集?与所有集合等的关系. 空集?，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ?， A 的所有子集构成的集合．若∣A ∣＝n ，则∣P (A )∣=2n ． 2．熟练掌握集合A 和B 的并A ?B ，交A ?B ，补集~A (~A 补集总相对于一个全集).差集A －B ，对称差⊕，A ⊕B ＝(A －B )?(B －A )，或A ⊕B ＝(A ?B )－（A ?B ）等运算，并会用文氏图表示． 掌握集合运算律(见教材第9～11页)(运算的性质). 3．掌握用集合运算基本规律证明集合恒等式的方法． 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A ＝B ，只需证明A ?B ，又A ?B ； (2)通过运算律进行等式推导． 重点：集合概念，集合的运算，集合恒等式的证明． 第2章 关系与函数 复习要点 1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如 离散数学笔记（特级教师精心整理） 第一章命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2命题联结词 （1） P↑P?﹁（P∧P）?﹁P； （2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。 （1）P↓P?﹁（P∨Q）?﹁P； （2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q； （3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）→R）∨S） （（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）?（∧Q））（∧Q） 1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。 本例可表示为：（?P→Q）∧（P→（R∨S））。 1.3.3 命题公式的解释定义 设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。 例如， 是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。 1.4 真值表与等价公式 1.4.1 真值表 定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。的幺元为（ ）。
华南农业大学 离散数学 期末考试2013试卷及答案
离散数学必备知识点总结
离散数学复习要点
中国石油大学大学《离散数学》期末复习题及答案
离散数学重点笔记
离散数学知识点整理
大学离散数学期末重点知识点总结(考试专用)
离散数学期末复习要点与重点
离散数学笔记(特级教师精心整理)
- 离散数学期末考试题答案
- 离散数学期末试卷
- 大学《离散数学》期末考试试卷及答案-(1)
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末试卷A卷
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学(1)期末考试
- 离散数学期末试卷A卷
- 北京理工大学数学专业离散数学期末试题
- 厦门大学离散数学2015-2016期末考试试题答案年
- 离散数学期末试卷
- 《离散数学》期末复习题_69521457073107968
- 最新南昌大学_离散数学_期末试卷
- 华南农业大学 离散数学 期末考试2013试卷及答案
- 山东大学离散数学期末试题答案
- 《离散数学(本科)》2018-2019期末试题及答案
- 浙江师范大学离散数学期末试卷A
- 大学《离散数学》期末考试试卷及答案 (1)
- 大学离散数学期末重点知识点总结(考试专用)
- 大学《离散数学》期末考试试卷及答案-(1)