집합과 명제, 그리고 공진

경고

전 수학 전공자가 아니라 아래 내용에는 수학 전공자나 전문가가 보기에 잘못된 내용이나 표현이 있을 수 있습니다. 해당 부분은 댓글 통해 지적해주시면 반영해 수정하도록 하겠습니다.

지인분의 부탁으로 영재키움 프로젝트라는 행사에서 어린 학생들(초4-고1, 대부분이 초등학생)에게 IT 개발을 소개하는 기회가 있었습니다. 집필이나 강연 경험이 있는 분들은 동감하시겠지만, 대상이 초보자일수록 알고 있는 지식을 전달하기는 심히 어려워집니다. 제 지식 전달 능력이 부족하다는 걸 애초에 잘 알고 있었기에 가급적 비전공자나 대학생 미만을 대상으로 하는 강연은 피해왔지만, 이 기회를 통해 다행히도 무려 초등학생을 대상으로 하는 강연을 무사히(?) 마쳤습니다 - ~~그런데 영재라는 사실은 함정!~~

청중이 수학적 지식이 거의 없다고 가정한 관계로(일부 학생은 비유클리드 기하를 얘기할 만큼의 실력을 보이기도... ㄷㄷㄷ), 강연 중 가급적 모든 대상이 이해할 수 있는 예를 찾기 위해 상당히 고민해야 했습니다. 그 중 한 가지 예가 순환소수(recurring decimal)에 대한 예였고,

$$0.9999... = 1$$

다른 하나가 소박한 집합론(naive set theory)에서 집합의 집합(set of sets)을 사용한 합집합(union), 교집합(intersection)의 일반적인 정의(arbitrary union and intersection)에 대한 내용이었습니다. 순환소수 개념은 사실 소수(fraction)를 알면 따라올 수 있는 부분이었으므로 큰 문제가 없었지만, 집합의 집합에 대한 개념은 끌고 오는 순간 그것만으로도 전체 시간의 절반을 잡아먹을 것으로 예상되어 어쩔 수 없이 아이들이 이해하기 쉬운 거짓말을 해야 했습니다.

제가 거짓말한 부분은 아래 내용입니다. (이 글 적느라고 블로그 엔진에 MathJax까지 적용했습니다.)

$$\emptyset \cap \emptyset = U$$

바로 공집합($\emptyset$, empty set, null set)의 교집합에 대한 이야기입니다. 물론, 수학적인 진실은 상식과 부합하는

$$\emptyset \cap \emptyset = \emptyset$$

입니다. 그리고, 제가 실제 적고 싶었던 수식은 저 위의 수식이 아니라

$$\bigcap \emptyset = \{ x | true \} = U$$

였습니다 - 믿기 어려우실 수도 있지만 이번엔 틀린 내용이 아닙니다 (이 시점에서 제가 소박한 집합론을 논하고 있음을 잊지 말아주셨으면 합니다). $\bigcap$ 기호가 익숙하지 않은 분들은 걱정하실 필요 없습니다. 아래에서 천천히 살펴볼 예정입니다.

제 설명의 의도는, 논리라는 것이 대장금이 홍시맛을 느끼는 것처럼 느낌이나 직관을 통해 타고 나는 것이 아니라 훈련에 의해 개발될 수 있는 부분이고, 스스로가 논리적인 사람이 아니라 생각해도 연습하면 충분히 논리적인 사람이 될 수 있다는 것이었습니다. 그리고 그런 논리가 바로 코딩이라는 활동을 지탱하는 밑받침이라는 사실이었습니다 - 지금보니 쓸데없이 거창했네요.

저 상식적이지 않은 논리적 결과를 이해하기 위해서는 공진(vacuous truth)을 이해해야 합니다. 그런데 이 공진이 사실 "느낌적인 느낌"으로 잘 와닿지 않기 때문에 처음 접했을 때 스스로를 설득하는데 상당한 시간이 걸리기도 합니다. 예를 들어 보겠습니다.

코끼리가 빨간색이면 다리가 10개이다.
코끼리가 빨간색이면 다리가 없다.
박근혜가 탄핵당하지 않았다면 똥파리도 새다.

위 문장(명제)들은 참일까요, 거짓일까요? 재미있게도 모두 _참_입니다! 어떻게 그럴 수 있을까요? 명제

$$P \implies Q$$

