Satisfiability Problem · Problem Statement
Lesson 10
Programming problem. Given a truth table of a Boolean function, express it as a CNF.
- Input format. The first line contains the number of inputs \(n \le 5\). The second line contains a binary string of length \(2^{n}\). (The \(i\)-th bit of the string is the value of the function for the input \((x_{1}, \dotsc, x_{n})=\texttt{list(product([0, 1], repeat=n))[i]}\).)
- Output format. Specify each clause on a separate line. A clause is a sequence of literals separated by spaces: for example, a clause \((x_{4} \lor x_{2} \lor \overline{x_1})\) is given as \(\texttt{4 2 -1}\).
Public samples
Input
2 0010
Expected output
1 2 1 -2 -1 -2