Boolean algebra

From Wikiversity
Jump to: navigation, search


Introduction[edit]

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

Boolean algebra describes logical and set 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 which 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[edit]

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 (ie q is the oppsite 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 = \lnotA 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:[edit]

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.

\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

\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

You should get familiar with these because you'll be seeing a lot of them later.

Rules and Syntax[edit]

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

Combining Operations[edit]

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 inner most 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 any one 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.