명제 논리

틀:위키데이터 속성 추적 명제 논리(命題論理, 틀:Llang)는 내부 구조가 없는 명제에 논리합이나 부정 따위의 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계이다.틀:Rp

정의

문법

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

• 각 $i\in I$에 대하여, 원자 명제(原子命題, 틀:Llang) ${𝗉}_i$
• 부정(否定, 틀:Llang) $\mathrm{\neg }$과 실질적 함의(實質的含意, 틀:Llang) $⟹$
  • 다른 논리 연산 기호들은 이 두 논리 연산을 통해 나타낼 수 있으므로 사용할 필요가 없다.
  • 다른 함수적 완전 집합을 사용하여도 좋다.

명제 논리의 논리식(論理式, 틀:Llang)은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.

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

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

공리와 추론 규칙

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

• 추론 규칙
  • (전건 긍정의 형식)틀:Mindent
• 공리 기본꼴
  • $P⟹(Q⟹P)$
  • $(P⟹(Q⟹R))⟹((P⟹Q)⟹(P⟹R))$
  • $(\mathrm{\neg }P⟹\mathrm{\neg }Q)⟹(Q⟹P)$

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

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

• 추론 규칙
  • (선언 도입, 틀:Llang, 또는 확장 규칙, 틀:Llang)틀:Mindent
  • (축소 규칙, 틀:Llang)틀:Mindent
  • (결합 규칙, 틀:Llang)틀:Mindent
  • (절단 규칙, 틀:Llang)틀:Mindent
• 공리 기본꼴
  • (배중률) $P\vee \mathrm{\neg }P$

의미론

명제 논리의 모든 논리식의 집합을 $\mathrm{Sent}({ℒ}_I)$라고 표기하자. 그렇다면 명제 논리의 구조(構造, 틀:Llang)는 다음 조건들을 만족시키는 함수 $v:\mathrm{Sent}({ℒ}_I)\to \{0,1\}$이다.

• 모든 논리식 $P$에 대하여,틀:Mindent
• 모든 논리식 $P$, $Q$에 대하여,틀:Mindent

(여기서 $\vee$, $\wedge$는 메타 언어의 논리합·논리곱 기호이다.)

논리식 $P$와 구조 $v$에 대하여 $v(P)=1$이 성립한다면, $v$가 $P$를 만족(滿足, 틀:Llang)시킨다고 하며, 이를

$v\models P$

로 표기한다.

명제 논리의 논리식의 집합(즉, $\mathrm{Sent}({ℒ}_I)$의 부분 집합)을 명제 논리의 이론(理論, 틀:Llang)이라고 한다. 명제 논리의 이론 $𝒯$와 구조 $v$가 주어졌을 때, 임의의 $P\in 𝒯$에 대하여 $v\models P$라면, $v$가 $𝒯$의 모형(模型, 틀:Llang)이라고 하며, 이를

$v\models 𝒯$

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

성질

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

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

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

$p$	$q$	모순 명제 $\mathrm{\perp }$	논리곱 $p\wedge q$	비함의 $p⟹̸q$	역비함의 $p⟸̸q$	부정 논리합 $p\downarrow q$	첫째 성분 $p$	둘째 성분 $q$	실질적 동치 $p⟺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

$p$	$q$	항진 명제 $\mathrm{\top }$	부정 논리곱 $p\uparrow q$	실질적 함의 $p⟹q$	역함의 $p⟸q$	논리합 $p\vee q$	첫째 성분의 부정 $\mathrm{\neg }p$	둘째 성분의 부정 $\mathrm{\neg }q$	배타적 논리합 $p⊻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항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 (극소) 함수적 완전 집합((極小)函數的完全集合, 틀:Llang)이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.틀:Rp

• 크기 1 (총 2개)
  • $\{\uparrow \}$
  • $\{\downarrow \}$
• 크기 2 (총 18개)
  • $\{⟹,\mathrm{\neg }\}$
  • $\{⟸,\mathrm{\neg }\}$
  • $\{⟹̸,\mathrm{\neg }\}$
  • $\{⟸̸,\mathrm{\neg }\}$
  • $\{\wedge ,\mathrm{\neg }\}$
  • $\{\vee ,\mathrm{\neg }\}$
  • $\{⟹,\mathrm{\perp }\}$
  • $\{⟸,\mathrm{\perp }\}$
  • $\{⟹,⟺̸\}$
  • $\{⟸,⟺̸\}$
  • $\{⟹̸,\mathrm{\top }\}$
  • $\{⟸̸,\mathrm{\top }\}$
  • $\{⟹̸,⟺\}$
  • $\{⟸̸,⟺\}$
  • $\{⟹,⟹̸\}$
  • $\{⟹,⟸̸\}$
  • $\{⟸,⟹̸\}$
  • $\{⟸,⟸̸\}$
• 크기 3 (총 6개)
  • $\{⟺,\wedge ,\mathrm{\top }\}$
  • $\{⟺,\vee ,\mathrm{\top }\}$
  • $\{⟺̸,\wedge ,\mathrm{\perp }\}$
  • $\{⟺̸,\vee ,\mathrm{\perp }\}$
  • $\{⟺,⟺̸,\wedge \}$
  • $\{⟺,⟺̸,\vee \}$
• 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

같이 보기

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

외부 링크

• 틀:Eom
• 틀:매스월드