방송대 방통대 인공지능 6강 - 논리에 의한 지식표현 - 요약 노트 시험족보 예상문제 - 올에이클래스

인공지능 6강 - 논리에 의한 지식표현

논리는 지식을 명확한 기호와 규칙으로 표현하고, 이미 알려진 사실에서 새로운 결론을 이끌어 내는 기반입니다. 이번 강의에서는 명제논리와 술어논리의 표현력을 비교하고, 단일화와 도출연역을 이용해 정리를 증명하는 과정을 학습합니다.

명제와 진리표

기본명제와 합성명제

명제(proposition)는 참과 거짓을 구분할 수 있는 문장입니다. “영수는 한국인이다”와 “존은 미국인이다”처럼 더 이상 분해할 수 없는 최소 단위 명제를 기본명제라 하며 p, q 등의 기호로 표시합니다. 기본명제는 명제상수 또는 원소식(atomic formula)이라고도 합니다.

두 개 이상의 기본명제를 논리연산자로 결합하면 합성명제가 됩니다. p가 “영수는 한국인이다”, q가 “존은 미국인이다”라면 p∧q는 두 문장이 모두 참임을, p∨q는 적어도 하나가 참임을 나타냅니다. 합성명제의 진릿값은 구성 명제의 모든 진릿값 조합을 나열한 진리표로 확인할 수 있습니다.

연산자	이름	의미
∨	선언(OR)	둘 중 적어도 하나가 참
∧	연언(AND)	둘 다 참
~	부정(NOT)	진릿값을 반대로 바꿈
→	함의	“p이면 q이다”
↔	동치	두 명제의 진릿값이 같음

조건명제와 명제논리의 정형식

조건명제의 진릿값

p→q는 “p이면 q이다”라는 조건명제입니다. p를 “비가 온다”, q를 “야유회를 취소한다”로 두면 비가 오는데 야유회를 취소하지 않는 경우, 즉 p가 참이고 q가 거짓일 때만 전체 명제가 거짓입니다. 나머지 경우에는 참이며, 진리표를 비교하면 p→q≡~p∨q임을 알 수 있습니다.

정형식의 생성 규칙

명제논리의 논리식은 임의 문자열이 아니라 생성 규칙을 따라야 합니다. 기본명제는 논리식이고, p가 논리식이면 ~p도 논리식입니다. p와 q가 논리식이면 p→q도 논리식이며, 이 규칙들로 얻는 식만 논리식입니다. 강의에서는 부정과 함의를 기본으로 두고 p∧q≡~(p→~q), p∨q≡~p→q로 다른 연산을 표현합니다.

시험 핵심: 조건명제는 전건이 참이고 후건이 거짓일 때만 거짓이며, p→q는 ~p∨q로 바꿀 수 있습니다.

표준형과 항진식

리터럴과 절

리터럴은 기본명제 또는 기본명제의 부정입니다. 표준형은 리터럴을 절로 묶고 절들을 다시 결합하여 논리식의 구조를 일정하게 만든 것입니다.

구분	절의 내부	절 사이	예
연언표준형(CNF)	리터럴의 논리합	절들의 논리곱	(p∨~q)∧(~r∨s∨t)
선언표준형(DNF)	리터럴의 논리곱	절들의 논리합	(~p∧r)∨(~q∧s∧t)

항진식

항진식은 구성 기본명제의 값과 관계없이 항상 참인 논리식입니다. p∨~p는 p가 참이든 거짓이든 항상 참입니다. 강의는 (p∧(p→q))→q와 ((p→q)∧(q→r))→(p→r)도 진리표의 모든 행에서 참이 되는 항진식으로 확인합니다.

명제논리의 연역

연역(deduction)은 이미 알고 있는 전제를 이용해 정확한 결론을 이끌어 내는 추론 과정입니다. 대표적인 규칙은 긍정논법과 부정논법입니다.

규칙	전제	결론
긍정논법(modus ponens)	α, α→β	β
부정논법(modus tollens)	~β, α→β	~α

긍정논법은 조건의 전건이 실제로 성립할 때 후건을 얻는 규칙입니다. 부정논법은 후건이 성립하지 않는다는 사실에서 전건도 성립할 수 없다고 추론합니다. 두 규칙 모두 전제의 구조와 결론의 방향을 정확히 구분해야 합니다.

술어논리의 지식표현

명제논리의 표현 한계

