Boolean Algebra
Background[edit]
The branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. It is a formal description of logical relations. It was introduced by George Boole in his first book The Mathematical Analysis of Logic in 1847.
Alternative names for true and false:
false | true |
---|---|
no | yes |
0 | 1 |
F | T |
Basic Operations[edit]
- AND, formally termed conjunction and denoted by
- OR, formally termed disjunction and denoted by
- NOT, formally termed negation, and denoted by
There are also several "shortcut" notations that we can use for more succinct expressions:
- conjunction may be written as multiplication, i.e. or, more simply,
- disjunction may be written as addition, i.e.
- negation may be written with a bar above the variable, i.e.
All Boolean operations can be expressed through a composition of these basic operations.
Secondary Operations[edit]
- EQUAL, formally termed equivalence and denoted by
- IMPLY, formally termed material implication and denoted by
- XOR, formally termed exclusive disjunction and denoted by , , ,
- Why is one of the symbols used for exclusive disjunction ?
Order of Operations[edit]
Expressions with multiple operators are evaluated from left to right, respecting the operator precedence as follows:
- (NOT) has the highest priority, followed by
- (AND)
- (OR)
- (IMPLY)
- , , (XOR), , (EQUIV)
As always, parentheses may be used to both emphasize and override the order of operations.
For clarification, here are several examples of equivalent expressions:
Without Parentheses | With Parentheses |
---|---|
It is important to note that the precedence list above, while generally agreed upon, is not implemented by all computer programming languages. It's important to pay close attention to the rules of each language, or, better yet, use parentheses to avoid ambiguity.
Truth Tables[edit]
Truth tables provide us with a straightforward means to specify the required output(s) for the specified input(s), in table form. On the left-hand side of the table we enumerate the input(s) and on the right-hand side of the table we specify the output(s). Assuming that we have inputs we may label each input as . The value of the inputs on any given row, may be referred to as an input tuple. Likewise, assuming that we have outputs we may label each output as , and the value of these outputs on any given row may be referred to as an output tuple. The number of rows in any such table is given by the formula . When there is a single output, we can formalize the relationship as
Why is the formula for determining the number of rows in a truth table related only to the number of inputs, and why is the formula ?
Note that for convenience we sometimes label inputs as A, B, C, etc. rather than etc. and do the same for outputs, often beginning with the letter Q.
When writing truth tables, it is very helpful to always write them in the same order. This helps in reading and memorizing the tables because we can simply memorize the output column(s), because the input columns will always be the same. For example, consider the AND truth table:
x | y | |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Rather than memorizing the entire table, we can just memorize the output column, i.e. 0 0 0 1. And, in most cases, we really only need to memorize the exceptional cases.
There are possible single-output Boolean functions that can be defined over inputs. These are enumerated, with explanations, in the following table.
Function Name | Boolean Algebraic Formula | Truth Table | Explanation | ||||
---|---|---|---|---|---|---|---|
x | 0 | 0 | 1 | 1 | |||
y | 0 | 1 | 0 | 1 | |||
Contradiction | 0 | 0 | 0 | 0 | 0 | Always false | |
AND | 0 | 0 | 0 | 1 | x and y are true | ||
AND NOT | 0 | 0 | 1 | 0 | x is true and y is false | ||
0 | 0 | 1 | 1 | x is true, y is irrelevant | |||
NOT AND | 0 | 1 | 0 | 0 | x is false and y is true | ||
0 | 1 | 0 | 1 | y is true, x is irrelevant | |||
XOR | 0 | 1 | 1 | 0 | x is true or y is true but both are not true x is different than y | ||
OR | 0 | 1 | 1 | 1 | Either x or y is true | ||
NOR | 1 | 0 | 0 | 0 | Neither x nor y is true | ||
EQUIVALENCE | 1 | 0 | 0 | 1 | x is the same as y | ||
NOT | 1 | 0 | 1 | 0 | y is false, x is irrelevant | ||
IMPLYs | 1 | 0 | 1 | 1 | x is true or y is false | ||
NOT | 1 | 1 | 0 | 0 | x is false, y is irrelevant | ||
IMPLYs | 1 | 1 | 0 | 1 | y is true or x is false | ||
NAND | 1 | 1 | 1 | 0 | x and y are not both true | ||
Tautology | 1 | 1 | 1 | 1 | 1 | Always true |
De Morgan's Laws[edit]
De Morgan's Laws provide a helpful formula to obtain the same truth table of:
- an AND operation by using negation and an OR operation, or
- an OR operation by using negation and an AND operation
The Laws are:
References[edit]
- Boolean Algebra (Wikipedia)
- De Morgan's Laws (Wikipedia)
- Logic Gates (Wikipedia)
- Truth Table (Wikipedia)
- Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.