명제 논리

문법

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

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

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

• 모든 원자 명제는 논리식이다.
• 논리식 ${\displaystyle P}$ , ${\displaystyle Q}$ 에 대하여, ${\displaystyle \lnot P}$ 와 ${\displaystyle P\Longrightarrow Q}$ 는 논리식이다.

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

공리와 추론 규칙

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

• 추론 규칙
  • (전건 긍정의 형식)
    ${\displaystyle {\begin{matrix}P,\;P\Longrightarrow Q\\\hline Q\end{matrix}}}$
• 공리 기본꼴
  • ${\displaystyle P\Longrightarrow (Q\Longrightarrow P)}$
  • ${\displaystyle (P\Longrightarrow (Q\Longrightarrow R))\Longrightarrow ((P\Longrightarrow Q)\Longrightarrow (P\Longrightarrow R))}$
  • ${\displaystyle (\lnot P\Longrightarrow \lnot Q)\Longrightarrow (Q\Longrightarrow P)}$

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

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

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

의미론

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

• 모든 논리식 ${\displaystyle P}$ 에 대하여,
  ${\displaystyle v(\lnot P)={\begin{cases}1&v(P)=0\\0&v(P)=1\end{cases}}}$
• 모든 논리식 ${\displaystyle P}$ , ${\displaystyle Q}$ 에 대하여,
  ${\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}}}$

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

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

${\displaystyle v\models P}$

로 표기한다.

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

${\displaystyle v\models {\mathcal {T}}}$

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

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

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

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

${\displaystyle p}$	${\displaystyle q}$	모순 명제 ${\displaystyle \bot }$	논리곱 ${\displaystyle p\land q}$	비함의 ${\displaystyle p\not \Longrightarrow q}$	역비함의 ${\displaystyle p\not \Longleftarrow q}$	부정 논리합 ${\displaystyle p\downarrow q}$	첫째 성분 ${\displaystyle p}$	둘째 성분 ${\displaystyle q}$	실질적 동치 ${\displaystyle 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

${\displaystyle p}$	${\displaystyle q}$	항진 명제 ${\displaystyle \top }$	부정 논리곱 ${\displaystyle p\uparrow q}$	실질적 함의 ${\displaystyle p\Longrightarrow q}$	역함의 ${\displaystyle p\Longleftarrow q}$	논리합 ${\displaystyle p\lor q}$	첫째 성분의 부정 ${\displaystyle \lnot p}$	둘째 성분의 부정 ${\displaystyle \lnot q}$	배타적 논리합 ${\displaystyle 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)이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.^[2]:132

• 크기 1 (총 2개)
  • ${\displaystyle \{\uparrow \}}$
  • ${\displaystyle \{\downarrow \}}$
• 크기 2 (총 18개)
  • ${\displaystyle \{\Longrightarrow ,\lnot \}}$
  • ${\displaystyle \{\Longleftarrow ,\lnot \}}$
  • ${\displaystyle \{\not \Longrightarrow ,\lnot \}}$
  • ${\displaystyle \{\not \Longleftarrow ,\lnot \}}$
  • ${\displaystyle \{\land ,\lnot \}}$
  • ${\displaystyle \{\lor ,\lnot \}}$
  • ${\displaystyle \{\Longrightarrow ,\bot \}}$
  • ${\displaystyle \{\Longleftarrow ,\bot \}}$
  • ${\displaystyle \{\Longrightarrow ,\not \Longleftrightarrow \}}$
  • ${\displaystyle \{\Longleftarrow ,\not \Longleftrightarrow \}}$
  • ${\displaystyle \{\not \Longrightarrow ,\top \}}$
  • ${\displaystyle \{\not \Longleftarrow ,\top \}}$
  • ${\displaystyle \{\not \Longrightarrow ,\Longleftrightarrow \}}$
  • ${\displaystyle \{\not \Longleftarrow ,\Longleftrightarrow \}}$
  • ${\displaystyle \{\Longrightarrow ,\not \Longrightarrow \}}$
  • ${\displaystyle \{\Longrightarrow ,\not \Longleftarrow \}}$
  • ${\displaystyle \{\Longleftarrow ,\not \Longrightarrow \}}$
  • ${\displaystyle \{\Longleftarrow ,\not \Longleftarrow \}}$
• 크기 3 (총 6개)
  • ${\displaystyle \{\Longleftrightarrow ,\land ,\top \}}$
  • ${\displaystyle \{\Longleftrightarrow ,\lor ,\top \}}$
  • ${\displaystyle \{\not \Longleftrightarrow ,\land ,\bot \}}$
  • ${\displaystyle \{\not \Longleftrightarrow ,\lor ,\bot \}}$
  • ${\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\land \}}$
  • ${\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\lor \}}$
• 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

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

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