wowo0709

wowo0709

큰 사람이 되려면 큰 물에서 놀아라

[Knowledge Expression] 논리 1 - 명제 논리

3 minute read


논리

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


명제 논리란?

명제

참, 거짓을 분명하게 판정할 수 있는 문장

명제 O: 아리스토텔레스는 플라톤의 제자이다. 1 + 1 = 3.

명제 X: 일어나서 아침 먹자.

  • 명제 기호의 진리값을 사용하여 명제들에 의해 표현되는 문장들의 진리값 결정

  • 문장 자체의 내용에 대해서는 무관심, 문장의 진리값에만 관심


기본 명제

하나의 진술(statement)로 이루어진 최소 단위의 명제

예 )

  • 알렉산더는 아시아를 넘본다. ➡ P
  • 징기스칸은 유럽을 넘본다. ➡ Q

복합 명제

기본 명제들이 결합되어 만들어진 명제

예 )

  • 알렉산더는 아시아를 넘보고, 징기스칸을 유럽을 넘본다. ➡ P ∧ Q


명제 논리의 구문

논리식

명제를 기호로 표현한 형식

  • 논리 기호

image-20210926125004541

리터럴

명제 기호 P 또는 명제 기호의 부정 ㄱP

절

리터럴들이 논리합으로만 연결되거나 (논리곱으로 연결된 논리식)

image-20210926125214769

논리곱 정규형(cojunctive normal form, CNF)

논리합 절들이 논리곱으로 연결되어 있는 논리식

image-20210926125339432

논리합 정규형(disjunctive normal form, DNF)

논리곱 절들이 논리합으로 연결되어 있는 논리식

image-20210926125354684

정형식

논리에서 문법에 맞는 논리식

📌 명제 논리에 대한 정형식

  1. 진리값 T, F와 명제 기호들 P, Q, R… 은 정형식이다.
  2. p와 q가 정형식이면, 논리 기호를 사용하여 구성되는 논리식 ㄱp, p or p ➡ p, p and q 도 정형식이다.
  3. 1과 2에 의해 정의되는 논리식만 정형식이다.



명제 논리의 의미

진리표

논리 기호에 따라 참, 거짓 값을 결합하는 방법을 나타낸 표

image-20210926125752439

논리식의 해석

논리식의 해석이란 논리식의 진리값을 결정하는 것입니다.

이를 위해서는 먼저 논리식의 명제 기호에 참 또는 거짓을 할당해야 합니다.

image-20210926130249566

해석이 주어지면, 진리표를 사용하여 논리식의 진리값을 결정할 수 있습니다.

image-20210926130337858

따라서, n개의 명제 기호가 논리식에 사용된다면, 각각 T 또는 F 값을 가질 수 있기 때문에, 총 2n개의 해석이 존재합니다.


타당한 논리식 (항진식, Valid logical expression)

모든 가능한 해석에 대해서 항상 참인 논리식

image-20210926131005510

항위식 (Contradiction)

모든 가능한 해석에 대해서 항상 거짓이 되는 논리식

image-20210926131038916

충족 가능한 논리식

참으로 만들 수 있는 해석이 하나라도 있는, 즉 모델이 존재하는 논리식

image-20210926131250739

충족 불가능한 논리식

참으로 만들 수 있는 해석이 전혀 없는, 즉 모델이 존재하지 않는 논리식 (항위식인 논리식)


동치 관계의 논리식

어떠한 해석에 대해서도 같은 진리값을 갖는 두 논리식

image-20210926131511888

동치관계를 이용한 논리식의 변환

논리식의 동치관계를 이용하면 임의의 논리식을 논리곱 정규형(CNF)과 같은 정형식으로 변환할 수 있습니다.

image-20210926131718118


논리적 귀결

  • Δ : 정형식(wff)의 집합.
  • ω: 정형식.

Δ 에 있는 모든 정형식을 참(T)으로 만드는 모델(해석)이, ω를 참(T) 으로 만든다.

➡ Δ 는 ω를 논리적으로 귀결한다. (logically entail)

➡ ω 는 Δ 를 논리적으로 따른다. (logically follow)

➡ ω 는 Δ 의 논리적 결론이다. (logical consequence)


표기법: Δ |= ω

➡ Δ 가 참이면, ω 도 참이다.

image-20210926132852167

image-20210926132901981



명제 논리의 추론

추론의 분류


귀납적 추론

  • 관측된 복수의 사실들을 일반화하여 일반적인 패턴 또는 명제를 도출하는 것
  • 기계학습 등에서 사용

연역적 추론

  • 참인 사실들 또는 명제들로부터 새로운 참인 사실 또는 명제를 도출하는 것
  • 논리에서 사용


추론 규칙

주어진 논리식들로부터 새로운 논리식을 만들어내는 기계적으로 적용되는 규칙

image-20210929223829243

긍정 논법

image-20210929223909142

부정 논법

image-20210929223930891

삼단 논법

image-20210929223947612

논리 융합

  • 일반화된 추론규칙

    • 긍정 논법, 부정 논법, 삼단 논법의 규칙을 포함한 추론 규칙

    image-20210929224958277

  • 두 개의 논리합절이 같은 기호의 긍정과 부정의 리터럴을 서로 포함하고 있을 때, 해당 리터럴들을 제외한 나머지 리터럴들의 논리합절을 만들어 내는 것

image-20210929225142684


추론 규칙의 정당성과 완전성

추론 규칙의 정당성

  • 주어진 논리식들이 있을 때, 추론 규칙에 의해 생성된 논리식이 논리적으로 귀결하는 논리식이면, 그 추론 규칙은 정당하다고 한다.
  • 즉, 추론 규칙이 만들어 낸 것은 항상 참이다.

image-20210929225326245

추론 규칙의 완전성

  • 주어진 논리식들이 있을 때, 논리적으로 귀결하는 논리식들을 추론 규칙이 생성할 수 있으면, 그 추론 규칙은 완전하다고 한다.

image-20210929225518108



정리 증명

  • 공리: 추론을 할 때, 참인 것으로 주어지는 논리식
  • 정리: 공리들에 추론 규칙을 적용하여 얻어지는 논리식
  • 정리 증명: 공리들을 사용하여 정리가 참인 것을 보이는 것
    • 구성적 증명: 공리들에 추론 규칙들을 적용하여 증명을 만드는 증명
    • 논리융합 반박: 증명할 정리를 부정한 다음, 논리 융합 방법을 적용하여 모순이 발생하는 것을 보여서, 정리가 참임을 증명하는 방법

image-20210929225812173



정리

  • 명제 논리를 이용한 지식 표현
    • 문장으로 표현된 지식으로부터 기본 명제들을 추출
    • 각 명제에 대해 명제 기호 부여
    • 기본 명제들의 논리적 연결 관계를 참고하여 대응되는 명제 기호들을 논리 기호로 연결하여 논리식 구성
  • 명제 논리로 표현된 지식에 대한 추론
    • 명제 기호가 나타내는 명제의 의미와는 무관
    • 대수적인 기호 연산을 통해서 추론 수행


Leave a comment

You may also enjoy