Boolean Algebra - Overview
Boolean Algebra is a branch of mathematics that deals with several logical operations on the variables that can have only two values - 0 and 1. Now, why this is so important for computer science? because these values, 0s and 1s, that are called bits (binary digits), are the fundamental building blocks of computers and associated operations of it.
Following are the logical operations:
All other operations are made up of these 3 fundamental logical operations. These operations are performed by their corresponding operators
Why is this called Boolean? - There was a mathematician named George Boole who first introduced this concept and so this algebra was named after him.
There are following basic logical operations, before that, let us assume we have two vaiables - a and b. Both can have possibly two values only - 0 and 1.
An operation requires the combination operator and operands. Keeping this in mind, the following operations can be applied to the operands a and b:
| Operation | Operator | Representation |
|---|---|---|
| Conjunction | AND | a ∧ b |
| Disjunction | OR | a ∨ b |
| Negation | NOT | ¬ a |
The Truth Table show the possible values and combinations of operands and the values that we can get if a logical operation is performed on them. To show how a truth table looks like, here is the truth table for the logical operation - conjunction:
| a | b | a ∧ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
For disjunction:
| a | b | a ∨ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
For negation:
| a | ¬ a |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND and OR requires two operands and NOT requires one operand.
Now, using these operations, one can construct logics. What are logics? It is a study of consequences. Obviously it will be way too much hard to create bigger logics but they are the fundamental building blocks of logics, computer logics and digital designs, like different components in computer, CPU. Boolean Algebra is important because it gives you a very fundamental idea as how a digital computer works in its lowest level, at the hardware level and how the bits interact with the computer. Combining these boolean operations creates up the bigger digital design and eventually a whole computer architecture.
Let us understand with a small example. Let's crete a small boolean expression, a small logic for the following problem:
You are in a selection process for a job. You want to select only those candidates who fulfils the following criteria:
Let's come up with a solution. First, let us assume that variable
c refers to whether candidate has a computer science degree or not,
k refers to whether candidate knows C++
j refers to whether candidate knows Java
r will be having the result if the candidate is selected or not
The values will be 0 and 1, 0 for no (false) and 1 for yes (true).
Suppose a candidate has following values to these variables,
c = 1, candidate has a computer science degree,
k = 1, candidate knows C++
j = 0, candidate doesn't know Java
then, the result will be
r = 1, candidate is selected
Let us take another candidate who has following values to these variables,
c = 0, candidate doesn't have a computer science degree,
k = 0, candidate don't know C++
j = 1, candidate know Java
then, the result will be
r = 0, candidate is not selected
The logical boolean expression will be:
r = c ∧ (k ∨ j)
Try to create a truth table for this expression of all possible values :)
AND
if a = b = 1, then
a ∧ b = 1, else
a ∧ b = 0
The conjunction value will only be 1 when both operands have value 1, if any of them have value 0, then the result will be 0.
OR
if a = b = 0, then
a ∨ b = 0, else
a ∨ b = 1
The disjunction value will only be 0 when both operands have value 0, if any of them have value 1, then the result will be 1.
NOT
if a = 0, then
¬ a = 1,
if a = 1, then
¬ a = 0,
The negation will be opposite to the operand value, if it is 0, then 1 else if it is 1, then 0.
This is so far the basics of Boolean Algebra, enough to get you started. There are other operations like XOR, XAND, XNOT, NAND, NOR, etc. and some laws like duality principle, moore"s law, etc. that will be covered in other post
© progshala.in