CNF

명제 논리나 1차 논리에서, 논리식은 논리 연산자(논리곱(AND, ∧), 논리합(OR, ∨), 부정(NOT, ¬) 등)와 변수(또는 원자 명제)를 결합하여 만들어진다. 이러한 논리식은 매우 복잡한 형태를 가질 수 있기 때문에, 이를 표준화된 형태로 변환하여 처리의 편의성과 효율성을 높이는 것이 중요하다. 이렇게 표준화된 형태를 정규형(Normal Form)이라고 한다.

주요 정규형에는 논리곱 표준형(Conjunctive Normal Form, CNF)과 논리합 표준형(Disjunctive Normal Form, DNF)이 있다. CNF는 하나 이상의 절(Clause)이 논리곱(∧)으로 연결된 형태이다. 각 절은 하나 이상의 리터럴(Literal)이 논리합(∨)으로 연결된 형태이다. 예를 들어, (A ∨ ¬B) ∧ (C ∨ D ∨ ¬E) ∧ (F)는 CNF이다. 반대로 DNF는 하나 이상의 항(Term)이 논리합(∨)으로 연결된 형태이며, 각 항은 리터럴의 논리곱(∧)이다. 예를 들어, (A ∧ ¬B) ∨ (C ∧ D) ∨ (¬E)는 DNF이다.

모든 명제 논리식은 논리적으로 동등한 CNF 또는 DNF로 변환할 수 있다[3]. 이 중 CNF는 특히 충족 가능성 문제(SAT)와의 밀접한 연관성 때문에 이론 및 응용 분야에서 더 널리 사용된다. SAT 문제는 주어진 CNF 논리식을 참으로 만드는 변수 값의 할당이 존재하는지 판별하는 문제로, 계산 복잡도 이론에서 최초의 NP-완전 문제로 증명되었다.

CNF는 명제 논리나 일차 논리의 논리식이 특정한 형태를 가질 때 붙여지는 이름이다. 구체적으로, 여러 개의 절이 논리곱(AND, ∧)으로 연결된 형태를 말한다. 각 절은 다시 하나 이상의 리터럴이 논리합(OR, ∨)으로 연결된 형태로 구성된다.

CNF의 일반적인 수학적 표현은 다음과 같다.

(절₁) ∧ (절₂) ∧ ... ∧ (절ₙ)

여기서 각 절은 (리터럴₁ ∨ 리터럴₂ ∨ ... ∨ 리터럴ₘ)의 형태를 가진다. 리터럴은 명제 변수 또는 그 부정(NOT, ¬)이다. 예를 들어, 명제 변수 A, B, C가 있을 때, (A ∨ ¬B) ∧ (¬A ∨ C ∨ D) ∧ (B)는 CNF의 한 예이다.

CNF의 구조를 이해하는 데 중요한 점은 모든 논리식이 논리적으로 동등한 CNF로 변환될 수 있다는 사실이다[4]. 이 변환은 분배 법칙과 드 모르간의 법칙 등의 논리적 동치 관계를 반복적으로 적용하여 수행된다. CNF는 그 구조적 단순함 덕분에 컴퓨터 알고리즘, 특히 SAT 문제를 해결하는 SAT 솔버에서 입력 형식의 표준으로 널리 사용된다.

CNF는 자동 정리 증명 시스템의 핵심적인 입력 형식으로 사용된다. 자동 정리 증명은 주어진 가정(공리)으로부터 결론(정리)이 논리적으로 따라나는지 컴퓨터를 통해 자동으로 증명하는 과정이다. 많은 자동 정리 증명 시스템은 증명해야 할 명제를 논리식으로 표현한 후, 이를 먼저 CNF로 변환한다. CNF는 모든 논리식이 녀언의 논리합으로 이루어진 절들의 논리곱 형태이기 때문에, 알고리즘이 체계적으로 절을 처리하고 모순을 탐지하기에 매우 효율적이다. 이 변환 과정을 통해 복잡한 논리 구조가 표준화된 단순한 형태로 정리되어, 증명 탐색 알고리즘이 적용 가능해진다.

