인공지능 필기

artificial intelligence는 크게 두 가지로 나뉜다. Reasoning(추론)과 machine learning(머신러닝). 머신 러닝은 대학원 가서 배우는 것이고 추론부터 나간다. 추론은 if then 구문처럼 정해 나가는 것이다.

컴퓨터의 역사

처음에 나온 컴퓨터는 ENIAC, 그 뒤에 나온 컴퓨터가 EDVAC. EDVAC은 폰 노이만의 프로그램 내장 방식, 즉, 폰노이만의 아키텍쳐로 만들어져 현재의 컴퓨터 구조와 비슷하다. 처음에는 이진수가 아닌 십진수(진공관의 불의 밝기 : 0~9까지)로 데이터를 표현하려 했으나 그 당시에는 전력이 제대로 공급이 안 됐고 사람의 눈에 4인지 5인지 밝기로 제대로 알 수가 없어 켜짐과 꺼짐인 1과 0으로 표현했다.

중학교 때 배웠던 수의 표현들도 다 의미가 있다. NUMBER(수 체계) -\> SET(집합) -\> FUNCTION(함수) -\> OPERATION(연산자)의 순으로 배우는데 NUMBER에는 N(Natural), Z(Integer), R(Rational), I(Irrational), R(Real) 이렇게 나누어진다. SET(집합)에는 X인 domain과 Y인 codomain을 중심으로 배운다.

조지 불이라는 사람이 생각했다. 논리는 True와 False로 나누어지는데 '사실 + 사실 = 사실'이기 때문에 1 + 1 = 1이 된다. 곱하기도 마찬가지.

라이프니츠가 '어떻게 사람의 생각을 계산할 수 있을까?'를 가장 처음 생각해냈는데 if A then B and if B then C, if A then C와 몇 가지 공식만 쓰고 다른 연구를 하셨다. 그 이후에 조지 불이라는 사람이 제대로 연구한다.

지금 말하는 4가지가 있어야 사람의 생각을 연산할 수 있다.

  1. operand(= proposition(명제 : 1 or 0))

  2. operator(= -(not), AND, OR, -\>(imply)) //-\>는 추론이 가능한 연산자로 매우 중요하다

  3. precedence

  4. Eq.Rules

X(가정) Y(결론) X -\> Y
0(거짓) 0 1(참)
0 1 1
1 0 0
1 1 1

-\>를 식으로 표현하면 X(1-Y) = 0 이다.

X -\> Y로 가고 Y -\> Z로 간다면 X -\> Z일까?

아니다. 이 삼단논법은 예외가 있기 때문에 성립하지 않는다.(ex. X : 우리 학교 대부분은 잘 생겼다. Y : 잘생기면 연예인을 한다. 그러면 우리 학교 대부분은 연예인을 할까? 아니다.)

그러나,

SOME X -\> Y로 가고 SOME Y -\> Z라면 SOME X -\> Z는 아니다. 예외가 있다. All X -\> Y로 가고 All Y -\> Z라면 All X -\> Z이다. 즉, 위 처럼 SOME은 해당 안 되지만 ALL이면 가능하다. 밑의 그림은 SOME과 ALL의 차이다. SOME은 겹치지 않는 부분이 예외이다.

P : A dog is sleeping //이 명제는 둘로 나눌 수 있다. A dog라는 주어부(Subject)와 is sleeping이라는 술어부(predicate)이다.

P(x) : X is sleeping ///문장에 변수가 있으므로 명제 수를 중일 수 있다. (Printf 문을 100번 해도 되나, 변수가 있다면 for문을 쓰면 된다.

즉, '모든'이 성립해야 -\>를 쓸 수 있다. for all에 대해서는 추론을 허락하고 for some에 대해서는 추론을 허락하지 않는다. H(x) ^ P(x) ??

프레게라는 사람이 "수학은 논리의 확장이다"라고 말함. 하지만 러셀이 반증함. Ex. 이발사의 패러독스. 집합이 사라질 뻔해서 수학에 큰 위기가 왔으나 그 시대 수학의 거장인 David Hilbert가 두 가지 주장을 함. 하지만 주장에 또 반문을 하는 사람이 나타남. '불완전성의 원리'라고. 어려워서 튜링이 쉽게 접근하게 함. 여기서 앨런 튜링이 CPU, Memory의 구조를 나타냄.

–이 전까지는 시험에 하나도 안 나옴.

튜링 테스트(시험문제 후보) : 어떤 사람 B가 A(컴퓨터와 사람)에게 질문했을 때 A의 응답을 B가 사람인지 컴퓨터인지 구분하지 못한다면 그 컴퓨터는 지능이 있다고 판단.

AI가 문제를 처리하는 방법과 그 문제들의 특징? (시험문제 후보)

AI는 결정적인(deterministic) 절차로 해결을 하지 못 한다. 시행착오(trial by error)로 되는 해결책을 원한다. 즉, 다 해봐야 된다. 수가 조금만 증가해도 가능성이 기하급수적(grow exponentially)으로 증가하기 때문에 경험, 직관적(heuristic)으로 접근하는 게 중요하다.

Agent -\> AI문제를 풀기위한 자율적인 개체

Stateful(뇌, 메모리를 갖고 있는) -\> 사람, 로봇 // Stateless(메모리가 없는) -\> 작은 벌레들

전지전능(omniscience)과 이성적(Rational)의 차이(시험문제 후보)

이성적(Rational)은 완전과 다르다. 전지전능은 모든 가능한 상황에서 옳은 결정, 최적의 결정을 내린다. 가능한 결과를 최대한 좋은 쪽으로, 내가 가진 데이터로 최선을 도출해내는 게 이성적인 것이고 항상 옳은 쪽, 항상 정확한 것은 전지전능이다.

2장 - Agent - 나올 거 없다고 하심

자극반응(Stimulus-response) 에이전트 -\> 내부 상태가 없으며 환경의 자극에 대해 간단한 반응을 보이는 기계

로봇 감지 능력 -\> 감지 입력 값을 인자로 취하는 함수를 구현해야 되고 행동 함수를 확정한다.

특징을 정했으면 적당한 경계 추적 행동을 선정하는 함수를 명시. x1 = 1, x2 = 0이면 동쪽으로 움직임. Default를 정해줘야 한다. x1 = 0, x2 = 0, x3 = 0, x4 = 0이면 북쪽. 이런 식으로.

부울 대수는 연산자 .(and) , +(or), -(not)를 사용한다. 연산해도 똑같으니 닫혀 있는 연산자라고 부른다..

λ1λ2λ3λ4λ5는 논리곱 = term이라고 부른다. λ1+λ2+λ3+λ4+λ5는 논리합 = clause이라고 부른다.

생성 시스템은 행동 함수의 편리한 표현 양식 중 하나이다. 생성 시스템은 생성 규칙이라고 하는 규칙의 정렬된 리스트로 구성된다. 규칙은 c -\> a와 같은 형태로 표현되는데 c를 조건부 a를 행동부라고 한다.

로봇을 구석으로 위치시킬 때 c -\> nill(null)으로 해줄 수 있는데 그래서 코드 맨 위에 넣어줘야 한다. (먼저 NULL인가 확인을 시켜주고 해야하니까)

7장 - 계획하는 에이전트

상태 공간 그래프(state space graph) : 실세계 모델과 행동들의 그래프. 모든 가능한 상태의 집합을 다 그리는 것. Goal로 가는 가중치가 다를 수 있다. Initial state부터 시작해서 쭉 퍼져 나가는(확장되는) 형태.

그래프는 node의 집합으로 구성된다. 어떤 노드의 쌍은 아크(arc)로 연결되어 있으며, 아크는 한 노드에서 다른 노드로 방향성을 가지고 있다.

그래프를 말할 때 G = \<V, E\> E V x V 라고 말해야 한다. (x는 Cartesion Product. V는 Vertex, E는 Edge이다.)

