[인공지능] Propositional Logic - 2

Inference: Entailment

Entailment(함의)이라는 개념은 한 논리적 표현이 다른 표현이 참이라는 것을 필연적으로 의미하는지를 설명한다.

기호로는 α⊨β 로 표현되며, 이는 “α entails β” 또는 “β follows from α”라고 읽을 수 있다.

정의:

• α⊨β :
  • α 가 참인 모든 가능한 세계에서 β 도 참이다.
  • 다르게 표현하면, α-worlds는 β-worlds의 부분집합이다. [models(a) ⊆  models(b)]
• 예제 설명: α_2​⊨α_1 이라고 가정.
  
  • 여기서 α_2​는 ¬Q∧R∧S∧W이고, α_1​은 ¬Q이다.
  • α_2​가 참인 모든 세계에서 α_1​도 참이어야 한다.
  • α_2​가 참이면, ¬Q는 반드시 참이므로, α_2​는 α_1​을 함축(entail)한다.

Inference: Proofs

논리적 표현 간의 entailment를 증명하는 과정을 설명

Proof는 α와 β 사이의 entailment를 보여주는 설명(demonstration)이다. 즉, α가 참이면 β도 참이라는 것을 증명하는 논리적인 과정이나 단계의 시퀀스이다.

• Sound Algorithm
  • Definition : Sound algorithm은 그것이 증명하려고 주장하는 모든 것이 실제로 entail되는 알고리즘이다.
• Complete Algorithm
  • Definition : Complete algorithm은 entail되는 모든 것을 증명할 수 있는 알고리즘이다. (sound algorithm과 반대)

Method 1. Model-Checking

• Model-checking 방법은 가능한 모든 세계(possible every world)에 대해 검사하여, α가 참인 경우  β도 참인지 확인한다.
• Process :
  • 가능한 모든 세계를 열거한다.
  • 각 세계에서 α 가 참인지 확인한다.
  • α  가 참인 세계에서 β 도 참인지 확인한다.
•  Applicability : 
  • Model-checking은 명제 논리(propositional logic)에 적합하다. 명제 논리에서는 가능한 세계의 수가 유한하기 때문이다.
  • 일차 논리(first-order logic)에서는 적용하기 어렵다. 일차 논리에서 가능한 세계의 수가 무한할 수 있기 때문이다.

Method 2. Theorem-Proving

• Theorem-proving 방법은 α 에서 β 로 이어지는 증명 단계의 시퀀스를 찾는다. (추론 규칙을 적용)
• Process :
  • α  에서 시작하여 추론 규칙(inference rules)을 적용하여 β 를 도출한다.
  • ex)
  • P 와 (P ⇒ Q) 가 주어진 경우, Modus Ponens 규칙을 사용하여 Q를 추론한다.
•  Applicability : 
  • Theorem-proving은 명제 논리와 일차 논리 모두에 적용할 수 있다. (?? 이건 맞는지 확인해볼것)

Propositional Logic Syntax

명제 논리의 기본 문법(syntax)을 설명한다. 명제 논리는 문장(sentence)의 진리 값을 분석하는 데 사용되는 수학적 표현 방식이다.

• Given : a set of Proposition Symbols: {X_1​,X_2​,…,X_n​}
  • 이들은 명제 기호(symbol)의 집합으로 이루어져있다. 편의상 참과 거짓의 진리 값을 부여한다.

규칙:

1. Atomic Sentences: 각 X_i​는 문장(sentence)이다.
2. Negation (부정): α가 문장이면, ¬α도 문장이다.
3. Conjunction (연결): α와 β가 문장이면, α∧β도 문장이다.
4. Disjunction (분리): α와 β가 문장이면, α∨β도 문장이다.
5. Implication (함축): α와 β가 문장이면, α ⇒ β도 문장이다.
6. Biconditional (양방향 함축): α와 β가 문장이면, α ⇔ β도 문장이다.
7. No Other Sentences: 위의 규칙을 사용하여 생성된 문장 외에는 다른 문장은 없다.

Propositional Logic Semantics

명제 논리의 의미론(Semantics)을 설명한다. 명제 논리의 문장이 어떻게 진리 값을 가지는지 설명한다.

 

규칙:

각 문장의 진리 값은 모델 m에 의해 결정된다고 하자. 모델 m은 각 명제 기호 {X1​,X2​,…,Xn​}에 참 또는 거짓을 할당한다.

1. Symbol (기호): α가 기호라면, 그 진리 값은 모델 m에서 주어진다.
   • 예: 모델에서 X_1​의 진리 값이 참이면, X_1​은 참이다.
2. Negation (부정): ¬α는 m에서 참이라면 α는 m에서 거짓이다. (반대도 마찬가지)
3. Conjunction (연결): α와 β가 모두 m에서 참일 때만,  α∧β는 참이다.
4. Disjunction (분리): α 또는 β (또는 둘 다)가 m에서 참일 때,  α∨β는 참이다.
5. Implication (함축): α가 거짓이거나 β가 참일 때 α ⇒ β는 m에서 참이다.
6. Biconditional (양방향 함축): α ⇒ β와 β ⇒ α가 모두 m에서 참일 때 α ⇔ β는 참이다.

Example

• 모델 m={A=true,B=true,C=false,D=false} 라고 하자.
• 문장 α=(A∧B)∨(C∧¬D) 라고 하자.

진리 값 평가 과정:

• α가 m에서 참이라면 (A∧B)가 m에서 참이거나 (C∧¬D)가 m에서 참이다.
  • (A∧B) 평가:
    • (A∧B)가 m에서 참이라면 A와 B가 모두 m에서 참이어야 한다.
    • 모델 m에서 A와 B는 모두 true이므로 (A∧B)는 참이다.
  • (C∧¬D) 평가 (선택적):
    • (C∧¬D)가 m에서 참이라면 C가 참이고 D가 거짓이어야한다.
    • 모델 m에서 C는 false이므로 (C∧¬D)는 거짓이다.
    • 하지만 이 부분은 α를 평가하는 데 필요하지 않다. 왜냐하면 (A∧B)가 참이기 때문이다.

결론:

• (A∧B)가 m에서 참이므로, 문장 α는 모델 m에서 참이다.