JANGUN


이산수학


지음 : 손 진곤



목차

요약
제1장 이산수학의 개요
제2장 논리
제3장 증명
제4장 집합론
제5장 행렬
제6장 관계
제7장 함수
제8장 부울대수
제9장 그래프
제10장 트리
제11장 조합이론
제12장 알고리즘
제13장 오토마타 및 형식 언어


요약

이산수학이란 : 이산적인 수학구조에 대해서 연구하는 학문
성공적인 문제 해결을 위해 도구, 기법, 방법론 선택이 중요하다.
- 수학의 도구(정의, 정리), 기법(근의 공식), 방법론(도구, 기법을 효율적으로 선택)
추상화 : 문제와 관련된 핵심 내용을 남기기 위해 관련 없는 내용을 제거 혹은 단순화 시키는 과정
정보모델링 : 실생활의 문제를 컴퓨터에서 해결할 수 있는 형태로 단순화 시키는 과정
알고리즘 언어 : 알고리즘을 모호하지 않게 표현하기 위해 컴퓨터 프로그래밍 언어, 순서도, 의사코드 등을 사용
이산 수학 응용분야 : 전문가 시스템, 그래픽, 데이터베이스, 디지털회로설계, 컴퓨터 네트워크

명제란 : 참과 거짓을 구분할 수 있는 문장 또는 수식, 논리합, 논리곱, 부정, (배타적 논리합)
명제함수 : 변수의 값에 의해 함수의 진리 값이 결정되는 문장이나 식
추론 : 참이라고 알려져 있는 사실로부터 논리적인 과정을 거쳐 참인 사실들을 이끌어 내는 과정

공리 : 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 기본적인 가정
증명 : 특정한 공리들을 가정하고 명제가 참임을 입증하는 작업
정리 : 가정(공리, 정의)으로부터 증명된 명제
증명방법 : 직접증명법, 수학적 귀납법, 간접 증명법
기타 증명법 (전수증명법, 조합적 증명법, 컴퓨터를 이용한 증명)

논리학과 집합론

행렬의 종류 : 정방행렬, 단위행렬, 대각행렬, 대칭행렬, 교대행렬, 삼각행렬, 전치행렬
부울행렬 : 0과 1로 구성된 행렬, 부울행렬의 합(V), 교차(⋀), 부울곱(⊙)

곱집합 : A x B = { (a, b) | a ∈ A, b ∈ B }

관계 R : A에서 B로의 관계 R ⊂ A x B
- 관계의 표현 : 화살표 도표, 방향 그래프, 부울행렬
- 관계의 성질 : 반사적, 대칭적, 추이적 - 동치관계
- 관계의 종류 : 역관계, 합성관계, 동치관계(동치류)

전사, 단사, 역함수, 합성함수
함수의 종류 : 계승함수(factorial), 바닥함수, 천정함수, 나머지함수

디지털 논리회로 : 기본 논리 게이트 (AND, OR, NOT) + 기타 (NAND, NOR, XOR, XNOR)
쌍대성원리, 부울함수의 보수, 부울함수의 대수적 간소화

그래프 G = (V, E) : Vertex, Edge, 방향 그래프, 무향 그래프, 단순 그래프
- 그래프 탐색 : 워크, 트레일, 경로
- 그래프 종류 : 완전 그래프, 이분 그래프, 완전 이분 그래프, 정규 그래프
- 그래프 표현 : 발생 행렬, 인접 행렬, 인접 리스트
- 평면 그래프 : 그래프의 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프
- 오일러 투어 : 시작점과 종점이 같고 모든 변들을 각각 한 번씩만 지나는 트레일
- 해밀턴 경로 : 모든 꼭지점들을 한 번씩만 지나는 경로, cf) 해밀턴 싸이클 : 닫힌 해밀턴 경로
- 가중 그래프 : 그래프의 각 변에 실수(가중치:weight)가 붙여진 그래프
- 최단 경로 문제 : 데이크스트라 알고리즘