V = {1, 2, 3, 4} 라고 하면 V x V = {(1,1) (1,1) (1,1) (1,1) (1,1) (1,1)(1,1)…. (1, 4) 부터 (4, 4)까지 그 중에서 이제 해당되는 걸 고르면 된다. G = { (1, 2), (2, 3) … }

데이터베이스의 테이블을 Relation이라고 부르는 이유가 여기 있다. R V * S * R 에서 R을 Relation이라고 한다. 그 뒤에 VSR은 칼럼이다. V부터 주민등록번호, 이름, 주소 등등…

그래프와 트리의 차이 -\> 트리는 사이클이 없고 Root를 가지고 있다.

부모가 없는 노드를 루트(root)노드라고 한다. 루트 노드의 깊이(depth)는 0이고, 다른 노드의 깊이는 부모 노드의 깊이에 더하는 것으로 정의된다.

이론적인 분석을 위해 정의되는 트리 중에 단말 노드를 제외한 모든 노드가 똑같이 b개의 자식을 가지는 경우가 있다. 이런 경우 b를 그 트리의 분기 계수(Branching factor)라고 한다.

Uninformed search(무정보 탐색 - 문제외에 추가 정보가 없다)

알고리즘을 개발할 때 누가 더 좋은 건지 판단하기 위해 몇 가지 기준이 생겼다.

  1. Completeness(완성도) -\> 만약 해가 존재한다면 알고리즘이 항상 그 해를 찾는 것을 보장하는가?
  2. Optimality(최적성) -\> 해결책을 찾는데 비용이 매우 적은가?
  3. Space complexity(공간 복잡성) -\> 공간을 얼마나 차지하는가

몇 가지 알고리즘을 봐야 할 게 있다.(4가지 - BFS, DFS, UCS, IDS) - 그림그릴 때 어느 방향으로 그려도 상관없으나 통일성을 위해 먼저 나온 노드를 항상 왼쪽부터 그렸다. 왼쪽에서 오른쪽으로(STACK이나 QUEUE가 상관없다.)

BFS(Breadth First Search) -\> 얕은 노드부터 확장하며 검색한다. Queue를 사용한다. 항상 Optimal(넓게 다 찾으니까 항상 가장 최단 거리를 찾게 된다.)하고 Complete해서 최단거리가 나온다. 하지만 얕게 다 검색하기 때문에 메모리가 오버되는 문제가 있다. 차례대로 순서대로 순서는 알파벳 순서.

여기 Pseudo 코드가 있다.

Insert a root node to O (queue, an open list) // root노드를 O(Open list)에 넣는다.

Do while O is not empty // O가 비어 있지 않다면

Node n \<- the first element in O // Node n은 O안에 있는 첫번째 노드다.

Insert n to C //Node n을 C(Closed list)에 넣는다.

Get all child nodes n1, n2, …, nk of n //n의 모든 child 노드를 가져온다.

For each ni (1 ≤ i ≤ k), which is not in O and C //O와 C에 들어있지 않은 ni를 반복한다.

Add a pointer to n //노드 n을 추가한다.

If it is a goal node, make a path and end search //만약 그게 목표 노드라면 길을 만들고 검색을 종료한다.

Add it to O //O에 추가한다.

Next

Loop

Search fails if reached here

O: {(a, s), (b, s), (d, s)} //넣는 순서는 알파벳 순으로 한다. (a, s)는 a가 s로부터 왔다는 걸 나타낸다.

C: (s, -)

O: (b, s), (d, s), {(s, a), (b, a), (c, a)} //새로 나온 얘들 중에서 O와 C에 있는 건 삭제한다. 앞 글자 (s, ?)만 보고 판단해도 된다.

C: (s, -), (a, s) //Queue이기 때문에 앞 순서부터 넣어준다.

O: (d, s), (c, a), {(s, b), (a, b), (d, b)}

C: (s, -), (a, s), (b, s)

O: (c, a), {(s, d), (b, d), (c, d), (g, d)}

C: (s, -), (a, s), (b, s), (d, s)

마지막에 나온 C의 값들과 O에서 g로 가는 노드를 써주면 된다. (s, -), (a, s), (b, s), (d, s), (g, d)의 값을 가지고 그래프를 그림

순서는 알파벳 순서로 들어오게 하고, 중가로에 들어오는 노드들 중에서 바깥에 있는 노드와 같은 게 있으면 버린다. 마지막 노드(G)가 나오면 바로 꺼내서 써주고 끝낸다.

시험에는 위와 같은 그림 하나 주고 결과 그래프만 그리면 된다. 답은 위의 그림이다.

DFS(Depth First Search) -\> stack이고 깊이 제한(Depth)을 줄 수 있다. 한 곳만 깊게 파기 때문에 Optimal하지도 않고 Complete하지도 않다. 그럼에도 가장 많이 쓰이는 이유는 메모리를 거의 안 잡아 먹기 때문이다.

DFS에서 메모리는 d(depth) * b(branch factor)가 된다. 왜냐면 경우의 수를 가보고 아니면 지우는 스택이니까. (깊게 갔다가 다시 올라와서 다시 깊게 간다.)

BFS는 메모리가 b^d이다. 엄청나게 차이 난다.

위와 똑같은 그림으로 DFS를 해보면 아래처럼 나온다.

O: {(a, s), (b, s), (d, s)}

C: (s, -)

O: (b, s), (a, s), {(s, d), (b, d), (c, d), (g, d)},

C: (s, -), (d, s) // 여기서 주의! Stack이므로 알파벳 순서에서 뒤부터 검색한다.

UCS(Uniform Cost Search) -\> BFS와 매우 비슷한데 가중치가 있다. 그래서 3개를 쓴다. 가중치까지. //O와 C에서 다 찾아서 삭제해준다. 그리고 목표 노드인 g가 다른 노드보다 먼저 와도 g는 없애지 말고 다른 노드부터 천천히 해준다. 정말 차근차근히 해야 된다. (그리고 뒤로 가면 갈수록 가중치가 커진다.) 코스트가 가장 작은 노드로 확장한다.(처음부터)

Uniform cost search는 모든 노드의 가중치가 같다면 BFS와 같아진다.

complete(해가 있으면 항상 찾는다.)하고 optimal하다.

노드의 코스트가 같다면 BFS와 같이 알파벳 순서로 close 리스트에 들어간다.(사실상, open list에 들어갔을 때부터 정렬이 되어있다. 먼저 open list에 넣고 정렬 작업(알파벳 순으로)을 해준다.

O: (a, 2, s), (b, 3, s), (d, 5, s)

C: (s, -, -)

O: (b, 3, s), (d, 5, s), {(s, 4, a), (b, 6, a), (c, 7, a)} // 가중치도 함께 더해준다. 여기서 (b, 3, s)와 (b, 6, a)를 비교한다. 6이 더 가중치가 크니까 6짜리를 날린다. s는 날린다. 그리고 O와 C에서 비교한다.

C: (s, -, -), (a, 2, s) //BFS와 마찬가지로 a부터

O: (d, 5, s), (c, 7, a),{(s, 6, b), (a, 7, b), (d, 7, b)} //OPEN된 큐는 항상 정렬된다. d에서 5가 더 작고 a에서 2가 더 작으니까

C: (s, -, -), (a, 2, s), (b, 3, s)

O: (c, 7, a),{(s, 10, d), (b, 9, d), (c, 6, d), (g, 9, d)} //여기서도 c, 7과 6이 있으니 7을 날린다. b에서 9와 3이 있으니 9를 날린다.

C: (s, -, -), (a, 2, s), (b, 3, s), (d, 5, s)

O: (c, 6, d), (g, 9, d)

C: (s, -, -), (a, 2, s), (b, 3, s), (d, 5, s)

O: (g, 9, d){(a, 11, c), (d, 7, c), (g, 8, c)} //OPEN에 G가 나온다고 끝내면 절대 안 된다.

C: (s, -, -), (a, 2, s), (b, 3, s), (d, 5, s),(c, 6, d)

O:

C: (s, -, -), (a, 2, s), (b, 3, s), (d, 5, s) (c, 6, d), (g, 8, c)

답은

O: (b, 4, S) (a, 5, S) //이유는 코스트가 작은 순부터 들어오기 때문에 b가 먼저 들어와야 한다.

C:(S, -, -) //

//알파벳 순이 아닌 코스트 순이다. 코스트가 작은 순서대로.

//그림도 순서가 있다. 왼쪽 오른쪽. 반드시 저 순서대로 해야된다.

//코스트가 없다면 openlist에 나왔을 때 바로 날려버릴 수 있다. 왜냐면 기존에 close리스트에 있다는 건 이미 거치고 갔다는 소리이기 때문이다. 그래서 또 고려할 필요가 없다.

//코스트가 있다면 비교를 해서 날려주어야 한다.

IDS(Iterative Deeping DFS)

Depth bound를 증가시키는 것. 결과가 없다면 계속 제한을 늘리면서 찾는 것이다. 얘는 Complete하다. 제한이 있으니까. Optimal이기도 하다. DFS라서 메모리를 적게 먹는다.

but 시간이 오래 걸린다. 근데 BFS보다 10%밖에 시간 차이가 안 남. 그래서 다들 DFS를 쓴다. 얘가 끝판 대장이다.

b : branching factor, d : depth (여기 표 시험에 나온다!)

  Memory Visit PROS CONS
BFS b^d   Complete/Optimal Memory
DFS b*d '' Memory X
UCS b^d '' Complete/Optimal Memory
IDS b*d   Complete/Optimal, Memory Time(10%)
  • Memory
  1. BFS는 그 목표까지 가는데 다 찾아야된다. b^d
  2. DFS는 한 Branch만 보고 나머지는 다 버리니까 b*d가 된다.
  3. IDS는 시간에 관계 없이 항상 DFS를 실행하니까 b*d이다.
  4. UCS는 COST가 붙어서 알고리즘이 어려울 뿐이지 BFS와 똑같다.
  • Visit

노드를 방문하는 횟수랑 메모리에 들어가는 숫자와는 다르다. 노드를 방문한다는 건 그만큼 시간이 걸린다는 것. 즉, 시간은 비슷하나 메모리가 다르다. IDS에만 시그마가 들어가 있어 더 많을 것 같지만 해보면 10%밖에 차이가 나지 않는다.

visit은 BFS와 DFS가 같다. 왜냐면 DFS에서 최악의 경우 모두 거치기 때문이다. 시작지점과 반대로 모두 갈 때. UCS는 COST가 다 똑같을 경우 모두 거치기 때문에 똑같다.

책 P.142 - 8.2의 답 (가정이 있기 때문에 조심.)

  1. DFS : 1, 4, 9, 8, 3, 7, 13

  2. IDS : 1, 2, 5, 6, 10, 11, 3, 7, 12, 13, D1(1, 4, 3, 2) D2(1, 4, 9, 8, 3, 7, 2, 6, 5) 그리고 DFS.

A* search** (무조건 시험)** -\> UCS와 같지만, 자기의 weight뿐만 아니라 추정치까지 봐줘야 한다.

UCS의 COST가 g(n)이라면 A*의 COST는 g(n) + h(n)이다. 즉 cost하나를 더 고려한 것이다. 마찬가지로 queue이다. g(n)은 길의 거리. h(n)은 goal까지의 거리이다. h(n)은 goal까지의 직선 거리(추정 거리). 실제 거쳐온 거리가 g(n)이고, h(n)은 goal까지의 추정거리다.

O: (a,6,s)

C: (s,6,-) //해당하는 h값을 써준다.

O: {(s,8,a), (b,6,a), (d,6,a), (e,9,a)} //자기 자신에 해당하는 h값과 거리(S까지 가는데의 거리를 다)들을 더해준다. 여기서는 가중치가 같으니까 알파벳 순서인 b가 와야 한다.

C: (s, -, -), (a,6,s)

O: (d,6,a), (e,9,a) {(a,8,b), (c,6,b)}

C: (s, -, -), (a,6,s), (b,6,a)

O: (d,6,a), (e,9,a) {(b,8,c), (d,7,c)} //d가 6이랑 7이 있는데 7이 더 크니까 7이 사라진다.

C: (s, -, -), (a,6,s), (b,6,a), (c,6,b)

O: (e,9,a) {(a,9,d), (c,10,d), (e,8,d), (g,6,d)} //돌아가는 얘들은 삭제해도 된다.

C: (s, -, -), (a,6,s), (b,6,a), (c,6,b), (d,6,a)

O: (e,8,d)

C: (s, -, -), (a,6,s), (b,6,a), (c,6,b), (d,6,a), (g,6,d)

문제 하나 더

O : (a, 6, s), (b, 4, s) //에서 4가 더 작으니 b가 먼저 온다.

C : (s, 8, -) //이런 식으로…하다보면

마지막쯤에 (a, 6, s)와 (g, 10, d)가 나오는데 가중치가 더 작은 a로 간다.

(s, 8, -), (b, 4, s), (c, 4, b), (d, 4, c), (a, 6, s), (g, 2, a)

문제 하나 더

(S, 8, -), (A, 8, S), (C, 8, S), (D, 8, C), (G, 8, D)

A* pathfinding : A*는 Cost function을 어떻게 주느냐에 따라 달라진다.

Cost function = g(n) + h(n)인데 g(n)은 수평, 수직적으로 인접한 칸에 가중치 10을 주고 대각선으로 인접한 칸에는 가중치 14를 준다.(막 돌아서 가도 되는 거리) h(n)은 맨하탄 거리. 즉, 직선 거리(최단 거리)를 의미한다.

왼쪽 위가 cost function, 왼쪽 아래가 g(n), 오른쪽 아래가 h(n)이다. 그래서 이 8개의 칸 중에 cost function이 가장 작은 바로 오른쪽, 40이 CLOSE에 들어간다. 녹색들은 OPEN LIST에 들어 간다. 여기서 전제가 있는데 파란색 블록은 대각선으로 해서 지나갈 수 없다는 것이다. (그래서 직선으로 가야한다.)

그 다음도 실행한다. 작은 순으로 간다. 그리고 이 때 보면 녹색 칸에서 두 칸 밑에 88이라고 적혀 있는데 대각 + 대각이라고 생각해서 그렇다.

아까 그 칸을 보면 80이 되어있다. 덮어씌운 것이다. 더 작으니까.

A* search charateristics** (시험문제후보 - 어떤 특징이 있고, 조건이 무엇인지.)**

A*는 h(n)을 어떻게 주느냐에 따라 달라진다.

Admissible

  • 모든 노드 n에 대하여 h(n)을 과하게 산정하지 않아서 g(n) \>= h(n)이 된다면 admissible이 된다.
  • A*가 Admissible이 된다면 Optimal하다.

Consistent

  • 모든 노드 n과 n의 자손들에 대하여 h(n) \<= c(n, n') + h(n')를 따른다면 Consistent가 된다.
  • A*가 Consistent가 된다면 tree search와 같게 된다.

가령, O : (c, 6, S) { (c, 4, a) }가 들어왔을 때 우리는 항상 4가 코스트가 작으니 4가 6을 엎어서 바꿨었다. 그러나 Consistent가 되면 엎어 쓰기 전부터 아예 코스트가 작은 게 안 들어간다. 엎어 쓰면 정렬하는 시간이 많이 걸린다. 근데 이 부등식을 쓰면 늘 정렬이 되어있다. 그래서 알고리즘도 간단해지고 훨씬 빨라진다. tree search는 부모로 돌아갈 필요가 없다. 그래서 간단해진다. (Consistent)

그렇다면 h(n)의 기준을 어떻게 잡을까?

위 그림은 최소 26번 째에서 답이 나올 수 있다. Start State에서 Goal State로 가기 위해서는 여러 방식이 있다. 여기서 두 가지 방식으로 h(n)을 구할 수 있다.

huristic 1. Start State에 각각 위치해 있는 타일이 Goal State에 있는 위치와 다르면 +1 해준다. 모두 다르니 8번을 더해서 8이 된다.

huristic 2. 맨하탄 거리라고 부른다. Start State에 각각 위치해 있는 타일이 Goal State에 있는 타일과 얼마나 떨어져 있나를 확인한다. 3+1+2+2+3+2+2+3 = 18 (72456831 순서로 했을 때)이 나온다.

둘 중에, 어떤 heuristic function이 더 좋을까? 막상 보면 1번이 더 좋을 것 같지만 두 번째가 더좋다. 왜 그럴까? 이유는 두 번째가 거리 정보를 갖고 있기 때문이다. (상수로 이루어져 있어 나중에 코딩을 할 때 주석으로 달아주는 게 좋다. h(n)이 더 크지만 거리정보가 있어서 더 좋다고.

위에서 말한대로 Start State 에서 최소 26번을 움직여야 goal state로 갈 수 있다. 그래서 8이나 18이나 26보다 작거나 같으면 admissible하기때문에 둘 다 admissible하다.

처음에는 성능이 비슷해보이나 12스텝을 갈 때쯤 이면 엄청 벌어진다. 맨하탄이 훨씬 더 좋다. 이처럼 h(n)을 어떻게 주느냐에 따라 알고리즘이 달라진다.

문제는 어떤 휴리스틱 함수가 좋은지 아느냐?인데 이는 유효 분기 계수(Effective branching factor)를 보면 된다. B가 유효 분기 계수이고, d는 depth이다. (시험문제후보)

N + 1 = 1 + B + B2 + … + Bd //이 식을 풀면 된다.

아래의 표는 Depth를 2의 배수로 주고 계산을 한 것이다. Search cost는 실제 몇 개의 노드가 확장되는지 보여준다. 오른쪽에 유효 분기 계수는 유효 분기 계수가 평균 몇 개를 확장했는지 보여준다. 각 단계 별로 B가 얼마나 확장됐는지를.

h1은 첫 번째(missed placed number), h2는 두 번째, 맨하탄이다.

보면 IDS는 컴퓨터로 못 푼다. 26단계까지 가야 되는데 너무 커져서 계산을 하지 못 한다. 그러나 A*는 컴퓨터로 풀 수 있다. A*에서 유효 분기 계수를 보면 평균 1.4니까 자식을 만들 때 2개도 확장 안한다는 소리이다. 1에 가까울수록 디자인이 더 잘 된 것이다. 그래서 h2가 더 좋은 거고.

5장 Beyond classical search

우리는 지금까지 최적의 답이 있는 것들만 생각했었다. 그래서 우리는 길을 찾아갈 수 있었다. 방금 했던 A*도 명확히 해가 있어서 어떤 h(n)이 좋다고 판단할 수 있었다.

그러나 현실 세계에서는 많은 문제들이 있다. 그래서 Optimal solution을 찾을 수 없다.

답이 명확하지 않고, 답이 여러 개이고, 예측할 수 없게 환경이 바뀌기 때문이다. (시험 문제 후보 - 현실 세계 문제의 특징을 써라, 어떤 게 있나?)

ex) 반도체 배선, 각 부서들을 어떻게 나눌지, 무슨 일부터 하는 게 베스트인지, 네비게이션 등..

여기서 우리는 Rational(현재 상태에서 Best를 찾는다)하게 찾아야 한다.

Constraint-satisfaction problem.(제약조건 만족 문제)

충돌이 안 나게 하는 문제들이 여기에 해당된다. N-queens 문제라든지, 시간표 작성, 반도체 배선을 어떻게 할 것인가 라든지. 스케줄링 문제 의 부류가 다 이 문제다.

이런 스케줄링 문제의 부류를 풀려면 Constraint graph 를 이용한다.

4*4의 칸이 있는 n-queens의 문제를 풀으라고 하면 왼쪽부터 q1, q2, q3, q4라고 하고 그림을 그린 후, 차례대로 해보면 된다. q1에는 1, 2, 3, 4를 다 써주고 q2부터 해당되는 숫자를 써주면 된다. 예를 들어, n-queens였을 때 q1이 1이었을 때는 q2에 3, 4가 들어갈 수 있다. 그러나 q3에는 들어갈 수가 없기 때문에 q2에 3을 지워주고 4를 해본다. 이런 식으로 하나하나 다 해보고 q4에 값이 하나라도 완성되면 끝이다.

시험 문제 후보 - Constraint-satisfaction problem 이 문제의 종류에 어떤 것이 있고 어떻게 풀 수 있나?

Local search algorithm

목표가 상관없을 때 쓸 수 있다. 즉, 최대한 좋은 결과를 내고 싶을 때 이 알고리즘을 쓴다. 최대한 Rational하게. 여러 알고리즘이 있는데 이 중, 대표적인 알고리즘이 hill-climbing이다. 가중치가 있다. Optimal하지 않고, Complete하지 않다.

Hill-climbing search

알고리즘을 보면 if조건(내려가는 게 있냐?)이 만족할 때까지 계속 돈다. 즉, 높은 걸 찾다가 내려가는 순간 알고리즘이 끝난다.

장점 : 과거를 돌아보지 않고 계속 올라가기만 한다. 그래서 메모리가 필요 없다. 그리고 알고리즘이 매우 단순하다. 그냥 올라가는 거니까 문제가 명확하지 않아도( 아무리 어렵더라도) 쓰인다.

단점 : 더 높은 게 있어도 찾지 않고 살짝만 내려가도 그냥 끝낸다.(즉, Optimal하지 않다.) 찾은 게 Best가 아니다.

그래도 대부분은 좋은 값을 배출한다.

'h = 충돌 수'로 줘서 h값으로 판단한다. h값이 낮아질 수록 Goal에 가깝다. 그래서 HC(hill climbing)는 h(n)만 본다. 다만 아까 단점에 말했듯이, local maximum에 가면 그걸로 끝난다.

hill climbing의 문제점 3가지.(시험 문제 후보 - 로컬 알고리즘의 문제점)

  1. 목적지가 최상이 아니다. global maximum이 아니라 local maximum 이다.

  2. 메모리가 없어서 내가 어디 있었는지 기억을 못 한다. 즉, plateau (local maximum이 flat할 때) 무한 루프에 빠져 계속 찾게 된다.
  3. 주파수같이 올라갔다 내려갔다 하면 못 푼다( ridges - 능선 )

그럼 이 문제를 어떻게 해결할까? 그 local maximum point를 어떻게 빠져나갈까?(시험문제 후보- 3개)

Hill Climbing을 n queens문제에 h(충돌 수)를 가지고 적용 했더니 1000개중에 140개만 Optimal하게 풀었다. 생각보다 못 풀었다. 그러나 h=0까지가 아니고 h=1을 끝으로 여러 개 줄 수 있도록 하니 문제 푸는 확률이 94%까지 올라갔다. 즉, h=1이 끝이라고 가정했을 때, 원래는 h=1에서 바로 끊겨버리는데 sideways move를 적용하면 h=1이 하나가 아니라 여러 개를 줄 수 있다.(물론 메모리는 더 커지겠지만…) 한 칸 옆으로 움직일 수 있게 허락해 주는 것(h=1을 여러 개 허락해 주는 것)을 sideways move 라고 한다.

Stochastic(probabilistic) hill climbing

산을 올라가는데 무조건 제일 높은 곳(동쪽)이 아니라 남쪽, 북쪽, 서쪽을 랜덤하게 가보는 것을 말한다. 확률론적으로 즉, h가 가장 큰 값으로 가는 게 아니라, 가장 큰 값에서 주변의 조금 작은 값으로 가, 더 위로 올라가는 길을 찾는 것을 말한다. 옆으로도 가고. 비스듬하게 가고. (2차원으로 생각하다가 갑자기 3차원으로 생각한 것 ㅎㅎ;;)

random restart hill climbing.

랜덤하게 starting point. 시작점을 다르게 주는 것이다. 원래 작은 값때문에 못 올라가던 곳을 올라갈 수 있게 해준다.

downhill moves - Simulated annealing(풀림)

칼이 안 부러지게 상온에 서서히 식힘. 물에 집어넣기 위해 상온에다 서서히 식히는 것. 즉, h값이 약간 커지는 것까지는 허용하는 것. h=2가 되는 것까지는 허용하자는 말.

//**********기말고사****************??

\<13장 명제논리\>

추론은 에이전트가 행동을 결정할 때 효율성을 높여준다. 로봇같은 움직임들을 추론하기 위해서 특정값을 표현할 수 있는 언어와 필요한 추론을 수행할 수 있는 추론 방법이 필요하다. 부울 대수에서 파생된 명제논리가 이러한 도구들을 제공한다.

명제 : 참, 거짓을 판별할 수 있는 문장(딱 두 개. 참과 거짓. 이진수와 비슷하다)

Algebra(대수학)

  • Operater(연산자) : +, *, -, 나누기
  • Operand(피연산자) : Number
  • Priority : (우선순위), *, + …
  • Eq.rules(등가법칙) : 교환법칙 등..

Boolean Algebra(부울 대수)

  • Operand에 ∨, ∧, ㄱ, →(집합에서는 ⊃가 동일한 의미이다.)

Algebra(기존의 수체계)와 Boolean Algebra와 다른 점은? (시험후보)

  1. 피연산자가 Proposition(명제)이다.
  2. Operation에 →(implication)이 있다.

→ : if X, then Y (implication, imply, 함축, 함의) - 시험문제후보(3단콤보 - 정의, 표현, 진리표)

  1. Def
  2. X = 0, Y = Don't care(항상 참이 나온다. 거짓이면 Y니까.)
  3. X = 1, Y = 1
  4. Expression : X(1 - Y) = 0
  5. Truth table
X(가정) Y(결론 - Conclusion) X -\> Y
0(거짓) 0 1(참)
0 1 1
1 0 0
1 1 1

Imply문제

(p ∧ ㄱq) → (p ∧ q) = ?는 뭘까?

이러한 문제를 풀 때는 항상 imply부터 없애줘야 한다. 왜냐면 → 얘가 있으면 문제를 풀지 못하기 때문이다. 수체계에 있는 여러 법들(Eq.rules)이 적용되지 않으니까. 그래서 →를 바꿔줘야 한다.

p q ㄱp ㄱp ∨ q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1

위의 표를 보면 p → q와 ㄱp ∨ q의 진리 값이 같다는 것을 알 수 있다. 그래서 표기할 때는 p → q ≡ ㄱp ∨ q 라고 쓴다. 중간에 =(equal)이 아니고 ≡(equivalent)인 이유는 의미론적인 값만 같지, 본질은 연관성이 없고 다르기 때문이다. 예를 들어 크기만 다르고 형태는 같은 삼각형을 보고 합동이라고 하는데 이 때도 ≡(equivalent)를 쓴다.

그래서 바꿔준다. ㄱ(p ∧ ㄱq) ∨ (p ∧ q)가 된다. ㄱ(not)은 단항 연산자이기 때문에 이항 연산자보다 우선순위가 높아 먼저 해준다. 그래서 (ㄱp ∨ q) ∨ (p ∧ q)가 된다.(이 때도 ≡를 써야한다. 여기서 문제가 또 있다.

  1. (ㄱp ∨ q) ∨ (p ∧ q)
  2. (ㄱp ∨ q) ∨ (p ∧ q)

배분해줄 때 앞과 뒤 중에 어느 걸 하냐 이다. 답은 a(앞)인데 이유는 b를 하게 되면 계속 확장돼서 못 풀기 때문이다. a로 풀면 (ㄱp ∨ q ∨ p) ∧ (ㄱp ∨ q ∨ q) 가 되고.(q ∨ q = q이다.) 이는 다시 ㄱp ∨ q가 된다. 이런 식으로 쉽게 바꿔줄 수 있다. 보다 정확한 이유는 ∨가 있는 쪽으로 해주면 된다.

13.2 언어

아톰(atom) = 명제(proposition) : 두 아톰 T(True)와 F(false) 그리고 P, Q, R, … P1, P2 등과 같이 대문자로 시작하는 문자열의 무한대 집합

연결자(connectives) = 연산자(operator) : ∨(or), ∧(and), →(implies), ㄱ(not)

문장(sentences)이라고도 하는 정형식(well-formed formulas, wffs)의 문법

  • 아톰들은 wff(우프)이다.
  • w1과 w2가 wff이면 다음도 wff이다.
  • w1 ∧ w2 (논리합)
  • w1 ∨ w2 (논리곱)
  • w1 → w2 (함의)
  • ㄱw1 (w1의 부정)

리터럴(litreral) : ㄱw1과 같이 아톰에 단항연산자가 붙어있는 것

w1 → w2에서 w1은 Premise(전제), w2는 결론(conclusion)이라고 한다.

어떤 문장이 wff인지는 wff의 정의를 재귀적으로 적용하여 판단할 수 있다. 예를 들어, (P∧Q)→ㄱR이 wff임을 보이자. P와Q가 wff이니까 P∧Q도 wff이다. ㄱR도 wff이다. wff끼리 imply하면 wff이다.

w1과 w2를 1이라고 가정했을 시, wff들로부터 다른 wff들을 만드는 방법은 여러 가지가 있는데, 이들을 추론 규칙(inference rule)이라고 한다.

//***************지금까지 중요한 거 없다고 하심****//

13.3 추론 규칙(Inference rules - w1과 w2는 참이라고 전제를 둔다.)

  • w2는 w1과 w1 → w2 로부터 추론할 수 있다. (이 규칙을 모더스 포넌스(modus ponens)라고 한다.
  • w1 ∧ w2는 w1과 w2로부터 추론할 수 있다.(∧의 소개 - introduction)
  • w2 ∧ w1는 w1 ∧ w2로부터 추론할 수 있다.(∧의 교환성 commutativity)
  • w1은 w1 ∧ w2로부터 추론할 수 있다. (∧의 제거 - elimination)
  • w1 ∨ w2 는 w1나 w2로부터 추론할 수 있다.(∨의 소개 - 여기서 전제가 w1가 true이다. w1이 참이면 무조건 참이므로 추론이 가능하다.)
  • w1은 ㄱ(ㄱw1)로부터 추론할 수 있다.(ㄱ제거)
    • w1 ∨ w2이면 w1이다 (∨ 제거는 안 된다. 0일 수도 1일 수도 있으니까).

Induction(귀납) vs Deduction(연역)

귀납법과 연역법은 다르다. 귀납법은 몇 가지 사례로부터 일반화를 하는 것을 말한다. 예를 들어, 비둘기는 난다, 독수리는 난다. -\> 모든 새는 난다라고 일반화할 수 있다. 하지만 팽귄이나 닭은 날지 못 하기 때문에 귀납법은 틀릴 수 있다.

하지만 이 귀납법과 수학적 귀납법과는 다르다. 이유는 수학적 귀납법은 룰의 베이스를 인간이 만들었기 때문이다. 사람이 만든 룰이라서 완벽하면 끝나지만, 그냥 귀납법은 룰의 베이스가 인간이 만든 게 아닌 물리, 자연현상이기 때문에 항상 틀릴 수 있는 여지가 있는 것이다.

연역법이란 이미 알고있는 하나 또는 둘 이상의 명제를 전제로 하여 명확히 규정된 논리적 형식들에 근거해 새로운 명제를 결론으로 이끌어 내는 추리의 방법이다. Ex) 모든 사람은 죽는다(전제) -\> 소크라테스는 죽는다.

그래서 우리는 연역법을 이용해 추론한다.

집합(SET), 멀티셋(Multiset), 시퀀스(Sequence)

A={1,2}, B={1,2,2} C={2,1,2}

A, B, C가 집합(SET)이라고 할 때 같은 집합은 무엇일까? 답은 다 같다. A, B, C모두 같다. 집합에서는 A, B, C가 같지만 컴퓨터에서 A, B가 같으면 문제가 될 수 있다. 즉, 중복을 허용하지 않는 개념이 나와야 한다.

Multiset(=Bag)으로 하면 A와 B, A와 C는 서로 다르고 B와 C는 같다. 이게 데이터 베이스의 개념이다.

sequence로 한다면 순서까지 개입되기 때문에 A와 B와 C가 모두 다르다. 순서를 허용하지 않는 것이다.

즉, SET, MULTISET, SEQUENCE을 구별하는 데에는 세 가지가 있는데 중복과 순서를 허용하냐 허용하지 않냐의 차이가 있다. 그리고 Multiset이 되어야 sequence까지 갈 수 있다. 왜냐하면 시퀀스는 순서와 중복까지 허용하지 않으니까.

13.4 증명(proof)의 정리

Δ(델타 - sequence) = {w1, w2, … , wn}으로부터 wn이 증명(deduce)될 수 있다는 것을 Δ ㅏ wn 이라고 표기한다. wn을 집합 Δ의 정리(theorems)라고 한다. (ㅏ기호가 deduce이다)

여기에 룰R(추론 규칙)을 적용한다고 했을 때의 표기 법은 Δ ㅏR wn이다. .(즉, 추론 규칙R을 이용하여 추론될 수 있다는 것)

Ex) Δ = {P, R, P -\> Q} 가 있을 때 Q ∧ R이 나올 수 있을까? 를 보면 P를 알면 Q를 추론할 수 있고(modus ponens) Q에 R과 추론 규칙 ∧(and introduction)해서 증명할 수 있게 된다는 소리이다. (Δ안에 있는 P같은 건 '개가 자고 있다'. 근데 옆에 실제로 자고 있다면 T. 의 형식이다)

즉, 추론 규칙 6가지를 적용해서 만들 수 있으면(증명할 수 있으면) 된 것이다.

wff가 주어진 해석 아래 True이면 그 wff를 만족시킨다라고 말한다. 항상 만족시키는 것(타당하다)이 있고 항상 만족시킬 수 없는 것이 있는데 전자를 tautology라고도 부른다. 만족시키지 못하는 것은 p ∧ ㄱp, F 정도가 있다.

tautology

  • p ∨ ㄱp = 1 (항상 1)
  • p -\> p = 1
  • p -\> (q -\> p) = ㄱp u ( ㄱq u p) = 그냥 풀린다. 가로가 둘다 u이니까. = ㄱp u ㄱq u p = 1

//*****************지금까지도 중요한 거 없다고 하심***********//

진리표를 이용하면 지수로 증가한다. 아톰 수에 비례해서. 비효율적.

지금까지 중요한 거 없다.

equivalent rules과 inference rules의 차이는 뭘까(시험문제 후보. 차이점과 예를 하나 드시오)

Eq는 반대방향이 존재하는데 inf는 존재하지 않는다는 것이다. 예를 들어, "P가 참이면 P U Q도 참이다." 라는 명제가 있었을 때 둘다 맞지만 Eq는 역으로 해도(P U Q가 참이면 P도 참이다) 가능한데 INF는 역으로 하면 안 된다는 것(OR Elemination)이다. 말이 그렇다는 소리다. Eq(교환법칙 등)는 양 방향이고 X -\> Y로 가는 것이 Inf이다.

13.5.6과 13.6이 시험문제 후보(정당성과 완전성의 정의)

13.5.6 귀결(Entailment - 꼬리에 꼬리를 따라감)

wff w가 집합 Δ에 있는 모든 wff를 True로 하는 해석에 대해 True 값을 가지면 Δ는 w를 논리적으로 귀결한다(logically entails)고 하며 w는 Δ를 논리적으로 따른다(logically follows)라고 한다. 논리적 귀결은 기호ㅑ를 이용해서 Δㅑw로 표시한다. (진리표가 같은 얘들)

예를 들어, Δ = {P, R, P → Q} 이면 Q ∧ R를 물었을 때 P와 R과 P → Q가 모두 111일 때 Q ∧ R이 1이 됨으로 여기서 Δㅑw가 참이 되는 것이다.

귀결(ㅑ)은 증명할 수 있는 방법이 진리표밖에 없고 진리표가 참이어야 Δㅑw는 참인데 진리표를 이용하면 Δ안에 아톰이 증가할 수록 지수적으로 증가하므로 매우 복잡해진다.( Δ 안에 있는 개수만큼 2의 승수로 들어간다.)

그래서 귀결대신 쓸 수 있는 방법으로 동치관계(≡)가 있다. Δㅑw ≡ ΔㅏR w이기 때문에 inference rules를 쓸 수 있다.Δㅑw 와 ΔㅏR w는 서로 다른 개념이지만 정당성과 완전성에 의해 서로 연관된다. Δㅑw ≡ ΔㅏR w은 서로 왔다 갔다 할 수 있어야 한다. 즉, 귀결 대신 추론을 쓰려면 정당성(Soundness)과 완전성(Completeness)을 증명하고 써야 한다는 뜻이다.

  1. 6 정당성과 완전성

정당성이란 Soundness로 추론(inference - w가 rule을 통해서 유도됐다)에서 귀결(entailment - 논리적으로 w가 참이다)로 가는 것을 의미하고 완전성이란 Completeness로 귀결에서 추론으로 가는 것을 의미한다.

귀결을 위해 추론을 쓰기 위해서는 2가지 정의가 필요하다.

  1. 어떤 wff가 Provable(연역이 가능하다) -\> wff는 True = 집합 R이 정당하다(Sound) //rule을 적용한 문장이 항상 참이 나와야 한다.
  2. 어떤 임의의 wff가 True -\> R을 통해서 증명(연역)이 가능하다 = 집합 R이 완전하다(Complete) //어떤 참인 문장이 rule을 통해서 나올 수 있다.

1번은 그냥 6가지 룰만 정해주면 쉽지만 2번은 문장이 무한대만큼 있을 수 있기 때문에 무한대에 대해서 증명해야 한다. 그래서 더 어렵고 수학적 귀납법을 이용해서 풀 수 있다. 수학적 귀납은 수학자에게 맡기고 우리는 1번만 생각하자.

참고로 정당성과 완전성은 알고리즘에도 쓰인다. 예를 들어, 버블 정렬의 경우, 결과가 정확히 정∑렬되는 것은 정당성, 예외 케이스가 와도 정렬되어야 하는 것은 완전성으로 볼 수 있다.

P.238의 예제 -\> Δ = { B, ㄱM, B ∧ L → M } ㅑ ㄱL 로 만들어 줄 수 있다.'

Δ 명제논리에서의 논리융합(Resolution)

Δ = { w1, w2, w3 } ㅏR w4 //모든 Element에 대해서 룰 6개에 대해 다 체크를 해야한다. 3개만 해도 6개니까 3*6. 18개 + w1`에 대한 것 + …가 나온다. 원소의 수가 많을 수록 더 기하급수적으로 늘어 가기 때문에 줄여야 한다. 그래서 수학자들은 이것들을 1개로 통합할 수 있는 방법을 생각해냈다. 바로 논리융합(Resolution) 이라는 하나의 규칙으로 통합될 수 있다.

리터럴(literal) : 아톰(하나의 명제 - 양의 리터럴) 혹은 아톰의 부정(음의 리터럴) 중의 하나이다.(아톰에 단항 연산자가 붙은 것)

절(clause) : 리터럴의 집합. 리터럴이 OR로 있는 것(논리합 - ㄱP ∨ Q). AND(논리곱)는 term이다. 집합은 그 안에 있는 모든 리터럴의 논리합을 의미한다. 그래서 절은 {}로도 표현된다.

명제 논리에서 논리융합 규칙은 다음과 같이 정리될 수 있다.

( { λ } ∪∑1 ) ∧ ( {ㄱλ} ∪∑2 )으로부터 ∑1 ∪ ∑2을 추론할 수 있고 이 과정을 논리 융합(Resolution)이라고 한다. 정확한 식은 ( { λ } ∪∑1 ) ∧ ( {ㄱλ} ∪∑2 ) ㅏres ∑1 ∪ ∑2 이다. 몇 가지 예를 살펴보자.

  • R ∨ P와 ㄱP ∨ Q는 R ∨ Q로 Resolution된다.(ㄱR → Q) 두 절은 함의를 이용하면 ㄱR⊃P와 P⊃Q로 나타낼 수 있다. 연결(Chaining - A -\> B, B -\> C는 A -\> C)이라는 추론 규칙이 이 함의들에 적용되면 ㄱR⊃Q가 나오며 이는 논리융합식 R ∨ Q와 동치이다. 연결은 논리융합의 특별한 경우이다.
  • R과 ㄱR ∨ P는 P로 논리융합된다. 두 번째 절이 R⊃P와 동치이므로 모더스 포넌스(modus ponens)도 논리융합의 특별한 경우이다.

14.1.3 논리융합의 정당성

앞서 소개된 논리융합은 정당한(sound) 추론 규칙이다. 즉, { λ } ∪∑1 과 {ㄱλ} ∪∑2 가 둘 다 True값을 가지면 그들의 논리융합식, ∑1 ∪ ∑2도 True이다. 이를 증명하는 방법은 한 가지 방법은 "사례별로 추론"을 하는 것이다. 직접 증명법이라고도 하는 이 방법은 λ가 True일 때와 λ가 false일 때 모두 구하면 되는 것이다.

  1. 1)λ가 True이면 { λ } ∪∑1는 무조건 1이 되고 {ㄱλ} ∪∑2은 ∑2이다. 교집합이니까. 1 ∧ ∑2인데 전제가 1이 되어야 하므로 ∑2는 1이 된다. 그래서 ∑1 ∪∑2은 1이 된다.
  2. 2)λ가 False일 때는 반대이니 똑같다.

