같은 학생 번호라면, 이름도 항상 같아야 할까요?

한 학교의 같은 학년도 수강 신청표를 살펴보겠습니다. 이 학교는 학생마다 고유한 번호를 부여하고, 이 표가 다루는 기간에는 이름을 고정해 기록한다고 가정합니다. 학생 한 명이 여러 과목을 신청하면 같은 번호와 이름이 여러 줄에 나타납니다.

첫 번째 기록을 읽으면 “101번 학생 민서가 논리를 신청했다”는 내용을 알 수 있습니다. 그 기록이 실제 신청 내용과 맞는지 확인하는 것이 한 기록에 대한 사실 확인입니다.

여기서 한 가지를 더 묻습니다. “학생 번호가 같은 기록끼리 비교하면 이름도 항상 같을까?” 101번이 적힌 두 기록을 함께 보면 이름이 모두 민서입니다. 이렇게 같은 번호에 어떤 이름이 연결되는지 비교하는 것이 이 글에서 다룰 질문입니다.

앞의 표에서 가로 한 줄을 행이라고 합니다. 한 행에는 학생 번호·이름·신청 과목이 함께 적혀 있습니다. 세로로 같은 항목이 모인 부분은 열입니다.

논리학에서는 학생 번호나 이름처럼 값을 넣을 항목을 ‘변수’로 나타냅니다. 각 항목에 101·민서·논리라는 값을 정해 놓은 한 기록을 할당이라고 부릅니다. 같은 항목들로 작성한 이런 기록을 모은 집합이 팀입니다. 이 글에서 팀은 비교할 기록의 묶음을 뜻합니다.

기록이 하나일 때도 정확히 구별해 봅시다. 논리학의 정의상 한 기록만 있는 팀도 “번호가 같으면 이름이 같다”는 의존 조건을 만족합니다. 서로 다른 이름으로 충돌하는 두 기록이 생길 수 없기 때문입니다. 다만 한 건의 관찰에서 확인한 사실과, 학교의 모든 기록에 적용할 일반적인 관리 규칙은 적용 범위가 다릅니다.

비교하는 기록 전체에서, 학생 번호가 같은 두 기록은 이름도 같다는 뜻입니다. 이 조건을 만족하면 학생 번호 하나에 이름 하나가 연결됩니다. 이를 함수적 의존이라고 합니다.

검사 방법은 두 단계입니다. 두 기록의 번호를 먼저 비교합니다. 번호가 같을 때 두 이름도 같은지 확인합니다. 번호가 다른 두 기록에는 같은 이름이 적힐 수도, 다른 이름이 적힐 수도 있습니다. 동명이인도 이 조건에 맞게 기록할 수 있습니다.

이를 짧게 =(학생 번호, 이름)이라고 적겠습니다. 괄호 앞의 등호와 두 항목을 함께 써서 의존 관계를 표시한 기호입니다. 읽을 때는 “학생 번호가 이름을 하나로 정한다”라고 풀어 읽으면 됩니다.

원인과 결과는 별도로 살펴야 합니다. 여기서 ‘정한다’는 말은 표에서 번호 하나에 이름 하나가 대응한다는 뜻입니다. 학생 번호 때문에 그 사람의 이름이 생겼다는 인과관계까지 주장하는 표현은 아닙니다. 또한 이 검사의 범위는 앞에서 정한 학교·학년도·기록 기간입니다.

한 학교의 기록만 모았다면 학교 이름은 모든 기록에서 같습니다. 예를 들어 학교 이름 칸이 전부 ‘가온학교’라고 적혀 있다고 해 봅시다. 번호를 확인하기 전부터 학교 이름이 하나로 정해져 있습니다. 이렇게 기록 전체에서 값이 같은 성질을 상수성이라고 부릅니다.

상수성은 의존의 특별한 경우로 나타낼 수 있습니다. 앞에 비교 기준을 두지 않아도 뒤의 값이 하나로 고정되는 경우입니다. 그래서 =(학교 이름)처럼 항목 하나를 적습니다.

의존 조건도 다른 조건들과 이어 쓸 수 있습니다. 이때 논리식은 기록들의 집합을 기준으로 해석합니다. 우선 ‘그리고’는 같은 기록 집합이 두 조건을 모두 만족한다는 뜻입니다. ‘또는’은 전체를 덮는 두 부분집합을 잡아 각각의 조건을 만족시키는 방식으로 읽습니다.

예를 들어 ‘논리 과목을 신청했거나 윤리 과목을 신청했다’는 조건은 논리 신청 기록과 윤리 신청 기록으로 전체를 나누어 확인할 수 있습니다. 여기에 의존 조건까지 함께 쓰면 각 부분의 기록 사이에 어떤 관계가 유지되는지도 물을 수 있습니다.

일차논리의 보통 문장만 사용하면, 팀에 대한 확인은 각 기록에서 그 문장이 성립하는지 확인하는 방식과 일치합니다. 의존을 나타내는 기호를 추가하면 여러 기록 사이의 값 일치 조건을 직접 표현할 수 있습니다.

