Boolean logic

Boolean logic is a complete system for logical operations. It was named after George Boole, an English mathematician at University College Cork who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software. In 1938, Claude Shannon showed how electric circuits with relays were a model for Boolean logic. This fact soon proved enormously consequential with the emergence of the electronic computer.

Boolean logic is used extensively in creating computer programs particularly to control flow of the program. 'If' statements are flow control instructions which are encountered in nearly every computer language and which use boolean logic. The 'if' statment returns a value of either true or false and the program is redirected accordingly.

Boolean Statements

True and False

Boolean logic statements can only return one of two values - true or false.

Boolean Operators and, or and equals

The main operators in Boolean statements are and, or and equals. To keep the statements succinct we use symbols to represent each of these operators. Programming languages use a range of abbreviations for these operators but in mathematics the following are used:

and - $\and$

or - $\lor$

equals - $=$

Equals is used to test whether the value on the left side of the statement is equivalent to the value on the right side. If it is then the returned value is true.

e.g. $2+3=5$ returns true. We can read this as "The statement two plus three equals five is true."

while $3+4=6$ returns false. We can read this as "The statement three plus four equals six is false." (Note that the addition operator, +, is not a boolean operator)

(This is sometimes called an equivalence test. In many computer languages this symbol ($=$) is also used to mean assignment (e.g. $A=B+5$) and so the boolean equivalence test is someimtes represented by $==$. Here we will use the simple $=$.)

These statements can now be combined using the and operator or the or operator as follows:

$(2+3=5)\land (4+2=6)$ returns true because both statements are true. (The brackets are only added to clarify what is happening.)

This can be read as follows: Because two plus three equals five is true and four plus two equals six is true then the overall statement is true.

Conversely we have this:

$(2+3=5)\land (4+2=7)$ returns false because one statement is true while one is false and with the 'and' operator it is necessary for both statements to be true for the overall one to return true.

This can be read as follows: two plus three equals five is true and four plus two equals seven is false so the overall statement is false.

The 'or' operator works differently from the and operator. With or it is only necessary that one part of the statement is true for the overall statement to be true. Thus:

$(2+3=5)\lor (4+2=7)$ returns true because one statement is true while one is false and with the or operator it is only necessary for one statement to be true for the overall one to return true.

If both statments are true then the overall statement is still true.

Since all this can become quite verbose we use another abbreviation to help. Instead of showing statements such as $(2+3=5)$ we represent a true statement by the value $1$ and any false statement by the value $0$.

Now our statement $(2+3=5)\land (4+2=6)$ becomes $1\land 1$ which is true and therefore equals $1$.

Further our statement $(2+3=5)\land (4+2=7)$ becomes $1\land 0$ which is false and therefore equals $0$.

Extending this to our or statements we get:

$1\lor 0=1$ and $1\lor 1=1$

Truth Tables

This now allows us to introduce the concept of truth tables. Truth tables allow us to show the results of our boolean statements in concise form.

For And we have

$0\land 0=0$

$0\land 1=0$

$1\land 0=0$

$1\land 1=1$

$0\land 0=0$  If statement 1 is false and statement 2 is false then the result is false

$0\land 1=0$  If statement 1 is false and statement 2 is true then the result is false

$1\land 0=0$  If statement 1 is true and statement 2 is false then the result is false

$1\land 1=1$  If statement 1 is true and statement 2 is true then the result is true

For Or we have

$0\lor 0=0$

$1\lor 0=1$

$0\lor 1=1$

$1\lor 1=1$

$0\lor 0=0$   If statement 1 is false or statement 2 is false then the result is false

$1\lor 0=1$   If statement 1 is true or statement 2 is false then the result is true

$0\lor 1=1$   If statement 1 is false or statement 2 is true then the result is true

$1\lor 1=1$   If statement 1 is true or statement 2 is true then the result is true

English example

We can also see that these types of statements can be used in normal English. For example, "You will pass the course if you pass subject A and subject B". From our truth tables for the and operator we can see that this means the person must pass both subjects. If they fail either subject or if they fail both they will fail the course.

Alternatively the statement could be "You will pass the course if you pass either subject A or subject B". This means they can pass either or both. This agrees with our truth table for or.

Boolean Operators - the not operator

The 'not' operator reverses the value of the statement. This makes sense since not true is obviously false and vice versa.

We represent not as follows:

not - $\lnot$

The Truth Table for not is

$\lnot 0 = 1$

$\lnot 1 = 0$

$\lnot 0 = 1$  not false is true

$\lnot 1 = 0$  not true is false

Combining Boolean Operators

These operators can now be combined to form complex statements. For example:

$1\land 1\lor 0=1$

$1\lor 1\land 0=1$

$0\land 1\lor 0=0$

Once we reach these complex statements the order that the operators are evaluated becomes important. As with arithmetic we don't just process them from left to right. The order of evaluation is not,and,or ($\lnot, \land, \lor$). In the examples the and is evaluated first in each case, followed by the or. The order of precedence can be changed by using parentheses similar to their use in arithmetic.

See also

• Boolean logic in Programming Languages