그러므로 ∑1 ∪∑2은 True값을 가진다.

14.2 임의의 wff를 절의 논리곱으로 변환하기

명제논리의 임의의 wff는 이와 동치인 절의 논리곱으로 변환할 수 있다. 절의 논리곱으로 나타낸 wff를 논리곱 정규형(Conjunctive normal form, CNF)이라고 한다. 예를 들어 ㄱ(P⊃Q) ∨ (R⊃P)를 푸는 방식은

  1. 함의 기호를 ∨를 이용하는 동치식으로 바꾸어 없앤다.
  2. ㄱ(ㄱP ∨ Q) ∨ (ㄱR ∨ P)
  3. 드모르간의 법칙을 이용하여 이중 ㄱ기호를 없앤다.
  4. (P ∧ ㄱQ) ∨ (ㄱR ∨ P) //왼쪽으로 분배를 해준다. 왜냐면 ∨∨가 있으니까.
  5. 결합 법칙과 배분 법칙을 이용하여 CNF로 변환한다.
  6. (P ∨ ㄱR) ∧ (ㄱQ ∨ ㄱR ∨ P)
  7. 절의 논리곱(wff의 CNF형태)은 보통 절의 집합으로 다음과 같이 표시된다.
  8. Δ = {(P ∨ ㄱR), (ㄱQ ∨ ㄱR ∨ P)}

