2023-10-08-DiscreteStructure-L03

• toc {:toc}

3.1 집합의 표현

• 집합 : 대상이 명확한 객체들의 모임 ⇒ 집합에는 중복되는 원소가 없어야 한다.

• 원소 나열법 : 집합의 원소들을 {}사이에 하나씩 나열하는 방법 e.g. {1, 2, 3, 4, 5}

• 조건 제시법 : 집합의 원소들이 가지고 있는 특정한 성질을 기술해 나타내는 방법 e.g.

• 카디날리티 : 집합 S 내에 있는 서로 다른 원소들의 개수 = 집합 S의 원소의 개수 = 원소수 = |S|

  • 집합 S1, S2이 유한 집합이고 일대일 대응 관계인 경우 서로 같은 카디날리티를 가지고 있다고 한다.
  • S1이 S2의 진부분 집합인 경우 서로 다른 카디날리티를 갖는다.
  • S1, S2가 e.g. 짝수의 집합, 모든 정수들의 집합처럼 무한 집합인 경우 진부분 집합,의 관계이나 같은 카디날리티를 가질 수 있다.
    • 그렇다고 모든 무한 집합이 같은 카디날리티를 갖는 것은 아니다.

• 집합 S의 원소의 개수에 따른 분류

  • 유한 집합 : S의 원소의 개수가 유한인 경우
  • 무한 집합 : S의 원소의 개수가 무한인 경우

• 가산적 집합/가산적으로 무한한 집합 : 정수의 집합과 일대일의 대응 관계에 있는 집합

• 부분 집합 : 집합 A, B에서 집합 A의 모든 원소가 집합 B의 원소에 속하는 경우 A, 개

• 진부분 집합 : 자기 자신을 제외한 부분 집합, 개

3.2 집합의 연산

• 벤 다이어그램 이용

1. 합집합 = {} : A, B에 속하는 모든 원소
2. 교집합 = {} : A, B 둘 다 속하는 모든 원소
   • 집합 A와 집합 B가 공통된 원소를 하나도 가지지 않은 경우 두 집합 A, B를 서로소라고 한다.
3. 차집합 = {} : A는 속하고 B에는 속하지 않는 모든 원소
4. 대칭 차집합
   • = {}
5. 곱집합 : A와 B의 원소의 순서쌍을 말한다.

• 집합 연산의 카디날리티

• 집합의 대수 법칙

• 쌍대 : 집합에 관한 명제에서 그 명제 안에 있는 교집합과 합집합을 전체 집합에 대한 여집합으로 바꾸어서 만든 새로운 명제 e.g. 드 모르간 법칙

3.3 집합류와 멱집합

• 집합류 : 부분 집합의 모임. 집합의 집합

• 멱집합 : 임의의 집합 S에 대하여, S의 모든 부분 집합을 원소로 가지는 집합

• 멱집합 산출 시 주의점

1. 멱집합 구한 후 멱집합의 원소의 개수가 가 되는지 확인한다.
2. 멱집합의 원소는 모두 집합이다. 공집합을 제외한 모든 원소는 집합을 표시하는 중괄호 안에 쓰여진다.
3. 집합 A의 원소 중 집합인 원소가 있을 때 멱집합에서는 추가적인 집합 표기가 필요하다. 원소가 집합이기 때문

3.4 집합의 분할

• S를 공집합이 아닌 임의의 집합이라 할 때 집합 S의 분할은 3가지 조건을 만족해야 한다.

1. 는 공집합이 아닌 집합 S의 부분 집합이다.
2. 분할의 원소들의 합집합이 전체집합이 된다.
3. 들 사이는 서로소이다.

• 분할의 원소 를 블록이라 한다.
  • 대한민국의 각 도를 합하면 대한민국 전체가 되고, 서로 겹치는 부분이 없다.
  • 각 도는 대한민국의 분할이 된다.

3.5 수의 표현과 진법의 변환

수의 표현

1. 10진법 - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
2. 2진법 - 0, 1
3. 8진법, 0, 1, 2, 3, 4, 5, 6, 7, 8
4. 16진법, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

진법의 변환

• 2, 8, 16진수을 10진수로 변경하기 자리수 별로 x진수의 x를 거듭제곱해 곱해주고 합한다.

• 10진수를 2, 8, 16진수로 변경하기 x진수로 변경할 때 x로 나눌 수 없을 때까지 나누고 나머지를 역순으로 작성한다.

• 소수를 2진수로 변환하기
  • 정수부와 소수부를 나누어 계산한다.
  • 정수부는 10진수를 2진수로 변환하는 방법을 똑같이 사용한다.
  • 소수부는 소수부가 0이 될 때까지 2를 계속 곱하고 위에서 아래 순서로 쓴다.

• 2진수, 8진수, 16진수의 상호 변환 관계 2진수에서 8진수로 변환할 때는 3개씩 묶어서 변환하고, 16진수로 변환할 때는 4개씩 묶어서 변환한다.

3.6 2진수의 덧셈과 뺄셈

• 2진수의 덧셈

1. 10진수를 2진수로 변환한다.
2. 두 수를 합하고, 자리 올림을 진행한다.
3. 연산 결과를 10진수로 변환한다.

• 보수의 개념

  • (r-1)의 보수 : (r-1)의 값에서 수의 각 자리의 숫자를 뺀 수. e.g. 의 9의 보수
  • r의 보수 : (r-1)의 보수에서 가장 낮은 자리에 1을 더한 수

• 보수를 이용한 뺄셈 : 1)올림수가 있는 경우와 2)올림수가 없는 경우 동작으로 나누어진다.

  • 올림수가 있는 경우
    1. 감수의 1의 보수를 취해 피감수에 더한다.
    2. 올림수를 가장 낮은 자리로 옮겨 더해준다.
  • 올림수가 없는 경우
    1. 감수의 1의 보수를 취해 피감수에 더한다.
    2. 결과의 1의 보수를 취한다.
    3. 부호를 붙인다.

참고문헌

• 4차 산업혁명 시대의 이산수학, 김대수, 생능출판사

연결문서