불의 전개식에서 결정 다이어그램으로

01 · 불이 풀려던 문제

여덟 경우를 더 짧은 계산 구조로 묶을 수 있을까요?

함수 f가 “x가 1이면 y, x가 0이면 z”라고 합시다. 식으로는 f=xy+(1−x)z입니다. x=1인 네 행에서는 z가 무엇이든 결과가 y이고, x=0인 네 행에서는 y가 무엇이든 결과가 z입니다. 여덟 행을 그대로 읽어도 맞지만, x를 먼저 물으면 두 갈래 뒤에 필요한 변수 하나씩만 확인하면 됩니다.

불 논리의 전개는 변수의 0·1 경우를 분리해 함수 전체를 표현했습니다. 20세기 결정 다이어그램은 이 경우 나누기를 그래프로 저장합니다. 같은 두 자식으로 가는 질문은 지우고, 같은 변수와 같은 두 자식을 가진 부분 그래프는 하나로 합칩니다.

02 · 불의 전개에서 그래프로

0가지와 1가지를 나누고 같은 부분을 공유합니다

한 변수 x를 기준으로 함수 f를 나누면 f=x·f|x=1 +(1−x)·f|x=0 꼴이 됩니다. 그래프의 x 마디에서 0선을 따르면 f|x=0, 1선을 따르면 f|x=1을 계산합니다. 선택한 입력 순서를 모든 경로에서 지키면 순서 BDD가 됩니다.

축약에는 두 규칙이 중요합니다. 첫째, 0선과 1선이 같은 곳으로 가는 마디는 질문해도 결과가 변하지 않으므로 지웁니다. 둘째, 변수·0선·1선이 모두 같은 마디는 하나만 남겨 공유합니다. 같은 변수 순서와 같은 함수라면 이렇게 축약한 그래프는 같은 구조가 됩니다.

03 · 불의 경우 나누기를 결정 그래프로 확인하기

입력 순서를 바꾸고 축약 마디 수를 비교하세요

x→y→z 순서에서는 x 뒤에 y 또는 z만 물어 세 질문 마디로 줄어듭니다. y나 z를 먼저 물으면 아직 x의 선택을 모르기 때문에 반복되는 결정이 더 남습니다. 순서를 바꾸어 마디 수와 경로를 비교해 보세요.

04 · 표에서 얻은 발견

같은 함수도 질문 순서에 따라 저장 크기가 달라집니다

어느 순서를 골라도 여덟 입력의 출력은 같습니다. 그래프는 표현 방법을 바꿀 뿐 함수의 뜻을 바꾸지 않습니다. 그러나 축약 뒤의 질문 마디 수는 순서에 따라 달라집니다. x를 먼저 두면 “x=1이면 y, x=0이면 z”라는 구조가 곧바로 드러납니다.

공유는 여러 입력이 같은 부분 그래프를 거치도록 경로를 합치는 방법입니다. 모든 입력의 결과는 그대로 유지됩니다. 현재 입력 버튼을 누르면 루트에서 0 또는 1선을 따라 종착값에 도달하고, 그 결과가 진리표의 강조 행과 일치합니다. 마디 표의 두 화살표를 따라가면 축약 뒤에도 각 입력의 계산 과정을 다시 확인할 수 있습니다.

05 · 오늘의 실제 적용

회로와 규칙의 동등성을 기호적으로 확인합니다

Bryant의 1986년 논문은 축약된 순서 함수 그래프가 고정된 변수 순서에서 불 함수를 표준적으로 표현하며, 논리 설계 검증에 사용할 수 있음을 보였습니다. 두 회로가 같은 함수를 계산하는지 비교하거나 어떤 입력이 오류 출력을 만드는지 찾을 때, 모든 행을 따로 저장하는 대신 공유 그래프를 계산에 이용할 수 있습니다.

결정 규칙에서도 같은 질문 뒤에 반복되는 하위 규칙을 공유하면 구조를 읽고 변경하기 쉬워집니다. 다만 실제 업무 규칙에는 숫자 범위·누락값·우선순위가 있어 0·1 BDD만으로 충분한지 먼저 판단해야 합니다.

06 · 역사와 한계

불 전개, 섀넌 분해, Bryant의 OBDD를 구별합니다

불은 1848년에 선택 함수의 전개 정리를 제시했습니다. 오늘 흔히 쓰는 ‘섀넌 전개’라는 이름과 스위칭 함수 문맥은 후대의 발전입니다. Bryant의 1986년 연구는 변수 순서, 축약 규칙, 그래프 연산 알고리즘을 결합해 OBDD를 실용적인 불 함수 자료구조로 정리했습니다.

BDD의 크기는 함수와 변수 순서에 따라 크게 달라집니다. 이 실험은 세 변수 선택 함수라 차이를 눈으로 확인할 수 있게 고른 가상 모형입니다.