논리와 명제

논리적이라는 것은 주어진 문제를 객관적으로 명확하게, 그리고 사고의 법칙을 체계적으로 추구하여 분석하는지의 여부로 결정된다. 논리의 중요한 목적 중 하나는 특정 논리를 통한 입증이 옳은가를 측정하는데 필요한 법칙을 제공한다는 것이다.

지금도 활발하게 진행되고 있는 논리에 대한 연구와 응용은 다른 연구 분야와 더불어 컴퓨터 관련 학문이나 공학 등 여러 분야에 폭넓게 응용되고 있다. 예를 들어, 알고리즘의 설계나 증명, 디지털 논리 회로의 설계, 논리 프로그램 관련 분야, 관계형 데이터베이스 이론, 오토마타와 계산 이론, 인공지능 등에 필요한 이론적 기반을 제공하고 있다.

명제 논리

---

명제(Proposition)란 논리적으로 참과 거짓이 분명한 문장이다. 명제 논리(Propositional logic)는 논리학의 한 분야로, 명제와 명제 사이의 관계 그리고 이것들을 기반으로 하는 논증을 다룬다. 합성 명제(Compound proposition)은 단순 명제(Simple proposition)들을 논리 접속사로 연결함으로써 만들 수 있다. 논리 접속사(Logical connectives)는 일상 언어에서 찾을 수 있는데, 그 예시로 ‘그리고(and)’, ‘또는(or)’, 부정(not), 그리고 ‘만약(if)’을 들 수 있다.

다음은 논리에서 간단한 추론의 예시이다.

전제1 : 비가 오면 흐리다.
전제2 : 비가 온다.
결론 : 흐리다.

이 추론의 개별 명제를 기호로 치환하여 나타내면 다음과 같다.

전제1 : P -> Q
전제2 : P
결론 : Q

공리(Axiom)와 추론 법칙의 시스템은 어떤 공식(Fomula)을 이끌어 낼 수 있고, 이 유도된 공식들은 참인 명제가 되며 정리(Theorem)라고 불린다.

논리 연산자

---

연산자	기호	의미
부정(Negation)	~, ¬	NOT
논리곱(Conjunction)	∧	AND
논리합(Disjunction)	∨	OR
배타적 논리합(Exclusive disjunction)	⊕	XOR
조건(Conditional)	→	If/then
쌍방 조건(Biconditional)	↔	If and only if

<hr/>

부정(Negation) : 임의의 명제 P가 주어졌을 때, 그 명제에 대한 부정은 명제 P의 반대되는 진릿값을 가진다.

P의 부정은 ~P라고 표기하며, NOT P 또는 P가 아니다라고 읽는다.

P	~P
T	F
F	T

---

논리곱(conjunction) : 임의의 두 명제 P, Q가 AND로 연결되어 있을 때, 두 명제의 논리곱은 두 명제가 모두 참인 경우에만 참의 진릿값을 가지고, 그렇지 않으면 거짓의 진릿값을 가진다.

P, Q의 논리곱은 P ∧ Q라고 표기하며, P AND Q 또는 P 그리고 Q라고 읽는다.

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

---

논리합(Disjunction) : 임의의 두 명제 P, Q가 OR로 연결되어 있을 때, 두 명제의 논리합은 두 명제가 모두 거짓인 경우에만 거짓의 진릿값을 가지고, 그렇지 않으면 참의 진릿값을 가진다.

P, Q의 논리합은 P ∨ Q라고 표기하며, P OR Q 또는 P 또는 Q라고 읽는다.

P	Q	P ∨ Q
T	T	T
T	F	T
F	T	T
F	F	F

---

배타적 논리합(Exclusive OR) : 임의의 두 명제 P, Q가 XOR로 연결되어 있을 때, 두 명제의 배타적 논리합은 각각의 두 명제의 진릿값이 같은 경우 참의 진릿값을 가지고, 다른 경우 거짓의 진릿값을 가진다.

P, Q의 배타적 논리합은 P ⊕ Q라고 표기하며, P Exclusive OR Q 또는 P XOR Q라고 읽는다.

P	Q	P ⊕ Q
T	T	F
T	F	T
F	T	T
F	F	F

