[이산 수학] Chapter 1 집합과 논리

 
 
 

---

 
1. 이산 수학이란?
2. 집합이란?
3. 논리란?
 

---

 
 
1. 이산 수학이란?
이산 수학은 그래프(정점과 간선의 집합) 및
부울 대수(정의된 특정 연산을 갖는 집합)와 같은 객체들을 다룬다.
 
 
 
2. 집합이란?
집합의 개념은 수학과 응용 수학의 모든 분야에서 기본이 된다.
집합(set)은 객체들의 모임이다.
여기서 객체들 사이의 순서는 중요하지 않다.
이 객체들을 원소 또는 멤버라고 부른다.
만약 어떤 집합이 유한하고 지나치게 크지 않다면
집합 내의 원소들을 나열하여 그 집합을 기술할 수 잇다.
예를 들어 아래의 수식을 보자.

A = {1,2,3,4}

해당 집합 A가 4개의 원소 1,2,3,4로 구성되어 있다는 것을 나타낸다.
집합은 원소들에 의해 결정되며, 원소들이 나열되는 특정한 순서에 의해서 결정되는 것은 아니다.
따라서 집합 A는 다름과 같이 나타낼 수도 있다.

A = {1,3,4,2}

집합 내의 원소들은 서로 다르다는 것을 가정하고 있다.
필요한 경우에는 중복된 원소를 갖기도 하지만,
보통 집합 내의 각 원소들은 한 번만 나타낸다.
 
만약 집합이 많은 원소를 갖는 유한 집합이거나 또는 무한 집합이라면,
집합의 원소가 될 수 있는 조건을 열거함으로써 그 집합을 나타낼 수 있다.
예를 들어 다음 수식과 같이 말이다.

B = {x|x 는 양수이고 짝수}

즉 B는 2,4,6,... 으로 구성된다.
해당 식은 "B는 양수이고 짝수인 모든 x의 집합이다"라고 읽는다.
 
집합은 어떠한 종류의 원소도 가질 수 있으며,
원소들이 모두 같은 종류일 필요는 없다.

 
|X|은 X의 기수(cardinality)라고 부른다.
집합 A에 대하여 |A| = 4이며, A의 기수는 4이다.
집합  {R,Z}는 2개의 원소, 즉 R 및 Z를 갖고 있으므로 기수는 2이다.
 
 
3. 논리란?
논리(logic)는 추론에 관한 연구이다.
특히 추론이 옳은지 아닌지 따져 보는 것과 관련된다.
논리는 특정한 문장의 내용과 대립하는 문장 사이의 관계에 초점을 맞춘다.
 

 

집합을 서술하는 방법

 

1. 원소나열법

2. 조건제시법

수학에서 중요한 건 조건제시법을 읽고 쓰는 걸 잘하는 것이다.

 

구간:

[a,b] = {x|a <= x <= b} <- 닫힌 구간

(a,b) = {x|a < x < b } <- 열린 구간

 

조건 명제와 논리적 동치

 

"만약 수학과에 6만 달러를 지원한다면,

신임 교수 한 명을 고용할 수 있다"

 

6만 달러가 지원된 상태라면,

그 학과는 신임 교수 한 명을 고용할 수 있다는 것을 의미한다.

위 같은 명제를 조건 명제라고 부른다.

 

p이면 q이다. 는 조건 명제라고 하며,

p를 가설이라고 하며 q인 명제를 결론이라고 부른다.

부정

~p라 쓰고 'not p 또는 p가 아니다' 라고 함

p의 진리값이 참이면 ~p의 진리값은 거짓

 

가설이 거짓이므로 참이 되는 조건 명제를 기본 참 명제 또는 무의미한 참 명제라고 부른다.

 

논리곱 

기호는 p ^ q 라 쓰고, 

p and q 또는 p 그리고 q 라고 한다.

p ^ q 는 p,q 두 명제가 모두 참인 경우에만 참의 진리값을 가진다.

 

필요조건

필요조건은 단지 어떤 특정한 결과가 이루어지기 위해 필요한 조건이다.

그 조건이 결과를 보장하는 것은 아니다.

그러나 그 조건이 성립하지 않을 경우 결과는 생기지 않는다.

 

충분조건

충분조건은 특정한 결과를 보장하기에 충분한 조건이다.

이 조건이 성립하지 않더라도 결과는 다른 방식에 의해 이루어질 수 있고

이루어지지 않을 수도 있다.

 

논리합

임의의 두 명제 p,q가 또는(or)로 연결된 것이다.

 

베타적 논리합 (exclusive OR)

p XOR q라고 한다.

두 명제 중 하나의 명제만 참인 경우에 진리 값을 가진다.

논리회로 구성에 많이 쓰인다.