[Discrete Mathematics] 2. Logic & Proposition
이산수학 - 논리와 명제
[Discrete Mathematics] 2. Logic & Proposition
이 포스팅 시리즈는 2026년 1학기 박캐서린교수님의 이산구조 수업 내용을 바탕으로 정리한 글입니다.
2. Logic & Proposition (논리와 명제)
1)논리와 명제
- 명제 논리(Propositional Logis)
- 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는 법칙
- 술어 논리(Predicate Logic)
- 주어와 술어로 구분하여 참 또는 거짓에 관한 법칙
- 명제(proposition)란 어떤 사고를 나타내는 문장 중에서 참(true)이나 거짓(false)을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식을 말한다.
- 명제의 진리 값은 참일 때는 T(true), 거짓일 때는 F(false)로 각각 표시한다.
- 명제는 T와 F의 2가지의 진리값만을 가지므로 이진 논리라고 한다.
2)논리 연산
논리 연산자(Logical Operators)
- 단순명제들을 연결시켜 주는 역활을 하는 ∨, ∧, ~과 같은 연결자라고 한다.
합성 명제의 진리값
- 단순 명제의 진리 값은 그 명제가 참이냐 거짓이냐에 따라 T 또는 F로 표시한다.
- 함성 명제의 진리 값은 복잡한 경우가 많다.
| 연산자의 이름 | 기호 | 연산자의 의미 |
|---|---|---|
| 부정 | ~ | NOT |
| 논리곱 | ∧ | AND |
| 논리합 | ∨ | OR |
| 부정 논리곱 | ⊼ | NAND |
| 부정 논리합 | ⊽ | NOR |
| 배타적 논리합 | ⊕ | XOR, Exclusive OR |
| 조건 | → | if ··· then |
| 쌍방 조건 | ↔ | if and only if (iff) |
1) 부정(Negation, NOT;~)
- 임의의 명제 p 가 주어졌을 때 그 명제에 대한 부정은 명제 p의 반대되는 진리값을 가진다.
- 기호로는 ~p라고 쓰고 ‘not p’ 또는 ‘p가 아니다’라고 한다.
| p | ~p |
|---|---|
| T | F |
| F | T |
2) 논리곱(Conjunction, AND;∧)
- 임의의 두 명제 p, q가 ‘그리고(AND)’로 연결되어 있을 때 명제 p, q의 논리곱은 p∧q로 표기한다.
- p and q 또는 p 그리고 q라고 함.
- 두 명제의 논리곱 p∧q는 두 명제가 둘 다 참인 경우에만 참, 그렇지 않으면 거짓이다.
| p | q | p∧q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3) 논리합(Djsjunction, OR;∨)
- 임의의 두 명제 p, q가 ‘또는(OR)’으로 연결되어 있을 때 명제 p, q의 논리합은 p∨q로 표시한다.
- p or q나 p또는 q라고 표현한다.
- 두 명제의 논리합 p∨q는 두 명제가 모두 거짓인 경우에만 거짓의 진리값을 가진다.
| p | q | p∨q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
4) 부정 논리곱(NAND;⊼)
- Not AND. 논리곱의 결과값을 부정한 것이다.
- 두 명제가 모두 참이면 거짓, 그 외에는 참값을 가진다.
| p | q | p⊼q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
5) 부정 논리합(NOR;⊽)
- Not OR. 논리합의 결과값을 부정한 것이다.
- 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다.
| p | q | p⊽q |
|---|---|---|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
6) 배타적 논리합(Exclusive OR, XOR;⊕)
- 임의의 두 명제 p⊕q로 표현한다.
- 진리 값은 p와 q 두 명제 중에서 하나의 명제가 참이고 다른 하나의 명제가 거짓일 때 참의 진리값을 가지고, 그렇지 않으면 거짓의 진리값을 가진다. (두 값이 다를 때)
| p | q | p⊕q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
7) 조건(Implication)
- 임의의 명제 p, q의 조건 연산자는 p→q로 표시한다.
- ‘p이면 q이다’라고 읽는다.
- p가 참일 때 Q도 반드시 참이다.
| p | q | p→q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
조건 연산자 →는 ‘p이면 q이다’뿐만 아니라, 다음과 같이 똑같은 진리 값을 가지는 표현으로 나타내질 수 있다.
- (a) p이면 q이다. (if p, then q)
- (b) p는 q의 충분조건이다. (p is sufficient for q)
- (c) q는 p의 필요조건이다. (q is necessary for p)
- (d) p는 q를 함축한다. (p implies q)
8) 쌍방 조건
- 임의의 명제 p, q의 쌍방 조건은 p↔q로 표시한다.
- ‘p이면 q이고, q이면 p이다.’라고 한다.
- 진리값은 p, q가 모두 참이거나 모두 거짓일 때 참의 값을 가지고, 그외에는 거짓의 값을 가진다.
| p | q | p↔q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
쌍방 조건도 같은 의미를 가진 다른 표현으로 나타내질 수 있다.
- (1) p이면 q이고, q이면 p이다. (p if and only if q)
- (2) p는 q의 필요충분조건이다. (p is necessary and sufficient for q)
논리 연산자의 우선순위
~ > ∧ > ∨ > → > ↔
- 명제 p → q에 대하여
- q → p를 역(converse)
- ~p → ~q를 이(inverse)
- ~q → ~p를 대우(contrapositive)
| (명제) | (역) | (이) | (대우) | ||||
|---|---|---|---|---|---|---|---|
| p | q | ~p | ~q | p→q | q→p | ~p→~q | ~q→~p |
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | T | T | F |
| F | T | T | F | T | F | F | T |
| F | F | T | T | T | T | T | T |
3)항진 명제와 모순 명제
- 항진 명제(tautology): 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리값이 항상 참(T)의 값을 가질 때
- 모순 명제(contradiction): 합성 명제에서 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리값이 항상 거짓(F)의 값을 가질 때
4)논리적 동치 관계
두 개의 명제 p, q의 쌍방 조건 p ↔ q가 항진 명제이면, 두 명제 p, q는 논리적 동치(logical equivalence)라 하고, p ≡ q 또는 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) ⇔ p | 드 모르간 법칙 (De Morgan’s law) |
| p → q ⇔ ~p ∨ q | 조건 법칙 |
| p → q ⇔ ~q → ~p | 대우 법칙 |
- 두 명제가 논리적 동치 관계임을 입증하는 방법
- 두 명제에 대한 진리표를 구하고 두 명제의 진리 값이 값음을 증명한다.
- 하나의 명제로부터 논리적 동치 관계의 기본 법칙을 이용하여 다른 명제로 유도해 낸다.
- 이 중 문제에 적당한 방법을 선택하여 문제를 해결한다.
5)추론
- 추론
- 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도해내는 방법.
- 주어진 명제들인 $p_1, p_2, …, p_n$을 전제(premise)라고 한다.
- 새로이 유도된 명제 q를 결론(conclusion)이라고 한다.
- 수학적표현: $p_1, p_2, …, p_n$ ⊢ q
- 유효 추론(valid argument)
- 주어진 전체가 참이고 결론도 참인 추론
- 허위 추론(fallacious argument)
- 결론이 거짓인 추론
- 여러 가지 추론 법칙
| 추론 법칙 | 법칙 이름 |
|---|---|
| p p → q ∴ q | 긍정 법칙 (modus ponens) |
| ~q p → q ∴ ~p | 부정 법칙 (modus tollens) |
| p → q q → r ∴ p → r | 조건 삼단 법칙 (hypothetical syllogism) |
| p ∨ q ~p ∴ q | 선언 삼단 법칙 (disjunctive syllogism) |
| (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) |
- 가장 많이 사용되고 잘 알려진 3가지 논리 법칙
- (a) 긍정 법칙: p, p → q ⊢ q
- (b) 부정 법칙: ~q, p → q ⊢ ~p
- (c) 삼단 법칙: p → q, q → r ⊢ p → r
6)술어 논리
- 술어 논리
- 명제 중에는 값이 정해지지 않는 변수나 객체(object)가 있어서 참과 거짓을 판별하기 힘든 경우가 있다.
- 변수의 값에 따라 그 명제가 참이 되고 거짓이 될 수 있다.
- 이와 같은 형태의 명제를 p(x)로 표시하도, p(x)를 변수 x에 대한 명제 술어(propositional predicate)라고 한다.
- 명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리(predicate logic)라고 한다.
- 술어 한정자
- 술어를 나타내는 방법 중에서 변수의 범위를 한정시키는 것
- 전체 한정자 (universal quantifier;∀): 변수 x가 가질 수 있는 모든 값에 대하여 p(x)가 참이라는 것을 나타냄.
- x의 모든 가능한 값에서 p(x)가 참이다
- 표기 방법: ∀xp(x)
- 존재 한정자 (existential quantifier;∃): 변수 x가 가질 수 있는 값 중에서 p(x)를 만족하는 값이 적어도 하나 존재한다는 것을 의미.
- p(x)를 만족하는 x가 하나 이상 존재한다
- 표기 방법: ∃xp(x)
- 전체 한정자 (universal quantifier;∀): 변수 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))
7)논리형 언어 - prolog
- 프롤로그(prolog) 언어
- 논리와 명제를 컴퓨터 프로그램을 통해 보다 빠르고 쉽게 구현할 수 있는 프로그래밍 언어
- prolog 특징
- 사실, 규칙, 질문들로 프로그래밍이 구성되어있다.
- 사실과 규칙들을 데이터베이스로 구성하였으며, 프로그램 실행은 자료에 대한 질문의 응답 형식이다.
- 대화식의 명령 방식을 사용한다.
- 사용자의 질문에 답하기 위해 추론 엔진(inference engine)응 사용하고 사용자가 사실과 규칙 등을 입력한다.
- prolog 프로그램
- 우리가 쉽게 접하기 드문 색다른 형태의 언어이다.
- 논리적 연산과 인공지는 분야에서의 논리 찬단을 위한 프로그램의 구현에 있어서 매우 중요한 역활을 담당한다.
- 사실과 규칙들만 기술하고 프로그램의 실행 순서는 명시하지 않으므로 ‘제 5세대 컴퓨터 언어’라고도 한다.
8)논리의 응용분야와 인공지능
- 논리와 명제는 현대 컴퓨터 관련 핵심 기술인 디지털 논리와 관계형 데이터베이스의 학문적 바탕이 된다.
- 최근 들어 떠오르는 논리 프로그래밍, 인공지능, 오토마타 이론 등에 넌ㄹ리 응용되고 있다.
(1) 논리의 응용 분야
- 디지털 논리(Digital Logic)
- 디지털 논리는 현실 세계에서 다양한 방면에 응용되고 있다.
- 관계형 베이터베이스(Relational Database)
- 논리는 관계형 데이터베이스를 통해 수많은 정보들을 체계적으로 저장한다.
- 다양한 질의에 대해 빠르고 정확하게 답변할 수 있는 바탕이 되기도 한다.
(2) 논리 기반 인공지능과 전문가 시스템
- 인공지능에서 지식을 구조적으로 표현하고 논리적으로 추론할 수 있는 바탕을 제공함
- Lisp, Prolog: 논리 기반 AI 언어
- Python은 인공지능의 머신러닝과 딥러닝에 폭 넓게 활용되고 있음.
- 전문가 시스템(Expert System): 사실과 규칙을 이용해 추론엔진으로 새로운 지식 생성, 의료 진단, 로보틱스, 게임 등 문제 해결에 폭 넓게 응용되며, 논리와 명제는 AI의 핵심 이론적 토대이자 필수 지식임.
This post is licensed under CC BY 4.0 by the author.