트리 : 싸이클이 없는 연결 그래프. 무방향 그래프이면서 싸이클이 없는 그래프
- 주요 용어 : 자식 노드, 부모 노드, 형제 노드, 단말 노드, 내부 노드, 노드의 차수, 트리의 차수, 노드의 레벨(루트노드의 레벨은 '0'), 트리의 높이, 트리의 무게
- 이진 트리 : 공집합이거나 모든 노드가 최대 2개의 서브 트리를 갖는 루트 트리
- 이진 탐색 트리 : 키 값을 노드에 저장하고 검색하기 위해 수성된 이진 트리,
- 최소 신장 트리 (MST) : 그래프 G의 모든 꼭지점을 포함하는 트리(신장 트리) 중 총 가중치가 가장 작은 것 (Kruskal 알고리즘, Prim 알고리즘)

순열 : P(n, r) = n! / (n-r)! / 중복 순열 : n ∏ r = nr / 원순열 : n! / n = (n-1)!
조합 C(n, r) = P(n, r) / r! = n! / r! x (n-r)!

알고리즘 : 문제를 해결하기 위한 명령어들의 유한 집합,
자료구조 : 효율적이며 인간지향적으로 데이터를 추상화한 결과
프로그램 = 알고리즘 + 자료구조
복잡도 분석 : 점근 성능의 표기법 (O, Ώ, Θ)

오토마타 (Automata) : 스스로 움직이는 기계, 자동 장치
유한 오토마타 (Finite Automata) : M = ( I, O, Q, f, g, σ ) 6개의 튜플로 구성
- 결정적 유한 오토마타(DFA), 비결정적 유한 오토마타 (NFA)
형식 언어 : 알파벳(음소)과 문제열(string), ∑n, ∑+, ∑*, 언어(Language)
형식 문법 : 문법, 유도 , L(G) – 문법에서 언어를 유도한다.
Chomsky 계층 : 무제약 문법, 문맥 의존 문법, 문맥 자유 문법, 정규 문법


제1장 이산수학의 개요

이산수학이란 : 이산적인 수학구조에 대해서 연구하는 학문
- 수학 : 대수학 / 해석학 / 기하학, 이산수학 / 연속수학

성공적인 문제 해결을 위해 도구, 기법, 방법론 선택이 중요하다.
수학의 도구, 기법, 방법론
- 도구 : 정의, 정리
- 기법 : 가우스 소거법, 근의 공식
- 방법론 : 상황에 따라 효과적이고 효율적인 도구와 기법을 선택하는 것

추상화 : 문제와 관련된 핵심 내용을 남기기 위해 관련 없는 내용을 제거 혹은 단순화 시키는 과정
- 일정한 인식 목표를 추구하기 위하여 여러 가지 표상이나 개념에서 특정한 특성이나 속성을 빼냄.
정보모델링 : 실생활의 문제를 컴퓨터에서 해결할 수 있는 형태로 단순화 시키는 과정
알고리즘 언어 : 알고리즘을 모호하지 않게 표현하기 위해 컴퓨터 프로그래밍 언어, 순서도, 의사코드 등을 사용
- 알고리즘 : 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임

이산 수학 응용분야 : 전문가 시스템, 그래픽, 데이터베이스, 디지털회로설계, 컴퓨터 네트워크


제2장 논리

명제란 : 참과 거짓을 구분할 수 있는 문장 또는 수식
- 명제의 진리값 : 참과 거짓 - 논리연산 : 논리합 (∨), 논리곱 (∧), 부정 (~), 배타적 논리합 (⊕)
- 합성명제, 조건명제 (→), 쌍조건 명제(↔), 논리적 동치 (≡)
- 항진명제와 모순 명제

논리 (logic)
- 명제 논리 : 명제
- 술어 논리 : 명제함수
- 명제함수 : 변수의 값에 의해 함수의 진리 값이 결정되는 문장이나 식
- 전체한정자(모든), 존재한정자(존재)

추론 : 참이라고 알려져 있는 사실로부터 논리적인 과정을 거쳐 참인 사실들을 이끌어 내는 과정
- 전제(premise) : 결론의 근거롤 제공하는 알려진 명제
- 결론(conclusion) : 새로 유도된 명제
- 유효 추론 : 전제를 참이라고 가정하였을 때 결론이 항상 참인 추론
- 추론 규칙 : 논리적 동치를 이용


