CS Fundamentals III: Boolean Algebra & Logic Gates
Hi!
This post is the third in the CS Fundamentals series, todays topic is another idea critical to the inner workings of all modern computer systems - Boolean algebra. Boolean algebra is similar to the algebra we all learned in maths at school, but the variables (X,Y,Z etc) can only take two values - true or false. In the “regular” algebra that we learned at school these variables could take the value of any number.
Contents
- What is boolean algebra?
- What is a logic gate?
- Boolean operators & equivalent logic gates
- Boolean algebra laws
- Boolean algebra expressions
- Conclusion
What is Boolean algebra?
Boolean algebra is a part of an area of maths known as discrete mathematics, this area of maths deals with discrete variables opposed to continuous variables. If a variable is discrete it can only take a value from a set of values, if a variable is continuous is can take on any value. The algebra we all think of when we hear the word algebra operates using continuous variables.
To put it simply:
- Boolean algebra - X,Y,Z can only be TRUE or FALSE (this corresponds to the 1 and 0 of binary).
- Regular algebra - X,Y,Z can be any number.
Also on top of this Boolean algebra has its own set of operators, it doesn’t use + - / *. It uses AND, OR and NOT operators.
If you’ve noticed the capitalization of the word Boolean that is because Boolean algebra was first introduced in 1847 by a mathematician named George Boole, over the following years the idea was refined and perfected by various other mathematicians.
Boolean algebra dictates the rules by which we can build circuits. This link was first fully realized in the 1930’s by Claude Elwood Shannon, a well known mathematician and electronic engineer. In his masters thesis he showed that electronic circuits made up of switches (think back to the previous article and how transistors that make up CPUs are tiny electronic switches) could solve all problems that Boolean algebra could solve. He showed this through the use of an abstraction called a logic gate.
What is a logic gate?
A logic gate is simply a device which implements a Boolean operator. This is how Claude Elwood Shannon combined the theoretical area of maths known as Boolean algebra with the physical reality of electronic circuitry - a logic gate can be made up of electrical switches or it can be entirely theoretical. It is just a way of modeling the complexities of Boolean algebra in such a way that it can be translated into the real world, and therefore be used to create real circuits.
A logic gate takes in inputs that are either TRUE or FALSE, and outputs a value either TRUE or FALSE. In a computer this would be 1 or 0, and in a circuit this would be voltage ON or OFF. Can you start to see how all these things are working together?
We can represent anything in a computer system using binary, we can create circuits that can manipulate these representations through the use of logic gates, and the logic gates themselves are a manifestation of Boolean algebra - the algebra of discrete variables. The 1 and 0 of binary are the discrete variables!
Interesting fact - Leibniz (the other inventor of calculus) studied the binary number system over 100 years before Boole came up with Boolean algebra, and he predicted its use in combining arithmetic and logic in the way that modern computers do. He was a genius who started university at 14 and graduated at 16.
Boolean operators & equivalent logic gates
So we know now that Boolean algebra is the algebra of two discrete values, typically written as TRUE and FALSE. We also know that the operators in this algebra are AND, OR and NOT. Furthermore we know that a logic gate is just a representation of these operators, this allows for the creation of electronic circuits that follow the rules of Boolean algebra. Lets look at the basic operators and their equivalent logic gates.
Basic operators
We can describe the operators in several different ways. I will first write what the operator does and then show how we can write it in a statement. Then we will derive a truth table. Finally we will look at the shape of its equivalent logic gate and how you would write it in using proper mathematical notation.
AND
The AND operator will return TRUE if and only if both of the input values are also TRUE.
Consider the statement:
“If I have money AND I have handed in my coursework, then I will go for a pint.”
We can represent this statement in Boolean algebra by assigning variables:
- x - Do I have money or not?
- y - Have I handed in my coursework?
- z - Will I go for a pint?
Then the entire statement is:
x AND y = z
Now lets look at the value of the statement z given each variable, given that we know both must be TRUE to provide a TRUE result.
- x = FALSE y = FALSE - I have no money, I haven’t handed in my coursework, I’m not going for a pint.
- x = FALSE y = TRUE - I have no money, I have handed in my coursework, I’m not going for a pint.
- x = TRUE y = FALSE - I have money, I haven’t handed in my coursework, I’m not going for a pint.
- x = TRUE y = TRUE - I have money, I have handed in my coursework, I’m going for a pint. - The ideal scenario.
This is the essence of a truth table. It shows you the truth value of the output, in this case z, given the truth values of the inputs. Check the truth table for the AND operator:
When we represent the AND operator as a logic gate we draw it like this:
When we use the AND operator in an algebraic expression it can be written like this:
OR
The OR operator will return TRUE if any input is TRUE.
Consider the statement:
“If I have money OR I have handed in my coursework, then I will go for a pint.”
We can use the same representations of our variables as we did for the AND operator.
Then the entire statement is:
x OR y = z
Lets work through the statement in the same way, given that we know only one variable needs to be TRUE to provide a TRUE result.
- x = FALSE y = FALSE - I have no money, I haven’t handed in my coursework, I’m not going for a pint.
- x = FALSE y = TRUE - I have no money, I have handed in my coursework, I’m going for a pint.
- x = TRUE y = FALSE - I have money, I haven’t handed in my coursework, I’m going for a pint.
- x = TRUE y = TRUE - I have money, I have handed in my coursework, I’m going for a pint. - The more realistic scenario.
Here is the truth table for the OR operator:
When we represent the OR operator as a logic gate we draw it like this:
When we use the OR operator in an algebraic expression it can be written like this:
NOT
The NOT operator is slightly different from the previous gates. It only takes 1 input, and inverts it. This is why it is sometimes called an inverter or a negation.
Consider the statement:
“I am going for a pint.”
We can represent this single statement as a single variable x.
- If x is currently TRUE, then NOT x would be FALSE.
- If x is currently FALSE, then NOT x would be TRUE.
Here is the truth table for the NOT operator:
When we represent the NOT operator as a logic gate we draw it like this:
When we use the NOT operator in an algebraic expression it can be written like this:
Combined operators
The three previous operators are the building blocks for everything else in Boolean algebra and we can combine them to do different things. There are a few common combinations of these three which are so common they get their own names.
XOR
The XOR operator, also called exclusive-OR, will return TRUE if and only if exactly 1 input is TRUE.
Here is the truth table for the XOR operator:
When we represent the XOR operator as a logic gate we draw it like this:
When we use the XOR operator in an algebraic expression it can be written like this:
NAND
The NAND operator, also called NOT-AND, is the opposite of the AND gate.
Here is the truth table for the NAND operator:
When we represent the NAND operator as a logic gate we draw it like this:
When we use the NAND operator in an algebraic expression it can be written like this:
NOR
The NOR operator, also called NOT-OR, is the opposite of the OR gate.
Here is the truth table for the NOR operator:
When we represent the NOR operator as a logic gate we draw it like this:
When we use the NOR operator in an algebraic expression it can be written like this:
Cheat-sheet
As a reference here is all the information from the this section in one image:
Simple example
To test our understanding of what we have covered so far lets look at a simple combination of logic gates and calculate the output value for a given set of input values.
Using the input values of v = TRUE , w = FALSE, x = FALSE, y = TRUE.
- v . w = T . F = F
- x + y = F + T = T
- (v . w) + (x + y) = F + T = T
- z = T
Boolean algebra laws
Hopefully we have now developed a rudimentary understanding of what Boolean algebra is, and how it relates to logic gates and circuits. Boolean algebra has several laws which helps us to manipulate algebraic expressions to more easily calculate the values of complex expressions. These might seem confusing at first, to really gain an understanding try constructing a truth table of the equivalent expressions.
Commutativity
The law of commutativity states that the order of the terms for an expression can be changed and the end will result will be no different.
Identity
The law of identity shows how expressions behave when one of the terms is fixed.
Complement
The law of complement shows the relationship between a variable and its negation. For example a variable OR its negation will always be true and a variable AND its negation will always be false.
Idempotent
The law of idempotent shows how an expression behaves when a variable is repeated. It can be simplified to itself.
Double negation
The law of double negation shows that when a variable is negated twice then the negation is negated, effectively meaning the variable is just equal to itself.
Associativity
The law of associativity shows the different ways that like terms can be grouped together and the end result remain the same.
Distributivity
The law of distributivity is similar to bracket expansion in traditional multiplication. See how the outer expression is effectively applied to the variables in the brackets, the operator in the brackets becomes the operator between the new sets of two brackets.
de Morgans’
de Morgans’ law is a special law that shows how AND and OR can be made to be equivalent through the use of the negation operator. This idea will be covered in more technical posts about propositional logic, in propositional logic AND and OR are called conjunction and injunction respectively. Essentially we can change an AND to an OR or vice-versa through the manipulation of negation operations.
Questions
Now we know as much about Boolean algebra as we need to look at more complex examples. We can take a Boolean expression and create a logic gate diagram, take a truth table and fill it out, or take a logic gate diagram and create a truth table. All these things are interchangeable ways of understanding the abstract concept of Boolean algebra.
Question 1
Given the Boolean expression below, construct a logic gate diagram and determine the output when inputs equal to x = FALSE, y = TRUE by constructing a truth table.
Click for answer.
Does this truth table look familiar? It is the XOR operation. This is one way that XOR can be constructed from the basic operators!
Question 2
Given the logic gate diagram, work out the corresponding Boolean expression and simplify.
Click for answer.
Question 3
Complete the given truth table, then draw the logic gate diagram.
Click for answer.
Conclusion
This post
Let’s summarize what we have covered in this post as it is much more abstract and technical then the previous posts in this series.
- We learned that Boolean algebra is a type of algebra that uses discrete variables (TRUE, FALSE) and its own operators (AND, OR, NOT).
- We learned a logic gate is an abstraction that represents a Boolean operation, it can be used abstractly in diagrams or be physically implemented using switches (such as transistors)
- We learned how each basic operator works, its truth table, its logic gate symbol and its algebraic notation
- We learned about combined operators that can be made from AND, OR, NOT operators
- We learned about several “Laws of Boolean algebra” which allow us to manipulate and simplify Boolean algebra, this can help us reduce the size of circuits to the minimum required number of logic gates
- We practiced three difficult questions
A lot to take in for one post, but understanding Boolean algebra is fundamental to understanding computer science!
Next post
The next post will be a change of track from the binary and Boolean algebra that we have been studying. We will look at a more complex version of Computer Architecture than the stored program computer mentioned in the first post.
Thanks for checking out the blog,
Max Sargent