명제 논리

**명제 논리**(命題論理, )는 내부 구조가 없는 명제에 논리합이나 부정 따위의 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계이다.

## 정의
### 문법
집합 I가 주어졌다고 하자. 그렇다면, I에 대한 명제 논리의 언어 \mathcal L_I는 다음과 같은 기호들로 구성된다.
* 각 i\in I에 대하여, **[[원자 명제]]**(原子命題, ) \mathsf p_i
* **[[부정 (논리학)|부정]]**(否定, ) \lnot과 **[[실질적 함의]]**(實質的含意, ) \Longrightarrow
** 다른 논리 연산 기호들은 이 두 논리 연산을 통해 나타낼 수 있으므로 사용할 필요가 없다.
** 다른 함수적 완전 집합을 사용하여도 좋다.

명제 논리의 **[[논리식]]**(論理式, )은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.
* 모든 원자 명제는 논리식이다.
* 논리식 P, Q에 대하여, \lnot P와 P\Longrightarrow Q는 논리식이다.

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

### 공리와 추론 규칙
명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 P, Q, R를 사용하여) 다음과 같이 나타낼 수 있다.
* 추론 규칙
** (전건 긍정의 형식)
* 공리 기본꼴
** P\Longrightarrow(Q\Longrightarrow P)
** (P\Longrightarrow(Q\Longrightarrow R))\Longrightarrow((P\Longrightarrow Q)\Longrightarrow(P\Longrightarrow R))
** (\lnot P\Longrightarrow\lnot Q)\Longrightarrow(Q\Longrightarrow P)

### 공리와 추론 규칙 (부정과 논리합을 사용할 경우)
명제 논리는 또 다른 함수적 완전 집합 \{\lnot,\lor\}을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 P, Q, R를 사용하여) 다음과 같이 나타낼 수 있다.
* 추론 규칙
** (선언 도입, , 또는 확장 규칙, )
** (축소 규칙, )
** (결합 규칙, )
** (절단 규칙, )
* 공리 기본꼴
** (배중률) P\lor\lnot P

### 의미론
명제 논리의 모든 논리식의 집합을 \operatorname{Sent}(\mathcal L_I)라고 표기하자. 그렇다면 명제 논리의 **[[구조 (논리학)|구조]]**(構造, )는 다음 조건들을 만족시키는 함수 v\colon\operatorname{Sent}(\mathcal L_I)\to\{0,1\}이다.
* 모든 논리식 P에 대하여,
* 모든 논리식 P, Q에 대하여,
(여기서 \lor, \land는 메타 언어의 논리합·논리곱 기호이다.)

논리식 P와 구조 v에 대하여 v(P)=1이 성립한다면, v가 P를 **[[구조 (논리학)|만족]]**(滿足, )시킨다고 하며, 이를
:v\models P
로 표기한다.

명제 논리의 논리식의 집합(즉, \operatorname{Sent}(\mathcal L_I)의 부분 집합)을 명제 논리의 **이론**(理論, )이라고 한다. 명제 논리의 이론 \mathcal T와 구조 v가 주어졌을 때, 임의의 P\in\mathcal T에 대하여 v\models P라면, v가 \mathcal T의 **[[구조 (논리학)|모형]]**(模型, )이라고 하며, 이를
:v\models\mathcal T
로 표기한다. 모형을 갖는 이론을 **만족 가능 이론**(滿足可能理論, )이라고 한다.

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

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

주어진 명제 논리의 2항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 **[[함수적 완전 집합|(극소) 함수적 완전 집합]]**((極小)函數的完全集合, )이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.
* 크기 1 (총 2개)
** \{\uparrow\}
** \{\downarrow\}
* 크기 2 (총 18개)
** \{\Longrightarrow,\lnot\}
** \{\Longleftarrow,\lnot\}
** \{\not\Longrightarrow,\lnot\}
** \{\not\Longleftarrow,\lnot\}
** \{\land,\lnot\}
** \{\lor,\lnot\}
** \{\Longrightarrow,\bot\}
** \{\Longleftarrow,\bot\}
** \{\Longrightarrow,\not\Longleftrightarrow\}
** \{\Longleftarrow,\not\Longleftrightarrow\}
** \{\not\Longrightarrow,\top\}
** \{\not\Longleftarrow,\top\}
** \{\not\Longrightarrow,\Longleftrightarrow\}
** \{\not\Longleftarrow,\Longleftrightarrow\}
** \{\Longrightarrow,\not\Longrightarrow\}
** \{\Longrightarrow,\not\Longleftarrow\}
** \{\Longleftarrow,\not\Longrightarrow\}
** \{\Longleftarrow,\not\Longleftarrow\}
* 크기 3 (총 6개)
** \{\Longleftrightarrow,\land,\top\}
** \{\Longleftrightarrow,\lor,\top\}
** \{\not\Longleftrightarrow,\land,\bot\}
** \{\not\Longleftrightarrow,\lor,\bot\}
** \{\Longleftrightarrow,\not\Longleftrightarrow,\land\}
** \{\Longleftrightarrow,\not\Longleftrightarrow,\lor\}
* 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

## 같이 보기
* 1차 논리
* 2차 논리
* 고차 논리
* 불 대수
* 부울 도메인
* 불 함수
* 조합 논리
* 선언적 삼단 논법
* 장 뷔리당
* 논리 기호
* 부정논리합
* 수리 논리학
* 연산 (수학)
* 대칭차
* 진리표

## 각주

## 외부 링크
* 
* 


분류:고전 논리