하지만 이 답은 Resolution이 안 된다. 왜냐면 ㄱP가 없고 R도 없기때문에 없어지질 않는다. 즉, Resolution은 sound하나 complete하지 않다.

14.3 논리융합 반박(Resolution refutation - proof by controdiction)

우리는 이미 논리융합이 정당한 추론 규칙임을 보았다. r이 하나의 절일 때, Δ ㅏres r은 Δㅑr을 함의한다. 즉, r이 참이라는 것을 의미한다. 그러나 논리융합이 완전하지는 않다. 예를 들어, P ∧ R ㅑ P ∨ R이지만 {P, R}은 없어질 게 없으므로 논리융합의 방법으로 추론할 수 없다. 허나 이는 또 모순의 의한 증명으로 풀 수 있다. Resolution은 항상 참이므로 반대도 성립해야 된다는 것이다.

  1. Δ에 있는 wff들을 절 형태(clause), 즉 절의 논리곱 집합의 형태로 바꾼다.
  2. 증명하고자 하는 w의 부정을 절 형태로 바꾼다.
  3. 1과 2단계의 결과인 절들을 하나의 집합 Δ`에 합친다.
  4. Δ`에 있는 절에 논리융합을 적용하여 결과를 다시 넣는 작업을 더 이상 추가될 논리융합식이 없거나 공절(공집합)이 나올 때까지 반복한다.

