논리식

3. 명제 논리

명제 논리는 명제를 기본 단위로 다루는 논리 체계이다. 명제 논리에서 논리식(명제식)은 명제 변수와 논리 연결사(¬, ∧, ∨, →, ↔)를 사용하여 구성된다.

3. 1. 명제 논리의 구문론

• 각 명제 변수는 그 자체로 공식이다.
• φ가 공식이면, ¬φ는 공식이다.
• φ와 ψ가 공식이고 •가 임의의 이항 연결사이면, ( φ • ψ)는 공식이다. 여기서 •는 통상적인 연산자 ∨, ∧, →, ↔ 등이 될 수 있다(하지만 이에 제한되지 않는다).

4. 술어 논리

명제 논리를 확장한 술어 논리는 대상, 술어, 함수, 양화사(∀, ∃)를 사용하여 더 복잡한 문장을 표현할 수 있다. 술어 논리에서 논리식은 원자 논리식으로부터 논리 연산을 유한 번 적용하여 얻을 수 있는 문자열로 정의되며, 이는 보통 재귀적으로 정의된다.

4. 1. 술어 논리의 구문론

5. 원자식과 개방식

원자식은 논리 연결사나 양화사를 포함하지 않는 논리식이다.^[14] 명제 논리에서 원자식은 명제 변수이다. 술어 논리의 경우, 원자는 술어 기호와 해당 인수로 구성되며, 각 인수는 항이다.^[14]

개방식은 양화사를 제외하고 논리 연결사만 사용하여 원자식을 결합하여 형성된다.^[14]

6. 닫힌식

'''닫힌 공식'''은 '''기저 공식''' 또는 '''문장'''이라고도 하며, 자유롭게 나타나는 변수가 없는 공식이다. 만약 '''A'''가 일차 논리 언어의 공식이고, 여기서 변수 $v\_1,\; \backslash cdots,\; v\_n$가 자유롭게 나타난다면, $\backslash forall\; v\_1\; \backslash cdots\; \backslash forall\; v\_n$가 앞에 붙은 '''A'''는 '''A'''의 ''전체 폐쇄''이다.

7. 논리식의 속성

• 언어 $\backslash mathcal\{Q\}$의 논리식 '''A'''가 $\backslash mathcal\{Q\}$의 모든 해석에 대해 참이면 ''타당''하다.
• 언어 $\backslash mathcal\{Q\}$의 논리식 '''A'''가 $\backslash mathcal\{Q\}$의 어떤 해석에 대해 참이면 ''만족''하다.
• 산술 언어의 논리식 '''A'''가 결정 가능 집합을 나타내는 경우, 즉 '''A'''의 자유 변수에 대한 대입이 주어졌을 때, 결과로 나온 '''A'''의 인스턴스가 증명 가능하거나 그 부정이 증명 가능하다고 말해주는 유효 방법이 있으면 ''결정 가능''하다.

8. 용어의 사용

초창기 수학 논리 연구에서 '논리식'이라는 용어는 기호로 이루어진 모든 문자열을 가리켰으나, 현대에는 잘 구성된 논리식만을 의미하는 경우가 많다.^[15] 몇몇 저자들은 단순히 '공식'이라고도 표현한다.^{[16][17][18][19]} 특히 컴퓨터 과학 분야에서 수학적 소프트웨어를 사용하는 경우, '논리식'이라는 용어는 대수적 개념만을 나타내고, 구체적인 문자열 표현 방식은 표기법 문제로 간주하는 경향이 있다.

'잘 구성된 논리식(well-formed formula, WFF)'이라는 표현은 학술적인 용어 외에도 대중문화에서 사용되기도 한다. 예를 들어, 레이먼 앨런이 예일 대학교 로스쿨에 재학 중에 개발한 학술 게임 "WFF 'N PROOF"는 WFF라는 용어를 활용한 말장난을 사용한다.^[20] 이 게임은 어린이들에게 기호 논리의 원리를 가르치기 위해 설계되었으며, 폴란드 표기법을 사용한다.^[21] 게임의 이름은 예일 대학교의 응원가로 사용된 무의미한 단어인 ''휘펀푸프''에서 유래했다.^[22]

참조

_[1] 서적
_[2] 서적 Introduction to Logic https://books.google[...] Routledge 2002-09-11
_[3] 서적 Discrete Mathematics Using a Computer https://books.google[...] Springer Science & Business Media 2013-04-17
_[4] 서적 Symbolic Logic: Syntax, Semantics, and Proof https://books.google[...] Rowman & Littlefield 2013
_[5] 서적 Essentials of Symbolic Logic - Third Edition https://books.google[...] Broadview Press 2008-03-17
_[6] 서적 A Pocket Guide to Formal Logic Broadview Press 2022-10-24
_[7] 서적 Discrete Algorithmic Mathematics, Third Edition https://books.google[...] CRC Press 2005-01-21
_[8] 서적 The Philosopher's Dictionary - Third Edition https://books.google[...] Broadview Press 2002-05-06
_[9] 서적 The Relational Database Dictionary, Extended Edition https://books.google[...] Apress 2008-10-14
_[10] 서적 The New Relational Database Dictionary: Terms, Concepts, and Examples https://books.google[...] "O'Reilly Media, Inc." 2015-12-21
_[11] 서적 Essentials of Symbolic Logic https://books.google[...] Broadview Press 1998-12-10
_[12] 간행물 2016
_[13] 서적 First-order logic and automated theorem proving https://books.google[...] Springer 1996
_[14] 서적 Handbook of the history of logic https://books.google[...]
_[15] 문서 Introduction to mathematical logic 1996
_[16] 서적 Principles of Mathematical Logic Chelsea, New York 1950
_[17] 서적 A shorter model theory Cambridge University Press 1997
_[18] 서적 Handbook of Mathematical Logic North-Holland, Amsterdam 1982
_[19] 서적 Mathematical Logic: A Course with Exercises Oxford University Press 2000
_[20] 문서 2002
_[21] 문서
_[22] 문서 1965