같은 학년도에 학생 번호 하나로 소속 반이 정해지고, 반 하나로 담임교사가 정해진다고 가정해 보겠습니다. 그러면 학생 번호로 담임교사도 정할 수 있습니다. 이미 확인한 두 의존 관계를 이어서 새로운 의존 관계를 얻은 것입니다.

논문은 이런 규칙들을 암스트롱 공리라고 소개합니다. 같은 항목은 자기 자신의 값을 정한다는 규칙, 비교 기준을 더 추가해도 이미 성립한 의존은 유지된다는 규칙, 항목의 순서를 바꾸어 적어도 관계가 유지된다는 규칙, 의존 관계를 차례로 이어 추론하는 규칙입니다.

이 규칙들의 ‘완전성’은 함수적 의존 관계들로부터 반드시 따라오는 다른 함수적 의존 관계를 모두 유도할 수 있다는 뜻입니다. 적용 범위가 의존 관계 사이의 추론이라는 점을 함께 기억하면 좋습니다. 복잡한 의존논리의 모든 추론은 추가로 살펴야 합니다.

모든 기록에서 같은 번호에 같은 이름이 연결되어 있었다고 합시다. 여기서 기록 몇 개를 골라 남기면, 남은 기록에서도 그 규칙이 유지됩니다. 남은 두 기록은 원래도 함께 검사했던 두 기록이기 때문입니다.

이 성질은 의존논리의 중요한 특징입니다. 반대 방향은 따로 확인해야 합니다. 일부 기록에서 규칙이 성립하더라도 다른 기록까지 합쳤을 때는 충돌이 드러날 수 있습니다. 오류가 있던 기록을 빼고 검사하면 그 오류가 검사 범위에서 빠지는 점도 주의해야 합니다.

행사에서 고를 수 있는 배지가 빨간 원, 빨간 별, 파란 원, 파란 별의 네 종류라고 합시다. 색을 빨강으로 골라도 모양은 원과 별 중에서 고를 수 있습니다. 파랑을 골랐을 때도 모양의 선택지는 같습니다.

팀 의미론의 독립은 이런 성질을 확인합니다. 표에 나타나는 색 하나와 모양 하나를 각각 골라 결합했을 때, 그 조합도 표에 있어야 합니다. 이를 ‘색 ⊥ 모양’으로 적습니다. 이때 색을 알게 되어도 가능한 모양의 범위가 줄어들지 않습니다. 색과 모양의 순서를 바꾸어 설명해도 같습니다.

여기서는 가능한 조합의 존재를 살펴봅니다. 각 조합이 나타날 확률이나 배지의 수량은 이 표에 주어져 있지 않습니다. 통계에서 말하는 확률적 독립을 판단하려면 확률분포에 관한 정보와 별도의 조건을 확인해야 합니다.

두 조건은 각각의 기준으로 검사해야 합니다. 색이 모양을 정하는지는 같은 색의 모양이 하나로 고정되는지 봅니다. 색과 모양이 독립인지는 표에 나타난 색들과 모양들의 모든 조합이 있는지 봅니다.

두 조건을 동시에 만족하는 경우도 있습니다. 빨간 원과 파란 원만 있다고 해 봅시다. 모양이 항상 원이므로 색마다 모양이 하나로 정해집니다. 동시에 표에 실제로 나타나는 두 색과 한 모양을 조합한 두 종류가 모두 있습니다.

지금까지는 의존이나 독립을 나타내는 짧은 기호 하나씩을 읽었습니다. 이런 기호를 ‘그리고’, ‘또는’, ‘어떤’, ‘모든’과 함께 쓰면 더 복잡한 조건을 표현할 수 있습니다. 예를 들어 여러 항목을 배정하면서 특정 정보만으로 각 배정값이 정해져야 한다는 조건을 적을 수 있습니다.

논문은 자유변수가 남아 있지 않은 완결된 논리 문장을 기준으로 의존논리와 독립논리의 표현력이 같다고 설명합니다. 자유변수는 문장 밖에서 값을 따로 정해야 하는 변수입니다. 완결된 문장에서는 그런 변수가 모두 처리되어, 주어진 수학적 구조 전체에 대해 문장의 참과 거짓을 묻게 됩니다.

존재 이차논리는 대상 하나의 존재를 묻는 데 더해, 일정한 조건에 맞는 관계나 함수가 존재하는지도 묻습니다. ‘규칙을 지키는 배정표 전체가 있는가’라는 질문으로 생각하면 출발점을 이해하기 쉽습니다. 앞에서 비교한 개별 의존 조건과 독립 조건의 뜻은 각각 그대로 유지됩니다.

이번 행사에서는 학년마다 배지를 고를 수 있는 범위가 다르다고 합시다. 1학년은 빨강·파랑과 원·별을 조합합니다. 2학년은 빨강·초록과 원·삼각형을 조합합니다. 각 학년 안에서는 그 학년에 허용된 색과 모양의 모든 조합을 고를 수 있습니다.

