방송대 인공지능 6강: 술어논리와 도출연역
“모든 회원은 대출할 수 있다”라는 규칙과 “민지는 회원이다”라는 사실에서 결론을 얻으려면, 자연어를 어떤 논리식으로 바꾸고 컴퓨터는 어떤 절차로 모순을 찾아야 할까요? 이 글은 명제논리의 진리표에서 출발해 술어·한정기호·단일화를 거쳐 도출연역으로 정리를 증명하는 전 과정을 하나의 변환 파이프라인으로 연결합니다.
논리적 지식표현은 문장을 증명 가능한 형태로 바꾸는 일이다
논리에 의한 지식표현에서는 문장의 뜻을 단순히 저장하지 않는다. 무엇이 참인지 판정할 수 있는 논리식으로 표현하고, 이미 참이라고 받아들인 전제에서 새로운 결론을 이끌어 낸다. 이 과정은 크게 세 층으로 나눌 수 있다.
| 층 | 핵심 질문 | 대표 도구 | 결과 |
|---|---|---|---|
| 표현 | 문장을 어떤 기호로 적을 것인가? | 명제, 술어, 객체, 한정기호 | 정형식 |
| 정규화 | 추론 규칙이 다루기 쉬운 꼴인가? | 함의 제거, 부정 이동, 연언표준형, 절 분리 | 절의 집합 |
| 추론 | 전제들이 목표를 논리적으로 보장하는가? | 단일화, 도출, 반박에 의한 증명 | 도출절 또는 모순 |
판단 핵심: 명제논리와 술어논리의 차이만 외우기보다, “개별 문장의 참·거짓이면 충분한가, 객체와 일반 규칙까지 표현해야 하는가?”를 먼저 묻는다. 뒤의 절 변환과 도출은 앞에서 만든 표현을 실제 증명에 사용하는 단계다.
명제논리는 문장 전체를 참 또는 거짓인 단위로 다룬다
명제는 참과 거짓을 구분할 수 있는 문장이다. 더 분해하지 않는 최소 단위는 기본명제 또는 원소식이며 p, q처럼 나타낸다. 기본명제를 논리 연산자로 결합하면 합성명제가 된다.
| 연산 | 기호 | 읽는 법 | 참이 되는 기준 |
|---|---|---|---|
| 부정 | ~p | p가 아니다 | p가 거짓 |
| 연언 | p ∧ q | p이고 q이다 | 둘 다 참 |
| 선언 | p ∨ q | p이거나 q이다 | 하나 이상 참 |
| 함의 | p → q | p이면 q이다 | p가 참이고 q가 거짓인 경우만 제외 |
| 동치 | p ↔ q | p와 q의 진릿값이 같다 | 둘의 진릿값이 같음 |
조건명제 p → q에서 유일한 거짓은 전건 p가 참인데 후건 q가 거짓인 경우다. 전건이 거짓이면 조건을 어긴 사례가 아니므로 전체 조건명제는 참으로 정의한다. 따라서 p → q와 ~p ∨ q는 모든 진릿값 조합에서 결과가 같아 논리적으로 동치다.
오개념 교정: “p이면 q”를 “q이면 p”로 뒤집을 수 없다. 또한 p → q와 p ∧ q도 다르다. 전자는 p가 거짓일 때 참일 수 있지만, 후자는 두 명제가 모두 참이어야 한다.
정형식은 기호를 임의로 늘어놓지 못하게 하는 문법이다
명제논리의 정형식은 재귀적으로 정의된다. 기본명제는 논리식이고, p가 논리식이면 ~p도 논리식이며, p와 q가 논리식이면 p → q도 논리식이다. 이 규칙으로 얻은 식만 논리식이다. 부정과 함의만으로도 p ∧ q ≡ ~(p → ~q), p ∨ q ≡ ~p → q처럼 다른 연산을 표현할 수 있으므로 이들은 논리 연산자의 완전집합을 이룬다.
표준형과 항진식은 식의 모양과 추론의 타당성을 점검한다
리터럴은 기본명제 또는 그 부정이다. 리터럴의 논리합을 절로 만들고 그 절들을 논리곱으로 연결하면 연언표준형(CNF)이다. 반대로 리터럴의 논리곱으로 된 절들을 논리합으로 연결하면 선언표준형(DNF)이다.
| 형식 | 바깥 연결 | 안쪽 절 | 예 |
|---|---|---|---|
| 연언표준형 | 절과 절을 ∧로 연결 | 리터럴을 ∨로 연결 | (p ∨ ~q) ∧ (~r ∨ s ∨ t) |
| 선언표준형 | 절과 절을 ∨로 연결 | 리터럴을 ∧로 연결 | (~p ∧ r) ∨ (~q ∧ s ∧ t) |
항진식은 기본명제의 진릿값과 관계없이 언제나 참인 논리식이다. p ∨ ~p뿐 아니라 {p ∧ (p → q)} → q도 항진식이다. 후자는 “p”와 “p이면 q”가 참이면 q가 참이라는 긍정논법의 타당성을 진리표 전체에서 확인한 식이다. 마찬가지로 {(p → q) ∧ (q → r)} → (p → r)는 조건의 연쇄가 타당함을 보인다.
연역은 전제를 근거로 결론을 필연적으로 끌어내는 추론이다. 긍정논법은 α와 α → β에서 β를, 부정논법은 ~β와 α → β에서 ~α를 얻는다. 후건을 긍정해 전건을 결론 내리거나 전건을 부정해 후건을 부정하는 것은 타당한 규칙이 아니다.
일반 규칙이 등장하면 문장 내부의 객체와 관계를 열어야 한다
명제논리에서 “소크라테스는 사람이다”를 p, “플라톤은 사람이다”를 q로 두면 두 문장 안에 공통으로 들어 있는 “사람”이라는 성질이 사라진다. “모든 사람은 죽는다”라는 규칙을 각 사람에게 적용하려면 문장을 더 세밀하게 분해해야 한다. 술어논리는 이를 술어(객체) 형식으로 표현한다.
Man(SOCRATES): 객체상수 SOCRATES가 사람이라는 성질을 갖는다.On(X, Y): 두 객체 X와 Y 사이에 “X가 Y의 바로 위에 있다”라는 관계가 있다.Korean(father(철수)): 함수father(철수)가 가리키는 객체가 한국인이다.
술어의 괄호 안에는 객체상수, 객체변수, 함수가 올 수 있다. 상수는 특정 객체를 지칭하고, 변수는 정의역의 여러 객체를 대신하며, 함수는 주어진 객체로부터 다른 객체를 지칭하는 항을 만든다. 함수는 참·거짓을 말하는 술어가 아니라 객체를 돌려준다는 점이 중요하다.
판단 핵심: father(철수)는 하나의 객체를 나타내는 항이고, Father(철수, 영호)는 두 객체 사이의 관계가 참인지 묻는 원소식이다. 괄호 모양만 보고 둘을 같은 종류로 판단하지 않는다.
한정기호는 변수가 가리키는 범위를 결정한다
전칭기호 ∀는 정의역의 모든 원소에 대해 성립한다는 뜻이고, 존재기호 ∃는 조건을 만족하는 원소가 적어도 하나 있다는 뜻이다. “모든 새는 날개가 있다”는 ∀x(Bird(x) → HasWings(x))이고, “키가 크지 않은 농구선수가 있다”는 ∃x(BasketballPlayer(x) ∧ ~Tall(x))이다.
두 문장의 연결자가 다른 이유에 주목해야 한다. 전칭 규칙은 “x가 새라는 조건을 만족하면 날개가 있다”이므로 함의를 쓴다. 존재 주장은 한 객체가 두 조건을 동시에 만족해야 하므로 연언을 쓴다. ∀x(Bird(x) ∧ HasWings(x))라고 쓰면 정의역의 모든 것이 새라고 주장하는 전혀 다른 문장이 된다.
한정기호의 부정은 기호를 바꾸고 술어 안으로 이동한다
- ~∃x P(x) ≡ ∀x ~P(x): P인 것이 하나도 없다는 말은 모든 것이 P가 아니라는 말과 같다.
- ~∀x P(x) ≡ ∃x ~P(x): 모두 P라는 말이 거짓이면 P가 아닌 반례가 적어도 하나 있다.
- ∀x(P(x) ∧ Q(x)) ≡ (∀x P(x)) ∧ (∀y Q(y))
- ∃x(P(x) ∨ Q(x)) ≡ (∃x P(x)) ∨ (∃y Q(y))
경계 사례: ∃x(P(x) ∧ Q(x))를 (∃x P(x)) ∧ (∃y Q(y))로 나누면 안 된다. 오른쪽은 P인 객체와 Q인 객체가 서로 달라도 참이지만, 왼쪽은 같은 한 객체가 두 성질을 모두 가져야 한다.
항과 정형식은 술어논리의 문법을 완성한다
객체상수와 객체변수는 항이다. t₁, …, tₙ이 항이고 f가 n항 함수기호이면 f(t₁, …, tₙ)도 항이며, 이 규칙으로 만든 것만 항이다. 참과 거짓은 정형식이고, 항을 인수로 갖는 원소식도 정형식이다. 정형식 P, Q에서 ~P, P → Q를 만들 수 있고, 변수 x를 ∀x P 또는 ∃x P로 한정할 수도 있다.
도출연역은 서로 반대인 리터럴을 지워 새 절을 만든다
도출연역(resolution)의 핵심은 두 부모절에 서로 보완적인 리터럴이 있을 때 그 쌍을 제거하고 나머지를 합쳐 도출절을 만드는 것이다. 예를 들어 ~P ∨ Q와 ~Q ∨ R에서 Q와 ~Q를 지우면 ~P ∨ R을 얻는다. P와 ~P를 도출하면 빈 절, 즉 false가 된다.
| 부모절 | 제거되는 쌍 | 도출절 |
|---|---|---|
| P, ~P ∨ Q | P와 ~P | Q |
| P ∨ Q, ~P ∨ Q | P와 ~P | Q |
| ~P, P | ~P와 P | false |
| ~P ∨ Q, ~Q ∨ R | Q와 ~Q | ~P ∨ R |
술어논리에서는 술어 이름뿐 아니라 인수도 일치해야 한다. Father(A,B)는 ~Father(C,D) ∨ Male(C)와 그대로 도출할 수 없다. 그러나 두 번째 절이 ~Father(x,y) ∨ Male(x)라면 치환 {x/A, y/B}로 두 원소식을 같게 만들 수 있다. 이처럼 변수에 항을 대입해 식을 일치시키는 과정을 단일화라고 한다.
실패 진단: 보완 리터럴의 술어와 인수 구조가 일치하지 않으면 도출할 수 없다. 상수가 서로 다른데 억지로 같은 값으로 바꾸는 것도 허용되지 않는다. 바꿀 수 있는 것은 변수이며, 하나의 치환은 같은 절 안의 해당 변수에 일관되게 적용해야 한다.
술어논리식은 아홉 단계를 거쳐 도출 가능한 절이 된다
도출 규칙은 논리합으로 된 절을 입력으로 받기 때문에 복잡한 술어논리식을 바로 사용할 수 없다. 강의의 절 분리 과정은 다음 순서를 따른다.
- 함의 제거: P → Q를 ~P ∨ Q로 바꾼다.
- 부정의 범위 축소: 드모르간 법칙과 한정기호 부정 등식을 써서 부정을 원소식 바로 앞까지 이동한다.
- 변수 표준화: 서로 다른 한정기호가 우연히 같은 변수 이름을 쓰지 않도록 이름을 바꾼다.
- 존재기호 제거: 존재변수를 스콜렘 상수 또는 앞선 전칭변수의 함수로 대체한다. 예컨대 x에 의존하는 존재변수는 g(x)로 나타낼 수 있다.
- 관두형으로 이동: 한정기호를 식의 앞부분에 모은다.
- 연언표준형 변환: 논리합을 논리곱에 대해 분배하여 “절들의 연언”으로 만든다.
- 전칭기호 제거: 남은 변수는 절에서 암묵적으로 전칭된 것으로 보고 기호를 생략한다.
- 연언기호 제거: 각 논리합을 독립된 절로 분리한다.
- 절별 변수 이름 분리: 서로 다른 절의 변수는 독립적이므로 같은 이름을 쓰지 않도록 표준화한다.
판단 핵심: 이 변환의 목적은 원래 식의 의미를 임의로 바꾸는 것이 아니라 도출 규칙이 처리할 수 있는 절 집합을 얻는 것이다. 특히 존재기호 제거에서 새 함수가 어떤 전칭변수에 의존하는지 놓치면 이후 증명의 의미가 달라진다.
정리 증명은 목표를 부정한 뒤 모순까지 거슬러 간다
도출연역에 의한 정리 증명은 직접 목표를 만드는 방식이 아니라 반박에 의한 증명이다. 증명할 정리 G를 부정한 ~G를 공리에 추가하고 모두 절로 변환한다. 도출 가능한 부모절을 반복해서 선택해 새 절을 만들며, 빈 절 false가 나오면 “공리와 ~G를 동시에 참으로 둘 수 없다”는 뜻이므로 원래 정리 G가 참임이 증명된다. 더 이상 새 절을 만들 수 없는데 모순이 없으면 그 절차에서는 증명에 실패한 것이다.
직접 만든 도서관 규칙으로 증명 흐름을 따라가 본다
정의역을 사람으로 두고 다음 지식을 가정하자.
- 규칙: 모든 회원은 대출 권한이 있다. ∀x(Member(x) → CanBorrow(x))
- 사실: 민지는 회원이다. Member(MINJI)
- 목표: 민지는 대출 권한이 있다. CanBorrow(MINJI)
규칙을 절로 바꾸면 ~Member(x) ∨ CanBorrow(x)이다. 목표의 부정 ~CanBorrow(MINJI)를 추가한다. 규칙절과 목표의 부정을 x ← MINJI로 단일화해 도출하면 ~Member(MINJI)를 얻는다. 이것을 사실 Member(MINJI)와 도출하면 false가 된다. 따라서 목표의 부정이 공리와 양립할 수 없고, CanBorrow(MINJI)가 증명된다.
강의의 블록 예제도 같은 구조다. On(A,B)와 On(B,TABLE), “바로 위이면 위에 있음”, “위에 있음은 추이적임”이라는 공리로부터 Above(A,TABLE)을 증명한다. 목표를 부정한 절에서 출발해 공리와 단일화하고, 관측 사실과 차례로 도출하면 마지막에 On(B,TABLE)과 그 부정이 만나 false가 된다.
자가 점검: 위 도서관 예제에서 사실 Member(MINJI)를 삭제하면 빈 절에 도달할 수 있는지 설명해 보자. 규칙은 회원인 경우의 결과만 말할 뿐 민지가 회원이라는 전제를 제공하지 않으므로 증명은 완성되지 않는다.
핵심 개념 정리
- 문장 전체의 진릿값만 필요하면 명제논리로 표현하고, 객체·관계·일반 규칙이 필요하면 술어논리로 확장한다.
- 표현의 문법은 항과 정형식이, 변수의 범위는 전칭·존재 한정기호가 결정한다.
- 추론 준비에서는 함의와 복잡한 한정 구조를 제거하고 연언표준형의 독립된 절들로 바꾼다.
- 추론 실행에서는 단일화로 인수를 맞춘 뒤 보완 리터럴을 제거해 새 절을 만든다.
- 정리 증명에서는 목표의 부정을 추가하고 도출을 반복해 빈 절이 생기는지 확인한다.
문제를 풀 때는 “자연어에서 객체와 조건을 구분한다 → 한정기호와 연결자를 정확히 선택한다 → 절 변환 순서를 지킨다 → 단일화 가능한 보완 리터럴을 찾는다 → 목표의 부정에서 모순까지 이어지는지 확인한다”라는 순서로 사고하면 표현 오류와 추론 오류를 함께 줄일 수 있습니다.
예상문제 10선
1. 명제논리의 조건명제 p → q가 거짓인 경우는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 전건의 약속과 후건의 결과가 함께 성립하므로 조건을 어기지 않는다.
- ② 오답: 전건이 거짓이면 조건을 위반한 사례가 아니므로 함의는 참이다.
- ③ 정답: 전건이 성립했는데 후건이 성립하지 않은 유일한 위반 사례다.
- ④ 오답: 전건이 거짓이므로 후건의 거짓만으로 조건명제를 거짓이라 할 수 없다.
2. 연언표준형에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 안쪽 절은 ∨, 절 사이의 바깥 연결은 ∧인 형태가 CNF다.
- ② 오답: 안쪽이 ∧이고 바깥이 ∨인 구조는 선언표준형이다.
- ③ 오답: 모든 진리배정에서 참인지는 항진식의 기준이며 식의 표준형과 다르다.
- ④ 오답: 정형식의 생성 규칙과 연언표준형의 구조 조건을 혼동했다.
3. “모든 새는 날개가 있다”를 가장 적절하게 표현한 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 새이면서 날개가 있는 객체가 하나 이상 있다는 존재 주장에 그친다.
- ② 오답: 정의역의 모든 객체가 새라고까지 주장하므로 원문보다 강하다.
- ③ 오답: 존재기호 아래 함의는 새가 아닌 객체 하나만 있어도 쉽게 참이 될 수 있다.
- ④ 정답: 정의역의 모든 x에 대해 x가 새라는 조건이면 날개가 있다는 규칙을 정확히 나타낸다.
4. 함수기호와 술어기호를 올바르게 구분한 설명은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 함수는 정의역의 객체를 나타내는 항을 만들고 술어가 진릿값을 갖는다.
- ② 정답: 함수항을 술어의 인수로 넣어 하나의 원소식을 만드는 구조를 정확히 구분했다.
- ③ 오답: 항인 인수들에 함수기호를 적용하면 한정기호 없이도 함수항이 된다.
- ④ 오답: 술어의 인수에는 상수뿐 아니라 변수와 함수항도 올 수 있다.
5. ~∀x P(x)와 논리적으로 동치인 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 모두가 P가 아니라는 주장은 “모두 P”의 부정보다 더 강하다.
- ② 정답: 모든 객체가 P라는 주장이 거짓이면 P가 아닌 반례가 적어도 하나 존재한다.
- ③ 오답: 이는 이중 변환하면 ∀x P(x)가 되어 원래 식의 반대다.
- ④ 오답: P인 객체의 존재는 P가 아닌 반례의 존재를 보장하지 않는다.
6. 부모절 ~P ∨ Q와 ~Q ∨ R을 도출했을 때 얻는 절은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 첫 부모절에 남는 리터럴은 P가 아니라 ~P다.
- ② 오답: Q는 ~Q와 보완쌍을 이루어 제거되므로 결과에 남지 않는다.
- ③ 오답: ~Q도 Q와 함께 제거되며 첫 절의 ~P를 누락했다.
- ④ 정답: 보완적인 Q와 ~Q를 지우고 두 부모절의 나머지 ~P와 R을 선언으로 합친다.
7. 술어논리식을 절로 바꾸는 과정에서 존재기호 제거보다 먼저 해야 할 단계는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 한정된 변수의 충돌을 먼저 없애야 존재변수의 의존 관계를 정확히 반영할 수 있다.
- ② 오답: 전칭기호 제거는 관두형과 연언표준형 변환 뒤에 수행한다.
- ③ 오답: 절 분리는 연언표준형을 얻고 전칭기호를 생략한 뒤의 단계다.
- ④ 오답: 절별 변수 이름 분리는 절을 나눈 뒤 수행하는 마지막 단계다.
8. ~Father(x,y) ∨ Male(x)와 Father(A,B)를 도출하기 위한 단일화 치환은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 인수 순서를 바꾸면 Father(B,A)가 되어 주어진 사실과 일치하지 않는다.
- ② 오답: 단일화에서는 변수를 항으로 대체하며 주어진 상수를 임의의 변수로 바꾸지 않는다.
- ③ 정답: 첫째 인수 x를 A로, 둘째 인수 y를 B로 바꾸면 보완 리터럴이 정확히 일치한다.
- ④ 오답: 둘째 인수가 A가 되어 Father(A,A)가 되므로 Father(A,B)와 다르다.
9. 반박에 의한 도출연역 증명에서 false가 도출되었다는 의미는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 모순은 공리만이 아니라 공리와 추가한 목표의 부정이 양립하지 않음을 뜻한다.
- ② 오답: false는 두 가정을 동시에 만족시키는 해석이 없다는 신호다.
- ③ 오답: 새 절 없이 종료되는 경우가 증명 실패이며, 빈 절 도출은 성공 조건이다.
- ④ 정답: 목표의 부정이 공리와 모순되므로 공리가 성립하는 범위에서 원래 목표가 따라온다.
10. 도서관 예제에서 Member(MINJI) 사실을 삭제했을 때 가장 적절한 판단은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 함의 규칙은 회원이라는 전건이 확보된 객체에만 대출 권한을 결론으로 준다.
- ② 오답: ∀x(Member(x) → CanBorrow(x))는 회원이면 권한이 있다는 뜻이지 모두가 회원이라는 뜻이 아니다.
- ③ 오답: ~CanBorrow(MINJI)와 규칙으로 ~Member(MINJI)를 얻어도 그 보완 사실이 없어 빈 절이 나오지 않는다.
- ④ 오답: 단일화는 같은 술어의 인수를 맞추는 과정이며 서로 다른 술어 이름을 같게 만들지 않는다.
참고 자료와 작성 기준
이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 강의의 논리식과 증명 범위를 유지하면서 개념 관계, 도서관 적용 예제, 오개념 분석과 문제 해설을 학습자의 이해를 돕도록 새로 구성하고 검토했습니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 한국방송통신대학교 컴퓨터과학과 「인공지능」 6강 ‘논리에 의한 지식표현’ 강의록(2025)
- 보충 자료: 외부 보충 자료를 사용하지 않음
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-08-17
댓글
댓글 쓰기