Semantics for the minimal well-determined logic

"만약"과 "그리고"의 논리: 진리의 땅에서 펼쳐지는 탐정 이야기

당신이 미스터리를 풀려는 탐정이라고 상상해 보세요. 하지만 지문이나 알리바이 대신, 당신의 단서는 문장들입니다. 논리학의 세계에는 단순한 진술을 연결하여 복잡한 진리를 구축하는 방법을 연구하는 **명제 논리(propositional logic)**라는 특별한 분야가 있습니다. 이것을 추론의 문법이라고 생각하면 됩니다. 이 문법에서 가장 유명한 두 가지 도구는 연언(두 가지를 하나로 묶는 "그리고"라는 단어)과 함축("만약... 그렇다면"이라는 조건부 표현)입니다.

보통 우리가 추론할 때, 우리는 **전건 긍정(Modus Ponens)**이라는 황금률을 따릅니다. 이것은 우리 사고를 움직이는 엔진입니다: "만약 비가 온다면, 땅은 젖는다. 비가 온다. 그러므로 땅은 젖는다." 이 규칙은 너무나 자연스러워서 우리는 종종 이를 당연하게 여깁니다. 하지만 만약 이 규칙이 자동으로 작동한다고 가정하지 않는 논리 체계를 만들려고 한다면 어떨까요? 만약 "그리고"와 "만약"이 전체 시스템을 망가뜨리지 않으면서도 서로 잘 작동하게 만드는 데 필요한 절대적인 최소한의 규칙을 찾고자 한다면 어떨까요? 이것이 바로 이고르 고르부노프(Igor Gorbunov)와 미하일 리바코프(Mikhail Rybakov)가 이 논문에서 다루는 질문입니다. 그들은 "최소한의 잘 결정된 논리(minimal well-determined logic)"라고 부르는, 잘 작동하는 논리의 "최소화된" 버전을 찾고 있습니다. 즉, 이해할 수 있을 만큼 충분히 강하면서도, 우리가 의도하지 않은 것을 받아들이도록 강요하지 않는 시스템을 찾는 것입니다.

논문의 거대한 발견: 엔진 없는 논리

이 논문에서 저자들은 최소 잘 결정된 논리라고 부르는 매우 구체적이고 간소화된 버전의 논리를 조사합니다. 그들은 다음과 같은 질문으로 시작합니다: "'그리고'와 '만약'이 작동하게 만들기 위해 필요한 가장 작은 규칙 세트는 무엇인가?"

보통 논리학자들은 일련의 공리(시작점이 되는 진리)와 규칙(모로스 포넨스 같은)을 나열하여 시스템을 구축합니다. 저자들은 모로스 포넨스를 시작 규칙으로 상정하지 않고도 이 최소 논리를 정의하는 방법을 찾아냈습니다. 알고 보니, 시스템을 적절하게 설정하기만 하면 "A이면 B이고, A이다, 그러므로 B이다"라는 규칙이 다른 규칙들로부터 자연스럽게 발생한다는 사실을 발견했습니다. 이는 마치 매번 밀어야 하는 것이 아니라, 열쇠를 돌리면 스스로 시동이 걸리는 자동차를 만드는 것과 같습니다.

이 논리가 작동함을 증립하기 위해, 저자들은 이를 시각화하는 새로운 방법을 고안해야 했습니다. 그들은 하한 준영역(lower semilattice)과 최댓값 원소라는 수학적 구조에 기반한 의미론(semantics)(기호를 해석하는 방법)을 만들었습니다.

이를 시각화하는 방법은 다음과 같습니다: 블록으로 만든 피라미드를 상상해 보세요.

• 블록은 서로 다른 진술이나 아이디어를 나타냅니다.
• 피라미드의 모양은 이러한 아이디어들이 어떻게 연관되는지를 나타냅니다. 만약 두 블록을 결합하여 더 큰 블록을 만들 수 있다면, 그것이 당신의 "그리고"(연언)입니다.
• 맨 위의 블록은 "최댓값 원소"이며, 궁극적인 진리 또는 모든 것이 충족된 상태를 나타냅니다.

대부분의 논리 체계에서 "만약... 그렇다면"(함축)은 두 블록을 가져가서 새로운 블록을 뱉어내는 기계와 같습니다. 하지만 이 최소 논리에서 저자들은 "만약... 그렇다면"이 항상 동일한 방식으로 새로운 블록을 만들어내지는 않는다는 점을 깨달았습니다. 때때로 조건이 충족되지 않으면 기계는 그냥 가만히 있습니다. 그래서 그들은 "만약... 그렇다면"을 **부분 함수(partial function)**로 정의했습니다. 이것은 마치 올바른 동전을 넣어야만 작동하는 자판기와 같습니다. 만약 당신이 올바른 블록의 조합(첫 번째 블록이 피라미드 내에서 두 번째 블록에 "포함되거나 작다"는 조건)을 넣으면, 기계는 맨 위의 블록(참)을 줍니다. 만약 조건이 충족되지 않으면, 기계는 결과를 내놓지 않습니다. 즉, 정의되지 않은 상태가 됩니다. 이 "부분적"인 성질이 모로스 포넨스 규칙을 처음부터 강제하지 않고도 논리가 작동하게 만드는 핵심입니다.

