relay circuit

These gates can be exteded to more than two inputs. In the case of NAND and NOR, the result it seems ambiguous.

Click here to add notes.

Click here to add notes.

Click here to add notes.

Click here to add notes.

Circuits lab

We generally prefer 2 level implementations, as they minimize the total delay in computation.

Either a canonical form or a standard form gives rise to a 2 level implementation.

We can also express a function as a sum of products, in which a given product need not be a minterm, or a product of sums where the sums need not be maxterms. These representations are called standard forms. Standard form representations are not unique.

Every boolean function can be represented in either of thses two canonical forms, as a sum of minterms or a product of maxterms. Such a representation is also unique.

Define the complement f prime of a function is the function whose value is always the complement of that function. The product of the maxterms for the rows where f1 is 0, simalarly for f2.

Click here to add notes.

So every maxterm is false in exactly one row of the truth table. We can find an expression for a given function by summing the minterms associated with the rows of the truth table when the function is true.

Minterms Maxterms

Each minterm is true in exactly 1 row of our truth table. A maxterm is a sum of 3 literals, each containing a different variable. By de Morgans laws every maxterm is the complement of some minterm.

Canonical and standard forms: Suppose were considering a function of 3 boolean variables x y z. A minterm is a product of 3 literals, each containing a different variable.

In expressions like the above, a variable or its complement is called a literal and a product or sum of literals is called a term. Both the number of literals and the number of terms are measures of the complexity of a formula.

Click here to add notes.

Click here to add notes.

Click here to add notes.

Truth table

Boolean Functions: Binary valued functions of binary variables. We have seen how we can implement Boolean functions using the operations of switching algebra, But algebraic manipulation sometimes we can simplify such implementations.

Our logical operators AND, OR and NOT are exactly the operators times plus and not that we have just defined.

This smallest Boolean algebra is called switching algebra

Click here to add notes.

Click here to add notes.

It turns out that the smallest Boolean algebra has only 0 and 1

By extension every boolean algebra has at least 2 distinct elements

De Morgans law can be extended to any number of variables.

Basic theorems of binary algebra, idempotence, involution, associativity, deMorgan, and absorption.

Click here to add notes.

de morgan

Click here to add notes.

Click here to add notes.

absorption

Click here to add notes.

Click here to add notes.

Click here to add notes.

Click here to add notes.

Click here to add notes.

axioms of boolean algebra

The usual high school algebra is that of a fields. On the other hand in a field every element has an additive inverse, and every nonzero element x has a multiplicative inverse x prime

For every element x in B its complement x prime is in B. There exists at least 2 element x not equal to y in B. For example let X be a set and P of X its power set, the set of all subsets, Then P of X together with union, intersection and set complement Y prime equals X minus Y is a boolean algebra.

The plus and times operations are commutative. Plus and times are distributive over each other.

1 The set B is closed with respect to these operations. Applying the operations to elements of B yields elements of B. 2a There exists an element 0 in B that is an identity element for addition. 2b there is an element 1 in B that is an identity element for multiplication

A boolean algebra is a set B equipped with two binary operators plus and times, and one unary operator not, such taht the following axioms are satisfied.

Shannon formulated this logical approach in terms of boolean algebra.

Gates are often called logic gates, and the resulting circuits are called logic circuits.

This is why we don t need more parentheses in out formula. We will assume that we have circuit components that implement these basic functions called gates.