이산수학의 기본이 되는 논리, 명제와 명제의 참과 거짓, 그리고 논리 연산 등을 통한 논리적 추론에 대해서 알아보도록 하겠습니다.
이번 주제에서는 수식이 길어 모바일 환경보다는 데스크탑이나 노트북 환경에서 포스팅을 보는 것을 추천합니다.
정의와 명제
새로운 분야를 접할 때 그 분야에서 통용되는 용어의 뜻을 알아야 그 분야에 잘 적응할 수 있어야 합니다. 그 때 잘 알아야 하는 것이 바로 용어의 “정의”입니다.
용어를 정의하는 방법으로는 두 가지가 있습니다. 첫 번째는 “무정의 용어”를 통해 용어를 정의하는 것입니다. 두 번째는 “무정의 용어”나 정의된 다른 용어를 통하여 또 다른 용어를 정의하는 것입니다.
💡 (정의) 무정의 용어 💡
수학적 의미를 가지고 있지 않은 일반적인 용어에 대해 정의하지 않고 사용하는 것
무정의 용어와 정의된 용어를 준비된다면 문장을 만들 수 있습니다. 문장에는 직관적 추론에 의하여 “참 또는 거짓인지를 명확히 구분할 수 있는 문장”(명제)와 그렇지 않은 문장으로 나뉩니다.
💡 (정의) 명제 💡
참 또는 거짓 중 단 하나만 갖는 문장을 말한다. 명제 중 명제의 내용이 참이 되는 명제를 “참 명제”라 하고, 명제의 내용이 거짓이 되는 명제를 “거짓 명제”라고 한다.
💡 (정의) 진리값 💡
참과 거짓을 진리값이라 하며, $\text{T}$(참, 1), $\text{F}$(거짓, 0)으로 표현한다. 명제 $\text{P}$는 $\text{T}$ 또는 $\text{F}$ 중 어느 하나만을 진리값으로 가집니다.
논리 연산
주어진 명제를 합성하여 새로운 명제를 만들게 되는데, 명제를 합성하기 위해서는 논리 연산이나 부울 연산을 진행하게 됩니다. 지금부터 논리 연산에 대해서 알아보도록 하겠습니다.
논리곱 (AND)
💡 (정의) 논리곱 💡
임의의 명제 $\text{P}$와 $\text{Q}$에 대해, 두 명제의 진리값이 모두 참일 경우에만 참이 되고 그렇지 않으면 거짓이 된다. $\text{P} \wedge \text{Q}$로 표기하며, $\text{P AND Q}$ 라고 읽는다.
논리곱 $\text{P} \wedge \text{Q}$의 진리표는 다음과 같습니다.
| P | Q | $\text{P} \wedge \text{Q}$ |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
논리합 (OR)
💡 (정의) 논리합 💡
임의의 명제 $\text{P}$와 $\text{Q}$에 대해, 두 명제의 진리값이 모두 거짓일 경우에만 거짓이 되고 그렇지 않으면 참이 된다. $\text{P} \vee \text{Q}$로 표기하며, $\text{P OR Q}$ 라고 읽는다.
논리합 $\text{P} \vee \text{Q}$의 진리표는 다음과 같습니다.
| P | Q | $\text{P} \vee \text{Q}$ |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
부정 (NOT)
💡 (정의) 부정 💡
임의의 명제 $\text{P}$에 대해, $\text{P}$의 진리값의 반대의 값을 도출한다. $^\neg \text{P}$ 로 표기하며, $\text{negation P, not P}$ 라고 읽는다.
부정 $^\neg \text{P}$ 의 진리표는 다음과 같습니다.
| P | $^\neg \text{P}$ |
| T | F |
| F | T |
배타적 논리합 (XOR)
💡 (정의) 배타적 논리합 💡
임의의 명제 $\text{P}$와 $\text{Q}$에 대해, 두 명제의 진리값 중 어느 하나만 참일 경우에 참이 되고 모두 참이거나 거짓일 경우에는 거짓이 된다. $\text{P} \oplus \text{Q}$로 표기하며, $\text{P exclusive or Q}$ 라고 읽는다.
배타적 논리합 $\text{P} \oplus \text{Q}$의 진리표는 다음과 같습니다.
| P | Q | $\text{P} \oplus \text{Q}$ |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
논리 함축
💡 (정의) 논리 함축 💡
임의의 명제 $\text{P}$와 $\text{Q}$에 대해, 두 명제가 $\rightarrow$로 결합되었을 때를 논리 함축이라고 한다. $\text{P} \rightarrow \text{Q}$로 표기하며, $\text{P implies Q}$ 라고 읽는다. 논리 함축 $\text{P} \rightarrow \text{Q}$에서 $\text{P}$ 를 “가정”이라고 하며 $\text{Q}$ 를 “결론”이라고 한다. $\text{P} \rightarrow \text{Q}$는 “$\text{P}$이면 $\text{Q}$이다”, “$\text{P}$는 $\text{Q}$의 충분조건이다”, “$\text{Q}$는 $\text{P}$의 필요조건이다” 등으로 표현 가능하다.
논리 함축 $\text{P} \rightarrow \text{Q}$의 진리표는 다음과 같습니다.
| P | Q | $\text{P} \rightarrow \text{Q}$ |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
역(Converse), 이(Inverse), 대우(Contrapositive)
💡 (정의) 역 (Converse) 💡
논리 함축 $\text{P} \rightarrow \text{Q}$에 대해, $\text{Q} \rightarrow \text{P}$를 말한다. 즉, 명제의 가정과 결론의 위치를 바꾼 것이다.
💡 (정의) 이 💡
논리 함축 $\text{P} \rightarrow \text{Q}$에 대해, $^\neg\text{P} \rightarrow ^\neg\text{Q}$를 말한다. 즉, 명제의 가정과 결론을 각각 부정으로 만든 것이다.
💡 (정의) 대우 💡
논리 함축 $\text{P} \rightarrow \text{Q}$에 대해, $^\neg\text{Q} \rightarrow ^\neg\text{P}$를 말한다. 즉, 명제의 가정과 결론의 위치를 바꾸고 바뀐 가정과 결론에 부정을 붙인 것이다. 명제가 참이면 반드시 대우도 참이 된다.
논리적 동치
💡 (정의) 논리적 동치 💡
임의의 명제 $\text{P}$와 $\text{Q}$에 대해, 두 명제가 $\Leftrightarrow$로 결합되었을 때를 논리적 동치라고 한다. $\text{P} \Leftrightarrow \text{Q}$로 표기하며, $\text{P logical equivalence Q}$ 라고 읽는다. 논리적 동치 $\text{P} \Leftrightarrow \text{Q}$는 “$\text{P}$는 $\text{Q}$의 필요충분조건이다” 라고 표현 가능하다.
논리적 동치 $\text{P} \Leftrightarrow \text{Q}$의 진리표는 다음과 같습니다.
| P | Q | $\text{P} \Leftrightarrow \text{Q}$ |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
논리 연산자 우선순위
합성 명제가 길어질 경우 가독성이 매우 떨어집니다. 그렇기에 연산자 우선순위를 통하여 식을 정리하는 것이 필요합니다. 논리 연산자들의 우선순위는 다음과 같습니다.
$$ ^\neg \text{ (not)} > \wedge \text{ (and)} > \vee \text{ (or)} > \ (\rightarrow) > (\Leftrightarrow) $$
즉, 부정을 가장 먼저 연산하고, 그 후 논리곱, 논리합, 논리 함축, 마지막으로 논리적 동치를 연산하는 것입니다.
명제의 종류
기본적으로 명제의 종류에는 항진 명제, 모순 명제, 사건 명제 등이 있습니다.
항진 명제
💡 (정의) 항진 명제 💡
항상 참의 진리값을 가지는 명제를 말한다.
모순 명제
💡 (정의) 모순 명제 💡
항상 거짓의 진리값을 가지는 명제를 말한다.
사건 명제
💡 (정의) 사건 명제 💡
항진 명제도, 모순 명제도 아닌 명제를 말한다.
항등
위에서 논리적 동치에 대해서 알아보았습니다. 논리적 동치는 명제 변수 $\text{P, Q}$가 똑같은 진리값을 갖는 것을 말하는 것이었습니다. “항등”이란 논리적으로 동치인 명제를 말하는 것입니다. 항등을 통하여 명제를 간단하게 하는 것이 가능합니다.
명제의 표현
명제를 표현할 때는 간단하게 쉽게 표현하는 것이 좋습니다. 그 이유는 바로 “가독성” 때문입니다. 명제를 간단하고 쉽게 표현하는 개념들에 대해서 알아보겠습니다.
술어
💡 (정의) 술어 💡
한 객체의 성질이나 객체와 객체 사이의 관계를 표현하는 것을 말한다.
정의만 봐서는 술어를 제대로 이해하기가 어렵습니다. 예시를 통해서 알아보도록 하겠습니다.
“$x \text{ is less than 50}$” 이라는 문장이 있을 때, 여기서 $x$는 “변수”라고 합니다. 그리고 $\text{less than 50}$을 “술어”라고 합니다. 이때 술어를 조금 더 특별하게 표현하면 $\text{T}(x)$로 나타낼 수 있는데 $\text{T}$를 술어라고 하고 $x$를 개별 변수라 합니다. 한 문장에 변수가 많아지면 술어는 $\text{P}(x_1, \ x_2, \cdots \ x_n)$으로 나타낼 수 있으며, $\text{P}$는 $n$개의 인수를 가진 술어라고 합니다.
한정자
💡 (정의) 한정자 💡
어떤 명제 변수가 성립하는 범위를 한정하는데 사용하는 것을 말하며, 한정자에는 전체 한정자, 존재 한정자, 유일 한정자가 있다.
- 전체 한정자: 기호 $\forall$로 나타내고 “모든”, “임의의” 라고 읽는다. “임의의 $x, \text{P}(x)$”는 “$x$의 모든 값들에 대해 명제 $\text{P}(x)$는 참이다”라고 해석한다.
- 존재 한정자: 기호 $\exists$로 나타내고 “어떤”, “적어도 하나에 대해” 라고 읽는다. “어떤 $x, \text{P}(x)$”는 “명제 $\text{P}(x)$가 참이 되는 $x$의 값이 존재한다”라고 해석한다.
- 유일 한정자: 기호 $\exists !$로 나타내고 “~에 대한 유일한 $x$가 존재한다” 라고 읽는다. “$\exists !$ $x, \text{P}(x)$”는 “명제 $\text{P}(x)$가 참이 되는 $x$의 값이 유일하게 존재한다”라고 해석한다.
수식어
💡 (정의) 수식어 💡
수식하는 단어를 사용하여 이름을 구별하는 것을 말한다. 즉, 정보를 덧붙여 같은 이름을 구별하는 것이다.
논리적 추론
지금까지 명제를 배운 이유는 바로 논리적 추론을 하기 위함입니다. 논리적 추론은 인간의 추론 방법 가운데 가장 연구가 많이 진행되었습니다.
💡 (정의) 논리적 추론 💡
어떤 명제가 참인 것을 근거로 하여 다른 명제가 참인 것을 유도해내는 것을 말한다. 근거가 되는 명제를 “가정” 또는 “전제”라고 하며, 유도되는 명제를 “결론”이라고 한다.
논리적 추론을 할 때 가장 기본이 되는 법칙은 바로 “대체”입니다. 어떤 표현을 그것과 완전히 같은 의미를 가진 다른 표현으로 나타내는 것을 말합니다. 그리고 항상 참의 값을 가지는 항진 명제를 이용하여 논리적 추론을 하는 방식도 많습니다. 다음은 항진 명제의 형태를 이용하여 추론하는 방법들입니다.
참고자료 (래퍼런스)
https://namu.wiki/w/%EB%85%BC%EB%A6%AC%20%EC%97%B0%EC%82%B0
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=hihoyeho&logNo=140127993860
https://shu07002.tistory.com/7
