User Tools

Site Tools


en:mathematics:logic:boolean
 
 

Basics of boolean algebra

If “today is Monday'” is true then “Not(today is Monday)” is false. This logical expression translates into English as “today is Not Monday” and this makes it easier to see that it is false if today is indeed Monday. Explanations like that rapidly become convoluted and difficult to follow and this is part of the power of Boolean logic. You can write down arguments in symbolic form. To simplify the handling of complex binary connectives, the mathematician George Boole developed Boolean Algebra, using ordinary algebraic notations AND, OR and NOT. Alternatives that you may encounter are ^ for AND, v for OR, and either over-score or prefix for NOT.

And … The Boolean AND is the same as the English use of the term, but the Boolean OR is a little different: If you are asked “coffee OR tea?”, in most western households you are not expected to say “yes” to both, while in the Boolean case OR includes both. The Boolean operator that corresponds to the English use of the term “OR” is the XOR.

Burglary in progress

Suppose you want to build a security system which only works at night and responds to a window or the front door being opened. If you have light sensors you can use these for giving off a signal indicating the truth of the statement:

Front door open Window open Burglary in progress
False False False
False True True
True False True
True True True

We can make the propositions as complex as we want:

(Burglary in progress) = (NOT(It is daytime)) AND ((Window open) OR (Front door open))

                               ---------
        Front door open -----> |       |
                               |  OR   |-----
            Window open -----> |       |    |       ---------
                               ---------    +-----> |       |
                                                    |  AND  |-----> Burglary in progress
                               ---------    +-----> |       |
                               |       |    |       ---------
         It is day time -----> |  NOT  |-----
                               |       |
                               ---------

Precedence and maintaining order

Boolean operations are carried out in a well defined order or “precedence”:

Operator Symbol Precedence
NOT ' Highest
AND . Middle
OR + Lowest

Expressions inside brackets are always evaluated first, overriding the default precedence order. The Boolean equation of the Burglary in progress block diagram in fully bracketed form:

B = ((T'). ((W) + (F)))

Using the precedence rules this can be simplified to:

B = T'. (W + F)

Manipulating boolean expressions

Unary NOT

And there are rules to manipulate Boolean expressions. The most simple are the rules for the unary operator NOT:

(A')' = A
A' . A = 0
A' + A = 1

General rules for AND and OR

For more see Group theory Boolean Algebra

Associative:

(A . B) .C = A . (B . C)
(A + B) + C = A + (B + C)

Commutative:

A . B = B . A
A + B = B + A

Distributive:

A . (B + C) = A . B + A . C
A + (B . C) = (A + B) . (A + C)

Simplification rules

The first group of simplification rules uses one variable:

A . A = A
A + A = A

The second group uses Boolean constants:

A . 0 = 0
A . 1 = A
A + 0 = A
A + 1 = 1

en/mathematics/logic/boolean.txt · Last modified: 2018/08/18 15:50 by Digital Dot