명제논리는 “소크라테스는 사람이다”, “플라톤은 사람이다”, “모든 사람은 죽음을 면할 수 없다”를 각각 독립된 명제로 나타냅니다. 이 방식은 사람이라는 공통 속성과 개별 객체의 관계를 드러내지 못하므로 일반 규칙을 개별 객체에 적용하기 어렵습니다.

술어와 객체

술어논리는 문장을 객체와 객체를 수식하는 술어로 분해하여 ‘술어(객체)’ 형식으로 표현합니다. “소크라테스는 사람이다”는 Man(SOCRATES), “플라톤은 사람이다”는 Man(PLATO)입니다. 여러 객체의 관계도 On(X,Y)처럼 표현할 수 있습니다.

술어논리 기본명제의 일반형은 술어(객체₁, 객체₂, …, 객체ₙ)입니다. 객체 자리에는 상수, 함수, 변수가 올 수 있습니다. 함수는 다른 객체를 가리키는 항을 만듭니다. 예를 들어 father(철수)가 영호를 나타낸다면 Korean(father(철수))는 Korean(영호)와 같은 객체를 가리킵니다.

시험 핵심: 술어는 객체의 성질이나 관계를 나타내고, 객체는 상수·함수·변수로 표현할 수 있습니다.

변수와 한정기호

하나 이상의 객체에 적용되는 문장을 표현할 때 객체변수를 사용합니다. 변수의 범위는 한정기호로 정합니다. 전칭기호 ∀는 정의역의 모든 원소에 대해 성립함을, 존재기호 ∃는 조건을 만족하는 원소가 적어도 하나 존재함을 뜻합니다.

“모든 사람은 죽음을 면할 수 없다”는 ∀x(Man(x)→Mortal(x))로 표현합니다. 이 규칙과 Man(SOCRATES), Man(PLATO)를 결합하면 Mortal(SOCRATES), Mortal(PLATO)를 각각 이끌어 낼 수 있습니다. “모든 새는 날개가 있다”는 ∀x(Bird(x)→HasWings(x)), “농구선수 중에는 키가 크지 않은 선수도 있다”는 ∃x(BasketballPlayer(x)∧~Tall(x))입니다.

한정기호에 대한 동치

• ~∃xP(x)≡∀x~P(x)
• ~∀xP(x)≡∃x~P(x)
• ∀x(P(x)∧Q(x))≡∀xP(x)∧∀yQ(y)
• ∃x(P(x)∨Q(x))≡∃xP(x)∨∃yQ(y)

“모든 A는 B이다”는 일반적으로 ∀x(A(x)→B(x))이고, “어떤 A는 B이다”는 ∃x(A(x)∧B(x))입니다. 전칭문에서는 함의, 존재문에서는 연언이 쓰이는 차이를 주의해야 합니다.

술어논리의 항과 정형식

항의 정의

객체상수와 객체변수는 항(term)입니다. t₁,t₂,…,tₙ이 항이고 f가 n개의 인자를 받는 함수기호라면 f(t₁,t₂,…,tₙ)도 항입니다. 이 규칙으로 정의되는 것만 항이며, 항은 정의역 D의 원소를 나타냅니다.

정형식의 정의

참(T)과 거짓(F)은 정형식(wff)입니다. P가 n개의 항을 수식하는 술어라면 P(t₁,…,tₙ)은 정형식입니다. P와 Q가 정형식이면 ~P와 P→Q도 정형식이며, P가 정형식이고 x가 객체변수이면 ∀xP와 ∃xP도 정형식입니다. 오직 이 생성 규칙으로 만들어진 식만 정형식입니다.

도출연역과 단일화

기본 도출식

도출연역(resolution)은 두 부모절에서 서로 상보적인 리터럴을 제거하고 남은 리터럴을 합쳐 도출절을 만드는 추론 규칙입니다. P와 ~P∨Q에서는 P와 ~P가 제거되어 Q를 얻습니다. ~P와 P에서는 아무 리터럴도 남지 않아 false가 됩니다. ~P∨Q와 ~Q∨R에서는 Q와 ~Q를 제거하여 ~P∨R을 얻습니다.

술어논리에서 객체 일치

술어논리에서는 술어 이름뿐 아니라 객체 인자도 일치해야 상보쌍이 됩니다. ~Father(A,B)∨Male(A)와 Father(A,B)에서는 Male(A)를 도출할 수 있지만 Father(C,D)는 객체가 달라 곧바로 도출할 수 없습니다.

변수가 있을 때는 단일화(unification)를 수행합니다. ~Father(x,y)∨Male(x)와 Father(A,B)에 x←A, y←B를 적용하면 ~Father(A,B)∨Male(A)가 되어 Male(A)를 도출할 수 있습니다.

