Boolean Algebra

Boolean functions

sum, product, complement, 0 and 1

A boolean function of degree n: there are 2^2^n different functions of a given degree

function of degree n takes n variables as its arguments

Identities of Boolean Algebra

We can prove any one of the identities using the truth table

We can prove new laws using either the truth table or using one of the identities

Duality

interchange 0 and 1

interchange + and *

if f = g then fd = gd

The abstract definition of a Boolean algebra:

Any algebra that provides or, and, negation operators. Also defines values for 0 and 1 such that the five laws on page 614 are obeyed, it is a Boolean algebra

Let us say we have a set U. We can define a Boolean algebra using the variables which are subsets of U.

union will be the or, intersection will be and, setwise complement is negation. 0 will correspond to empty set and 1 will correspond to U.

We can prove that all the five laws are obeyed.

therefore the set algebra we defined just now is a Boolean algebra

complemented distributive lattice can also define a Boolean algebra

Greatest element is mapped to 1, least element is mapped to 0

and corresponds to glb

or correspond to lub

we only need to prove three laws: identity laws, associative laws, commutative laws.

Once we prove these laws then we have a Boolean algebra. An abstract Boolean algebra doesn’t have to deal with traditional interpretation involving true and false.

Section 9.2 (Representing Boolean functions)

Given an arbitrary Boolean function, we can find a mathematical form for the function

For every 1 in the function column create a minterm (definition on page 618). Sum of the minterms will have the same value as the function

See two quizzes.

Do we need all the three operators: the answer is no

combination of or and negation

combination of and and negation

either one of the pairs is enough, because we will be using it with De Morgan’s law

x or y can be rewritten as not(not x and not y)

 

 

The above table shows that we only need one operator either the nand or the nor.

Logic gates (9.3)