명제 논리 문서 원본 보기

{{위키데이터 속성 추적}}
'''명제 논리'''(命題論理, {{llang|en|propositional logic}})는 내부 구조가 없는 [[명제]]에 [[논리합]]이나 [[부정 (논리학)|부정]] 따위의 [[논리 연산]]을 가하여 구성한 명제들을 다루는 논리 체계이다.<ref name="Srivastava">{{서적 인용
|성=Srivastava
|이름=S. M.
|제목=A Course on Mathematical Logic
|url=https://archive.org/details/courseonmathemat0000sriv
|언어=en
|총서=Universitext
|출판사=Springer
|위치=New York, NY
|날짜=2008
|isbn=978-0-387-76275-3
|doi=10.1007/978-0-387-76277-7
|lccn=2008920049
}}</ref>{{rp|30, Chapter 3}}

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

명제 논리의 '''[[논리식]]'''(論理式, {{llang|en|(well-formed) formula}})은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.
* 모든 원자 명제는 논리식이다.
* 논리식 <math>P</math>, <math>Q</math>에 대하여, <math>\lnot P</math>와 <math>P\Longrightarrow Q</math>는 논리식이다.

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

=== 공리와 추론 규칙 ===
명제 논리의 [[추론 규칙]]과 [[공리 기본꼴]]들은 (임의의 논리식을 나타내는 기호 <math>P</math>, <math>Q</math>, <math>R</math>를 사용하여) 다음과 같이 나타낼 수 있다.
* 추론 규칙
** ([[전건 긍정의 형식]]){{mindent|<math>\begin{matrix}
P,\;P\Longrightarrow Q\\
\hline
Q
\end{matrix}</math>}}
* 공리 기본꼴
** <math>P\Longrightarrow(Q\Longrightarrow P)</math>
** <math>(P\Longrightarrow(Q\Longrightarrow R))\Longrightarrow((P\Longrightarrow Q)\Longrightarrow(P\Longrightarrow R))</math>
** <math>(\lnot P\Longrightarrow\lnot Q)\Longrightarrow(Q\Longrightarrow P)</math>

=== 공리와 추론 규칙 (부정과 논리합을 사용할 경우) ===
명제 논리는 또 다른 함수적 완전 집합 <math>\{\lnot,\lor\}</math>을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 <math>P</math>, <math>Q</math>, <math>R</math>를 사용하여) 다음과 같이 나타낼 수 있다.
* 추론 규칙
** ([[선언 도입]], {{llang|en|disjunction introduction}}, 또는 확장 규칙, {{llang|en|expansion rule}}){{mindent|<math>\begin{matrix}
P\\
\hline
P\lor Q
\end{matrix}</math>}}
** (축소 규칙, {{llang|en|contraction rule}}){{mindent|<math>\begin{matrix}
P\lor P\\
\hline
P
\end{matrix}</math>}}
** (결합 규칙, {{llang|en|associative rule}}){{mindent|<math>\begin{matrix}
P\lor(Q\lor R)\\
\hline
(P\lor Q)\lor R
\end{matrix}</math>}}
** (절단 규칙, {{llang|en|cut rule}}){{mindent|<math>\begin{matrix}
P\lor Q,\;\lnot P\lor R\\
\hline
Q\lor R
\end{matrix}</math>}}
* 공리 기본꼴
** ([[배중률]]) <math>P\lor\lnot P</math>

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

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

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

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

=== 논리 연산과 함수적 완전 집합 ===
<math>n</math>개의 원자 명제로 구성된 명제 논리의 논리식이 가질 수 있는 [[진리표]]는 총 <math>2^{2^n}</math>개이다. 특히, 명제 논리는 총 16개의 (서로 동치가 아닌) 2항 논리 연산이 존재하며, 이들은 다음과 같다.
{| class="wikitable"
! <math>p</math>
! <math>q</math>
! [[모순 명제]] <math>\bot</math>
! [[논리곱]] <math>p\land q</math>
! [[비함의]] <math>p\not\Longrightarrow q</math>
! [[역비함의]] <math>p\not\Longleftarrow q</math>
! [[부정 논리합]] <math>p\downarrow q</math>
! 첫째 성분 <math>p</math>
! 둘째 성분 <math>q</math>
! [[실질적 동치]] <math>p\Longleftrightarrow q</math>
|-
| 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"
! <math>p</math>
! <math>q</math>
! [[항진 명제]] <math>\top</math>
! [[부정 논리곱]] <math>p\uparrow q</math>
! [[실질적 함의]] <math>p\Longrightarrow q</math>
! [[역함의]] <math>p\Longleftarrow q</math>
! [[논리합]] <math>p\lor q</math>
! 첫째 성분의 [[부정 (논리학)|부정]] <math>\lnot p</math>
! 둘째 성분의 부정 <math>\lnot q</math>
! [[배타적 논리합]] <math>p\veebar q</math>
|-
| 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항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 '''[[함수적 완전 집합|(극소) 함수적 완전 집합]]'''((極小)函數的完全集合, {{llang|en|(minimal) functionally complete set}})이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.<ref name="Wernick">{{저널 인용
|성=Wernick
|이름=William
|제목=Complete Sets of Logical Functions
|언어=en
|저널=Transactions of the American Mathematical Society
|권=51
|호=1
|쪽=117-132
|날짜=1942-01
|issn=0002-9947
|doi=10.2307/1989982
|jstor=1989982
}}</ref>{{rp|132}}
* 크기 1 (총 2개)
** <math>\{\uparrow\}</math>
** <math>\{\downarrow\}</math>
* 크기 2 (총 18개)
** <math>\{\Longrightarrow,\lnot\}</math>
** <math>\{\Longleftarrow,\lnot\}</math>
** <math>\{\not\Longrightarrow,\lnot\}</math>
** <math>\{\not\Longleftarrow,\lnot\}</math>
** <math>\{\land,\lnot\}</math>
** <math>\{\lor,\lnot\}</math>
** <math>\{\Longrightarrow,\bot\}</math>
** <math>\{\Longleftarrow,\bot\}</math>
** <math>\{\Longrightarrow,\not\Longleftrightarrow\}</math>
** <math>\{\Longleftarrow,\not\Longleftrightarrow\}</math>
** <math>\{\not\Longrightarrow,\top\}</math>
** <math>\{\not\Longleftarrow,\top\}</math>
** <math>\{\not\Longrightarrow,\Longleftrightarrow\}</math>
** <math>\{\not\Longleftarrow,\Longleftrightarrow\}</math>
** <math>\{\Longrightarrow,\not\Longrightarrow\}</math>
** <math>\{\Longrightarrow,\not\Longleftarrow\}</math>
** <math>\{\Longleftarrow,\not\Longrightarrow\}</math>
** <math>\{\Longleftarrow,\not\Longleftarrow\}</math>
* 크기 3 (총 6개)
** <math>\{\Longleftrightarrow,\land,\top\}</math>
** <math>\{\Longleftrightarrow,\lor,\top\}</math>
** <math>\{\not\Longleftrightarrow,\land,\bot\}</math>
** <math>\{\not\Longleftrightarrow,\lor,\bot\}</math>
** <math>\{\Longleftrightarrow,\not\Longleftrightarrow,\land\}</math>
** <math>\{\Longleftrightarrow,\not\Longleftrightarrow,\lor\}</math>
* 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

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

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Propositional calculus}}
* {{매스월드|id=PropositionalCalculus|title=Propositional calculus}}

{{글로벌세계대백과사전}}

{{전거 통제}}

[[분류:명제 논리| ]]
[[분류:고전 논리]]