Boolean Algebra |
Boolean Algebra
Values
Boolean algebra uses two values: true or false.
True is represented by the numeric value 1.
False is represented by the numeric value 0.
Variables
Boolean expressions contain variables that can represent either true(1) or false(0).
In this activity, Boolean expressions use the variables A, B, C and D.
Explanations relating the laws of Boolean algebra use the variables X, Y and Z.
The values 1 and 0 can also be used in Boolean Expressions.
Logical Operators
Logical operators can be used to perform operations between the Boolean variables
There is only one possible operation that can be performed on a single variable:
- NOT: generates the inverse of the value, changing true to false and false to true
Logical Operators for two variables
The standard logical operations on two variables that are used in this activity are:
- AND
- OR
- XOR
- NAND
- NOR
Expressions
Boolean expressions contain a combination of Boolean variables and logical operators.
There are rules that govern how a complex Boolean expression can be simplified (See Rules Tab).
Truth Tables
The result of a Boolean expression can be worked through using a truth table.
A truth table considers each possible set of values that the variables in a Boolean expression can take and works through the output.
There are four difference combinations of values for two variables with sixteen possible outcomes (See Truth Tables Tab).
There are eight difference combinations of values for three variables with 256 possible outcomes.
There are sixteen difference combinations of values for four variables with 65536 possible outcomes.
A AND B
True if both A and B are true
Boolean Expression
A · B
Logical Notation
A ∧ B
Truth Table for Q = A AND B
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
A OR B
True if either A or B is true
Boolean Expression
A + B
Logical Notation
A ∨ B
Truth Table for Q = A OR B
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
A XOR B (exclusive or)
True if either A or B is true but not both
Boolean Expression
A ⊕ B
Logical Notation
A ⊻ B
Truth Table for Q = A XOR B
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOT A
True if A is false and false if A is true
Boolean Expression
~ A
Logical Notation
¬ A
Truth Table for Q = NOT A
| A | Q |
| 0 | 1 |
| 1 | 0 |
A NOR B (not or)
True if (A OR B) is false
Boolean Expression
~ ( A + B )
Logical Notation
¬ ( A ∨ B )
Truth Table for Q = A NOR B
| A | B | Q |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NOR Definitions for the other logical operators
| NOT A | A NOR A | |
| A AND B | (A NOR A) NOR (B NOR B) | |
| A OR B | (A NOR B) NOR (A NOR B) | |
| A OR B | (A NOR B) NOR 0 | |
| A NAND B | ((A NORA ) NOR (B NORB ) ) NOR ((A NOR A) NOR (B NOR B)) | |
| A NAND B | ((A NOR A) NOR (B NOR B)) NOR 0 | |
| A XOR B | (( A NOR B ) NOR A ) NOR ( ( A NOR B ) NOR B) NOR (( A NOR B ) NOR A ) NOR ( ( A NOR B ) NOR B) | |
| A XOR B | (( A NOR B ) NOR A ) NOR ( ( A NOR B ) NOR B) NOR 0 |
A NAND B (not and)
True if (A AND B) is false
Boolean Expression
~ ( A · B )
Logical Notation
¬ ( A ∧ B )
Truth Table for Q = A NAND B
| A | B | Q |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND Definitions for the other logical operators
| NOT A | A NAND A | |
| A AND B | (A NAND B) NAND (A NAND B) | |
| A AND B | (A NAND B) NAND 1 | |
| A OR B | (A NAND A) NAND (B NAND B) | |
| A NOR B | ( ( A NAND A ) NAND ( B NAND B ) ) NAND ( ( A NAND A ) NAND ( B NAND B )) | |
| A NOR B | ( ( A NAND A ) NAND ( B NAND B ) ) NAND 1) | |
| A XOR B | ( ( A NAND B ) NAND A ) NAND ( ( A NAND B ) NAND B ) |
Truth Tables for Two Booleans Variables
0 | |||||||||||||||
|
A AND B | |||||||||||||||
|
A AND NOT B | |||||||||||||||
|
A | |||||||||||||||
|
NOT A AND B | |||||||||||||||
|
B | |||||||||||||||
|
A XOR B | |||||||||||||||
|
A OR B | |||||||||||||||
|
A NOR B | |||||||||||||||
|
NOT A XOR NOT B | |||||||||||||||
|
NOT B | |||||||||||||||
|
A OR NOT B | |||||||||||||||
|
NOT A | |||||||||||||||
|
NOT A OR B | |||||||||||||||
|
A NAND B | |||||||||||||||
|
1 | |||||||||||||||
|
Operator Priority
Boolean expressions contain logical operators and may also contain brackets.
Brackets
- Brackets take the highest priority in any Boolean expression.
- The results of the expressions in the brackets are determined first before calculating the result of logical operators between bracketed expressions.
- Brackets can be embedded within other brackets.
Operator Priority
- As with mathematical algebra that uses BIDMAS to order the prioity of each operator, the same principle can be applied to logical operators.
- This activity orders the priority of the logical operators, from highest to lowest, as follows
| Logical Operator | Boolean Expression | Priority |
|---|---|---|
| NOT | ~A · B | (~A) · B |
| AND | X · Y + X · Y ⊕ Z | (X · Y) + (X · Y) ⊕ Z |
| XOR | X ⊕ Y + Z | (X ⊕ Y) + Z |
| OR | A + B · C + D | A + (B · C) + D |
Expanding Brackets
Brackets are expanded using a similar method to mathematical algebra with AND equating to times and OR equating to plus.
| Boolean Expression | Expanded |
|---|---|
| A · (B + C) | = A · B + A · B |
| (A + B) · (C + D) | = A · C + A · D + B · C + B · D |
Rules for Simplifying Expressions
Rules and laws used when simplifying Boolean expressions.
| Boolean Expression | Simplified To | Law/Concept |
|---|---|---|
| A · 1 | A | Identity |
| A · 0 | 0 | Null |
| A + 1 | 1 | Null |
| A + 0 | A | Identity |
| A ⊕ 1 | ~A | Inverse |
| A ⊕ 0 | A | Identity |
| A · A | A | Idempotent |
| A · ~A | 0 | Inverse |
| A + A | A | Idempotent |
| A + ~A | 1 | Inverse |
| A ⊕ A | 0 | Inverse |
| A ⊕ ~A | 1 |
Laws for Simplifying Expressions
Rules and laws used when simplifying Boolean expressions.
| A + A · B | A | Absorption Law |
| A + B · C | (A + B) · (A + C) | Distributive law |
| A + ~A · B | (A + ~A) · (A + B) = A + B | Distributive and inverse |
| ~(A · B) | ~A + ~B | De Morgan's Law |
| ~(A + B) | ~A · ~B | De Morgan's Law |
| A ⊕ B | A · ~B + ~A · B | XOR Law |