[Tutorial] Introduction to Boolean Algebra, Part I

[Acid_Snake]

As part of my programming tutorials I wanna teach you guys the concept of Boolean Algebra, and how to work with it.
But first, what's Boolean Algebra? wikipedia has this to say:

In mathematics and mathematical logic, Boolean algebra is the subarea of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. Instead of elementary algebra where the values of the variables are numbers, and the main operations are addition and multiplication, the main operations of Boolean algebra are the conjunction and, denoted ∧, the disjunction or, denoted ∨, and the negation not, denoted ¬.

Boolean algebra was introduced in 1854 by George Boole in his book An Investigation of the Laws of Thought.[1] According to Huntington the term "Boolean algebra" was first suggested by Sheffer in 1913.[2]

Boolean algebra has been fundamental in the development of computer science and is yet the basis of the abstract description of digital circuits. It is also used in digital logic, computer programming, set theory, and statistics.[3]

Wikipedia has this nasty way of grabbing an easy concept and turn it into a hard-to-understand one, so I'll break this up to you.
Boolean Algebra is the basis of modern computer science, instead of normal algebra that uses numbers, Boolean Algebra uses True/False values, also denoted as 0/1. There are three main operations: AND, OR, NOT and works with variables (usually denoted as A, B, C, D, etc) that can take either one of those two values (1, 0), the result of a boolean function is usually denoted as Z.


Main Operations

- AND: this operation returns 1 (true) if the variables AND'ed are all true (1), it returns false (0) otherwise.
The operator used for AND is usually the multiplication sign (*) or ∧. The truth table for AND is:
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1

- OR: this operation returns 1 if at least one of the variables OR'ed is true (1), otherwise it returns 0.
The operator used for OR is usually the addition sign (+) or ∨. The truth table for OR is:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1

- NOT: this operation negates the value of a variable, if the variable is 0 it returns 1, if it's 1 it returns 0.
The operator used for NOT is usually the apostrophe (') or ¬. The truth table for NOT is:
¬0 = 1
¬1 = 0


Boolean Functions
A boolean function (usually denoted F, G, etc) is one that given different parameters (A, B, C, etc) does operations with them (AND, OR, NOT, etc) to return a value (usually called Z). Here's an example of such function:

Code: Select all

F(ABC) = AB + ¬AC

This function is broken down to: an AND between A and B, then the result is OR'ed with the negation of A AND'ed with C.
Lets go step by step of what this function would do if take the parameters A=1, B=0, C=1:
- AB = 1*0 = 0
- ¬A = 0
- ¬AC = 0 * 1 = 0
- AB + ¬AC = 0 + 0 = 0
so with the above mentioned values for A, B and C the function will return 0.

This is all for now, as a training exercise take the above shown function and calculate it's return values for the following combinations of values:
- A=0, B=1, C=0
- A=1, B=0, C=0
- A=1, B=1, C=1
- A=0, B=0, C=0
- A=0, B=1, C=1

Se you on the next lesson.

Next: viewtopic.php?f=37&t=33507

Advertising

[m0skit0]

Interesting tuto, but I doubt people will want to read this, even if it's very useful for programming... Also ^ is used for XOR-ing in a lot of programming languages. This might be confusing for newbies

Advertising

[Acid_Snake]

Interesting tuto, but I doubt people will want to read this, even if it's very useful for programming...

this is just a quick set of tutos that most people will learn in 5-10 minutes, unlike actual programming languages that require a heck lot more to be learnt

Also ^ is used for XOR-ing in a lot of programming languages. This might be confusing for newbies

problem is that symbol is also used in probability, which has a lot in common with boolean algebra, that's why it's more regarded as an AND rather than a XOR, but I digress, I will never use that symbol here, I prefer + (OR) and * (AND), XOR on the other hand is not an operation in itself, it's more like a function, A XOR B = A'B + AB' but I'll cover that later.

[pspfanMOHH]

Code: Select all

F(ABC) = AB + ¬AC

Answer Key:
- A=0, B=1, C=0 = (0 * 1) + (1 * 0) = 0 (False/Off)
- A=1, B=0, C=0 = (1 * 0) + (0 * 0) = 0 (False/Off)
- A=1, B=1, C=1 = (1 * 1) + (0 * 1) = 1 (True/ON)
- A=0, B=0, C=0 = (0 * 0) + (1 * 0) = 0 (False/Off)
- A=0, B=1, C=1 = (0 * 1) + (1 * 1) = 1 (True/ON)

Understanding the process was easy, nice tutorial just took 4 minutes of my time to read and easy to get it

Edit: This helps understand programming clearly, especially assembly, I can see why once someone see a piece of assembly code their heads say whats all the variables for, this tutorial explains 50/100 of assembly

[Acid_Snake]

It's good, the next lesson has been created.

[m0skit0]

This helps understand programming clearly, especially assembly

Programming is build over this concepts

[Xian Nox]

About the exercise:
[spoiler]

Code: Select all

F = AB + (-A)C

A = 1, B = 1, C = 1     F = 1*1 + 0*1 = 1 + 0 = 1
A = 1, B = 1, C = 0     F = 1*1 + 0*0 = 1 + 0 = 1

A = 1, B = 0, C = 1     F = 1*0 + 0*1 = 0 + 0 = 0
A = 1, B = 0, C = 0     F = 1*0 + 0*0 = 0 + 0 = 0

A = 0, B = 1, C = 1     F = 0*1 + 1*1 = 0 + 1 = 1
A = 0, B = 1, C = 0     F = 0*1 + 1*0 = 0 + 0 = 0

A = 0, B = 0, C = 1     F = 0*0 + 1*1 = 0 + 1 = 1
A = 0, B = 0, C = 0     F = 0*0 + 1*0 = 0 + 0 = 0

if A = 1        F = 1*B + 0*C = B
if A = 0        F = 0*B + 1*C = C

[/spoiler]