Skip to content

Logic and Reasoning

details in Introduction to AI.

Modern Algebra

Magma

magma 代数系统

Binary operation assume S is a set mapping f: \(S\times S\rightarrow S\) is a dyadic operation on S.

dyadic operation 二元运算:

  1. The result of the dyadic operation is still belong to S.

  2. Every element in S can participate in the dyadic operation and get a unique result.

e.g. In the natural number set N addition and multiplication are binary operators on N, but subtraction and division are not.

Quasigroup

准群

assume G is a nonempty set and \(\circ\) is the dyadic operation on the G, then \(\circ\) is called multiplication. If the following condition is true, we call G is a quasigroup about binary operation multiplication \(\circ\).

\(a,b\in G\), equation \(a\circ x=b\) and \(y\circ a=b\) have solutions in G.

Semigroup

半群

assume G is a nonempty set and \(\circ\) is the dyadic operation on the G, \(\circ\) is called multiplication. If the following condition is true, we call G is a semigroup about dyadic operation multiplication \(\circ\).

\(a,b,c\in G\), \((a\circ b)\circ c=a\circ(b\circ c)\). (associative law)

Monoid

幺半群

Suppose that S is a set and \(\cdot\) is some dyadic operation in S, then S with \(\cdot\) is a monoid if it satisfies the following two axioms

  1. Associativity for all a, b and c in S, the equation \((a\cdot b)\cdot c=a\cdot(b\cdot c)\) holds.
  2. Identity element. there exists an element e in S such that for every element a in S, equation \(e\cdot a=a\cdot e\) hold.

Group

群

A group is a set, G, together with an operation \(\cdot\) that combines any two elements a and b to form another element, denoted \(a\cdot b\) or \(ab\). To qualify as a group, the set and operation, \((G,\cdot)\), must satisfy 4 requirements known as the group axioms 群公理

  1. Closure for all a, b in G, the result of the operation \(a\cdot b\), is also in G.
  2. Associativity. for all a, b and c in G, \((a\cdot b)\cdot c=a\cdot(b\cdot c)\).
  3. Identity element. there exists an element e in S such that for every element a in S, equation \(e\cdot a=a\cdot e\) hold.
  4. Inverse element. for each a in G, there exists an element b in G, commonly denoted \(a^{-1}\) or \(-a\), s.t. \(a\cdot b=b\cdot a=e\), where e is the identity element.

Ring

A ring is a set R equipped with 2 binary operations \(+\) and \(\cdot\), satisfying the following 3 sets of axioms, called the ring axioms.

  1. R is an abelian group（阿贝尔群） under addition. i.e.
  2. \((a+b)+c=a+(b+c)\) associative
  3. \(a+b=b+a\) commutative 交换律
  4. there is an element 0 in R s.t. \(a+0=a\) for all a in R (0 is additive identity)
  5. for each a in R there exists -a in R s.t. \(a+(-a)=0\) (-a is the additive inverse of a) 加法逆元
  6. R is a monoid under multiplication.
  7. \((a\cdot b)\cdot c=a\cdot(b\cdot c)\) associative
  8. \(a\cdot1=1\cdot a=a\) multiplicative identity
  9. Multiplication is distributive with respect to addition.
  10. \(a\cdot(b+c)=(a\cdot b)+(a\cdot c)\) left distributivity
  11. \((b+c)\cdot a=(b\cdot a)+(c\cdot a)\) right distributivity

Set Theory

Set

Difference Set 差集

Symmetry difference 对称差 \(A\Delta B=A\bigcup B-A\bigcap B\)

De Morgen's Law

The principle of capacitive repulsion. 容斥原理

Map

Injective: x1!=x2, f(x1)!=f(x2) 单射

surjective: every y has a x from X that points to it. 满射

bijection: injective + surjective. 双射

Graph Theory

Undirect Graph 无向图

Direct Graph 有向图

Euler Graph

Has Euler Circle.

Undirect: degree of vertices is even number.

Direct: Input degree=Output Degree

能“一笔画”的图

Hamiltonian Graph

Has a Hamiltonian Circle

能“一笔画”且回到原点的图

Minimum Spanning Tree

Kruskal algorithm

Prim algorithm

details in Introduction to algorithm