CS 전공지식

집합과 논리

무야호야호 2023. 2. 11. 23:18

이산수학이란?

집합과 논리

1. 집합

집합이란?

여러 원소들(element)의 모임으로, 중복된 원소를 가지지 않음

벤다이어그램

집합 사이의 관계를 표시하기 위해 도형으로 표기한 것

유한집합 / 무한집합

집합 A에 속하는 원소의 개수를 |A|로 표현하며, 원소가 유한개인 집합을 유한집합, 원소가 무한개인 집합을 무한집합이라고 한다.

집합의 포함관계

집합 A,B에 속하는 원소가 모두 동일할 때, 두 집합은 서로 같다고 하며 기호로 A = B로 표시한다.

합집합 : A ∪ B

A의 원소들과 B의 원소들을 모두 모은 집합을 A와 B의 합집합이라 하며 위와 같이 표기한다. 아래의 벤 다이어 그램에서 색칠된 부분을 뜻한다.

교집합 : A ∩ B

A에 속하는 원소임과 동시에 B에도 속하는 원소들의 집합을 교집합이라 하며 위와 같이 표기한다. 아래의 벤 다이어 그램에서 색칠된 부분을 뜻한다.

서로소

집합 A와 B에 공통으로 속한 원소가 하나도 없을 경우 서로소라 부른다.

차집합 : A - B

A의 원소 중에서 B에 속하지 않는 원소만으로 이루어진 집합을 A - B라 하며 A - (A ∩ B)와 같다.

여집합 : A^c

집합 A에 속하지 않지만 전체집합 U에 속하는 원소들의 집합을 A의 여집합이라 하며 아래와 같이 표기한다.

집합의 법칙들

2. 명제

명제란?

객관적으로 참, 거짓을 판단할 수 있는 문장이나 수식. 이 때, 보통 참인 경우 알파벳 T로 거짓인 경우 알파벳 F로 표시한다. 참, 거짓을 가리키는 값을 진릿값(Truth value)이라고 한다.

3. 논리

논리연산자들

부정 ~p

명제 p에 대하여 p의 진릿값을 반대로 갖는 명제를 위와 같이 표기하며 p가 아니다 또는 not p라고 읽는다

참고 : p가 참인 명제일 경우 ~ p는 거짓, p가 거짓인 명제일 경우 ~p는 참이다.

논리곱(and) : p ∧ q

명제 p,q에 대하여 p와 q가 모두 참일 경우에만 참이고, 그렇지 않을 경우 거짓이 되는 명제

논리합(or) : p ∨ q

명제 p,q에 대하여 p와 q가 모두 거짓일 경우에만 거짓이고, 그렇지 않을 경우 참이 되는 명제

조건명제

명제 p,q에 대하여 p가 가정이고 q가 결론이 되는 명제이다. 이 때, p이면 q이다 또는 if p, then q 등으로 읽는다.

주의) 조건명제 p → q의 진릿값은 p가 거짓일 경우 항상 참이고 p가 참일 경우 q의 진릿값과 일치한다.

역, 이, 대우

역

조건 명제 조건 명제 p → q에 대하여 가정과 결론이 바뀐 q → p를 p → q, 역이라 부른다.

이

조건 명제 p → q에 대하여 가정과 결론을 각각 부정한 ~p → ~q를 p → q의 이라 부른다.

대우

조건 명제 p -> q에 대하여 가정과 결론이 바뀐 동시에 부정한 ~q → ~p를 p → q의 대우라 부른다.

명제함수와 한정자(quantifier)

명제함수 P(x)

변수 X를 포함하여 진릿값을 판별할 수 있는 문장이나 수식.

예) P(x)가 x + 1= 0 이라는 명제 함수라고 하자. 그러면 X의 값에 따라 P(x)의 진릿값을 판별할 수 있다.
- x가 1일 경우, P(1)은 1+ 1= 0이라는 명제가 되고 이는 거짓인 명제이다.
- x가 -1일 경우, P(-1)은 -1+ 1= 0이라는 명제가 되고 이는 참인 명제이다.

전체한정자∀

모든 값에 대하여 라는 말을 쓸 때 라는 수학기호를 쓰며 영어로 for every 라고 읽는다.

∀xP(x) 또는 for every x, P(x)라는 명제는 논의의 대상이 되는 모든 x에 대하여 참일 경우 참인 명제이다.

존재한정자 ∃

어떤 값이 존재하여 라는 말을 쓸 때 크 라는 수학기호를 쓰며 영어로 there exists 라고 읽는다.

∃xP(x) 또는 there exists x, P(x)라는 명제는 P(x)가 참이 되는 x가 하나라도 있을 경우 참이되는 명제이다.

요약

이산수학의 집합과 논리는 여러 원소들의 모임인 집합과 그 사이의 관계를 벤다이어그램으로 표현하는 것으로, 유한집합과 무한집합, 합집합, 교집합, 서로소, 차집합, 여집합 등의 개념을 사용한다.

Uploaded by