Some basic notes for chapter 1

I have started reading chapter 1, and am having an absolutely awesome time re-learning so many of these things. Honestly, I had no clue how much I had forgotten.

In this blog post, I am going to enter a few notes, and document my my process of understanding various concepts I come across in this chapter.

Fact 1:

The simplest way to specify a boolean function is to enumerate all the possible values of the function's input variables along with the function's output for each set of input. This is also known as the truth table.

Fact 2:

Every boolean function can be represented with what is known as a Canonical representation. The truth table below represents a function with 3 variables.

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

To get the canonical function, we have to OR all the rows which have 1 as the result. From the table above the canonical function will be:

f(x,y,z) = ^xy^z + x^y^z + xy^z

This shows, that all functions can be represented with a combination of AND, OR, and NOT

Fact 3 (with some sense making):

The book states in the last paragraph of page 9 - "the number of boolean functions that can be defined with n binary variables is 2^2^n". I had a hard time understanding this at first. But them I realized that n variables will lead to 2^n combinations (rows), and if we assume each row as a variable, then it is possible to have 2^2^n truth tables. Since each truth table is a function, we can say that for n variables, we can have 2^2^n functions.

Fact 4:

The NAND and NOR functions have an interesting theoretical property. Each of the functions AND, OR, and NOT, can be constructed using either NAND or NOR functions. And since any function can be represented using AND, OR, NOT (see fact 2), we can represent any function using only NAND, or NOR function.