즉, Resolution은 Sound하기만 하나 refutation을 붙이면 Complete해진다.

예를 들어보자.

  1. Δ = { A, B, A ∧ D → C, B → D } ㅑ C
  2. Δ` = { A, B, ㄱ(A ∧ D) ∨ C, ㄱB ∨ D} ㅏ ㄱC
  3. Δ` = A, B, ㄱ(A ∧ D) ∨ C, ㄱB ∨ D, ㄱC //이때 결과인 ㄱC를 기준으로 차례대로 풀어준다. 그러다보면 공집합이 나온다.

14.5 Horn 절(이거 다 시험후보임)

절의 형태 중에서 AI 및 여러 컴퓨터 과학 분야에서 중요하게 다루어지는 특수한 형태가 있다. Horn 절은 최대 1개의 양 리터럴만 갖는 형태의 절이다. (Positive 리터럴이 하나만 있는 것)

3가지 형태가 있다.

  1. 단일 아톰 - 사실(Fact)라고 한다. //P, Q, R등…
  2. 함의 - 앞은 양 리터럴의 논리곱으로 이루어지고 결론부는 단일 양 리터럴로 이루어진 형태 규칙(rule)이라고 한다. //P → Q 등
  3. 음 리터럴의 집합. 전제는 양 리터럴의 논리곱으로 이루어져 있고 결론은 비어있는 함의의 형태이다. 이와 같은 절을 목표(goal)이라고 한다. //P → Ф이라고 한다.