제3장 증명

정의 : 공리, 증명, 정리
- 공리 : 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정
- 증명 : 특정한 공리들을 가정하고 명제가 참임을 입증하는 작업
- 정리 : 가정(공리, 정의)으로부터 증명된 명제

증명방법 :
- 직접증명법 (연역법 deduction) :공리와 정의, 그리고 정리를 논리적으로 직접 연결하여 증명한다.
- 연역법 : 이미 증명된 하나 또는 둘 이상의 명제를 전제로 하여 새로운 명제를 결론으로 이끌어내는 것.

- 수학적 귀납법 : 모든 자연수 n에 대해 명제가 성립함을 증명하는 방법
-- 출발점 n=1일때 성립을 보임 (n의 출발점에서 명제가 성립하는가 확인)
-- n=k일때 성립한다고 가정
-- n=k+1일 때도 성립함을 증명)

- 간접 증명법 : 증명해야 핛 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법이다. 대우증명명, 모순증명법, 반례증명법, 존재증명법
- 기타 증명법 : 전수증명법, 조합적 증명법(전단증명, 중복산정), 컴퓨터를 이용한 증명


제4장 집합론

논리학과 집합론
- 집합과 원소, 집합의 표기법, 부분집합, 집합의 분할(partition), 집합의 멱집합
- 무정의 용어 : 정의 없이 사용하는 용어, 직관적으로 이해핛 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용됨
- Georg Cantor의 집합 “우리의 직관이나 사고로부터 핚정적이고 분리된 객체들의 전체 M에서의 수집”

집합의 표기법 :
- 원소나열법 (예) S = {1, 2, 3}
- 조건나열법 (예) S = { x | x는 0보다 크고, 4보다 작은 자연수}
- 집합의 원소 : a ∈ S, b !∈ S
- 부분 집합 : A는 B의 부분집합이라 하고 A ⊂ B
- 집합의 분할 : 집합 A를 ∅이 아닌 부분집합들로 나눌 때 A의 모든 원소들이 각각 나누어진 부분집합들 중 하나에만 포함될 경우 이 부분집합들 전체의 집합을 A의 분할이라고 함.
- 멱집합 : 집합 A의 모든 부분집합들의 집합을 A의 멱집합이라고 하고, P(A)로 표기

집합연산 : 합집합, 교집합, 차집합, 여집합, 대칭 차집합 (=> 배타적 논리합)
- 집합의 대수법칙 : n(A ⋃ B) = n(A) + n(B) – n(A ⋂ B)
- 교환법칙, 결합법칙, 분배법칙, 드모르간 법칙, 항등법칙, 보수법칙, 이중보수법칙, 멱등법칙, 전체한계법칙, 흡수법칙

러셀(Bertrand Russell)의 역설 : 초기의 '소박한' 집합론에 모순이 있음을 밝힘
- 대부분의 집합은 원소와 원소의 집합이 서로 다름
- M을 "자싞을 원소로 포함하지 않는 모든 집합들의 집합"이라고 정의할 때, M ∈ M ?
- 이러한 상황 자체가 존재하지 않는데 억지로 정의하였기 때문에 모순이 발생.
- 세비아에는 스스로 이발하지 않는 모든 사람들만 이발시켜 주는 이발사(M)가 있다. 이 이발사는 스스로 이발을 할까?


제5장 행렬

m x n 행렬, A = (aij), 행벡터, 열벡터
- 영행렬

행렬의 연산 : 합, 차, 곱, 스칼라 곱
- 행렬 곱 연산의 특이 성질 : 교환법칙이 성립하지 않는다.

가우스 소거법 : 일차연립방정식 - 확장행렬 - 행사다리꼴 - 기약 행사다리꼴

행렬의 종류 : 정방행렬, 단위행렬, 대각행렬, 대칭행렬, 교대행렬, 삼각행렬, 전치행렬

부울행렬 : 0과 1로 구성된 행렬, 부울행렬의 합(V), 교차(⋀), 부울곱(⊙)


