불 대수로 사람 사이의 연결 계산하기

01 · 불이 풀려던 문제

한 사람씩 따라가지 않고 연결 전체를 계산할 수 있을까요?

가상의 학습 모임에 지민·서윤·도윤·하린 네 사람이 있습니다. “행의 사람이 열의 사람에게 자료를 요청할 수 있다”를 직접 연결이라고 하겠습니다. 지민이 서윤에게, 서윤이 도윤에게 요청할 수 있다면 지민은 서윤을 거쳐 도윤에게 닿습니다. 사람이 많아질수록 문장을 하나씩 따라가는 일은 빠뜨리기 쉽습니다. 불 논리는 이런 조건을 반복 가능한 계산 규칙으로 정리하는 출발점을 줍니다.

불이 해결하려 했던 더 넓은 문제는 언어로 표현한 부류와 조건을 기호 계산으로 옮기는 일이었습니다. 그의 곱셈 xy는 x이면서 y인 부분을 고르고, 각 선택 기호는 x²=x를 만족합니다. 연결표에서도 “첫 연결이 있고 두 번째 연결도 있다”를 곱으로 읽을 수 있습니다.

02 · 불의 연산을 행렬로 옮기기

중간 사람마다 곱하고, 하나라도 성립하면 1입니다

직접 연결 행렬을 A라고 하겠습니다. A_ik=1은 i가 k에게 직접 이어짐을, 0은 직접 이어지지 않음이 확인되었음을 뜻합니다. 미확인은 0으로 넣지 않고 먼저 조사해야 합니다. 정확히 두 단계를 거쳐 i에서 j로 이어지는지는 모든 중간 사람 k를 확인해 계산합니다.

보통 행렬곱은 곱한 수를 더해 0, 1, 2처럼 경로 수를 남깁니다. 불 행렬곱은 각 곱을 AND로, 더하는 자리를 OR로 바꾸므로 가능한 중간 사람이 한 명 이상이면 결과가 1입니다. 따라서 결과 1은 “두 단계 경로가 존재한다”는 뜻이며 경로가 몇 개인지는 별도 개수표가 필요합니다.

03 · 불의 제안을 연결표에서 확인하기

직접 연결을 누르고 두 단계 결과를 비교하세요

‘한 줄 연결’에서는 지민→서윤→도윤과 서윤→도윤→하린이 보여 두 단계 결과에 지민→도윤, 서윤→하린이 생깁니다. 지민→하린은 세 단계이므로 A⊙A에는 아직 나타나지 않습니다. 표의 1을 누르며 중간 사람의 증거가 어떻게 바뀌는지 확인해 보세요.

04 · 표에서 얻은 발견

두 단계 1에는 반드시 중간 사람이라는 증거가 있습니다

결과 칸이 1이면 직접 연결 두 개가 동시에 1인 중간 사람을 적어도 한 명 찾을 수 있습니다. 결과 칸이 0이면 네 사람 가운데 어느 누구도 두 연결을 모두 만족하지 못합니다. 이처럼 불 행렬곱은 “가능한 모든 중간 후보를 검사하고 하나라도 성공하는가”를 한 식으로 묶습니다.

직접 연결 수와 두 단계 연결 수는 사람 수가 아닙니다. 둘 다 방향이 있는 순서쌍의 개수입니다. 같은 사람으로 돌아오는 대각선의 1도 한 쌍으로 셉니다. ‘모두 1’에서는 16개 직접 쌍과 16개 두 단계 쌍이 나오지만, 이것을 16명이라고 읽으면 안 됩니다.

05 · 오늘의 실제 적용

권한·이동·의존 관계에서 두 단계 후보를 찾습니다

조직의 승인 전달, 교통의 환승, 소프트웨어 모듈의 의존 관계처럼 방향이 있는 연결은 인접 행렬로 나타낼 수 있습니다. A⊙A는 직접 연결 하나를 더 거쳐 닿는 후보를 보여 줍니다. 예를 들어 직접 연락망에서 한 사람을 경유해 전달 가능한 대상을 찾거나, 부품 의존표에서 두 단계 뒤에 영향을 받는 모듈을 점검할 수 있습니다.

1962년 Stephen Warshall은 불 행렬을 갱신해 그래프의 추이적 폐쇄, 곧 몇 단계를 거치든 도달 가능한 모든 쌍을 구하는 알고리즘을 발표했습니다. 이번 표는 정확히 두 단계인 A²만 계산합니다. A, A², A³…을 합치거나 Warshall 방식으로 갱신해야 전체 도달 관계가 됩니다.

06 · 역사와 한계

불의 부류 계산과 후대의 관계 행렬을 구별합니다

불의 1847년과 1854년 저술은 부류와 명제를 선택 기호와 대수식으로 계산했습니다. 오늘의 불 행렬, 그래프 인접 행렬, 관계 합성 표기는 그 원리를 이어받은 후대의 수학입니다. Warshall의 1962년 논문도 불 이후 약 한 세기가 지난 연구입니다.

이 실험의 사람과 연결은 모두 가상입니다. 연결 1은 정해 둔 관계가 성립한다는 뜻입니다. 실제 사람 관계를 0·1로 단순화할 때는 자료 수집 동의, 갱신 시점, 누락값, 관계의 방향을 함께 기록해야 합니다.