Boolean logic
Boolean formula
An expression built from Boolean variables and logical connectives.
Definition
Boolean formula
A Boolean formula evaluates to true or false after its variables receive Boolean values.
The same formula can be true under one assignment and false under another. SAT asks whether at least one assignment makes it true.
01
Example
(a or b) and not a is true when a is false and b is true.
02
Important distinction
An arithmetic comparison can produce a Boolean result, but SMT retains the arithmetic structure instead of treating it as a plain Boolean variable.
After reading this article, you should be able to
- Define Boolean formula in the sense used on this site.
- Find an assignment that makes a small Boolean formula true.