여러가지 증명 방법 이산수학 내에서 증명법은 크게 수학적 귀납법 / 직접 증명법 / 간접 증명법으로 나눌 수 있습니다. 수학적 귀납법(mathematical induction): 연역법의 일종으로, 주어진 사실들과 공리들에 입각해 추론을 통해 새로운 사실을 도출하는 것 직접 증명법(direct proof): 정의에 의해 혹은 이미 결과가 나온 내용을 토대로 논리적으로 명제를 직접 증명하는 것 간접 증명법(indirect proof): 모순, 대우, 논리적 동치 등을 이용해 간접적으로 결론이 참임을 이끌어 내 증명 수학적 귀납법 $P(n)$이 양의 정수 $n$에 의해 정의된다고 하자. $a$가 임의의 정수일 때, 다음의 두 명제가 참임을 가정한다. 1. $P(a)$는 참이다. 2. 모든 $k ≥ a$인 정..

분할 (partition) 분할 (partition): 공집합이 아닌 집합 $A = \{A_1, A_2, A_3, \cdots\}$는 다음과 같은 조건을 만족시켜야 한다. (1) $A$는 모든 $A_i$의 합집합이다. (2) 집합 $A_1, A_2, A_3, \cdots$는 서로소이다. 즉, $i ≠ j$이면, $A_i \cap A_j = \phi$이다.

멱집합 (power set) 멱집합 (Power Set): 임의의 집합 $S$에 대하여, $S$의 모든 부분 집합을 원소로 가지는 집합 $$P(S) = \{A \space | \space A \subseteq S \}$$ $$|P(S)| = 2^{|S|}$$

벤 다이어그램 (Venn Diagram) 벤 다이어그램 (Venn Diagram) 주어진 집합들 사이의 관계와 집합의 연산에 대하여 이해하기 쉽게 전체 집합 $U$를 사각형으로 표현하고 안에 원으로 표현한 방식 합집합 합집합 (Union): 임의의 두 집합 $A$, $B$에 대하여 집합 $A$ 또는 집합 $B$에 속하는 모든 원소들의 집합 $$A \cup B = \{x \space | \space x \in A \space or \space x \in B\}$$ 교집합 교집합 (Intersection): 임의의 두 집합 $A$, $B$에 대하여 집합 $A$에도 속하고 집합 $B$에도 속하는 모든 원소들의 집합 $$ A \cap B = \{x \space | \space x \in A \space an..

집합의 표현 집합(Set): 수학적 성질을 가지는 객체들의 모임. 어떤 객체가 특정 집합에 속하는지 아닌지 분명히 구분할 수 있어야 함. 유한 집합 원소의 개수가 유한인 경우 무한 집합 유한 집합이 아닌 경우 원소나열법 원소나열법(Set-Roster Notation): 집합의 원소들을 중괄호 사이에 하나씩 나열하는 방법 $$S = \{1, 2, 3, 4, 5\}$$ 조건제시법 조건제시법(Set-Builder Notation): 집합의 원소들이 가지고 있는 특정한 성질을 기술해 나타내는 방법 $$\{x \in S \space | \space p(x)\}$$ 카디널리티 (Cardinality) 카디널리티(Cardinality): 집합 $S$ 내에 있는 서로 다른 원소들의 개수 $$|S| = 5$$ ..

술어 (Predicate) 명제에 관한 논제들은 참과 거짓이 명확히 결정되었습니다. 그러나 앞으로 볼 명제들은 변수의 값에 따라서 참이 될 수도 있고 거짓이 될 수도 있습니다. 술어 (Predicate): 특정 값이 변수에 따라 대체될 때 명제가 되는 유한한 숫자의 변수를 포함하는 문장. 술어 변수의 정의역(domain)은 변수로 대체될 수 있는 모든 값의 집합이다. $x^2 + 5x + 6 = 0$이라는 명제는 $x$의 값이 -2 또는 -3일 경우에는 참의 값을 가지고 그렇지 않으면 거짓의 값을 가집니다. 이런 경우 ‘식을 만족시키는 변수가 있다’고 합니다. 이와 같은 형태의 명제를 $p(x)$로 표시하고 $p(x)$를 변수 $x$에 대한 명제 술어(propositional predicate)라 합니다..

추론 (argument): 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도해내는 방법. 여기서 주어진 명제들인 $p_1, p_2, ..., p_n$을 전제(premise)라 하고, 새로이 유도된 명제 $q$를 결론(conclusion)이라고 합니다. 주어진 전제가 참이고 결론도 참인 추론을 유효 추론(valid Argument)이라 하고, 추론이 거짓이면 허위 추론(fallacious argument)이라 합니다. 진리표를 이용하여 전제가 참인 경우 결론이 참인지 거짓인지 봄으로써 구분할 수 있습니다. 전제를 $p_1, p_2, ..., p_n$이라 하고 결론을 $q$라 할 때 추론에 대한 것을 식으로 표현하면 $$p_1, p_2, ..., p_n \vdash q$$ 라고 표시합니..