이산수학 1-7주차

메가존아이티평생교육원 이산수학 참고

---

이산수학 개념과 응용 분야

• 이산수학
  • 디지털 컴퓨터가 데이터를 처리하는 과정에 필요한 수학적 개념
  • 명제, 논리의 참과 거짓, 집합의 포함 및 관계의 유무, 함수의 입출력 등 애매함 없이 확실히 결정되는 개념을 다룸
• 어디에 응용될까?
  • 예) 행렬, 관계 → 2/3차원 그래픽, 머신러닝, 관계형 데이터베이스
  • 예) 부울 대수 → 디지털 회로 설계
  • 예) 그래프, 트리 → 통신 네트워크, 라우팅 알고리즘, 탐색

명제

• 명제 proposition
  • 참, 거짓을 명확히 구분할 수 있는 문장이나 수식
  • 의문문, 감탄문, 명령문은 명제가 될 수 없음
• 종류
  • 단순명제
    • 더 이상 나눌 수 없는 단위의 명제
    • 예) 5는 3과 같다.
  • 합성명제 = 복합명제 = 겹명제
    • 하나 이상의 단순명제가 연산에 의해 결합되어 만들어진 명제
    • 예) 조지 워싱턴은 미국인인고, 도쿄는 영국의 수도이다.
    • 항진명제: 명제를 구성하는 명제의 진리값에 상관없이 합성명제의 진리값이 항상 참인 명제
    • 모순명제: 명제를 구성하는 명제의 진리값에 상관없이 합성명제의 진리값이 항상 거짓인 명제
  • 논리연산자
    • 논리합: '또는'으로 연결, p ∧ q
    • 논리곱: '그리고'로 연결, p ∨ q
    • 부정: '반대'로, ~p
    • 조건명제: p이면 q이다, p → q == ~p ∨ q
    • 쌍조건명제 == p → q ∧ q → p

조건명제

 

논리

• 명제논리
  • 명제의 참과 거짓에만 관심을 가지므로, 명제를 구성하는 요소를 이용해 새로운 사실을 추론하긴 어려움
• 술어논리
  • 명제를 주어와 술어로 분리하여, "술어(주어)"의 형태로 표현하고, 다양한 새로운 사실을 추론함
  • 술어는 유한개의 변수를 가진 문장
    • 예) 호랑이는 동물이다. → 동물이다(호랑이) → 동물이다(변수 x)
• 명제함수
  • 변수 값에 의해 함수의 진리값이 결정되는 문장이나 식
    • 변수 값에 따라 진리값이 바뀌므로 명제라 할 수 없음!
  • 명제함수를 명제로 만드는 방법
    • 구체적인 값을 할당한다면
      • 예) 동물이다(기린)
    • 한정자를 사용한다면
      • 한정자 quantifier
        • some 또는 all과 같은 양을 취급하는 단어
      • 예) 사람 x는 죽는다(all x)

추론

• 추론 inference
  • 참이라고 알려져 있는 사실로부터 논리적인 과정을 거쳐 참인 사실을 이끌어내는 과정
    • 전제 premise: 이미 알려진 명제
    • 결론 conclusion: 새로 유도된 명제
  • 유효추론: 정당한 근거에 따른 추론
• 추론 규칙 inference rule
  • 기본적인 추론 규칙은 논리적 동치를 이용하는 것 - 논리적으로 동치인 문장은 여러 번 대치해도 영향을 주지 않는다는 점을 활용
  • 선언적 부가 disjunctive addition
    • p가 참이면, p or q도 참이다.
  • 단순화 simplication
    • p and q가 참이면, p는 참이다.
  • 긍정논법 modus ponens
    • p가 참이고 p → q가 참이면, q는 참이다.
  • 부정논법 modus tollens
    • ~q가 참이고 p → q가 참이면, ~p는 참이다.
  • 선언적 삼단논법 또는 소거 disjunctive syllogism
    • p or q가 참이고 ~p가 참이면, q는 참이다.
  • 가설적 삼단논법 또는 추이 hypothetical syllogism
    • p → q가 참이고 q → r이 참이면, p → r은 참이다.

