Yunseok's Dev Blog

배운 것을 적는 블로그입니다.

술어논리와 관계형 모델은 어떤 관계를 가지고 있는가?

술어논리와 관계형 모델

관계형 모델은 집합론을 기초로 한 데이터 모델이기도 하면서 술어논리라는 논리학에 기초한 데이터 모델이기도 하다.

명제란 무엇인가?

명제란 어떤 사물에 관해 설명한 문장이 참인지 거짓인지 물을 수 있는 것을 말한다. 예를 들면 코끼리는 동물이다. 타조는 날지 못한다 등의 문장들이 있다.

명제가 아닌 문장은 참과 거짓이 정해지지 않은 것이다. 예를 들어 꽃이 예쁘다 같은 사람의 감정을 나타내는 문장이 있다.

명제논리란 무엇인가?

명제논리란 어떤 명제의 참과 거짓을 알고 있을 때 다른 명제의 참과 거짓이 무엇인지 알아내는데 특화된 학문을 말한다. 어떤 명제의 참과 거짓을 이용해 다른 명제의 참과 거짓을 증명할 때 중요한 것은 명제들의 참과 거짓뿐이며 명제가 가진 다른 의미는 아무런 영향을 끼치지 못한다.

명제를 P나 Q등의 기호로 표현하고 P나 Q등의 명제의 참과 거짓을 알고 있을 때 더욱 복잡한 명제의 참과 거짓은 어떨까?가 명제논리라는 학문의 주제다.

(논리)연결자

명제에서 새로운 참과 거짓을 도출하기 위한 기호를 ‘연결자’라고 한다.

  • ¬ NOT
  • ∧ AND
  • ∨ OR
  • ⊃ 포함
  • ≡ EQ
  • ⊻ XOR
  • NAND
  • NOR

항진식이란 무엇인가?

매개변수가 되는 명제의 값에 상관없이 항상 참이 되는 논리식을 항진식이라고 부른다. 예를 들면 (P ⊃ Q) ⊃(¬ Q ⊃ ¬ P)는 P와 Q의 값에 상관없이 항상 참이다.

항진식이 왜 필요할까?

항진식은 어떠한 상황에서도 항상 참이기 때문에 절대적인 법칙을 나타낸다. 항상 참이 된다는 것을 알고 있으므로 어떤 설명이 바른지 아닌지 증명하는데 사용되거나 참이 되는 논리식에서 다른 참이 되는 논리식을 도출할 때 사용한다.

다음은 항상 참이 된다.

  • 동일법칙 P ⊃ P
  • 배중법칙 P ∨ ¬P
  • 이중부정법칙 ¬ ¬ P
  • 모순법칙 ¬(P ∧ ¬ P)
  • Principle of explosion (P ∧ ¬P) ⊃ Q
    • 가정이 되는 명제에 모순이 있다면 어떤 결론도 도출할 수 없다.
  • 대우법칙 (P ⊃ Q) ⊃ (¬Q ⊃ ¬P)
  • 추이법칙 ((P ⊃ Q) ∧ (Q ⊃ R)) ⊃ (P ⊃ R)
  • 분배법칙 P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) 또는 P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
  • 드모르간 ¬(P ∨ Q) ≡ ¬P ∧ ¬Q 또는 ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
  • 전건긍정식 ((P ⊃ Q) ∧ P) ⊃ Q
  • 후건부정식 ((P ⊃ Q) ∧ ¬Q) ⊃ ¬P
  • 선언적삼단법 ((P ∨ Q) ∧ ¬P) ⊃ Q

공리란 무엇인가?

어떤 서술이 올바른지 증명하려면 전제가 되는 명제가 참인 것을 증명하여야 한다. 하지만 만약 전제도 증명을 해야 하려면 다른 전제들이 필요할 것이고 그러다 보면 영원히 증명만 하다가 끝날 것이다. 그래서 증명할 필요가 없이 자명한 진리이자 다른 명제들을 증명하는 데 전제가 되는 원리들이 존재하는 데 이를 공리라고 한다.

공리로 정의된 명제끼리 모순이 없어야 하고 공리는 다뤄지는 주제가 전체를 포괄할 수 있는 것을 가정하여 정의해야 한다. 이처럼 고민하고 정한 공리의 집합을 공리계라고 한다.

만약 전제되는 명제에 모순이 있다면 어떤 명제도 참이 된다.

명제논리의 한계는 무엇인가?

  • 세상에는 명제논리만으로 해석할 수 없는 논리학적인 문제가 많다.
  • 사실을 단순한 명제를 이용해 표현할 수 없을 때는 대응할 수 없다.

이와 같은 문제를 해결하기 위해 양화논리가 있다.

양화논리란 무엇인가?

집단을 대상으로 참과 거짓을 묻는 것을 말한다.

술어논리에서 다루는 양화논리는 두 종류가 있다.

  • 어떤 집단의 요소 전체가 어떠한 성질을 충족하는가? -> 범용정량 ∀
  • 어떤 집단의 요소는 어떠한 성질을 충족하는 것이 존재하는가? -> 존재정량 ∃

