1.1 Propositional Logic 정리
0. Introduction
이번 섹션 1.1에서는 명제논리(propositional logic)를 다룬다. 명제논리는 “참(true)” 또는 “거짓(false)”으로만 평가되는 문장들을 대상으로, 이들을 기호화하고 규칙적으로 다루는 도구이다.
컴퓨터공학 관점에서 보면, 명제논리는
- 조건문
if (x > 0) { ... }의 의미를 정확히 표현하고, - 논리회로(AND, OR, NOT 게이트 등)를 수학적으로 표현하며,
- 프로그램이 모든 입력에 대해 올바르게 동작하는지 증명할 때
기초가 되는 언어라고 볼 수 있다.
1. 핵심 정의 및 개념
1.1 명제(proposition)
명제(proposition)란 참(true) 또는 거짓(false) 중 하나의 진릿값(truth value)을 가지는 문장이다.
예:
- “서울은 한국의 수도이다.” → 참
- “3은 짝수이다.” → 거짓
- “오늘은 기분이 좋다.” → 애매하지만, 맥락을 정하면 일단 참/거짓을 줄 수 있으니 명제로 취급하기도 한다.
질문문 “지금 몇 시야?”, 명령문 “문을 닫아라” 같은 것은 참/거짓으로 평가되지 않으므로 명제가 아니다.
명제를 나타낼 때는 보통 소문자 영어 문자를 사용한다:
p, q, r, s, …
각 명제는 진릿값(truth value) T(true) 또는 F(false)를 갖는다.
1.2 논리 연산자(logical operator, connective)
기본 명제들로부터 복합 명제(compound proposition)를 만드는 기호들을 논리 연산자(logical operator, connective)라고 한다.
이 섹션에서 다루는 주요 연산자:
- 부정(negation) :
¬ - 논리곱(conjunction) :
∧ - 논리합(disjunction, 포함 “또는”) :
∨ - 배타적 논리합(exclusive or, XOR) :
⊕(기호는 문맥에 따라 다를 수 있음) - 조건문(conditional) :
→ - 쌍조건문(biconditional) :
↔
각 연산자는 진리표(truth table)로 의미를 정의한다.
1.3 부정(negation)
정의 (Definition 1). 명제 p의 부정(negation) ¬p 는
“p가 아니다(it is not the case thatp)”
라는 명제이다.
- 표기:
¬p또는~p등 - 읽기: “not p”, “p가 아니다”
진리표:
| p | ¬p |
|---|---|
| T | F |
| F | T |
즉, 부정은 진릿값을 뒤집는 연산이다.
예시:
-
p: “Michael의 PC는 리눅스를 실행한다.”
→¬p: “Michael의 PC는 리눅스를 실행하지 않는다.” -
q: “Vandana의 스마트폰은 최소 32GB 메모리를 가진다.”
→¬q: “Vandana의 스마트폰은 32GB 미만의 메모리를 가진다.”
여기서 “at least 32GB” 의 부정을 자연스럽게 “less than 32GB” 로 바꾸는 식의 일상 언어 정리 작업이 중요하다.
1.4 논리곱(conjunction) p ∧ q
정의 (Definition 2). 명제 p, q 에 대해
논리곱(conjunction) p ∧ q 는
“p 그리고(and) q”
라는 명제이고, p와 q가 모두 참일 때만 참이다.
진리표:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
직관적으로는 조건을 “동시에” 만족해야 할 때 사용하는 연산이다.
예:
p: “오늘은 월요일이다.”q: “오늘은 비가 온다.”- →
p ∧ q: “오늘은 월요일이고, 비가 온다.”
1.5 논리합(disjunction) p ∨ q
논리합(disjunction) p ∨ q 는
“p 또는(or) q”
를 의미하고, 두 명제 중 적어도 하나가 참이면 참이다.
진리표:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
여기서 ∨ 는 포함적(inclusive) “또는” 이다.
즉 “둘 다”인 경우도 허용한다.
일상 언어에서는 “또는”이 포함적/배타적 둘 다로 쓰이기 때문에,
논리에서는 ∨ 와 “exclusive or”를 구분하는 것이 중요하다.
1.6 배타적 논리합(exclusive or, XOR)
배타적 논리합(exclusive or), 줄여서 XOR 은
“p 또는 q 이지만 둘 다는 아니다”
라는 의미이다.
진리표:
| p | q | p XOR q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
예: “오늘은 월요일이거나 화요일이다.”라고 말할 때, 보통은 둘 다 동시에 될 수 없으므로 XOR에 가깝다.
1.7 조건문(conditional) p → q
조건문(conditional statement) p → q 는
“만약 p이면, q이다(if p, then q)”
라고 읽는다. 여기서
p: 가정(antecedent, hypothesis)q: 결론(consequent)
진리표는 다음과 같다.
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
특히 중요한 두 줄:
- p 가 거짓인데 q 가 참인 경우: 참
- p 가 거짓이고 q 도 거짓인 경우: 참
직관: “약속을 어겼냐?”에 집중해서 생각하면 된다.
예를 들어, “숙제를 하면(= p) 게임을 한다(= q).”라는 약속이 있을 때,
- 숙제를 했는데 게임을 못했다 → 약속 어김 →
p → q거짓 - 숙제를 안 했다면, 게임을 하든 말든 이 약속을 어겼다고는 하지 않음 →
p → q참
[[picture : 조건문 p → q 의 진리표와, ‘약속’을 지켰는지 여부를 비교해서 보여주는 그림]]
조건문의 변형: 역·이·대우
- 역(converse) :
q → p - 이(inverse) :
¬p → ¬q - 대우(contrapositive) :
¬q → ¬p
중요한 사실:
p → q와 대우¬q → ¬p는 항상 같은 진리표를 갖는다 (논리적으로 동치).- 반면 역(
q → p) 과 이(¬p → ¬q) 는 일반적으로 동치가 아니다.
1.8 쌍조건문(biconditional) p ↔ q
쌍조건문(biconditional) p ↔ q 는
“p 일 때 그리고 오직 그때만 q 이다 (p if and only if q)”
라고 읽는다.
진리표:
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
즉, p와 q의 진릿값이 같을 때 (둘 다 참이거나 둘 다 거짓일 때) 쌍조건문은 참이다.
일상 언어 표현들:
- “p 당하고 오직 그때만(if and only if) q”
- “p는 q의 필요충분조건(necessary and sufficient condition)이다.”
1.9 진리표(truth table)와 복합 명제
지금까지 본 모든 연산자는 진리표로 의미가 결정된다. 여러 개의 변수와 연산자를 포함하는 복합 명제의 진리값은 다음 방식으로 계산한다.
- 포함된 명제 변수들의 가능한 진릿값 조합을 행으로 나열한다.
- 안쪽에서 바깥으로, 연산 순서에 맞게 중간 열들을 계산한다.
- 마지막 열이 전체 복합 명제의 진리값이 된다.
예로, 다음 명제를 보자:
$$ (p \lor ¬q) \to (p \land q). $$
이 명제의 진리표는 다음과 같이 계산된다.
| p | q | ¬q | p ∨ ¬q | p ∧ q | (p ∨ ¬q) → (p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
[[picture : 위와 같은 진리표를 표 형식으로 정리한 그림]]
1.10 연산자 우선순위(precedence of logical operators)
괄호가 없으면 어떤 연산을 먼저 할지 규칙이 필요하다. 보통 다음과 같이 우선순위를 정한다.
- 부정(negation)
¬ - 논리곱(conjunction)
∧ - 논리합(disjunction)
∨ - 조건문
→ - 쌍조건문
↔
예:
¬p ∧ q는(¬p) ∧ q로 읽어야 하고,¬(p ∧ q)와는 다르다.
그래도 헷갈릴 때는 괄호를 적극적으로 쓰는 것이 좋다.
[[picture : 같은 식 ¬p ∧ q 와 ¬(p ∧ q) 를 두 개의 작은 논리회로(또는 truth table)로 비교한 그림]]
2. 중요한 정리 / 원리 / 아이디어
이 섹션 1.1에서 핵심이 되는 아이디어들을 몇 가지로 정리해 보자.
-
모든 논리 연산자는 진리표로 정의된다.
즉 “의미를 직관적으로 느낀다”가 아니라, 표를 보고 기계적으로 참/거짓을 결정할 수 있다. -
조건문
p → q의 진리표는 ‘약속’ 관점으로 이해하면 덜 낯설다.
p가 거짓이면 “약속을 위반할 상황이 애초에 안 생겼다” 고 보아 참으로 취급한다. -
대우(contrapositive)는 원래 조건문과 항상 동치다.
→ 나중에 증명할 때 “p → q를 직접 증명하기 어려우면¬q → ¬p를 증명하자”라는 전략을 쓸 수 있다. -
우선순위를 명확히 정해 두면, 논리식을 파싱(parse)하는 규칙이 일관적이 된다.
→ 컴파일러가 조건문을 해석할 때도 같은 아이디어를 사용한다.
3. 예제와 풀이 또는 논리적 reasoning 과정
예제 1. 명제인지 판별하기
다음 문장들이 명제인지, 그리고 명제라면 참/거짓을 말해보자.
- “3은 소수이다.”
- “x + 1 = 0”
- “오늘 저녁에 비가 올 것이다.”
- “문을 닫아라.”
해설
- “3은 소수이다.” → 참/거짓이 명확히 정해짐 (참). → 명제.
-
“x + 1 = 0” → x가 무엇인지 구체적으로 주어지지 않았기 때문에, 현재 상태에서는 참/거짓을 말할 수 없다.
→ 이건 나중에 다룰 명제 함수(predicate)의 예이고, 명제가 아니다. - “오늘 저녁에 비가 올 것이다.” → 현재 시각에서는 모르지만, 어떤 하나의 사실로 결론이 난다(올지, 안 올지). → 명제.
- “문을 닫아라.” → 명령문, 참/거짓으로 평가할 수 없다. → 명제가 아니다.
예제 2. 자연어 문장의 부정 구하기
문장:
“이 시스템은 최소 8GB 메모리를 가진다.”
를 명제 p로 보고, ¬p를 자연스러운 한국어로 써보자.
- 직역: “이 시스템은 최소 8GB 메모리를 가지는 것이 아니다.”
- 자연스럽게: “이 시스템은 8GB 미만의 메모리를 가진다.”
즉, “at least 8GB” 의 부정은 “less than 8GB” 가 된다.
예제 3. 복합 명제의 진리표 직접 만들어 보기
명제:
$$ (p ∨ ¬q) → (p ∧ q) $$
에 대해 진리표를 만들고, 어떤 경우에 거짓이 되는지 살펴보자.
p, q의 조합은 4가지: (T, T), (T, F), (F, T), (F, F)- 각 행에서
¬q→p ∨ ¬q→p ∧ q→(p ∨ ¬q) → (p ∧ q)순서로 계산.
결과는 다음과 같다.
| p | q | ¬q | p ∨ ¬q | p ∧ q | (p ∨ ¬q) → (p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
이 표를 해석해 보면, 이 명제는 두 행에서 거짓이 된다:
- p = T, q = F
- p = F, q = F
즉 “왼쪽 (p ∨ ¬q) 는 참인데, 오른쪽 (p ∧ q) 가 거짓인 경우”에만 전체가 거짓이다.
이는 “A → B 는 A 가 참인데 B 가 거짓이면 거짓”이라는 조건문 정의를 다시 확인시켜 준다.
[[picture : p, q, ¬q, p ∨ ¬q, p ∧ q, (p ∨ ¬q) → (p ∧ q) 여섯 개 열로 구성된 진리표 그림]]
예제 4. 우선순위 헷갈릴 수 있는 식
다음 두 식을 비교해 보자.
¬p ∧ q¬(p ∧ q)
우선순위 규칙에 따르면, 괄호가 없을 때 부정이 먼저 적용되므로
¬p ∧ q 는 사실상 (¬p) ∧ q 이다.
두 식의 진리표를 비교해 보자.
| p | q | ¬p | (¬p) ∧ q | p ∧ q | ¬(p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | F | T | F |
| T | F | F | F | F | T |
| F | T | T | T | F | T |
| F | F | T | F | F | T |
특히 (p, q) = (F, T) 에서 (¬p) ∧ q 는 참이고, ¬(p ∧ q) 도 참이어서 여기서는 우연히 같지만, 전체적으로는 열이 다르다.
메시지: 괄호와 우선순위를 잘못 해석하면 완전히 다른 논리식을 얻게 된다.
4. 응용 또는 컴퓨터공학적 맥락
명제논리는 단순히 “수학 퍼즐”을 위한 것이 아니라, 실제 컴퓨터공학에서 굉장히 많이 쓰인다.
4.1 프로그램 조건문 표현
예를 들어,
if (x > 0 && y == 0) { ... }
라는 조건문이 있을 때,
명제 p : “x > 0”, q : “y == 0” 이라 두면
조건은 p ∧ q 로 표현된다.
복잡한 조건문을 명제논리식으로 바꿔두면, 논리적 오류(괄호 실수, NOT 위치 오류 등)를 찾기 쉬워진다.
[[picture : if-else 블록과 대응하는 논리식(p, q, r)을 나란히 배치한 그림]]
4.2 논리회로 설계(logic circuits)
- 하드웨어에서 AND, OR, NOT 게이트는 각각
∧, ∨, ¬에 정확히 대응한다. - 회로의 출력이 모든 입력 조합에서 어떻게 되는지 분석하는 것도 진리표를 만드는 것과 동일하다.
- 나중의 Boolean algebra 내용과도 직접 연결된다.
[[picture : 입력 두 개와 AND, OR, NOT 게이트가 있는 간단한 논리회로와, 그에 대응하는 명제논리식 p ∧ ¬q 그림]]
4.3 프로그램 검증(program verification)
- “어떤 입력이 들어와도 이 프로그램은 안전한 상태를 유지한다” 같은 문장을 논리식으로 표현해 놓으면,
- 그 논리식이 항상 참인지(tautology) 검증하는 식으로, 프로그램의 안전성을 수학적으로 논의할 수 있다.
- 이는 나중의 “규칙 추론, 증명”과 이어지는 핵심 아이디어이다.
5. 요약
-
명제(proposition) 는 참/거짓 중 하나의 진릿값을 갖는 문장이고,
명제 변수
p, q, …로 기호화한다. - 부정, 논리곱, 논리합, 조건문, 쌍조건문 등 논리 연산자는 모두 진리표로 의미가 정의되며, 이를 이용해 복합 명제를 구성한다.
-
조건문
p → q는 “p이면 q이다”를 의미하며, 대우¬q → ¬p와 항상 동치인 반면, 역·이는 일반적으로 동치가 아니다. - 연산자 우선순위(¬, ∧, ∨, →, ↔) 를 정해 두면 괄호 없이도 논리식을 해석할 수 있고, 이는 프로그래밍 언어의 조건문, 논리회로 설계, 프로그램 검증 등의 기초가 된다.