증명

• 공리 axiom
  • 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정, 별도의 증명 없이 참으로 판단
  • 예) 유클리드 기하학 - 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그릴 수 있다.
• 증명 proof
  • 제안된 명제가 참임을 입증하는 작업
  • 방법
    • 수학적 귀납법
      • 기본단계, 귀납가정, 귀납단계를 이용 
      • 자연수 n에 대한 명제를 증명하는 데에 유용: 명제가 n = 1일때 참임을 증명하고, n = k일 때 참이면 n = k + 1일 때도 참임을 증명하는
    • 직접 증명법 direct proof
      • 공리, 정의, 정리를 논리적으로 직접 연결
      • = 연역법 deduction: 이미 증명된 명제를 활용해 다른 명제를 증명해내는
    • 간접 증명법 indirect proof
      • 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명
      • 대우증명법: 증명하고자 하는 명제의 대우명제를 이용
      • 모순증명법: 주어진 명제를 부정한 뒤, 그 식을 전개할 때 결론이 모순임을 보여 명제가 참임을 증명
      • 반례증명법: 전체한정자가 사용되었을 때, 해당 명제가 거짓임을 증명하기 위해 반례를 찾음
      • 존재증명법: 존재한정자가 사용되었을 때, 해당 명제가 참임을 증명하기 위해 예를 찾음
      • 전수증명법: 명제로부터 유도될 수 있는 경우의 수가 적을 때, 모든 경우의 수를 조사
      • 조합적 증명법: 두 집합의 원소 개수가 동일함을 증명해야 한다면,
        • 전단 증명:
          • 원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 일대일 관계임을 보여 n = m임을 증명
          • 예) 한 반의 학생 수와 의자의 수가 같다는 것을 증명하기 위해, 모든 학생이 하나의 의자에 앉고, 비어 있는 의자가 없다는 것을 보여주는 것. 즉, 모든 학생(A)에게 의자(B)가 하나씩 짝지어진다는 것을 증명함으로써 A와 B의 개수가 같음을 보임.
        • 중복 산정
          • 하나의 집합의 원소를 세는 두 가지 다른 방법을 제시하고, 두 방법으로 얻은 결과가 동일하다는 것을 보여 증명
      • 컴퓨터 이용 증명법: 증명과정 중에 컴퓨터를 이용한 계산을 포함
• 정리 theorem
  • 논리적으로 증명된 결론
  • 보조정리 lemma: 정리를 증명하는 과정 중에 사용되는 증명된 명제
  • 따름정리 corollary: 정리로부터 쉽게 도출되는 부가적인 명제

집합

• 집합 set
  • 주어진 명확한 조건에 의해 공통된 특징을 갖는 원소들의 모임
  • 순서는 고려하지 않고, 중복은 없음
  • 표현방법
    • 원소나열법
      • 집합을 구성하는 모든 원소들을 하나씩 나열하는 방법
      • 예) A = {1, 2, 3, 4, 5}
    • 조건제시법
      • 집합을 구성하는 원소들의 공통적인 특징을 조건으로 제시하는 방법
      • 예) A = {x | 0 < x < 5, x는 정수}
  • 종류
    • 유한집합 finite set: 원소 개수가 유한한 경우
    • 무한집합 infinite set: 원소 개수가 무한한 경우
    • 공집합: 원소를 하나도 갖지 않는 경우
  • 연산: 합집합, 교집합, 차집합, 여집합
  • 집합의 대수법칙: 항등법칙, 지배법칙, 멱등법칙, 교환법칙, 결합법칙, 분배법칙, 드모르간의 법칙, 흡수법칙
    • 드모르간의 법칙: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
    • 흡수법칙: A ∪ (A ∩ B) = A
• 카디널리티 cardinality
  • 원소의 개수
  • 예) 집합 A의 원소 개수는 |A|와 같이 나타냄
