Namu | 나무 개발자 블로그입니다

[방통대] 이산수학 수업 정리 by namu

Created at
| 2021-04-24 20:06
Updated at
| 2021-04-24 20:06
discrete mathematics image
image by openuped

목차

  1. 이산수학의 개요
  2. 논리
  3. 증명
  4. 집합론

참조


들어가며

다음은 2021학년도 1학기 이산수학 수업에 대한 정리입니다.

오리엔테이션

이산수학의 개요

이산수학 학습 목표

주요용어


1. 이산수학의 개요

1.1 수학의 분류와 이해

[수학적 분류] 수학에는 대수학, 해석학, 기하학이 있습니다.

미지수에 대한 방정식을 만들어 푸는 것을 대수학, 수열이나 급수, 수열의 극한 그리고 미분화 적분에 대한 것을 해석학, 어떤 점으로부터 일정한 거리에 있는 점들의 집합에 대한 것을 기하학이라고 이해하면 됩니다.

수학을 다른 방식으로 분류할 수도 있습니다.

[컴퓨터적 분류] 바로 연속된 수를 다루는지, 단절된 수를 다루는지에 따른 것이 그 기준입니다.

연속된 수를 다루는 것을 연속수학, 분절적인 수를 다루는 것을 이산수학이라고 이해합니다.

1.2 문제해결

문제를 해결하기 위해서는 도구, 기법, 방법론이 필요합니다.

수학에서의 도구는 정의나 정리, 기법은 일차연립 방정식, 2차, 3차 방정식과 같은 것들을 의미합니다. 방법론은 정의와 기법을 언제 어디에 어떻게 사용할 것인지에 대한 것을 다룹니다. 즉, 가장 효율적인 도구와 기법을 적재적소에 선택하는 것이죠.

문제해결의 과정

기본적으로 추상화(abstraction) 또는 모델링의 단계를 거칩니다.

추상화에 익숙하고 잘할수록 문제해결 능력이 높다고 볼 수 있습니다.

추상화? (抽象化, abstraction)

정의1. 일정한 인식 목표를 추구하기 위하여 여러 가지 표상이나 개념에서 특정한 특성이나 속성을 빼냄.

정의2. 문제와 관련된 핵심내용만 남기고 관련 없는 내용을 제거하여 문제를 단순화시키는 과정.

사과를 예로 들어봅시다. 분명 지구상에는 다양한 형태와 색과 맛을 가지는 ‘사과’가 존재할 것입니다. 우리는 그 모든 것들을 통칭해 ‘사과’라고 명명합니다. 그것은 사과에 해당되는 특성이나 속성을 가지고 있기 때문이며, 우리는 ‘사과’라는 추상화 과정을 통해 그것을 인식할 수 있습니다.

이것은 사과란 무엇인가에 대한 문제 해결 과정입니다.

그렇다면 컴퓨터에 대해서는 어떨까요?

컴퓨터의 특성을 추상화 하자면, 그것은 입력장치와 기억장치, 처리장치와 제어장치, 그리고 출력장치를 가지고 있는 것입니다. 따라서 이 다섯 가지 기본 특성을 지니는 있는 모든 기기는 컴퓨터라고 추상화할 수 있습니다.

디지털 논리 회로를 간소화한 그림을 한번 봅시다. (제 8강. 부울대수, 그림 1-4) digital logic circuit01

추상화의 과정을 통해 복잡해 보이는 디지털 논리회로를 간소화된 그림으로 표현하였습니다. AND, OR, NOT 등의 연산을 약속된 기로호 표현해 알아보기가 쉽습니다.

이번에는 도출된 논리식을 더 간소화해 봅시다.

F(X, Y) = X + XY + notXY
        = X(1 + y) + notXY  ∵ 분배법칙
        = X + notXY         ∵ 1 + Y = 1
        = (X + notX)(X + Y) ∵ 분배법칙
        = X + Y             ∵ X + notX = 1

위와 같이 디지털 논리회로를 수학적으로 간소화하여 비교한다면, 더 효율적인(간소화하여 논리연산 1번이면 해결) 회로를 선택할 수 있을 것입니다.(문제의 해결)

