Search the Kids Internet
Encyclopedia > Satisfiability
Article Content
Satisfiability
In mathematics, a formula of propositional logic is said to be satisfiable if truth-values can be assigned to its free variables in a way that makes the formula true. The class of satisfiable formulas of propositional logic is NP-complete, as is that of its variant 3-satisfiability[?].
(There is also such a thing as satisfiability of formulas of first-order and second-order logic.)
Compare with: decision problem
All Wikipedia text is available under the terms of the GNU Free Documentation License
|
Search Encyclopedia
|
Featured Article
|