Boolean algebra

Introduction

Boolean algebra is a specialized algebraic system that deals with boolean values, i.e. values that are either true or false. It forms part of a system called boolean logic^wp, but we will discuss it here as part of a course on digital electronics.

Boolean algebra describes logical and sets operations. A logical operation might be for example: "I have flour and water, I can make dough". In a case where I have flour and water, this statement is true. If one of the elements is not true then it is clearly false.
Another might be: "I have eggs or bacon, I have food" In a case where I had eggs but not bacon, or if I had only bacon, or if I had eggs and bacon, the statement I have food would be true. Only if I did not have eggs nor bacon would "I have food" be false.

Boolean Algebra works like this. One creates statements that are true only if all their component statements are true.

Now, taking the first example lets replace flour with a letter representative of it: F, water with W, and dough with D. In order to write it out, we need a symbol for "and". The symbol for "and" in boolean algebra is $\land$.
Therefore, bringing the above together, "I have flour and water, I can make dough" could be described: $F\land W=D$

Symbols

We now have the concept of symbols that can be true and false, and symbols describing logic. Lets have a look at these logic operations:

• $\land$ Signifies a logical AND.
• $\lor$ Signifies a logical OR.
• $\lnot$ Signifies a logical NOT.
• $\rightarrow$ Signifies logical implication.

To add a bit of confusion, engineers often use + for OR and a multiply sign, x or * for AND. Some use a line above a symbol or expression to signify NOT, whereas others use the symbol ! after a term, or the symbol ~ before a term, to signify NOT. Examples:

• q = a*b means if a AND b is true, q is true
• q = a+b means if either a OR b is true, q is true
• q = a! means if a is true, q is false. If a is false, q is true (i.e., q is the opposite of a)

Operations, One by one:

• $\land$ signifies AND. I like to remember this by its similarity to an 'n'.

AND describes a situation where the statement is true if and only if the parts on its left and its right are true.

• $\lor$ signifies OR.

OR describes a situation where the statement is true if at least one of the parts on its left or its right are true. (Note that if both a and b are true, a+b is still true)

• $\lnot$ signifies NOT.

NOT inverts the symbol or bracketed expression following it. So if A is true and I say B = $\lnot$A then B is false.

• $\rightarrow$ signifies implication.

Implication means that if the part on the left is true, then the part on the right is true. It does not, however, say anything meaningful if the part on the left is false, for example, "If apples and oranges exist, then something exists" is certainly true, as apples and oranges exist, and something exists, but "If apples exist but oranges do not, then something exists" is also true, although oranges do exist, making "apples exist but oranges do not" false.

Truth Tables:

A truth table is a mathematical table which describes the output of a logical function in terms of its inputs for all combinations of different inputs.

$\lor$ OR Examining equation: $A\lor B=X$ Where each row has a different combination of A and B, and the result value X A B X True True True True False True False True True False False False A B x

$\land$ AND Examining equation: $A\land B=X$ Where each row has a different combination of A and B, and the result value X A B X True True True True False False False True False False False False A B x

Rules and Syntax

We now know the symbols usable in boolean algebra, and what they mean, and have seen a few basic examples. Now let's have a look at rules and syntax:

Combining Operations

So two elements contributing to one result is all very well, but what if I consider bacon and eggs and Cheese food?
Elements can simply be chained together by putting in more operations. So the above would be:
$Bacon\land Eggs\land Cheese$
But what about if you have both OR and AND operations present? In order to clearly and unambiguously communicate our equation, we have to use parentheses(brackets). Bracketed expressions are solved from the innermost brackets first. For example:
If I only consider only Bacon AND Eggs a meal, but cheese is also a meal on its own I would write:
${\text{I have }}((Bacon\land Eggs)\lor Cheese)={\text{I have a meal}}$
If I only consider Bacon AND Eggs, or Bacon AND Cheese a meal but anyone item alone, or egg and cheese not to be a proper meal I would write:
${\text{I have }}(Bacon\land (Eggs\lor Cheese))={\text{I have a meal}}$

Just as in ordinary algebra, where multiplication takes priority over addition AND takes priority (or precedence) over OR. In fact, AND can be written as × and OR as +, and the instinctive notion of order of operations applies directly to Boolean Algebra.