정량자와 술어논리

이 마을의 주민은 모두 정직하다라는 문장을 보면 어떤 집단의 요소 전체가 어떤 성질을 충족한다는 것은 범용정량자 ∀ 를 사용해서 표현한다. 이때 집단의 각 요소를 표현하기 위한 변수와 집단의 요소가 충족하는 모든 성질을 표현하기 위해서 함수를 사용한다. 예를 들어 x는 정직하다라는 것을 표현하는 함수를 F(x)라고 하면 이 마을의 주민은 모두 정직하다라는 문장은 다음과 같이 식으로 표현할 수 있다.

∀ x F(x)

모든 x에 대해서 F(x)라는 성질을 만족한다고 해석할 수 있다.

이 마을에는 정직하지 않은 사람이 있다라는 문장은 다음과 같이 표현할 수 있다.

∃ x ¬F(x)

F(x)라는 성질을 만족하지 않는 x가 존재한다고 해석할 수 있다.

이렇게 변수와 정량자 그리고 함수를 사용해서 집단에 대한 성질을 기술한 문장을 논리식으로 표현할 수 있다. 이러한 표현을 사용한 명제논리를 확장한 체계를 술어논리라고 한다.

속박변수

여기서 정량자 ∀나 ∃와 함께 사용되는 x라는 변수를 속박변수라고 한다. 왜냐하면 일반적인 변수처럼 보이지만 그 범위가 대상의 논리식 내로 한정되기 때문이다.

술어논리에서도 논리식끼리 복잡한 논리식을 표현할 수 있다. 예를 들면 ∃ x F(x) ∧ ∀ x G(x)와 같은 형태다.x라는 공통된 기호를 사용했지만 각 x의미가 다르다. 볌수의 범위가 정량자의 영향 범위에 속하기 때문이다. 그래서 속박변수라고 부른다. 프로그래밍의 변수의 스코프와 비슷하다고 생각할 수 있다.

자유변수

정량자를 사용하지 않는 변수를 자유변수라고 한다. 자유변수는 임의의 값을 얻을 때 정량자와 같은 범위에 속박되지 않는다. 예를 들어 F(x) ⊃ G(x)는 첫 번째 x와 두 번째 x가 같은 x를 가리킨다.

술어논리와 집합론

술어와 집합은 등가교환 가능하다.

술어는 술어 F(x)가 참이 되는 모든 x들을 포함한 집합으로 볼 수 있다. 즉 F(x)라는 술어는 x ∈ SF라는 집합과 요소의 포함관계로 표현할 수 있다. 따라서 술어와 집합은 등가교환할 수 있다.

집합의 포함관계

⊃ 는 왼쪽 논리식의 조건이 참이면 오른쪽의 논리식도 참이 된다는 의미다. 왼쪽의 논리식이 거짓이라면 오른쪽의 논리식은 참이든 거짓이든 상관없다.

도메인

술어논리는 논의의 대상이 되는 집합을 가정하는 것이 일반적이며, 이처럼 논의의 대상이 되는 집합을 도메인이라고 부른다. 이 개념은 관계형 모델에서도 통용된다.

2차 술어논리

1차 술어논리는 술어의 매개변수가 되는 것은 한 개인이나 구체적인 것이었다.

2차 술어 논리는 술어의 특징을 표현하는 술어를 다루는 게 특징이다. 예를 들어 “x는 참인 매개변수가 한 개 이상 존재하지만, 항진이 아닌 술어다”와 같은 형태다. 2차 술어논리는 집합을 요소로 하는 집합을 다룬다.

술어 자신을 술어의 대상으로 하면 자신도 그 술어의 대상이 될 수 있다. “x는 참인 매개변수가 한 개 이상 존재하지만, 항진이 아닌 술어다”라는 술어는 자신을 평가하면 참이 될 것이다. 이처럼 자기 자신을 언급할 수 있는 것이 2차 술어논리의 특징이다.

관계형 모델은 1차 술어논리를 바탕으로 디자인된 데이터 모델이다.

릴레이션과 술어논리

릴레이션은 집합이다. 집합은 1차 술어논리와 1대1로 대응된다. 따라서 릴레이션에는 대응하는 술어가 존재한다.

릴레이션은 참인 명제의 집합이라고 할 수 있다. 이 릴레이션이 참인 명제의 집합이라는 것은 릴레이션의 연산은 논리연산 외에는 없다는 말이다. 즉 DB에 대한 질의를 수행하는 것은 어떤 데이터가 필요한지를 술어로 표현하고 그 술어에 대한 질의를 수행하는 것은 어떤 데이터가 필요한지를 술어로 표현하고 그 술어에 대한 논리연산을 수행한 결과, 쿼리에 해당하는 술어가 참이 되는 집합을 새롭게 취득하는 동작이다. 쿼리를 작성하는 행위는 술어를 표현하는 것 외에는 없다.

페쇄 세계 가정

