참 또는 거짓 중 하나의 값만을 갖는 수학적 문장을 명제라고 부른다. 고등학교 과정에서 공부했던 방식대로 명제의 성질에 대하여 논할 때는 보통 명제를 , , , ⋯와 같은 알파벳으로 나타낸다.
명제 에 대하여 ‘가 아니다’를 의 부정이라고 부르고 ∼ 로 나타낸다. 즉 가 참일 때 ∼ 는 거짓이며,
가 거짓일 때 ∼ 는 참이다. [∼는 보통 ‘not p’라고 읽는다.]
둘 이상의 명제를 결합하여 새로운 명제를 만들 수 있다. 두 명제 , 에 대하여 ‘와 가 모두 참이다’를 와 의 논리곱이라고 부르며 ∧ 로 나타내고 ‘ 그리고 ’라고 읽는다. 그리고 ‘ 또는 중 하나 이상이 참이다’를 와 의 논리합이라고 부르며 ∨ 로 나타내고 ‘ 또는 ’라고 읽는다.
보기
1.1.1 ‘는 홀수이다’를 로 나타내고 ‘는 소수이다’를 로 나타내면 ∧ 는 ‘는 홀수인 소수
이다’가 되고 ∨ 는 ‘는 홀수이거나 소수이다’가 된다. 한편 ‘는 홀수이지만 소수가 아니다’를 논리 기호로 나타내면 ∧ ∼ 이다. □
01 수학의 논리와 집합
13
1.1 명제와 조건
문장에 따라서 그 자체로는 참, 거짓이 판별되지 않지만 변수에 값을 대입했을 때 참, 거짓이 판별되는 경우도 있다. 예를 들어 ‘는 짝수이다’는 의 값에 따라 참이 되기도 하고 거짓이 되기도 한다. 이러한 문장을 명제 함수 또는 조건이라고 부른다. 명제함수의 변수를 강조할 때에는 , , , ⋯와 같이 나타내기도 하고, 변수를 강조할 필요가 없을 때에는 명제와 같이 , , , ⋯로 나타내기도 한다.
명제 ‘가 참일 때마다 도 참이 된다’를 조건문 또는 함의라고 부르고 → 로 나타내며 ‘이면 이다’라고 읽는다. 이것을 ‘는 를 함의한다’라고 읽기도 한다.
보기
1.1.2 ‘∆ABC는 이등변삼각형이다’를 로 나타내고 ‘∆ABC의 두 각의 크기가 같다’를 로 나타내
면 → 는 ‘∆ABC가 이등변삼각형이면 ∆ABC의 두 각의 크기가 같다’가 된다. 물론 이것을 ‘이등변삼각형은 두 각의 크기가 같다’로 더 간단하게 표현할 수도 있다. □
논리곱, 논리합, 조건문은 다음과 같이 진리표(truth table)로 나타낼 수 있다.
∧ ∨ →
T T T T T
T F F T F
F T F T T
F F F F T
진리표에서 T는 참(true)을 나타내고 F는 거짓(false)을 나타낸다.
명제함수 가 주어졌을 때 에 대입할 수 있는 값들의 모임을 의 대상영역이라고 부른다. 명제함수
의 대상영역
에서 가 참이 되도록 하는 로 이루어진 집합을 의 진리집합이라고 부르고∈
로 나타낸다. 집합을 이와 같은 꼴로 나타내는 방법을 조건제시법이라고 부른다. 집합을 조건제시법으로 나타낼 때 대상영역이 명확하여 혼동할 염려가 없으면 와 같이 나타내기도 한다. 한편
⋯
와 같이 원소를 일렬로 나열하는 방법으로 집합을 나타낼 수도 있는데 이러한 방법을 원소나열법이라고 부른다.
원소나열법은 원소의 규칙이 명확하여 혼동될 염려가 없을 때에만 사용한다.
‘대상영역
의 모든 원소 에 대하여 이다’라는 명제를∀∈
(1)로 나타낸다. 이 명제를 전칭명제라고 부르고 ∀를 전칭기호라고 부른다. ‘
의 원소 중에서 인 것이 하나 이상 존재한다’라는 명제를∃∈
(2)로 나타낸다. 이 명제를 존재명제라고 부르고 ∃를 존재기호라고 부른다. 전칭명제와 존재명제를 통틀어 한정명 제라고 부르고 전칭기호와 존재기호를 통틀어 한정기호라고 부른다.
참고로 전칭명제와 존재명제는 진리집합을 이용하여 정의할 수도 있다. 대상영역이
인 명제 의 진리집합을
라고 하자. 이때 (1)이 성립할 필요충분조건은
가
를 포함하는 것이다. 또한 (2)가 성립할 필요충분조건 은
∩
≠ ∅인 것이다.보기
1.1.3 소수인 자연수들의 집합
를 대상영역으로 하는 두 명제함수 와 가 ≡‘는 홀수이다’, ≡‘는 보다 크다’
라고 정의되었다고 하자. 이때 와 에 대한 한정명제는 각각 다음과 같다.
한정명제 의미
∀∈
모든 소수는 홀수이다. (거짓)∃∈
홀수인 소수가 존재한다. (참)∀∈
모든 소수는 보다 크다. (참)∃∈
보다 큰 소수가 존재한다. (참) □대상 영역이 동일한 두 명제함수 , 에 대하여 → 도 명제함수가 된다. 대상 영역
의 모든 원소에 대하여 이 명제함수가 참인 것, 즉 ∀∈
→ 가 참인 것을 ⇒ 로 나타낸다.이때 를 이기 위한 충분조건이라고 부르며 를 이기 위한 필요조건이라고 부른다. ⇒ 이면서 동시에
⇒ 인 것을 ⇔ 로 나타내며, ‘와 는 서로 필요충분조건이다’라고 말한다.
기호 ≡ 는 와 가 완전히 동일한 명제 또는 명제함수라는 것을 의미한다. 또한 ⇔ 는 와 의 진리 여부가 서로 같다는 것을 의미한다. ⇔는 주로 두 명제 또는 명제함수의 관계를 나타낼 때 사용되고 ≡는 주 로 정의할 때에 사용된다. 책에 따라서는 ⇔를 길게 ⇐⇒로 나타내기도 한다.
한편 대수학이나 해석학에서 ≡는 두 식이 항등적으로 동일한 값을 가진다는 의미로 사용되기도 한다. 예를 들 어 와 가 함수일 때
≡ 는
‘대상 영역의 모든 에 대하여 가 성립한다’
를 의미한다.
보기
1.1.4 자연수 전체 집합 ℕ을 대상영역으로 하는 두 명제함수 와 가 각각
≡‘은 홀수이다’, ≡‘은 홀수이다’
라고 정의되었다고 하자. 이때
‘임의의 자연수 에 대하여, 이 홀수일 때마다 도 홀수가 된다’
는 참이다. 즉
∀∈ℕ →
이 참이므로 ⇒ 이라고 쓸 수 있다. 같은 방법으로 ⇒ 이라고도 쓸 수 있다. 따라서 와
는 서로 필요충분조건이다. □
정의할 때 나 ≡를 사용하면 어느 쪽이 정의하는 문장이고 어느 쪽이 정의되는 용어인지 혼동되는 경우가 있다. 이때에는 ≔를 사용한다. 즉 ≔ 는 ‘를 로서 정의한다’는 의미이다. 이때 는 이미 정의되어 알고 있는 용어로 구성된 문장이며 는 새롭게 도입되는 기호이다. 기호 ≔는 정의하는 문장과 정의되는 기호의 관 계를 명확히 구분할 수 있게 해준다.
15
1.1 명제와 조건
명제 또는 명제함수 , 에 대하여 다음과 같이 정의한다.
∙ → 의 역 : →
∙ → 의 이 : ∼ → ∼
∙ → 의 대우 : ∼ → ∼
참고로 명제 → 에서 를 가정, 를 결론이라고 부른다.
보기
1.1.5 대상영역이 삼각형의 집합인 두 명제함수 와 가 각각
≡‘는 이등변삼각형이다’, ≡‘는 정삼각형이다’
라고 정의되었다고 하자. 이때 조건문 → 와 그 역, 이, 대우는 각각 다음과 같다.
∙ → : 이등변삼각형은 정삼각형이다. (거짓)
∙ → : 정삼각형은 이등변삼각형이다. ( → 의 역, 참)
∙ ∼ → ∼ : 이등변삼각형이 아니면 정삼각형이 아니다. ( → 의 이, 참)
∙ ∼ → ∼ : 정삼각형이 아니면 이등변삼각형이 아니다. ( → 의 대우, 거짓) □
명제와 그 대우의 참 거짓 여부는 항상 동일하다. 이와 같이 참, 거짓 여부가 서로 동일할 때 ‘두 명제는 동치 이다’ 또는 ‘두 명제는 동등하다’라고 말한다. 두 명제 , 가 동치인 것을 ⇔ 로 나타내기도 하고 ≡ 로 나타내기도 한다.
명제 , , 에 대하여 다음과 같은 추이법칙(transitive rule)이 성립한다.
→ ∧ → ⇒ →
추이법칙은 이미 정당성이 인정된 사실을 이용하여 새로운 사실을 증명할 때 사용한다. 즉 추이법칙을 이용하 면 두 명제 → 와 → 를 이용하여 → 가 성립함을 증명할 수 있다.
다음으로 여러 가지 명제의 부정법칙을 살펴보자. 먼저 명제 , 에 대하여 다음과 같은 드모르간(De Morgan)의 법칙이 성립한다.
∼ ∧ ⇔ ∼ ∨ ∼ ,
∼ ∨ ⇔ ∼ ∧ ∼ .
드모르간의 법칙을 여러 개의 명제에 적용하면 다음과 같다.
∼ ∧ ∧ ∧ ⋯ ∧
⇔
∼ ∨ ∼ ∨ ∼ ∨ ⋯ ∨ ∼
,
∼ ∨ ∨ ∨ ⋯ ∨
⇔
∼ ∧ ∼ ∧ ∼ ∧ ⋯ ∧ ∼
. 이것은 차례대로 다음과 같이 표현할 수 있다.∼ , , , ⋯, 이 모두 참이다 ⇔ , , , ⋯, 중 거짓인 것이 존재한다,
∼ , , , ⋯, 중 참인 것이 존재한다 ⇔ , , , ⋯, 이 모두 거짓이다.
따라서 드모르간의 법칙을 일반화하여 다음과 같은 한정명제의 부정법칙을 얻을 수 있다.
∼ ∀∈
⇔ ∃∈
∼ ,∼ ∃∈
⇔ ∀∈
∼ .즉 한정명제의 부정법칙은 드모르간의 법칙을 일반화한 것이다.
보기
1.1.6 모든 각
(angle)의 집합
를 대상영역으로 하는 명제 가 ≡‘는 작도 가능하다’
라고 정의되었다고 하자. 이때 전칭명제 ∀∈
는 ‘임의의 각은 작도 가능하다’가 되며, 그 부정은∃∈
∼ 로서 ‘작도 불가능한 각이 존재한다’가 된다. □보기
1.1.7 앞의 보기 1.1.4에서 대상영역이 ℕ이 아니면 와 는 서로 필요충분조건이 아닐 수도 있다. 예
를 들어 대상영역이 실수 집합 ℝ이면 인 경우 은 홀수이지만 은 홀수가 아니다. 즉
∃∈ℝ ∧ ∼
이 참이다. 그런데 이 명제는 ∀∈ℝ → 의 부정과 동일하므로 는 의 충분조건이 아니다.
즉 대상영역이 ℝ일 때 와 는 서로 필요충분조건이 아니다. □
한정명제가 두 개 이상 겹쳐있는 경우를 살펴보자.
보기
1.1.8 명제함수 가 ≡ ‘는 의 배수이다’라고 정의되어 있고, 와 의 범위가 자연수 집합
ℕ이라고 하자. ∀∈ℕ ∃∈ℕ 는 ‘각 자연수 에 대하여 의 배수 가 하나 이상씩 존재한 다’가 된다. 이 명제는 참이다. 반면에 ∃∈ℕ ∀∈ℕ 는 ‘어떤 자연수 가 모든 자연수 의 배수이다’가 된다. 하나의 자연수가 모든 자연수의 배수가 될 수는 없으므로 이 명제는 거짓이다. □위 보기에서 보다시피 한정기호의 순서가 바뀌면 명제의 의미가 달라진다.
보기
1.1.9
명제 ∀∈ℝ ∃∈ℂ 은 직관적으로 ‘각 실수 에 대하여 을 만족시키는 복 소수 가 존재한다’라는 의미를 가지고 있다. 이 명제는 참이다. 이 명제의 부정을 구하면
∼
∀∈ℝ ∃∈ℂ
⇔
∼ ∀∈ℝ ∃∈ℂ
⇔
∃∈ℝ ∼ ∃∈ℂ
⇔
∃∈ℝ ∀∈ℂ ∼
⇔
∃∈ℝ ∀∈ℂ ≠
⇔
∃∈ℝ ∀∈ℂ ≠
이다. 이 명제의 의미는 ‘실수 중에는 복소수 를 제곱해서 만들 수 없는 것도 있다’이다. 이 명제는 거짓이
다. □
대상영역이 같은 두 전칭기호나 두 존재기호가 연달아 나타난 경우 이것을 하나로 줄여 간단히 나타내기도 한 다. 예를 들어
∀∈
∀∈
를 줄여서 간단히 ∀ ∈
로,∃∈
∃∈
를 줄여서 간단히 ∃ ∈
로나타낼 수 있다. 그러나 ∀∈