离散数学专业名词

2024年2月3日发(作者：)

第一章 集合论、逻辑与算法基础

1.1集合

set（集合） power set（幂）

complement of a set（补集） roster method（枚举法）

universalset set（全集） symmetric difference（对称差集）

set-builder method（集合构造方法） Venn diagrams（文氏图）

ordered pair（有序对） subset（子集）

union of sets（并集） Cartesian product（笛卡尔积）

superset（父集） intersection of sets（交集）

diagonal of a set（对角集） proper subset（真子集）

disjoint sets（不相交集） ordered n-tuples（有序n元组）

equal sets（相等集合） index set（索引集）

n-flod Cartesian product（n次笛卡尔积）

empty （null）set（空集） set difference（差集）

bit string（位串） finite set（有限集）

mutually disjoint（互不相交） length（长度）

infinite set（无限集） pairwise disjoint（互不相交）

singleton set（单体集合） relative complement（相对补集）

1.2数理逻辑

statement（命题） condition（条件）

converse（逆命题） proposition（命题）

biimplication（双向蕴涵） inverse（反命题）

truth value（真值） biconditional（双向条件）

contrapositive（逆否命题） negation（非）

logical connectives（逻辑连接词） statement formula（命题公式）

conjunction（合取） well-formed formulas（良态公式）

formula（公式） disjunction（析取）

tautology（重言式） implication（蕴涵）

contradiction（矛盾式）

1.3论证有效性

proof（证明） modus tollens（否定法）

disjunctive addition（析取加法） argument（论证）

disjunctive syllogisms（析取三段论） conjunctive addition（合取加法）

conclusion（结论） hypothetical syllogism（假设三段论）

logically valid（逻辑有效） premise（前提）

dilemma（二难推论） modus ponens（断言法）

conjunctive simpli fications（合取简化）

1.4量词与一阶逻辑

statement logic（命题逻辑） predicate（谓词）

domain（域） propositional logic（命题逻辑）

propositional function（命题函数） free vricable（自由变量）

n-place predicate（n位谓词） bound variable（约束变量）

first-order logic（一阶逻辑） universal quantifier（全称量词）

counterexample（反例） existential quantifier（存在量词）

disproof（反证）

1.5证明方法

theorem（定理） indirect proof（间接证明）

proof by contradiction（反证法） proof by direct method（直接证明方法）

direct proof（直接证明）

1.6 算法

algorithm（算法） two-way selection（双路选择）

list（列表） input（输入）

if two-dimensional array（二维数组）

output（输出） then

read precision（精度）

else print

uniqueness（唯一性） while

subproprams（子程序） finiteness（有限性）

do procedure

generality（通用性） for

function assignment operator（赋值运算符）

begin constant polynomial（常量多项式）

assignment statement（赋值语句） end

degree（次数） control structures（控制结构）

return one-way selection（单路选择）

arrays（数组）

第三章 关系与偏序集

3.1关系与偏序集

binary relation （二元关系） directed graph representation（有向图表示）

digraph （有向图） relation （关系） vertex（顶点）

adjacent to （与...相邻） R-related （R-相关） directed edge（有向边）

adjacent from（从...相邻） related （相关） directed arc（有向弧）

loop （环） empty relation （空关系） arrow diagram （矢量图）

domain （域） universal relation （全称关系） directed graph（有向图）

range （值域） image (映像) equivalence class （等价类）

transitive closure （传递闭包） inverse （逆） R-class（R-类）

directed walk （有向通路） composition （复合） reflexive （自反）

R-equivalence class （R-等价类） walk （通路） partition （划分）

vertices of the walk （通路顶点） transitive （传递）

equivalence relation induced by the partition （划分推出的等价关系）

terminal vertex （终止顶点） equivalence relation （等价关系）

internal vertices （内部顶点） equality relation （相等性关系）

reflexive closure （自反闭包） path （路径）

congruence modulo m （模m同余） symmetric closure （对称闭包）

3.2偏序集

antisymmetric （反对称） lexicographic order （词典序）

topological ordering （拓扑排序） partial order （偏序）

dictionary order （字典序） upper bound（上界）

partially ordered set （偏序集） closed （闭合） poset （偏序集）

least upper bound（lub） （最小上界） covers （覆盖）

lower bound （下界） dual （序偶） Hasse diagram （哈赛图）

greatest lower bound （glb） （最大下界） comparable （可比）

minimal element （极小元） lattice （格）

