离散数学期末复习
一、选择题
1、下列各选项错误的是
A、???
B、???
C、?∈{ ?}
D、??{? }
2、命题公式 (p∧q) →p 是
A、矛盾式
B、重言式
C、可满足式
D、等值式
3、如果是R是A上的偏序关系,R-1是R的逆关系,则R∪R-1是
A、等价关系
B、偏序关系
C、全序关系
D、都不是
4、下列句子中那个是假命题?
A、是无理数.
B、2 + 5 =8.
C、x + 5 > 3
D、请不要讲话!
5、下列各选项错误的是?
A、???
B、??{? }
C、?∈{ ?}
D、{? } ??
6、命题公式 p→(p∨q∨r)是?
A、重言式
B、矛盾式
C、可满足式
D、等值式
7、函数f : N→N, f(x)=x+5,函数f是
A、单射
B、满射
C、双射
D、都不是
8、设D=
A、强连通
B、单向连通
C、弱连通
D、不连通的
9、关系R1和R2具有反自反性,下面运算后,不能保持自反性的是
A、R1?R2
B、R1-1
C、R1?R2
D、R1-R2
10、连通平面图G有4个结点,3个面,则G有()条边。
A、7
B、6
C、5
D、4
二、填空题
1、将下面命题符号化。设p:天冷,q:小王穿羽绒服。只要天冷,小王就穿羽绒服.符号化为
2、将下面命题符号化,设p:天冷,q:小王穿羽绒服。因为天冷,所以小王穿羽绒服.符号化为
3、将下面命题符号化,设p:天冷,q:小王穿羽绒服。若小王不穿羽绒服,则天不冷.符号化为
4、将下面命题符号化,设p:天冷,q:小王穿羽绒服。只有天冷,小王才穿羽绒服.符号化为
5、将下面命题符号化,设p:天冷,q:小王穿羽绒服。除非天冷,小王才穿羽绒服.符号化为
6、将下面命题符号化,设p:天冷,q:小王穿羽绒服。除非小王穿羽绒服,否则天不冷.符号化为
7、将下面命题符号化,设p:天冷,q:小王穿羽绒服。小王穿羽绒服仅当天冷的时候.符号化为
8、将下面命题符号化,设p:天冷,q:小王穿羽绒服。如果天不冷,则小王不穿羽绒服.符号化为
9、设p:王蓉努力学习,q:王蓉取得好成绩。则
(1)命题“只要王蓉努力学习,她就会取得好成绩。”符号化为
。
(2)命题“王蓉取得好成绩,如果她努力学习。”符号化
为
。
(3)命题“只有王蓉努力学习,她才能取得好成绩。”符号化为
。
(4)命题“除非王蓉努力学习,否则她不能取得好成绩。”符号化
为
10、公式?xF(x)→?xF(x)的类型为
11、公式?xF(x)→(?x?yG(x,y)→?xF(x))的类型
为
12、公式?xF(x)→(?xF(x)∨?yG(y))的类型为
13、公式 (F(x,y)→R(x,y))∧R(x,y)的类型
14、公式?x?yF(x,y)→?x?yF(x,y)的类型为
15、公式?xF(x,y)的类型
16、令F(x):x是人,G(x):x犯错误.则命题“没有不犯错误的人”符号化为
17、令F(x):x是人,G(x):爱看电影.则命题“不是所有的人都爱看电影”符号化为
18、公式??x(M(x)∧F(x))的前束范式为:
19、公式?xF(x)∧??xG(x)的前束范式为:
20、公式?xF(x)∨??xG(x)的前束范式为
21、公式?xF(x)→?y(G(x,y)∧?H(y))的前束范式为
22、公式?x(F(x,y)→?y(G(x,y)∧H(x,z)))的前束范式为
23、集合A=?,B={1,{a,b}},C={?,{?}},D={2,2,2,3};则幂集
P(A)= ;P(B)= ;P(C)= ;P(D)= ;
24、设A={1,2,3}, B={a,b,c}
则A?B= ;
B?A = 。
25、设集合A={?}, 则P(A)?A= 。
26、设|A|=n, 则|A×A|= , A×A的子集
有个. 集合A上有个不同的二元关系.
27、设A={1,2}, 则E A= ;I A= 。
28、集合A={2,3,4,5,6,10,12,24},R是A上的整除关系,则R的极大元是,极小元是。
29、设A={1,2,3}上的关系 R={<1,1>,<1,2>,<1,3>,<3,3>} ,则关系R具备性质。
30、设集合A={1,2,3},关系R={<1,2>, < 2,1>, <2,3>,<3,3>}, 则自反闭包r(R)= , 对称闭包s(R)= 。31、已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有个顶点。
32、n阶无向完全图K n,边数m= 。
33、n阶有向完全图K n,边数m= 。
34、设无向图G 有10 条边, 3 度与4 度顶点各2 个, 其余顶点的度数均小于3, 则G 中至少有个顶点,在最少顶点的情况下,图G 的度数列,
??(G)= ,δ?(G)=
.
35、设无向图中有6 条边, 3 度与5 度顶点各一个, 其余的都
是2 度顶点, 则该图有个顶点。
36、已知n阶连通平面图G有r个面,则G的边数
m= 。
37、设A={1,2,3}上的关系 R={<1,2>,<2,3>,<3,1> } ,则R?R= 。
38、设F(x):x是兔子,M(x):y是乌龟,H(x,y): x比y跑得快,则命题“兔子比乌龟跑得快”符号
为
三、计算题
1、给出公式A= (q→p) ∧q→p的真值表。
2、给出公式A= (q→p) ∧q→p的真值表。
3、给出公式C= (p∨q) →?r的真值表
4、用等值演算法判断公式q∧?(p→q)的类型
5、求公式A=(p→?q)∨?r的析取范式与合取范式。
6、求公式B=(p→?q)→r的析取范式与合取范式。
7、求公式A=(p→?q)→r的主析取范式与主合取范式.
8、在一阶逻辑中将下面命题符号化
(1) 人都爱美;
(2) 有人用左手写字分别取(a) D为人类集合, (b) D为全总个体域.
9、在一阶逻辑中将下面命题符号化(1) 正数都大于负数
10、在一阶逻辑中将下面命题符号化(1) 有的无理数大于有的有理数
11、试画出4阶3条边的所有非同构的无向简单图
12、画出所有K4的所有非同构的生成子图。
13、给定下面的图(前两个为无向图, 后两个为有向图)的集合表示,画出它们的图形表示G1 = ?V1, E1?, 其
中, V1 = {v1,v2, v3,v4, v5}, E1 = {(v1,v2),(v2,v3),(v3,v4), (v3, v3), (v4,v5)};
G2 = ?V2, E2?, 其中V2 = V1, E2 =
{(v1, v2),(v2,v3),(v3, v4),(v4,v5),(v5,v1)};
D1 = ?V3, E3?, 其
中V3 = V1, E3 = {?v1,v2?, ?v2, v3?, ?v3,v2?
, ?v4, v5?, ?v5, v1?};D2 = ?V4, E4?, 其
中V4 = V1, E4 = {?v1,v2?, ?v2, v5?, ?v5,v2?
, ?v3, v4?, ?v4, v3?}.
14、先将图中各图的顶点标定顺序, 然后写出各图的集合表示.
15、写出图中各图的度数列, 对有向图还要写出出度列和入度列.
16、画一个简单无向图,使它是欧拉图,但不是哈密顿图。
17、已知集合A={a, b, c, d, e, f}和关系
R={,,,
画出偏序集的哈斯图。
18、设A={a, b, c, d}, R={,,,,
19、有向图D如图所示,写出D的邻接矩阵和可达矩阵
20、设A=Z+×Z+,在A上定义二元关系R如下:<
21、求公式(P∨Q)→R的主析取范式。
22、求公式?x(F(x)∧?yG(x,y,z))→?xH(x,y,z)的前束范式。
23、已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式.
24、设A={1,2,3,4}, 定义A上的关R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}。求R的关系矩阵M R和关系图G R?
华南农业大学期末考试试卷(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。