제6장 관계

곱집합 : A x B = { (a, b) | a ∈ A, b ∈ B }
관계 R : A에서 B로의 관계 R ⊂ A x B
- 관계의 표현 : 화살표 도표, 방향 그래프, 부울행렬
- 화살표 도표

- 방향 그래프 : 점[꼭지점](vertex)과 선[변](edge)으로 이루어진 도형으로 방향을 가진 그래프 ~ G = (V, E)

- 부울행렬 :


관계의 성질 :
- 반사적 : ∀a∈A, (a, a)∈R
- 대칭적 : ∀a, b ∈A, a,b ∈R => (b, a) ∈R
- 추이적 : ∀a, b, c ∈A, ((a,b) ∈R (b,c)∈R) =>(a,c)∈R
=> 반사, 대칭, 추이적이면 동치관계가 성립한다

관계의 종류 : 역관계, 합성관계, 동치관계(동치류)


제7장 함수

함수 : 관계의 특별한 상황
- X에서 Y로의 함수(function) f : ∀x∈X,∃!y∈Y, x,y∈f 를 만족하는 X에서 Y로의 관계
- X:f의 정의역, Y:f의 공역
- y:x의 상, x:y의 역상
- f(X) : f의 치역 (f(X)={y∈Y|∀x∈X, y=f(x)})

전사 : 함수 f:X->Y가 전사함수(surjective function) ⇔ ∀y∈Y,∃x∈X, f(x) = y
단사 (1대일 함수) : 함수 f:X->Y가 단사함수(injective function) ⇔ ∀x1,∀x2∈X, f(x1)=f(x2)
=> x1=x2 = ∀x1,∀x2∈X, x1!=x2 => f(x1) != f(x2)
전단사함수 : 함수 f:X->Y가 전단사함수(bijective function) = f가 전사함수 ∧ f가 단사함수
역함수 : 함수 f:X->Y가 전단사함수일 때, f의 역관계 f−1를 f의 역함수(inverse function)
합성함수 : 두 함수 f:X->Y와 g:Y->Z에 대해, 다음과 같이 정의되는 함수 g*f:X->Z를 f와 g의 합성함수(composition function)
- ∀x∈X, (g*f)(x)=g(f(x))
함수의 종류 : 계승함수(factorial), 바닥함수(버림), 천정함수(올림), 나머지함수(mod)


제8장 부울 대수

디지털 논리회로 : 기본 논리 게이트 (AND, OR, NOT) + 기타 (NAND, NOR, XOR, XNOR)
부울 대수의 기본정리


부울 대수의 성질 : 항등법칙, 지배법칙, 멱등법칙, 부정법칙, 교환법칙, 결합법칙, 분배법칙, 드모르간 법칙, 흡수법칙
쌍대성원리 : 부울식에서 논리곱( ∙ )과 논리합(+)을 서로 바꾸고 논리상수 0과 1을 서로 바꾸면 원래 부울식의 쌍대(dual)를 얻게 됨
- 주어진 부울식과 그것의 쌍대는 진리값이 서로 같다.
부울함수의 보수 : 드 모르간 법칙을 이용하거나 쌍대성 원리를 이용한다.
부울함수의 대수적 간소화 : 항결합, 문자 소거, 합의 정리


제9장 그래프

그래프 G = (V, E) : Vertex, Edge
- 방향 그래프, 무향 그래프, 단순 그래프
- 주요 용어 : 부분 그래프 (부분 집합), 신장 부분 그래프 (꼭지점은 동일한 부분 그래프), 차수(degree), 진입차수, 진출차수

그래프 탐색 : 워크, 트레일, 경로
그래프 종류 : 완전 그래프, 이분 그래프, 완전 이분 그래프, 정규 그래프
그래프 표현 : 발생 행렬, 인접 행렬, 인접 리스트

특수한 그래프
- 평면 그래프 : 그래프의 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프
- 오일러 투어(싸이클) : 시작점과 종점이 같고 모든 변들을 각각 한 번씩만 지나는 트레일
- 해밀턴 경로 : 모든 꼭지점들을 한 번씩만 지나는 경로, cf) 해밀턴 싸이클 : 닫힌 해밀턴 경로

