P1745 [CERC2016] Lost Logic

Gustav is reading about *2-satisfiability*, a well known problem of assigning truth values to boolean variables in order to satisfy a list of *constraints* — simple logical formulas involving two variables each. We are using $n$ variables $x_1, x_2, \cdots , x_n$ that can take on values $0$ (false) and $1$ (true). A constraint is a formula of the form $a\to b$ where both $a$ and $b$ are possibly negated variables. As usual, $\to$ denotes logical implication: $a \to b$ is $0$ only when $a$ is $1$ and $b$ is $0$. The negation of variable $a$ is denoted by $!a$. Given an assignment of values to variables, we say that the constraint is *satisfied* if it evaluates to $1$. Gustav has constructed a list of constraints and correctly concluded that there are *exactly three* different assignments of values to variables that satisfy all the constraints. Gustav has wrote down all three assignments but has, unfortunately, lost the list of constraints. Given three assignments of $n$ values to variables, find any list consisting of at most $500$ constrains such that the three given assignments are the *only* assignments that satisfy all the constraints.

无

无