CNF의 가장 유명한 활용 사례는 충족 가능성 문제(SAT)이다. SAT 문제는 주어진 명제 논리 식을 참으로 만드는 변수 값의 할당이 존재하는지 판단하는 문제이다. 일반적인 논리식은 SAT 문제로 직접 다루기 어렵기 때문에, 먼저 논리식을 CNF로 변환한 후 SAT 솔버에 입력한다. SAT 문제는 최초로 증명된 NP-완전 문제[6]로, 이론적 중요성이 매우 크다. SAT 솔버는 CNF 형태의 식을 입력받아 그 충족 가능성을 판단하며, 효율적인 SAT 알고리즘의 발전은 CNF 표현에 크게 의존한다.

자동 정리 증명과 SAT 문제 해결은 밀접하게 연관되어 있다. 한 명제의 타당성을 증명하는 것은 그 부정의 불만족성을 증명하는 것, 즉 부정 명제를 CNF로 변환한 후 그 식이 불만족함을 SAT 솔버로 확인하는 것과 동일하다. 이 접근법은 모델 검증, 정형 검증, 계획 문제 및 전제 조건 추론 등 다양한 분야에서 실제로 적용된다. 따라서 CNF는 복잡한 논리 문제를 컴퓨터가 처리 가능한 표준 형식으로 단순화하는 데 필수적인 중간 표현 언어 역할을 한다.

CNF는 복잡한 시스템의 정확성을 수학적으로 검증하는 형식 검증 분야에서 핵심적인 입력 형식으로 사용된다. 특히 회로 설계와 소프트웨어 공학에서 시스템의 명세나 설계가 특정 속성을 만족하는지, 또는 결함이 존재하지 않는지를 증명하거나 반례를 찾는 데 활용된다.

하드웨어 검증에서는 집적 회로나 프로세서 설계의 논리적 정확성을 검증하는 데 CNF가 널리 쓰인다. 설계를 부울 함수로 모델링한 후 CNF로 변환하면, SAT 솔버를 이용해 특정 입력 조건에서 오류가 발생하는지(예: 두 신호가 동시에 활성화되는 경우)를 효율적으로 확인할 수 있다. 이는 제조 전 설계 오류를 발견하여 막대한 비용 손실을 방지하는 데 기여한다.

소프트웨어 검증에서는 프로그램의 코드나 명세를 정적 분석 도구를 통해 CNF 형태의 제약 조건으로 변환한다. 이를 통해 메모리 누수, 경쟁 조건, 또는 특정 안전 속성 위반 여부를 자동으로 탐지할 수 있다. 예를 들어, 프로그램의 모든 실행 경로가 특정 불변식을 만족하는지 증명하는 문제는 CNF로 표현된 SAT 문제 또는 그 확장인 SMT 문제로 환원되어 해결된다.

이러한 검증 과정은 시스템의 신뢰성을 극대화하며, 자율 주행 자동차, 의료 기기, 항공 전자 장비 등 고신뢰성이 요구되는 분야에서 필수적인 절차가 되었다.

명제 논리와 1차 논리의 지식을 CNF 형태로 표현하는 것은 인공지능 분야, 특히 지식 기반 시스템과 자동 추론에서 핵심적인 단계이다. CNF는 복잡한 논리적 진술을 표준화된 절의 집합으로 변환하여, 컴퓨터가 효율적으로 처리하고 새로운 사실을 도출할 수 있게 한다.

지식 표현에서 CNF의 주요 역할은 지식 베이스를 구성하는 것이다. 자연어나 다른 형태로 표현된 규칙과 사실들은 먼저 논리식으로 번역된 후, Tseitin 변환이나 분배 법칙을 적용하여 CNF로 변환된다. 예를 들어, "비가 오면 길이 미끄럽다"와 "길이 미끄러우면 조심해야 한다"는 두 규칙은 CNF로 변환되어 지식 베이스에 저장된다. 이후 추론 엔진은 이 CNF 형태의 지식 베이스와 현재 상황(예: "비가 온다")을 결합하여 논리적 함의 관계를 검사하거나, 해결 원리를 적용해 새로운 결론(예: "조심해야 한다")을 자동으로 도출한다.

이러한 방식은 전문가 시스템, 자동 계획 시스템, 그리고 최근에는 정형 검증과 시맨틱 웹의 규칙 처리에도 광범위하게 활용된다. 특히 만족 가능성 문제 (SAT) 솔버의 발전으로, 대규모 CNF 형태의 지식 베이스를 대상으로 한 효율적인 추론이 가능해졌다. CNF는 복잡한 제약 조건을 표현하는 데도 적합하여, 스케줄링 문제나 퍼즐 (예: 스도쿠)의 규칙들을 CNF 절로 인코딩한 후 SAT 솔버를 통해 해답을 찾는 방식이 일반적이다.