가 있을 때, $P$가 거짓이면 $Q$의 참/거짓 여부와 무관하게 해당 명제($P \implies Q$)는 무조건 참입니다. 예에서 $P$ 부분에 해당하는 "코끼리가 빨간색이면", "박근혜가 탄핵당하지 않았다면" 은 모두 거짓이므로, 공진 원리에 의해 $Q$ 부분인 "다리가 10개이다", "다리가 없다", "똥파리도 새다" 가 참인지 여부와 무관하게 전체 명제는 참이 됩니다.

이를 공진(vacuous truth)이라고 하는데, 처음 접하면 도무지 상식적으로 받아들이기 어려운 면이 있습니다. 재미있는 사실은 프로그래밍 언어를 학습한 경우 이미 이 공진의 원리에 익숙하다는 사실입니다.

우리가 논리 연산자인 ||(논리 OR 연산자) 와 &&(논리 AND 연산자) 를 배울 때 중요하게 다루는 사실이 하나 있습니다. 바로 "단축 평가" 혹은 "단락 평가(short circuit evaluation)"라고 부르는 기능입니다. 단축 평가가 중요한 이유는 바로 아래와 같은 코드를 작성할 수 있도록 해주기 때문입니다.

if (p != NULL && *p == ch)

(! 는 논리 부정 연산자 logical negation operator 입니다.) 만약, 단축 평가가 없다면, p가 널 포인터(NULL)인 경우에도 우측 수식인 *p == ch 가 평가되기 때문에 널 포인터 참조(null pointer dereferencing)가 발생해 프로그램이 오동작하게 됩니다. 하지만, 단축 평가 덕분에 && 연산자의 좌측부터 평가되고, p 가 NULL 인 경우 우측은 평가하지 않는다는 사실이 보장됩니다.

그런데 이 단축 평가가 동작할 수 있는 이유는 && 연산자의 경우 좌측이 거짓인 경우 우측과는 무관하게 전체 수식이 거짓이 되기 때문이고, || 연산자의 경우 좌측이 참인 경우 우측과는 무관하게 전체 수식이 참이 되기 때문입니다. 바로 이 부분이 공진을 이해할 수 있는 부분입니다.

$$P \implies Q$$

는 (학창 시절 공부했던 집합과 명제 과정을 떠올려보면) 아래와 동일한 의미입니다.

$$\neg P \lor Q$$

($\neg$ 는 논리 부정, $\lor$ 은 논리 OR 을 의미합니다.)

그럼, 이제 공진이었던 문장 중 하나를 프로그래밍 언어인 척 표현해 보겠습니다. $P$ 는 "코끼리가 빨간색이면" 이고, $Q$ 는 "다리가 없다" 이므로 이를 $\neg P \lor Q$ 로 표현하면,

!코끼리가_빨간색이라면 || 다리가_없다

가 됩니다. 이때 코끼리가_빨간색이라면이 거짓이므로 || 연산자의 좌변은 참이 되고, 우변의 참/거짓 여부와 무관하게 전체 수식은 참이 됩니다 - 바로 _공진_입니다!

이제 공진이 조금은 쉽게 받아들여집니다. 더불어, "집합과 명제"에서 $P \implies Q$ 를 $\neg P \lor Q$ 혹은 $P^c \cup Q$ 와 같다고 했던 게 무슨 의미였는지도 자연스럽게 이해됩니다 - 코딩이 이렇게나 유익합니다!

이제 이 공진을 가지고 문제의 공집합의 교집합에 대한 내용인

$$\bigcap \emptyset = U$$

를 이해해 보도록 하겠습니다.

우선, 교집합의 가장 일반적인 정의($\bigcap$)에 대해 살펴보겠습니다.

$$\bigcap_{A \in X} = \{ x : \forall A \in X, x \in A \}$$

조금 복잡해 보이기는 한데, 우선 몇가지만 짚고 넘어가겠습니다.

$X$는 집합들의 집합(set of sets)입니다. 헷갈리므로 이를 "모음(collection)"이라고 부르도록 하겠습니다.
$X$는 모음이므로 그 요소(member)는 집합입니다.
$\bigcap$ 에 주어지는 것이 모음이므로 $\bigcap$ 은 모음 안에 있는 집합들에 적용되는 것으로 이해할 수 있습니다.

이제 저 정의를 부정확하지만 그나마 이해하기 쉽게 말로 풀어쓰면,

모음 $X$ 안에 집합이 있고 이를 $A$ 라고 하면, 어떤 요소 $x$ 가 모든 $A$ 에서 요소이면 $x$ 를 결과 집합(교집합)의 요소로 넣는다.

