개념 정리 - (1) 이산 수학 편
우리가 배운 개념이 어디서 어떻게 쓰이는지 알아보자
대학교에서는 다양한 전공 과목을 배운다. 학교라는게 여러 사람들을 동시에 가르치는 기관이다보니 세부 전공의 내용을 배우기보다는 두루 배우는 편이다. 이에 따라 생기는 문제가 도대체 내가 배우고 있는 이 개념이 어디서 쓰이길래 배우는 것인지 알기 어렵다는 것이다. 나름대로 대학교 강의를 수강하는 과정에서 이 개념을 왜 배우는지 많이 고민했었는데, 이번 개념 정리 글 시리즈에서 전공 과목별 몇 가지 주요 개념들을 왜 배우는지 소개해보고자 한다.
이산 수학은 정말 완전 기초에 해당하는 과목이기 때문에 필요성을 이해하기가 쉽지 않다. 마치 공기와 같아서 자신도 모르게 이미 쓰고 있거나, 다른 기본 개념에 녹아있는 개념들이 많다. 예를 들어 명제나 집합에 대해 왜 배워야하는지 설명하기란 쉽지 않지만 컴퓨터 공학의 여러 세부 전공에 대해 공부하면서 명제나 집합 개념을 잘 이해하고 있지 않다면 이해도가 떨어지는 결과로 나타난다. 재귀나 그래프, 트리, 탐색 같은 매우 중요하지만 그 중요성을 쉽게 느낄 수 있는 부분은 제외하고 작성하였다. 아마 추후 다른 편에서 소개할 수도 있을 것이다.
1차 논리(First Order Logic)
명제와 논리는 중등 교육 과정에서부터 중요하게 다뤄지기 때문에 다들 잘 알 것이다. 이산 수학에서는 명제를 넘어서 생소한 1차 논리라는 것을 다룬다. 나는 프로그래밍을 하는 친구들에게 1차 논리를 설명할 때 이해를 돕기 위해 변수 개념을 이용하여 설명하는데, 완전히 대치 가능한 개념은 아니지만 이해를 쉽게 해주기 때문이다. 1차 논리는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이다. 예를 들어 "x가 한국인이라면 x는 인간이다. : Korean(x) -> Man(x)"와 같은 논리를 표현할 수 있는데, 이 논리에서 x를 변수로 이해하면 좀 더 쉽게 느껴질 것이다. 위 예에서 변수 x가 나타내는 집합을 정의역(Domain)이라고 하며, 이 x에 전칭 기호(Universal Quantifier), 존재 기호(Existential Quantifier)를 붙여 표현력을 키울 수 있게 된다.
여기서 말하는 표현력을 키운다는 것이 무슨 의미인지 말하기 위해 좀 더 나아가보자. 인공 지능의 종류 중 논리적 에이전트(Logical Agent)라는 것이 있다. 인간이 완전히 논리적 사고를 하는 동물은 아니지만 뇌에서 논리적으로 사고할 수 있는 능력이 있는데, 이것을 모사한 인공 지능이다. 이 인공 지능은 가진 지식(Knowledge Base)을 기반으로 논리적 사고를 하여 질의(Query)에 대해 응답하는 방식으로 작동한다. 예를 들어, "소크라테스는 사람이다", "플라톤은 사람이다"라는 지식을 갖고 있으면 "플라톤이 사람인가"라는 질의에 대해 논리적 계산을 통해 참이라는 답을 내릴 수 있는 것이다.
문제는 사람이 한 두 명이 아니라는 것이다. 컴퓨터의 메모리는 한정되어 있기 때문에 수 십, 수 백억 사람들에 대한 명제 논리를 지식으로 모두 갖고 있을 수가 없다. 이 때, 표현력을 좀 더 키운 술어 논리로 지식을 구성하도록 하고, 술어에 한정 기호를 사용함으로써 좀 더 적은 데이터로 더 많은 정보를 표현할 수 있도록 하는 것이다. 예를 들어, "모든 사람은 죽는다", "플라톤은 사람이다"라는 술어 논리 지식을 갖고 있으면 플라톤이 죽느냐는 질의에 대해 참이라고 응답할 수 있게 된다.
위 내용은 앞으로도 계속 인지해야 할 컴퓨터는 물리적 한계를 가진 존재라는 것을 함의하고 있다. CPU도, 메모리도, 기억 장치도, 네트워크 자원도 모두 부족하다. 부족한 자원 내에서 최고의 효율을 추구해야한다. 그것을 위해 각종 수학적인 기술을 총동원한다.
나머지 연산(Modular Arithmetic)
사칙연산은 굳이 말하지 않아도 다들 필요성을 많이 이해하고 있지만, 나머지 연산은 실생활에서 필요로 하게 되는 일이 잘 없다보니 왜 배우는지 납득이 잘 되지 않는 것이 사실이다. 게다가 중국인의 나머지 정리(Chinese remainder theorem)는 또 왜 그렇게 중요하게 다루는지... 특이한 알고리즘 문제를 풀지 않는 이상 정수론은 알고리즘적인 문제 해결을 하지 않는 이상 직접 느낄 일이 거의 없고, 다른 적절한 예로 암호학이 있다. 아마 많은 대학에서 교재로 선택하는 이산 수학 책에서도 분명 RSA 암호화를 예시로 들 것이다.
중국인의 나머지 정리 같은 것을 왜 배우냐하면 결국 효율성을 위한 것이다. 참조되어 있는 위키피디아에서 말했듯이 OpenSSL 같은 암호화 기능이 있는 라이브러리에서는 복호화의 효율성을 위해 중국인의 나머지 정리를 활용한다.
이항 관계(Binary Relation)
집합 내의 원소들간의 존재할 수 있는 관계에 대한 개념이다. 이항 관계는 n항 관계에서 n이 2인 특수 경우이다. 우리가 흔히 생각하는 "a는 b보다 크다"와 같은 개념도 관계의 하위 개념이다.관계를 이야기하면서 함수를 빼놓을 수가 없는데, 함수는 관계의 하위 개념이면서 동시에 프로그래밍의 꽃이라고 볼 수 있기 때문이다. 함수가 관계의 하위 개념이라는 것은 함수가 나타낼 수 있는 개념의 영역이 이항 관계가 나타낼 수 있는 개념의 영역의 부분 집합이라는 뜻이다. 왜냐하면 함수의 정의가 "첫 번째 집합의 임의의 한 원소를 두 번째 집합의 오직 한 원소에 대응시키는 대응 관계"이기 때문이다.
출처 : https://plus.google.com/u/0/+JoelDavidHamkins1/posts/Gu3eScwxDzf이항 관계 중에서도 몇 가지 특이한 관계가 유형으로 정의되어 있다. 반사 관계, 대칭 관계, 반대칭 관계, 비대칭 관계, 추이 관계가 그것인데,각 관계의 정의는 위키피디아에 잘 정리되어 있으니 찾아보는 것이 어렵지 않을 것이다. 추이 관계가 앞으로 공부하면서 자주 등장할 수 있는 개념인데, 데이터베이스의 관계를 제 3 정규형을 만들기 위해(정규화) 추이적 함수 종속성을 제거해야한다는 것에서 추이 관계가 녹아있음을 알 수 있다. 또는, 그래프에서 경로 개념에서 추이적 관계를 생각할 수도 있다. 만약 정점 a와 b(aRb), b와 c(bRc)가 연결되어 있으면 a에서 c로 가는 경로가 존재한다(aRc)는 식으로 생각할 수 있는 것이다.
부분 순서(Partial Order)
집합 A에 대한 관계 R이 반사 관계, 반대칭 관계, 추이 관계이면 이 관계 R을 부분 순서 관계(Partial Ordered Relation)이라고 한다. 순서라는 단어만 봐도 예상할 수 있는 것이 선행자, 후행자 관계일 것이다. 예를 들어 빨래를 한다고 생각하면 먼저 빨래를 세탁기로 세탁하는 작업을 끝낸 뒤에야 빨래를 널어서 말릴 수 있고, 빨래가 다 마른 뒤에야 개어서 정리해둘 수 있다.
이런 식으로 작업간의 선후관계가 정의되어 있다면 어떤 순서로 작업을 수행할 수 있는지를 파악할 수 있다. 그 순서대로 정렬하는 것을 위상 정렬(Topological Sort)이라고 한다. 위상 정렬은 임계 경로(Critical Path)를 찾는 알고리즘에 이용될 수 있다. PERT(Program Evaluation and Review Technique) 차트 상에서 병목을 일으키는 작업을 찾기 위해서는 임계 경로를 구하는 것이 효과적인데, 위에서 예를 든 빨래가 아니라 기업의 프로젝트 진행 계획과 같이 복잡한 순서 관계상에서 임계 경로를 눈으로 찾기란 매우 어렵다. 이 때, 부분 순서를 이용한 임계 경로를 찾는 알고리즘을 이용할 수 있다.
불 대수(Boolean Algebra)
일단 공부하라니까 하지만 왜 하는지 이해가 안 되는 불 대수일 것이다. 사실 나도 불 대수를 공부해야 할 필요성을 강하게 느끼지 못하기도 하지만, 어디서 쓰이는지 대략적이나마 언급하고자 한다. 코딩하면서 if 문의 조건에 여러 가지 조건을 and 혹은 or 조건으로 결합하는 것도 불 대수라고 볼 수 있으며, 좀 더 컴퓨터의 하드웨어 레벨로 내려가면 산술논리 연산장치(ALU : Arithmetic Logic Unit)에서도 논리 게이트들을 구성하기 위해 불 대수 지식을 요구한다. 아니, 전자 회로는 그냥 전부 다 불 대수 덩어리다....
계속해서 효율성에 대해 이야기를 하지 않을 수가 없는데, 논리 게이트들을 더 적게 써서 연산장치를 만들면 더 적은 비용으로 연산장치를 생산할 수 있게 된다. 즉, 다른 형태의 불 대수 식이더라도 결과가 같다면 더 간소화 된 불 대수 식을 선택하는 것이 효율적이라는 뜻이다. 이 간소화 작업에서 카르노 맵 기법이 쓰일 수 있다. 여담으로 if 문의 조건이 매우 복잡한 것을 카르노 맵을 이용하여 간소화 한 뒤 즐거워하던 지인이 기억난다(?)
나는 전자 회로 쪽보다는 좀 더 소프트웨어 계층에 가까워서 이 부분은 더 이상 언급하기가 곤란하므로 넘어가겠다.
이상 이산 수학에서 몇 가지 개념들이 어떻게 활용되는지 알아보았다. 다음 편에서는 선형 대수에 대해 다뤄보겠다.
