Revision as of 04:03, 29 November 2015

Boolean algebra (or less commonly symbolic logic) is a branch algebra that deals with only two logic values - 0 (corresponding to false) and 1 (corresponding to true).

Today, Boolean algebra is the primary mathematical tool used in designing modern digital systems. Switching functions are described using Boolean algebra since they deal with two discrete states - ON and OFF (or 1 and 0). Those functions are in turn implemented via transistors which act as switches, a natural implementation for representing Boolean algebra operations. Once primitive Boolean operation circuits such as NOT, AND, and OR gates are implemented, any conceivable system of logic can be implemented using them like Lego pieces.

Variables

Main articles: Boolean Variables and boolean data type

Boolean algebra uses variables just like normal algebra. Those variables can only have one of two values - either a 0 or a 1. Variable are commonly represented as a single alphabet letter. While there is no one acceptable convention, a it's not uncommon to see letters such as used for inputs and for output. That's also the convention used on WikiChip. Sometimes it's desired to represent the negated (opposite) value of a variable, that's often done with a bar or a tick (prime) above or next to the letter, for example or although other notations exist. is read "not A", regardless of notation.

Operations & Truth tables

Main articles: Boolean Operations and truth table

Boolean algebra has a set of operations that can be performed on Boolean values. The three common Boolean operators are AND, OR, and NOT. Understanding those operators can better be done by examining their behavior via tool called a truth table. truth tables is a table that lists all possible input values and their respective output values. Truth tables are an excellent way of seeing the relationships between input values and given Boolean expressions.

AND operator

Main article: conjunction

The Boolean operator AND is usually represented by either , , or no symbol at all: for example "", "", and "" are all equivalent and are read "A AND B". The behavior of this operator is shown in the truth table on the right. The result of "A AND B" is true if both A and B are true; otherwise the result is false. This expression is also called a Boolean product.

For example, suppose we have the function

Or

OR operator

Main article: disjunction

The Boolean operator OR is usually represented by or operators. For example "" and "". The expression is read "A or B". The result of "A OR B" is true if either A is true or B is true; otherwise the result is false. This expression is also called a Boolean sum.

For example, suppose we have the function

Or

NOT operator

Main article: negation

The Boolean operator NOT is represented by many notations, the three most popular ones are "", "", and "". Note that unlike the AND and OR operators, the NOT operator is a unary operator and is thus drawn above or on the side of the variable. The expression is read "not A". The truth table for the NOT operator is shown on the right. The result of the NOT operator is true if A is false, otherwise the result is true. This expression is called a Boolean complement.

For example, suppose we have the function

Or

Order of operations

Main article: Order of Operations

So far we've made it simple by explicitly using parenthesis in all of our examples to indicate a certain part of the expression is evaluated before another part. The order of operations of a Boolean expression is very important to obtain correct result. For example consider the function for input . Does it mean ? or does it mean ? Same expression, different results. It turns out the the correct order is (and ). In Boolean expressions, the NOT operator has the highest precedence, followed by AND, then OR.

For example,

and

Laws

Main article: Boolean Algebra Laws

Boolean algebra is govern by a set of special laws or identities that say what kind of Boolean expression manipulations can be done. Many of those laws are common to both Boolean algebra and ordinary algebra. Using those laws, equations can be converted into different forms. One particular transformation known as minimization plays a crucial role in the design of logic circuits. One last thing to note before we get to the actual laws is that Boolean algebra identities come in pairs. This is known as duality principle and it is covered in much more detail later on.

It's interesting to note that it's easy to see the divergence between Boolean algebra and ordinary algebra from those laws. For example consider . From Dominance Law we know the answer is . This is clearly not true for ordinary algebra where . Likewise from the Absorption Law we know that while in ordinary algebra this is not true either.

Laws explanation

This section is empty; you can help add the missing info by editing this page.

Minimization

This section is empty; you can help add the missing info by editing this page.

Complementary Function

This section is empty; you can help add the missing info by editing this page.

Canonical Form

This section is empty; you can help add the missing info by editing this page.