증명(proof)

수학적 의미 - 특정한 공리들을 가정하고, 그 가정 하에서 어떤 명제가 참이라는 것을 보여주는 것.
논리적인 법칙을 이용하여 주어진 가정으로부터 결론을 유도하는 추론의 한 방법으로 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업.

• 증명을 위해 참인 전제들이 주어지고 참인 전제들의 결론 또한 참이 되는것을 유효 추론(vaild argument)라고 한다.
  유효 추론이 성립되었을 때 정확한 증명이라고 할 수 있다.

공리(Axiom)

: 별도의 증명이 필요 없이 항상 참으로 이용되는 명제(Proposition)

• 이론체계에서 가장 기초적인 근거가 되는 명제, 어떤 다른 명제를 증명하기 위한 전제로 이용되는 가장 기본적인 가정이다.

정리(Theorem)

: 공리와 정의를 통해 참으로 확인된 명제, 즉 증명이 완료된 명제다.

• 수학에서 가정(Assumption)으로부터 증명된 명제.
• 보조정리(Lemma) : 정리를 증명하기 위해 사용되는 보조적인 명제
• 따름정리(Corollary) : 정리로부터 쉽게 도출되는 부가적인 명제

정의(Definition)

: 논의 대상이 지니는 의미와 내용에 착오가 일어나지 않도록 뚜렷이 규정한 문장 이나 식.

증명방법

수학적 귀납법

Mathematical induction
: 바탕 명제(base case)가 참일 대, 귀납 규칙(induction rule)을 증명하여 무한히 많은 다른 명제들도 참이라는 것을 보이는 것.

귀납적 추론(induction reasoning)은 개별적이고 특수한 사례들로부터 일반적이고 보편적인 법칙을 찾아가는 것.
연역적 추론(deductive reasoning)은 하나의 일반적인 원리와 사실을 전제로 특수한 다른 원리나 개별적인 사실을 이끌어내는 것.(연결하여 추론)
귀납적 추론과 연역적 추론은 서로 반대의 개념

수학적 귀납법은 이름과 달리 귀납적 논증이 아닌 연역적 논증에 속한다.

Ex) 계단을 오를 경우 첫 번째 계단을 오르고 그 후 n번째 계단을 지나 n+1번째 계단을 같은 방법으로 오르는 것.

❗️ 수학적 귀납법의 3단계
1) 기초 단계(basic)
2) 귀납 가정(inductive assumption)
3) 귀납 단계(inductive step)

직접 증명법

Direct proof
: 주어진 명제를 변경하지 않고 참이라 가정하고 공리, 정리, 정의 등을 이용하여 증명하는 방법.

모순 증명법

Proof by contradiction
: 주어진 명제를 일단 부정하고 논리를 전개하여 그것이 모순됨을 보임으로써 주어진 명제가 사실임을 증명하는 방법이다.

• 기존의 방법으로 쉽게 증명할 수 없을 경우에 매우 유용한 증명방법이다.

대우 증명법

Contraposition proof
: 조건명제 p → q와 ¬q → ¬p 가 대우 관계로서 논리적 동치임을 이용하여 ¬q → ¬p 가 참인 것을 증명함으로써 p → q가 참이 됨을 증명하는 방법

반례 증명법

