명제 논리

명제 논리(命題論理, 영어: propositional logic)는 내부 구조가 없는 명제에 논리합이나 부정 따위의 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계이다.^[1]^{:30, Chapter 3}

정의

문법

집합 $I$ 가 주어졌다고 하자. 그렇다면, $I$ 에 대한 명제 논리의 언어 $ℒ_{I}$ 는 다음과 같은 기호들로 구성된다.

각 $i \in I$ 에 대하여, 원자 명제(原子命題, 영어: atomic proposition) $𝗉_{i}$
부정(否定, 영어: negation) ¬과 실질적 함의(實質的含意, 영어: material implication) ⟹
- 다른 논리 연산 기호들은 이 두 논리 연산을 통해 나타낼 수 있으므로 사용할 필요가 없다.
- 다른 함수적 완전 집합을 사용하여도 좋다.

명제 논리의 논리식(論理式, 영어: (well-formed) formula)은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.

모든 원자 명제는 논리식이다.
논리식 $P$ , $Q$ 에 대하여, $\neg P$ 와 $P ⟹ Q$ 는 논리식이다.

주어진 논리 체계의 문장(文章, 영어: sentence)은 자유 변수를 갖지 않는 논리식으로 정의된다. 명제 논리의 논리식은 변수를 포함하지 않으므로 모든 논리식은 문장이다.

공리와 추론 규칙

명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 $P$ , $Q$ , $R$ 를 사용하여) 다음과 같이 나타낼 수 있다.

추론 규칙
- (전건 긍정의 형식)
  $\begin{matrix} P, P ⟹ Q \\ Q \end{matrix}$
공리 기본꼴
- $P ⟹ (Q ⟹ P)$
- $(P ⟹ (Q ⟹ R)) ⟹ ((P ⟹ Q) ⟹ (P ⟹ R))$
- $(\neg P ⟹ \neg Q) ⟹ (Q ⟹ P)$

공리와 추론 규칙 (부정과 논리합을 사용할 경우)

명제 논리는 또 다른 함수적 완전 집합 ${\neg, \lor}$ 을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 $P$ , $Q$ , $R$ 를 사용하여) 다음과 같이 나타낼 수 있다.

추론 규칙
- (선언 도입, 영어: disjunction introduction, 또는 확장 규칙, 영어: expansion rule)
  $\begin{matrix} P \\ P \lor Q \end{matrix}$
- (축소 규칙, 영어: contraction rule)
  $\begin{matrix} P \lor P \\ P \end{matrix}$
- (결합 규칙, 영어: associative rule)
  $\begin{matrix} P \lor (Q \lor R) \\ (P \lor Q) \lor R \end{matrix}$
- (절단 규칙, 영어: cut rule)
  $\begin{matrix} P \lor Q, \neg P \lor R \\ Q \lor R \end{matrix}$
공리 기본꼴
- (배중률) $P \lor \neg P$

의미론

명제 논리의 모든 논리식의 집합을 $Sent (ℒ_{I})$ 라고 표기하자. 그렇다면 명제 논리의 구조(構造, 영어: structure)는 다음 조건들을 만족시키는 함수 $v : Sent (ℒ_{I}) \to {0, 1}$ 이다.