그래프의 활용
- 가중 그래프 : 그래프의 각 변에 실수(가중치:weight)가 붙여진 그래프
- 최단 경로 문제 : 데이크스트라 알고리즘


제10장 트리

트리 : 싸이클이 없는 연결 그래프. 무방향 그래프이면서 싸이클이 없는 그래프
주요 용어 : 자식 노드, 부모 노드, 형제 노드, 단말 노드, 내부 노드, 노드의 차수, 트리의 차수, 노드의 레벨(루트노드의 레벨은 ‘0’ ), 트리의 높이, 트리의 무게
트리의 표현 : 중첩된 집합, 중첩된 괄호, 결각

주요 정리 : G = (V, E)가 |V| = n인 연결 그래프에서 G가 트리이기 위한 필요충분조건은 |E| = n-1 (|E| =Edge의 수)

이진 트리 : 공집합이거나 모든 노드가 최대 2개의 서브 트리를 갖는 루트 트리
- 이진 트리의 종류 : 완전 이진 트리, 포화 이진 트리, 경사 이진 트리
- 이진 탐색 트리 : 키 값을 노드에 저장하고 검색하기 위해 수성된 이진 트리, 검색의 효율을 고려한 이진 트리

주요 정리
- 높이가 k인 포화 이진 트리의 노드 수 : 2k+1 – 1
- N개의 노드의 이진 트리의 최소 높이 Hmin = ⌊log2n⌋ (바닥함수)
- 최소 신장 트리 (MST) : 그래프 G의 모든 꼭지점을 포함하는 트리(신장 트리) 중 총 가중치가 가장 작은 것
- Kruskal 알고리즘, Prim 알고리즘


제11장 조합이론

기본 계수 법칙 : 곱의 법칙 (동시), 합의 법칙 (또는)
- 순열 : n개의 원소를 갖는 집합에서 순서를 고려해 r개의 원소를 뽑는 방법의 수 -> P(n, r) = n! / (n-r)!
- 중복 순열 : n ∏ r = nr
- 원순열 : n! / n = (n-1)!

-조합 : n개의 원소를 갖는 집합에서 순서를 무시하고 r개의 원소를 뽑는 방법의 수 - C(n, r) = P(n, r) / r! = n! / r! x (n-r)!
- 이항 정리 :
- 확률 : 수학적 확률, 통계적 확률
- 수학적 확률 : p(E) = 특정 사건의 경우의 수 / 전체 사건의 경우의 수
- 점화식 : 주어진 수열의 항 사이에 성립하는 관계식, 일반항 an을 n에 관한 함수(식)으로 나타내는 것


제12장 알고리즘

알고리즘 : 문제를 해결하기 위한 명령어들의 유한 집합, 입력-출력-명확성-유한성-유효성이 있어야 한다.
자료구조 : 효율적이며 인간지향적으로 데이터를 추상화한 결과
- 프로그램 = 알고리즘 + 자료구조

알고리즘 분석의 기준 : 정확성, 수행량, 기억장소 사용량, 단순성, 최적성
알고리즘의 복잡도 : 시간 복잡도, 공간 복잡도
복잡도 분석 : 점근 성능의 표기법 (O, Ώ, Θ)
정렬 알고리즘 : 선택 정렬, 퀴 정렬, 병합 정렬


제13장 오토마타와 형식 언어

오토마타 (Automata) : 스스로 움직이는 기계, 자동 장치
- 유한 오토마타 (Finite Automata) : M = ( I, O, Q, f, g, σ ) 6개의 튜플로 구성
- 결정적 유한 오토마타(DFA), 비결정적 유한 오토마타 (NFA)

형식 언어 : 알파벳(음소)과 문제열(string), ∑n, ∑+, ∑*, 언어(Language)
형식 문법 : 문법, 유도 , L(G) – 문법에서 언어를 유도한다.
- Chomsky 계층 : 무제약 문법, 문맥 의존 문법, 문맥 자유 문법, 정규 문법