1.1. 연역 추론과 논리 연산

연역 추론은 증명의 기본. 연역 추론의 대표적인 예시는 삼단 논법. 두 개의 전제와 하나의 결론으로 구성됨. 기본적으로 결론이 만약 거짓이라면 전제 중 하나는 반드시 거짓이어야 함. 예를 들어보자:

a) 오늘이나 내일 출근을 할 것이다
b) 오늘은 집에 있을 것이다
c) 그러므로 내일 일을 할 것이다

여기서 만약 b) 전제가 잘못됐다면, 즉 만약 오늘 출근을 했었다면 내일 출근을 반드시 할 거란 보장이 없다. 내일 출근을 하지 않더라도 전제 a)가 참이기 때문이다. 반대로 두 전제가 참이라면 결론도 참일 것이다.

만약 결론이 참이 아닌데 전제가 둘 중 하나라도 참이 아닌 경우가 있다면, 그 주장(위의 abc 같은 주장)은 유효하지 않은 주장이다. 예를 들어보자:

a) 철수나 영희 둘 중 적어도 한 명은 잘못을 했다
b) 영희나 길동 둘 중 적어도 한 명은 잘못을 했다
c) 그러므로 철수나 길동 둘 중 적어도 한 명은 잘못을 했다

위의 주장은 유효하지 않다. 전제가 둘 다 참이더라도 결론이 잘못될 수 있기 때문이다. 만약 영희가 잘못한 사람이었다면 a)도 참, b)도 참이지만 c)는 거짓이다.

기본적으로 간단하게 유효한 주장을 하는 방법은 다음과 같다:

P 혹은 Q 중 적어도 하나는 참이다
Q는 아니다
그러므로 P이다

법을 다룰 때나 논쟁을 할 때는 말로 해도 충분하지만, 수학하는 사람들은 귀차니즘으로 가득찬 사람들이기 때문에 말로 전부 표현하기 싫어한다. 그래서 위의 예시처럼 적당히 P나 Q로 명제들을 퉁칠 수 있다. 뿐만 아니라 자주 사용하는 논리적 용어들을 수학적 기호로 퉁칠 수 있다. 예를 들어:

“P랑 Q 둘 다 참이어야 한다” -> P∧Q is true (플밍에선 && 혹은 &)
“P랑 Q 중 적어도 하나는 참이다” -> P∨Q is true (플밍에선 || 혹은 |)
“P는 아니다” -> ¬P (플밍에선 ! 혹은 ~)

위의 세 명제들을 순서대로 “논리곱”, “논리합”, “부정”으로 표현한다.

1.2. 진리표

어떤 주장을 듣고 이 주장의 유효성을 판단하고 싶거나 모든 경우의 수를 보고 싶을 때 쓸 수 있는 방법 중 가장 단순 무식한 방법은 표를 그리는 것이다:

P = 철수는 잘 생겼다
Q = 철수는 돈이 많다
P∧Q = 그러므로 철수는 잘 생겼고 돈도 많다

P Q P∧Q
거짓 거짓 거짓
거짓 참 거짓
참 거짓 거짓
참 참 참

위의 표에서 보는 것처럼 전제가 전부 참일 때 결론도 참이므로 유효한 주장이라고 볼 수 있다. 하지만 이 세상엔 항상 유효한 주장만 있는 건 아니다 (뉴스나 인터넷만 봐도 이상한 놈들 천지니까!!!) 그러므로 전제가 참이라고 해서 결론이 항상 참인지는 모른다. 그래서 가짜 뉴스 조심해야한다. 가짜 뉴스만 보면 전제가 전부 참이니까 결론이 참이라고 착각하기 쉽다. 주장 자체가 유효한지도 검증해야한다.

진리표를 사용하면 논리학에서 사용하는 논리 연산자들의 여러 속성들을 알아 볼 수 있다:

드모르간 법칙:
¬(P∧Q) == ¬P∨¬Q
¬(P∨Q) == ¬P∧¬Q