놀라운 반전: 매우 빠르다!

여기서 이야기는 매우 흥미진진해집니다. 보통 논리를 뼈대만 남기고 깎아내면, 수학적으로 매우 복잡해지거나 규칙을 확인하는 것이 엄청나게 어려워질 것이라고 예상하기 쉽습니다. 당신은 "표준 규칙들을 제거하면, 어떤 문장이 참인지 판별하는 데 영원히 걸릴지도 몰라"라고 생각할 수도 있습니다.

하지만 저자들은 놀라운 사실을 발견했습니다: 사실 매우 빠릅니다.

그들은 주어진 문장이 이 최소 논리에서 "항진식"(항상 참인 문장)인지 확인하는 특정 알고리즘(컴퓨터를 위한 단계별 레시피)을 설계했습니다. 그들은 이 알고리즘이 다항 시간(polynomial time) 안에 실행된다는 것을 증명했습니다.

이를 일상적인 용어로 설명하자면 이렇습니다: 당신에게 퍼즐이 있다고 상상해 보세요. 만약 퍼즐이 "어려운" 경우(많은 복잡한 논리 문제들처럼), 퍼즐을 푸는 데 걸리는 시간은 퍼즐이 커짐에 따라 기하급급수적으로 늘어납니다. 즉, 크기가 두 배가 되면 시간을 백만 배 더 오래 걸리게 만들 수도 있습니다. 하지만 이 최소 논리의 경우, 문제를 푸는 데 걸리는 시간은 단순히 완만한 곡선(예를 들어 크기의 제곱 정도)을 그리며 늘어납니다. 문장의 길이가 두 배로 길어져도, 컴퓨터는 백만 배 더 많은 일을 하는 것이 아니라 아주 조금의 작업량만 더 수행하면 됩니다.

저자들은 이 점에 놀랐습니다. 그들은 대부분의 "자연스러운" 논리들(고전 논리를 포함하는 논리들)이 컴퓨터가 빠르게 해결하기 매우 어려운 것으로 악명이 높다(coNP-hard)는 점에 주목했습니다. 그러나 이 최소화되고 간소화된 논리는, 그 기묘한 "부분적" 규칙들에도 불구하고, 컴퓨터가 처리하기에 실제로 매우 쉽습니다.

이것이 의미하는 바

이 논문은 단순히 "여기에 새로운 논리가 있다"라고 말하는 데 그치지 않습니다. 그것은 완전한 도구 상자를 제공합니다:

1. 새로운 정의: 그들은 표준적인 "A이면 B이다" 규칙을 가정하지 않고 이 논리를 구축하는 방법을 보여주었습니다.
2. 새로운 지도: 그들은 논리가 어떻게 작동하는지 설명하기 위해 "피라미드" 의미론(준영역)을 구축했습니다.
3. 증명: 그들의 지도가 규칙과 완벽하게 일치한다는 것을 증명했습니다(건전성과 완전성).
4. 속도 테스트: 이 시스템에서 문장이 참인지 확인하는 것이 계산적으로 쉽다는 것을 증명했습니다(다항 시간).

저자들은 또한 이 최소 논리가 하나의 토대라는 점을 지적합니다. 당신은 나중에 더 많은 규칙을 추가하여 더 강력한 논리를 만들 수 있지만, 이 깨끗하고 효율적인 기초에서 시작하게 됩니다. 그들은 심지어 이 논리가 고전 논리와 근본적인 방식으로 다르다는 점을 보여주었습니다. 즉, 고전 논리를 컴퓨터에게 어렵게 만드는 "어려운" 문제들을 이 논리는 포함하고 있지 않습니다.

요약하자면, 고르부노프와 리바코프는 논리 체계에서 가장 유명한 엔진을 제거했고, 그 결과 자동차가 여전히 잘 달린다는 것을 발견했을 뿐만 아니라, 그것이 믿을 수 없을 정도로 빠르게 달리는 스포츠카라는 사실까지 찾아냈습니다. 그들은 "만약"과 "그리고"에 대해 수학적으로 우아하면서도 계산적으로 효율적인 새로운 방식을 우리에게 제시했습니다.