명제논리의 Horn절에 대한 중요한 사실은 선형 시간 연역 알고리즘이 존재한다는 것이다. 즉, Horn절이어야 컴퓨터가 풀 수 있다.

시험문제 후보

  1. 논리융합의 정의
  2. 왜 논리융합 반박을 하는지
  3. 논리융합 반박으로 풀어라
  4. Horn의 정의, 형태, 효과(horn절이어야 컴퓨터가 풀 수 있다)

15장 술어논리

실세계에 대한 명제뿐만 아니라 실세계에 존재하는 객체를 나타낼 수 있는 언어라면 더욱 유용할 것이다. 이렇게 객체, 변수를 나타낼 수 있는 것이 술어논리이다.

시험문제 후보

술어의 의미는? -\> 명제는 참, 거짓을 판별할 수 있는 문장이고 술어는 명제에서 주어를 변수로 두고 술어 부분만 빼 온 것을 말한다.

명제(Proposition)와 술어(Predicate)의 차이(3단논법의 폐해를 막을 수 있음 - H(x) -\> M(x), M(x) -\> B(x)에서 그대로 이어지지 않고 변수를 바꾸거나 앞에 한정사를 써서 막을 수 있다.)

  1. 변수
  2. 한정사(모든(∀ - 전체 한정사) or 어떤(∃ - 존재 한정사))

Δ = { P(x) ∨ Q(x), ㄱP(y) } 에서 P(x)와 P(y)는 같은 함수다. 여기서 P(f(x))처럼 함수가 들어갈 수 있는데 P를 관계상수(Predicate)라고 하고 f(x)를 함수상수(Functor)라고 한다.

한정사

U = { a, b, c }일 때, ∀x와 ∃x의 의미는 아래와 같다.

∀xP(x) = P(a) ∧ P(b) ∧ P(c)

∃xP(x) = P(a) ∨ P(b) ∨ P(c)

한정사에 대하여 드모르간의 법칙과 유사한 다음과 같은 동치 관계가 성립한다.

ㄱ∀xP(x) ≡ ∃xㄱP(x) - 그냥 해보면 나온다.

∀xㄱP(x) ≡ ㄱ∃xP(x) - 얘도 해보면 나온다.

명제논리에서 추론 규칙을 잘 확장하면 술어논리에서도 사용할 수 있다.

∀xP(x) -\> P(a), P(a) -\> ∃xP(x)

16장 술어논리에서의 논리융합

문제 1) Δ = { P(x), ㄱP(y) } 여기서 융합하려면 어떻게 해야할까?

  1. 전자의 인자x를 y로 바꾼다.
  2. 후자의 인자를 x로 바꾼다.
  • 답은 둘 다 상관없다. 변수(Variable)를 바꾸는 것이기 때문에. 다만 알파벳 순으로 하는 게 좋으므로 2번이 더 낫다.

문제 2) Δ = { P(x), ㄱP(A) } 여기서 융합하려면 어떻게 해야할까?(A는 상수이다.)

  1. 전자의 인자 x를 A로 바꾼다.
  2. 후자의 인자 A를 x로 바꾼다.
  • 답은 1번이다. 왜냐하면 최대한 정보가 많은 상수(Constant)를 가져야 하기 때문이다.

문제 3) Δ = { P(A), ㄱP(B) } 여기서 융합하려면 어떻게 해야할까?(A, B는 상수이다.)

  1. 전자의 인자 A를 B로 바꾼다.
  2. 후자의 인자 B를 A로 바꾼다.
  • 답은 둘다 안 된다. 왜냐햐면 그 상수 자체를 바꾸는 것이기 때문에.

문제 3) Δ = { P(f(y), A) ∨ Q(B, C), ㄱP(x, A) ∨ R(x, C) ∨ S(A, B) } 여기서 융합하려면 어떻게 해야할까?(A, B, C는 상수이다.)

  1. 전자의 P 인자 f(y)를 x로 바꾼다.
  2. 후자의 P 인자 x를 f(y)로 바꾼다.
  • 답은 2번이다. 왜냐하면 변수에 함수를 넣는 건 가능하지만 함수에 변수를 넣는 건 안 되기 때문이다. 예를 들어, int y = sq(x)는 되지만 int sq(x) = y는 안 된다.

p.271

16.1 단일화

여기서 λ1, λ2, … λn 는 변수 x1, x2 … xn을 포함하고 있는 리터럴을 나타낸다. 하나의 절을 { λ

1, λ2, … λn} 와 같은 집합 형식으로 표현하기도 하는데 이런 경우 각 원소들이 논리합으로 연결되어 있는 것으로 가정한다.

두 절이 똑같은 리터럴을 포함하고 있으면서 각 리터럴이 서로 상반된 경우 명제논리에서와 마찬가지로 이 둘을 논리융합(resolution) 할 수 있다.

예를 들어, 두 절 P(f(y), A) ∨ Q( B, C) 와 ㄱP(x, A) ∨ R( x, C) ∨ S(A, B)가 있다고 하자. 두 번째 절에서 x를 f(y)로 치환하면 ㄱP(f(y), A) ∨ R( f(y), C) ∨ S(A, B)가 된다. 그러면 두 번째 절의 첫 번째 리터럴은 첫 번째 절의 첫 번째 리터럴과 정확히 상반되는 꼴이다. 따라서 이 리터럴에 대하여 논리융합을 수행하면 R( f(y), C) ∨ S(A, B) ∨ Q( B, C)라는 논리융합식을 얻게 된다.

이러한 치환은 단일화(unification)라는 과정에 의해 이루어진다.

정형식의 각 항은 변수, 객체 상수, 또는 함수식 등이 가능하다. 여기서 함수식이란 함수 상수와 항으로 이루어진 것을 의미한다.

예를 들어, P(x, f(y), B)를 치환해 보자. 4가지 경우가 있다.

P(z, f(w), B) (z / x, w / y) Variable -\> Variable(변수)
P(x, f(A), B) (A / y) Variable -\> Constant(상수)
P(g(z), f(A), B) (g(z) / x, A /y) Variable -\> functor(함수식)
P(c, f(A), B) (C /x, A / y) Variable -\> Constant(상수)

(A / y)의 의미는 y를 A로 치환하겠다는 의미이다. '퍼'라고 발음한다.

어떤 식 w를 s로 치환한 치환 사례를 ws와 같이 표기하기로 한다.

치환 합성은 결합 법칙이 성립한다. 따라서 (s1s2)s3 = s1(s2s3)가 성립한다. (ws1)s2 = w(s1s2)

일반적으로 치환은 교환법칙이 성립하지 않는다. s1s2=s2s1의 관계가 성립하지 않는다. w(s1s2)과w(s2s1)은 다르다.

w1s= w2s=…의 관계가 성립하는 s를 단일자(unifier)라고 한다. 즉, 치환을 했을 때 항상 같게 만드는 놈이다. 그러나 가장 간단한 형태의 단일자는 아닌데 하다보면 줄일 수 있다. 가장 간단한 단일자를 mgu(most general unifier)라고 한다.

즉, 이렇게 predicate(관계 상수)가 단일화되어야 논리융합이 가능하다.

UNIFY 알고리즘의 기초는 불일치 집합이라는 개념이다. 공집합이 아닌 정형식의 집합 W에 대한 불일치 집합을 얻기 위해서는 …. 부분식을 추출하면 된다.