즉, 모음 안에 있는 모든 집합들에 공통으로 속해있는 요소를 추려 결과로 집합을 만드는 것입니다. 그리고,

$$A \cap B = \bigcap \{ A, B \}$$

입니다.

구체적인 예를 보면,

$$A = \{ 1, 2, 3 \}$$ $$B = \{ 2, 3 \}$$ $$C = \{ 3, 4 \}$$ $$X = \{ A, B, C \}$$

라고 할 때

$$\bigcap X$$ $$= \bigcap \{ A, B, C \}$$

가 되고 집합 $A$, $B$, $C$ 에 모두 속한 요소인 $3$ 을 결과로 가져

$$\bigcap X = \{ 3 \}$$

이 됩니다. $\bigcap$ 의 정의를 "imply"($\implies$) 를 사용해 다시 기술할 수도 있지만 그보다 코딩으로 표현하는 것이 보다 분명하게 의미가 전달됩니다.

위에 기술된 정의의 의미 그대로 살려 코딩으로 표현하면 아래와 같습니다.

for each member x in Universe
{
    A = getIteratorFor(X);    // X 가 비어있으면 null 반환
    if (!isNonNull(A) || checkIfAllHave(x, A))
        addTo(x, result);    // result 집합에 x 추가 
}

// iterator A 에서 집합(B)을 하나씩 가져와서
// x 가 모든 B 에 있을 때에만 true 반환
checkIfAllHave(x, A) {
    assert(A != null);    // iterator A 가 null 이면 안 됨
    B = getNextMemberFrom(A);    // 모두 소진되면 null 반환
    while (isNonNull(B)) {
        if (!isMemberOf(x, B))
            return false;
        B = getNextMemberFrom(A);
    }
    return true;
}

이제 이 코드에 위의 간단한 예를 대입해보면

Universe = { 1, 2, 3, 4 };
X = {
    { 1, 2, 3 },    // X1
    { 2, 3 },       // X2
    { 3, 4 }        // X3 라고 부르겠습니다
};

이므로 x 는 각각 1, 2, 3, 4 가 되며 루프를 돕니다.

A = getIteratorFor(X);

이제 iterator A 는 모음 X 의 요소(3개의 집합)에 대해 순환할 준비를 하게 됩니다. 그리고 checkIfAllHave() 안에서 x 가(처음에는 1이겠죠?) X1, X2, X3 모두에 속하는지 확인합니다. 1 은 그렇지 않으므로 false 가 반환되어 결과 집합에 속하지 못할 것입니다. 이런 식으로 루프를 돌고나면 결국 3 만이 결과 집합에 들어가 우리가 의도한 결과가 나올 것입니다.

이제 문제의

Universe = { 1, 2, 3, 4 };
X = {};    // 공집합

를 살펴보겠습니다. for 루프 안으로 진입한 후

A = getIteratorFor(X);    // X 가 비어있으면 null 반환

에서 A 는 null 이 됩니다. 그리고 그 밑의 if 문에서

if (!isNonNull(A) || checkIfAllHave(x, A))

|| 연산자의 좌변이 참이 됩니다 (공진입니다)! 고로 우변은 확인할 필요도 없이 Universe 의 모든 요소가 결과 집합으로 들어가게 됩니다. 즉,

$$\bigcap X = \bigcap \emptyset = U$$

가 되는 것입니다!

그럼, 이제 $\emptyset \cap \emptyset = \emptyset$ 을 살펴보겠습니다. 앞서 설명했듯이

$$\emptyset \cap \emptyset = \bigcap \{ \emptyset, \emptyset \}$$

입니다. (사실 공집합은 유일 unique 하기 때문에 $\{ \emptyset, \emptyset \} = \{ \emptyset \}$ 입니다만...) 고로 이 경우, 모음의 요소가 되는 집합들은 공집합이지만, 모음 자체는 공집합이 아닙니다. 따라서, 모음 자체가 공집합인 경우와 달리 상식 선의 결과가 나오게 됩니다. 코드에 적용해보면,

Universe = { 1, 2, 3, 4 };
X = {
    {},
    {}
};

로 놓고, 실행한 결과를 생각해보면 됩니다.

별로 대단치도 않고 재미도 없는 이야기를 더 재미없게 돌려 풀어놓은 감이 없진 않지만, 그래도 이렇게 글이라도 적어 강연 시간에 남발했던 "선의의" 거짓말을 속죄하는 느낌으로 글을 마무리짓도록 하겠습니다.

집합과 명제, 그리고 공진
일상의 습관화를 통한 최적화