• 서로소 disjoint: 두 집합의 교집합에 원소가 없는 경우
• 분할 partition: 집합을 겹치지 않게 분할한 부분집합들의 집합
• 멱집합 power set
  • 임의의 집합에서 발생할 수 있는 모든 부분집합들을 원소로 갖는 집합
  • 예) A = {a, b} 이면 P(A) = {0, {a}, {b}. {a, b}}
• 곱집합 cartesian product
  • A와 B의 곱집합을 구한다면? A의 원소와 B의 원소의 모든 순서쌍들의 집합

행렬

• 행렬 matrix
  • 행과 열로 수를 배열한 것
  • 행 벡터 row vector = 1 x n 행렬
  • 열 벡터 column vector = m x 1 행렬
  • 영 행렬 zero metrix = 모든 원소가 0인 행렬
  • 정방행렬 square matrix = 행의 수와 열의 수가 같은 행렬
    • 정방행렬의 대각선에 있는 원소들을 대각원소라고 함
  • 단위행렬 unit matrix = 대각원소가 모두 1이고 나머지 원소는 모두 0인 정방행렬
  • 대각행렬 diagonal matrix = 대각원소 이외의 모든 원소가 0인 정방행렬
  • 대칭행렬 symmetric matrix = $a_{ij} = a{ji}$인 행렬
  • 교대행렬 skew matrix = $a_{ij} = - a_{ji}$이고 대각원소가 모두 0인 행렬
  • 삼각행렬 triangle matrix
    • 상삼각행렬 = 주대각선 아래에 있는 모든 원소들이 0인 행렬
    • 하삼각행렬 = 주대각선 위에 있는 모든 원소들이 0인 행렬
  • 전치행렬 transpose matrix = 행과 열을 서로 교환한 행렬
• 행렬의 연산
  • 행렬의 합, 차는 같은 위치에 있는 원소끼리 - 따라서 두 행렬의 크기가 같아야 함!
  • 행렬에 대한 스칼라 곱은 각 위치에 있는 원소에 대해
  • 행렬의 곱은 A의 행 * B의 열 = C의 한 원소
    • 교환법칙이 성립하지 않음을 주의하자!
  • 가우스 소거법은 일차연립방정식의 풀이에 행렬을 활용할 때 사용
    • 일차연립방정식을 AX = B의 형태로 표현한다면
      • A는 계수행렬
      • X는 미지수 행렬 또는 해
      • B는 상수행렬
      • (A|B)는 확장행렬
    • 일차연립방정식의 해를 구하기 위해 행 대체 연산
      • 두 개의 식을 더해서 새로운 식을 만듦
      • 두 식의 위치를 서로 교환
      • 하나의 식에 0이 아닌 상수를 곱함

• 부울 행렬
  • 두 행렬 A, B가 부울 행렬일때
    • 합 join은 A ∨ B
    • 교차 meet는 A ∧ B
    • 부울 곱 boolean product는 A ⊙ B
      • 합과 교차는 같은 위치에 있는 원소끼리 했다면, 부울 곱은 행렬 곱처럼 연산하되, 부울에 대해서

관계

• 관계: 서로 다른 집합에 있는 원소들 사이의 관련성
• 이항관계 binary relation

• 예) A = {1, 2, 3, 4}, B = {1, 3, 5, 7}에 대한 이항관계 R을 a + 2 = b라고 할 때 R을 순서쌍으로 나타낸다면?
  R = {(1, 3), (3, 5)}
  • 집합 A에서 B로 가는 어떤 이항관계 R이 있다고 할 때
    • 집합 A는 정의역 domain: dom(R)
    • 집합 B는 공변역 codomain: codom(R)
    • 실제로 대응되는 집합 B의 부분집합은 치역 range: ran(R)
• 관계가 아래 성질을 가질 수도?

• 역관계
  • R에서 순서쌍의 순서를 바꾸는 것이기 때문에, 관계 R이 존재할 때에만 그의 역관계를 만들 수 있음
  • 정의역이 치역이 되고, 치역이 정의역이 되는!
• 합성관계 composition relation
  • R1이 A에서 B로의 관계이고, R2가 B에서 C로의 관계일 때, R2 * R1는 A에서 C로의 관계
  • 표현 순서를 주의하자!