---

조건(Conditional) : 임의의 두 명제 P, Q에 대해 P 이면 Q 일 때, P → Q라고 표기하며, If P, then Q 또는 P 이면 Q이다라고 읽는다. 이는 아래 표현과 동치이다.

- P는 Q를 함축한다. (P implies Q)

- P는 Q의 충분조건이다. (P is sufficient for Q)

- Q는 P의 필요조건이다. (Q is necessary for P)

두 명제 P, Q에 대해 P → Q는 P의 진릿값이 참이고 Q의 진릿값이 거짓일 때만 거짓의 진릿값을 가지고, 그렇지 않으면 참의 진릿값을 가진다.

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

---

쌍방 조건(Biconditional) - 임의의 두 명제 P, Q에 대해 P 이면 Q이고 Q 이면 P 일 때, P ↔ Q라고 표기하며, P if and only if Q 또는 P 이면 Q이고, Q 이면 P이다라고 읽는다. 이는 아래 표현과 동치이다.

- P는 Q의 필요충분조건이다. (P is necessary and sufficient for Q)

두 명제 P, Q에 대해 P ↔ Q는 P, Q의 진릿값이 모두 참이거나 거짓일 때 참의 진릿값을 가지고, 그렇지 않으면 거짓의 진릿값을 가진다.

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	F

---

합성 명제를 구성할 때 여러 논리 연산자가 사용될 수 있으며, 이때 연산자 우선순위는 다음과 같다.

연산자	우선순위
~	1
∧	2
∨	3
→	4
↔	5

명제의 상호 관계

---

명제 P → Q에 대해

Q → P	역(Converse)
~P → ~Q	이(Inverse)
~Q → ~P	대우(Contrapositive)

라고 하며 다음과 같은 관계가 성립한다.

- 명제와 그의 대우는 논리적 동치 관계이다.

- 역과 이는 서로 대우 관계이다.

- 그 이외에는 논리적 동치 관계가 존재하지 않는다.

항진 명제와 모순 명제

---

항진 명제(Tautology)란 합성 명제에서 그 명제를 구성하는 단순명제들의 진릿값에 관계없이 그 합성명제의 진릿값이 항상 참인 명제를 의미한다.

모순 명제(Contradiction)란 합성 명제에서 그 명제를 구성하는 단순 명제들의 진릿값에 관계없이 그 합성 명제의 진릿값이 항상 거짓인 명제를 의미한다.

임의의 두 명제 P, Q에 대한 합성 명제 P ↔ Q가 항진 명제라면, 두 명제 P와 Q는 논리적 동치(Logical equivalence)이며 P ≡ Q 또는 P ⇔ Q라고 표기한다.

다음은 논리적 동치 관계의 기본 법칙이다.

논리적 동치 관계	법칙
P ∨ P ⇔ P P ∧ P ⇔ P	멱등 법칙 (Idempotent law)
P ∨ T ⇔ T P ∨ F ⇔ P P ∧ T ⇔ P P ∧ F ⇔ F	항등 법칙 (Identity law)
~T ⇔ F ~F ⇔ T P ∨ (~P) ⇔ T P ∧ (~P) ⇔ F	부정 법칙 (Negation law)
~(~P) ⇔ P	이중 부정 법칙 (Double negation law)
P ∨ Q ⇔ Q ∨ P P ∧ Q ⇔ Q ∧ P P ↔ Q ⇔ Q ↔ P	교환 법칙 (Commutative law)
(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R)	결합 법칙 (Associative law)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)	분배 법칙 (Distributive law)
P ∨ (P ∧ Q) ⇔ P P ∧ (P ∨ Q) ⇔ P	흡수 법칙 (Absorption law)
~(P ∨ Q) ⇔ (~P) ∧ (~Q) ~(P ∧ Q) ⇔ (~P) ∨ (~Q)	드 모르간 법칙 (De Morgan’s law)
P → Q ⇔ ~P ∨ Q	조건 법칙 (Implication law)
P → Q ⇔ ~Q → ~P	대우 법칙 (Contrapositive law)

추론

---

추론(Argument)이란 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참임을 유도하는 방식이다.

