Per ardua ad astra.

그래프의 활용 네트워크의 데이터 흐름이나 스케줄링, 논리회로 설계, 정렬, 탐색, 인공지능의 지식 정보 생성 과정 등 그리고 실생활에서 많이 접할 수 있는 도로망 설계나 버스 및 지하철 노선 설계 등과 같이 어떤 문제를 해결하기 위한 모델링 과정에서 그래프 이론은 매우 중요하게 쓰인다. 이러한 모델링에서 최단 경로를 구하거나 정보 탐색을 하는 방법이 많이 쓰인다. 최단 경로 문제(Shortest Path Problem) $|E| > 0$ 인 연결 그래프 $G = (V, \; E)$ 에서 정점 $v_{1}, v_{2} \in V$ 간의 가장 짧은 거리의 경로를 찾는 문제 지도의 어떤 지역 A에서 다른 지역 B로 이동하는 경로나, 네트워크의 어떤 호스트 A에서 다른 호스트 B로 이동하는 경로는 다양할 수 있..

오일러와 해밀턴 연결 그래프에는 하나의 정점에서 다른 정점으로 가는 다양한 길이 존재할 수 있는데, 그 중에서 같은 변을 반복적으로 지나지 않는 길이 경로이다. 순환(Cycle) / 회로(Circuit) 연결 그래프에서 시작하는 정점과 끝나는 정점이 같은 경로 길이(Length) 경로 또는 순환을 구성하는 변의 수 한 그래프에 포함되는 임의의 정점에서 다른 정점 혹은 다시 원래의 정점으로 가는 길은 다양하다. 그중 변을 한 번씩만 지나 다른 정점으로 가는 길은 경로이고, 원래의 정점으로 다시 돌아오는 경로는 순환이다. 예 (1) $a - c - d - f$ (2) $a - e - c - d - b - f$ (3) $a - c - e - a$ (4) $a - e - c - a$ (5) $a - c - d ..

그래프의 표현 그래프는 수학적 기호와 그림뿐 만 아니라 그래프를 이용한 연산이나 데이터의 구조를 나타내기 위해 행렬이나 리스트 형태로 표현하기도 한다. 인접 행렬(Adjacency Matrix : $A_{G}$) 그래프 $G = (E, \; A)$ 에서 $|V| = n$ 일 때, $n \times n$ 행렬 $A_{G} = [a_{ij}]$ $$a_{ij} = \begin{cases} \text{해당 정점에 근접하는 변의 수} &, (v_{i},\; v_{j}) \in E \\ 0 & , (v_{i}, \; v_{j}) \not \in E \end{cases}$$ 관계를 행렬로 표현하는 관계 행렬은 관계 집합에 순서쌍 원소가 있는지 없는지를 1과 0으로 표현하는 행렬로, 부울 행렬의 형태이다. 그래프도 ..

그래프의 종류 그래프는 정점과 변이 어떻게 구성되는지에 따라 종류를 구분한다. 부분 그래프와 신장 부분 그래프 부분 그래프(Subgraph) 그래프 $G = (V, \; E)$ 에 대하여, $V' ⊆ V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 $G \ne G'$ 인 그래프 $G' = (V', \; E')$ 신장 부분 그래프(Spanning Subgraph) 그래프 $G = (V, \; E)$ 에 대하여, $V' = V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 그래프 $G' = (V', \; E')$ 부분 그래프 `G'` 은 어떤 그래프 `G` 에 포함된 정점과 변의 일부 또는 전체로 구성된 그래프이다. 부분 그래프 `G'` 을 구성하는 정점의 집합과 변의 집합은 각각 그래프 `G` 의 정..

그래프의 개념 점과 선을 이용해 개념, 구조 또는 과정 등을 이해하는 데 필요한 주요 요소 간의 관계, 거리, 비용 등을 시각적으로 표현한 도구를 그래프(Graph)라고 한다. 그래프는 글이나 수식으로는 복잡하고 어렵게 표현되는 것을 그림으로 표현하기 때문에 컴퓨터 시스템의 회로나 네트워크 설계나 구조, 프로그램의 알고리즘, 인공지능의 지식 정보의 파생 과정 및 내용 등을 표현하는 데 효율적이고 효과적으로 활용된다. 그래프는 정점과 변으로 표현되기 때문에 정점에 대한 정보와 변에 대한 정보를 정의함으로써 그래프를 정의하고 표현한다. 그래프는 보통 그림 형태로 표현하지만, 집합 표현과 같은 수학적 기호로 표현할 수도 있다. 그래프의 정의와 표현 그래프(Graph : $G = (V, \; E)$ ) 공집합이..