• 반순서 partial ordering
  • 관계가 반사성, 반대칭성, 추이성을 갖는 경우

• 동치관계 equivalence relation
  • 관계가 반사성, 대칭성, 추이성을 갖는 경우

함수

• 함수
  • 한 집합의 원소가 다른 집합의 원소에 각각 한번씩만 대응하는 관계
  • 정의역의 한 원소가 공변역의 한 원소로 대응되지 않았거나, 정의역의 한 원소가 공변역의 둘 이상의 원소로 대응되었다면, 함수라고 할 수 없음!
• 정의역과 공변역의 대응 관계에 따라
  • 단사 함수 injective function: 일대일 대응
  • 전사 함수 surjective function: 치역과 공변역이 같음
  • 전단사 함수 bijective function: 단사 함수이면서 전사 함수
• 함수의 상등: 정의역과 공변역이 같고, 정의역의 모든 원소 x에 대하여 f(x) = g(x)의 값이 같을 때 두 함수 f와 g는 '상등하다'고 함
• 주요 함수
  • 상수 함수: 정의역의 값에 관계 없이 항상 동일한 값이 나오는 함수
  • 항등 함수: 어떠한 값을 입력하든 그대로의 값이 나오는 함수
  • 역함수 inverse function
  • 합성 함수: 두 개 이상의 함수를 합성하여 만든 함수
    • 교환법칙은 성립하지 않으나, 결합법칙은 성립함
  • 계승함수 factorial
  • 나머지 함수 mod
  • 바닥함수 floor function = greatest integer function
  • 천장함수 ceiling function = least integer function

부울대수

• 디지털 논리 회로
  • 입력 신호로 논리 연산을 수행하여 출력 신호를 생성시키는 전자적 회로
  • 기본 논리 게이트: AND, OR, NOT
  • 기타 게이트: NAND, NOR, XOR, XNOR

• 반가산기 half adder / 전가산기 full adder
  • 반가산기는 2개의 입력(X, Y)만을 받고, 전가산기는 3개의 입력(X, Y, 이전 자리에서 넘어온 C)를 받음
  • S sum = X와 Y를 더한 값
  • C carry = X와 Y를 더하는 과정에서 자리올림이 발생한다면 1, 발생하지 않는다면 0

왼쪽이 반가산기, 오른쪽이 전가산기

• 부울대수 boole
  • 복잡한 논리회로를 간단하게 표현하는 데에 유용한 논리대수
    • 논리회로를 직접 간소화하는 것은 어렵기 때문에 → 논리 회로를 논리식으로 표현한 후, 부울대수의 기본 규칙을 활용해 간소화
    • 방법
      • 아래 방법들을 구분해서 외울 필요는 전혀 없음! 다만 간소화할 때 적절히 잘 활용할 수 있으면 됨
      • 항결합: 두개의 항을 결합하여 하나의 항으로 만드는 방법
      • 문자 소거: 중복된 문자를 제거하는 방법
      • 중복항 첨가: 주어진 함수식의 의미가 변하지 않도록 하면서 간소화를 위해 적절한 항을 함수식에 첨가시키는 방법
      • 합의 정리를 활용하는 방법
      • 카르노맵 karnaugh map: 부울변수에 대한 최소항들을 도표로 그려서 인접한 항들을 서로 묶은 후 최소화하는 방법
        • 정규합형 disjunctive normal form
          • 변수의 곱을 합한 형태
          • 예) F = xy + x'y 이라면 xy, x'y는 minterm
        • 정규곱형 conjunctive normal form
          • 변수의 합을 곱한 형태
          • 예) F = (x+y)(x'+y) 이라면 x+y, x'+y는 maxterm
        • 카르노맵 활용 방법

• 부울대수의 변수는 0과 1 중 한 값을 가짐
  • 부울함수: 부울대수와 기본연산을 활용
  • 부울보수: 2진 변수의 값을 반전시키는 단항 연산자

그래프

• 그래프는 비선형 자료구조
  • 각 정점들이 순서에 따라 이어지기 보다는 필요에 따라서 첫번째 정점과 마지막 정점이 연결될 수도 있는 형태이기에
• 그래프 이론은 오일러가 쾨니히스베르크 다리 문제 해결에 최초로 사용
  • 정점의 차수가 짝수일 때 해결 가능함을 보임
• 그래프는 정점들의 집합 V와 간선들의 집합 E로 구성됨
  • 연결된 두 정점은 서로 인접 adjacent 한다고 함
  • 어떠한 간선으로도 연결되지 않은 정점은 고립 isolated 되었다고 함
• 방향 directed / 무방향 undirected 그래프
  • 일반적으로 ‘그래프’는 무방향 그래프를 의미함
  • 무방향 그래프: G = (V, E)
  • 방향 그래프: G = <V, E>
    • 예) G = <V, E>
      • E = {<a, a>, <a, b>, <b, c>}
      • V = {a, b, c}
    • 간선 v가 임의의 두 정점 순서쌍 <a, b>로 연결되었다고 한다면
      • a는 간선 v의 출발점 initial vertex
      • b는 간선 v의 도착점 terminal vertex