이 관계를 색 ⊥_학년 모양으로 적겠습니다. “학년을 고정하면 색과 모양이 독립이다”라고 읽습니다. 아래에 적힌 ‘학년’이 비교할 때 같게 유지하는 조건입니다. 조건부 독립도 각 조건 안에서 가능한 값의 결합을 검사합니다.

논문의 정리 11은 조건부 독립을 사용한 논리식을, 조건을 아래에 붙이지 않은 독립 기호와 일차논리의 표현들로 다시 쓸 수 있다고 밝힙니다. 필요한 보조 변수와 양화사 등을 함께 사용해 원래 식과 같은 조건을 표현하는 것입니다.

앞의 예에서 ‘학년’을 그대로 지우면 뜻이 달라집니다. 실제로 각 학년 안에서는 독립이 성립하지만 전체에서는 파란 삼각형이 빠져 있었습니다. 따라서 변환할 때는 원래 식의 ‘같은 학년끼리 비교한다’는 요구를 다른 부분에 정확히 담아야 합니다.

연구에서는 같은 뜻을 여러 방식으로 표현하는 일이 중요합니다. 한 표현에 대해 얻은 결과를 다른 표현을 사용하는 연구에도 연결할 수 있기 때문입니다. 여기서는 ‘조건을 생략한다’와 ‘조건의 뜻을 다른 식으로 표현한다’를 분명히 구별하면 됩니다.

‘이런 답이 존재한다’는 조건을 논리식으로 적는 일과, 그 답을 실제로 찾아내는 일은 서로 다른 과제입니다. 예를 들어 연결된 두 지점의 색이 서로 다르도록 모든 지점에 세 가지 색을 배정하는 문제를 생각해 봅시다.

논문은 유한한 구조에서 독립논리가 엔피(NP) 성질을 표현한다는 결과를 소개합니다. 엔피는 답이 ‘예’인 경우 적당한 길이의 증거를 제시받아 입력 크기의 다항식 시간 안에 확인할 수 있는 결정 문제들의 종류입니다. 이 결과는 논리로 표현할 수 있는 조건의 범위를 설명합니다.

이 표현력 결과만으로 모든 문제의 답을 빠르게 찾아 주는 프로그램이 얻어지는 것은 아닙니다. 앞서 학생 번호와 이름을 비교한 간단한 검사, 복잡한 배정표의 존재를 묻는 문제, 논리식 자체를 입력으로 받는 문제는 각각의 계산 과제를 구분해 살펴야 합니다.

그렇게 읽을 수도 있습니다. 이번에는 여러 실제 신청 기록을 모으는 대신, 아직 확인 중인 책의 위치를 적어 봅시다. 책이 A서가의 1칸 또는 A서가의 2칸에 있다고 생각한다면 두 상황을 각각 한 기록으로 적을 수 있습니다.

이 정보 상태에서는 서가가 A라는 점은 정해져 있고, 몇 번째 칸인지는 추가 확인이 필요합니다. 그래서 ‘서가’의 상수성은 이미 아는 값에 대응합니다. 이때의 팀은 현재 가능하다고 여기는 상황들의 집합입니다.

“책은 2칸에 있다”는 새 정보를 받아들이면 그 정보와 맞는 둘째 상황을 남겨 위치를 더 좁힐 수 있습니다. 반대로 다른 사람이 고려하는 가능성까지 함께 받아들이면 비교할 상황이 늘어날 수도 있습니다. 논문 5절은 의존·독립을 이런 정보 상태를 설명하는 언어로 해석하고, 두 사람이 생각하는 가능성을 합치는 경우도 살펴봅니다.

한 사람이 가능하다고 여기는 상황과 실제 상황은 구별해야 합니다. 이 모형은 그 사람이 가진 정보의 구조를 표현합니다. 정보의 정확성은 별도의 확인 대상입니다.

처음에 정한 학교의 기록 규칙에 따르면, 같은 학생 번호가 적힌 기록에는 같은 이름이 적혀 있어야 합니다. 이 조건을 확인하려면 번호가 같은 기록들을 찾아 이름을 비교하면 됩니다. 번호 101에 민서와 지우가 함께 적혀 있다면 두 기록이 규칙과 충돌하는 지점을 정확히 찾은 것입니다.

이제 글의 출발점을 두 질문으로 말할 수 있습니다. “이 한 기록이 실제 사실과 맞는가?” 그리고 “여러 기록을 함께 놓았을 때 같은 번호에 같은 이름이 연결되는가?” 뒤의 질문처럼 정보 사이에 어떤 관계가 유지되는지 살피는 것이 의존논리를 이해하는 첫걸음입니다.

독립을 살필 때는 가능한 값들을 서로 조합해 보고, 조건부 독립을 살필 때는 학년처럼 정해 둔 항목의 값이 같은 기록끼리 나누어 비교합니다. 무엇을 기록했고 무엇을 같게 두어 비교하는지 밝히면, 낯선 논리 용어도 구체적인 검사 방법으로 이해할 수 있습니다.