5.2 Propositional Constraints

Chapter 4 shows how to reason with constraints. Logical formulas provide a concise form of constraints with structure that can be exploited.

The class of propositional satisfiability problems have:

• Boolean variables: a Boolean variable is a variable with domain $\{\mbox{true},\mbox{false}\}$. If $X$ is a Boolean variable, we write $X=\mbox{true}$ as its lower-case equivalent, $x$, and write $X=\mbox{false}$ as $\neg{x}$. Thus, given a Boolean variable Happy, the proposition happy means $\mbox{Happy}=\mbox{true}$, and $\neg{\mbox{happy}}$ means $\mbox{Happy}=\mbox{false}$.

• Clausal constraints: a clause is an expression of the form $l_{1}\vee l_{2}\vee\dots\vee l_{k}$, where each $l_{i}$ is a literal. A literal is an atom or the negation of an atom; thus a literal is an assignment of a value to a Boolean variable. A clause is satisfied in a possible world if and only if at least one of the literals that makes up the clause is true in that possible world.

If $\neg a$ appear in a clause, the atom $a$ is said to appear negatively in the clause. If $a$ appears unnegated in a clause, it is said to appear positively in a clause.

In terms of the propositional calculus, a set of clauses is a restricted form of logical formulas. Any propositional formula can be converted into clausal form.

In terms of constraints, a clause is a constraint on a set of Boolean variables that rules out one of the assignments from consideration – the assignment that makes all literals false.

Example 5.4.

The clause $\mbox{happy}\vee\mbox{sad}\vee\neg{\mbox{living}}$ is a constraint among the variables Happy, Sad, and Living, which is true if Happy has value true, Sad has value true, or Living has value false. The atoms happy and sad appear positively in the clause, and living appears negatively in the clause.

The assignment $\neg{\mbox{happy}}$, $\neg{\mbox{sad}}$, living violates the constraint of clause $\mbox{happy}\vee\mbox{sad}\vee\neg{\mbox{living}}$. It is the only assignment of these three variables that violates this clause.

It is possible to convert any finite CSP into a propositional satisfiable problem:

• A CSP variable $Y$ with domain $\{v_{1},\dots,v_{k}\}$ can be converted into $k$ Boolean variables $\{Y_{1},\dots,Y_{k}\}$, where $Y_{i}$ is true when $Y$ has value $v_{i}$ and is false otherwise. Each $Y_{i}$ is called an indicator variable. Thus $k$ atoms, $y_{1},\dots,y_{k}$, are used to represent the CSP variable.

• There are constraints that specify that $y_{i}$ and $y_{j}$ cannot both be true when $i\neq j$. There is a constraint that one of the $y_{i}$ must be true. Thus, the knowledge base contains the clauses: $\neg y_{i}\lor\neg y_{j}$ for $i and $y_{1}\lor\dots\lor y_{k}$.

• There is a clause for each false assignment in each constraint, which specifies which assignments to the $Y_{i}$ are not allowed by the constraint. Often these clauses can be combined resulting in simpler constraints. For example, the clauses $a\lor b\lor c$ and $a\lor b\lor\neg{c}$ can be combined to $a\lor b$.