술어논리와 관계형 모델
명제
명제란 어떤 사물이나 개념에 대한 설명인지 참인지 거짓인지 명확히 물을 수 있는 것이다.
명제논리
어떤 명제의 참과 거짓을 알고 이를 이용해 다른 명제의 참과 거짓을 알아내는 데 특화된 학문을 명제논리라고 한다. 명제 이외의 다른 것은 의미를 가지지 않으므로 명제는 보통 기호로 표현한다. P와 Q등의 참과 거짓을 알 때 복잡한 명제의 참과 거짓은 어떻게 되는지가 명제논리의 주제이다.
(논리)연결자
두가지 혹은 한개의 명제에서 참과 거짓을 도출하기 위한 기호를 연결자라고 한다. 일반적으로 논리 연산이라고 불린다.
| ￢ | ∧ | ∨ | ⊃ | ≡ | | | ↓ | ⊻ |
|---|---|---|---|---|---|---|---|
| 부정 | 연언, 논리곱 | 선언, 논리합 | 포함 | 동치 | 부정논리곱 | 부정논리합 | 배타적논리합 |
| NOT | AND | OR | IMP | EQ | NAND | NOR | XOR |
| 명제가 그것이 아님을 나타낸다. 참이면 거짓, 거짓이면 참이 된다. | 두 명제의 논리곱이 모두 참일 때만 참이된다. | 두 명제의 논리합이 모두 거짓일 때만 거짓이 된다. 어느 하나라도 참이면 참이다. | 조건명제이며 P가 참이고 Q가 거짓일 때만 P→Q는 거짓이 되고 그외 모두 참이다. | 명제가 서로 같을때만 참이된다. | Not+AND의 연산이다. 두 명제 모두 참일 때 거짓이 된다. 나머지는 참이 된다. | Not+OR의 연산이다. 두 명제 모두 거짓일 때 참이된다. | 두 명제중 어느 하나만 참일때 결과값이 참이 다. |
진리함수의 진리값
논리 기호는 각기의 논리값을 가지며 식 전체의 진리값을 고유하게 결정하는 역할을 한다. 이러한 성질을 가지는 것을 진리함수라고 한다.
| P | Q | ￢P | P∧Q | P∨Q | P⊃Q | P≡Q | P|Q | P↓Q | P⊻Q |
|---|---|---|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T | F | F | F |
| T | F | F | F | T | F | F | T | F | T |
| F | T | T | F | T | T | F | T | F | T |
| F | F | T | F | F | T | T | T | T | F |
동어반복
조합된 식에 따라서 주어진 명제가 무엇이든 식 전체의 참과 거짓 값이 항상 참이 되는 경우가 있다. 이처럼 매개변수가 되는 명제의 값에 상관없이 식 전체의 명제 값이 항상 참이 되는 식을 동어반복 또는 항진식이라고 한다. 반대로 항상 거짓이 되는 논리식은 모순식이라고 한다.
| P | Q | ￢P | ￢Q | ￢Q⊃￢P | P⊃Q | (P⊃Q)⊃(￢Q⊃￢P) |
|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
명제논리에서 동어반복은 언제 어떠한 상황에서도 성립하는 절대적인 법칙이다. 다음은 명제논리에서 자주 사용되는 동어반복이다.
- 동일법칙: P⊃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
공리
정리의 전제가 되는 정리를 찾아 올라가 전제가 되는 명제로 어떤 명제를 참인지 증명한다. 아무런 전제 없이도 올바르다고 인정하자는 합의하에 정해진 다른 정리의 출발점이 공리라고 한다. 모든 정리는 공리가 출발점이다. 공리는 여러 개의 명제를 조합하여 성립한다. 공리로 정의된 명제끼리는 모순이 없어야 하고 주제가 전체를 포괄할 수 있는 것을 가정하여 정의해야 한다. 이처럼 고민하고 정한 공리의 집합을 공리계라고 한다.
귀류법
모순이 생기는 명제는 틀리다라는 도출규칙을 귀류법이라고 한다.
예를들어 P⊃(Q∧￢Q)에서 P를 가정하면 Q∧￢Q가 도출되는데, Q이면서 ￢Q인 명제는 항상 거짓이 된다. 이른바 모순식이다.명제 P는 참이라는 가정이 없으므로 P는 거짓이다. 즉 ￢P가 참이 된다.
명제논리의 한계
어떤 사실을 참과 거짓 값을 명제로 표현할 수 있다면 문제 없지만 그렇지 않은 경우, 즉 사실을 단순한 명제를 이용해 표현할 수 없는 때는 대응할 수 없다.
“이 마을의 모든 주민이 정직하다고 할 수 없다”라는 문장은 논리식으로 표현하기 어려울수 있다.
양화논리
양화논리란 집단을 대상으로 참과 거짓을 묻는 것이다.
- 어떤 집단의 요소 전체가 어떠한 성질을 충족하는가? - 범용정량 ∀
- 어떤 집단의 요소는 어떠한 성질을 충족하는 것이 존재하는가? - 존재정량 ∃
정량자와 술어논리
어떤 집단의 요소 전체가 어떤 성질을 충족한다는 것은 범용정량자를 사용해서 표현한다. x라는 것이 명제에 만족한다는 것의 표현을 함수로 F(x)라고 한다면 모든 x에 대한 명제는 ∀×F(x)로 표현한다.
술어논리
범용정량자를 사용한 식은 “모든 x에 대해서 F(x)라는 성질을 만족한다”는 의미의 논리식이다. 이처럼 변수와 정량자 그리고 함수를 사용해 집단에 대한 성질을 기술한 문장을 논리식으로 표현할 수 있다. 이렇게 명제논리를 확장한 체계를 술어논리라고 한다.
“F(x)를 만족하지 않는 x가 있다”라는 문장은 ∃×￢F(x) 로 표현할 수 있다. 여기서 ￢F(x)는 x는 만족하지 않는다라는 의미가 된다.
속박변수
정량자와 함께 사용되는 변수는 속박변수라고 한다. 속박변수는 일반 변수로 보이지만 그 범위가 대상의 논리식 내로 한정된다. 가령 ∃×F(x) ∧ ∀×G(x) 와 같은 술어논리에서는 ∧ 앞뒤에 있는 x의 의미가 다르다. 프로그래밍으로 보았을때 변수의 스코프가 다르다라고 생각하면 될것이다.
자유변수
정량자를 사용하지 않는 변수를 자유변수라고 한다. 자유변수는 임의의 값을 얻을 때 정량자와 같은 범위에 속박되지 않는다. F(x)⊃G(x)는 노리식에서 첫 번째 x도 두 번째x도 같은 x를 가리킨다. 그렇게 F(x)가 갖는 의미는 참도 될수 있고 거짓도 될수있는 명제함수라고 하며, 명제함수는 술어라고도 한다. 술어논리는 술어를 이용한 논리체계이다.
술어논리와 집합론
술어와 집합의 등가교환
“코끼리는 초식동물이다”를 논리식으로 표현하면 다음과 같다.
∀×(F(x)×G(x))
“x가 코끼리다”는 F(x), “x가 초식동물이다”는 G(x)이다. F(x)는 x가 코끼리이면 참 그렇지 않으면 거짓을 반환한다. F(x)는 모든 코끼리를 포함한 집합이라고 말할 수 있다. F(x)가 참이되는 집합을 SF라고 할때 x∈SF라고 할 수 있다. 마찬가지로 초식동물이 참인 경우 x∈SG라고 할 수 있고 이를 이용해 다시 집합으로 표현하면
∀×(x∈SF × x∈SG)
로 표현할 수 있다. SF, SG를 사용해도 논리식이 의미하는 참과 거짓은 같다. 술어와 집합은 등가교환을 할 수 있다.
집합의 포함관계
⊃는 왼쪽 논리식의 조건이 참이면 오른쪽의 논리식도 참이된다는 의미이다. 왼쪽 논리식이 거짓이라면 오른쪽의 식은 참이든 거짓이든 상관없다. 이런 경우 x∈SF가 거짓이면 x∈SG가 참이될 수도 있다. 이를 집합의 포함관계로 다시표현하면 이렇게 된다.
SF ⊆ SG
SF가 SG에 포함된다는 의미이다. 이것은 “코끼리라는 집합은 초식동물이라는 집합에 포함된다”라는 의미가 된다.
집합과 요소의 포함 관계 차이
∈는 어떠한 요소가 어떠한 집합에 포함된다라는 요소-집합 관계를 의미한다.
⊆는 어떠한 집합의 모든 요소가 어떠한 집합에 포함된다라는 집합-집합 관계를 의미한다. 이런 경우 포함하는 집합은 상위 집합(슈퍼셋)이라고 하고 포함되는 집합은 부분집합(서브셋)이라고 한다.
술어논리와 공리계
∀×{x∈SF}에서 SF의 원소는 {a1, a2, a3, a4 … , an}라고 하면은 앞의 명제는 다음과 같이 표현할 수 있다.
F(a1)∧F(a2)∧F(a3)… ∧F(an)
마찬가지로 ∃×G(x)의 경우는
F(a1)∨F(a2)∨F(a3)… ∨F(an)
으로 표현할 수 있다. 이는 정량자 기호가 ∨와 ∧와 흡사하다고 볼 수 있다.
도메인
F(x)에서 x는 특정 대상을 지칭하고 있다. 예를들어 “x는 모두 이 마을 사람이다”라고 했을 때 x라는 것이 인간만 들어가야 하는지, 개와 고양이도 들어갈 수 있지 않을까라는 의문이 들 수 있다. 일반적으로 논의의 대상이 되는 집합을 가정하는 것이 일반적이며, 이처럼 논의의 대상이 되는 집합을 도메인, 영역이라고 부른다.
1차 술어논리
여기까지 이야기한 것은 정확히 1차 술어논리라고 한다. 일반적으로 부연 설명이 없다면 1차 술어논리를 말한다고 생각하면 된다.
2차 술어논리
1차 술어논리는 술어의 매개변수가 되는 것은 한 개인이나 구체적인 것이다. 2차 술어논리는 술어의 특징을 표현하는 술어를 다루는게 특징이다. 예를 들어 “x는 참인 매개변수가 한 개 이상 존재하지만, 항진이 아닌 술어다”와 같은 문장이다. 술어와 집합은 1대1로 대응하므로 2차 술어논리는 집합을 요소로 하는 집합을 다루나독 할 수 있다.술어 자신을 술어의 대상으로 하면 자신도 그 술어의 대상이 될 수 있다. 관계형 데이터 베이스는 1차 술어논리로 디자인되어 있다.
릴레이션
술어논리와 집합이 1대 1로 대응되는 것에 관해 설명했다. 이 것의 결론은 릴레이션에는 대응하는 수렁가 있다는 것이다. 어떠한 릴레이션에 튜플의 대한 참, 거짓여 부를 본다면 F(t)가 될것이다. 여기서 t는 튜플을 의미한다. 이 릴레이션에 포함된 튜플은 모두 F(t)에 대입하면 참으로 평가된다. 즉 이 릴레이션의 의미는 ∀tF(t)의 논리식과 등가이다.
릴레이션과 논리연산
릴레이션의 개별 튜플은 F(t)에 대입하면 참이되므로, 릴레이션은 참인 명제의 집합이라고 볼 수 있다. 참인 명제를 다르게 말하면 사실이라고 할 수 있고, 릴레이션은 사실의 집합이다. 이 말은 릴레이션의 연산은 논리연산 외에는 없다는 말이다. DB에 대한 질의를 수행하는 것은 어떤 데이터가 필요한지를 술어로 표현하고 그 술어에 대한 논리연산을 수행한 결과, 쿼리에 해당하는 술어가 참이 되는 집합을 새롭게 취득하는 동작이다.
폐쇄 가정
릴레이션에 포함되지 않는 사실에 어떻게 표현할지에 대한 문제가 있다. 관계형 모델은 술어에 대입해 참이 되는 것은 릴레이션에 포함되는 튜플뿐이고 참이 되는 명제는 모두 빠짐없이 릴레이션에 포함하는 것으로 가정하고 있다. 이 가정은 폐쇄 세계 가정이라고 한다. 즉 알지 못하는 사실은 존재하지 않고 “사실”은 모두 판명돼 있다고 생각하고 이를 전제로 데이터 모델을 설계하자는 생각이다.
모순된 DB는 쓸모가 없다
술어논리에 있어 가장 복잡한 것은 모순이다. 릴레이션에 모순된 데이터가 있다면, 그 릴레이션에서 도출된 질의의 결과는 믿을 수가 없게 된다.
관계형 모델의 한계
앞서 말했듯이 관계형 모델은 1차 술어논리로 디자인 되어 있기 때문에, 그 틀에서 벗어난 데이터나 연산을 표현할 수가 없다. 대표적으로 그래프가 있다.