전시실을 준비하는데 운영 지침을 아무리 맞춰도 장치가 켜지지 않습니다. 담당자는 “규칙을 모두 지킬 수 없다”는 말만 듣습니다. 어떤 규칙끼리 충돌하는지 알면 수정할 곳을 좁힐 수 있겠지요. 여기서 필요한 것은 규칙 하나를 곧바로 잘못이라고 지목하는 일이 아니라, 함께 놓았을 때 불가능해지는 묶음을 찾는 일입니다.
연구를 읽는 두 가지 질문
불가능하다는 답 다음에는 무엇이 필요할까?
Liffiton과 Sakallah는 제약 조건을 만족시킬 수 없을 때 그 이유를 작은 부분집합으로 찾는 문제를 다룹니다. 최소 불충족 부분집합(MUS)은 그 자체로 만족 불가능하면서, 어느 조건 하나를 제거하면 만족 가능해지는 묶음입니다. 여기서 최소는 더 줄일 수 없다는 뜻이며, 모든 후보 중 조건 수가 가장 적다는 뜻과 구분해야 합니다. [1]
왜 한 묶음을 찾는 것으로 끝나지 않을까?
논문은 이런 묶음을 모두 찾는 CAMUS의 이론과 알고리즘을 제시합니다. 전체 규칙 안에 충돌 묶음이 여러 개라면 한 묶음의 문제를 고쳐도 다른 충돌이 남을 수 있습니다. 따라서 하나의 설명을 발견한 것과 시스템 전체가 작동하도록 수리한 것은 다른 성취입니다. [1]
조명과 팬의 네 가지 상태
LTCT의 가상 전시실에는 조명 A와 팬 B가 있습니다. ① 조명은 켠다, ② 조명을 켜면 팬도 켠다, ③ 팬은 끈다, ④ 조명은 켜거나 끈다는 규칙을 놓았습니다. 장치 상태는 둘 다 끔, 팬만 켬, 조명만 켬, 둘 다 켬의 네 가지뿐입니다. 아래 진리표는 각 상태를 빠짐없이 검사합니다.
먼저 ④만 빼 보세요. 가능한 상태는 여전히 0개입니다. 이제 ①·②·③ 중 어느 하나를 빼면 적어도 한 상태가 살아납니다. 예를 들어 ②를 빼면 조명만 켜는 상태가 가능합니다. 이로써 세 규칙은 더 줄일 수 없는 충돌 묶음이 됩니다.
이 결과가 ②를 폐기하라는 운영 지시는 아닙니다. 팬을 켜야 하는 이유가 안전 문제인지, ③이 일시적인 정비 조건인지 알아야 수정 대상을 고를 수 있습니다. 논리는 충돌 위치를 좁혀 주지만 어느 목적을 포기할지는 별도의 판단입니다.
규칙을 하나씩 빼 보세요
체크를 풀어 규칙을 하나씩 빼 보세요. 네 가지 장치 상태 중 살아남는 경우가 있는지 확인합니다.
| 조명 A | 팬 B | 규칙 충족 |
|---|---|---|
| 꺼짐 | 꺼짐 | × 불가능 |
| 꺼짐 | 켜짐 | × 불가능 |
| 켜짐 | 꺼짐 | × 불가능 |
| 켜짐 | 켜짐 | × 불가능 |
가능한 상태 0개 · 모순은 있지만, 불필요한 규칙이 남아 있습니다.
어디까지 말할 수 있을까요?
- 활동은 두 변수의 네 상태를 전부 검사하는 작은 예시입니다. 원문 알고리즘의 성능 비교를 재현하지 않습니다.
- 이 예시의 충돌 묶음은 하나입니다. 실제로 여러 묶음이 있을 때도 규칙 하나만 빼면 모두 해결된다고 일반화할 수 없습니다.
원문에 근거한 한계와 LTCT의 적용 범위 검토입니다. [1]
교육 현장과 연결해 보면
수업 활동에서는 모순이 있다는 답에 더해, 남긴 규칙과 삭제한 규칙을 기록하도록 할 수 있습니다. 어떤 규칙을 빼도 가능한 상태가 생긴다는 근거를 한 줄씩 붙이면 최소성의 의미가 분명해집니다.
학습자는 먼저 진리표로 가능한 상태를 찾고, 그다음 운영 목적을 읽어 수정안을 제안합니다. 논리적 일관성 점검과 실제 규정 변경의 이유를 구분하는 연습입니다.
④를 뺐는데도 모순이면, ④는 아무 의미가 없는 규칙일까요?
생각을 비교할 해설 펼치기
현재의 고전 명제논리 해석에서 ④는 항상 참이므로 상태를 더 제한하지 않습니다. 그래서 이번 모순의 원인은 아닙니다. 다만 실제 문서에서는 용어를 설명하거나 가능한 상태를 정하는 역할이 있을 수 있습니다. 형식화된 조건의 기능과 문장의 모든 쓰임을 같은 것으로 보면 안 됩니다.
원문과 출처 정보
한국어 제목은 이해를 돕기 위한 LTCT 번역입니다. 한글 제목 뒤 괄호에 원제를 함께 표기했습니다. 저자·학술지·원문 버전은 원문 서지정보를 기준으로 확인할 수 있습니다.
제약 조건의 최소 불충족 부분집합을 계산하는 알고리즘 (Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints)
Mark H. Liffiton & Karem A. Sakallah (2008). Journal of Automated Reasoning, 40(1), 1–33.
- 자료 성격
- 동료심사 학술지 논문
- 읽은 버전
- 저자 공개 원고(2007-10-10 표시), 2008년 게재 서지 대조
- 확인 범위
- 저자 공개 본문의 서론, MUS 정의와 CAMUS의 목표 확인
- 원문 확인일
이 글은 한국어 해설이며 원문 전문 번역이 아닙니다. 도식과 활동의 제작·재구성 범위는 각 그림과 본문에 표시했습니다. 자료 선정과 출처 기준
같은 연구 흐름에서 이어 읽기
같은 원문, 저자·연구 흐름, 공통 개념 태그를 기준으로 연결한 관련 해설입니다.