离散数学公式总结

1

SpongeBob SquarePants

基本等值式

1.双重否定律 A ? ┐┐A 2.幂等律 3.交换律 4.结合律

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∨(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

5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） 6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B 7.吸收律 8.零律

9.同一律 11.矛盾律

10.排中律 12.蕴涵等值式 13.等价等值式 14.假言

一些著名的数学公式 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 塞尔伯格迹公式 泰勒公式 乘法公式 二倍角公式 全期望公式 全概率公式 和差平方 和平方 和立方 外尔特征标公式 婆罗摩笈多公式 差平方 差立方 拉普拉斯展开 斯托克斯公式 斯特灵公式 斯科伦范式 柯西-阿达马公式 柯西积分公式 格林公式 格林第一公式 格林第二公式 欧拉-笛卡尔公式 欧拉公式 海伦公式 牛顿-寇次公式 立方和差 素数公式 蔡勒公式 角平分线长公式 诱导公式 默比乌斯反演公式

基本乘法公式及恒等式 （因式分解） 分配律 基本 和平方 三数 差平方 平方差 和立方 差立方 立方和 立方差 其他公式 立方和是数学公式的一种，它属于因式分解、乘法公式及恒等式，被普遍使用。立方和是指一个立方数，加上另一个立方数，即是它们的总和。公式如下：

同时

立方和被因式分解后，答案分别包含二项式及三项式，与立方差相同。此公式对几何学及工程学等有很大作用。 主验证

验证此公式，可透过因式分解，首先运用环的原理，设以下公式：

初中数学公式定理总结

1、 过两点有且只有一条直线 2、 两点之间线段最短 3、 同角或等角的补角相等 4、 同角或等角的余角相等

5、 过一点有且只有一条直线和已知直线垂直

6、 直线外一点与直线上各点连接的所有线段中，垂线段最短 7、 平行公理 经过直线外一点，有且只有一条直线与这条直线平行 8、 如果两条直线都和第三条直线平行，这两条直线也互相平行 9、 同位角相等，两直线平行 10、 11、 12、 13、 14、 15、 16、 17、 18、 19、 20、 21、

内错角相等，两直线平行 同旁内角互补，两直线平行 两直线平行，同位角相等 两直线平行，内错角相等 两直线平行，同旁内角互补 定理 三角形两边的和大于第三边 推论 三角形两边的差小于第三边

三角形内角和定理 三角形三个内角的和等于180° 推论1 直角三角形的两个锐角互余

推论2 三角形的一个外角等于和它不相邻的两个内角的和 推论3 三角形的一个外角大于任何一个和它不相邻的内角 全等三角形的对应边、对应角相等

22、 23、 24、 25、 26、

边角边公理(SAS) 有两边和它们的夹角对应相等的两个三角形全等 角边角公理( ASA) 有两角和它们的夹边对应相等的两个

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

离散数学标准化作业纸 专业班级 学号 姓名 第一章 命题逻辑的基本概念

一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！”

（4）刘红和魏新是同学。 （5）a+b

（6）你去图书馆吗？

（7）如果买不到飞机票，我哪儿也不去。

（8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！

二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3?2。 （3）只有2<1，才有3?2。 （4）除非2<1，才有3?2。 （5）除非2<1，否则3?2。 （6）2<1仅当3<2。 三、将下列命题符号化

(1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。

- 1 -

离散数学标准化作业纸 专业班级 学号 姓名 四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r) （2）（p?r）

第一讲 引言

一、课程内容

·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。

二、数理逻辑发展史

1. 目的

·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。 ·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

2. 数理

《离散数学》练习

福建农林大学东方学院

2009 ——2010 学年第一学期

第一篇 数理逻辑

一、填空题及单项选择题：

1、设解释I为：客体城D?{2,3}，

a2b,3f(2)3f(3),2P(2,2)1P(2,3)1P(3,2)0P(3,3) 0则P(a,f(a))?P(b,f(b))? ，?x?yP(x,y) 。

2、公式G?(P?(?Q?R))?Q的主析取范式为 。 3、下列命题等值式正确的是 【 】 （A）P?Q?(P?Q)?(Q?P)；

P?Q?(P?Q)?(P??Q)；（B）

（C）P?Q??Q??P； （D）P?Q?P??Q.

4、设命题公式G?(Q?P)?(?P?Q)，则G是 【 】 （A）可满足的； （B）永真的； （C）永假的； （D）析取范式

5、前提?xP(x)与?x(P(x)?Q(x))的有效结论是 【 】

命题演算

? 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

原始命题/原子命题 复合命题 逻辑连接词 否定/┐ 合取/∧ 析取/∨

条件/→（┐P∨Q）

双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)） 真值表 命题公式/公式 命题变元 命题演算

等价（自反性、对称性、传递性，等价变换法俗称“少林派”） 结合律 交换律 分配律

德·摩根律/反演律 双重否定率 代换

蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”） 对偶法则 对偶

不可兼析取（析取符上加一横，异或） 逆条件（条件符上加字母c） 与非/↑ 或非/↓

? ? ? ? ? ? ? ? ? ?

结合力（ ⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件 ） 析取范式 合取范式

主析取范式（∑=m∨…） 主合取范式（∏=M∧…） 直接推演 P规则 T规则

CP规则（俗称“北冥神功”） 间接推演/间接证明/反

第六章 图论基础

图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念

我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。 任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有(a,b)?(b,a)。 设A,B为两个集合，无序对的集合{(a,b)a?A?b?B}称为集合A与B的无序积（Unordered Product），记作A&B。无序积与有序积的不同在于A&B?B&A。

例如，设A??a,b?，B??0,1,2?，则A&B?{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)} ?B&A,A&A?{(a,a),(a,b),(b,b)}。 为了引出图的定义，我们先介绍如下的例子。

B start s=0,i =1 i=1 S i=11? Y N s

总结 离散数学知识点

第二章 命题逻辑

1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；

5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项；

7.n个变元共有2n个极小项或极大项，这2n为(0~2n-1)刚好为化简完后的主析取加主合取；

8.永真式没有主合取范式，永假式没有主析取范式；

9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则

①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑

1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;

3.既有存在又有全称量词时，先消存在量词，再消全称量词；