2. 귀납적 정의 (Inductive Definitions) 2

Natural Numbers

자연수 집합 N = {0,1,2,3...}를 귀납적으로 정의하면 /0, n/n+1 이다.

이 규칙은 다음과 같이 문법적으로 표현될 수 있다: n → 0 | n + 1

 

Strings

알파벳 집합 {a ... z}을 사용하여 문자열 집합을 정의해보자.

빈 문자열 ε이 있을 때,

/ ε , α / aα, α / bα ...  α / zα 로 귀납적 정의할 수 있다.

문법적으로는,

α → ε | xα (x ∈ {a,...,z})으로 나타낼 수 있다.

 

Boolean Values

불린값 B = {true, false}는 유한한 값이다.

이는 그저 공리에 의해서 정의될 수 있다.

/true, /false

문법적으로는, b → true | false 이다.

 

Lists

리스트의 끝을 nil로 나타낼 때,

 

추론규칙으로 다음과 같이 나타낸다.

 

문법적으로는 다음과 같이 나타낸다.

l → nil | nl (n ∈ Z)

 

이는 위와 같이 증명할 수 있는데, 이러한 증명법을 derivation tree(유도 트리) 또는 deduction tree(연역 트리)라고 부른다.

 

 

Binary Trees

1. leaf

2. (2, leaf, leaf)

3. (1, (2, leaf, leaf), leaf)

4. (1,(2, leaf, leaf),(3, (4, leaf, leaf), leaf))

 

이진 트리를 위와 같이 나타낼 때,

추론 규칙으로 나타내면 다음과 같다.

문법적으로 나타내면 다음과 같다.

t → leaf | (n, t, t) (n ∈ Z)

 

t가 leaf일 때, 어떤 자연수 n에 대하여 t는 (n, t, t)로 변환된다.

 

이진트리를 다르게 나타내는 방법도 있다.

자연수 초기값 n이 있을 때,

t는 (t, nil) 또는 (nil, t)로 변환된다.

t1과 t2가 있을 때 이는 (t1, t2)로 변환된다.

 

문법적으로 나타내면 다음과 같다.

t → n (n ∈ Z)

| (t, nil)

| (nil, t)

| (t, t)

 

((1, 2), (3, nil))을 나타내면,

위와 같이 생성된다.

 

 

Expressions

위와 같이 생성되는 식이 있을 때,

 

추론규칙은 다음과 같다.

 

이를 문법적으로 나타내면,

e → n (n ∈ Z)

| -e

| e + e

| e * e

| (e)

 

위와 표현할 수 있다.

 

이를 유도 트리로 증명하면,

위와 같이 표현된다.

 

 

Propositional Logic (명제논리)

[[T]] = true

[[F]] = false

[[¬f]] = not [[f]]

[[f1 ∧ f2]] = [[f1]] andalso [[f2]]

[[f1 ∨ f2]] = [[f1]] orelse [[f2]]

[[f1 ⇒ f2]] = [[f1]] implies [[f2]]

f가 위와 같은 의미를 가질 때,

 

f → T | F

| ¬f

| f ∧ f

| f ∨ f

| f ⇒ f

 

(참고로, f1 ⇒ f2 는 f1이 참이면 f2도 참이라는 뜻이다)

 

[[(T ∧ (T ∨ F)) ⇒ F]]

= [[T ∧ (T ∨ F)]] ⇒ implies false

= [[true andalso (T ∨ F)]] implies false

= [[true andalso (true orelse false)]] implies false

 

 

Structural Induction (구조적 귀납법)

구조적 귀납법으로 어떤 명제 P(s)가 모든 구조 s에 대해 참임을 증명하는 과정은 다음과 같다.

1. Base case : 가장 기본적인 구조가 부분 구조(substructures)에서 참임을 보인다.

2. Inductive case : 만약 P가 s의 부분 구조들에 대해 참이라면, s 자체에 대해서도 참임을 보인다. 이를 I.H.라 부른다.

 

예시 1.

모든 x ∈ S에 대하여, x가 3으로 나뉨을 증명하자.

 

1. Base case

x가 3일 때, x는 3으로 나뉜다.

 

2. Inductive case

x가 3으로 나뉘고, y가 3으로 나뉜다면, x = 3k1, y = 3k2로 나타낼 수 있다.

여기서 x+y는 3(k1 + k2)이므로 3으로 나뉜다.

따라서 x+y는 3으로 나뉜다.

 

 

예시 2.

위 추론규칙으로 만들어지는 모든 요소에 대해, '('과 ')'의 개수가 같음을 보이자.

즉 x ∈ S에서 l(x) = r(x) 을 증명하면 된다. (l(x) 는 왼쪽 괄호의 개수, r(x)는 오른쪽 괄호의 개수)

 

l(()) = 1, r(()) = 1,

l((x)) = l(x) + 1, r((x)) = r(x) + 1,

l(xy) =  l(x) + l(y), r((x)) = r(x) + r(y) 이다.

 

1. Base case

x = ()일 때, l(x) = 1 = r(x)이다.

 

2. Inductive case

I.H.  l(x) = r(x), l(y) = r(y)

case 1. l((x)) = r((x))를 증명하자.

l((x)) = l(x) + 1

= r(x) + 1

= r((x))

 

case 2. l(xy) = r(xy)를 증명하자.

l(xy) = l(x) + l(y)

= r(x) + r(y)

= r(xy)

 

 

예시 3.l

위 이진트리에서, 잎의 개수는 내부 노드의 개수보다 항상 하나 더 많다는 것을 증명하자.

즉, t ∈ T 이면 l(t) = i(t) + 1 임을 보이자.

 

l(leaf) = 1, i(leaf) = 0 이다.

l(n, t1, t2) = l(t1) + l(t2) 이고, i(n, t1, t2) = i(t1)+i(t2) + 1 이다.

 

1. Base case

t = leaf일 때, l(leaf) = 1, i(leaf) = 0이다.

 

2. Induction case

l(t1) = i(t1) + 1, l(t2) = i(t2) + 1 이므로,

l((n, t1, t2))

= l(t1) + l(t2)

= i(t1) + 1 + i(t2) + 1

= i(n, t1, t2) + 1

이므로, 잎의 개수는 내부 노드의 개수보다 항상 하나 더 많다.