함수의 종류 항등 함수(Identity Function : $I_{A}$ ) 집합 `A` 에 대한 함수 $f : A \rightarrow A$ 가 $f(a) = a$ 로 정의되는 관계 항등 함수가 성립하려면 함수의 정의역, 공역, 치역 집합이 모두 상등이어야 한다. 항등 함수는 정의역의 원소 $x_{1}, x_{2}$ 가 $x_{1} \ne x_{2}$ 일 때 $f(x_{1}) = x_{1} \ne x_{2} = f(x_{2})$ 이므로 단사 함수이고, 모든 공역의 원소 `y` 에 대하여 `f(x) = y` 를 만족하는 정의역 원소 `x` 를 가지므로 전사 함수이다. 따라서 항등 함수는 전단사 함수이다. 예 집합 $A = \{-1, 0, 1 \}$ 에 대한 함수 $f_{1}(x) = x$ 와 $f_{2}..

합성 함수 합성 함수의 정의 삼각 함수 공식 중 $\sin (α + β)$ 와 같은 식이 있다. 이 식은 다음과 같이 두 함수 `f(x)` 와 `g(x, y)` 를 합성한 결과이다. $$f(x) = sin(x), \; g(x, y) = x + y \quad \Rightarrow \quad sin(α + β) = f(g(α, β))$$ 이처럼 최초 입력을 이용해 2개 이상의 함수를 차례로 연산하여 최종 출력을 내어 입력과 출력을 대응하는 함수를 합성 함수라고 한다. 합성 함수(Composite Function : $g \circ f$ ) 두 함수 $f : A \rightarrow B$ 와 $g : B \rightarrow C$ 가 있을 때, 집합 `A` 의 각 원소를 집합 `C` 의 원소에 대응하는 함수 ..

함수의 성질 함수의 입력과 출력의 대응 형태에 따라 함수의 성질이 결정된다. 함수의 성질을 알면 정의역과 공역의 관계뿐만 아니라 공역과 치역 간의 포함 관계도 알 수 있다. 이는 컴퓨터 및 인공지능 시스템에서 자료의 활용을 계획하는 데 좋은 정보가 된다. 함수는 정의역과 공역의 대응 관계에 따라서 단사 함수, 전사 함수, 전단사 함수로 구분한다. 단사 함수(Injective Function, Injection, One-to-One Function) = 일대일 함수 함수 $f \; : \; X \rightarrow Y$ 가 있을 때, 임의의 두 정의역 원소 $x_{1}, \; x_{2} \; \in \; X$ 에 대하여 $x_{1} \ne x_{2}$ 이면 $f(x_{1}) \ne f(x_{2})$ 인 함..