시험 핵심: 단일화는 객체변수를 치환하여 상보 리터럴의 술어와 인자를 서로 일치시키는 과정입니다.

술어논리식의 절 분리

도출연역을 적용하려면 술어논리식을 절들의 집합으로 바꾸어야 합니다. 강의의 변환 과정은 다음 아홉 단계로 구성됩니다.

1. 함의 제거: p→q를 ~p∨q로 바꿉니다.
2. 부정 범위 축소: 드모르간 법칙과 한정기호 동치를 이용해 부정을 원소식 가까이 이동합니다.
3. 변수 표준화: 서로 다른 한정 범위에서 같은 이름을 쓰는 변수를 다른 이름으로 바꿉니다.
4. 존재기호 제거: 존재변수를 스콜렘 상수 또는 의존 전칭변수의 스콜렘 함수로 대체합니다.
5. 관두형으로 표현: 한정기호를 식의 앞부분으로 이동합니다.
6. 연언표준형 변환: 분배법칙을 이용해 절들의 논리곱으로 만듭니다.
7. 전칭기호 제거: 남은 변수는 전칭된 것으로 간주하고 기호를 생략합니다.
8. 연언기호 제거: 각 연언 성분을 독립된 절로 분리합니다.
9. 변수 이름 분리: 서로 다른 절의 변수 이름이 겹치지 않도록 다시 바꿉니다.

강의 예제에서는 존재변수 w를 g(x)로 대체합니다. 이는 w가 바깥 전칭변수 x에 의존하기 때문입니다. 최종 절에서는 x를 x₁, x₂, x₃처럼 서로 다르게 바꾸어 각 절의 변수가 독립적으로 단일화되도록 합니다.

도출연역에 의한 정리 증명

귀류법 기반 알고리즘

1. 증명할 정리를 부정하여 공리 목록에 추가합니다.
2. 모든 공리를 연언표준형의 절로 변환합니다.
3. 도출 가능한 절의 쌍을 골라 단일화하고 도출절을 만듭니다.
4. 도출절이 false이면 모순이므로 원래 정리가 참임이 증명됩니다.
5. false가 아니면 새 도출절을 목록에 넣고 과정을 반복합니다.
6. 더 이상 도출할 절의 쌍이 없는데 false를 얻지 못하면 증명에 실패합니다.

블록 관계 예제

On(x,y)는 x가 y의 바로 위에 있음을, Above(x,y)는 x가 y보다 위에 있음을 뜻합니다. 공리는 ∀x∀y(On(x,y)→Above(x,y))와 ∀x∀y∀z((Above(x,y)∧Above(y,z))→Above(x,z))입니다. 관측 사실은 On(A,B), On(B,TABLE)이며 목표는 Above(A,TABLE)입니다.

첫 공리는 ~On(u,v)∨Above(u,v), 두 번째 공리는 ~Above(x,y)∨~Above(y,z)∨Above(x,z)로 바꿉니다. 목표의 부정 ~Above(A,TABLE)을 추가한 뒤 단일화와 도출을 반복하면 ~On(A,y)∨~On(y,TABLE)을 얻습니다. On(A,B)를 적용해 y←B로 두면 ~On(B,TABLE)이 남고, 관측 사실 On(B,TABLE)과 도출하면 false가 됩니다.

예제 결론: 목표의 부정이 공리 및 관측 사실과 모순되므로 Above(A,TABLE)이 참임이 증명됩니다.

핵심 개념 정리

• 명제논리: 참·거짓을 갖는 문장을 기호화하며, 조건명제 p→q는 ~p∨q와 동치입니다.
• 표준형: CNF는 선언절의 연언이고 DNF는 연언절의 선언입니다.
• 연역: 긍정논법은 α와 α→β에서 β를, 부정논법은 ~β와 α→β에서 ~α를 얻습니다.
• 술어논리: 문장을 술어와 객체로 분해하며 객체에는 상수·함수·변수가 올 수 있습니다.
• 한정기호: ∀는 정의역 전체, ∃는 조건을 만족하는 적어도 한 원소를 나타냅니다.
• 단일화: 술어논리의 상보 리터럴이 같은 객체를 가리키도록 변수를 치환합니다.
• 절 분리: 함의와 존재기호를 제거하고 CNF로 바꾼 뒤 각 절의 변수를 독립적으로 표준화합니다.
• 정리 증명: 목표를 부정해 공리에 추가하고 도출연역으로 false를 얻으면 원래 목표가 참입니다.