Tseitin 변환은 주어진 임의의 명제 논리 논리식을 CNF로 변환하는 알고리즘으로, 변환 결과의 크기가 원래 논리식의 크기에 대해 선형적으로 증가한다는 특징을 가진다. 이는 분배 법칙을 이용한 변환에서 발생할 수 있는 지수적 폭발을 방지한다. 변환의 핵심은 원래 논리식에 존재하는 각각의 논리 연결자(∧, ∨, ¬ 등) 하위 식에 대해 새로운 보조 변수를 도입하고, 그 하위 식과 새 변수의 논리적 동치를 나타내는 절(clause)들의 집합을 생성하는 것이다.

구체적인 변환 과정은 다음과 같다. 먼저, 원래 논리식의 각 논리 연산을 수행하는 하위 식에 고유한 새로운 변수(예: x1, x2, ...)를 할당한다. 그런 다음, 각 연산에 대해 그 연산의 입력 변수(또는 하위 식을 대표하는 변수)와 출력 변수 사이의 관계를 정의하는 일련의 CNF 절을 생성한다. 예를 들어, z ≡ (x ∧ y)라는 하위 식이 있다면, 이는 (¬z ∨ x) ∧ (¬z ∨ y) ∧ (z ∨ ¬x ∨ ¬y)라는 세 개의 절로 변환된다. 이 과정을 모든 하위 식에 대해 재귀적으로 적용한 후, 최상위 식을 대표하는 변수 하나로 구성된 단위 절을 추가하여 완성한다.

이 변환의 결과는 원래 논리식과 충족 가능성이 동등하다. 즉, 원래 식이 참이 되게 하는 변수 값이 존재한다면, 변환된 CNF도 참이 되게 하는 (원래 변수들과 새 보조 변수들을 포함한) 값 할당이 존재하며, 그 역도 성립한다. Tseitin 변환은 SAT 솔버에 입력을 공급하기 위한 전처리 단계에서 널리 사용되며, 회로나 복잡한 제약 조건을 CNF 형태로 효율적으로 표현하는 데 필수적이다.

분배 법칙을 이용한 변환은 명제 논리나 일차 논리의 임의의 논리식을 CNF 형태로 바꾸는 가장 기본적이고 직관적인 방법이다. 이 방법은 논리식의 구조를 재귀적으로 탐색하며, 분배 법칙을 적용하여 논리합이 논리곱 위로 분배되도록 변환한다. 변환 과정은 일반적으로 다음 단계를 따른다.

먼저, 주어진 논리식에서 함의와 동치 연산자를 제거한다. 예를 들어, A → B는 ¬A ∨ B로, A ↔ B는 (¬A ∨ B) ∧ (A ∨ ¬B)로 바꾼다. 다음으로, 드 모르간의 법칙을 적용하여 부정 연산자가 논리 변수에 직접 적용되도록 한다. 예를 들어, ¬(A ∧ B)는 ¬A ∨ ¬B로, ¬(A ∨ B)는 ¬A ∧ ¬B로 변환한다. 마지막으로, 분배 법칙 A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)을 반복적으로 적용하여 전체 식이 절들의 논리곱 형태, 즉 CNF가 되도록 한다.

이 방법은 개념적으로 이해하기 쉽지만, 변환 결과 생성되는 CNF의 크기가 원래 논리식에 비해 기하급수적으로 커질 수 있다는 단점이 있다. 특히, 논리곱이 논리합 안에 중첩된 형태의 식에 분배 법칙을 적용하면 절의 수가 폭발적으로 증가한다. 다음은 간단한 예시와 변환 과정을 보여주는 표이다.

따라서 분배 법칙을 이용한 변환은 이론적 설명이나 소규모 문제에 적합하지만, 실제 SAT 문제 해결이나 대규모 하드웨어 검증에서는 Tseitin 변환과 같이 새로운 변수를 도입하여 식의 크기 증가를 선형으로 제한하는 효율적인 알고리즘이 더 널리 사용된다.