모든 논리식 $P$ 에 대하여,
$v (\neg P) = {\begin{matrix} 1 & v (P) = 0 \\ 0 & v (P) = 1 \end{matrix}$
모든 논리식 $P$ , $Q$ 에 대하여,
$v (P ⟹ Q) = {\begin{matrix} 1 & v (P) = 0 \lor v (Q) = 1 \\ 0 & v (P) = 1 \land v (Q) = 0 \end{matrix}$

(여기서 $\lor$ , $\land$ 는 메타 언어의 논리합·논리곱 기호이다.)

논리식 $P$ 와 구조 $v$ 에 대하여 $v (P) = 1$ 이 성립한다면, $v$ 가 $P$ 를 만족(滿足, 영어: satisfy)시킨다고 하며, 이를

v ⊨ P

로 표기한다.

명제 논리의 논리식의 집합(즉, $Sent (ℒ_{I})$ 의 부분 집합)을 명제 논리의 이론(理論, 영어: theory)이라고 한다. 명제 논리의 이론 $𝒯$ 와 구조 $v$ 가 주어졌을 때, 임의의 $P \in 𝒯$ 에 대하여 $v ⊨ P$ 라면, $v$ 가 $𝒯$ 의 모형(模型, 영어: model)이라고 하며, 이를

v ⊨ 𝒯

로 표기한다. 모형을 갖는 이론을 만족 가능 이론(滿足可能理論, 영어: satisfiable theory)이라고 한다.

성질

명제 논리는 건전성, 완전성, 콤팩트성 정리를 만족시킨다.

논리 연산과 함수적 완전 집합

$n$ 개의 원자 명제로 구성된 명제 논리의 논리식이 가질 수 있는 진리표는 총 $2^{2^{n}}$ 개이다. 특히, 명제 논리는 총 16개의 (서로 동치가 아닌) 2항 논리 연산이 존재하며, 이들은 다음과 같다.

$p$	$q$	논리곱 $p \land q$	비함의 $p ⟹̸ q$	역비함의 $p ⟸̸ q$	부정 논리합 $p ↓ q$	첫째 성분 $p$	둘째 성분 $q$	실질적 동치 $p ⟺ q$
1	1	1	0	0	0	1	1	1
1	0	0	1	0	0	1	0	0
0	1	0	0	1	0	0	1	0
0	0	0	0	0	1	0	0	1

$p$	$q$	항진 명제 $⊤$	부정 논리곱 $p ↑ q$	실질적 함의 $p ⟹ q$	역함의 $p ⟸ q$	논리합 $p \lor q$	첫째 성분의 부정 $\neg p$	둘째 성분의 부정 $\neg q$	배타적 논리합 $p ⊻ q$
1	1	1	0	1	1	1	0	0	0
1	0	1	1	0	1	1	0	1	1
0	1	1	1	1	0	1	1	0	1
0	0	1	1	1	1	0	1	1	0

주어진 명제 논리의 2항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 (극소) 함수적 완전 집합((極小)函數的完全集合, 영어: (minimal) functionally complete set)이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.^[2]^:132

크기 1 (총 2개)
- ${↑}$
- ${↓}$
크기 2 (총 18개)
- ${⟹, \neg}$
- ${⟸, \neg}$
- ${⟹̸, \neg}$
- ${⟸̸, \neg}$
- ${\land, \neg}$
- ${\lor, \neg}$
- ${⟹, ⊥}$
- ${⟸, ⊥}$
- ${⟹, ⟺̸}$
- ${⟸, ⟺̸}$
- ${⟹̸, ⊤}$
- ${⟸̸, ⊤}$
- ${⟹̸, ⟺}$
- ${⟸̸, ⟺}$
- ${⟹, ⟹̸}$
- ${⟹, ⟸̸}$
- ${⟸, ⟹̸}$
- ${⟸, ⟸̸}$
크기 3 (총 6개)
- ${⟺, \land, ⊤}$
- ${⟺, \lor, ⊤}$
- ${⟺̸, \land, ⊥}$
- ${⟺̸, \lor, ⊥}$
- ${⟺, ⟺̸, \land}$
- ${⟺, ⟺̸, \lor}$
크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

같이 보기

각주

↑ Srivastava, S. M. (2008). 《A Course on Mathematical Logic》 (영어). Universitext. New York, NY: Springer. doi:10.1007/978-0-387-76277-7. ISBN 978-0-387-76275-3. LCCN 2008920049.
↑ Wernick, William (1942년 1월). “Complete Sets of Logical Functions” (영어). 《Transactions of the American Mathematical Society》 51 (1): 117-132. doi:10.2307/1989982. ISSN 0002-9947. JSTOR 1989982.

외부 링크

“Propositional calculus” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Propositional calculus” (영어). 《Wolfram MathWorld》. Wolfram Research.

파일:Heckert GNU white.svg파일:Cc.logo.circle.svg 이 문서에는 다음커뮤니케이션(현 카카오)에서 GFDL 또는 CC-SA 라이선스로 배포한 글로벌 세계대백과사전의 내용을 기초로 작성된 글이 포함되어 있습니다.

모듈:Authority_control 159번째 줄에서 Lua 오류: attempt to index field 'wikibase' (a nil value).

[Srivastava-1] Srivastava, S. M. (2008). 《A Course on Mathematical Logic》 (영어). Universitext. New York, NY: Springer. doi:10.1007/978-0-387-76277-7. ISBN 978-0-387-76275-3. LCCN 2008920049.

[Wernick-2] Wernick, William (1942년 1월). “Complete Sets of Logical Functions” (영어). 《Transactions of the American Mathematical Society》 51 (1): 117-132. doi:10.2307/1989982. ISSN 0002-9947. JSTOR 1989982.

[1]

[2]