Boolean Logic
A Boolean quantity has only two values. Strictly speaking, the two values are "true" and "false," but, more generally (and more usefully to engineering), they can be used to describe any information with only two values. That information could have two values because the information is inherently discrete (a door is locked or it isn't, an airplane's wheels are on the ground or they aren't), or because an an analog value has been discretized into two ranges (a temperature is above or below 50°, there is more or less than 25,000 lux of sunlight shining on the lawn).
Some nomenclature: The word "quantity" to describe a measurable attribute is awkward if you're not a physicist or mathematician. The word "variable" would work well except that it is burdened by its connection with software, and this is not a software course. So, throughout this text, the word "signal" will be used to describe something that carries information.
A note on analog ranges: the paragraph above said that a Boolean signal might represent a temperature being above or below 50°. Many students ask "What if it's equal to 50°? Does 'true' mean ≥50° or strictly greater than?"
The answer is that it doesn't matter. It is not possible to create two things that behave differently based on analog information being compared with '>' vs. '≥' (or '<' vs. ≤), so the distinction is meaningless.
A system that operates on Boolean signals is often called a digital system, and so Boolean signals are often also called digital signals. They are sometimes also called binary signals, but that word has numerical connotations, so Boolean signals and digital systems are the most appropriate terms when talking about this concept in general.
To simplify discussion, design, and documentation of digital systems, the symbols "0" and "1" are very often used to stand in for the two values of a Boolean signal, because 0 and 1 are compact and general.
Important! The symbols '0' and '1' are useful for brevity and for simplification (so that you can focus on the logic instead of the specific implementation), but always remember that they represent something else. "1" could mean that a switch is closed, or a light is on, or the voltage is higher than a threshold, or that a goose is on your lawn -- we (as engineers) just use "0" and "1" because they're easy to write and easy to think about. We also often think in terms of "true" and "false" or "active" and "inactive" -- these are all simply tools to help us think about complicated systems.
Very importantly, a signal can be used to represent any information to us regardless of its physical manifestation. Just like how, in the analog realm, the speed of a car can be represented by the angle of a needle, or the location of the top of a column of mercury can represent air pressure, a digital signal implemented as voltage on a wire can represent something like whether or not a person is seated or whether or not you ate something in the last hour. Also, in this class, the physical parameter used to represent information will almost always be voltage, but it could be pneumatic pressure, light intensity, or any other physical parameter.
Truth Tables
As described in the previous section, one of the most common purposes that we design systems for is to manipulate information -- to take some input information and to change it to something more useful or desireable. To begin the design of such a system, we have to describe how the output information depends on the input information.
Since this is a digital system design course, all signals can only have two values. If we wanted to design a system that has a single input (here named 'A' for simplicity), it is very easy to list every possible value that that input can have:
| A |
|---|
| 0 |
| 1 |
As the engineer designing this system, we can then create a new signal -- let's call it ‘X’ -- and we can define what value it should have for each value of A. For example, X might have the same value as A:
| Input | Output |
|---|---|
| A | X |
| 0 | 0 |
| 1 | 1 |
This type of table is called a truth table. On the left side of a truth table is the input (this one just has one input, but there can be multiple inputs), and on the right side of the table is the output (again, one here, but there can be more than one output).
We (as the engineers designing this system) can make other output signals, ‘Y’ and ‘Z’, with different values for each value of A. Here, Y is always 0 (which is perfectly valid, if not very interesting), and Z is the opposite of A.
| Input | Outputs | ||
|---|---|---|---|
| A | X | Y | Z |
| 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
A truth table defines the output values for every possible combination of input values. When there is only one input, that's trivial, but each additional input doubles the number of rows in the table, because the existing rows need to be listed with the new input being 0 and then listed again with the new input being '1'. That means that with N inputs, a truth table will have 2^N rows.
Important concept: An output that can be defined for every combination of input values is called combinational, and logic with this property is called combinational logic. You can determine if an output is combinational by asking yourself "if I know what the current values of the inputs are, do I know what the value of the output is?" If the anwer is yes, it's combinational. An easy counter-example is a calculator: the buttons are the inputs to the system, but just knowing that someone is holding down the = button doesn't tell you what is displayed on the screen.
Here is every possible combination of two inputs named A and B:
| Inputs | |
|---|---|
| A | B |
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 1 | 1 |
To then define an output signal with values based on those inputs, we have to define its value for every combination of input values. For example:
| Inputs | Output | |
|---|---|---|
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean Functions
A truth table is one way to describe a Boolean function. Just like a mathematical function, a Boolean function takes inputs and provides an output. (If a truth table has multiple outputs, it is describing multiple Boolean functions; we just reuse the input side of the table to save space and to better display related outputs.)
Truth tables quickly become very cumbersome though -- four inputs requires 16 rows to list all possible combinations of input values, five inputs would need 32 rows, and just eight inputs would require 256 rows. A more concise description of behavior is often needed, and like in mathematics, that is done by defining a few simple operations that allow us to write expressions.
If an output is the opposite of an input, that is called logical inversion, or the NOT logic function.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
If all of the inputs must be true for the output to be true, that is logical AND. The truth table for the AND function for two inputs is
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
If any of the inputs being true makes the output true, that is logical OR. The truth table for the OR function for two inputs is
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Those simple functions can then be combined to create more complex functions; for example (NOT A) AND (B OR C). Just like with a mathematical expressions, to evaluate a Boolean expression, intermediate steps can be evaluated before evaluating the final result.
| Inputs | Intermediate | Output | |||
|---|---|---|---|---|---|
| A | B | C | NOT A | B OR C | AND |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 |
There is one more named function which, although less common, needs to be introduced. It is the "exclusive OR" function, XOR, which can be described as "one or the other but not both" for two inputs, or, more generally, as "the number of true inputs is odd."
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Boolean Algebraic Expressions
While Boolean expressions written with words (AND, OR, NOT) is more compact than a truth table, one more step can make things even cleaner: replacing the operations with symbols. The symbols used for Boolean logic expressions are
| Word | Symbol |
|---|---|
| NOT A | A (overbar) |
| A AND B | A · B (middle dot) |
| A OR B | A + B (plus sign) |
| A XOR B | A ⊕ B (circled plus sign) |
Bars can be placed over subexpressions to invert the result of that section; for example A+B is NOT(A OR B).
Some notes about reading Boolean expressions:
- The overbar can either be read as "NOT" or by post-fixing the word "bar"; i.e. A can be read either as "not A" or as "A bar".
- Even though the symbols · and + are the same as used for multiplication and addition, they are always read as "AND" and "OR", never "times" or "plus".
- Defining a signal is often done with an "=" (e.g. Y = A · B), but the "=" symbol should be read as "is defined as" or "is" (e.g. "Y is A AND B") because it is a definition, not an equality. Sometimes you will see ":=" used instead of just "=" to emphasize this point.
The order of operations is important when evaluating Boolean expressions (just like it is in math). The order of operations for Boolean algebraic expressions is:
- NOT
- AND
- OR
As in other mathematics, parentheses can be used to force a certain order of operations. Also note that even though NOT has the highest priority, any subexpression under an overbar must be evaluated before the result of that can be inverted. Effectively, the bar creates implied parentheses around everything underneath it.
Let's evaluate a Boolean expression to create a truth table:
RUN = ON·ERROR+HAZARD
Note: if speaking out loud, this expression could be said as
- "RUN is ON and not ERROR or HAZARD" (though that can be ambiguous about what the NOT affects unless you emphasize the order of operations)
- "RUN is ON and ERROR or HAZARD bar" (also ambiguous about what the 'bar' covers unless you convey order of operations)
Thankfully, the written expression is always unambiguous! Try evaluating it yourself and then comparing with the solution:
| ON | ERROR | HAZARD | RUN |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Summary
- Boolean signals can only have two values.
- In a real system, the two values represent some information, but when only considering the logic, that is abstracted away and the signals often take values of '1'/'true' and '0'/'false'.
- Boolean functions can be defined that take one or more inputs and produce an output.
- Since Boolean signals can each only have two values, there is a finite number of combinations of all inputs: 2^N, where N is the number of inputs.
- All combinations of inputs can be listed along with the output of a Boolean function. This is called a truth table.
- Boolean functions can also be described using Boolean expressions, which use symbols to represent the three fundamental Boolean operations: AND, OR, and NOT. (XOR is another one, but it is less-frequently used)
- An output that can be fully defined for each combination of input values is combinational.
- You should be able to fill in a truth table for any given Boolean expression. Going the other way will be the topic of a later section.