논리에 의한 지식표현의 핵심은 문장을 구조화하고 그 구조에 맞는 추론 규칙을 적용하는 것입니다. 명제논리는 문장 사이의 참·거짓 관계를 다루고, 술어논리는 객체·관계·변수와 한정기호로 일반 규칙을 표현하며, 도출연역은 절 변환과 단일화를 통해 지식에서 새로운 결론을 기계적으로 증명합니다.

예상문제 20선

1. 명제에 대한 설명으로 옳은 것은?

① 반드시 복합문장이어야 한다. ② 참과 거짓을 구분할 수 있는 문장이다. ③ 질문이나 명령만을 의미한다. ④ 진릿값을 가질 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
명제는 참과 거짓을 구분할 수 있는 문장이다. 더 분해할 수 없는 최소 단위 명제를 기본명제 또는 원소식이라 한다.

2. 조건명제 p→q가 거짓인 경우는?

① p와 q가 모두 참 ② p가 거짓이고 q가 참 ③ p와 q가 모두 거짓 ④ p가 참이고 q가 거짓

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
조건명제는 전건 p가 참인데 후건 q가 거짓일 때만 거짓이다. 그 밖의 세 경우에는 참이다.

3. p→q와 동치인 논리식은?

① ~p∨q ② p∧~q ③ p∨~q ④ ~p∧q

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
조건명제 p→q는 ~p∨q와 동치이다. 이 동치는 조건식을 절 형식으로 바꿀 때 기본적으로 사용된다.

4. 연언표준형(CNF)에 대한 설명으로 옳은 것은?

① 리터럴들의 논리곱으로 된 절들을 논리합한 형식 ② 항상 하나의 기본명제로만 된 형식 ③ 리터럴들의 논리합으로 된 절들을 논리곱한 형식 ④ 모든 함의를 그대로 유지한 형식

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
연언표준형은 리터럴의 논리합으로 이루어진 절들을 논리곱으로 연결한 형식이다.

5. 항진식의 정의로 옳은 것은?

① 모든 기본명제가 거짓인 식 ② 기본명제의 값과 관계없이 항상 참인 논리식 ③ 진리표를 만들 수 없는 식 ④ 어떤 경우에도 참이 되지 않는 식

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
항진식은 구성 기본명제의 진릿값 배정과 무관하게 항상 참인 논리식이다. p∨~p가 대표적인 예이다.

6. 긍정논법(modus ponens)의 올바른 추론은?

① α→β와 ~β에서 α ② α와 β에서 α→β ③ ~α와 α→β에서 ~β ④ α와 α→β에서 β

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
긍정논법은 α와 α→β가 성립할 때 β를 결론으로 이끌어 내는 연역 규칙이다.

7. 명제논리만으로 일반 규칙을 표현하기 어려운 이유로 가장 적절한 것은?

① 논리 연산자가 없기 때문 ② 진릿값이 없기 때문 ③ 개별 객체와 객체의 성질을 분리하고 변수로 일반화하기 어렵기 때문 ④ 기본명제를 만들 수 없기 때문

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
명제논리는 문장 전체를 하나의 기호로 다루므로 객체와 속성의 내부 구조를 드러내기 어렵다. 술어논리는 이를 술어와 객체로 분해한다.

8. ‘소크라테스는 사람이다’를 술어논리로 바르게 표현한 것은?

① Man(SOCRATES) ② SOCRATES(Man) ③ ∀Man(SOCRATES) ④ Man→SOCRATES

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
문장을 객체 SOCRATES와 이를 수식하는 술어 Man으로 분해하면 Man(SOCRATES)가 된다.

9. 술어논리 기본명제의 객체로 사용될 수 없는 것은?

① 객체상수 ② 함수 ③ 객체변수 ④ 논리연산자의 진리표

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
술어논리의 기본 형식은 술어(객체들)이며 객체 자리에는 상수, 함수, 변수가 올 수 있다.

10. ‘모든 새는 날개가 있다’의 표현으로 옳은 것은?

① ∃x(Bird(x)∧HasWings(x)) ② ∀x(Bird(x)→HasWings(x)) ③ ∀x(Bird(x)∧~HasWings(x)) ④ ∃x(Bird(x)→~HasWings(x))

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
‘모든’은 전칭기호 ∀로 표현한다. 정의역의 모든 x에 대해 새라면 날개가 있다는 조건식이 성립해야 한다.

11. ‘농구선수 중에는 키가 크지 않은 선수도 있다’의 표현으로 옳은 것은?

