离散数学期末复习要点与重点大纲
(复习以课本和笔记为主。文中标红为需重点掌握的,祝大家都能取得好成绩!)
第1章 命题逻辑
复习要点
1.理解命题概念,会判别语句是不是命题.理解五个基本联结词:否定?P 、析取∨、合取∧、条件→、和双条件?及其真值表,理解其他联结词的定义及基本等价式,会将简单命题符号化.
具有确定真假意义的陈述句称为命题.
命题必须具备:其一,语句是陈述句;其二,语句有唯一确定的真假意义.
2.理解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法.能熟练地作公式真值表.理解永真式和永假式概念,掌握其判别方法.
判定命题公式类型的方法:其一是真值表法,其二是等价演算法.
3.了解公式等价概念,掌握公式的重要等价式和判断两个公式是否等价的有效方法:等价演算法、列真值表法和主范式方法.
4.理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念,熟练掌握它们的求法(真值表法和等价推导法).
命题公式的范式不惟一,但主范式是惟一的.
命题公式A 有n 个命题变元,A 的主析取范式有k 个小项,有m 个大项,则
n
m k 2=+ 于是有
(1) A 是永真式?k =2n (m =0); (2) A 是永假式?m =2n (k =0);
5.了解C 是前提集合{A 1,A 2,…,A m }的有效结论或由A 1, A 2, …, A m 逻辑地推出C 的概念.要理解并掌握推理理论的规则、重言蕴含式和等价式,掌握命题公式的证明方法:真值表法、直接证法、间接证法.
重点:命题与联结词,真值表,主析取(合取)范式,命题演算的推理理论.
第2章 谓词逻辑
复习要点
1.理解谓词、量词、个体词、个体域,会将简单命题符号化.
原子命题分成个体词和谓词,个体词可以是具体事物或抽象的概念,分个体常项和个体变项.谓词用来刻划个体词的性质或之间的关系.
量词分全称量词?,存在量词?.
命题符号化注意:使用全称量词?,特性谓词后用→;使用存在量词?,特性谓词后用∧.
2.了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念.掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法.
由原子公式、联结词和量词构成谓词公式.谓词公式具有真值时,才是命题.
在谓词公式?xA 或?xA 中,x 是指导变元,A 是量词的辖域.会区分约束变元和自由变元.
在非空集合D (个体域)上谓词公式A 的一个解释或赋值有3个条件.
在任何解释下,谓词公式A 取真值1,A 为逻辑有效式(永真式);公式A 取真值0,A 为永假式;至少有一个解释使公式A 取真值1,A 称为可满足式.
在有限个体域下,消除量词的规则为:设D ={a 1, a 2, …, a n },则
)(...)()()(21n a A a A a A x xA ∧∧∧??
)(...)()()(21n a A a A a A x xA ∨∨∨??
会求谓词公式的真值,量词的辖域,自由变元、约束变元,以及换名规则、代入规则等. 掌握谓词演算的等价式和重言蕴含式.并进行谓词公式的等价演算. 3.理解前束范式的概念,掌握求公式的前束范式的方法. 若一个谓词公式F 等价地转化成 B x Q x Q x Q k k ...2211,那么B x Q x Q x Q k k ...2211就是F 的前束范式,其中Q 1,Q 2,…,Q k 只能是?或?,而x 1, x 2, …, x k 是个体变元,B 是不含量词的谓词公式.前束范式仍然是谓词公式.
重点:翻译;前束范式.
第3章 集合与关系
复习要点
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 )等运算.
掌握集合运算律(运算的性质).
3.掌握用集合运算基本规律证明集合恒等式的方法.
集合的运算问题:其一是进行集合运算;其二是运算式的化简;其三是恒等式证明. 证明方法有二:(1)要证明A =B ,只需证明A ?B ,又A ?B ;
(2)通过运算律进行等式推导.
4.了解有序对和笛卡尔积的概念,掌握笛卡尔积的运算.
有序对就是有顺序二元组,如
注意:有序对≠,以a , b 为元素的集合{a , b }={b , a };有序对(a , a )有意义,而集合{a , a }是单元素集合,应记作{a }.
集合A ,B 的笛卡尔积A ×B 是一个集合,规定A ×B ={
5.理解关系的概念:二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图,掌握关系的集合运算及复合关系、逆关系的性质与求法.
二元关系是一个有序对集合,},{B y A x y x R ∈∧∈><=,记作xRy .
设A 、B 是两个集合,且|A|=m ,|B|=n ,则从A 到B 可产生的不同的二元关系个 数为nm
2。
关系的表示方法有三种:集合表示法, 关系矩阵:R ?A ×B ,R 的矩阵???
? ??==?????/==?n j m i b R a Rb a r r M j i j i ij n m ij R ,...,2,1,...,2,101,)(. 关系图:R 是集合上的二元关系,若∈R ,由结点a i 画有向弧到b j 构成的图形.
空关系?是唯一、是任何关系的子集的关系; 全关系},,{A b a b a E A ∈><=A A ?≡; 恒等关系},{A a a a I A ∈><=,恒等关系的矩阵M I 是单位矩阵.
关系的集合运算有并、交、补、差和对称差. 复合关系}),,(,{2121R c b R b a b c a R R R >∈<∧>∈><== ;
复合关系矩阵:21R R R M M M ?=(按逻辑运算);
有结合律:(R S ) T =R (S T ),一般不可交换. 逆关系},,{1R y x x y R >∈<><=-;
逆关系矩阵满足:T R R M M =-1;
复合关系与逆关系存在:(R S )-1=S -1 R -
1.
6.理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示),掌握其判别方法(利用定义、矩阵或图,充分条件),知道关系闭包(自反,对称,传递)的定义和求法.
注:(1)关系性质的充分必要条件:
① R 是自反的?I A ?R ;
②R 是反自反的?I A ?R =?;
③R 是对称的 ?R =R -1;
④R 是反对称的?R ?R -1?I A ;
⑤R 是传递的?R R ?R .
(2)I A 具有自反性,对称性、反对称性和传递性.E A 具有自反性,对称性和传递性.?具有反自反性、对称性、反对称性和传递性.
重点:集合的运算,笛卡尔积,关系的性质,复合关系和逆关系,关系的闭包.
第4章 函数
复习要点
1.理解函数概念:函数(映射),函数相等,复合函数和反函数.理解单射、满射和双射等概念,掌握其判别方法.
设f 是集合A 到B 的二元关系,?a ∈A ,存在惟一b ∈B ,使得∈f ,且Dom(f )=A ,f 是一个函数(映射).函数是一种特殊的关系(设A 、B 是两个集合,且|A|=m ,|B|=n ,则从A 到B 可产生的不同的函数关系个数为m
n ) .
集合A ×B 的任何子集都是关系,但不一定是函数.函数要求对于定义域A 中每一个元素a ,B 中有且仅有一个元素与a 对应,而关系没有这个限制.
二函数相等是指:定义域相同,对应关系相同,且定义域内的每个元素的对应值都相同.
函数有:单射——若)()(2121a f a f a a ≠?≠;
满射——f (A )=B 或,,A x B y ∈?∈?使得y =f (x );
双射——单射且满射.
复合函数,:,:,:C A f g C B g B A f →→→ 则 即))(()(x f g x f g = .
复合成立的条件:)(Dom )(Ran g f ?.一般g f f g ≠,但f g h f g h )()(=. 反函数——若f :A →B 是双射,则有反函数f -1:B →A ,
},)(,,{1A a b a f B b a b f ∈=∈><=-,f f g f f g ==-----11111)(,)( 重点:函数.
第5章 代数结构
复习要点
1.掌握代数系统中运算及其性质(自反,对称,传递,等幂),会判断某代数系统具有哪种性质。
2. 掌握半群,独异点,群,阿贝尔群,循环群的概念及判定方法。
半群:封闭+可结合。
独异点:封闭+可结合+有幺元。
群:封闭+可结合+有幺元+每个元素有逆元。
阿贝尔群:群+可交换。
循环群:群+有生成元。
3. 掌握同态与同构的概念,理解同态的相关性质,并熟练掌握同态与同构的证明方法。 重点:代数系统的运算性质,群与循环群的证明方法,同构与同态的证明方法。
第7章 图的基本概念
复习要点
1.理解图的概念:结点、边、有向图,无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理.
图是一个有序对
掌握无向边与无向图,有向边与有向图,混合图,零图,平凡图、自回路(环),无向平行边,有向平行边等概念.
简单图,不含平行边和环(自回路)的图、
在无向图中,与结点v (∈V )关联的边数为结点度数deg (v );在有向图中,以v (∈V )为终
点的边的条数为入度deg -(v ),以v (∈V )为起点的边的条数为出度deg +(v ),deg(v )=deg +(v )
+deg -(v ).
无向完全图K n 及其边数)1(2
1-=n n E ;有向完全图及其边数)1(-=n n E . 了解子图、真子图、补图的概念. 知道图的同构概念,更应知道图同构的必要条件,用其判断图不同构.
重要定理:
(1) 握手定理 设G =
∑∈=V v E v 2)deg(; (2) 在有向图D =
;
(3) 奇数度结点的个数为偶数个.
2.了解路与回路概念.会求路和回路的长度.
了解无向图的连通性,会求无向图的连通分支.了解点割集、边割集、割点、割边等概念.了解有向图的强连通强性;会判别其类型.
设图G =
无向图G 中,结点u , v 存在通路,u , v 是连通的,G 中任意结点u , v 连通,G 是连通图.P (G )表示图G 连通分支的个数.
要知道:强连通??→?必是
单侧连通??→?必是弱连通,反之不成立. 3.掌握邻接矩阵,可达矩阵和距离矩阵的概念,掌握其构造方法及其应用.
4.理解欧拉通路(回路)、欧拉图的概念,掌握欧拉图的判别方法.
通过连通图G 的每条边一次且仅一次的路(回路)是欧拉路(回路).存在欧拉回路的图是欧拉图.
欧拉回路要求边不能重复,结点可以重复.笔不离开纸,不重复地走完所有的边,走过所有结点,就是所谓的一笔画.
欧拉图或通路的判定定理
(1) 无向连通图G 是欧拉图?G 为连通图且G 不含奇数度结点(即G 的所有结点为偶数度);
(2) 非平凡图G 含有欧拉路?G 为连通图且G 最多有两个奇数度的结点;
(3) 连通有向图D 含有有向欧拉回路?D 中每个结点的入度=出度.
(4) 连通有向图D 含有有向欧拉路?D 中除两个结点外,其余每个结点的入度=出度,且此两点满足一个结点的入度比出度大1,另一个结点的出度比入度大1.
5.了解汉密尔顿路(回路)、汉密尔顿图的概念,会做简单判断.
通过连通图G 的每个结点一次,且仅一次的路(回路),是汉密尔顿路(回路).存在汉密尔顿回路的图是汉密尔顿图.
汉密尔顿图的充分条件和必要条件
(1) 在无向简单图G =
(2) 有向完全图D =
(3) 设无向图G =
若此条件不满足,即存在V 1?V ,使得P (G -V !)>∣V 1∣,则G 一定不是汉密尔顿图(非汉密尔顿图的充分条件).
6.了解树、树叶、生成树和最小生成树等概念,掌握求最小生成树的方法.
连通无回路的无向图是树.树的判别可以用图T 是树的充要条件(等价定义).
注意:(1) 树T 是连通图; (2)树T 满足m =n -1(即边数=顶点数-1).
图G 的生成子图是树,该树就是生成树.
每边指定一正数,称为权,每边带权的图称为带权图.G 的生成树T 的所有边的权之和是生成树T 的权,记作W (T ).最小生成树是带权最小的生成树.
7.了解有向树、根树等概念.
有向图删去边的方向为树,该图为有向树.
对非平凡有向树,恰有一个结点的入度为0(该结点为树根),其余结点的入度为1,该树为根树.
有关树的求法:
(1)生成树的破圈法和避圈法求法;
(2)最小生成树的克鲁斯克尔求法;
重点:图的概念,握手定理,路、回路以及图的矩阵表示,欧拉图和哈密顿图的基本概念及判别,树与根树的基本概念,最小生成树的求法.
离散数学必备知识点总 结 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、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做,检验一下第一遍与第二遍复习情况,要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1.下列句子中,()是命题。 A.2是常数。B.这朵花多好看呀! C.请把门关上!D.下午有会吗? 2.令p: 今天下雪了,q:路滑,r:他迟到了。则命题“下雪路滑,他迟到了” 可符号化为()。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3.令:p今天下雪了,:q路滑,则命题“虽然今天下雪了,但是路不滑”可符号化为()。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4.设() Q x:x会飞,命题“有的鸟不会飞”可符号化为()。 P x:x是鸟,() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y:x大于等于y;命题“所有整数 f x:x的绝对值,(,) P x:x是整数,() 的绝对值大于等于0”可符号化为()。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人,() G x:x犯错误,命题“没有不犯错误的人”符号化为()。 A.(()()) ??→? x F x G x ?∧B.(()()) x F x G x C.(()()) ??∧? x F x G x ??∧D.(()()) x F x G x 7.下列命题公式不是永真式的是()。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8.设() R x:x为有理数;() Q x:x为实数。命题“任何有理数都是实数”的符号化为()
离散数学复习要点第一章命题逻辑 一、典型考查点 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.无 8.设P:他聪明,Q:他用功,命题“他虽聪明但不用功”的符号化正确的是()
第一章,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、下列各选项错误的是 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=
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:小王穿羽绒服。只有天冷,小王才穿羽绒服.符号化为
离散数学 一、逻辑和证明 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也是可数的。
离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程,共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。
离散数学习题参考答案 第一章集合 1.分别用穷举法,描述法写出下列集合 (1)偶数集合 (2)36的正因子集合 (3)自然数中3的倍数 (4)大于1的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } 2.确定下列结论正确与否 (1)φ∈φ× (2)φ∈{φ}√ (3)φ?φ√ (4)φ?{φ}√ (5)φ∈{a}× (6)φ?{a}√ (7){a,b}∈{a,b,c,{a,b,c}}× (8){a,b}?{a,b,c,{a,b,c}}√(9){a,b}∈{a,b,{{a,b}}}× (10){a,b}?{a,b,{{a,b}}}√ 3.写出下列集合的幂集 (1){{a}} {φ, {{ a }}} ( 2 ) φ {φ} (3){φ,{φ}} {φ, {φ}, {{φ}}, {φ,{φ}} } (4){φ,a,{a,b}} {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (5)P(P(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } 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× (4)若A?B,且B∈C,则A?C × 5.对任意集合A,B,C,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y
《离散数学》复习题 一、单项选择题 1.下列句子是原子命题的是( A) A. 大熊猫产在我国; B. 2+x=5; C. 小王和小李是学生; D. 别讲话了! 2. 设p:天下雨,q:我去新华书店,命题“除非天不下雨,我去新华书店”的符号化形式为( D ) A.p→qB.q→pC.┐q→pD.┐p→q 3. 以下命题不是重言式的有(A ) ?P B. P∨?P A. P∧ C. (P→Q)?(?Q→?P) D. P→P∨Q 4. 以下语句中不是命题的为(B) A.明天我要上门去谢你。B.谢谢你给了我机会。 C.如果不说,我就不谢你。D.除非你做了,我才谢你 5.与(x) M(x) 等价的是 (D) A.(x) M(x) B.(x) M(x) C.(x) M(x) D.(x) M(x) 6. 设P(x)为“x是大学生”,Q(x)为“x满30岁”。命题“所有大学生都不满30岁”写成谓词公式为( C ) A. ?x(P(x)∧Q(x)) B.? x(P(x)∧Q(x)) ?(P(x)→Q(x)) D.? x(P(x)→Q(x)) 7.公式 (x) (P(x)→(y)R(x, y))中,x的辖域为 ( B ) A.P(x) B.(P(x)→(y)R(x, y))
C.P(x)和R(x, y) D.P(x)→(y) 8.设S={a, b, c},则S的幂集的元素的个数有 ( C ) A.3 B.6 C. 8 D.9 9.以下等式中不正确的是: ( A ) A.A∪(B×C)=(A∪B)×(A∪C) B.A×(B∪C)=(A×B)∪(A×C) C.(A∪B)×C=(A×C)∪(A×C) D(A×B)×C=A×(B×C) 10.设A={1, 2, 3, 4}, A上的等价关系R={<1, 2>, <2, 1>, <3, 4>, <4, 3>}∪I A, 则对应于R的A的划分是 ( D ) A.{{1},{2, 3}, {4}} B.{{1, 2},{3}, {4}} C.{{1},{2}, {3}, {4}} D.{{1,2}, {3, 4}} 11.设函数f:{1,2}→{1},则f是 ( B ) A.入射B.满射C.双射D.非入射非满射 12.设Z-是负正整数集合,+,-,*,△是普通数的加法、减法和平方运算,则能构成代数系统是 ( B ) A.< Z-, +> B.< Z-, -> C.< Z-, *> D< Z-, △> 13.若他聪明,他用功,则“他虽聪明但不用功”,可符号化为( B ) A. B. C. D. 14. 若一个代数系统(A,*)满足运算封闭性及结合律,且有幺元,则它是 ( A ) A.独异点B.群C.格D.布尔代数15.设G为无限群,则( C )
一、单项选择题 1.对任意集合A 、B 、C ,下述论断正确的是 【 A 】 (A )若A ∈B ,B ?C ,则 A ∈C (B )若A ∈B ,B ?C ,则 A ?C (C )若A ?B ,B ∈C ,则 A ∈C (D )若A ?B ,B ∈C ,则 A ?C 2.设{} {}a a A ,=,则下列选项错误的是 【 B 】 (A ){})(A P a ∈ (B ){})(A P a ? (C ){}{ })(A P A ∈ (D ){}{})(A P A ? 3.设{}c b a A ,,=上的关系如下,有传递关系的有 【 D 】 (A ){}><><><><=a b b a a c c a R ,,,,,,,1 (B ){}><><=a c c a R ,,,2 (C ){}><><><><=c b a b c c b a R ,,,,,,,3 (D ){},,4><=a a R 4.R 是A 上的自反关系,则 【 B 】 (A )R R R ? (B )R R R ? (C )A I R R = (D )A I R R = 5.4K 中含3条边的不同构生成子图有 【 C 】 (A )1个 (B )2个 (C )3个 (D )4个 6.设E V G ,=为无向图,V v u ∈,,若v u ,连通,则 【 D 】 (A )0),(>v u d (B )0),(=v u d (C )0),( 离散数学期末试题及答 案 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的补元( ). 《离散数学》试题及答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答:(1),(4) 2、下列公式中哪些是永真式?( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)?B(y,x))??z C(y,z))?D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z 5、判断下列语句是不是命题。若是,给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗? (4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧! 答:(1)是,T (2)是,F (3)不是 (4)是,T (5)不是(6)不是 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1)P ?(4)Q P→ ? P? Q→ ?(2)Q P? →(3)Q 8、设个体域为整数集,则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答:(1)对任一整数x存在整数 y满足x+y=0(2)存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合,确定下列命题的真值: (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式?x(P(x)?Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是()。 答:2不是偶数且-3不是负数。 12、永真式的否定是() (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能 答:(2) 13、公式(?P∧Q)∨(?P∧?Q)化简为(),公式 Q→(P∨(P∧Q))可化简为()。 答:?P ,Q→P 14、谓词公式?x(P(x)??yR(y))→Q(x)中量词?x的辖域是()。 答:P(x)??yR(y) 15、令R(x):x是实数,Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为()。 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={离散数学期末试题及答案完整版
《离散数学》复习题及答案
大学离散数学期末重点知识点总结(考试专用)