DPLL 알고리즘은 충족 가능성 문제(SAT)를 해결하기 위한 고전적이면서도 효율적인 알고리즘이다. 이 알고리즘은 데이비스(Davis), 퍼트넘(Putnam), 로제먼(Logemann), 러블랜드(Loveland)의 이름을 따서 명명되었으며, 1960년대 초에 데이비스-퍼트넘 알고리즘을 개선하여 개발되었다[8]. 이 알고리즘은 주어진 CNF 논리식의 충족 가능성을 결정하고, 만족하는 경우 그 진리값 할당을 찾는 것을 목표로 한다.

알고리즘의 핵심은 결정(decision), 단위 절 전파(unit propagation), 순수 문자 규칙(pure literal rule), 그리고 백트래킹(backtracking)의 조합이다. 먼저, 알고리즘은 아직 값이 할당되지 않은 변수 중 하나를 선택하여 참 또는 거짓으로 결정한다. 그 후, 단위 절 전파를 수행한다. 단위 절은 아직 할당되지 않은 변수가 하나만 남은 절을 의미하며, 이 경우 해당 변수는 절이 참이 되도록 강제적으로 값이 할당된다. 이 과정은 더 이상 단위 절이 없을 때까지 반복된다. 또한, 모든 절에서 같은 극성(모두 긍정적이거나 모두 부정적)으로만 나타나는 순수 문자는 참으로 설정하여 절을 간소화한다. 만약 어떤 절이 거짓이 되면(모든 리터럴이 거짓인 충돌이 발생하면), 알고리즘은 가장 최근의 결정 지점으로 돌아가서(백트래킹) 반대 값을 시도한다. 이 과정을 통해 모든 변수에 값이 할당되어 충족하는 모델을 찾거나, 모든 가능한 탐색 공간을 확인한 후 공식이 불만족함을 증명할 때까지 계속된다.

DPLL 알고리즘의 성능은 변수 결정 순서(decision heuristic)와 효율적인 데이터 구조에 크게 의존한다. 다음은 알고리즘의 기본적인 의사코드 흐름을 보여준다.

DPLL은 이후 더 강력한 CDCL 알고리즘의 기반이 되었으며, 현대의 고성능 SAT 솔버들도 여전히 그 기본 골격을 유지하고 있다. 이 알고리즘은 이론적 완전성과 실제 적용 가능성 사이의 균형을 잘 보여주는 예시이다.

CDCL(Conflict-Driven Clause Learning) 알고리즘은 현대 SAT 솔버의 핵심을 이루는 완전한(complete) 결정 절차이다. 이 알고리즘은 DPLL 알고리즘의 기본적인 백트래킹 구조를 기반으로 하지만, 충돌 분석과 절 학습이라는 새로운 개념을 도입하여 성능을 획기적으로 향상시켰다. CDCL은 단순히 충돌이 발생하면 되돌아가는 것이 아니라, 그 충돌의 원인을 분석하여 새로운 절을 CNF 공식에 추가함으로써 동일한 충돌을 반복하지 않도록 한다.

알고리즘의 주요 단계는 결정(Decision), 전파(Propagation), 충돌 분석(Conflict Analysis), 절 학습(Clause Learning), 백점프(Backjumping)로 구성된다. 먼저, 알고리즘은 아직 값이 할당되지 않은 변수 중 하나에 진리값(참 또는 거짓)을 결정한다. 이 결정은 단위 절 전파(Unit Propagation)를 유발하며, CNF 내 다른 절들의 진리값을 논리적으로 추론하여 추가적인 변수 할당을 만든다. 만약 어떤 절의 모든 리터럴이 거짓이 되어 충돌이 발생하면, 알고리즘은 충돌 분석 단계로 들어간다.

충돌 분석은 현재 충돌에 이르게 한 결정들의 집합을 탐색하여 그 원인을 규명한다. 분석 결과는 충돌의 근본 원인을 포착하는 새로운 절, 즉 학습된 절(Learned Clause)로 표현된다. 이 절은 원래의 CNF 공식에 추가되어 이후 탐색에서 동일한 실수를 방지하는 지식이 된다. 이후 알고리즘은 학습된 절에 기반하여 백점프를 수행한다. 이는 단순히 직전 결정으로 돌아가는 것이 아니라, 학습된 절이 만족되기 위해 필요한 수준까지 결정 스택을 되감는 것이다. 이 과정은 충돌이 없이 모든 변수가 할당되거나(만족 가능), 가능한 모든 결정을 탐색했음에도 충돌이 지속되면(만족 불가능) 종료된다.

