离散数学第一章知识点总结(仅供参考)
1.判断给定的句子是否为命题的基本步骤:首先应是陈述句;其次要有唯一的真值。
例:(1)我正在说谎。
不是命题。因为无法判定其真假值,若假设它为假即我正在说谎,则意味着它的反为真,即我正在说实话,二者相矛盾;若假定它为真即我正在说实话,则意味着它的反为假,我正在说谎,二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题
(2)x-y >2。
不是命题。因为x, y的值不确定,某些x, y使x?y>2为真,某些x, y使x?y>2为假,即x?y>2的真假随x, y的值的变化而变化。因此x?y>2的真假无法确定,所以x?y>2不是命题。
2.命题可以分为两种类型:原子命题(不能再分解为更简单命题,又可称为简单命题);
复合命题(通过联结词、标点符号将原子命题联结而成的命题)
3.命题常元:一个命题标识符如果表示确定的简单命题,就称为命题常元
命题变元:如果一个命题标识符只表示任意简单命题的位置标志,就称它为命题变元
注:当命题变元P用一个特定的简单命题取代时,P才能确定真值,这时也称对P进行指派
4.联接词:(1)否定联接词:﹁假为真,真为假;还可以用“非”、“不”、“没有”、“无”、
“并不”等多种方式表示否定
(2)合取联接词:∧一个为假就为假还可用“并且”、“同时”、“以及”、“既……
又……”、“不但……而且……”、“虽然……但是……”等多种方
式表达合取
(3)析取联接词:∨一个为真就为真;一般用或表示
注:联结词∨是可兼或,因为当命题P和Q的真值都为真时,
其值也为真。但自然语言中的“或”既可以是“排斥或 ”
也可以是“可兼或 ”。
例1.6 晚上我们去教室学习或去电影院看电影。(排斥或)
例1.7 他可能数学考了100分或英语考了100分。(可兼或) 例1.8 刘静今天跑了200米或300米远。(既不表示“可兼或”
也不表示“排斥或”,它只是表示刘静所跑的大概路程,
因此它不是命题联结词,故例1.8是原子命题。)
(4)蕴涵联结词:? 前真后假才为假;还可以用当……则……、因为……所
以……、仅当、只有……才……、除非……才……、除非……、
否则非 ……表示
(5)等价联接词:? 同真同假才为真;还可以用当且仅当、充分必要表示
5.命题公式:1)单个命题变元是合式公式,并简称为原子命题公式;
2)如果A是合式公式,那么(﹁A)也是合式公式;
3)如果A, B都是合式公式,那么(A∧B ), (A∨B ), (A?B ), (A B )都是合式
公式;
4)当且仅当有限次地应用1), 2), 3)所得到的包含命题变元、联结词和括号的字
符串是合式公式。
根据定义1.6可知,P, (﹁P ), (P ? (P∨Q )), ((﹁P∧Q )∧P ), ((P ? Q ) ?R )
都是命题公式。而 (∨P ), (P ?Q, (P ∨Q ) ? R )都不是命题公式。
6.n元命题公式:一个命题公式中总共包含有n个不同的命题变元
7. 1)若公式A是单个的命题变元,则称A为0层公式。
2)称A是n+1(n≥0)层公式是指下面情况之一:
(1)A=﹁B, B是n层公式;
(2)A=B∧C,其中B, C分别为i层和j层公式,且n=max(i,j);
(3)A=B∨C,其中B, C的层次同(2);
(4)A=B?C,其中B, C的层次同(2);
(5)A=B?C,其中B, C的层次同(2);
3)若公式A的层次为k,则称A是k层公式。
例1.19 (﹁P∧Q)?R为3层公式。
(﹁(P?﹁Q))∧((R∨S) ?﹁P) 为4层公式。
8.真值表p17可分为重言式(永真式)、矛盾式(永假式)、可满足式
9.逻辑等价:若对出现在A与B中的所有命题变元的任一组赋值,公式A和B的真值都相
同,则称公式A与B是逻辑等价或称逻辑相等,记作A B.
逻辑等价公式(熟记):1)双重否定 A ﹁﹁A
2)幂等律AA∨A 、AA∧A
3)交换律A∨BB∨A、 A∧BB∧A
4)结合律 (A∨B)∨CA∨(B∨C) 、(A∧B)∧CA∧(B∧C)
5)分配律 A∨(B∧C) (A∨B)∧(A∨C) (∨对∧的分配律)
A∧(B∨C) (A∧B)∨(A∧C) (∧对∨的分配律)
6)德摩根律﹁(A∨B) ﹁A∧﹁B
﹁(A∧B) ﹁A∨﹁B
7)吸收律 A∨(A∧B) A
A∧(A∨B) A
8)零律 A∨11 、A∧00
9)同一律 A ∧ 1A 、A ∨ 0A
10)排中律A∨﹁A1
11)矛盾律 A ∧ ﹁A0
12)蕴涵律 A→B﹁A∨B
13)等价律A B(A→B)∧(B→A)
14)假言易位律A→B﹁B→﹁A
15)等价否定律A ? B﹁A?﹁B
16)归谬律 (A→B)∧(A→﹁B) ﹁A
10.逻辑蕴含:设A、B是任意公式,若A→B是重言式,则称A逻辑蕴涵B,记为AB
逻辑蕴含公式(熟记):1)附加律A (A∨B)
2)化简律(A∧B )A
3)假言推理 (A→B)∧A B
4)拒取式 (A→B)∧﹁B ﹁A
5)析取三段论 (A∨B)∧﹁B A
6)假言三段论(A→B)∧(B→C)(A→C)
11.对偶:在给定的仅使用联结词﹁, ∧, ∨的命题公式A中,若把∧和∨互换,0和1互换
而得到一个命题公式A*,则称A*是A的对偶式。
显然,A也是A*的对偶式;可见,A*和A互为对偶式且(A*)*=A
注:设A和B是两个命题公式,若AB,则A*B*
12.范式:1)一个简单析取式是重言式当且仅当它同时含某个命题变元及它的否定式。
2)一个简单合取式是矛盾式当且仅当它同时含某个命题变元及它的否定式。
析取、合取范式:1)由有限个简单合取式构成的析取式称为析取范式。
2)由有限个简单析取式构成的合取式称为合取范式。
3)析取范式与合取范式统称为范式。
主范式、极小值、极大值p35-p37
求主析取范式、主合取范式的四个方法:p37-39
13.有效结论:设A1,A2,…,Ak和B都是命题公式,若对于A1,A2,…,Ak和B中出现的命题
变元的任意一组赋值,
或者A1∧A2 ∧…∧Ak为假,
或者当A1∧A2 ∧…∧Ak为真时,B也为真,
则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的,并称B是有效结论。
判断推理有效性的方法:(1)真值表法、(2)逻辑等价演算法、(3)主析(合)取范式法
14.命题演算推证的命题定律(9、10)和推理定律(熟记)p43
15.题演算推证由三个要素组成:推理根据、推理规则和证明方法。
1)推理根据 :命题演算推证的命题定律和推理定律;即主要指已知的基本逻辑等价式和
逻辑蕴涵式(见表1.17)
2)推理规则:
(1) 前提引入规则(P规则):在推证的任何步骤上都可以引入前提。
(2) 结论引入规则(T规则):在推证的任何步骤上所得到的结论都可以作为后继
证明的前提。
(3)附加前提规则(CP规则):若从A和B能有效地推出C,则从A可有效地推
出B→C。(通常在结论为蕴涵式时使用)
例:构造下列推理的证明:
前提:(﹁P ? Q ),(P ?R ),(﹁Q∨S )
结论:S∨R。
证:(1) ﹁P →Q P
(2) ﹁Q∨S P
(3) Q→ S T (2) E
(4) ﹁P→ S T (1)(3) I
(5) ﹁S →P T (4) E
(6) P →R P
(7) ﹁S→R T (5)(6) I
(8) ﹁﹁S∨R T (7) E
(9) S∨R T (8) E
证毕
3)证明方法:a.直接证明法,如前例
b.反证法:设命题公式集合{A1, A2, …, Am}是相容的,那么从{A1,
A2, …,Am}出发可逻辑地推出结论B的充分必要条件是从{A1,
A2, …, Am,﹁B}可逻辑地推出一个矛盾式。
例:如果今天我没课,则我去机房上机或去图书馆查资料;若机房没有空机器,则我没
法去上机;今天我没课,机房也没有空机器,所以我去图书馆查资料。
证:设P:今天我没课;
Q:我去机房上机;
R:我去图书馆查资料;
S:机房没有空机器
则上述语句可翻译为命题关系式: P→Q∨R, S→﹁Q, P, S R
(1) ﹁R P(结论的否定)
(2) P→Q∨R P
(3) P P
(4) Q∨R T (2)(3) I
(5) Q T (4)(1) I
(6) S →﹁Q P
(7) S P
(8) ﹁Q T (6)(7) I
(9) Q∧﹁Q T (5)(8) I
证毕
c)附加前提证法:由(S∧B)C证得S(B→C),就是前面提到的CP规则;其中
的B称为附加前提。
例:试证明(P∨Q) ∧(P→R)∧(R→﹁S) S→Q.
证: (1) P →R P
(2) R →﹁S P
(3) P →﹁S T (1)(2) I
(4) S CP
(5)﹁P T (3)(4) I
(6) P∨Q P
(7)Q T (5)(6) I
证毕
16.常见提醒解析p48-p50
第二篇:数学第一章知识点总结
小学数学知识点百分数的总结
(一)百分数的基本概念
1.百分数的定义:表示一个数是另一个数的百分之几的数,叫做百分数。百分数也叫做百分率或百分比。 百分数表示两个数之间的比率关系,不表示具体的数量,所以百分数不能带单位。
3.百分数通常不写成分数形式,而在原来分子后面加上“%”来表示。分子部分可为小数、整数,可以大于100,小于100或等于100。
4.小数与百分数互化的规则:
把小数化成百分数,只要把小数点向右移动两位,同时在后面添上百分号;
把百分数化成小数,只要把百分号去掉,同时把小数点向左移动两位。
5.百分数与分数互化的规则:
把分数化成百分数,通常先把分数化成小数(除不尽的保留三位小数),再把小数化成百分数;
把百分数化成分数,先把百分数改写成分数,能约分的要约成最简分数。
(二)百分数应用题
百分数应用题(一)
求增加百分之几?减少百分之几?
公式:增加百分之几=增加的部分÷单位1
减少百分之几=减少的部分÷单位1
例如:1、45立方厘米的水结成冰后,冰的体积为50立方厘米,冰的体积比原来水的体积增加百分之几? 解题思路:根据公式增加百分之几=增加的部分÷单位1,先确定单位1是水,已经知道是45:增加的部分不知道,可以利用50减45求得5;最后用增加的部分5÷单位1水的45就等于增加百分之几。
计算步骤:第一步:单位1:水:45立方厘米
第二步:增加的部分:50—45=5立方厘米
第三步:增加百分之几:5÷45=11.1%
2、45立方厘米的水结成冰后,体积增加了5立方厘米,冰的体积比原来水的体积增加百分之几?
解题思路:根据公式增加百分之几=增加的部分÷单位1,先确定单位1是水,已经知道是45:增加的部分是5立方厘米;最后用增加的部分5÷单位1水的45就等于增加百分之几。
计算步骤:第一步:单位1:水:45立方厘米
第二步:增加的部分: 5立方厘米
第三步:增加百分之几:5÷45=11.1%
3、水结成冰后,体积增加了5立方厘米,冰的体积为50立方厘米,冰的体积比原来水的体积增加百分之几? 解题思路:根据公式增加百分之几=增加的部分÷单位1,先确定单位1是水,不知道但可以根据题目“水结成冰后,体积增加了5立方厘米”知道水是少的,冰是多的,所以可以用50—5求出水是45立方厘米。加的部分是5立方厘米;;最后用增加的部分5÷单位1水的45就等于增加百分之几。
计算步骤:第一步:单位1:水:50—5=45立方厘米
第二步:增加的部分: 5立方厘米
第三步:增加百分之几:5÷45=11.1%
4、“减少百分之几与增加百分之几”的解题方法完全相同。
5、与增加百分之几相同的还有“多百分之几”“提高百分之几”
“增长百分之几“等。
与减少百分之几相同的还有“少百分之几”“降低百分之几”“节约百分之几”等。
百分数应用题(二)
比一个数增加百分之几的数,比一个数减少百分之几的数。
例如1、矣得小学去年有80名学生,今年的学生人数比去年增加了25%,今年有多少名学生?
解题思路:单位1去年已经知道用乘法,增加用(1+25%)
算式:80×(1+25%)
2、矣得小学去年有80名学生,今年的学生人数比去年减少了25%,今年有多少名学生?
解题思路:单位1去年已经知道用乘法,减少用(1-25%)
算式:80×(1-25%)
3、矣得小学今年有100名学生,比去年增加了25%,去年有多少名学生?
解题思路:单位1去年不知道用除法,增加用(1+25%)
算式:100÷(1+25%)
4、矣得小学今年有100名学生,比去年减少了25%,去年有多少名学生?
解题思路:单位1去年不知道用除法,增加用(1-25%)
算式:100÷(1-25%)
百分数应用题(三)列方程解百分数应用题
1、小明看一本书,第一天看了全书的25%,第二天看了全书的20%,第一天比第二天多看20页,这本书一共有多少页?
解题思路:单位1一本书不知道,可以选用方程或除法来解答。
根据“第一天比第二天多看20页”可以知道第一天是多的,第二天是少的,第一天减去第二天等于多出的20页。
等量关系式:第一天—第二天=20页
方法1:解:设这本书一共有X页。
由“第一天看了全书的25%”可以知道第一天等于全书乘以25%,用X可以表示为25%X,由“第二天看了全书的20%”可以知道第二天等于全书乘以20%,用X可以表示为20%X.依据等量关系式“第一天—第二天=20页”可以列方程为:25%X—20%X=20
方法2:“第一天比第二天多看20页”可以知道20页是第一天和第二天的差。要求单位1只要用20页除以20页的对于分率。
列算式为:20÷(25%—20%)
2、小明看一本书,第一天看了全书的25%,第二天看了全书的20%,两天共看了20页,这本书一共有多少页? 等量关系式:由“两天共看了20页”可以知道第一天+等二天=20页。
方程法:解:设这本书共有X页,则第一天为25%X,第二天为20%X。
方程列为:25%X+20%X=20
算术法:由“两天共看了20页”可以知道20页是第一天和第二天的和,要求单位1只要用20页除以20页的对于分率。
列算式为:20÷(25%+20%)
3、小明看一本书,第一天看了全书的25%,第二天看了全书的20%,还剩20页,这本书一共有多少页? 等量关系式:一本书—第一天—第二天=20页
方程法:解设这本书一共有X页,则第一天为25%X,第二天为20%X。
列方程为:X—25%X—20%X=20
算术法:20÷(1- 25%X- 20%)
4、小明看一本书,第一天看了全书的25%,第二天比第一天多看10页,还剩20页,这本书一共有多少页? 方程法:解设这本书一共有X页,则第一天为25%X,第二天为(25%X+10)页。
列方程为:X—25%X—(25%X+10)=20
百分数应用题(四)利息的计算
1.本金:存入银行的钱叫做本金。
2.利息:取款时银行多支付的钱叫做利息。
利息=本金×利率×时间
3.20xx年x月x日以前国家规定,存款的利息要按20%的税率纳税。国债的利息不纳税。20xx年x月x日以后免收利息税。所以如无特殊说明,就不在计算利息税。
4.利率:利息与本金的比值叫做利率。
5.银行存款税后利息的计算公式:税后利息=利息×(1-20%)
6.国债利息的计算公式:利息=本金×利率×时间
7.本息:本金与利息的总和叫做本息。
8.应纳税额:缴纳的税款叫应纳税额。
9.税率:应纳税额与各种收入的比率叫做税率。
10.应纳税额的计算:应纳税额=各种收入×税率
例如:李老师把20xx元钱存入银行,整存整取五年,年利率按4.14%计算,到期时,李老师的本金和利息共有多少元?
解题思路:要求“本金和利息共有多少元”应该用本金的20xx元加上利息的。
解题步骤:第一步:根据“利息=本金×利率×时间”算利息
利息:20xx×4.14%×5=414元
第二步:本金+利息:20xx+414=2414元。
例如:李老师把20xx元钱存入银行,整存整取五年,年利率按4.14%计算,到期时,李老师的本金和利息共有多少元?(如果利息按20%来上税)
解题思路:要求“本金和利息共有多少元”应该用本金的20xx元加上利息的。
解题步骤:第一步:根据“利息=本金×利率×时间”算利息
利息:20xx×4.14%×5=414元
第二步:算税后利息:414×(1—20%)=331.2元
本金+利息:20xx+331.2=233.2元。
第三篇:离散数学知识点
第一章
1. 将下列命题符号化: 解:令p:天下雨,q:我骑自行车上班,则
(1)只要不下雨,我就骑自行车上班 ?p是q的充分条件,所以符号化为:?p→q
(2)只有不下雨,我才骑自行车上班 ?p是q 的必要条件,所以符号化为:q→? p
(3)除非下雨,否则我就骑自行车上班 ?p仍然是q的充分条件,所以符号化为:?p→q
(4)如果下雨,我就不骑自行车上班 p是?q的充分条件,所以符号化为:p→?q
2.命题: 判断结果惟一的陈述句(注意: 感叹句、祈使句、疑问句都不是命题
陈述句中的悖论以及判断结果不惟一确定的也不是命题)
3.p?q为假当且仅当 p 为真 q 为假
4.p?q (q 为 p 的必要条件)
“如果 p,则 q ” 的不同表述法很多:
若 p,就 q
只要 p,就 q
p 仅当 q
只有 q 才 p
除非 q, 才 p 或 除非 q, 否则非 p
因为….所以
5.p?q为真当且仅当p与q同真或同假
6. p 0层
?p 1层
?p?q 2层
?(p?q)?r 3层
((?p?q) ?r)?(?r?s) 4层
7.双重否定律 ??A?A
等幂律: A?A?A, A?A?A
交换律: A?B?B?A, A?B?B?A
结合律: (A?B)?C?A?(B?C) (A?B)?C?A?(B?C)
分配律: A?(B?C)?(A?B)?(A?C) A?(B?C)? (A?B)?(A?C)
德·摩根律: ?(A?B)??A??B ?(A?B)??A??B
吸收律: A?(A?B)?A, A?(A?B)?A
零律: A?1?1, A?0?0
同一律: A?0?A, A?1?A
排中律: A??A?1
矛盾律: A??A?0
蕴涵等值式: A?B??A?B
等价等值式: A?B?(A?B)?(B?A)
假言易位: A?B??B??A
等价否定等值式: A?B??A??B
归谬论: (A?B)?(A??B) ??A
设A,B为两个命题公式,若A ? B,则A* ? B*.
9.求公式A的范式的步骤:
(1) 消去A中的?, ?(若存在) (2) 否定联结词?的内移或消去
(3) 使用分配律 ?对?分配(析取范式) ?对?分配(合取范式)
(公式的范式存在,但不惟一)
10.设A含n个命题变项,则
A为重言式?A的主析取范式含2n个极小项
?A的主合取范式为1.
A为矛盾式? A的主析取范式为0
? A的主合取范式含2n个极大项
A为非重言式的可满足式
?A的主析取范式中至少含一个且不含全部极小项
?A的主合取范式中至少含一个且不含全部极大项
第二章
第三章
1.相对补 A?B = { x | x?A ? x?B }=A - (A?B)
对称差 A?B = (A?B)?(B?A)= (A?B)?(A?B)
绝对补 ?A = E?A
|A?A?...?A|12m m
|Ai?Aj|?|Ai?Aj?Ak|?... ?|S|?|Ai|?
i?11?i?j?m1?i?j?k?m m ?(?1)|A1?A2?...?Am|
第四章
1.R=M1 S=M2 R°S = M2 * M1
2.(1) (F?1)?1=F (2) domF?1=ranF, ranF?1=domF
(1) (F°G)°H=F°(G°H) (2) (F°G)?1= G?1°F?1
3.关系性质的充要条件 设R为A上的关系, 则
(1) R在A上自反当且仅当 IA ?R
(2) R在A上反自反当且仅当 R∩IA=?
(3) R在A上对称当且仅当 R=R?1
(4) R在A上反对称当且仅当 R∩R?1?IA
(5) R在A上传递当且仅当 R?R?R
4.定理1 设R为A上的关系, 则有
(1)自反闭包 r(R) = R∪R0
(2)对称闭包s(R) = R∪R?1
(3)传递闭报 t(R) = R∪R2∪R3∪…
5. Mr = M + E E 是和 M 同阶的单位矩阵, M’是 M 的转置矩阵.
Ms = M + M’ 注意在上述等式中矩阵的元素相加时使用逻辑加
Mt = M + M2 + M3 + … ???
6.集合A上的恒等关系 IA 是A上的偏序关系.
小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系
7.数集上的小于或等于关系是全序关系;整除关系不是正整数集合上的全序关系
8.哈斯图特点:每个结点没有环,两个连通的结点之间的序关系通过结点位置的高低表示,
位置低的元素的顺序在前,具有覆盖关系的两个结点之间连边
9.特殊元素的性质:
? 对于有穷集,极小元和极大元必存在,可能存在多个.
? 最小元和最大元不一定存在,如果存在一定惟一.
? 最小元一定是极小元;最大元一定是极大元.
孤立结点既是极小元,也是极大元
10.哈斯图应注意:
(1).哈斯图不应出现三角形
第七章
1.握手定理 任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所
有顶点入度之和等于出度之和等于边数
2.环是长度为1的圈, 两条平行边构成长度为2的圈
3.Kn无点割集
n阶零图既无点割集,也无边割集.
若G连通,E ?为边割集,则p(G?E ?)=2
若G连通,V ?为点割集,则p(G?V ?)?2
4.强连通?单向连通?弱连通
5. 定理(强连通判别法) D强连通当且仅当D中存在经过每个顶点至少一次的回路
定理(单向连通判别法) D单向连通当且仅当D中存在经过每个顶点至少一次的通路
6.无向图的关联矩阵性质:
(1) 每一列恰好有两个1或一个2
m (2)mij?d(vi)(i?1,2,...,n)j?1 mij?2m (3)
i,j (4)平行边的列相同
7.有向图的关联矩阵性质:
(1) 每一列恰好有一个1和一个-1
(2) 第i行1 的个数等于d+(vi), -1 的个数等于d-(vi)
(3) 1的总个数等于-1的总个数, 且都等于m (4) 平行边对应的列相同
8.有向图的邻接矩阵性质:
n(1)? (1)a?d(vi),i?1,2,...,nijj?1 n(1)?a?d(vj),j?1,2,...,n (2)iji?1
(1)(3)aij?m???D中长度为1的通路数 i,j
n (1)(4)a???D中长度为1的回路数iii?1 ??????
9有向图的可达矩阵性质:
P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1
第八章
1.定理8.1 无向图G=<V,E>是二部图当且仅当G中无奇圈
2.欧拉图的判别法
定理8.4 无向图G为欧拉图当且仅当G连通且无奇度顶点.
无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点
定理8.5 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.
有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出
度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.
3.环不影响图的欧拉性. 环与平行边不影响图的哈密顿性
4.定理8.6 设无向图G=<V,E>是哈密顿图, 则对于任意V1?V且V1??, 均有 p(G?V1)?|V1|.
5.定理8.7 设G是n阶无向简单图, 若任意两个不相邻的顶点的度数之和大于等于n?1, 则
G中存在哈密顿通路.
当n?3时, 若任意两个不相邻的顶点的度数之和大于等于n, 则G中存在哈密顿
回路, 从而G为哈密顿图.
6.定理8.10 (欧拉公式) 设G为n阶m条边r个面的连通平面图,则 n?m+r
=2
第九章
1.定理9.2 设T 是 n 阶非平凡的无向树,则T中至少有两片树叶
2.求带权图的最小生成树 检验:边数达到n-1 (n:顶点数)