5 Propositions and Inference

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 {true,false}. If X is a Boolean variable, we write X=true as its lower-case equivalent, x, and write X=false as ¬x. Thus, given a Boolean variable Happy, the proposition happy means Happy=true, and ¬happy means Happy=false.

  • Clausal constraints: a clause is an expression of the form l1l2lk, where each li 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 ¬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 ℎ𝑎𝑝𝑝𝑦𝑠𝑎𝑑¬𝑙𝑖𝑣𝑖𝑛𝑔 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 ¬ℎ𝑎𝑝𝑝𝑦, ¬𝑠𝑎𝑑, living violates the constraint of clause ℎ𝑎𝑝𝑝𝑦𝑠𝑎𝑑¬𝑙𝑖𝑣𝑖𝑛𝑔. 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 {v1,,vk} can be converted into k Boolean variables {Y1,,Yk}, where Yi is true when Y has value vi and is false otherwise. Each Yi is called an indicator variable. Thus k atoms, y1,,yk, are used to represent the CSP variable.

  • There are constraints that specify that yi and yj cannot both be true when ij. There is a constraint that one of the yi must be true. Thus, the knowledge base contains the clauses: ¬yi¬yj for i<j and y1yk.

  • There is a clause for each false assignment in each constraint, which specifies which assignments to the Yi are not allowed by the constraint. Often these clauses can be combined resulting in simpler constraints. For example, the clauses abc and ab¬c can be combined to ab.