우선, 명제의 개수 n=3일 때를 예시로 들겠습니다. 명제들을 각각 x, y, z라고 하면 8개의 해(가능한 조합)가 다음과 같이 나옵니다.
x y z (theta)
000
001
010
011
100
101
110
111
이 때, 어떤 논리식을 참으로 만드는 해집합을 생각해볼 수 있는데 일단 가장 간단하게 x를 참으로 만드는 해들을 구해보면 100, 101, 110, 111로 4가지입니다.
그런데 위에 제가 theta를 썼는데 저렇게 이진법 표현으로 생각했을 때 수가 커지는 방향으로 순서를 부여한다면 각 해에 theta가 몇인지를 말할 수 있게 됩니다. 그렇다면 x는 해집합으로 나타내면 00001111이었는데 이것이 theta에 대한 함수라고 생각해보고 (오차를 허용하면서) 푸리에 급수로 나타내면 어떨까 합니다. 참고로 y는 00110011, z는 01010101입니다.
논리 연산자를 생각해본다면 not은 (1-함수)가 되겠고, and는 함수를 곱하게 되겠죠. 이런 식으로 x, y, z라는 간단한 식에서 점차 연산해나가서 복잡한 표현도 푸리에 급수로 나타내면 좋을 것 같습니다.
푸리에 급수 항의 개수는 n 정도면 되지 않을까 합니다. 만약 된다면 해집합의 유무를 통해 boolean function을 나타내기 위해 2^n개의 메모리를 쓰는 것보다 이득일 것 같습니다.
