명제와 논리 연산

명제란 ‘참, 거짓을 명확히 판단할 수 있는 문장’을 뜻한다. 예를 들어, ‘지구는 2012년에 멸망한다’는 명제이지만, ‘우리집은 매우 넓다’는 명제가 될 수 없다. 명제에는 단순명제와 합성명제가 있는데, 단순명제는 더이상 나눌 수 없는 긍정형의 명제를 말하고 합성명제는 하나 이상의 단순명제가 연산에 의해서 합쳐진 것을 말한다.

진리표

진리표는 단순명제나 합성명제의 모든 가능성을 나열한 표이다.

Example

이것은 진리표의 한 예인데, 단순명제 p의 가능한 경우의 수를 모두 보여주고 있다. (+) 참고로 T는 True을, F는 False를 뜻한다.

논리 연산

논리 연산은 하나 이상의 명제를 가공하여 또다른 명제를 만들 수 있는 도구이다. 이것은 무수히 많이 만들어 낼 수 있지만 크게 ~(not), ∧(and), ∨(or), →(~하면), ↔(~하면, 그리고 그때에만)가 주로 쓰인다.

~(not)

~(not)은 다음과 같이 정의한다.

Not

이것은 아주 간단하다. 그냥 ~이 붙여진 명제의 진리값의 부정만 취하면 되는 것이다.

∧(and)

∧(and)는 논리곱이라고도 불리며, 이것은 다음과 같이 정의한다.

And

두 명제가 모두 참인 경우에만 두 명제의 논리곱은 참이고 나머지 경우에는 거짓이 된다.

∨(or)

∨(or)은 논리합이라고도 불리며, 이것은 다음과 같이 정의한다.

Or

논리곱과 다르게 두 명제가 모두 거짓일 때에만 논리합이 거짓이고 나머지 경우에는 참이다. 여기까지는 이해하기가 어렵지 않다.

→(~하면)

→라는 연산은 이해하기가 꽤 어려운데, 이것은 우리가 일반적으로 생각하는 ‘~하면 ~이다’와는 의미가 다르다. 일상 생활에서 이런 가정형의 문장을 쓸 때에는 가정이 참이든 거짓이든 이 문장 자체에는 영향을 주지 않는다. 따라서 굳이 가정이 참인 경우와 거짓인 경우를 나눌 필요가 없는 것이다. 예를 들면 ‘내일 비가 오면 축구를 할 것이다’라는 가정형의 문장에서 내일 비가 오지 않을 경우 이 문장이 참인지 거짓인지는 따질 필요가 없다.

하지만 수학자들은 →의 정의를 명확히 하기 위해서 가정과 결론이 참과 거짓인 경우를 모두 따졌고, 그에 따라 이것의 정의를 다음과 같이 정했다.

If

즉, p가 참이면서 q가 거짓인 경우를 제외하고 모두 참이라고 한 것이다. 이것을 다른 말로 하면 p→q를 ~p∨q라고 할 수 있으며, 따라서 ~(p→q)는 p∧~q이다.

이런 정의를 도입하면 증명할 수 있는 것이 무척 많은데, 그중 하나가 ‘공집합은 모든 집합의 부분집합이다’라는 명제이다. 이 명제를 다른 말로 하면 ‘공집합에 속하는 임의의 원소가 x이면 x는 집합 A에 속한다’이다. 이 때, 가정에 해당되는 ‘공집합에 속하는 임의의 원소가 x’가 거짓이므로1 이 명제는 참이 된다.

p→q가 참일 때 이것은 p⇒q라고 표현하며, 이것을 ‘p는 q에 함의된다’라고 말한다.

↔(~하면, 그리고 그때에만)

p↔q는 (p→q)∧(q→p)로 정의한다. 이것을 진리표로 나타내면 다음과 같다.

Only If

p↔q가 참일때 이것을 p⇔q라고 표현하며, ‘p와 q는 동치이다’라고 말하는데, 이것을 p≡q라고 쓰기도 한다.

항진명제와 모순

항진명제는 주어진 명제의 진리표를 그려봤을 때 모두 참이 나오는 경우를 말한다. 예를 들면, p→p는 항진명제로, p가 참이든 거짓이든 참이 나온다. 반대로 모순은 명제의 진리표를 그려봤을 때 모두 거짓이 나오는 경우를 말한다. 예를 들면, p→~p는 p가 참이든 거짓이든 거짓이 되므로 모순이다.

항진명제를 t, 모순을 c라고 하면 t≡~c의 관계가 있다.

  1. 공집합에는 원소가 하나도 없으므로 ‘임의의 원소가 x’라는 말부터 잘못되었다.

4 comments

  1. 이해 가능..
    역시 과학고에서는 어려운걸 배우는구나
    중학교때 공부좀 열심히 해놓을걸..

    근데 T와 F에 대한 설명이 없어서 처음에 무슨말인지 이해못햇었어
    true,false, 라고 표기 부탁드림~

  2. “공집합에 속하는 임의의 원소”가 하나도 없지만 그렇다고 틀린건 아닙니다.

    1. 과고 수학 선생님이 그렇게 가르쳐 주셨는데 그게 아닌가 보네요. 어떻게 증명하는지 찾아봐야 겠어요.

      (+)
      인터넷에서 좀 찾아봤는데 대부분 위의 설명 방식을 취하고 있었습니다. 다른 방법이 있는 것인가요?

      (+)
      공집합이 집합 A의 부분집합이 아니라고 가정하면 집합 A에 포함되지 않는 원소가 공집합에 존재해야 하므로 모순이다.

      라고 증명하는 방법도 있네요.

댓글을 남겨주세요.