집합과 논리(집합, 명제, 논리)

집합

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

집합의 표기법
원소나열법 : 집합에 속하는 원소들을 일일이 나열하는 방법이다. 예시) A = {1, 2, 3, 4, 5}
조건제시법 : 집합에 포함되는 원소들의 성질을 조건식으로 제시하는 방법이다. 예시) A = {𝑥 | 0 < 𝑥 ≤ 10, 𝑥는 자연수 }

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

집합의 종류
전체 집합 : 논의 대상이 되는 원소 전체를 포함하는 집합으로, 보통 알파벳 U로 표기한다.
공집합 : 원소를 하나도 가지지 않는 집합으로 ∅ 또는 { }로 표기한다.

집합의 포함관계
집합 A, B에 속하는 원소가 모두 동일할 때, 두 집합은 서로 같다고 하며 기호로 A = B로 표시한다.
부분집합 : A ⊆ B
집합 A의 모든 원소가 집합 B에 포함될 때 A는 B의 부분집합이라 하고 위와 같은 기호로 표시한다.
진부분집합 : A ⊂ B
집합 A가 집합 B의 부분집합이지만 A = B는 아닐 경우 A는 B의 진부분집합이라 한다.

원소와 집합의 포함 관계
원소 a가 집합 A에 포함될 때, a ∈ A로 표시하고 "a는 A의 원소다." 라고 읽는다.
원소 a가 집합 A에 포함되지 않을 때, a ∉ A로 표시하고 "a는 A의 원소가 아니다." 라고 읽는다.

합집합 : A ∪ B
A의 원소들과 B의 원소들을 모두 모은 집합을 A와 B의 합집합이라 하며 위와 같이 표기한다.

교집합 : A ∩ B
A에 속하는 원소임과 동시에 B에도 속하는 원소들의 집합을 교집합이라 하며 위와 같이 표기한다.

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

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

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

집합	법칙
A ∪ ∅ = A, A ∩ U = A	항등법칙
A ∪ U= U, A ∩ ∅ = ∅	지배법칙
A ∪ A = A, A ∩ A = A	멱등법칙
A ∪ B = B ∪ A, A ∩ B = B ∩ A	교환법칙
A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C	결합법칙
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)	분배법칙
( A ∁ ) ∁ = A	이중 여집합
A ∪ A ∁= U, A ∩ A ∁ = ∅, ∅ ∁ = U, U ∁ = ∅	여집합의 법칙
( A ∪ B ) ∁ = A ∁ ∩ B ∁, ( A ∩ B ) ∁ = A ∁ ∪ B ∁	드 모르간의 법칙
A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A	흡수 법칙

 

명제

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

다음 중 명제는 무엇일까?
1. 홍길동은 잘 생겼다.
2. 홍길동은  머리가 좋다.
3. 홍길동은  만 21살이다.
4. 1 + 1 = 2

1. 객관적으로 판단할 수 없으므로(개인의 기준에 따라 다르므로) 명제가 아니다.
2. 객관적으로 판단할 수 없으므로(개인의 기준에 따라 다르므로) 명제가 아니다.
3. 주민등록상 객관적으로 판단할 수 있으므로 명제. 단, 거짓인 명제이다.
4. 산수의 원리에 따라 객관적으로 참, 거짓을 판단할 수 있으므로 명제이며, 참인 명제이다.

논리

논리연산자
부정 ~p 명제 p에 대하여 p의 진릿값을 반대로 갖는 명제를 위와 같이 표기하며 p가 아니다 또는 not p라고 읽는다.
만약 p가 참인 명제일 경우 ~p는 거짓, p가 거짓인 명제일 경우 ~p는 참이다.

논리곱(and): p ∧ q
명제 p, q에 대하여 p와 q가 모두 참일 경우에만 참이고, 그렇지 않을 경우 거짓이 되는 명제이다.

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

논리합(or): p ∨ q
명제 p, q에 대하여 p와 q가 모두 거짓일 경우에만 거짓이고, 그렇지 않을 경우 참이 되는 명제이다.

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

조건명제
조건 명제 p → q
명제 p, q에 대하여 p가 가정이고 q가 결론이 되는 명제이다.
이 때 p이면 q이다 또는 if p, then q 등으로 읽는다.
따라서 조건명제 p → q의 진릿값은 p가 거짓일 경우 항상 참이고 p가 참일 경우 q의 진릿값과 일치한다.

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

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

p	q	조건명제	역	이	대우
		p → q	q → p	~p → ~q	~q → ~p
T	T	T	T	T	T
T	F	F	T	T	F
F	T	T	F	F	T
F	F	T	T	T	T

명제함수와 한정자(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가 하나라도 있을 경우 참이되는 명제이다.