함수의 개념 관계(Relation)는 두 집합의 원소들 사이의 대응을 정의한 것이다. 함수는 입력과 출력이 일대일로 대응하는 관계의 한 형태이다. 함수(Function : $f \; : \; A \rightarrow B$) 집합 `A` 에서 집합 `B` 로 가는 관계가 성립할 때, 집합 `A` 의 임의의 원소 `a` 에 대하여 집합 `B` 의 원소 `b` 하나가 대응되는 관계 함수 용어 정리 : 원상(Preimage), 상(Image), 정의역(Domain), 공역(Codomain), 치역(Range) 집합 `A` 에서 집합 `B` 로 가는 함수 $f \; : \; A \rightarrow B$ 에 대하여, ① 원상(Preimage) : 집합 `B` 의 원소 `b` 와 대응하는 집합 `A` 의 원소 `a..

동치 관계와 부분 순서 관계 관계 `R` 이 어떤 성질을 갖느냐에 따라 관계에 의미를 부여하여 그 의미에 따라 관계의 순서쌍을 구성하는 원소들을 활용할 수 있다. 관계에 부여되는 의미에는 동치 관계나 부분 순서 관계가 있는데, 동치 관계의 경우 그 관계의 순서쌍을 구성하는 원소들이 같은 의미라는 것을 뜻하며, 부분 순서 관계의 경우는 그 관계의 순서쌍을 구성하는 원소들 사이에 순서가 존재한다는 것을 뜻한다. 동치 관계(Equivalence Relation) 반사 관계, 대칭 관계, 추이 관계가 모두 성립하는 관계 동치는 표현이 달라도 의미가 같아서 동등하게 사용할 수 있음을 의미한다. 예) 10진수 $7_{10}$ 과 2진수 $111_{2}$ 이 표현은 다르지만 같은 값으로 사용되므로 동치라고 할 수 있..

관계의 폐포 학번을 입력하면 학생의 이름을 비롯한 학생의 기타 정보를 검색할 수 있는 시스템이 있다고 하자. 하지만, 이 시스템은 등록된 전체 학생 중 재학생만 검색할 수 있다. 이 시스템에서 휴학생의 정보도 검색할 수 있으려면 휴학생의 학번과 정보도 추가해야할 것이다. 이처럼 자료 집합에 필요한 원소를 추가하여 특정 조건을 만족하도록 만드는 것을 관계의 폐포라고 한다. 관계의 폐포(Closure) 집합 `A` 에 대한 관계를 `R` 이라 하고 관계 `R` 이 가져야 하는 성질을 `P` 라고 할 때, 관계 `R` 을 포함하면서 성질 `P` 를 갖는 가장 작은 집합 `A` 에 대한 관계 `S` 성질 `P` 를 갖지 않는 관계 `R` 이 성질 `P`를 갖도록 순서쌍을 추가할 때는 반드시 필요한 최소한의 순서..

합성 관계 2개 이상의 관계를 이용해 새로운 관계를 만드는 것을 '관계를 합성한다'고 하고, 이렇게 만든 관계를 합성 관계라고 한다. 합성 관계(Composite Relation : $S \circ R$) 집합 `A` 에서 집합 `B` 로의 관계 `R` 과 집합 `B` 에서 집합 `C` 로의 관계 `S` 가 있을 때, 이 두 관계를 이용해 구하는 집합 `A` 에서 집합 `C` 로의 관계 $$S \circ R = \{(a, c) ∈ A \times C \; | \; a ∈ A, \; b ∈ B, \; c ∈ C, \; (a, b) ∈ R, \; (b, c) ∈ S \}$$ 합성 관계를 구하려면 둘 이상의 관계 사이에 공통으로 사용되는 자료 집합이 있어야 한다. 예 수강과목 담당교수 정보 학번 과목코드 교수..

관계의 성질 하나의 집합에 대한 관계의 경우, 순서쌍 원소의 구성에 따라 관계의 성질을 판별할 수 있다. 관계의 성질에는 반사, 비반사, 대칭, 반대칭, 추이 5가지가 있다. 반사 관계와 비반사 관계 반사 관계(Reflexive Relation) 집합 `A` 에 대한 관계 `R` 이 있을 때, 모든 $a ∈ A$ 에 대해 $(a, a) ∈ R$ 인 관계 ($Δ_{A} = \{ (a, a) \; | \; a ∈ A \}$) 비반사 관계(Irreflexive Relation) 집합 `A` 에 대한 관계 `R` 이 있을 때, 모든 $a ∈ A$ 에 대해 $(a, a) \not ∈ R$ 인 관계 집합 `A` 에 대한 관계 `R` 이 반사 관계이려면, 집합 `A` 에 포함되는 모든 원소 `a` 에 대해 자기 자신..

관계의 표현 관계는 일반적으로 순서쌍의 집합으로 표현하지만, 이 외에도 화살표 선도, 좌표 도표, 관계 행렬, 방향 그래프 등 여러 가지 방식으로 표현할 수 있다. 화살표 선도를 이용한 관계 표기 화살표 선도(Arrow Diagram) 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 두 집합의 원소 간의 관계를 화살표로 나타낸 도표 화살표 선도에서 화살표의 방향은 관계에 포함되는 순서쌍의 앞에 오는 원소에서 시작하여 뒤에 오는 원소로 향하도록 한다. 역관계의 경우, 관계 `R` 의 화살표 선도와 화살표 방향이 반대이다. 좌표 도표를 이용한 관계 표기 좌표 도표(Coordinate Diagram) 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 집합 `A` (정의역)의 ..

관계의 개념 인공지능은 데이터베이스에 저장된 지식을 활용하여 새로운 지식을 생성하거나 문제를 해결한다. 데이터베이스는 자료를 효율적으로 처리할 수 있도록 관련 있는 자료를 중복 없이 통합한 집합으로, 구조화된 자료 형태이다. 이처럼 구조화된 자료에 의미 있는 관계를 부여하면 새로운 정보를 만들 수 있고, 같은 자료 사이의 관계라고 하더라도 부여된 관계에 따라 전혀 다른 정보가 될 수 있다. 그러므로 데이터베이스에 저장된 자료 자체뿐 아니라 그 자료 사이의 관계는 인공지능이 지식을 생성하고 판단하는데 큰 영향을 미친다. 다음과 같은 자료 집합이 존재하고, 각 집합에 포함된 자료는 오류와 중복이 없어 정보를 제공하는 데 충분하다고 가정하자. 위 그림처럼 자료 집합을 개별적인 정보만으로 구성한다면 학생, 전공..

집합의 분할 인공지능에서 지식의 자원이 되는 데이터를 관리하려면 일정한 기준으로 전체 데이터를 분류하는 과정이 필요하다. 이 과정을 통해 분류한 데이터 집합은 반드시 하나 이상의 데이터를 포함해야 하고, 데이터 집합을 모두 합쳤을 때는 제외된 데이터가 없어야 한다. 또한 분류한 집합 사이에 공통으로 포함되는 데이터가 존재하지 않아야 한다. 이렇게 보유한 데이터를 정확하게 분류해서 관리해야 인공지능이 쓸데없는 추론 과정을 수행하지 않으면서 정확한 정보를 추론할 수 있다. 이러한 인공지능의 데이터 관리에 적용할 수 있는 개념이 집합의 분할이다. 분할(Partition : $A = \{A_{1}, A_{2}, \cdots, A_{n} \}$ ) 공집합이 아닌 임의의 집합 $A$ 를 서로소이면서 공집합이 아닌 ..

집합의 대수 법칙 수에 대한 사칙 연산에도 일정한 규칙이 있듯이, 집합 연산에도 일정한 규칙이 있다. 이를 집합의 대수 법칙이라고 하는데, 대수 법칙을 이용하면 복잡한 집합 연산을 간단히 할 수 있다. 집합의 대수 법칙 집합 연산 법칙 $A ∪ \varnothing = A$ $A ∩ U = A$ 항등 법칙(Identity Law) $A ∪ U = U$ $A ∩ \varnothing = \varnothing$ 지배 법칙(Domination Law) $A ∪ A = A$ $A ∩ A = A$ 멱등 법칙(Idempotent Law) $A ∪ B = B ∪ A$ $A ∩ B = B ∩ A$ 교환 법칙(Commutative Law) $A ∪ (B ∪ C) = (A ∪ B) ∪ C$ $A ∩ (B ∩ C) = (A..

집합의 연산 집합과 집합의 연산을 통해 새로운 집합을 구할 수 있다. 합집합과 교집합 합집합(Union : $A ∪ B$ ) 집합 `A` 와 `B` 에 모두 속하거나 둘 중 한 집합에만 속하는 원소들로 이루어진 집합 $$A ∪ B = \{ x \; | \; x ∈ A \lor x ∈ B \}$$ 합집합은 두 집합에 포함된 원소들을 모두 합쳐서 새로운 집합을 만드는 연산으로, 두 집합에 공통으로 존재하는 원소는 한 번만 작성한다. 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{4, 5, 6, 7 \}$ 일 때, $A ∪ B = \{ 1, 2, 3, 4, 5, 6, 7 \}$ 교집합(Intersection: $A ∩ B$ ) 집합 `A` 와 `B` 에 모두에 속하는 원소들로 이루어진 집합..

집합의 종류 집합은 구성되는 원소의 개수나 집합 간의 포함 관계에 따라 명칭이 정의된다. 전체 집합(Universal Set : $U$ ) 논의 대상이 되는 원소 전체를 포함하는 집합 전체 집합은 논의 대상에 따라 달라질 수 있으므로, 주어지는 문제에 따라 달라질 수 있다. 예) 집합 $A = \{ a \; | \; a > 13, \; a ∈ \mathbb{N} \}$ 가 주어질 때, 문제에 따라 집합 `A` 에 대한 전체 집합은 자연수 집합 $\mathbb{N}$ 이 될 수 있고, 집합 `A` 자체가 될 수 있다. 그러므로 전체 집합에 대한 판단은 문제에 따라 달라진다. 공집합(Empty Set : $\varnothing$ ) 원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합 ($|\varnoth..

집합의 개념 컴퓨터가 활용하려는 데이터들은 정리되어 있지 않으면 효용 가치가 없다. 그렇기 때문에 컴퓨터에서 데이터를 효율적이고 효과적으로 활용하기 위해서는 기준에 따라 데이터를 정리하여 관리할 필요가 있다. 이 때 필요한 개념이 집합이다. 집합(Set : $A, B, C, \cdots$) 명확한 기준에 따라 공통 성질을 가지며 중복되지 않는 원소(Element, Member)의 모임 ① 유한 집합(Finite Set) : 집합을 구성하는 원소의 개수가 유한개인 집합 ② 무한 집합(Infinite Set) : 집합을 구성하는 원소의 개수가 무한히 많은 집합 집합은 공통 성질을 가지며, 중복되지 않는 원소로 구성된다. 그러므로 집합에 포함되는 원소들을 구분할 수 있는 명확한 기준이 있어야 하는데, 이 기준..

행렬과 연립 일차 방정식 행렬은 연립 일차 방정식을 풀기 위한 방법을 연구하면서 나온 개념이다. 일차 방정식(Linear Equation) / 선형 방정식 $a_{1}, a_{2}, \cdots, a_{n}, b$ 가 실수일 때, 다음과 같이 표현되는 식 $$a_{1}x_{1} + a_{2}x_{2} + \cdots + a_{n}x_{n} = b \quad (a_{1}, a_{2}, \cdots, a_{n} : \text{계수}, \; b : \text{상수}, \; x_{1}, x_{2}, \cdots, x_{n} : \text{변수})$$ 문제를 해결하기 위한 어떤 식이 한 개 이상의 변수를 포함할 때 이 식을 방정식(Equation)이라고 하며, 포함하는 변수의 차수가 1일 때 이를 일차 방정식 또..

역행렬 어떤 수의 곱셈에 대한 역원은 그 수와 곱했을 때 항등원이 나오는 수로, `a ≠ 0` 인 실수 `a` 의 곱셈에 대한 항등원은 `1` 이고, `a` 의 역원은 $\frac{1}{a}\left( a × \frac{1}{a} = 1 \right)$ 이다. 행렬에서도 항등원과 역원의 역할을 수행하는 행렬이 있는데, 항등원인 행렬은 단위 행렬 `I` 이고, 역원인 행렬은 역행렬이다. 역행렬(Inverse Matrix : $A^{-1}$) 정사각 행렬 `A` 에 대하여, `AB = BA = I` 를 만족하는 행렬 `B` $$AA^{-1} = A^{-1}A = I$$ 일반적으로 행렬의 곱셈은 교환 법칙이 성립하지 않지만, 행렬 `A` 와 행렬의 역행렬 `A^{-1}` 를 곱한 $AA^{-1}$ 와 $A^{..

행렬식 하나 이상의 수로 구성된 `n` 차 정사각 행렬에는 이 행렬을 대표하는 수를 대응할 수 있는데, 그 수를 구하는 식을 행렬식(Determinant)이라고 한다. 행렬식을 이용하면 역행렬이 존재하는지 여부를 판별할 수 있고, 연립 일차 방정식의 해가 유일하게 존재하는지도 판단할 수 있다. 행렬식(Determinant : $det(A)$ 또는 $|A|$) `n` 차 정사각 행렬에 대응하는 수를 구하는 식 $$det(A) = |A| = \begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1} & a_{n2} & \cdots..

행렬의 종류 행렬의 형태 혹은 구성 원소에 따라 다양한 종류의 행렬로 나눌 수 있다. 대각 행렬(Diagonal Matrix) `n` 차 정사각 행렬에서 주대각 원소 $a_{11}, a_{12}, \cdots, a_{nn}$ 을 제외한 나머지 원소가 모두 `0` 인 행렬 $$A = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & a_{nn} \end{bmatrix}$$ 대각 행렬은 반드시 정사각 행렬이어야 한다. 예 $A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 &..

행렬의 연산 행렬에서 가능한 연산은 덧셈, 뺄셈, 스칼라곱, 곱셈이 있다. 행렬의 덧셈과 뺄셈 행렬의 덧셈과 뺄셈이 가능하려면 두 행렬의 크기가 같아야 한다. 행렬의 크기가 `m × n` 인 두 행렬 `A, B` 에서 같은 위치에 있는 원소끼리 더하거나 빼는 연산 $A = [a_{ij}] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}, \quad B = [b_{ij}] = \begin{bmatrix} b_{11} & b_{12} & \cd..

행렬의 개념 행렬은 다수의 동일한 타입의 데이터들에 동일한 연산을 수행하기에 적합하다. 행렬(Matrix : $A = [a_{ij}]$) 하나 이상의 원소를 1차원 또는 2차원의 형태로 나열한 배열 `m` 행 `n` 열로 나열한 실수의 2차원 배열 ($m > 0, \; n > 0$) $$A = [a_{ij}] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix} \quad (1 ≤ i ≤ m, \; 1 ≤ j ≤ n)$$ - `a_{ij}` : ..

수학적 귀납법 첫 번째 단계가 성립하고 `n` 번째 단계가 성립한다고 가정했을 때, `n + 1` 번째 단계로 성립함을 보이는 방식의 증명 방법을 수학적 귀납법이라고 한다. 수학적 귀납법은 0보다 크거나 같은 정수의 범위에서 발생하는 일정한 규칙을 증명하는 데 유용하다. 수학적 귀납법(Mathematical Induction) 0보다 크거나 같은 정수 범위에서 발생하는 일정한 규칙을 나타내는 명제 `P(n)` 이 성립함을 증명하는 방법 수학적 귀납법은 다음 세 단계로 증명한다. ① 기본 가정 : 명제의 논의 영역 `D` 의 첫 번째 값 `d` 에 대하여, `P(d)` 가 참(T)임을 보인다. ② 귀납 가정 : 논의 영역에 속하는 임의의 값 `k` 에 대하여, `P(k)` 가 참(T)이라고 가정한다. ③ ..

간접 증명법 간접 증명법은 증명해야 하는 명제를 변형하여 증명하는 방법으로, 모순 증명법, 대우 증명법 그리고 존재/반례 증명법이 있다. 모순 증명법 : 증명해야 하는 조건 명제에서 결론에 해당하는 명제를 부정하여 증명하는 방법 대우 증명법 : 증명해야 하는 조건 명제를 대우 명제로 변형하여 증명하는 방법 존재/반례 증명법 : 명제를 참(T)으로 만드는 원소가 있는지, 혹은 명제를 거짓(F)으로 만드는 원소가 있는지를 판단하여 증명하는 방법 모순 증명법(Proof by Contradiction) 조건 명제 `p → q` 와 $\neg (p \land \neg q)$ 가 동치임을 이용해, $p \land \neg q$ 가 거짓(F)임을 보임으로써 증명하는 방법 $\neg (p \land \neg q)$ $..

직접 증명법 직접 증명법은 주어진 명제를 변형하거나 예를 구하는 것이 아니라, 공리, 정의, 정리 등을 이용하여 주어진 그대로 증명하는 방식이다. 직접 증명법(Direct Proof) 조건 명제 `p → q` 가 참(T)임을 증명하기 위해 전제 `p` 를 참(T)으로 가정했을 때, 결론 `q` 도 참(T)임을 증명하는 방법 예 : '두 홀수 `m` 과 `n` 의 곱은 홀수이다.' 를 직접 증명법으로 증명하기 '두 홀수 `m` 과 `n` 의 곱은 홀수이다' 라는 명제를 조건 명제의 형태로 나타내면 다음과 같다. `p → q` : 두 정수 `m, n` 이 홀수이면, `m` 과 `n` 의 곱은 홀수이다. `p` : 두 정수 `m, n` 은 홀수이다. `q` : `m` 과 `n` 의 곱은 홀수이다. 홀수 `m`..

증명의 이해 증명은 어떤 사실이 참(T)임을 보이는 것으로서 증명에 사용되는 모든 내용들이 타당해야만 정당한 증명이 된다. 증명(Proof) 하나의 명제가 참(T) 임을 확인하는 과정 증명의 과정에는 추론 방식이 적용된다. 추론 : 참(T)으로 판별된 전제를 이용하여 결론이 참(T) 또는 거짓(F)임을 판별하는 과정 그러므로 증명 과정에서도 참(T)인 전제를 사용해야 하며, 이 전제를 이용하여 주어진 명제가 참(T)임을 보여야 한다. 증명에서 사용되는 전제로는 공리, 정의, 정리가 있다. 공리(Axiom) 별도의 증명 없이도 항상 참(T)이라고 판단하는 명제 다음 명제들은 공리의 대표적인 예이다. 명제 `p` 가 참(T)이면, 명제 $p \lor q$ 도 참(T)이다. 두 점이 주어질 때, 그 두 점을 ..