UNIFY (Γ) (Γ는 리스트로 표현된 정형식의 집합을 나타낸다.) - (mgu를 구하라 시험문제후보)

  1. k = 0, Γk = Γ, δk = ε (ε는 공집합을 나타낸다. 처음이다. 즉, = Ф)
  2. 만약 Γk가 하나의 정형식인 경우에는 δk로 단일화가 종료된다. 이 때 δk는 Γ에 대한 mgu가 된다. 그렇지 않은 경우에는 단일화를 계속 한다. //여기서 같은 여러 개의 집합은 하나의 집합이 되므로 합쳐주면 된다. 즉, 한 개가 되고 종료된다.
  3. Dk = (Γk에 대한 불일치 집합) //처음부터 쭉 스캐닝 한다. 그리고 다른 게 있으면 체크하고 집합에 넣어준다. 뒤로 더 가지 않는다. 한 개만 뽑는다. //여기서 D = {y, z}와 같이 나온다.
  4. vk는 tk에 나타나지 않는 변수라고 하자. 이러한 조건을 만족하는 변수 vk와 tk가 Dk에 존재하는 경우에는 단일화를 계속한다. 그렇지 않은 경우에는 단일화가 실패된 것으로 보고 단일화를 종료한다. 즉, 이러한 경우는 Γ는 단일화 할 수 없다. (무한 루프이기 떄문에) // δ를 구했는데 δ = {f(x) / x}와 같이 tk안에 vk가 속해 있을 때이다. 이러면 그 뒤에 가서도 δ = {f(x) / x}가 나와 무한 반복된다. p.285 16.1.3 참조.
  5. = { / }, = { / } (= 임에 주의하라) //여기서 아까 나온 D = {y, z}에서 를 {y / z}로 할 것인지 {z / y}로 할 것인지 고민해봐야 한다. 보통 저렇게 변수끼리 나온다면 알파벳 순서(빠른 거 기준 - y / z)로 하고 변수와 상수가 나오면 상수의 정보는 바뀔 수 없으니 A / y처럼 변수에 상수를 넣어줘야 한다. 함수식도 마찬가지로 바뀔 수 없으니 변수에 함수를 넣어준다. ({g(A, x) / z}와 같이 상수가 섞여 있어도 통째로 바꿔준다.)
  6. k = k+1
  7. 단계 2로 간다.

마지막으로 나오는 mgu = {B / z}{A / z}{A /z}의 형태로 되고 교환법칙이 성립 안 되므로 순서를 바꾸면 안 된다. = { / } 이므로 D0에서 나온 걸 원래의 뒤에다 붙여야 한다.

16.2 술어논리 논리융합

r1과 r2를 각각 리터럴의 집합으로 표현된 절이라고 하자. r1에 아톰 Ф(phi = predicate = P(x))가 있고 r2에 리터럴 ㄱψ(psi = predicate)가 있을 때 Ф와ψ가 mgu를 가지고 있다면 이 두 절은 논리융합식 ρ(ro = result)를 가진다. 논리융합식은 r1과 r2의 합집합에 치환 mgu를 적용함으로써 얻어진다. (쉽게 말하면 Ф = P(x), ψ = P(y)라고 보면 된다) (P(x) ∨ Q(x) 가 r1이고 ㄱP(y) ∨ R(y) 가 r2이다) ( Ф = ψ{ x / y } )

Δ = { P(x) ∨ Q(x), ㄱP(y) ∨ R(y) }

여기서 ㄱP(y) ∨ R(y)에서 { x / y }를 함으로써 P(x)와 ㄱP(x) 을 없애서 논리융합으로 Q(x) ∨ R(x)를 얻을 수 있다.

16.3 완전성과 정당성

술어논리에서의 논리융합은 정당(sound)하다. 명제논리에서와 마찬가지로 주어진 정형식의 집합으로부터 논리적으로 귀결되는 모든 식을 추론할 수 없다. 명제논리에서 했듯이 논리융합 반박(resolution refutation)을 이용하여 이러한 문제점을 술어논리에서 극복할 수 있다.

16.4 임의 정형식을 절 형태로 변환하기

명제논리에서와 같이 임의의 정형식을 다음과 같은 단계에 따라 절 형태로 변환할 수 있다. (시험문제 후보)

  1. 함의( -\> )를 나타내는 부호를 제거한다. //그래야 not(ㄱ)이 앞으로 가서 ∃x를 바꿀 수 있다. 처음에 함의를 줄 때 ㄱ(not)을 붙일 때 가로가 다 들어간다. 조심!
  2. 부정을 나타내는 부호의 범위를 줄인다.
  3. 변수 표준화를 한다. 각 한정사가 한정하는 변수의 이름이 유일하도록 변수명을 바꾼다.
  4. 존재 한정사(∃)를 제거한다. // 예를 들어보자. (∀x) [(∃y)Height(x, y)] 에서 존재 한정사는 전체 한정사의 범위 내에 있다. 따라서 y는 x의 값에 의존하게 된다. ∃를 없애줘야 하는 이유는 만약 ∀y가 되면 모든 x가 돼서 때문에 무한대가 된다. 여기서 풀 수 있는 방법이 있는데 바로 skolem 함수(h(x))이다. y대신 skolem 함수를 쓰면 존재 한정사를 제거할 수 있다. (∀x) [(∃y)Height(x, y)]는 (∀x) [Height(x, h(x))] 로 바꿔진다. 여기서 중요한 게 여기서 사용된 Skolem 함수의 인자는 현재 제거중인 존재 한정사의 범위를 포함하는 전체 한정사에 의해 한정을 받는 변수들로 이루어진다.
  5. prenex 형식으로 변경한다. //∀(전체 한정사)를 앞으로 다 뺀다
  6. 명제논리에서와 마찬가지로 행렬을 논리곱 정규형으로 변형한다. //즉, 분배한다
  7. 전체 한정사를 제거한다.
  8. 논리곱 ∧ 기호를 제거한다.
  9. 변수 이름을 변경한다.

자 이제 연습해보자.

∀x ( ∃y { P(x, y) ∧ Q (y, x) -\> R(x) } ) 를 바꿔보자.

  1. ∀x ( ∃y { ㄱP(x, y) ∨ ㄱQ (y, x) ∨ R(x) } )
  2. 이미 안에 있으니 넘어가고
  3. 넘어간다.
  4. ∀x { ㄱP(x, h(x) ) ∨ ㄱQ (h(x), x) ∨ R(x) }
  5. 이미 앞으로 나와있다.
  6. 분배가 안 된다.
  7. { ㄱP(x, h(x) ) ∨ ㄱQ (h(x), x) ∨ R(x) }
  8. 없고
  9. 없다.

답 : ㄱP(x, h(x) ) ∨ ㄱQ (h(x), x) ∨ R(x)

{ ∃xP(x) ∨∃xQ(x) } -\> ∃x(P(x) ∨ Q(x)) 를 바꿔보자. (가로를 잘 보자)

  1. { ㄱ∃xㄱP(x) ∧ ㄱ∃xㄱQ(x) } ∨∃x(P(x) ∨ Q(x)) //조심해야 할 게 ∃xP(x) 여기서 not을 붙이면 따로따로 줘야 한다. 바로 바뀌는 게 아니고.
  2. { ∀xㄱP(x) ∧∀xㄱQ(x) } ∨∃x(P(x) ∨ Q(x))
  3. { ∀xㄱP(x) ∧∀yㄱQ(y) } ∨∃x(P(x) ∨ Q(x)) //각 한정사가 한정하는 변수의 이름이 유일하도록 바꿔줘야 하니까 앞 쪽에 있는 전체 한정사 중 하나를 y로 바꾼다. 같으면 안 되니까?

//여기서 조심해야 할 게 오른쪽(전체 한정사가 있는 곳)과 왼쪽(존재 한정사가 있는 곳)에 있는 x는 서로 다른 x다. 왜냐하면 서로 앞에 전체 한정자가 있기 때문에 . 존재 한정사에 묶여있는 얘들은 또 다른 x이다.

//∀x[ㄱP(x) -\>∀y[∃zㄱQ(x, y) ∨∃zㄱR(y, x)]]의 경우 존재 한정사가 z로 되어있으니 그냥 없애줘도 된다.

//∃xㄱP(x) ∨ ∃x(∀zQ(x, z) ∨ ∀zR(x, y, z)) //전체 한정사 범위 밖에 있으니 x를 상수로 만들어주고 전체 한정사는 유일하게 w같은 걸로 바꿔준 후, 앞으로 빼내서 바꿔주면 된다.

//그냥, 존재 한정사는 전체 한정사 바깥에 있을 때 상수로 바꿔주면 되고 안에 있을 때는 Skolem 함수로 해주면 된다.

  1. { ∀xㄱP(x) ∧∀yㄱQ(y) } ∨ (P(A) ∨ Q(A)) // 그 다음에는 존재 한정사를 없애줘야 한다. 제거중인 존재 한정사가 전체 한정사 범위 밖에 있다면 인자가 없는 Skolem함수 즉, 상수를 사용한다. 따라서 ∃xP(x)는 P(A)가 된다. 전체 범위니까 가로를 잘 쳐줘야 한다.
  2. ∀x∀y {ㄱP(x) ∧ ㄱQ(y) } ∨ (P(A) ∨ Q(A)) //이제 앞으로 빼준다. ∀x나 ∀y를 꺼낼 때 주변 상황을 잘 봐야한다. 세 가지 경우를 봐야한다. 1) 동위치 선상에 있는지, 2) 반대쪽에 같은 게 있는지, 3) 전체적으로 판단(중가로를 넘어서까지 봐야한다)
  3. ∀x∀y {ㄱP(x) ∨ (P(A) ∨ Q(A)) } ∧ { ㄱQ(y) ∨ (P(A) ∨ Q(A)) } //분배 ∨∨의 쪽으로.
  4. {ㄱP(x) ∨ (P(A) ∨ Q(A)) } ∧ { ㄱQ(y) ∨ (P(A) ∨ Q(A)) } //전체 한정사 삭제
  5. Δ = {ㄱP(x) ∨ (P(A) ∨ Q(A)) , ㄱQ(y) ∨ (P(A) ∨ Q(A)) } //논리곱을 ,로 만들어준다.

짐꾸러미를 운반하는 로봇을 예로 들어보자. 이 로봇은 27번방에 있는 모든 짐꾸러미가 28번 방에 있는 것보다 작다는 것을 알고 있다고 하자. 따라서 아래와 같이 된다.

Δ = (∀x, y) [Package(x) ∧ Package(y) ∧ Inroom(x, 27) ∧ Inroom(y, 28)] -\> Smaller(x, y)

술어 기호를 이용해 표현하면

P(x) ∧ P(y) ∧ I(x, 27) ∧ I(y, 28) -\> S(x, y)가 된다.

P(x) ∧ P(y) ∧ I(x, 27) ∧ I(y, 28) -\> S(x, y) 얘네들을 정리하면 ㄱP(x) ∨ ㄱP(y) ∨ ㄱI(x, 27) ∨ ㄱI(y, 28) ∨ S(x, y)가 된다.