교환 법칙:
P∧Q == Q∧P
P∨Q == Q∨P

결합 법칙:
P∧(Q∧R) == (P∧Q)∧R
P∨(Q∨R) == (P∨Q)∨R

멱등 법칙:
P∧P == P
P∨P == P

분배 법칙:
P∧(Q∨R) == (P∧Q)∨(P∧R)
P∨(Q∧R) == (P∨Q)∧(P∧R)

흡수 법칙:
P∨(P∧Q) == P
P∧(P∨Q) == P

이중 부정 법칙:
¬¬P == P

이때 P∨¬P 처럼 항상 참인 명제를 항진명제라 부르고, 반대로 항상 거짓인 명제는 모순이라 부른다.

항진 법칙:
P∧(항진명제) == P
P∨(항진명제) == 항진명제
¬(항진명제) == 모순

모순 법칙:
P∧(모순) == 모순
P∨(모순) == P
¬(모순) == 항진명제

1.3. 변수와 집합

뭔가 명제를 말할 때 그걸 문장으로 쓰기 귀찮을 땐 P와 같은 변수를 쓸 수 있다. 심지어 어떤 명제 안에 또 변수가 있을 수도 있다. 예를 들어 “어떤 사람이 학생이다”라는 명제에서 어떤 사람을 x로 대체하고, 전체 명제는 P(x)로 대체할 수 있다. 이때 P(x)를 참으로 만드는 모든 x의 집합을 진리 집합이라 부른다.

집합이라는 건 기본적으로 어떤 한 객체의 모음이라는 뜻이고, 이 객체들을 수학에서는 원소라 부른다. 한 원소 x가 어떤 집합 A에 속한다를 수학에서는 간단하게 x ∈ A로 표기한다. 반대는 중간에 선 그어서 x ∉ A로 쓴다. 위의 표기법을 활용해서 간단하게 명제를 집합으로 표현하면:

P = { x | x는 학생이다 }

여기서 우측에 있는 조건을 원소 판별이라 부른다.

우리가 “어떤 y가 x는 학생이다는 집합에 속한다”라는 명제를 변수와 집합으로 표현해보자:

y ∈ { x | x는 학생이다 }

여기서 실제로 의미가 있는 변수는 y다. 우리가 궁금한 건 특정한 y니까. x는 사실 별 상관 없다. 그냥 의미 전달을 위해 있는 거다. 이때 y를 자유 변수라고 하고, x를 묶인 변수 혹은 형식 변수라고 한다. 그렇기 때문에 {x | …. }라는 표기법은 변수 x와 묶여있다고 한다.

구체적으로 사실 살펴보면 “그래서 어떤 y가 도대체 뭔데? 사람이라는거야? 한국인만? 어른만?” 등의 전제에 대한 질문이 들 수 있다. 이런 것처럼 어떤 명제를 다룰 땐 전제에 대응하는 배경 맥락을 필요로 한다. 이런 것처럼 어떤 한 변수가 속해 있는 전체 집합을 논의 영역이라 부르고, 보통 U로 표현한다. 이때 변수들은 이 영역을 범주로 한다고 표현한다. 이 부분까지 명시적으로 표현해보면:

P = { x ∈ U | x는 학생이다 }

위와 같이 표현한다.

처음에 어떤 사람을 x로 바꾸기로 했으니, 이 명제의 논의 영역은 모든 사람을 포함하는 집합 U가 될 것이다. 이제 위의 “어떤 y가 x는 학생이다는 집합에 속한다”를 다시 수학적으로 표현해보면:

y ∈ { x ∈ U | x는 학생이다 }

가 되고, 이를 집합으로 표현하자면

y ∈ x ∈ U ∧ x는 학생이다

가 된다.

중학교에서 집합을 배웠다면 이미 알고 있겠지만, 원소가 아무 것도 없는 집합을 공집합이라 부르고 Ø로 표기한다. 즉, Ø = {}이다.

