1.1. 개요
“이산수학”(Discrete Mathematics)은
“가산집합”(Countable Set)의 영역에 해당하는 개념과 원소의 특징에 대해 설명하는 수학과목입니다.
이번 과목인 이산수학은 조합론과 정수론이 다소 섞여서 설명이 이루어지기 때문에
“조합론” 또는 “정수론”에 대해 심도 있게 다루고자 하는 의도로 제작되지 않았다는 점을 미리 밝힙니다.
또한, 이산적인 개념에 걸맞게 프로그램 코드를 추가로 사용하여 설명하기 위해
C++ 또는 Haskell을 예제로 사용 할 예정이므로 만약, C++, Haskell을 배우거나 설명을 보고 싶으시다면
Develop에 PL파트를 참고하여 주시고
예제가 이해가 안된다면 그냥 넘어가도 이해가 되도록 수학적 정의는 언급 할 예정입니다.
1.2. 페아노 공리
“주세페 페아노”(Giuseppe Peano) 의 “자연수에 대한 공리”는 다음과 같습니다.
1). \(1 ∈ ℕ\) ( \(ℕ\) 은 자연수 집합 )
2). \(∀n ∈ ℕ , ∃! succ(n)\)
3). \(∄ n ∈ ℕ : succ(n) = 1\)
4). \(a , b ∈ ℕ => succ(a) = succ(b) => a = b\)
5). \(1 ∈ ℕ ∧ n ∈ ℕ => succ(n) ∈ ℕ\)
다음은 haskell로 자연수를 사용한 예제입니다.
--Natural numbers type in haskell
data Nat = One | Succ Nat
toInt :: Nat -> Int
toInt One = 1
toInt (Succ n) = 1 + toInt n
main = do
print $ toInt One
print $ toInt (Succ (Succ (Succ One)))“닫힘 성질”(Closure Property)은 어떠한 연산(함수)이 정의역과 공역이 같은 범위로 정의 가능하면,
닫힘 성질을 만족한다고 표현하고,
닫힘 성질을 만족하는 입력 두 개의 함수( \(A (*) A -> A\) 꼴 )를 “이항 연산”으로 표현합니다.
( 자세한 자연수의 성질은 해석학에 설명되어 있습니다. )
1.3. 소수
소수(Prime Number)는 \(1\)과 자기 자신만 나누어 떨어지는 \(1\)을 제외한 자연수들의 집합입니다.
반대로, 합성수(Composite Number)는 소수를 제외한 \(1\)을 제외한 자연수 집합의 나머지들의 집합입니다.
추가로, 자연수 \(1\)은 소수도 합성수도 아닙니다.
컴퓨터에서는 소수를 구할 때, 에라토스 테네스의 체를 보편적으로 사용하기 때문에,
에라토스 테네스의 체에 대해 간략하게 살펴 보겠습니다.
에라토스 테네스의 체는 다음과 같습니다.
1). \(2\)부터 하나씩 값을 선정합니다.
2). 선정된 값이 필터가 되지 않은 값이면, 그 값은 “소수”입니다.
3). 선정된 값이 소수이면, 그 값의 배수가 되는 값들을 필터링 합니다.
haskell 코드로는 다음과 같습니다.
--Sieve_of_Eratosthenes in haskell
primes :: Int -> [Int]
primes n = sieve [2..n]
where
sieve :: [Int] -> [Int]
sieve [] = []
sieve (prime : xs) = prime : sieve [x | x <- xs, x `mod` prime /= 0]
main = do
print $ primes 1001.4. 논리연산
두 “부울”의 연산은 산술연산과 유사하지만 조금 다르게 정의하여 사용되고 있습니다.
( 논리는 둘 중 하나( 진실 아니면 거짓 )이기 때문에 이항연산의 정의도 조금은 다른느낌이 됩니다. )
1). \(∧ :\) 논리 곱, (AND) <=> \(True ∧ True = True\) , 나머지는 \(False\)
2). \(∨\) : 논리 합, (OR) <=> \(False ∨ False = False\) , 나머지는 \(True\)
3). \(¬\) : 부정 기호, \(\sim\), (NOT) <=> \( ¬True = False, ¬False = True\)
이론적으로 이 세가지로 모든 부울 연산을 수행 할 수 있습니다.
다음은 위의 연산으로 자주 쓰이는 응용연산을 정의합니다.
4). \(⊕\) : 베타적 논리 합, (XOR) : \(P ⊕ Q => (¬P ∧ Q) ∨ (P ∧ ¬Q)\) ( 두 값이 다를 때 True 같으면 False )
5). \(→\) : 논리 함축 : \(=> : P → Q => ~ P ∨ Q\) ( \(True → False = False\), 나머지는 \(True\) )
6). \(⇔\) : 동치 : \(P ⇔ Q => P → Q ∧ Q → P <=> ¬( P ⊕ Q )\) ( 두 값이 같을 때 \(True\) 다르면 \(False\) )
어떤 명제에 대해 \(P → Q\) 라고 표현할 수 있고, 해당 명제에는 다음 3개의 추가적인 관계를 만들 수 있습니다.
1). 역 : \(Q → P\) ( 가정과 결론을 바꾼 명제입니다. )
2). 이 : \(¬P → ¬Q\) ( 가정과 결론을 반대로 정의한 명제입니다. )
3). 대우 : \(¬Q → ¬P\) ( “역” 명제를 “이” 하거나 “이” 명제를 “역” 한 명제 입니다. )
이 때, 기본 명제와 대우 명제는 논리적 동치가 됩니다.
따라서 대우 명제가 참임을 밝혀 해당 명제를 증명하는 방법이 존재하고 이를 대우증명법이라고 표현합니다.
또한, 역과 이도 논리적 동치가 됩니다.
다음은 haskell로 기호와 정의를 나타낸 것입니다.
--AND
(∧) :: Bool -> Bool -> Bool
True ∧ True = True
_ ∧ _ = False
--OR
(∨) :: Bool -> Bool -> Bool
False ∨ False = False
_ ∨ _ = True
--NOT ¬ 또는 ~을 쓰지만 언어의 한계상 (¬)로 정의하였습니다.
(¬) :: Bool -> Bool
(¬) True = False
(¬) False = True
--IMPLICATION
(⇒) :: Bool -> Bool -> Bool
True ⇒ False = False
_ ⇒ _ = True
--EQUIVALENCE
(⇔) :: Bool -> Bool -> Bool
True ⇔ True = True
False ⇔ False = True
_ ⇔ _ = False
--XOR
(⊕) :: Bool -> Bool -> Bool
True ⊕ True = False
False ⊕ False = False
_ ⊕ _ = True
--NAND
(⊼) :: Bool -> Bool -> Bool
True ⊼ True = False
_ ⊼ _ = True
--NOR
(⊽) :: Bool -> Bool -> Bool
False ⊽ False = True
_ ⊽ _ = False
--XNOR
(⊻) :: Bool -> Bool -> Bool
True ⊻ True = True
False ⊻ False = True
_ ⊻ _ = False다양한 명제에 대해서 모든 경우의 수에 대해서 진리표를 작성하여
해당 명제를 축소 시키거나 어떠한 다른 명제로 유도를 해내는 방식으로 사용 가능합니다.
모든 명제는 반드시 세 가지 중 하나로 표현할 수 있습니다.
1). \(T\) : 항진명제(Tautology)는 항상 참의 진리 값을 가지는 명제입니다.
2). \(F\) : 모순명제(Contradiction)는 항상 거짓의 진리 값을 가지는 명제입니다.
3). 사건명제(Contingency)는 항진명제도 아니고 모순명제도 아닌 명제입니다.
1.5. 부울행렬
행렬의 자세한 정의는 선형대수학에 엄밀하게 설명되어 있습니다. 여기서는 부울행렬에 대해서만 다뤄보겠습니다.
“부울 행렬”(Boolean Matrix)은 “부울”(Boolean)로 치환 가능한 행렬을 나타냅니다.
( 원소가 둘 중 하나로만 치환된다면 부울 행렬이 될 수 있습니다. )
다음은 부울 행렬의 이항연산 중 세 가지를 정의 한 것입니다.
어떠한 행렬 \(A\) 와 \(B\)에 대해
1). \(A ∨ B\) : ( \(A\)와 \(B\)의 논리 합(Join) ) <=>
결과 행렬 \(C\) 와 \(A\) 와 \(B\)의 행의 수와 열의 수가 모두 같습니다.
( \( C_{ij} = ( A_{ij} ∨ B_{ij} ) \) )
2). \(A ∧ B\) : ( \(A\)와 \(B\)의 논리 곱(Meet) ) <=>
결과 행렬 \(C\) 와 \(A\) 와 \(B\)의 행의 수와 열의 수가 모두 같습니다.
( \( C_{ij} = ( A_{ij} ∧ B_{ij} ) \) )
3). \(A ⊙ B\) : ( \(A\)와 \(B\)의 부울 곱(Boolean Product) ) <=>
결과 행렬 \(C\) 의 행의 수는 \(A\)의 행의 수와 같고 \(C\)의 열의 수는 \(B\)의 열의 수와 같고
\(A\)의 열의 수가 \(B\)의 행의 수와 같습니다. ( \( C_{ij} = \sum_{k=1}^{n}{ A_{ik} ∧ B_{kj} }\) : \(n = A\)의 열의 수 )
( 여기서 \(\sum\) 은 각 원소들을 전부 \(∨\) 한 결과를 도출합니다. 부울 곱은 행렬 곱셈과 유사한 개념입니다. )
1.6. 명제와 추론
“항등관계”는 논리적으로 두 명제가 동치임이 밝혀진 관계입니다.
이 명제들은 어떠한 명제를 간략화 하여 문제 해결을 하기 위해 자주 사용됩니다.
다음의 항등관계들은 자주쓰이곤 하는 관계들을 나열한 것입니다.
1). \(P <=> P ∨ P\) : \(∨\)의 멱등법칙
2). \(P <=> P ∧ P\) : \(∧\)의 멱등법칙
3). \(( P ∨ Q ) <=> ( Q ∨ P )\) : \(∨\)의 교환법칙
4). \(( P ∧ Q ) <=> ( Q ∧ P )\) : \(∧\)의 교환법칙
5). \([ ( P ∨ Q ) ∨ R ] <=> [ P ∨ ( Q ∨ R ) ]\) : \(∨\)의 결합법칙
6). \([ ( P ∧ Q ) ∧ R ] <=> [ P ∧ ( Q ∧ R ) ]\) : \(∧\)의 결합법칙
7). \(¬ ( P ∨ Q ) <=> ( ¬ P ∧ ¬ Q )\) : 드 모르간 법칙
8). \(¬ ( P ∧ Q ) <=> ( ¬ P ∨ ¬ Q )\) : 드 모르간 법칙
9). \([ P ∧ ( Q ∨ R ) ] <=> [ ( P ∧ Q ) ∨ ( P ∧ R ) ]\) : \(∧\)의 분배법칙
10). \([ P ∨ ( Q ∧ R ) ] <=> [ ( P ∨ Q ) ∧ ( P ∨ R ) ]\) : \(∨\)의 분배법칙
11). \(( P ∨ T ) = T\) : 항등법칙
12). \(( P ∧ T ) = P\) : 항등법칙
13). \(( P ∨ F ) = P\) : 항등법칙
14). \(( P ∧ F ) = F\) : 항등법칙
15). \(( P ∨ ¬ P ) = T\) : 여 법칙
16). \(( P ∧ ¬ P ) = F\) : 여 법칙
17). \(P <=> ¬ ( ¬ P )\) : 이중 부정
18). \([ ( P ∧ Q ) → R ] <=> [ P → ( Q → R ) ]\) : 수출
19). \([ ( P → Q ) ∧ ( P → ¬ Q ) ] <=> ¬ P\) : 모순
20). \(( P → Q ) <=> ( ¬ Q → ¬ P )\) : 대우
“술어”(Predicate)는 어떠한 것의 성질이나 둘 사이의 관계를 표현하는 것을 말합니다.
술어는 매개변수들의 관계함수로 \(P\)( 변수들 ) 꼴로 변환 가능하고 이는 명제가 아닙니다.
그렇다면 명제가 되려면 어떻게 해야할까요?
명제가 되려면 “한정자”를 지정하여 반드시 참과 거짓으로 분별되도록 해야 합니다.
( 비슷한 느낌으로 자명한 해가 반드시 나오도록 구간을 정하는 방정식 처럼
반드시 참과 거짓으로만 구별되도록 변환 해야 합니다. )
한정자의 종류는 해석학에 설명 되어있으므로 여기서는 언급하지 않겠습니다.
“논리적 추론”(Logical Inference)은 어떤 참인 명제를 사용하여 다른 어떤 명제를
참과 거짓을 구별하는 것을 말합니다.
이 때, 사용된 참인 명제를 가정( 또는 전제, Hypothesis, Promise)이라고 표현하고,
구별되는 다른 명제를 결론(Conclusion)이라고 표현합니다.
다음은 항진명제의 형태를 이용하여 추론하는 법칙들과 이름들을 나열한 것입니다.
1). \(P => (P ∨ Q)\) : “선언적 부가”(Disjunctive Addition)
2). \(( P ∧ Q ) => P\) : “단순화”(Simplication)
3). \([ P ∧ ( P → Q ) ] => Q\) : “전건 긍정”(Modus Ponens)
4). \([ ¬ Q ∧ ( P → Q ) ] => ¬ P\) : “후건 부정”(Modus Tollen)
5). \([ ( P ∨ Q ) ∧ ¬ P ] => Q\) : “선언 삼단 논법”(Disjunctive Syllogism)
6). \([ ( P → Q ) ∧ ( Q → R ) ] => ( P → R )\) : “가언 삼단 논법”(Hypothetical Syllogism)
7). \([ ( P → Q ) ∧ ( R → S ) ∧ ( P ∨ R ) ] => ( Q ∨ S )\) : “구성적 양도 논법”(Constructive Dilemma)
8). \([ ( P → Q ) ∧ ( R → S ) ∧ ( ¬ Q ∨ ¬ S ) ] => ( ¬ P ∨ ¬ R )\) : “파괴적 양도 논법”(Destructive Dilemma)
1.7. 증명법
가정에서 논리적 법칙을 이용해서 결론을 이끌어내는 것을 “증명”(Proof)이라고 표현합니다.
이 때, 추론이 참이면, “진위(Valid)추론”이라고 표현하고, 추론이 거짓이면, “허위(Fallacious)추론”이라고 표현합니다.
다음은 증명방법들을 나열 한 것입니다.
1). Vacuous 증명법 : \(P → Q\) 에서 \(P\)가 거짓이면 명제는 항상 참임을 이용한 증명법입니다.
2). trivial 증명법 : \(P → Q\) 에서 \(Q\)가 참이면 명제는 항상 참임을 이용한 증명법입니다.
3). 직접( Direct Proof ) 증명법 : \(P → Q\) 에서 P를 참이라 하고 \(Q\)가 참임을 직접 증명하는 방법입니다.
4). 간접( Indirect Proof ) 증명법 : 직접 증명이나 다른 증명을 하기에 어려운 경우
간접적으로 접근하기 쉬운 방법을 사용하기도 합니다.
_1. 대우 증명법 : \(( P → Q ) <=> ( ¬ Q → ¬ P )\) 이므로 대우가 증명하기 쉽다면 사용하는 방법입니다.
_2. 배리법 : \(P\) 가 참임을 보이기 위해 \(¬ P\) 가 거짓임을 보여서 증명하는 방법입니다.
_3. 존재 증명법 : 명제가 어떠한 변수의 존재성에 관한 내용일 때,
그 변수의 조건에 맞는 해를 찾아 증명하는 방법입니다.
5). 반증을 이용한 방법 : 명제의 전체 또는 일부 논리적인 오류가 있는지 확인하여
오류가 있는 부분을 찾아내면 거짓 임을 이용하여 증명하는 방법입니다.
_1. 반례(Counter Example)에 의한 반증 방법 : 명제가 특정 조건 내 모든 가능성에 대해 결론을 정의할 때,
특정 조건 내 일부 가능성 중에서 정의한 결론과 맞지 않는 부분을 찾아 거짓임을 증명하는 방법입니다.
_2. 모순(Contradiction)에 의한 반증 방법 : 명제를 참이라 가정한 후 명제로부터 논리를 확장하다가
확장된 논리들과 모순되는 논리를 찾아서 거짓임을 증명하는 방법입니다.
6). 수학적 귀납법: 수학적 귀납법은 해석학 1.3절에 정렬원칙과 함께 자세하게 정의 되어 있습니다.
간단하게 어떤 논리( 수열 )가 모두 “기저조건”과 “귀납과정”으로 표현 가능한 경우일 때,
기저조건 과 귀납가정이 둘 다 참이라면, 해당논리는 반드시 참이 됨을 이용한 방법입니다.