linearly ordered set （线性有序集） maximal element （极大元）

distributive （可分配性） totally ordered set （完全有序集）

greatest element （最大元） complement （补元）

chain （链） least element （最小元） Boolean algebra （布尔代数）

product partial order （积偏序） compatible （兼容，相容）

第四章 矩阵与关系闭包

4.1矩阵

matrix（矩阵） diagonal matrix（对角矩阵）

join（并） rectangular array（矩阵阵列）

identity matrix（单位矩阵） Boolean meet（布尔交）

element（元素） sum（和）

meet（交） entry（项）

difference（差） join of meet expression（相交表达式的并）

equal（等于） multiplication（乘法）

Boolean product（布尔积） square matrix（方阵）

transpose（转置） product（积）

zero matrix（零矩阵） symmetric（对称）

diagonal element（对角元素） Boolean join（布尔并）

4.2 关系矩阵与闭包

matrix of a relation（关系矩阵）

Warshall’s algorithm（Warshall算法）

第五章 函数

5.1 函数

function（函数） target（目标）

onto（满射） well defined（合理定义）

range（值域） surjective（满射）

single valued（单值） numeric functions（数字函数）

surjection（满射） image（映像）

identity function（恒等函数）

one-to-one correspondence（一一映射）

preimage（预映像，前射，前像，原像） constant function（常数函数）

bijective（双射） mapped（映射）

one-one（单射函数） bijection（双射）

domain（域） injective（内射）

composition（复合） codomain（合域）

injection（内射）

5.2 特殊函数与集合的基数

inverse function（逆函数） images（映像）

cardinality（基数） left invertible（左可逆）

direct image（直接映像） equivalent（等价）

left inverse（左逆） inverse image（逆映像）

equipotent（幂等） right invertible（右可逆）

floor（下限） countable（可数）

right inverse（右逆） ceiling（上限）

uncountable（不可数） restriction（限制）

floor function（弱取整函数） extension（扩展）

ceiling function（强取整函数）

5.3 序列与字符串

sequence（序列） sum of the terms（项之和）

index（索引） nth term of the sequence（序列第n项）

summation symbol（求和符号） subscript（下标）

finite sequence（有限序列） string（字符串）

infinite sequence（无限序列） word（字符）

integer sequence（整数序列） dummy variable（哑变量）

alphabet（字母表） arithmetic progression（AP）（等差数列）

lower limit（下限） length（长度）

first term（首项） upper limit（上限）

empty string（空字符串） common difference（公差）

general term（通项） empty word（空串）

geometric progression（GP）（等比数列） product of the terms（项之积）

concatenation（接合） common ratio（公比）

product symbol（求积符号）

5.4 二元运算

binary operation（二元运算） mathematical system（数学系统）

idempotent（幂等） close under（在……下闭合）

groupoid（群） idempotent semigroup（幂等半群）

associative（可结合） identity（单位元）

band（带） commutative（可交换）

semigroup（半群）

free semigroup generated by（由……生成的自由半群）

Cayley multiplication table（Cayley乘法表） monoid（幺半群）

free monoid generated by（由……生成的自由幺半群）

Cayley table（Cayley表） transformation semigroup（变换半群）

第六章 同余

6.1同余

Congruent （同余） congruence class modulo （模m的同余类）

6.3线性同余

linear congruence in one variable （一个变量x的线性同余式）

inverse （逆） residue representation （余数表示）

unique modulo （唯一模） modular representation （模表示）

round-robin tournament （循环赛） hashing （散列）

hash address （散列地址） linear probing （线性探测）

hash table （散列表） hashing function （散列函数）

probe sequence （探测数列） hash function （散列函数）

collision （冲突） double hashing （双重散列）

6.4特殊同余定理

Euler phi-function （欧拉phi函数） ciphertext （密文）

encryption key （加密钥匙） plaintext（明文）

decryption function （加密函数） decryption key （揭秘钥匙）

第十章 图论

10.1图的定义与符号

graph （图） parallel （平行边） arc（弧）

set of vertices （顶点集合） isolated vertex （顶点孤立）

Staring vertex （始点） set of edges （边集） degree （度）

terminating vertex （终点） incidence function （关联函数）

k-regular graph （k-正则图） in-degree （入度）

end vertices （端点） even degree vertex （偶度顶点）

out-degree （出度） endpoints（端点）

odd degree vertex （奇度顶点） simple graph （简单图）

incident （关联） degree sequence (度数列) complete graph（完全图）

