1∧1 = 1.
Also needed is negation, denoted by a bar, and defined by
We consider now boolean expressions in conjunctive normal form (CNF). In
this form, we create expressions from variables x 1 ,x 2 ,…, x n , starting with
The terms t i , t j ,…, t k are created by or-ing together variables and their negation,
that is,
where each s l , s m ,…, s p stands for a variable or the negation of a variable. The s i
will be called literals, while the t i are said to be clauses of a CNF expression e.
The satisfiability problem is then simply stated: Given a satisfiable
expression e in conjunctive normal form, find an assignment of values to the
variables x 1 , x 2 ,…, x n that will make the value of e true. For a specific case, look
at
The assignment x 1 = 0, x 2 = 1, x 3 = 1 makes e 1 true so that this expression is
satisfiable. On the other hand,
is not satisfiable because every assignment for the variables x 1 and x 2 will make
e 2 false.
A deterministic algorithm for the satisfiability problem is easy to discover.
We take all possible values for the variables x 1 , x 2 ,…, x n and for each evaluate
the expression. Since there are 2 n such possibilities, this exhaustive approach has
exponential time-complexity.
Again, the nondeterministic alternative simplifies matters. If e is satisfiable,
Also needed is negation, denoted by a bar, and defined by
We consider now boolean expressions in conjunctive normal form (CNF). In
this form, we create expressions from variables x 1 ,x 2 ,…, x n , starting with
The terms t i , t j ,…, t k are created by or-ing together variables and their negation,
that is,
where each s l , s m ,…, s p stands for a variable or the negation of a variable. The s i
will be called literals, while the t i are said to be clauses of a CNF expression e.
The satisfiability problem is then simply stated: Given a satisfiable
expression e in conjunctive normal form, find an assignment of values to the
variables x 1 , x 2 ,…, x n that will make the value of e true. For a specific case, look
at
The assignment x 1 = 0, x 2 = 1, x 3 = 1 makes e 1 true so that this expression is
satisfiable. On the other hand,
is not satisfiable because every assignment for the variables x 1 and x 2 will make
e 2 false.
A deterministic algorithm for the satisfiability problem is easy to discover.
We take all possible values for the variables x 1 , x 2 ,…, x n and for each evaluate
the expression. Since there are 2 n such possibilities, this exhaustive approach has
exponential time-complexity.
Again, the nondeterministic alternative simplifies matters. If e is satisfiable,