Boolean Logic, also called Boolean Algebra, is the logic system used by computers. It was invented in the mid 1800s by a man named George Boole to serve the purpose of letting many things be written in the form of bits and bytes! Bits, or binary digits, are the digits found in the Binary System, the number system used by computers. There are only two binary digits-1 and 0.
In Boolean Logic, there is a set of gates. You can input different binary digits into the gate, and you will get a certain output determined by the nature of the gate. Let's take a look at three of the most important gates:
In the diagram above, the letters A and Q are variables. Just like in regular algebra, variables are used to represent a certain element. A represents the element that is being inputted into the NOT gate. Q represents the result after the operation denoted by the NOT gate has been calculated.
The NOT gate, often called an inverter, denotes that when any value A is inputted, its opposite will be outputted:
In the AND gate, two binary digits, A and B, are inputted. When A and B both go through the AND gate, the result (Q) will be 1 if and only if both A and B are equal to 1. Otherwise, Q will be equal to 0. Thus:
If A = 0 and B = 0, then Q = 0
If A = 0 and B = 1, then Q = 0
If A = 1 and B = 0, then Q = 0
If A = 1 and B = 1, then Q = 1
This is the OR gate. Like the AND gate, there are two binary digits being inputted into the OR gate, A and B. The OR gate denotes that when two values, A and B, are inputted, the result, Q, will be equal to 1 if either A, B, or both are equal to 1. Thus:
In addition to the AND, OR, and NOT gates, there are four more commonly used gates. The following four gates are merely different combinations or different variations of the AND, OR, and NOT gates:
NAND Gate (combination of And and NOT):
This is what the NAND gate looks like. As you can see, it resembles both the AND gate and the NOT gate. The NAND gate states that when two binary digits, A and B, are inputted, the result, Q, will equal 0 if both A and B are equal to 1. Otherwise, Q will be equal to 1. Thus:
The NOR gate is quite similar to the NAND gate in that it combines two gates. This time, the NOT and OR gates are put together. When two bits, A and B, are inputted into the NOR gate, the result, Q, will be 0 if A, B, or both A and B are equal to 1. Otherwise, Q will be 1. Thus:
In the XOR gate, you have two input values, A and B. If A or B (not both) is equal to 1, then Q is also equal to 1. However, if both A and B equals 1 or both A and B equals 0, then Q will be equal to 0. Thus:
The XNOR is very similar to the XOR gate. Basically, the XNOR gate dictates that for binary digits A and B, if A or B (not both) is equal to 1, then Q is equal to 0. If both A and B are equal to 1 or if both A and B are equal to 0, then Q is equal to 1. Thus:
So, you might ask, how in the world are these gates used in computers? Well, recall that computers use the Binary System. Well, using these gates, we can create logic systems called adders that are capable of carrying out binary addition.
Let's take a look at a simple adder:
You can perform this simple operation by using an AND gate, which, as you might recall, states that the result, Q is equal to 1 if and only if both the inputs, A and B, are equal to 1. In the addition problem, both A and B are equal to 0. Thus, Q will be equal to 0. This fits in perfectly with the AND gate.
Obviously, the AND gate won't fit here, because if we input a 0 and a 1 into an AND gate, we will get a 0 as the output. But, we can use a different gate, the XOR gate. Recall that the XOR gate states that if either A or B (and not both) is equal to 1, then the output will also be 1. As you can see, this fits perfectly in with the addition problem above!
(Remember, this is the Binary System, not the decimal system we use in our everyday lives!)
Well, as you can see, instead of having just 1 bit for an output like all of the other addition problems, you need two bits for the output. The 1 in the output of this equation is called a "carry." Carries are very important in more complex addition problems, which can be represented by using full binary adders.
Now, we shall talk about full binary adders. A typical full binary adder looks like this:
The CO and CI represent the carries. This will be clearer if we take a look at a 4-bit full adder, which would be four full binary adders connected to each other:
Now, let's break this down. Each binary adder represents an addition problem. A and B are the two values that are being added, and Q is the output. So, what about the carries? Well, CO represents carry-out, and CI represents carry-in. Let's pretend that in the first binary adder, A and B both equal 1. So, when you add 1 and 1 in the Binary System, you will get 10. Thus, it would make sense for Q to equal 10. However, in full binary adders, the carry is not outputted as Q, but is instead fed into the next adder. Thus, the 1 in the previous example would not be outputted as part of Q (instead, Q would be equal to just the 0), but would instead be part of the input in the next adder. Thus, in this 4-bit full adder, you input a total of 8 bits (4 As and 4Bs), and for the output you will get 4 bits (4 Qs-the carries do not become part of the actual output).
You can connect any number of adders to represent a wide array of mathematical problems!Flip-Flops:
Now, we shall look at flip-flops. Flip-flops describe another way to use the logic gates described above. This time, we can use these gates to create memory for a computer!
Basically, flip-flops are created when you arrange the logic gates in a certain
way so that the output value will be fed back into the input. This is the
very core of computer memories. Let's take a look at a simple example. Pretend
that you have two not gates connected like so:
We know that if we input a 1, then the 1 will always remain a 1, and if we input a 0, it will likewise remain a 0. We can take this idea and create even more complicated flip-flops! Basically, in a flip-flop, the output depends on the sequence of the previous inputs!
These seemingly simple logic gates, adders, and flip-flops can be combined
to create gates so complex that they can form the basis of a whole computer