Logical Inference, Syntax of Propositional Logic, Semantics of Propositional Logic

Logical Inference

- logical entailment between sentence

• KB |= a 는 KB가 참이면 a가 참임을 의미한다. 

-  KB 가 논리적으로 a를 entail 하는지를 결정하는 알고리즘이 필요하다. 

• (Logical) inference algorithms 

- model checking algorithm

• M(a) 가 M(B) 의 부분집합인지 확인한다.

  

    

- 알고리즘 i의 결과는 KB가 a를 entail 할 수도 있고, entail 하지 않을 수도 있다.

 

 

Properties of (Logical) Inference Algorithms

- Soundness

• entail 된 sentence 만 유도한다. -> KB |= a 는 KB 에서 a가 유도된다라고 말할 수 있다.
• 실제로 entail 이 된 sentence 이지만, 유도되지 않을 수도 있다.
• 어떤 알고리즘은 모든 sentence 에 대해서 no라고 하며 유도하지 않는데, 이 알고리즘은 sound 하다. 
• -> soundness 는 yes 라고 했을 때만 entail 인지 확인하므로, 이 알고리즘은 yes 가 없어서 sound 하다.
• 즉, no는 상관이 없고, yes 한 것 중 entail 되지 않은 것이 있을 때만 sound 하지 않은 것이다.

 

- Completeness

• 모든 entaill 된 sentence 는 유도되어야 한다.
• 그러나, 실제로는 유도된 sentence 가 entail 하지 않을 수도 있다.
• 모든 sentence 에 대해서 yes라고 하는, 즉 모든 sentence 가 유도되는 알고리즘이 존재할 때, 이 알고리즘은 completeness 하다.
• 즉, 모든 entail 된 sentence 이든 아니든 모두 유도되기 때문에, 모든 entail sentence 는 yes 이므로 completeness 를 만족하는 것이다. 그러나, sound 하지는 않다. 왜냐하면 yes 된 것 중 entail 하지 않은 것도 포함되기 때문이다.

->  sound 하면서 동시에 complete 한 알고리즘이 좋은 알고리즘이다. 

 

 

 

Connection between Logic and the Real World

 

Syntax of Propositional Logic

- Backus Naur form (BNF) 

 

- ex)

- Atomic sentence

• Propositional symbols (P, Q 처럼 명제 하나를 가르킨다.)
• P, Q, R, W1,3( [1,3] 에 wumpus 가 있다.) , P1,1 ([1,1] 에 pit 가 있다.) -> 경우에 따라 참이거나 거짓일 수 있다.
• True, False -> 항상 참이거나, 거짓.

- Complex sentence

• ㄱW1,3 ( ㄱ 는 negation)
  • literal : propositional symbol 이거나, negation 이 붙은 propositional sybmol

  • 

 

Semantics of Propositional Logic

- sentence 가 주어졌을 때 특정한 모델에 대해서 참인지 거짓인지를 결정하는 규칙을 Semantics 라고 한다.

- model in propositional logic

• 세상을 구성하는 모든 propositional symbol 에 대해 참 거짓 값을 정해놓은 것이다.

- ex) 만약 우리가 다루고 있는 knowledge base 에 propositional symbol 이 다음의 세 개밖에 없다면?

-> symbol 에 대한 할당이 하나의 모델이 될 수 있다. 따라서 8개의 모델이 존재할 수 있다.

- Atomic sentences

- Complex sentences

-> 5개의 논리 연산에 의해 정해진다.