1.4. 집합 연산

두 집합이 접하는 부분을 수학에선 교집합이라 부르고 A∩B로 표기한다.

정의: A∩B = { x | x ∈ A 그리고 x ∈ B }

두 집합을 합친 전체를 수학에서는 합집합이라 부르고 A∪B로 표기한다.

정의: A∩B = { x | x ∈ A 혹은 x ∈ B }

한 집합에서 나머지 한 집합의 원소들을 제거한 부분을 수학에서는 차집합이라 부르고 A \ B로 표기한다.

정의: A∩B = { x | x ∈ A 그리고 x ∉ B }

사실 보통 집합을 다룰 때는 수식보다는 벤 다이어그램으로 그리는 게 직관적이다. 물론 다룰 집합의 수가 넷 이상이면 벤 다이어그램을 쓸 수 없지만, 보통 그럴 일은 거의 없으니 벤 다이어그램을 애용하면 이해하기 편하다.

예를 들어 “치즈를 좋아하는 집합 C”와 “마라를 좋아하는 집합 M”이 있을 때, 둘 중 딱 하나만 좋아하는 집합을 구해보자. 이걸 수식으로 하면:

(C ∪ B) \ (C ∩ B)

가 된다. 근데 벤 다이어그램으로 그리면 그냥 그믐달이랑 초승달 두 개가 붙어 있는 형태로 바로 그림 그려주면 끝이다. 참고로 위와 같은 집합을 대칭 차집합이라 부르고, A 2 B라고 표기한다.

벤 다이어그램으로 어떤 한 명제의 진리 집합 P를 그려보면, ¬P의 영역은 전체에서 동그라미 하나 파 먹은 형태가 된다. 즉, 전체 U에 집합 P를 뺀 형태가 되므로, ¬P = U \ P로 표기할 수 있다.

이렇듯 집합론의 연산이 논리 연산과 똑같이 가는 것처럼 보이지만, 둘이 동치인 건 아니다. 논리 연산은 명제에만 쓸 수 있고, 집합 연산은 집합에만 쓸 수 있는 것이다.

집합 내부에는 그 집합의 부분을 이루는 부분 집합이 있을 수 있다. 경희대학교 안에는 외국어대학이라는 부분 집합이 있듯이 말이다.

어떤 집합 A의 모든 원소가 다른 집합 B에 전부 포함될 때 A를 B의 부분 집합이라고 부르고, A ⊆ B로 표기한다. 반대로 만약 두 집합 A와 B가 서로 아예 공통의 원소가 없을 경우 서로소 집합이라 부른다. 즉 A ∩ B = Ø인 것이다. 참고로 그 어떠한 임의의 집합 A와 B가 주어지든 우리는 서로소 집합을 만들어 낼 수 있다. 바로 ( A ∩ B ) ∩ (A \ B) = Ø 이다. 반대로 무조건 부분 집합인 경우 ( A ∪ B ) \ B ⊆ A가 있다.

1.5. 조건 및 동치 연산

“만약 A라면 B다.”처럼 조건이 존재하는 명제를 표현할 땐 조건 연산자 ⇒를 사용하여 A ⇒ B로 표기한다. 이때 A를 선행 사건이라 부르고 B를 결과 사건이라 부른다. 이것이 명제라는 것은 참과 거짓을 가를 수 있다는 것이다. 즉 진리표를 작성할 수 있다. 근데 이게 조건 명제가 젤 골때리는 부분이다. 예를 들어보자:

A: 수능에서 모든 과목에서 1등급을 받았다
B: 의대에 합격한다.

위의 두 명제가 있다고 가정해보자. 그렇다면 A ⇒ B는 “수능에서 모든 과목에서 1등급을 받는다면 의대에 합격한다”라는 명제가 된다. 만약 A와 B 둘 다 참이라면 A ⇒ B도 참인 명제다. 너무나도 당연하다. 반대로 만약 수능 점수는 받았는데 의대에 떨어졌다면 결론인 A ⇒ B가 개소리라는 거니까 거짓이 된다

