Boolean logic: introduction

Most digital systems - such as the Qibec CPU - are implemented using electrical circuits performing Boolean logic.

The following text first introduces Boolean logic (George Boole, 1847) by comparing it to common arithmetic. Numeric and Boolean expressions are then treated as "function-blocks", whose outputs depend on their inputs.

Numerical function-blocks

As an example, imagine a group of people visiting a fair, where the entrance fee is EUR 2 per child, and EUR 3 per adult. The total due amount for the whole group would then be:

amount  =  ( children x 2 ) + ( adults x 3 )

This formula can be regarded as a "function-block", with the number of children and adults as input-values, and the total due amount as output-value.

As can be seen, this particular function-block is constructed out of 2 sub-blocks, each containing a multiplication.

Everyday Boolean logic

The above formula used numeric terms (the amount of people, number of Euros).

Boolean logic uses only the values "True" and "False" (or "1" and "0", or "high" and "low").

That is, every Boolean (sub)expression can be simplified to one out of two possible truth-values.

Many everyday expressions can be simplified to either True or False:

• "I am outside"
• "it rains"
• "I get wet"
• "the Earth is flat"

Like the earlier formula to calculate the total entrance-fee, function-blocks can be formed using Boolean terms:

"I get wet"  =  "I am outside"  AND  "it rains"

Here, the right-hand terms can be either True or False. The left-hand term ("I get wet") is only True if both right-hand terms are also True.

Boolean operators

Whereas numeric arithmetic has operators like "+" (addition) and "x" (multiplication), Boolean logic has operators working on truth-values instead of numbers. (Addition and multiplication would make no sense there.)

One such operator was the Boolean "AND", as shown in the previous formula.

Some other operators that map easily to everyday expressions are "OR" (e.g. "panic = flood OR fire") and "NOT" ("dangerous = NOT safe").

The Qibec CPU mainly uses 2 other operators, "NAND" ("not-AND") and "NOR" ("not-OR"), which can be regarded as an "AND" respectively "OR" function-block, followed by a "NOT"-block.

An example of the NAND-operator:

"I can escape"  =  "window is locked"  NAND  "door is locked"

Or to put it differently: one can escape, unless both the window and the door are locked.

An example of the NOR-operator:

"I am happy"  =  "I am cold"  NOR  "I am hungry"

Or rather: I'm happy unless I'm cold or hungry. (Or: I'm happy if I'm cold nor hungry.)

Boolean function-blocks

Boolean function-blocks, like numerical ones, can be combined to form new blocks.

For example, a new Boolean operator - "exclusive-OR", or "XOR" - can be constructed. This new operator states that something is True if either of two conditions are True, but not both.

A real-life example when trying to push a sheep off the road:

"movement"  =  "I push left"  XOR  "you push right"

(The sheep will move if either one pushes it in the direction of choice, but not both.)

Such a new XOR-block can be created by combining AND-, OR- and NOT-blocks, operating on input-conditions named "A" and "B":

output  =  ( A OR B )  AND  ( NOT ( A AND B ) )

(Literally: the result is True if either A or B are True, but not both.)