• 차수 degree
  • 정점에 연결된 간선의 개수
    • 홀수점 odd vertex: 차수가 홀수인 정점
    • 짝수점 even vertex: 차수가 짝수인 정점
  • 무방향 그래프에서
    • 모든 정점의 차수의 총합은 모든 간선의 개수의 2배!
    • (a, a) 간선이 있다고 했을 때 a의 차수는 2
  • 방향 그래프에서
    • 외부 차수 outdegree: 정점을 출발점으로 갖는 간선의 개수
    • 내부 차수 indegree; 정점을 도착점을 갖는 간선의 개수
    • 총 차수 = 외부 + 내부

• 부분 그래프 subgraph
  • 어떤 그래프 G를 구성하는 일부 정점과 간선으로만 구성된 그래프
  • G’ ≤ G
    • V’ ≤ V and E’ ≤ E
  • 부분신장 그래프 spanning graph
    • 부분 그래프 중에서 그래프 G의 정점을 모두 포함한 부분 그래프
    • G’ ≤ G
      • V’ = V and E’ ≤ E

• 경로 path
  • 두 정점을 연결하는 간선들을 나열한 것
    • 정점만 표시되어 있고 간선들에 이름이 부여되어 있지 않은 경우, 정점들을 나열하여 경로를 나타내기도 함
  • 같은 간선은 두 번 이상 지나갈 수 없음
  • 단순 경로 simple path: 경로의 정점들이 모두 다른 경우

• 그래프의 종류
  • 사이클 cycle
    • 해당 경로의 시작 정점과 끝 정점이 같음
    • 단순 사이클: 시작 정점과 끝 정점을 제외한 모든 정점이 다름
  • 연결 그래프 connected graph
    • 모든 정점들 사이에 경로가 존재함
      • 어떤 두 정점에 인접하는 간선이 존재하지 않더라도, 다른 정점들과 간선들을 통해 두 정점이 연결되면 두 정점 간의 경로가 존재하는 것으로 봄
  • 완전 그래프: 모든 정점들 사이에 간선이 존재하는 그래프

• 그래프의 표현
  • 컴퓨터에서 그래프를 표현하기 위해서는 인접 행렬과 인접 리스트를 사용
  • 인접 행렬 adjacency matrics
    • 두 정점을 연결하는 간선이 존재하면 행렬의 원소는 1, 존재하지 않으면 행렬의 원소는 0
      • 행에서 열로 가는 간선으로 따져볼 것!
    • 무방향 그래프를 인접 행렬로 표현하면 주대각선을 중심으로 대칭적
  • 인접 리스트 adjacency lists
    • 각 정점들에 인접하는 정점들을 연결 리스트로 표현한 것
    • 연결 리스트 linked list
      • 각 노드는 2개의 필드로 구성됨
      • 첫 번째 필드는 데이터 필드 (정점 필드), 두 번째 필드는 포인터 필드 (다음 노드의 주소)
      • 마지막 노드는 포인터 필드에 null