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.