불리언 논리

명제는 명제 기호와 연결 연산자로 이루어진 논리식이다. 명제는 다음 규칙으로 재귀적으로 정의된다.

1. 모든 명제 기호(이 문제에서는 a, z처럼 하나의 소문자)는 명제이다.
2. $P$가 명제이면 (!$P$)도 명제이며, $P$는 그것의 직접 부분식이다.
3. $P$와 $Q$가 명제이면 ($P$&$Q$), ($P$|$Q$), ($P$-->$Q$), ($P$<->$Q$)도 명제이며, $P$와 $Q$는 각각의 직접 부분식이다.
4. 그 밖의 것은 명제가 아니다.

연산자 !, &, |, -->, <->는 각각 부정, 논리곱, 논리합, 함의, 동치를 나타낸다. 명제 $P$가 명제 $R$의 부분식이라는 것은 $P = R$이거나, $P$가 어떤 명제 $Q$의 직접 부분식이면서 $Q$가 $R$의 부분식인 경우를 말한다.

이제 명제 $P$를 하나 고르고, $P$에 나타나는 모든 명제 기호에 불 값($0$ 또는 $1$)을 배정하자. 그러면 연산자의 표준 의미에 따라 $P$의 모든 부분식에 불 값이 정해진다.

이렇게 하여 $P$의 값이 계산된다. 이 값은 명제 기호에 대한 배정에 따라 달라진다. $P$에 서로 다른 명제 기호가 $n$개 있으면 배정은 모두 $2^n$가지이다. 가능한 모든 배정을 살펴보기 위해 진리표를 사용한다.

진리표는 배정 하나당 한 줄씩, 즉 모두 $2^n$줄로 이루어진다. 각 줄에는 해당 배정에서의 모든 부분식의 값이 적힌다. 부분식이 명제 기호이면 그 값을 해당 기호의 위치에 맞추어 적고, 그렇지 않으면 연산자의 가운데에 맞추어 적는다.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 줄은 하나의 명제를 나타내고, 문자 사이에 임의 개수의 공백이 들어갈 수 있다. 입력은 마지막 테스트 케이스 뒤의 개행 문자 직후에 끝난다.

각 테스트 케이스마다 주어진 명제의 진리표를 출력한다. 먼저 입력 줄을 그대로 한 번 출력하여 진리표를 시작한다. 그다음 명제와 그 모든 부분식을 명제 기호에 대한 가능한 모든 불 값 배정에 대해 계산하여, 배정마다 한 줄씩 출력한다. 각 줄의 길이는 대응하는 입력 줄의 길이와 정확히 같아야 하며, 공백과 문자 0, 1만으로 이루어져야 한다. 각 부분식의 값은 위에서 설명한 위치에 적는다. 각 테스트 케이스 뒤에는 빈 줄을 하나 출력한다.

주어진 명제의 명제 기호를 알파벳 순으로 정렬한 것을 $s_1, \ldots, s_n$이라 하자. 그러면 $s_1$에 $0$을 배정하는 모든 경우가 $s_1$에 $1$을 배정하는 모든 경우보다 앞에 와야 한다. 각 블록 안에서는 다시 $s_2$에 $0$을 배정하는 경우가 $s_2$에 $1$을 배정하는 경우보다 앞에 오고, 이런 식으로 계속된다(따라서 $s_n$이 가장 빠르게 바뀐다).