명제 논리

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

## 문법
집합 I가 주어졌다고 하자. 그렇다면, I에 대한 명제 논리의 언어 \mathcal L_I는 다음과 같은 기호들로 구성된다. * 각 i\in I에 대하여, **원자 명제**(原子命題, atomic proposition) \mathsf p_i * **부정**(否定, negation) \lnot과 **실질적 함의**(實質的含意, material implication) \Longrightarrow ** 다른 논리 연산 기호들은 이 두 논리 연산을 통해 나타낼 수 있으므로 사용할 필요가 없다. ** 다른 함수적 완전 집합을 사용하여도 좋다. 명제 논리의 **논리식**(論理式, (well-formed) formula)은 다음 문법을 따르는 명제 논리 기호들의 문자열이다. * 모든 원자 명제는 논리식이다. * 논리식 P, Q에 대하여, \lnot P와 P\Longrightarrow Q는 논리식이다. 주어진 논리 체계의 **문장**(文章, sentence)은 자유 변수를 갖지 않는 논리식으로 정의된다. 명제 논리의 논리식은 변수를 포함하지 않으므로 모든 논리식은 문장이다.
## 공리와 추론 규칙
명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 P, Q, R를 사용하여) 다음과 같이 나타낼 수 있다. * 추론 규칙 ** (전건 긍정의 형식)\begin{matrix} P,\;P\Longrightarrow Q\\\ \hline Q \end{matrix} * 공리 기본꼴 ** 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를 사용하여) 다음과 같이 나타낼 수 있다. * 추론 규칙 ** (선언 도입, disjunction introduction, 또는 확장 규칙, expansion rule)\begin{matrix} P\\\ \hline P\lor Q \end{matrix} ** (축소 규칙, contraction rule)\begin{matrix} P\lor P\\\ \hline P \end{matrix} ** (결합 규칙, associative rule)\begin{matrix} P\lor(Q\lor R)\\\ \hline (P\lor Q)\lor R \end{matrix} ** (절단 규칙, cut rule)\begin{matrix} P\lor Q,\;\lnot P\lor R\\\ \hline Q\lor R \end{matrix} * 공리 기본꼴 ** (배중률) P\lor\lnot P
## 의미론
명제 논리의 모든 논리식의 집합을 \operatorname{Sent}(\mathcal L_I)라고 표기하자. 그렇다면 명제 논리의 **구조**(構造, structure)는 다음 조건들을 만족시키는 함수 v\colon\operatorname{Sent}(\mathcal L_I)\to\\{0,1\\}이다. * 모든 논리식 P에 대하여,v(\lnot P)=\begin{cases} 1&v;(P)=0\\\ 0&v;(P)=1 \end{cases} * 모든 논리식 P, Q에 대하여,v(P\Longrightarrow Q)=\begin{cases} 1&v;(P)=0\lor v(Q)=1\\\ 0&v;(P)=1\land v(Q)=0 \end{cases} (여기서 \lor, \land는 메타 언어의 논리합·논리곱 기호이다.) 논리식 P와 구조 v에 대하여 v(P)=1이 성립한다면, v가 P를 **만족**(滿足, satisfy)시킨다고 하며, 이를 :v\models P 로 표기한다. 명제 논리의 논리식의 집합(즉, \operatorname{Sent}(\mathcal L_I)의 부분 집합)을 명제 논리의 **이론**(理論, theory)이라고 한다. 명제 논리의 이론 \mathcal T와 구조 v가 주어졌을 때, 임의의 P\in\mathcal T에 대하여 v\models P라면, v가 \mathcal T의 **모형**(模型, model)이라고 하며, 이를 :v\models\mathcal T 로 표기한다. 모형을 갖는 이론을 **만족 가능 이론**(滿足可能理論, satisfiable theory)이라고 한다.
# 성질
명제 논리는 건전성, 완전성, 콤팩트성 정리를 만족시킨다.
## 논리 연산과 함수적 완전 집합
n개의 원자 명제로 구성된 명제 논리의 논리식이 가질 수 있는 진리표는 총 2^{2^n}개이다. 특히, 명제 논리는 총 16개의 (서로 동치가 아닌) 2항 논리 연산이 존재하며, 이들은 다음과 같다. {| class="wikitable" ! p ! q ! 모순 명제 \bot ! 논리곱 p\land q ! 비함의 p\not\Longrightarrow q ! 역비함의 p\not\Longleftarrow q ! 부정 논리합 p\downarrow q ! 첫째 성분 p ! 둘째 성분 q ! 실질적 동치 p\Longleftrightarrow q |- | 1 || 1 || 0 || 1 || 0 || 0 || 0 || 1 || 1 || 1 |- | 1 || 0 || 0 || 0 || 1 || 0 || 0 || 1 || 0 || 0 |- | 0 || 1 || 0 || 0 || 0 || 1 || 0 || 0 || 1 || 0 |- | 0 || 0 || 0 || 0 || 0 || 0 || 1 || 0 || 0 || 1 |} {| class="wikitable" ! p ! q ! 항진 명제 \top ! 부정 논리곱 p\uparrow q ! 실질적 함의 p\Longrightarrow q ! 역함의 p\Longleftarrow q ! 논리합 p\lor q ! 첫째 성분의 부정 \lnot p ! 둘째 성분의 부정 \lnot q ! 배타적 논리합 p\veebar 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)이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.jstor=1989982132 * 크기 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 이상의 극소 함수적 완전 집합은 존재하지 않는다.