① ∃x(BasketballPlayer(x)∧~Tall(x)) ② ∀x(BasketballPlayer(x)→Tall(x)) ③ ~∃x BasketballPlayer(x) ④ ∀x(BasketballPlayer(x)∧~Tall(x))

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
조건을 만족하는 원소가 적어도 하나 존재한다는 뜻이므로 존재기호를 쓰고, 농구선수이면서 크지 않다는 두 조건을 연언한다.

12. 한정기호 부정의 동치식으로 옳은 것은?

① ~∃xP(x)≡∃x~P(x) ② ~∀xP(x)≡∀x~P(x) ③ ∀xP(x)≡∃xP(x) ④ ~∃xP(x)≡∀x~P(x)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
존재하지 않는다는 것은 모든 원소가 그 성질을 갖지 않는다는 뜻이므로 ~∃xP(x)≡∀x~P(x)이다.

13. 술어논리에서 항(term)에 대한 설명으로 옳은 것은?

① 항은 오직 객체상수만 뜻한다. ② 술어 자체만 항이다. ③ 객체상수와 객체변수는 항이며 항들에 함수를 적용한 식도 항이다. ④ 논리식은 모두 항이지만 정의역 원소는 아니다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
객체상수와 객체변수는 항이고, 함수기호 f에 항 t₁,…,tₙ을 적용한 f(t₁,…,tₙ)도 항이다. 항은 정의역의 원소를 나타낸다.

14. 기본 도출식에서 P와 ~P∨Q로부터 얻는 도출절은?

① Q ② P∨Q ③ ~Q ④ false

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
상보 리터럴 P와 ~P를 제거하면 남는 Q가 도출절이 된다.

15. 술어논리 도출연역에서 단일화가 필요한 이유는?

① 모든 변수를 상수로 영구 삭제하기 위해 ② 도출절의 쌍을 이루는 객체가 일치하도록 객체변수를 대체하기 위해 ③ 함의를 새로 추가하기 위해 ④ 전칭기호를 존재기호로 바꾸기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
술어논리에서는 상보 술어의 객체 인자가 일치해야 도출할 수 있다. 단일화는 적절한 치환으로 두 리터럴을 일치시킨다.

16. ~Father(x,y)∨Male(x)와 Father(A,B)를 단일화할 때 올바른 치환과 도출절은?

① x←B, y←A; Male(B) ② x←A만 치환; Father(A,B) ③ y←A만 치환; Male(y) ④ x←A, y←B; Male(A)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
x를 A, y를 B로 치환하면 Father 리터럴이 상보쌍을 이루어 제거되고 Male(A)가 남는다.

17. 술어논리식을 절로 분리하는 과정에서 존재기호를 제거할 때 사용하는 것은?

① 진리표 ② 항진식 ③ 스콜렘 함수 또는 스콜렘 상수 ④ 긍정논법

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
존재변수는 그 변수가 의존하는 전칭변수의 함수인 스콜렘 함수로 바꾸거나, 의존 변수가 없으면 스콜렘 상수로 바꾸어 제거한다.

18. 도출연역에 의한 정리 증명의 첫 단계는?

① 증명할 정리를 부정하여 공리 목록에 추가한다. ② 관측 사실을 모두 삭제한다. ③ 목표 정리를 곧바로 참이라고 선언한다. ④ 도출 가능한 절을 만들지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
도출연역의 정리 증명은 귀류법을 사용한다. 증명할 정리의 부정을 공리에 더하고 모순인 false가 도출되는지 확인한다.

19. 도출연역에 의한 정리 증명에서 false가 도출되었다는 의미는?

① 공리들이 모두 거짓이다. ② 추가한 목표 정리의 부정이 공리들과 모순이므로 원래 정리가 참이다. ③ 단일화가 실패했다. ④ 더 이상 어떤 결론도 얻을 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
공리와 목표의 부정으로부터 모순이 생겼으므로 목표의 부정은 성립할 수 없다. 따라서 원래 목표 정리가 참임이 증명된다.

20. 블록 예제에서 On(A,B), On(B,TABLE)과 주어진 공리로 증명하는 결론은?

① On(TABLE,A) ② ~Above(A,TABLE) ③ Above(A,TABLE) ④ Above(B,A)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
On(x,y)이면 Above(x,y)이고 Above 관계가 추이적이라는 공리를 이용하면 A는 B 위, B는 TABLE 위이므로 A는 TABLE 위에 있음을 증명할 수 있다.