CDCL 알고리즘의 도입은 SAT 문제 해결 분야에 혁명을 가져왔으며, 이를 통해 산업적 규모의 복잡한 문제들도 효율적으로 해결할 수 있게 되었다. 학습 절 관리 전략, 재시작(restart) 전략, 효율적인 변수 선택 휴리스틱과 결합되어 오늘날 가장 강력한 SAT 솔버들의 기반을 이룬다.

CNF는 복잡한 논리식을 다루기 위한 표준 형식이지만, 변환 과정에서 절의 수와 각 절 내 리터럴의 수가 급격히 증가할 수 있다. 이는 SAT 솔버의 성능에 직접적인 영향을 미치므로, 솔버의 효율성을 높이기 위해 CNF 공식을 간소화하는 기법들이 개발되었다.

주요 간소화 기법으로는 순수 리터럴 제거, 단위 절 전파, 하위 절 제거 등이 있다. 순수 리터럴 제거는 특정 리터럴이 전체 공식에서 오직 긍정적 또는 부정적인 형태로만 나타날 경우, 그 리터럴을 참으로 설정하고 해당 리터럴을 포함하는 모든 절을 제거하는 방법이다. 단위 절 전파는 리터럴 하나만으로 구성된 절(단위 절)이 존재할 경우, 그 리터럴의 값을 참으로 고정시키고, 그 리터럴과 모순되는 리터럴을 다른 절들에서 제거하는 과정이다. 하위 절 제거는 한 절의 모든 리터럴이 다른 절에 포함되어 있을 경우(즉, 하위 절인 경우), 더 큰 절을 제거하는 최적화이다.

이러한 기법들은 대부분의 현대 CDCL 알고리즘 기반 SAT 솔버에 전처리 또는 사전 처리 단계로 통합되어 있다. 또한, 절의 데이터 구조를 효율적으로 관리하고 중복 검색을 최소화하기 위한 다양한 휴리스틱과 데이터 구조(예: 감시 리터럴)가 사용된다. 간소화를 통해 공식의 크기를 줄이고 구조를 단순화함으로써, 솔버의 탐색 공간을 축소하고 실행 시간을 크게 단축시킬 수 있다.

MaxSAT는 주어진 CNF 논리식에서 만족시킬 수 있는 최대 절의 개수를 찾는 최적화 문제이다. 전통적인 SAT 문제가 모든 절을 만족시키는 변수 할당의 존재 여부를 묻는 결정 문제인 반면, MaxSAT는 일부 절이 거짓이 될 수 있음을 허용하며, 만족되는 절의 수를 최대화하는 것을 목표로 한다. 이는 현실 세계의 많은 문제가 완벽한 해결책보다는 최선의 타협점을 요구하는 경우에 유용하게 적용된다.

Weighted MaxSAT는 MaxSAT의 일반화된 형태로, 각 절에 가중치가 부여된다. 문제의 목표는 만족된 절들의 가중치 합을 최대화하는 변수 할당을 찾는 것이다. 이는 다양한 제약 조건들이 서로 다른 중요도를 가지는 상황을 모델링할 수 있게 해준다. 예를 들어, 시스템 설계에서 '반드시 지켜야 하는' 핵심 요구사항과 '가급적 지켜졌으면 하는' 선호 사항을 구분하여 표현할 수 있다.

MaxSAT와 Weighted MaxSAT 문제를 해결하기 위한 전용 솔버들이 개발되어 왔다. 이들은 대체로 SAT 솔버를 핵심 엔진으로 사용하지만, 만족되지 못한 절(즉, 위반된 제약)을 최소화하거나 가중치 합을 최대화하기 위한 추가적인 논리와 검색 전략을 포함한다. 일반적인 접근법에는 만족되지 않은 절에 대한 패널티를 점진적으로 증가시키거나, 가중치를 고려한 분기 결정 전략을 사용하는 방법 등이 있다.

이들의 주요 응용 분야는 다음과 같다.

MaxSAT 및 Weighted MaxSAT는 NP-난해 문제에 속하지만, 현대의 전용 솔버들은 실용적인 규모의 많은 문제 인스턴스를 효율적으로 해결할 수 있다. 이는 조합 최적화와 제약 조건 만족 문제 분야에서 강력한 도구로 자리 잡았다.