hypothesis를 true라 두고, conclusion을 유도.

-Mathematical Induction

N을 양의 자연수의 집합이라 하고, S(n)을 propositional function이라 하자.

(∀n)S(n)         D: N

를 증명하기 위해서는 이 proposition을 

∀n[ S(n) -> S(N+1) ]

로 바꾸어서 Direct proof를 보이면 된다.

conclusion을 false라 두고, hypothesis와의 contradiction을 보임.

A sentence that can be determined to be either true or false.

Hypothesis is the given proposition.

Conclusion is the proposition that follows from the hypothesis.

forming new compound proposition.

-conditional propositions: p->q

"If P, then q. " or "p only if q."

p: hypothesis , q: conclusion

-Biconditional proposition: p<->q

it equal (p->q) ^ (q->p)

"p if and only if q" of "p iff q"

- the order of evaluation is first ~, then ^, then v, last ->.

Two truth tables are identical, denoted P ≡ Q.

① p -> q ≡ ~p v q

② contrapositive 

p -> q ≡ ~q -> ~p

③ De Morgan's lows

~(p ^ q) ≡ ~p v ~q

~(p v q) ≡ ~p ^ ~q

④ a v ( b ^ c) ≡ (a v b) ^ (a v c) 

    a ^ ( b v c) ≡ (a ^ b) v (a ^ c) 

- ∀

The symbol ∀ means "for all".

Let P be a propositional function with domain of discourse D. The statement

for all x, P(x)

may be written 

(∀x)P(x).

it is true if for all x in D, P(x) is true.

-∃

The symbol ∃ means "there exists".

there exist x, P(x)

may be written 

(∃x)P(x).

it is true if for at least one x in D, P(x) is true.

~(∀x P(x)) ≡ (∃x)~P(x)

~(∃x P(x)) ≡ (∀x)~P(x)

A function f from a set X to a set Y(f : X->Y) is a subset of XxY such that for all x∈X, there is exactly one y∈Y with (x, y)∈f.

The floor of x, denoted └x┘, is the greatest integer less than or equal to x.

The ceiling of x, denoted ┌x┐, is the least integer greater than or equal to x.

- one-to-one                          for all x1, x2∈X, if(x1) = f(x2), then x1 = x2.

- onto                                   for all y∈Y, there exists x∈X such that y=f(x).

- bijection                              one-to-one, onto

- Binary operator on a set X       a function from X x X to X

- unary operator on X               a function from X to X

Let f be a bijection function from X to Y.

the inverse of f, denoted f^-1, is the funtion from Y to X defined by

f^-1 = { (y, x)| (x, y) ∈ f}

Let g be a function from X to Y and f be a funtion from Y to Z.

the composition of f with g, denoted f ∘ g, is the funtion from X to Z defined by

f ∘g(x) = f( g(x) )

A (binary) relation R from a set X to a set Y is a subset of XxY.

If (x, y)∈R, we write xRy and say that x is relation to y.

If X=Y, we call R a (binary) relation on X.

domain of R is Dom(R) = { x∈X| (x, y)∈R for some y∈Y}.

range of R is Rng(R) = { y∈Y|(x,y)∈R for some x∈X}

① draw dots to represent the elements of X.

② If the element (x,y) is in R, draw an arrow from x to y.

- reflexive             xRx for all x∈X.

- symmetric           if xRy, then yRx.

- anti-symmetric    if xRy and yRx, then x=y.

- transitive            if xRy  and yRz, then xRz.

- If R is reflexive, anti-symmetric, transitive, then R is a partial order. and If (x, y) or (y, x)∈R for      every pair of elements in X, then R is total order.

Let R be a relation from X to Y.

the inverse of R, denoted R^-1, is the relation from Y to X defined by

R^-1 = { (y, x)| (x, y)∈R}

Let R1 be a relation from X to Y and R2 be a relation from Y to Z.

the composition of R1 and R2, denote R2∘R1, is the relation from X to Z defined by

R2∘R1 = { (x, z)| (x, y)∈R1 and (y, z)∈R2 for some y∈Y}.

R is an equivalence relation if R is reflexive, symmetric and transitive.

Let S be a partition of a set X. if for some set T in S, x, y are in T, Define xRy on X. Then R is an equivalence relation on X. 

Let R be an equivalence relation on a set X. For each a∈X, let

[a] = { x∈X | xRa }

then 

S = { [a] | a∈X}

is a partition of X.

the sets [a] are called the equivalence classes of X given by the relation R.

Let X,Y be sets and R a relation from X to Y.

Write the matrix A of the relation R as follows:

- Rows of A = elements of X

- Columns of A = elements of Y

- Element a(ij) = if the element of X in low i and the element of Y in column j are related, it is 1 else 0.

Let R1 be the relation from X to Y and let R2 be the relation from Y to Z.

Let A1 be the matrix of R1 and let A2 be the matrix of R2.

The product of these matrices is A1A2.

if the (i,k)th entry in A1A2 is nonzero, then (Xi, Zk)∈R2∘R1.

Let A be the square matrix of a relation R from X to itself.

Let A^2 is the matrix product AA.

- R is reflexive if and only if all terms a(ii) in the main diagonal of A are 1.

- R is symmetric if and only if a(ij) = a(ji) for all i and j.

- R is transitive if A^2=A(whenever c(ij) in C = A^2 in nonzero then entry a(ij) is A is also nonzero.).

we call (x, y) on ordered pair.

(x1, x2)=(y1, y2) if and only if x1=y1, and x2=y2.

X x Y = { (x, y) | x∈X and y∈Y} 

A sequence is an ordered list.

S or {Sn} is a sequence named S, the entire sequence.

Sn is single element of the sequence S at index n.

A sub-sequence {Snk} is a sequence that consist of certain element of {Sn} retained in the original order in S.

A string over a set X is a finite sequence of elements from X.