Adjacent （相邻） directed graph（有向图） triangle （三角形）

loop （环） digraph （有向图） bipartite graph （二分图）

incidence table （关联表） directed edge（有向边）

Bipartition （二分） complete bipartite （完全二分） subgraph （子图）

Complement of a graph（补图） Ramsey number （Ramsey数）

10.2通路，路径与圈

walk （通路） initial vertex （始点） terminal vertex（终点）

directed walk （有向通路） length of a walk （通路长度）

length of a directed walk （有向通路长度） u-v walk （u-v通路）

u-v directed walk （u-v 有向通路） closed walk （闭合通路）

closed directed walk （闭合有向通路） open walk （开放通路）

open directed walk （开放有向通路） trail （迹)

path （路径） trivial walk （平凡通路） trivial path （平凡路径）

trivial trail （平凡迹） nontrivial walk （非平凡通路）

nontrivial path （非平凡路径） nontrivial trial （非平凡迹）

circuit （回路） cycle （圈） k-cycle （k圈）

even cycle （偶数圈）odd cycle （奇数圈） subwalk （子通路）

reduction of P by Q（P用Q简化） decomposition （分解）

connected （连接） connected graph （连接图，连通图）

disconnected graph （不连接图，不连通图） component （分支）

distance （距离）matching （匹配） M-saturated （M-饱和）

M-unsaturated （M-不饱和） perfect matching （完美匹配）

maximum matching（最大匹配） neighbors （邻居）

10.3图的矩阵表示

adjacency （相邻矩阵） incidence matrix（关联矩阵）

10.4特殊回路

Euler circuit （欧拉回路） Euler trail （欧拉迹）

Hamiltonian graph （汉密尔顿图） Euler graph （欧拉图）

Hamiltonian cycle （汉密尔顿圈） Hamiltonian path （汉密尔顿路径）

10.5同构

isomorphic （同构） different （不同）

10.6图算法

weight （权） weighted graph （加权图）weight matrix （加权矩阵）

length of a path （路径长度） shortest path algorithm （最短路径算法）

greedy algorithm （贪婪算法） topological ordering （拓扑排序）

immediate successor （直接后继） queue （队列）

rear （队尾）

10.7 平面图和图着色

planar graph（平面图） exterior face（外面）

proper vertex coloring（正常顶点着色） plane graph（平面图）

interior face（内面） chromatic number（色数）

planar representation of a graph（图的平面表示）

subdivision of a graph（图的细分） edge coloring（边着色）

faces（面） homeomorphic（同胚）

proper edge coloring（正常边着色） boundary（边界）

vertex coloring（顶点着色） chromatic index（色索引）

第十一章 树与网络

11.1 树

tree（树） acyclic graph（无环图）

11.2 有根树

rooted tree（有根树） binary tree（二叉树）

postorder traversal（后序遍历） lever（层）

trivial tree（平凡树） inorder sequence（中序顺序）

child（子节点） left child（左子节点）

preorder sequence（前序顺序） terminal vertex（终点）

right child（右子节点） postorder sequence（后序顺序）

leaf（叶子） left subtree（左子树）

binary search tree（二叉搜索树） internal vertex（内顶点）

right subtree（右子树） infix（中缀）

descendant（后代） full binary tree（完全二叉树）

prefix（前缀） ordered rooted tree（有序有根树）

inorder traversal（中序遍历） postfix（后缀）

height（高度） preorder traversal（前序遍历）

expression tree（表达式树）

11.3 生成树

spanning tree（生成树） minimal spanning tree（最小生成树）

weighted tree（加权树） Prim’s algorithm（Prim算法）

weight（权）

11.4 网络

single-source，single-sink network（单元单汇网络）

flow conservation（流量守恒） quasipath（拟路径）

source（源） flow in edge（边流）

forward arc（正向弧） target（目标）

flow into（流入） backward arc（反向弧）

sink（汇） flow out of（流出）

slack（松弛） s-t network（s-t网络）

conservation of flow（流量守恒） F-saturated（F-饱和）

capacity（容量） value of a flow（流值）

F-unsaturated（F-不饱和） transport network（传输网络）

s-t cut of network（网络的s-t分割） flow augmenting（流增广）

network（网络） capacity of an s-t cut（s-t分割容量）

patent（父节点）

minimal cut（最小分割）

capacity constraint（容量限制）

flow（流）

immediate predecessor（直接前驱）

maximal flow（最大流）