Suppose you have n Boolean variables, named A, B, C, ..., and you have an expression in
the propositional calculus (that is, you can use **and**, **or**, and **not** to
form the expression.) Is there an assignment of truth values to the variables (e.g. A=**true**,
B=**true**, C=**false**, ....) that will make the expression **true**?

Here is a nondeterministic algorithm to solve the problem: For each Boolean variable, assign it the proper truth value. This is a linear algorithm.

We can find a deterministic algorithm for this problem in much the same way as we did
for the integer bin problem. Effectively, the idea is to set up a systematic procedure to
try every possible assignment of truth values to variables. The algorithm terminates when
a satisfactory solution is found, or when all 2^{n} possible assignments have been
tried. Again, the deterministic solution requires exponential time.

Problems such as this arise in circuit design.

Copyright © 1996 by David Matuszek

Last modified Apr 28, 1996