명제 논리(命題論理, 영어: propositional logic)는 내부 구조가 없는 명제에 논리합이나 부정 따위의 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계이다.[1]:30, Chapter 3
공리와 추론 규칙 (부정과 논리합을 사용할 경우)
명제 논리는 또 다른 함수적 완전 집합
을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호
,
,
를 사용하여) 다음과 같이 나타낼 수 있다.
- 추론 규칙
- (선언 도입, 영어: disjunction introduction, 또는 확장 규칙, 영어: expansion rule)
![{\displaystyle {\begin{matrix}P\\\hline P\lor Q\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0a400d9b7fd659c520b5b2debaa402b2f5d34e06)
- (축소 규칙, 영어: contraction rule)
![{\displaystyle {\begin{matrix}P\lor P\\\hline P\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/953f867f3de0af247bf771d1c3a5e396de69eb89)
- (결합 규칙, 영어: associative rule)
![{\displaystyle {\begin{matrix}P\lor (Q\lor R)\\\hline (P\lor Q)\lor R\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/cf4d2678e70d12fa61ce3d92e6538f5c64be14db)
- (절단 규칙, 영어: cut rule)
![{\displaystyle {\begin{matrix}P\lor Q,\;\lnot P\lor R\\\hline Q\lor R\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/c0642e46e0bc51b78d72436b457e1a07aa00360d)
- 공리 기본꼴
- (배중률)
![{\displaystyle P\lor \lnot P}](//wikimedia.org/api/rest_v1/media/math/render/svg/310d66594a3a962616c9421ff1a924714da310c1)
의미론
명제 논리의 모든 논리식의 집합을
라고 표기하자. 그렇다면 명제 논리의 구조(構造, 영어: structure)는 다음 조건들을 만족시키는 함수
이다.
- 모든 논리식
에 대하여,![{\displaystyle v(\lnot P)={\begin{cases}1&v(P)=0\\0&v(P)=1\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/087908db256b44fed62e605d30d141eb90f6f2d8)
- 모든 논리식
,
에 대하여,![{\displaystyle v(P\Longrightarrow Q)={\begin{cases}1&v(P)=0\lor v(Q)=1\\0&v(P)=1\land v(Q)=0\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/3b8a2ec0acc39a40c6d282d64f1dd53f2aec72a3)
(여기서
,
는 메타 언어의 논리합·논리곱 기호이다.)
논리식
와 구조
에 대하여
이 성립한다면,
가
를 만족(滿足, 영어: satisfy)시킨다고 하며, 이를
![{\displaystyle v\models P}](//wikimedia.org/api/rest_v1/media/math/render/svg/1e09bd33cd465838080e607f98c907250dfbac0e)
로 표기한다.
명제 논리의 논리식의 집합(즉,
의 부분 집합)을 명제 논리의 이론(理論, 영어: theory)이라고 한다. 명제 논리의 이론
와 구조
가 주어졌을 때, 임의의
에 대하여
라면,
가
의 모형(模型, 영어: model)이라고 하며, 이를
![{\displaystyle v\models {\mathcal {T}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/f1cc4ddd9e40424a3d3152548738b87f7f39f401)
로 표기한다. 모형을 갖는 이론을 만족 가능 이론(滿足可能理論, 영어: satisfiable theory)이라고 한다.
명제 논리는 건전성, 완전성, 콤팩트성 정리를 만족시킨다.
논리 연산과 함수적 완전 집합
개의 원자 명제로 구성된 명제 논리의 논리식이 가질 수 있는 진리표는 총
개이다. 특히, 명제 논리는 총 16개의 (서로 동치가 아닌) 2항 논리 연산이 존재하며, 이들은 다음과 같다.
주어진 명제 논리의 2항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 (극소) 함수적 완전 집합((極小)函數的完全集合, 영어: (minimal) functionally complete set)이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.[2]:132
- 크기 1 (총 2개)
![{\displaystyle \{\uparrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a32a3f2caaa359634df304ad5964711507b5a2ba)
![{\displaystyle \{\downarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a680fc5f220df2ab4fd6c8a144fa44cb8d5aad4f)
- 크기 2 (총 18개)
![{\displaystyle \{\Longrightarrow ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7ce7e75d0589e36b17911dc32a9a99b36ebcae01)
![{\displaystyle \{\Longleftarrow ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/197f9df1f6cd458a273e488c4c66b82f5189dfc1)
![{\displaystyle \{\not \Longrightarrow ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/b90df6649267135b0dc950b891a2c3e2125d6fd2)
![{\displaystyle \{\not \Longleftarrow ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/2f6d5f989216b8339fd9c426893e4374ca879f6e)
![{\displaystyle \{\land ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/abafd3bfc91ad6fbbde79afba535eb3e615f95f3)
![{\displaystyle \{\lor ,\lnot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7421f5ba05cb6e9d201b88eb9990c7b5abb26f12)
![{\displaystyle \{\Longrightarrow ,\bot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/8293a710da4148076f0a2d29f3d3b7a416d8f219)
![{\displaystyle \{\Longleftarrow ,\bot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/5992314325c9b3e93020a67146323a01dd98300f)
![{\displaystyle \{\Longrightarrow ,\not \Longleftrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/5578c414f5a2ba93535e4519c5458fc1470ab755)
![{\displaystyle \{\Longleftarrow ,\not \Longleftrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/baeaec9479df30e05afec62065f1aa73fdc40db0)
![{\displaystyle \{\not \Longrightarrow ,\top \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/dc77df9873588746a033ec574494bc6e95d1a5c0)
![{\displaystyle \{\not \Longleftarrow ,\top \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/cae9dca8a26e378f97cf59bd0c28b0db846209e5)
![{\displaystyle \{\not \Longrightarrow ,\Longleftrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a4033c468b57a65223e83e35ce0711964f345ffc)
![{\displaystyle \{\not \Longleftarrow ,\Longleftrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/2c9f93d118d2a24e6c45d290a18b15533fae70af)
![{\displaystyle \{\Longrightarrow ,\not \Longrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/dd3445f1eca275a0d4947808a89a9883e1b62e98)
![{\displaystyle \{\Longrightarrow ,\not \Longleftarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0887c6e9ba44ef5faf25a0168683f9a770665f99)
![{\displaystyle \{\Longleftarrow ,\not \Longrightarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/681c335c37dcc91719beede2da294c3cea9ab254)
![{\displaystyle \{\Longleftarrow ,\not \Longleftarrow \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e1a8db04554b9e58ffae1ecc2521d38e10c442b5)
- 크기 3 (총 6개)
![{\displaystyle \{\Longleftrightarrow ,\land ,\top \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/2aeb15d203c96f1f59f88331868024ff3e3c33c5)
![{\displaystyle \{\Longleftrightarrow ,\lor ,\top \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0f0a892a4e9be06b0e7acc95a0376f850275006f)
![{\displaystyle \{\not \Longleftrightarrow ,\land ,\bot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/f8f9aa043679ceabe9b3e7875e325d7236e2524f)
![{\displaystyle \{\not \Longleftrightarrow ,\lor ,\bot \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a7b08c17cf24a774973b75bd0c2244e117d118b3)
![{\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\land \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/753418d8e1b6455c228e7fddcb8886054790eeb3)
![{\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\lor \}}](//wikimedia.org/api/rest_v1/media/math/render/svg/49911464bd77e683745712c513c42e5ccbe01987)
- 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.