명제 논리

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

정의

문법 
집합 가 주어졌다고 하자. 그렇다면, 에 대한 명제 논리의 언어 는 다음과 같은 기호들로 구성된다.
 각 에 대하여, 원자 명제(原子命題, ) 
 부정(否定, ) 과 실질적 함의(實質的含意, ) 
 다른 논리 연산 기호들은 이 두 논리 연산을 통해 나타낼 수 있으므로 사용할 필요가 없다.
 다른 함수적 완전 집합을 사용하여도 좋다.

명제 논리의 논리식(論理式, )은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.
 모든 원자 명제는 논리식이다.
 논리식 , 에 대하여, 와 는 논리식이다.

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

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

공리와 추론 규칙 (부정과 논리합을 사용할 경우) 
명제 논리는 또 다른 함수적 완전 집합 을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 , , 를 사용하여) 다음과 같이 나타낼 수 있다.
 추론 규칙
 (선언 도입, , 또는 확장 규칙, )
 (축소 규칙, )
 (결합 규칙, )
 (절단 규칙, )
 공리 기본꼴
 (배중률)

의미론 
명제 논리의 모든 논리식의 집합을 라고 표기하자. 그렇다면 명제 논리의 구조(構造, )는 다음 조건들을 만족시키는 함수 이다.
 모든 논리식 에 대하여,
 모든 논리식 , 에 대하여,
(여기서 , 는 메타 언어의 논리합·논리곱 기호이다.)

논리식 와 구조 에 대하여 이 성립한다면, 가 를 만족(滿足, )시킨다고 하며, 이를

로 표기한다.

명제 논리의 논리식의 집합(즉, 의 부분 집합)을 명제 논리의 이론(理論, )이라고 한다. 명제 논리의 이론 와 구조 가 주어졌을 때, 임의의 에 대하여 라면, 가 의 모형(模型, )이라고 하며, 이를

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

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

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

주어진 명제 논리의 2항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 (극소) 함수적 완전 집합((極小)函數的完全集合, )이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.
 크기 1 (총 2개)
 
 
 크기 2 (총 18개)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 크기 3 (총 6개)
 
 
 
 
 
 
 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

각주

외부 링크 
 
 

 
고전 논리