Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Determining the Satisfiability of a Boolean Formula

ALGOR-R21BD9

When working with boolean formulas composed of boolean variables and logical connectives, it is often necessary to determine the satisfiability of a formula. A formula is satisfiable if there exists some assignment of true or false to each of the variables in the formula which renders the entire formula true. For example, the following formula is satisfiable:

$(A ∨ B)$

This formula, which contains two variables connected by the ∨ (OR) operator, it satisfied if either A is true or B is true (or both). An assignment of true or false to each variable in a boolean formula is referred to as a truth assignment. Because a truth assignment exists which renders the entire formula true, the formula is satisfiable.

Now consider the following formula, which is unsatisfiable:

$(A ∧ ¬A)$

This formula contains only one variable, A, along with its negation, ¬A, connected by the ∧ (AND) operator. This formula will only be satisfied if A and ¬A are both true, which is impossible. No truth assignments exist which satisfy this formula, therefore it is deemed unsatisfiable.

Answer the following questions about boolean formulas and their satisfiability.