1.3 알고리즘 언어

알고리즘(algorithm)이란, 어떠한 문제(task)를 해결하기 위한 여러 step by step 동작들의 유한한 모임 으로 정의할 수 있습니다.

1.3.1 알고리즘의 표현 방법에는 프로그래밍 언어, 플로우 챠트, 수도코드가 있습니다.

프로그래밍 언어는 잘 알다시피 알고리즘을 상세하게 표현하지만, 통일된 언어가 존재하지 않습니다. 순서도는 약속된 기호로 가장 추상적으로 알고리즘을 도식화하여 흐름에 따라 기술하기에 이해하기 쉽지만, 내용이 복잡하거나 커지면 표현이 어렵습니다. 수도코드 더 발전적이고 추상적인 표현 방식으로, 모호한 부분은 프로그래밍 언어를 차용(C언어 기반)하여 명료하게 하고, 구체적이지 않아도 되는 부분은 자연어로 설명식으로 기술합니다. 추상화하여 이해하기에 가장 좋지만, 알고리즘을 설명하는 용도로면 사용하게 됩니다. 의사코드는 할당문과 제어문을 활용해 표현합니다.

세상의 모든 문제 중 순서성Sequence, 선택성Selection, 반복성Iteration을 가지는 것은 알고리즘으로 표현할 수 있습니다. 즉, 컴퓨터 프로그래밍 언어로 구현할 수 있다는 것입니다. 이 세 가지 특성은 의사코드에서 제어문에 속하게 됩니다.

1.3.2 기본 제어구조는 다음과 같습니다.

if 문을 사용한 의사코드 예는 다음과 같습니다. (제 1강. 이산수학의 개요, 예제 1.3) psudo01

순차, 선택, 반복구조가 포함된 수도코드의 예시를 더 찾아봅시다.

1.4 이산수학의 응용분야

이산수학의 응용분야는 다음과 같습니다. 기본적으로 각각의 문제해결을 위한 고민의 결과이며, 예외적인 상황을 하나라도 더 찾아내는 논리성이 중요합니다.

grounds of discrete mathematics


2. 논리

이번 강의의 학습 목표는 다음과 같습니다.

주요용어: 명제, 논리연산자, 조건명제, 쌍조건명제, 논리적 동치, 술어논리, 전체한정자, 존재한정자, 벤 다이어그램, 추론규칙

2.1 명제

명제 (Proposition)

참과 거짓을 구별할 수 있는 문장이나 수학적 식을 명제라고 합니다. 명제의 진리값은 True T or False F 입니다.

예를 들어, “6은 2의 배수다.”와 같은 진술은 참거짓 판별이 가능하여 명제이지만, “철수는 공부를 잘 한다.”와 같은 추상적 진술은 기준이 불문명하여 참거짓 판별이 불가능해 명제가 아닙니다.

비슷한 맥락으로 “2 더하기 3은 7이다.”는 거짓이긴 하지만 명제입니다.

그렇다면, “x + 2 = 0” 진술은 어떨까요? 이 때는 x 값을 알 수 없어 명제라 할 수 없습니다. 하지만 x 값이 정해지면 참거짓 판별이 가능하므로, 명제함수라고 부릅니다.

명제의 종류는 아래와 같습니다.

2.2 논리연산

이번엔 ‘연산’에 대해 다뤄봅니다. 더하기 빼기 곱하기 나누기 등도 연산의 하나입니다. 컴퓨터에서 연산은 operation, 연산자는 operator 라고 합니다.

그럼 일반적인 연산에서 필요한 요소들을 알아봅시다.

이들을 통해 수식을 도출합니다. > 0.5x + y

그렇다면 논리 연산에서 위의 요소들은 어떻게 대응될까요?

앞서 수식을 도출했듯이 논리 연산의 요소(명제, 연산자)들을 통해 합성명제(논리연산식)를 도출합니다.

합성 명제

하나 이상의 명제와 논리연산자 그리고 괄호로 이루어진 명제

2.2.1 논리 연산자

[진리표01 - or, and]
논리표01 출처: https://thrillfighter.tistory.com/265

[진리표02, not]
논리표02 출처: https://thrillfighter.tistory.com/223

