Logic Stuff 

D = A + B + C;//  (plus is the or operator)
F = A*B*C; 
E = (( A * B C') + (A C B') + (C B A'));

// second way

E = [(A * B) + (A * C) + (B * C)] * (ABC)'

proving this:

Demorgan's Law
Distributive law
Distributive law
Inverse law
Null law 
Identity law

Proofs

NOR is equivalent to AND with inputs complemented

(X + Y)' = X' * Y';
(X * Y)' = X' + Y'; // This one supports the NAND example

NAND is equivalent to OR with inputs complemented

Half Adder

With A, B, Sum, Carry

Sum is adding them,

While Carry is multiplying them

Part 1;

A, B, Carry-in = inputs.

Sum, Carry-out = outputs.

Sum = A' B' Cin + A' B Cin' + A B' Cin' + A B Cin;
// adding the sums of each potential options, highlighint the only options that will produce 1, which are odd batches of 1's(1 one in a combination, or all three)
Carry-out = A' B Cin + A B' Cin + A B Cin' + A B Cin;
// the only ones where you have at least 2 1's, which is four of them. (3 of them, the other one(last one), is all three in a combination being 1.

Simplifying the Carry-out.

Cout = A' B Cin + A B' Cin + A B Cin' + A B Cin;

(Idempotency) = A' B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
(Commutative) = A' B Cin + A B Cin A B' Cin + A B Cin' + A B Cin 
(Distributive) = (A' + A) B Cin + A B' Cin + A B Cin' + A B Cin
(Inverse) = (1) B Cin + ...
(Idempotency) = B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
(Commutative) B Cin
(Distributive)
(Inverse)
(Distributive)
(Inverse)
= B Cin + A Cin + A B

Boolean minimization

(helps to reduce it from the beginning to the end, shown below.

Logic Gates Further

And can also be X down sign Y

Or can also be X up sign Y

Instead of drawing a lot of logic inverters, it would have bubbles pointing to other ones.

Different Realizations of a function

for 1(two-level realization), having and and or, (round bulb is and, sharp bulb is or)

(we don’t count NOT gates)

    for first bulb, it is ABC’

    for second bulb, it is A’C

    for third bulb, it is B’C

    for the sharp bulb or, it is the sum of products of all the minterms(the combination of and terms)

for 2.(multi-level realization),

(gates with fewer inputs)

for 3(XOR gate, simplier, but more expensive to build)

Which realization is best?

Reduce number of inputs:

  • literal: input variable(complemented or not)

  • Fewer literals means less transistors

  • Fewer inputs implies faster gates

  • Fan-ins(# of gate inputs) are limited in some technologies

Reduce number of Gates

  • Fewer gates (and the packages they come in) means smaller circuits

Reduce numbers of levels of gates

  • fewer levesl fo gates implied reduced signal propagation delays

  • minimum delay configuration typically requires more gates

How to explore tradoffs between circuit delay and size?

  • Automated tools to generate different solutions

  • Logic minimization: reduce number of gates and complexity

PA + PA' = P(A' + A) // need rest of formula

Canonical Forms

  • Sum of products: a logical sum (OR) of products( terms using the AND operator)

  • Produce of sums: A logical product (AND) of sums (terms using the OR operator)

Example

D = A + B + C

F = A*B*C
E = (A*B*C') + (A*C*B') + (B*C*A') ( sum of products)
other solution for E is Noncanonical, since it had multiplying and adding (AND and OR) between terms

Disjunctive normal form, minterm expansion:

Alternative ways of saying the sum of products

For Minterm expansion

F(A, B, C) = Sigmam(1,3,5,6,7)(position of 1’s in the outputs)

F’(A,B,C) = Sigma m(0,2,4)

Product term(minterm)

ANDed product of literals (which the output is true)

    Each variable appears exactly once, in true or inverted form(not both)

Canonical form is not equal to the minimal form

Need to use the Boolean algebra laws to simplify

Product of sums

Conjunctive normal form, maxterm expansion

Alternative ways of saying product of sums

F(A,B,C) = M(0,2,4)(capaital version of sigma)

(A’+B’+C’)( A’+B+C’) (A+B’+C’)(no)

F = (A + B + C) (A + B’ + C) (A’ + B + C)// fpr maxterm, you need to make it zero, so it would be reverse what you would normally have

F’ = the regular way

Sum Term

ORed sum of literals

    same variable condition as minterm

can still be minimized using logical laws

Minterm and MAXterm are the same thing, leading to the same result(for example , AB + C

Mapping between canonical forms

  • Minterm to maxterm conversion

    • Use maxterms whose indices do not appear in the minterm expansion

  • Maxterm to minterm conversion

    • same thing as before, but opposite(use minterms who indices do not appear in maxterm conversion

  • Minterm expansion of F to maxterm expansion of F’

    • same thing as the first one

  • Maxterm expansion of F to minterm expansion of F.’

    • same thing as the second one

De Morgan’s theorem can change S-o-P to P-o-S, and back.

Programmable Logic Array

The relationship between a truth table and a two-level representation allows us to generate a gate-level implementation of any set of logic functions.

S-o-P(Sum of Products) corresponds to a programmable logic array.

From 0-9, binary-coded decimal digits are encoded from 0000 to 1001.

“past 0-9, there are “dont care terms”, where the output of these input patterns/combinations doesn’t matter, like output is X or D

The set of 0000 is called the offset of W

the set of 1001 as on-set of W

MAxterm set uses don’t care set(D) + offset

Minterm set uses don’t care set(d) + on-set

output don’t care is when the output is free to be true or false

input don’t care is when only some of the inputs work i assume

F = m(2,3,4) + 0,7(d)

F = M(1,5,6) + 0,7(D)

Simplification of two-level combinational logic

  • Goal is to find a minimal sum of products or product of sums realization

Uniting theorem. : A(B’ + B) = A

Boolean cubes: Visual technique for when the uniting theorem can be applied. n input variables = n-dimensional “cube”

Faces represent an expression in one variable, with F(ABC) = m(4,5,6,7)

Karnaugh maps

  • Flat map of Boolean cube

    • Wrap around at edges

    • Hard to draw and visualize past 4 dimensions

    • virtually impossible for more than 6 dimensions

  • Alternative to truth-tables to help visualize adjacencies

    • Guide to applying the uniting theorem

    • On-set elements with only one varibale changing value are adjacent unlike the situation in a linear truth-table

  • GRay-code: only one bit changes between cells

  • Layout for 2-4 dimension k maps

for homework

it goes from 000 to 111( 001, 010, 011, 100, 101, 110, 111

Examples of karnaugh maps

(this one makes so much sense now, the gray scale is just the binary representations of AB, C, the big 0/1 are just F, where A/B/C is 1 is where they are, outside of that C’, B’, A’, the groups make sense, etc.)

(this is with four variables. where it lines up and more.

Definitions of terms for two-level simplifcations

  • Implicant

    • single element of On-set or DC-set or any group of these elements that cna be combined to form a subcube

  • Prime implicant

    • implicant that can’t be combined with another to for a larger subcube

  • Essential prime implicant

    • prime implicant is essential if it alone covers an element of ON-set

    • will particiapte in All possible covers of the ON-set

    • DC-set used to form prime implicants but not to make implicant essential

  • Objective

    • Grow implicants into prime implicants (minimize literals per term)

    • Cover the ON-set with as few prime implicants as possible(minimize number of product terms)