Lesson 02

From yes-or-no rules to Boolean formulas

How can a set of ordinary yes-or-no rules become one exact formula?

Boolean logic represents each basic statement as true or false, then combines those values with connectives whose meanings do not change from one problem to the next.

After this lesson, you should be able to

Evaluate formulas that use not, and, or, and implication.
Translate short rules into Boolean variables, literals, and clauses.
Find an assignment that satisfies a formula in conjunctive normal form.

2.1

A formula fixes the meaning of each combination

Let a mean that a student takes art, b mean biology, and c mean chemistry. Each variable receives one Boolean value. The expression a or b is true when either course is selected, including the case in which both are selected.

An implication such as c → b says that chemistry requires biology. It is false only when c is true and b is false. The equivalent clause not c or b is often easier for a SAT solver to use.

2.2

Clauses identify forbidden combinations

A literal is a variable or its negation. A clause joins literals with or and fails only when every literal is false. The clause not c or b therefore rules out one combination: chemistry selected and biology absent.

Conjunctive normal form, abbreviated CNF, joins clauses with and. Every clause must hold at the same time. This regular shape supports Boolean propagation and conflict analysis.

2.3

A model checks every clause

A satisfying assignment gives each variable a value and makes the whole formula true. Checking it is direct: evaluate every literal, then every clause, then the conjunction of clauses.

Unsat makes a universal claim about all assignments. A formula with three Boolean variables has eight assignments, so exhaustive checking is possible. Real SAT instances can contain millions of variables, which is why solvers need stronger search methods.

Worked example

Choose courses under three rules

Choose at least one of art or biology. Chemistry requires biology. Art and chemistry cannot both be selected.

Name variables
Use a, b, and c for art, biology, and chemistry.
Write clauses
The rules become (a or b), (not c or b), and (not a or not c).
Try an assignment
Set a = true, b = false, and c = false.
Check every clause
The clauses evaluate to true, true, and true. The assignment is a model.

Result. The course rules are sat. Selecting art alone is one model.

2.4

Check your understanding

Answer each question before opening the explanation.

1 When is the clause not c or b false?

It is false only when c is true and b is false.

2 Why must a CNF model satisfy every clause rather than most clauses?

CNF joins its clauses with and, so one false clause makes the complete formula false.

Concept wiki

Terms in this lesson

All concepts