[인공지능] 지식표현과 추론 - 명제 논리

논리

• 말로 표현된 문장들에 대한 타당한 추론을 위해, 기호를 사용하여 문장들을 표현하고 기호의 조작을 통해 문장들의 참 또는 거짓을 판정하는 분야

명제 논리(propositional logic)

• 명제(proposition)
  • 참, 거짓을 분명하게 판정할 수 있는 문장
• 명제를 P, Q등과 같은 기호로 표현
• 명제 기호의 진리값(truth value)을 사용하여 명제들에 의해 표현
• 문장 자체의 내용에 대해서는 무관심, 문장의 진리값에만 관심
• 기본 명제(primitive proposition)
  • 하나의 진술(statement)로 이루어진 최소 단위의 명제
• 복합 명제(compound proposition)
  • 기본 명제들이 결합되어 만들어진 명제
• 논리식(logical expression)
  • 명제를 기호로 표현한 형식
  • 명제기호, 참과 거짓을 나타내는 T와 F, 명제 기호를 연결하는 논리기호인 ¬, ∨, ∧, →, ≡를 사용하여 구성

  • 

    논리 기호

  • 리터럴(literal)
    • 명제 기호 P 또는 명제 기호의 부정 ¬P
  • 절(clause)
    • 리터럴들이 논리합으로만 연결되거나 논리곱으로 연결된 논리식
    • 보통 논리합으로 연결되는 절이 일반적이다.
  • 논리곱 정규형(conjunctive normal form, CNF)
    • 논리합 절들이 논리곱으로 연결되어 있는 논리식 (합의 곱)
  • 논리합 정규형(disjunctive normal form, DNF)
    • 논리곱 절들이 논리합으로 연결되어 있는 논리식 (곱의 합)
  • 정형식(well-formed formula, wff)
    • 논리에서 문법에 맞는 논리식
    • 명제 논리에 대한 정형식
      • 진리값 T, F와 명제 기호들 P, Q, R, ...은 정형식이다
      • p와 q가 정형식이면, 논리 기호를 사용하여 구성되는 논리식 ¬p, p ∨ q, p ∧ q, p → q, p ≡ q도 정형식이다.
      • 위 2개의 규칙에 의해 정의되는 논리식만 정형식이다.
  • 진리표(truth table)
    • 논리기호에 따라 참, 거짓 값을 결합하는 방법을 나타낸 표

    • 

      진리표

  • 논리식의 해석(interpretation)
    • 논리식의 진리값을 결정하는 것
    • 우선 각 명제기호의 진리값 결정 필요
      • 명제 기호에 "명제"를 대응시키고, 해당 명제의 진리값을 결정
      • 대응된 명제를 명제 기호의 외연 또는 의미(denotation)라 함
    • 해석이 주어지면, 진리표를 사용하여 논리식의 진리값 결정
    • n개의 명제기호가 논리식에 사용된다면, 각각 T 또는 F값을 가질 수 있기 때문에, 총2ⁿ개의 해석이 존재
  • 타당한 논리식(valid logical expression)
    • 모든 가능한 해석에 대해서 항상 참인 논리식
    • 항진식(tautology)
  • 항위식(contradiction)
    • 모든 가능한 해석에 대해서 항상 거짓이 되는 논리식
  • 충족가능한(satisfiable) 논리식
    • 참으로 만들 수 있는 해석이 하나라도 있는, 즉 모델이 존재하는 논리식
  • 충족불가능한(unsatisfiable) 논리식
    • 참으로 만들 수 있는 해석이 전혀 없는, 즉 모델이 존재하지 않는 논리식
    • 항위식인 논리식
  • 동치관계(equivalence relation)의 논리식
    • 어떠한 해석에 대해서도 같은 진리 값을 갖는 두 논리식
    • 논리식의 동치관계를 이용하면 임의의 논리식을 CNF와 같은 정형식으로 변환 가능하다
  • 논리적 귀결(logical entailment)
    • Δ는 정형식의 집합, ω는 정형식
    • Δ에 있는 모든 정형식을 참으로 만드는 모델(해석)이 ω를 참으로 만든다
      • Δ는ω를논리적으로귀결한다(logically entail)
      • ω는Δ를논리적으로따른다(logically follow)
      • ω는Δ의논리적결론(logical consequence)이다
    • 표기법 = Δㅑω
    • Δ가 참이면, ω도 참이다
• 추론(inference)
  • 귀납적 추론(inductive inference)
    • 관측된 복수의 사실들을 일반화(generalization)하여 일반적인 패턴 또는 명제를 도출하는 것
  • 연역적 추론(deductive inference)
    • 참인 사실들 또는 명제들로부터 새로운 참인 사실 또는 명제를 도출하는 것
  • 추론 규칙(inference rule)
    • 주어진 논리식들로부터 새로운 논리식을 만들어내는 기계적으로 적용되는 규칙

    • 

    • 논리 융합(resoution)
      • 일반화된 추론규칙
        • 긍정 논법, 부정 논법, 삼단 논법의 규칙을 포함한 추론 규칙
      • 두 개의 논리합절이 같은 기호의 긍정과 부정의 리터럴을 서로 포함하고 있을 때, 해당 리터럴들을 제외한 나머지 리터럴들의 논리합절을 만들어 내는 것
    • 추론 규칙의 정당성과 완정성
      • 추론 규칙의 정당성(sound)
        • 주어진 논리식들이 있을 때, 추론 규칙에 의해 성성된 논리식이 논리적으로 귀결하는 것이면, 그 추론규칙은 정당하다고 한다.
        • 측, 추론 규칙이 만들어 낸 것은 항상 참이다
      • 추론 규칙의 완정성(complete)
        • 주어진 논리식들이 있을 때, 논리적으로 귀결하는 것들을 추론 규칙이 생성할 수 있으면 그 추론규칙은 완전하다고 한다.
  • 정리증명(theorem proving)
    • 공리(axiom)
      • 추론을 할 때, 참인 것으로 주어지는 논리식
    • 정리(theorem)
      • 공리들에 추론 규칙을 적용하여 얻어지는 논리식
    • 정리 증명
      • 공리들을 사용하여 정리가 참인 것을 보이는 것
      • 구성적 증명(constructive proof)
        • 공리들에 추론 규칙들을 적용하여 증명을 만들어 보이는 증명
      • 논리융합 반박(resolution refutation)
        • 증명할 정리를 부정한 다음, 논리융합 방법을 적용하여 모순이 발생하는 것을 보여서, 정리가 참임을 증명하는 방법
        • 우선 주어진 지식이나 사실을 논리식으로 표현한 다음, CNF로 변환한다. 그리고 이 CNF의 각 논리합절을 부모절로 놓는다. 그리고 증명할 논리식, 즉 정리를 부정하여 CNF로 변환한 다음, 부모절에 추가한다. 그러고 나서 이들 부모덜들에 대해서 논리융합을 계속 적용한다. P, ¬P와 같이 긍정과 부정이 모두 참이 되어버리는 모순된 상황이 나오게 되면 멈춘다. 이는 정리가 참임을 반증한다.
  • 명제논리를 이용한 지식 표현
    • 문장으로 표현된 지식으로부터 기본 명제들을 추출
    • 각 명제에 대해 명제기호 부여
    • 기본 명제들의 논리적 연결 관계를 참고하여 대응되는 명제 기호들을 논리기호로 연결하여 논리식 구성
  • 명제 논리로 표현된 지식에 대한 추론
    • 명제 기호가 나타내는 명제의 의미와는 무관
    • 대수적인 기호 연산을 통해서 추론 수행