문제는 여기서부터다. 만약 전제가 거짓이라면? 만약 수능을 1등급을 못 받았다면? 그럼 애초에 의대에 합격하니 마니에 대한 논의를 할 의미가 없다. 전제가 글러 먹었는데. 그래서 이 경우에는 조건 명제 A ⇒ B가 참일까 거짓일까? 인간의 논리로 생각해보면 사실 말이 안된다. 전제가 글러 먹었으니 수능에서 1등급 받는다고 의대 갈지 말지를 알 수가 없기 때문이다. 하지만 수학에서는 두 경우 다 참이라고 판단한다!!!!!! 이걸 나름대로 이해해보려고 했는데, 나름대로 떠오른 방법은 다음과 같다:

판단하려는 건 “수능에서 모든 과목에서 1등급을 받는다면 의대에 합격한다”라는 명제가 참인지 거짓인지를 판별하는 거다. 당연히 둘 다 참이면 명제가 참인거고 1등급 다 받았는데도 의대 못 가는 케이스가 있으면 글러 먹은(거짓인)거다. 근데 만약 전제에서 애초에 글러 먹었으면 이 명제 자체가 동작할 수가 없다. 즉 참거짓을 판별할 수가 없다. 그 의미는 이 명제가 참임을 존중해야 한다는 뜻이다

누군가가 “수능에서 모든 과목에서 1등급을 받는다면 의대에 합격한다”라는 명제가 틀렸음을 증명한다고 가정해보자. 그러면 수능에서 모든 과목에서 1등급 맞았는데도 의대 불합격한 사람을 찾지, 애초에 성적 안 되는 사람을 찾지도 않는다. 그 사람 데려온다고 해서 이 명제가 거짓인 걸 어떻게 증명할 것인가? 그렇기 때문에 참으로 판별하는 것이다.

이렇게 되면 A ⇒ B은 ¬A ∨ B와 같은 명제가 된다. 이걸 인간의 언어로 표현해보자: “인생은 의대로 결정되는거야~ 수능에서 모든 과목에서 1등급을 못 맞았든가, 의대에 합격했든가 둘 중 하나라고~ 전자면 걍 재수해라~”. 즉, “수능에서 모든 과목에서 1등급을 받는다면 의대에 합격한다”라는 명제랑 같은 얘기다. 둘이 같다는 법칙을 조건 법칙이라 부른다.

이때 위의 명제 순서를 바꿔서 말하면 완전 다른 말이 된다. “의대에 합격했다면 수능에서 모든 과목에서 1등급을 받은 것이다.” 보통 사람들 일상 대화헤서는 이것도 참이라고 말할 때가 있지만, 그건 일상 대화 얘기고, 논리적으로 보면 완전 다른 얘기다. 국영수 전부 100점 맞고 과탐 하나 2등급일 수도 있지. 이처럼 두 명제의 순서를 바꾼 조건 명제를 역이라 부른다. 원래 조건 명제랑 같은 다른 조건 명제는 “수능에서 모든 과목에서 1등급을 받지 못했다면 의대에 불합격한다.”로, 대우라고 부른다.

우리가 보통 사람의 언어로 조건 명제를 표현할 땐 “A는 곧 B를 의미한다”, “A면 B다.” “B일 때만 A다”, “A는 B의 충분 조건이다.”, “B는 A의 필요 조건이다.” 등으로 표현한다.

만약 어떤 논리 명제가 그 역과 동일하다면 A ⇔ B로 표기하고 동치 명제라고 부른다. 말로는 “A인 경우 오직 그 경우에만 B이다”라고는 하는데, 그냥 A iff B로 표기한다. 좀 더 수학적인 한국말로는 “A는 B의 필요충분조건이다”라고 한다.