离散数学

张顺淼,章静,张永晖, 梁泉

目录

  • 1 第一单元 命题逻辑
    • 1.1 序言
      • 1.1.1 附录 常用符号
    • 1.2 命题符号化及联接词
    • 1.3 命题公式及分类
    • 1.4 等值演算
    • 1.5 范式
    • 1.6 题例分析
    • 1.7 推理理论
  • 2 第二单元 一阶逻辑
    • 2.1 一阶逻辑基本概念
    • 2.2 一阶逻辑合式公式及解释
    • 2.3 一阶逻辑等值式与前式范式
    • 2.4 题例分析
  • 3 集合的基本概念和运算
    • 3.1 集合的基本概念
    • 3.2 集合的基本运算
    • 3.3 集合中元素的计数
    • 3.4 题例分析
  • 4 二元关系和函数
    • 4.1 集合的笛卡尔积与二元关系
    • 4.2 关系的运算
    • 4.3 关系的性质
    • 4.4 关系的闭包
    • 4.5 等价关系和偏序关系
    • 4.6 函数的定义和性质
    • 4.7 函数的复合和反函数
    • 4.8 题例分析
  • 5 图的基本概念
    • 5.1 无向图及有向图
    • 5.2 通路、回路和图的连通性
    • 5.3 图的矩阵表示
    • 5.4 最短路径、关键路径和着色
    • 5.5 题例分析
  • 6 特殊图
    • 6.1 二部图
    • 6.2 欧拉图
    • 6.3 哈密顿图
    • 6.4 平面图
    • 6.5 题例分析
  • 7 树
    • 7.1 无向树及生成树
    • 7.2 根树及其应用
    • 7.3 题例分析
  • 8 代数系统简介
    • 8.1 二元运算及其性质
    • 8.2 代数系统
    • 8.3 题例分析
序言



附录 常用符号

https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E7%AC%A6%E5%8F%B7/685756

符号种类

编辑

数量符号

X轴Y轴X轴Y轴

如:i,

  

,a,x,e,π。详见下。

运算符号

加号(+),减号(-),乘号(×或·),除号(÷或/),两个集合并集(∪),交集(∩),根号(√ ̄),对数(log,lg,ln,lb),(:),绝对值符号| |,微分(d),积分(∫),闭合曲面(曲线)积分(∮)等。

关系符号

如“=”是等号,“≈”是近似符号(即约等于),“≠”是不等号,“>”是大于符号,“<”是小于符号,“≥”是大于或等于符号(也可写作“≮”,即不小于),“≤”是小于或等于符号(也可写作“≯”,即不大于),“→ ”表示变量变化的趋势,“∽”是相似符号,“≌”是全等号,“∥”是平行符号,“⊥”是垂直符号,“∝”是正比例符号(表示反比例时可以利用倒数关系),“∈”是属于符号,“⊆”是包含于符号,“⊇”是包含符号,“|”表示“能整除”(例如a|b 表示“a能整除b”,而

  

||b表示r是a恰能整除b的最大幂次),x,y等任何字母都可以代表未知数

结合符号

如小括号“()”,中括号“[ ]”,大括号“{ }”,横线“—”,比如

  

性质符号

正号“+”,负号“-”,正负号

  

”(以及与之对应使用的负正号“

  

”)

省略符号

三角形(△),直角三角形(Rt△),正弦sin)(见三角函数),


双曲正弦函数sinh),x函数f(x)),极限lim),(∠),

 因为

 所以

总和,连加:,求积,连乘:,从n个元素中取出r个元素所有不同的组合数

  

n元素的总个数;r参与选择的元素个数),

  

等。

排列组合符号

组合数

A (或P) 排列数

n 元素的总个数

r 参与选择的元素个数

阶乘,如5!=5×4×3×2×1=120,规定0!=1

!! 半阶乘(又称双阶乘),例如7!!=7×5×3×1=105,10!!=10×8×6×4×2=3840

∑连加

离散数学符号

∀ 全称量词