[진리표03, xor, xnor]
논리표03 출처: http://www.ktword.co.kr/abbr_view.php?m_temp1=4420

xnor는 배타적 논리합의 역입니다. > ~(p ⊕ q)

xor example01

함께 보기: [진리표04, nor, nand]
논리표04 출처: https://thrillfighter.tistory.com/265

2.2.2 조건명제

조건 명제 (conditional proposition, →)

명제 p, q가 있을 때 명제 p가 조건의 역할을, q가 결론의 역할을 수행하는 경우

p → q 에서, p는 q의 충분조건, q는 p의 필요조건이라 합니다. 조건명제의 진리표는 다음과 같습니다.

[조건명제 진리표]
조건명제 진리표 출처: https://bite-sized-learning.tistory.com/364

주목할 부분은 조건 p가 거짓인 아래 두 경우입니다. 조건이 F이면 결과가 무엇이든 간에 조건명제 전체는 참(T)로 약속합니다.

조건명제 예제01

쌍조건 명제 (↔)

명제 p, q가 있을 때 명제 p와 q가 조건의 역할과 결론의 역할을 동시에 수행하는 경우

쌍조건 명제에서는 조건명제의 역방향도 가정합니다. 이는 p ↔ q ≡ (p → q) ∧ (q → p) 와 같은 형태로 동치입니다. 쌍조건 명제의 진리표는 다음과 같습니다.

[쌍조건명제 진리표]
쌍조건명제 진리표 출처: https://ziondragon1.tistory.com/category/?page=33

표에서 보다시피 역방향에 대해서도 조건명제의 약속이 성립하여 참거짓이 판별됩니다.(q → p 열 참조)

쌍조건 명제에서는 정방향 조건명제와 역방향 조건명제가 모두 T 이거나 F 이면 결과가 T 입니다.

2.2.3 동치

논리적 동치 (logical equivalence, ≡)

두 명제 p, q가 논리적으로 동등하다.

논리적으로 동등하다는 말은 두 명제가 항상 동일한 진리값을 가진다는 의미입니다. 따라서 두 명제가 동치임을 밝히고자 한다면, 각 명제의 진리표를 작성하여 진리값이 항상 같음을 증명하면 됩니다.

역, 이, 대우는 상호간에 다음과 같은 대응관계를 갖습니다.

[역, 이, 대우 대응표]
역, 이, 대우 대응표 출처: https://swimming79.com/15

동치 예제01 - 드모르간

2.3 술어논리

논리는 명제논리와 술어논리로 나눌 수 있습니다.

명제논리는 앞서 살펴본 것처럼 전체 진술에 대한 참거짓을 판별하는 논리입니다. 명제 자체가 원자성의 띄기 때문에 주어와 술어에 대한 분리를 수행하지 않습니다.

술어논리는 주어와 술어 요소를 분리하여 서술적으로 참거짓을 판별하는 논리입니다. 술어가 수식하는 객체(주부)에 따라 참거짓이 결정되며, 그 형태는 술어(객체)와 같습니다. 여기서는 논리 내부 구조에 대한 분석이 가능합니다.

2.3.1 술어논리와 명제함수

술어논리에는 대표적으로 명제함수가 있습니다. 명제함수는 명제가 아닙니다. (ex. x + 2 = 0)

명제함수 (propositional function)

변수의 값에 의해 함수의 진리값이 결정되는 문장이나 식.

2.3.2 타당성 검사

한정자가 사용된 명제함수의 타당성은 벤 다이어그램을 통해 직관적으로 검사합니다. 예를 들어, “모든 평행사변형은 사각형이다“는 진술의 타당성은 평행사변형의 범주가 사각형의 범주 내에 있음을 확인함으로써 검사합니다.

2.4 추론

추론 (inference)

참으로 알려진 명제를 기초로 하여 다른 명제를 유도해 내는 과정

(1) 이때 결론의 근거를 제공하는 알려진 명제를 전제(premise),
(2) 새로 유도된 명제는 결론(conclusion)이라고 합니다.

추론 예제01


3. 증명


4. 집합론

Written on April 24th, 2021 by namu
Feel free to share!

You may also enjoy: