2. 논리와 명제

01 명제란 무엇인가?

수학적 논리의 가장 기본 단위, 명제의 개념을 정리합니다

 

 

컴퓨터 시스템은 현실 세계를 이산적으로 구현하기 위한 시스템입니다. 이를 위해 현실 세계를 수학적으로 모델링해야 하며, 그 모델링은 명제들의 나열, 즉 수학적 논리(Mathematical Logic)로 표현됩니다.

 

📖 명제(Proposition)의 정의
참(True)이나 거짓(False)을 객관적이고 명확하게 구분할 수 있는 문장 또는 수학적 식

· 참/거짓이 애매하지 않아야 함
· 진릿값(Truth Value) : 참(T) 또는 거짓(F)

 

명제 예시

 

문장	명제 여부	진릿값
28은 4의 배수이다	✅ 명제	T (참)
6은 2의 배수이다	✅ 명제	T (참)
고래는 어류이다	✅ 명제	F (거짓)
지금 몇 시예요?	❌ 명제 아님	-

 

 

 

 

02 논리 연산자의 종류

단순 명제를 연결해 합성 명제를 만드는 논리 연산자 4가지

 

하나의 문장으로 구성된 명제를 단순 명제, 여러 단순 명제가 논리 연산자로 연결된 것을 합성 명제(Compound Proposition)라고 합니다. 단순 명제를 이어주는 역할을 하는 것이 바로 논리 연산자(Logical Operator)입니다. 각 연산자가 만들어내는 결과를 한눈에 정리한 표를 진리표(Truth Table)라고 하며, 복잡한 합성명제의 진릿값을 계산할 때 필수적으로 활용됩니다.

 

연산자	기호	영문명	설명
논리합	∨	OR	둘 중 하나라도 참이면 참, 모두 거짓일 때만 거짓
논리곱	∧	AND	둘 다 참일 때만 참, 하나라도 거짓이면 거짓
부정	~ (또는 ¬ )	NOT	진릿값을 반전. 참이면 거짓, 거짓이면 참
배타적 논리합	⊕	XOR	둘 중 하나만 참일 때 참, 같으면 거짓

 

⚠️ 논리 연산자 우선순위
우선순위가 헷갈리면 잘못된 진릿값을 계산하게 됩니다!

1순위 : ( ) 괄호
2순위 : ~ 부정
3순위 : ∧ 논리곱
4순위 : ∨ 논리합
5순위 : → 조건
6순위 : ↔ 쌍방조건

 

 

 

 

03 합성명제의 종류

항진명제, 모순명제, 사건명제 — 진릿값 패턴으로 분류

 

항진명제 (Tautology) 단일 명제의 진릿값에 상관없이 항상 참(T)인 합성명제 예) p ∨ ~p

모순명제 (Contradiction) 단일 명제의 진릿값에 상관없이 항상 거짓(F)인 합성명제 예) p ∧ ~p

사건명제 (Contingency) 항진명제도 모순명제도 아닌 일반적인 합성명제 예) p ∧ q

 

 

 

 

04 조건명제와 쌍방조건명제

P → Q 의 의미와 진릿값 규칙을 명확히 이해해봅시다

 

조건명제 (P → Q)

 

명제 P가 가정(전제), 명제 Q가 결론(결과)이 되는 명제를 조건명제 혹은 함축이라고 합니다. "P이면 Q이다"로 읽으며, P → Q로 표기합니다.

 

핵심! 조건명제의 진릿값 규칙
P가 참(T)이고 Q가 거짓(F)인 경우에만 거짓(F)
나머지 경우는 모두 참(T) — "거짓 전제에서는 무엇이든 참"

 

· P이면 Q이다 (P → Q의 기본 표현)

· P는 Q를 함축한다

· P는 Q의 충분조건이다

· Q는 P의 필요조건이다

· Q일 경우에만 P이다

 

쌍방조건명제 (P ↔ Q)

 

P와 Q가 동시에 가정이자 결론이 되는 명제입니다. P와 Q의 진릿값이 같을 때 참(T), 다를 때 거짓(F)입니다.

 

쌍방조건명제의 다양한 표현
· P이면 Q이고, Q이면 P이다
· 만약 P이면 Q이며, 그 반대도 성립한다
· P는 Q의 필요충분조건이다
· Q일 때만 P이다

 

 

 

 

05 역 · 이 · 대우

조건명제에서 파생되는 세 가지 변형 명제

 

출처: 나무위키(https://namu.wiki/w/%EB%AA%85%EC%A0%9C)

구분	기호	설명
원래 명제	P → Q	P이면 Q이다
역(Converse)	Q → P	가정과 결론의 위치를 교환
이(Inverse)	~P → ~Q	위치는 그대로, 가정과 결론을 부정
대우(Contrapositive)	~Q → ~P	위치 교환 + 부정 (원래 명제와 진릿값 동일!)

 

✓ 중요 포인트!
조건명제(P → Q)와 대우(~Q → ~P)는 항상 진릿값이 같습니다.
따라서 직접 증명이 어려운 명제는 대우를 이용해 증명할 수 있습니다.

 

 

 

 

06 논리적 동치와 술어 논리

두 명제가 동치인 조건과, 변수를 포함하는 술어 논리의 개념

 

논리적 동치 (Logical Equivalence)

 

두 합성명제 P와 Q의 진릿값이 모든 경우에서 동일할 때, 두 명제는 논리적 동치라고 합니다. 기호로는 P ≡ Q 또는 P ⟺ Q로 표현합니다.

 

논리적 동치의 판별 방법
두 명제 P, Q의 쌍방조건 P ↔ Q가 항진명제이면
→ P와 Q는 논리적 동치

동치인 두 명제는 서로를 대체해서 사용할 수 있습니다.

 

✓ 대표 예시 — 드 모르간의 법칙 (De Morgan's Laws)
논리적 동치의 가장 유명한 법칙으로, 부정과 논리합·논리곱의 관계를 나타냅니다.

· ~(p ∨ q) ≡ ~p ∧ ~q : "p 또는 q"의 부정 = "p 아님 그리고 q 아님"
· ~(p ∧ q) ≡ ~p ∨ ~q : "p 그리고 q"의 부정 = "p 아님 또는 q 아님"

예) "비가 오거나 바람이 분다"의 부정 → "비가 오지 않고 바람도 불지 않는다"

 

술어 논리 (Predicate Logic)

 

명제 중에는 값이 정해지지 않은 변수나 객체가 있어서 참/거짓을 바로 판별하기 어려운 경우가 있습니다. 이때 술어(Predicate)를 활용합니다.

 

술어(Predicate) : 한 객체의 성질이나 객체와 객체 사이의 관계를 표현하는 것

예) "x is tall" → x는 변수, "is tall"은 술어 → T(x) 로 표현

· 전체한정자 (∀) : '임의의', '모든' — 모든 원소에 대해 성립
· 존재한정자 (∃) : '어떤', '적어도 하나' — 특정 원소에 대해 성립

 

 

 

 

07 논리적 추론과 현실 응용

논리적 추론의 원리와 4차 산업혁명과의 연결

 

 

논리적 추론이란 어떤 명제가 참인 것을 근거로 다른 명제가 참임을 유도해내는 것입니다. 주어진 가정(전제)이 참일 때, 새로운 결론이 참이 되는 것을 유도합니다.

 

✅ 유효추론 (정당한 추론) · 주어진 전제를 이용해 유도된 결론이 정확한 추론 · 전제가 참(T)일 때 결론이 모두 참(T)인 추론

❌ 허위추론 (부당한 추론) · 주어진 전제를 이용해 유도된 결론이 틀린 추론 · 전제가 참(T)인 경우, 결론이 거짓(F)인 경우가 하나라도 있는 추론

 

논리의 응용 분야

 

· 디지털 논리 : 논리 회로, 디지털 컴퓨터, 엘리베이터 등 가전제품 개발에 응용

· 관계형 데이터베이스 : 수많은 정보를 체계적으로 저장, 빠르고 정확한 질의 처리

· 지식 베이스 시스템 : 인공지능 에이전트가 활용하는 전문 지식 시스템

· AI 프로그래밍 언어 : Lisp(범용, 사실·규칙·질문으로 구성), Prolog(논리·추론 특화)

 

 

 

 

📌 핵심 정리

· 명제 : 참/거짓을 객관적으로 판별할 수 있는 문장 또는 수식
· 논리 연산자 : 논리합(∨), 논리곱(∧), 부정(~), 배타적 논리합(⊕)
· 합성명제 종류 : 항진명제(항상 T), 모순명제(항상 F), 사건명제(경우에 따라)
· 조건명제 P → Q : P가 참이고 Q가 거짓인 경우에만 거짓
· 역·이·대우 : 대우는 원래 명제와 진릿값이 항상 같음
· 논리적 동치 : 두 명제의 진릿값이 모든 경우에서 동일
· 술어 논리 : 변수를 포함한 명제 표현 — 한정자(∀, ∃) 사용
· 논리적 추론 : 전제가 참일 때 결론도 참이면 유효추론

 

 

태그 : 이산수학논리와명제명제논리연산자조건명제역이대우논리적동치술어논리논리적추론진리표