`Proof by Counter Example``
: 주어진 명제가 참 또는 거짓임을 기존의 방법으로 입증하기가 어려운 경우, 모순이 되는 예를 보임으로써 증명하는 방법

존재 증명법

Existence proof
: 주어진 명제가 참이 되는 예를 찾아 증명하는 방법

---

수의 표현

• 진수 표현 : 10, 2, 8, 16 진수 등
• n진법과 n진수 : 0과 n-1 사이의 숫자들을 이용해서 수를 표현하는 방식 또는 그렇게 표현된 수를 말한다.

n : 기수(Base number), 표현된 수의 오른쪽 아래에 표기

진법별 수의 표현

10진수

Decimal number
: 기수를 10으로 하는 수 체계

• 0부터 9까지의 수 사용.
• 10을 한 자리의 기본 단위로 하는 진수.
• 소수점 아래의 숫자들의 기수는-임

2진수

Binary number
: 기수를 2로 하는 수 체계

• 0과 1의 조합으로 숫자를 표하는 진법.
• 2를 한 자리의 기본단위로 하는 진수.

8진수

Octal number
: 기수를 8로 하는 수 체계

• 0부터 7까지의 수 사용.
• 8을 한 자리의 기본 단위로 하는 진수.

16진수

Hexadecimal number
: 기수를 16으로 하는 수 체계

• 0부터 9까지의 수 + A부터 F까지의 영문자 사용. (두 자리수와 구분하여 한 자리수로 표현하기 위해 알파벳을 사용한다. A=10~)
• 16을 한 자리의 기본 단위로 하는 진수.

진법 변환

: 컴퓨터에서 처리하기 위해서 우리가 입력하는 10진수를 2,8,16진수로 변환해야하고 그 반대로도 처리 할 수 있어야한다.

• 직접적으로 8진수 ←→ 16진수 변환할 수 없어서 2진수나 10진수로 변환한 후 8진수나 16진수로 변환한다.

10진수 → 2진수, 8진수, 16진수 변환

10진수를 2진수, 8진수, 16진수로 변환할 때 정수부분과 소수부분을 변환하는 방법이 다르기 때문에 구분하여 변환한다.
정수부 변환 : 변환하려는 기수로 몫이 0이 될 때까지 나누면서 나오는 나머지를 역순으로 읽는다.
소수부 변환 : 소수부가 0이 될 때까지 변환하려는 기수를 곱한다. 이 과정에서 곱한 결과의 정수부분은 변환 결과로 사용하고 남은 소수부분만 0이 될 때까지 계속 0을 곱한다.

2진수, 8진수, 16진수 → 10진수 변환

: 해당 기수와 수를 구성하는 숫자의 자릿수 이용한다.

2진수 ←→ 8진수 변환

한 자릿수에서 가장 큰 수인 7은 2진수로 111이여서 8진수 한자리를 2진수로 표현할 때 최대 3 자릿수의 2진수가 필요하다. 즉, 2진수 3자리 = 8진수 한자리

2진수 → 8진수

진수를 소수점 기준으로 3비트씩 나누고 각 3비트를 10진수로 변환하여 구한다.

• 3비트씩 나눌 때 왼쪽 끝이나 오른쪽 끝의 비트가 3비트가 안되면 각각 앞과 뒤에 부족한 비트만큼 0을 추가하여 3비트로 만들어 변환한다.

8진수 → 2진수

각 숫자의 연산의 결과가 0이나 1이되어 결과가 1비트가 되거나 2나 3이 되어 2비트인 경우에 부족한 만큼 왼쪽을 0으로 채운다.

• 2진수로 변환 후 왼쪽과 오른쪽 끝에 있는 0은 지워도 되는 수이므로 지운다.

2진수 ←→ 16진수 변환

16진수는 한 자릿수에서 가장 큰 수인 F는 10진수로 15이고 2진수로 1111이다. 따라서 16진수 한자리로 표현할 때 최대 4자릿수의 2진수가 필요하다.
즉, 2진수 4자리 = 16진수 한자리

2진수 → 16진수

2진수를 소수점 기준으로 4비트씩 나누고 각 4비트를 10진수로 변환하여 구한다. 이때 10부터 15까지는 알파벳으로 표기한다.

• 4비트씩 나눌 때 왼쪽이나 오른쪽 끝의 비트가 4비트가 안되면 각각 앞과 뒤에 부족한 비트만큼 0을 추가하여 4비트로 만들어 변환한다.

8진수 → 16진수

각 숫자의연산의 결과가 1,2,3비트 인 경우 부족한 비트는 왼쪽을 0으로 채운다.

• 2진수로 변환한 후 왼쪽과 오른쪽 끝 0은 지워도 되는 수임으로 지운다.

이진법 연산

모든 진법의 사칙연산은 10진수의 연산과 덧셈에서 올림수가 발생하는 수와 뺄셈에서 빌림수가 다를 뿐 기본원리는 동일함.

• 올림수는 수의 체계와 관계없이 1이고 빌림수는 각 진수에 해당하는 수를 빌려온다.

이진법의 덧셈

: 두 수의 합이 2가 되면 한 자리가 올라간다. 즉, 1+1 = 10
이와 동일하게 8진수는 두 수의 합이 8이되면 한자리가 올라가고 16진수는 두 수의 합이 16이 되면 한자리가 올라간다.

보수

: 음수표현

• 제한된 자릿수의 정수만을 사용할 때 음의 부호 표현을 사용하는 대신 보수(Complement)를 이용하여 표현한다.

진수를 나타내는 수를 r이라고 할 때 r의 보수 / r-1의 보수로 나타낼 수 있다.

보수를 만드는 방법

r-1의 보수 : r-1의 값에서 수의 각 자리의 수 빼기
Ex) 1234(10) 의 9의 보수 : 9999(10) - 1234(10) = 8765(10)
	2진수의 1의 보수 : 1 → 0,  0 → 1
r의 보수 : r-1의 보수 + 가장 낮을 자리에 1 더해준다.
Ex) 1234(10) 의 9의 보수 : 9999(10) - 1234(10) + 1 = 8766(10)

보수를 이용한 뺄셈 : 음수를 보수로 표현하여 더하기

Ex) 7-4의 경우
7 + (-4) 로 연산한다.
-4 : 4에 대한 보수를 취하여 음수 표현 → -4 + 7 
1100(2) - 1001(2) = ?
1 101 + 0110 = 0100 = 13 - 9 = 4
(여기서 가장 왼쪽 비트 값이 0임으로 양수이다.)