计算机数理逻辑-一阶逻辑-序

1. Orderings 序

序是一个关系

A (strict) ordering on a set X is a transitive and irreflexive binary relation on X, here denoted by ≻ （只有严格有序集是要求非自反，即无相等元素的？毕竟相等的话就是multi-set了，并且这个符号也不是$\geq$）

  • The pair(X, ≻) is then called a (strictly) ordered set有序集 (感觉有点类似群，只不过群是在集合的基础上定义加乘法，而有序集是在集合的基础上定义了序)

An element x of X is minimal wrt.(with regard to) ≻, if there is no y in X such that x ≻ y

  • A minimal element x in X is called the smallest (or strictly minimal) element, if for all y ∈ X different from x, y ≻ x. 唯一与不唯一的区别
  • Maximal and largest (or strictly maximal) elements are defined analogously(类似的)
  • $≺$ for the inverse relation $≻^{−1}$
  • x ⪰ y iff either x ≻ y or x = y
  • In a total ordering if an element is minimal then it is the smallest element.
  • In any ordering, the smallest element is unique唯一, if exists

1.1. Strict partial order 严格偏序

  1. Irreflexivity
  2. Transitivity
  3. Asymmetry

1.1.1. Total order 全序关系

  • 也称linear order线性关系
  • A strict total order 则会将reflexive变为irreflexive. Anitsymmetry变为Asymmetry.

1.2. Well-founded relation 良基关系

A (strict) ordering ≻ over X is called well-founded (or Noetherian or terminating), if there is no infinite decreasing chain x0 ≻ x1 ≻ x2 ≻ . . . of elements xi ∈ X.

(X, ≻) is well-founded iff every non-empty subset Y of X has a minimal element.

  • 集合 X 上的一个二元关系 R 被称为是良基的，当且仅当所有 X 的非空子集都有一个 极小值(非最小值)（注意前提是有限有序集）

1.3. Noetherian Induction 归纳

Let (X, ≻) be a well-founded ordering, let Q be a property(集合论中的属性) of elements of X.

  • If
    • for all x ∈ X the following implication is satisfied
      1
      2
      if Q(y) holds, for all y ∈ X such that x ≻ y,
      then Q(x) holds.
    • “如果比x小的都成立则x成立”这一规则成立的话
  • Then
    • the property Q(x) holds for all x ∈ X

Proof：By contradiction反证法

By contradiction.

Thus, suppose for all x ∈ X the implication above is satisfied（premise前提成立）, but Q(x) does not hold for all x ∈ X (conclusion结论不成立).

Let A = {x ∈ X | Q(x) is false}. Suppose $A \neq ∅$.

Since (X, ≻) is well-founded, A has a minimal element x1. Hence for all y ∈ X with x1 ≻ y the property Q(y) holds. （x是最小值，没有比他更小的了，所以成立）

On the other hand, the implication which is presupposed for this theorem holds in particular also for x1, hence Q(x1) must be true so that x1 cannot belong to A. Contradiction.

1.4. Multi-Set Orderings

Let (X, ≻) be an ordering. The multi-set extension $≻_{mul}$ of ≻ to (finite) multi-sets over X is defined by

  • $S1 ≻_{mul} S2$ ⇐⇒ $S1 \neq S2$ and ∀x ∈ S2\S1（S2-S1差集）. ∃y ∈ S1\S2. y ≻ x
  1. Remove common occurrences of elements from S1 and S2. Assume this gives S′= S′

2.Then check that for every element x in S′there is an element y ∈ S′′ that is greater than x. Then S1 $≻_mul$ S2.

Ordering with one minimal element, but without the smallest element:

  • ${(0,y)\in {\Bbb{R}}^2: 0<y<1} \cup{} {(1,y)\in {\Bbb{R}}^2: 0\leq y<1}$
    • $(1,0)$ is the one and only one minimal element but not a smallest element
    • because it is not related to the elements with $x=0$

2. Lexicographic Combination 词法组合

拼接两个排序

Let $(X1, ≻1)$, $(X2, ≻_2)$ be two orderings. Lexicographic combination of (X1, ≻1), (X2, ≻2) is an ordering: $≻{lex}= (≻_1, ≻_2)$ on X1 × X2 such that

  • (x1, x2) ≻lex (y1, y2) iff
    • x1 $≻_1$ y1
    • or else x1 = y1 and x2 $≻_2$ y2

2.1. Properties

Let (X1, $≻_1$), (X2, $≻_2$) be two orderings. Then

  1. $≻_lex$ is an ordering.
  2. if both $≻_1$ and $≻_2$ well-founded then $≻_lex$ well-founded.
  3. if both $≻1$ and $≻_2$ total then $≻{lex}$ total.

3. ground literal and clause orderings

  • 也就是说命题逻辑中的literal相当于一阶逻辑中的ground literal