4-3. Logic-syntax, semantics, Truth Table

Propositional logic (명제 논리)

Inference

soundness procedure : 해당 절차를 따라 생성된건 다 맞음

completeness procedure : 해당 절차는 모든 case를 만들어냄

first order logic : sound and complete한 inference procedure가 존재하는 logic, KB에 알려진 사실들을 기반으로 procedure 진행

 

Syntax

• atomic sentence는 1개의 proposition symbol(명제기호)로 구성
  • 명제기호 : True이거나 False인 1개의 명제를 나타냄 ex) P, Q, R ..
• atomic sentence를 괄호와 logical connective(논리접속사)로 연결해서 복합 문장을 만들 수 있음
  •   논리접속사

Semantics (의미론)

각 literal이 어떤 값을 가지는지에 따라 문장 전체의 진리값이 달라짐

즉, literal에 할당하는 진리값 하나하나에 따라 가능한 possible world가 달라짐

각각의 possible world를 model이라는 개념으로 나타냄

semantics는 어떤 model에서 sentence의 진위여부를 결정하기 위한 규칙을 정의

 

atomic sentence에 대한 semantics 

• True는 모든 model에서 참이고, False는 모든 model에서 거짓
• 다른 모든 명제 기호(P, Q …)의 진릿값은 반드시 model 자체에 명시되어 있어야 함

 

compound sentences에 대한 semantics

모형 m 안의 임의의 문장 S1와 S2에 대해 성립

Truth Table 이용

 

Wumpus world 내 Pit에 대한 KB 만들기

Equivalence, validity, satisfiability

Logical equivalence

논리적 동치

두 문장 a와 b가 동일한 model에서 참인 경우 a와 b는 동치 관계에 있음

a가 b를 함축하고, b가 a를 함축하는 경우 a와 b는 동치

 

Validity (유효성)

• 유효한 문장 = 모든 model에서 True인 문장
• Validity를 통해 Entailment의 정의에서 Deduction Theorem을 이끌어낼 수 있음

 

Deduction Theorem (연역 정리)

임의의 문장 a, b에 대해 오직 a=> b가 유효알때만 a ⊨ b

따라서 a ⊨ b가 참인지 알아내려면

1) 모든 모형에서 a => b가 참인지 확인

2) a => b가 True와 동치인지 증명

Satisfiability (만족 가능성)

• 주어진 문장을 만족하는 model (=주어진 문장이 True가 되는 model)이 존재하면 해당 문장은 만족 가능한 문장
• 즉, 모든 모형 중에서 하나 이상의 모형이 주어진 문장을 만족했을 때 그 문장은 만족 가능하다고 말함
• 모든 모형 중에서 주어진 문장을 만족하는 모형이 하나 이상 나올때까지 모든 가능한 모형을 확인

ex) KB ∧ ¬a가 False인 경우 KB ⊨ a