어떤 사실의 집합에서 다른 사실의 집합을 릴레이션이라는 구조를 통해서 얻는 것이 관계형 모델이다. 관계형 모델은 술어에 대입해 참이 되는 것은 릴레이션에 포함되는 튜플뿐이며 참이 되는 명제는 모두 빠짐없이 릴레이션에 포함되는 것으로 가정하고 있다. 이 가정이 폐쇄 세계 가정(Closed World Assumption)이라고 한다. 즉 알지 못하는 사실은 존재하지 않고 ‘사실’은 모두 판명돼 있다고 생각하고 이를 전제로 데이터 모델을 설계하자는 생각이다.

모순된 DB는 쓸모없다.

술어논리에서 모순이 포함돼 있으면 Principle of explosion 정리에 따라 어떠한 결과도 도출할 수 있게 된다. 즉 모순된 데이터를 가진 릴레이션에서 도출된 질의의 결과는 전혀 믿을 수 없게 된다.

관계형 모델의 한계

술어논리(집합론)에 따른 데이터 모델이라서 그 틀에서 벗어난 데이터나 연산을 표현할 수 없다. 즉 1차 술어논리의 표현력보다 복잡하거나 유연한 데이터 또는 연산은 관계형 모델에서는 표현할 수 없다. 대표적인 데이터 구조인 그래프는 관계형 모델에서 표현하기 어렵다.

릴레이션의 연산과 술어 논리

Restrict

제한은 대상 릴레이션에 관해 새로운 술어를 적용하는 작업이다.

P(t) ∧ Q(t)

Product

2개의 전제가 되는 사실로부터 어떻게 새로운 사실을 도출할지가 곱집합이라는 작업이다. 모든 튜플의 조합으로 얻을 수 있다.

P(t1) ∧ Q(t2)

Join

곱집합은 결합의 특별한 경우다.

P(t1) ∧ Q(t2)

차이점은 두 개의 릴레이션에 ‘공통 속성’이 존재하는지 아닌지다.

곱집합은 두 개의 릴레이션에 공통된 속성이 존재하지 않는다. 결합은 일반적으로 두 개의 릴레이션 사시에 공통된 특성이 존재한다.

결합한 후의 릴레이션에 포함된 튜플은 공통의 속성값이 같은 것뿐이다. 왜 그런가 하면 공통의 속성은 같은 의미가 있으며 같은 값이 아니면 모순되기 때문이다. 그래서 공통된 특성 값을 갖는 튜플끼리만 결합할 수 있다.

Intersect

교집합도 결합의 특수한 경우다. 교집합은 반대로 모든 속성이 공통인 릴레이션 사이의 결합이라고 할 수 있다.

P(t) ∧ Q(t)

Union

모든 특성이 공통인 릴레이션 사시의 연산이다.

P(t1) ∨ Q(t2)

Difference

차집합은 한쪽의 릴레이션에는 포함돼 있지만 다른 쪽의 릴레이션에는 포함되지 않은 튜플의 집합을 반환하는 연산이다. 차집합도 합집합과 마찬가지로 연산하는 릴레이션의 특성은 모두 공통이어야 한다.

P(t) ∧ ¬Q(t)

Projection

프로젝션은 여러 개의 특성이 있는 릴레이션에서 특정 속성만 남기는 작업이다.

Rename

기존의 속성명을 변경하는 것뿐이라면 논리식의 구조에는 변화가 없다.

Extend

확장으로 추가된 속성과 원래의 튜플 사이에는 논리적인 관계가 없다. 논리 연산이 아닌 어떤 법칙으로 새로운 사실을 도출하는 것이 확장이 가진 의미다.

관계형 모델의 쿼리

쿼리를 작성할 때의 목표는 어떤 집합에서 새로운 집합을 도출하기 위한 법칙을 기술하는 것이다. 이 법칙이 술어다. 어떤 데이터가 필요한가?라는 것을 출발점으로 논리적인 결과로부터 쿼리를 작성할 수 있는 것이 관계형 모델의 최대 강점이다. 술어논리와 집합론은 1대1로 대응하므로 술어를 제대로 작성하면 원하는 집합을 얻을 수 있다.

릴레이션에 관한 어떤 연산을 실행한 결과는 릴레이션이 된다. 이것이 클로저라는 성질이다. 이 장에서 소개하는 술어도 클로저다. 술어를 조합해 조금 더 복잡한 술어를 표현하는 것 그것이 관계형 모델에서의 쿼리의 실체라고 할 수 있다.

모두 이해했다면 다음 질문에 답해보자.

  • 명제란 무엇인가?
  • 명제논리란 무엇인가?
  • 논리 연결자의 종류에는 무엇이 있는가?
  • 다음 진리표에 진리값을 채워라
P Q ¬ P P ∧ Q P ∨ Q P ⊃ Q P ≡ Q P ⊻ Q
T T            
T F            
F T            
F F            
  • 항등식이란 무엇인가?
  • 공리란 무엇인가?
  • 공리계란 무엇인가?
  • 명제논리의 한계란 무엇인가?
  • 양화논리란 무엇인가?

Source