여기서 주어진 명제들을 전제(Premise)라고 하며, 유도된 명제를 결론(Conclusion)이라고 한다.

전제를 p1, p2, p3, ..., pn이라하고 결론을 q라 할 때 p1, p2, p3, …, pn ⊢ q라고 표기한다.

유효 추론(Valid argument)이란 주어진 전제(참)에 의해 유도된 결론이 참인 추론이다.

허위 추론(Fallacious argument)이란 주어진 전제(참)에 의해 유도된 결론이 거짓인 추론이다.

여러가지 추론 법칙

추론 법칙	법칙 이름
p p → q ∴ q	긍정 법칙 (Modus ponens)
~q p → q ∴ ~q	부정 법칙 (Modus tollens)
p → q q → r ∴ p → r	조건 삼단 법칙 (Hypothetical syllogism)
p ∨ q ~p ∴ q	선언 삼단 법칙 (Disjunctive dilemma)
(p → q) ∧ (r → s) p ∨ r ∴ (q ∨ s)	양도 법칙 (Constructive dilemma)
(p → q) ∧ (r → s) ~q ∨ ~s ∴ ~p ∨ ~r	파괴적 법칙 (Destructive dilemma)
p ∴ p ∨ q	선접 법칙 (Disjunctive addition)
p ∧ q ∴ p	분리 법칙 (Simplication)
p q ∴p ∧ q	연접 법칙 (Conjunction)

술어 논리

---

위에서 설명한 것처럼 명제는 참과 거짓을 명확하게 구분할 수 있어야 한다.

그런데 명제 중에서도 x + 5 > 10 와 같이 변수가 포함된 명제가 있다.

이런 경우, 명제의 참 거짓을 명확하게 하기 위해서는 변수 x가 속하는 범위가 있어야 하며, 이 범위를 논의 영역(Universe of discourse)이라고 한다.

논의 영역 D에 속하는 변수 x가 포함된 명제를 명제 함수(Propositional Function) 또는 변수 x에 대한 명제 술어(Propositional)라고 하며, P(x)라고 표기한다.

명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리(Predicate logic)라고 한다.

술어 논리는 대상과 술어 사이의 관계를 다루는 논리학으로, 1차 논리, 2차 논리, 고차 논리로 분류된다.

술어 논리는 수학, 철학, 언어학 그리고 컴퓨터 공학에서 사용되는 형식 체계(Formal system)의 컬렉션이며 비논리적인 대상에 정량화된 변수를 사용하고, 명제 논리와 달리 변수가 포함된 문장이 가능하다.

한정자

---

술어 논리에서 변수에 대한 논의 영역의 범위는 한정자(Quantifier)를 통해 정의한다.

한정자는 전체 한정자(Universal quantifier)와 존재 한정자(Existential quantifier)이 있다.

전체 한정자는 논의 영역에 속하는 모든 값을 범위로 지정하며(For all), 기호는 ∀로 표기한다.

명제 ∀x P(x)는 논의 영역 U에 속하는 모든 x에 대해 P(x)가 참일 때, 참의 진릿값을 가진다.

존재 한정자는 논의 영역에 속하는 어떤 값을 범위로 지정하며(There Exist), 기호는 ∃로 표기한다.

명제 ∃x P(x)는 논의 영역 U에 속하는 어떤 x에 대해 P(x)가 참일 때, 참의 진릿값을 가진다.

전체 한정자에서 ‘모든 x에 대하여 P(x)가 성립한다’라고 하면, 그의 부정은 ‘P(x)가 성립하지 않는 x가 존재한다’가 된다. 이를 논리 기호로 나타내면 다음과 같다.

~(∀x P(x)) ⇔ ∃x (~P(x))

마찬가지로 존재 한정자에서 ‘P(x)가 성립하는 x가 존재한다’라고 하면, 그의 부정은 ‘모든 x는 p(x)가 성립하지 않는다’가 되며, 이를 논리 기호로 나타내면 다음과 같다.

~(∃x P(x)) ⇔ ∀x (~P(x))

참고 자료

---

- 김대수, ‘4차 산업혁명 시대의 이산수학’, 생능출판

- 위키백과