로봇이 어느 방인지는 모르지만 27번 방 아니면 28번 방에 짐꾸러미 A가 있다는 사실을 알고 있다고 하자. 이 로봇은 짐꾸러미 B가 27번 방에 있으며, 짐꾸러미 B는 짐꾸러미 A보다 작지 않다는 것을 알고 있다.

얘를 다시 술어 기호를 이용해 표현하면

P(A), P(B), I(A, 27) ∨ I(A, 28), I(B, 27), ㄱS(B, A) 이다.

정리하면

Δ = { ㄱP(x) ∨ ㄱP(y) ∨ ㄱI(x, 27) ∨ ㄱI(y, 28) ∨ S(x, y), P(A), P(B), I(A, 27) ∨ I(A, 28), I(B, 27), ㄱS(B, A) } ㅏ I(A, 27) 이 된다.

논리융합 반박을 이용해서 바꿔보자.

Δ = { ㄱP(x) ∨ ㄱP(y) ∨ ㄱI(x, 27) ∨ ㄱI(y, 28) ∨ S(x, y), P(A), P(B), I(A, 27) ∨ I(A, 28), I(B, 27), ㄱS(B, A), ㄱI(A, 27) }

ㄱI(A, 27) 와 I(A, 27) ∨ I(A, 28) 을 하면 I(A, 28)가 남고 얘를 ㄱP(x) ∨ ㄱP(y) ∨ ㄱI(x, 27) ∨ ㄱI(y, 28) ∨ S(x, y)와 하면 된다. 뒤 상수 28은 바꿀 수 없으니 {A / y}를 해주면 날라가고 ㄱP(x) ∨ ㄱP(A) ∨ ㄱI(x, 27) ∨ S(x, A) 가 남는다. {B / x}를 해서 P(A)와 P(B)로 날리고 다 날라간 후 Ф이 된다.

논리적 추론 시스템의 세 가지 주요한 성질로 정당성(Soundness), 완전성(Completeness), 유순성(Tractability - 현재 주어진 메모리 안에서 풀 수 있어야 한다)

17.2 Horn 절을 이용한 추론

Horn절은 양의 리터럴이 많아야 한 개만 있는 절이라고 정의한 바 있다.

  1. 적어도 하나 이상의 음의 리터럴(ㄱP)과 하나의 양의 리터럴(Q)이 있다면 Horn 절은 전제부가 양의 리터럴의 논리곱이고 결과부가 하나의 양의 리터럴인 함의로 다시 쓸 수 있다. 이러한 형태의 절을 ' 규칙(Rule)'이라고 한다.
  2. 사실(Fact) : 주어진 절에 음의 리터럴이 하나도 없는 경우도 있다. 이러한 경우 주어진 절은 전제부가 공백이고 결과부는 하나의 양의 리터럴로 이루어진 함의로 쓸 수 있는 절을 '사실(Fact)'이라고 한다.
  3. 주어진 절에 양의 리터럴이 하나도 없는 경우도 있을 수 있다. 이러한 경우 우리는 결과부는 공백이고 전제부는 양의 리터럴들의 리스트인 함의로 쓸 수 있다. 이러한 절을 목표(Goal)이라고 부른다.

Horn절은 PROLOG(Programming Logic)와 같은 프로그래밍 언어의 기초가 된다.

PROLOG 절에 대한 추론은 목표절(Goal clause)에 대한 증명을 의미하는데 이는 PROLOG프로그램을 수행함으로써 이루어진다. 이러한 증명은 PROLOG 형식으로 표현된 사실, 목표, 규칙에 대하여 수행되는 논리융합과 유사한 연산에 의해 이루어진다.

PROLOG 프로그램은 목표절, 사실, 규칙 순(GFR)으로 나열되는 것이 보통이다. PROLOG 인터프리터는 주어진 목표절과 논리융합이 가능한 절이 있는지 차례대로 살펴본다.

예를 들어보자.

P ∧ Q -\> R : Rule, Ф -\> R (Fact), P ∧ Q -\> Ф (Goal)

Δ(Sequence) = { P ∧ Q-\> R, P, Q} ㅏR 이라면

R : - P, Q // P : - // Q : - // : - R(앞에 아무 것도 없다.) 로 쓸 수 있다. 쓰는 방법이 모두 다르니 조심하자.

Δ = { B ∧ L -\> M, B, L } ㅏ M 을 풀어보자. (시험문제후보 - 델타를 보여주고 Resolution, Prolog, tree 총 3가지에 대해서 쓰라고 한다. 명제로 낼 수도, Predicate로 낼 수 있다.)

  1. Resolution : Δ = { ㄱB ∨ ㄱL ∨ M, B, L, ㄱM }
  2. ㄱM과 ㄱB ∨ ㄱL ∨ M을 융합하면 ㄱB ∨ ㄱL이 된다.
  3. ㄱB ∨ ㄱL을 B와 융합해서 ㄱL이 된다.
  4. ㄱL을 L와 융합해서 Ф으로 Resolution 된다.
  5. Prolog(GFR 순으로 정의하고 중요한 건 목표를 not한 걸로 하는 게 아니라 추론이 있는 걸로 해야 한다.)
  6. : - M
  7. B : -
  8. L : -
  9. M : - B, L
  10. AND OR tree(Prolog의 순서로 위에서 아래로 찾는다. 안 보이면 맨 위로 가서 반복한다)
  11. Prolog의 첫 번째 : - M을 그린다. (목표)
  12. 이제 밑으로 내려가는데 왼쪽에 M이 있나 없나 찾는다. 없으면 다시 아래로, 있으면 그걸 써주면 된다.
  13. D에 있다. M이 B와 L로 나누어 진다. ,니까 AND로 써준다. (AND 노드 표시!)
  14. 끝까지 왔으니 다시 위로 올라가서 내려온다. B가 있으니 써주고 L이 있으니까 써준다.

이 그림에서 각 사각형내의 노드들은 PROLOG 프로그램의 각 문장(목표, 규칙, 사실)에 해당한다. 각 노드에는 위의 문장 번호를 명시하였다. 노드와 노드를 연결하는 아크는 매치아크(match arc)와 규칙아크(rule arc)의 두 종류가 있다. 매치아크는 겹선으로 나타내며 규칙아크는 단선으로 나타낸다.

블록세계를 이용하여 변수를 사용한 예를 보자. 어떤 블록이 다른 블록(바로 위에 있다는 것이 아니라) 위쪽에 있다(above)는 개념을 사용하려고 한다. 술어논리를 사용하여 위쪽이라는 개념은 다음과 같은 식을 재귀적으로 적용하여 정의할 수 있다. 여기서 On은 "바로 위"를 나타낸다.

(∀x, y)[On(x, y) -\> Above(x, y)]

(∀x, y, z){(∃z)[On(x, z) ∧ Above(z, y)] -\> Above(x, y)}

블록 A가 블록 B 바로 위에 있고 블록 B가 블록 C 바로 위에 있다면 블록 A가 블록 C의 위쪽에 있다는 것을 증명할 수 있다.

Δ = { O(x, y) -\> A(x, y), O(x, z) ∧ A(z, y) -\> A(x, y), O(A, B), O(B, C) } ㅏ A(A, C)

델타가 위와 같이 주어지면 일단 Resolution부터 해보자.

  1. Resolution : Δ = { ㄱO(x, y) ∨ A(x, y), ㄱO(x, z) ∨ A(z, y) ∨ A(x, y), O(A, B), O(B, C), ㄱA(A, C) } //보기 쉽게 하기 위해서 Δ = { 1, 2, 3, 4, 5 }라고 해보자.

  2. 1)5는 1, 2를 융합시킬 수 있다.
  3. 2)5와 1을 먼저 해본다.
  4. 3){A / x, C / y}를 하면 ㄱO(A, C)이다.
  5. 4)매치를 시켜줘야하는데 ㄱO(A, C)는 상수이므로 대체가 불가능하다. 그래서 3과 5하고도 되지 않는다. 여기서 백 트레킹으로 뒤로 돌아간다.
  6. 5)5와 2를 해본다.
  7. 6){A / x, C / y}를 하면 ㄱO(A, z) ∨ ㄱA(z, C)이다.
  8. 7)3번과 가능하다. {B / z}
  9. 8)ㄱA(B, C)를 1번과 한다. {B / x, C / y}

  10. 9)ㄱO(B, C)만 남고 Ф으로 Resolution이 된다.

  11. Prolog

  12. 1): - A(A, C)
  13. 2)O(A, B) : -
  14. 3)O(B, C) : -
  15. 4)A(x, y) : - O(x, y)

  16. 5)A(x, y) : - O(x, z), A(z, y)

  17. AND OR tree

  18. 1)첫 번째로 목표를 그려주고
  19. 2){ A / x, C / y }를 먼저 해주고 차례대로 내려가니 4번을 그려준다. O(A, C)에 해당하는 것을 찾는데 없다.
  20. 3)이러면 다시 백트레킹을 해서 다른 걸 찾아야 한다. 백트레킹이 OR 노드이고(따로 표기는 없는듯?) 백트레킹을 할 때 4번에서 5번으로 그대로 내려온다.
  21. 4)똑같이 { A / x, C / y }를 먼저 해준다. 5번을 그려준다. AND표시도 그려준다. 그려줄 때 그 뒤에 오는 노드들도 mgu가 적용된 채로 그려줘야 한다.
  22. 5)Prolog의 처음부터 가서 내려오니까 O(A, B)를 해준다. {B / z}를 먼저 해주고 그린다. ok됐고
  23. 6)똑같은 노드의 위치이므로 똑같은 룰({B / z})을 적용시킨다. 그래서 A(B, C)를 해준다. 2번은 OK됐으니 빠지고 3번으로 넘어가 O(B, C)가 된다.
  24. 7)그리고 이제 바로 3번을 찾으면 끝이다.

문제풀이는 내가 사진으로 찍어 놓았다.

4차 산업혁명.

4차가 왜 나왔냐. 인터넷때문에.

소비자들이 똑똑. 소비자들의 요구가 다양해짐. 소비자 맞춤형으로 제작.

SNS를 통해 똑똑해짐. 빅데이터. 인공지능.

기업이 뭘 개발하고 있는지.