Factorung by Filling entries on boolean Division Matrix
Oh-Hyeong Kwon · The Journal of Korean Institute of Information Technology · 2013
인수 분해식은 대수 인수 분해식과 부울 인수 분해식으로 구분할 수 있으며, 부울 인수 분해식이 대수 인수분해식보다 적은 수의 리터럴로 다단 논리식을 표현할 수 있는 것은 이미 잘 알려진 사실이다. 본 논문에서는 자료구조로 부울 나눗셈 행렬과 이 행렬에 부울 공리를 적용한 나눗셈에 의한 부울 인수 분해식 산출 방법을 제안한다. 제안하는 핵심 방법은 먼저 주어진 논리식에서 2개의 항들을 선택하여 부울 나눗셈 행렬을 만드는 것이고, 다음 부울 나눗셈 행렬에서 단위 열과 지배받는 열을 찾아 제거한 간략화된 부울 나눗셈 행렬을 산출하는 것이다. 제안한 간략화된 부울 나눗셈 행렬은 사각형 추출을 보다 용이하도록 하여 부울 인수 분해식을 산출하도록 하였다. 실험 결과 타 인수 분해식 산출 방법들보다 리터럴 개수를 줄일 수 있었다.