Boolean Logic

Youtube

#Booleans and Binary


Pair	Common Domain
0 / 1	Computing
False / True	Logic
Off / On	General, electronics
Low / High	Electronics

The above terms are synonymous, in that they all refer to the same idea: binary values. Earlier computers did not always use binary, it took decades of iteration to settle on binary because of its simplicity and efficiency.

#Logic

Languages need ways to express not just things, but what happens to those things.

In English, verbs describe actions:

fight, run, attack, defend

In mathematics, operations transform quantities:

add, subtract, multiply, divide

In binary, boolean operations transform truth values and bits:

AND, NOT, OR, XOR ...

Boolean logic gives binary its “verbs.”

#Operations on Binary Values

AND(*)
A	B	OUTPUT
0	0	0
0	1	0
1	0	0
1	1	1

OR(+)
A	B	OUTPUT
0	0	0
0	1	1
1	0	1
1	1	1

NOT(!)
INPUT	OUTPUT
0	1
1	0

Above are 3 common boolean operations, AND, NOT, OR and their truth tables, which show all possible inputs and outputs of each operation. The inputs are electrical signals that are either high or low voltage, which we represent as 1 and 0 respectively.


Operation	English	Algebraic Notation	Logic Notation	Example
AND	both	`A * B` or `AB`	`A ∧ B`	`1 AND 0 = 0`
OR	either	`A + B`	`A ∨ B`	`1 OR 0 = 1`
NOT	opposite	`A̅`, `Ā`, or `A'` or `!A`	`¬A`	`NOT 1 = 0`
XOR	one or the other, but not both	`A ⊕ B`	`A ⊕ B`	`1 XOR 0 = 1`
NAND	NOT AND	`(AB)'` or `¯(AB)`	`¬(A ∧ B)`	`1 NAND 1 = 0`
NOR	NOT OR	`(A+B)'` or `¯(A+B)`	`¬(A ∨ B)`	`0 NOR 0 = 1`

Boolean operations re-use symbols from math such as addition and multiplication + *, and work almost the same. The important thing you have to watch out for is the case of 1 +(or) 1. It’s not 2! Because we are working with binary values, not regular numbers! So use the truth table or speak out loud and read + as OR to resist your natural math instincts.

Let’s evaluate some boolean expressions:

Evaluate:

!((1 * 0) + (1 + 1))

Evaluate the inner parentheses and work your way outwards
Problem:
```
!((1 * 0) + (1 + 1))
```
Solution:
```
!((0) + (1))
```
```
! (1)
```
```
0
```
Answer: 0

#Check your understanding!

Evaluate: 1 * (0 + !(1))

1 * (0 + !(1))

1 * (0 + 0)

1 * 0

Answer: 0

Evaluate: ((1 + 1) * (1 + 0)) + !(1 + 1)

((1 + 1) * (1 + 0)) + !(1 + 1)

((1)     * (1))     + !(1)

(1) + 0

Answer: 1

#Boolean Functions

Abstracting to using functions instead of conrete values, since we’re dealing with binary values, we have the luxury of knowing every possible input and output of a boolean function.

Take for example the boolean function

f(x, y, z) = (x * y) + (!(x) * z)

Truth Table for f(x, y, z)


x	y	z	f (x, y, z)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Given 3 binary inputs, there can only be 8 possible combinations, so we can write a table for every possible input, and evaluate the function to get the output(the last row).
Going from:
Boolean function → truth table is pretty straight forward, we just plug in values and evaluate the boolean expression.
BUT
Truth table → Boolean function is a little more tricky.

You’ll be given a truth table, and you’re going to need to find the right combination of operations to write the boolean function that produces the truth table. Let’s explore why and how to do this with an example.

#Truth Table to Boolean Function

Youtube

How do you, given this truth table, write a boolean function that produces it?


Mush	Pep	OUT
0	0	1
0	1	0
1	0	1
1	1	1

Say you’re throwing a party, and you only want pizzas that have both mushrooms
AND pepperoni, OR ones that only mushrooms, OR ones that are plain with no toppings. Above is the truth table for this scenario.

To find the combination of operations that will allow the pizzas you want to pass, while rejecting ones you don’t want, all you have to do is:

#Steps to convert Truth Table to a Boolean Function

This is called “Disjunctive Normal Form”

Look at all the patterns that OUTputs 1
The 1st, 3rd, and 4th row in the table above
Mush Pep OUT ☆
0 0 1 ✅
0 1 0 ❌
1 0 1 ✅
1 1 1 ✅
Run a NOT operation on the 0’s in those patterns then AND them together
Mush Pep OUT Func
0 0 1 ( !M * !P )
1 0 1 ( M * !P )
1 1 1 ( M * P )
Those that are 1‘s remain the same, those that are 0‘s get a NOT operation, and then you AND them together to get
Then OR all of the different patterns together
Answer:
```
f(m,p) = (!M * !P) + (M * !P) + (M * P)
```

Mush	Pep	OUT	☆
0	0	1	✅
0	1	0	❌
1	0	1	✅
1	1	1	✅

Mush	Pep	OUT	Func
0	0	1	( !M * !P )
1	0	1	( M * !P )
1	1	1	( M * P )

#Gate Implementation

Pizza Gate Interactive Circuit for: `f(m,p) = (!M * !P) + (M * !P) + (M * P)`

This perfectly implements our truth table that filters out pizzas that we don’t want.
By cleverly combining and arranging these simple logic gates, we can create complex behavior. Everything you do on a computer from games, shopping, browsing the web, etc, all boils down to clever manipulations of 0’s and 1’s using these basic operations.

Try to come up with your own truth table and see if you can implement it with logic gates. Here are a few example problems:

Problem A
Given the truth table, write the boolean function f(x,y) = ... and implement it with logic gates


x	y	OUT
0	0	0
0	1	1
1	0	0
1	1	1

Problem A Answer:

f(x, y) = (!x * y) + (x * y)

Circuitverse implementation

Problem B
Given the truth table, write the boolean function f(x,y) = ... and implement it with logic gates


x	y	OUT
0	0	1
0	1	1
1	0	1
1	1	0

Problem B Answer:

f(x, y) = (!x * !y) + (!x * y) + (x * !y)

It’s really important that you get used to being given a truth table and converting it into a boolean function, because this underlies so much of the of the upcoming problems.
Circuitverse implementation