Truth-table Algorithm

The most basic algorithm for categorizing formulae is the truth-table algorithm. Propositional logic is ``nice.''

$$\begin{array} {ccc} x_1 & x_2 & (x_1+x_2)(x_1+\overline{x_2}) \ T&T&T\ T&F&T\ F&T&F\ F&F&F\end{array}$$

Therefore, satisfiable, not valid.

• sound: gives only correct answers
• complete: always gives an answer
• not efficient: exponential time, 2ⁿ table entries