存在量词

├ 断定符(公式在L中可证)

╞ 满足符(公式在E上有效,公式在E上可满足)

﹁ 命题的“非”运算,如命题的否定为﹁p

∧ 命题的“合取”(“”)运算

∨ 命题的“析取”(“”,“可兼或”)运算

→ 命题的“条件”运算

↔ 命题的“双条件”运算的

p<=>q 命题pq等价关系

p=>q 命题pq蕴涵关系(p是q的充分条件,q是p的必要条件

A* 公式A的对偶公式,或表示A的数论倒数(此时亦可写为

  

wff 合式公式

iff 当且仅当

↑ 命题的“与非” 运算( “与非门” )

↓ 命题的“或非”运算( “或非门” )

□ 模态词“必然”

◇ 模态词“可能”

空集

∈ 属于(如"AB",即“A属于B”)

∉ 不属于

P(A) 集合A幂集

|A| 集合A的点数

R²=R○R [R

=R

○R] 关系R的“复合”

ℵ Aleph,阿列夫

⊆ 包含

⊂(或⫋) 真包含

另外,还有相应的⊄,⊈,⊉等

∪ 集合的并运算

U(P)表示P的领域

∩ 集合的交运算

-或\ 集合的差运算

⊕集合的对称差运算

〡 限制

集合关于关系R等价类

A/R 集合A上关于R商集

[a] 元素a产生的循环群

I环,理想

Z/(n) 模n同余类集合

r(R) 关系 R的自反闭包

s(R) 关系 R的对称闭包

CP 命题演绎的定理(CP 规则)

EG 存在推广规则(存在量词引入规则)

ES 存在量词特指规则(存在量词消去规则)

UG 全称推广规则(全称量词引入规则)

US 全称特指规则(全称量词消去规则)

R 关系

相容关系

R○S 关系 与关系 的复合

domf 函数 的定义域(前域)

ranf 函数 的值域

f:xy fxy函数

(x,yxy最大公约数,有时为避免混淆,使用gcd(x,y)

[x,yxy最小公倍数,有时为避免混淆,使用lcm(x,y)

aH(HaH关于a的左(右)陪集

Ker(f) 同态映射f的核(或称f同态核)

[1,n] 1到n整数集合

d(A,B),|AB|,或AB 点A与点B间的距离

d(V) 点V度数

G=(V,E) 点集为V,边集为E的图G

W(G) 图G连通分支

k(G) 图G的点连通度

Δ(G) 图G的最大点度

A(G) 图G邻接矩阵

P(G) 图G可达矩阵

M(G) 图G关联矩阵

C 复数

虚数

自然数集,非负整数集(包含元素"0")

N*(N+) 正自然数集,正整数集(其中*表示从集合中去掉元素“0”,如R*表示非零实数)

P 素数质数)集

有理数

实数

整数

Set 集范畴

Top 拓扑空间范畴

Ab 交换群范畴

Grp 群范畴

Mon 单元半群范畴

Ring 有单位元的(结合)环范畴

Rng 环范畴

CRng 交换环范畴

R-mod 环R的左模范畴

mod-R 环R的右模范畴

Field 域范畴

Poset 偏序集范畴

希腊字母简表

序号

大写

小写

英语音标注音

英文

汉字注音

常用指代意义

1

Α

α

/'ælfə/

alpha

阿尔法

角度,系数,角加速度,第一个

2

Β

β

/'bi:tə/或/'beɪtə/

beta

贝塔

/毕塔

磁通系数,角度,系数

3

Γ

γ

/'gæmə/

gamma

伽玛

/甘玛

电导系数,角度,比热容比

4

Δ

δ

/'deltə/

delta

得尔塔

/岱欧塔

变化量,化学反应中的加热,屈光度,一元二次方程中的判别式

5

Ε

ε

/'epsɪlɒn/

epsilon

埃普西龙

对数之基数,介电常数

6

Ζ

ζ

/'zi:tə/

zeta

泽塔

系数,方位角,阻抗,相对黏度

7

Η

η

/'i:tə/

eta

伊塔

/诶塔

迟滞系数,效率

8

Θ

θ

/'θi:tə/

theta

西塔

温度,角度

9

Ι

ι

/aɪ'əʊtə/

iota

埃欧塔

微小,一点

10

Κ

κ

/'kæpə/

kappa

堪帕

介质常数,绝热指数

11

λ

/'læmdə/

lambda

兰姆达

波长,体积,导热系数

12

Μ

μ

/mju:/

mu

谬/穆

磁导系数,微,动摩擦系(因)数,流体动力黏度,微(千分之一),放大因数(小写)

13

Ν

ν

/nju:/

nu

拗/奴

磁阻系数,流体运动粘度,光子频率,化学计量数

14

Ξ

ξ

希腊/ksi/

英美/ˈzaɪ/或/ˈsaɪ/

xi

可西

/赛

随机变量,(小)区间内的一个未知特定值

15

Ο

ο

/əuˈmaikrən/

或/ˈɑmɪˌkrɑn/

omicron

欧(阿~)米可荣

高阶无穷小函数

16

π

/paɪ/

pi

求积,圆周率(=圆周÷直径≈3.1416),π(n)表示不大于n的质数个数

17

Ρ

ρ

/rəʊ/

rho

柔/若

电阻系数,柱坐标和极坐标中的极径,密度

18

σ,ς

/'sɪɡmə/

sigma

西格玛

求和,表面密度,跨导,正应力

19

Τ

τ

/tɔ:/或/taʊ/

tau

套/驼

时间常数,切应力,2π(两倍圆周率)

20

Υ

υ

/ˈipsɪlon/

或/ˈʌpsɪlɒn/

upsilon

宇(阿~)普西龙

位移

21

Φ

φ

/faɪ/

phi

弗爱

/弗忆

磁通,辅助角,透镜焦度,热流量

22

Χ

χ

/kaɪ/

chi

凯/柯义

统计学中有卡方(χ^2)分布

23

Ψ

ψ

/psaɪ/

psi

赛/普赛/普西

角速,介质电通量,ψ函数

24

Ω

ω

/'əʊmɪɡə/

或/oʊ'meɡə/

omega

欧米伽

/欧枚嘎

欧姆(电阻单位),角速度,交流电的电角度,化学中的质量分数

意义

编辑

符号(Symbol) 意义(Meaning)

等于 is equal to

≠ 不等于 is not equal to

≈ 约等于 approximately equal to

小于 is less than

大于 is greater than

// 平行 is parallel to

 

平行且相等

垂直

≥ 大于或等于 is greater than or equal to

≤ 小于或等于 is less than or equal to

≡ 恒等于或同余

π 圆周率 约为3.1415926536Ratio of circumference to diameter; Pi

自然常数 约为 2.7182818285Natural constant

|x| 绝对值或(复数的)absolute value of X

∽ 相似 is similar to

≌ 全等 is equal to(especially for geometric figure)

 

远大于

<< 远小于

∪ 并集

∩ 交集

⊆ 包含

∈ 属于

⊙ 

/ 除,求商值,部分编程语言中理解为整除

αβγφ… 角度系数

 无穷大(包括正无穷大+∞与负无穷大-∞)

lnx 以e为底的对数自然对数

lgx 以10为底的对数(常用对数

lbx 以2为底的对数

lim 求极限

floor(x) 或[x],亦可写为

  

下取整函数(直译为“地板函数”),又称高斯函数

ceil(x) 亦可写为

  

上取整函数(直译为“天花板函数”)

x mod y模,求余数

x-floor(x) 或{x} 表示x的小数部分

dy,df(x) 函数y=f(x)的微分(或线性主部)

f(x)d不定积分,函数f的全体原函数

平面二维k-ε紊流模型不同壁函数的对比及研究

函数fab定积分

表示imn逐一递增对

连加求和(sigma:∑ )

表示imn逐一递增对

连乘求积 (pi:Π)