주 메뉴 열기

명제 논리(命題論理, 영어: propositional logic)는 내부 구조가 없는 명제논리합이나 부정 따위의 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계이다.[1]:30, Chapter 3

정의편집

문법편집

명제 논리의 언어는 다음과 같은 기호들로 구성된다.

명제 논리의 논리식은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.

  • 모든 원자 명제는 논리식이다.
  • 논리식  에 대하여,  는 논리식이다.
  • 논리식   에 대하여,  는 논리식이다.

공리와 추론 규칙편집

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

  • 추론 규칙
    • (전건 긍정의 형식)

       

  • 공리 기본꼴
    •  
    •  
    •  

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

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

  • 추론 규칙
    • (선언 도입, 영어: disjunction introduction, 또는 확장 규칙, 영어: expansion rule)

       

    • (축소 규칙, 영어: contraction rule)

       

    • (결합 규칙, 영어: associative rule)

       

    • (절단 규칙, 영어: cut rule)

       

  • 공리 기본꼴
    • (배중률)  

의미론편집

명제 논리의 구조(構造, 영어: structure)는

 

꼴의 함수이다. (여기서 1, 0은 각각 메타 언어에서의 참과 거짓을 나타낸다.) 명제 논리의 구조  는 모든 논리식의 집합 위의 함수로 다음과 같이 확장할 수 있다.

  • 논리식  에 대하여,  일 필요충분조건은  
  • 논리식   에 대하여,  일 필요충분조건은  이거나  

논리식  와 구조  가 주어졌을 때, 만약  이라면,   만족(滿足, 영어: satisfy)시킨다고 하며, 이를

 

로 표기한다.

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

 

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

성질편집

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

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

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

    모순 명제   논리곱   비함의   역비함의   부정 논리합       실질적 동치  
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
    항진 명제   부정 논리곱   실질적 함의   역함의   논리합       배타적 논리합  
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개)
    •  
    •  
  • 크기 2 (총 18개)
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
  • 크기 3 (총 6개)
    •  
    •  
    •  
    •  
    •  
    •  
  • 크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다.

각주편집

  1. Srivastava, S. M. (2008). 《A Course on Mathematical Logic》. Universitext (영어). New York, NY: Springer. ISBN 978-0-387-76275-3. LCCN 2008920049. doi:10.1007/978-0-387-76277-7. 
  2. Wernick, William (1942년 1월). “Complete Sets of Logical Functions”. 《Transactions of the American Mathematical Society》 (영어) 51 (1): 117-132. ISSN 0002-9947. JSTOR 1989982. 

외부 링크편집

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