From d95532688cef1b12922d3f6e51eb27dc1d00f634 Mon Sep 17 00:00:00 2001 From: lshprung Date: Fri, 25 Sep 2020 11:14:46 -0700 Subject: Post-class 09/25 --- 2.md | 4 +++ 3.1.png | Bin 0 -> 15537 bytes 3.2.png | Bin 0 -> 18231 bytes 3.3.png | Bin 0 -> 10513 bytes 3.4.png | Bin 0 -> 22357 bytes 3.5.png | Bin 0 -> 18208 bytes 3.6.png | Bin 0 -> 25941 bytes 3.7.png | Bin 0 -> 9228 bytes 3.md | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 128 insertions(+) create mode 100644 3.1.png create mode 100644 3.2.png create mode 100644 3.3.png create mode 100644 3.4.png create mode 100644 3.5.png create mode 100644 3.6.png create mode 100644 3.7.png create mode 100644 3.md diff --git a/2.md b/2.md index f39bfcb..fba2a7a 100644 --- a/2.md +++ b/2.md @@ -199,3 +199,7 @@ - Connections by label is typical ![diagram](2.4.png) + +--- + +[Boolean Algebra and DeMorgan's Theorem ->](3.md) diff --git a/3.1.png b/3.1.png new file mode 100644 index 0000000..070cbb7 Binary files /dev/null and b/3.1.png differ diff --git a/3.2.png b/3.2.png new file mode 100644 index 0000000..19f896e Binary files /dev/null and b/3.2.png differ diff --git a/3.3.png b/3.3.png new file mode 100644 index 0000000..78a5a72 Binary files /dev/null and b/3.3.png differ diff --git a/3.4.png b/3.4.png new file mode 100644 index 0000000..cdf3435 Binary files /dev/null and b/3.4.png differ diff --git a/3.5.png b/3.5.png new file mode 100644 index 0000000..fbb92c8 Binary files /dev/null and b/3.5.png differ diff --git a/3.6.png b/3.6.png new file mode 100644 index 0000000..146a25a Binary files /dev/null and b/3.6.png differ diff --git a/3.7.png b/3.7.png new file mode 100644 index 0000000..8300ed9 Binary files /dev/null and b/3.7.png differ diff --git a/3.md b/3.md new file mode 100644 index 0000000..c31376b --- /dev/null +++ b/3.md @@ -0,0 +1,124 @@ +[\<- Truth tables, minterms, and simple synthesis](2.md) + +--- + +# Boolean Algebra and DeMorgan's Theorem + +## Boolean algebra basics + +### Boolean Algebra Properties + +- Commutative (input order doesn't matter) + - `X*Y` = `Y*X` + - `X+Y` = `Y+X` +- Associative (can combine like functions) + - `X*(Y*Z)` = `(X*Y)*Z` = `X*Y*Z` + - `X+(Y+Z)` = `(X+Y)+Z` = `X+Y+Z` +- Distributive (going the other way: factoring) + - `X * (Y+Z)` = `X*Y + X*Z` +- Combining + - `X * Y + X * !Y` = `X * (Y + !Y)` = `X` + +--- + +## DeMorgan's Theorem + +- `!(X*Y)` = `!X + !Y` (and `!(X+Y)` = `!X * !Y`) +- Allows us to transform any AND gate to an OR gate, or vice versa +- NOTE: `!(X*Y)` != `!X * !Y` + +|x|y| |x\*y|!(x\*y)| |!x|!y|!x + !y| +|-|-|-|----|-------|-|--|--|-------| +|0|0| |0 |1 | |1 |1 |1 | +|0|1| |0 |1 | |1 |0 |1 | +|1|0| |0 |1 | |0 |1 |1 | +|1|1| |1 |0 | |0 |0 |0 | + +### NAND and NOR gates + +- An AND gate with an inverter on the output is called a NAND gate +- An OR gate with an inverter on the output is called a NOR gate + +![diagram](3.1.png) + +### Visualizing DeMorgan + +- "Flip" the gate type (AND \<-> OR), invert all the inputs, invert the output + - Remember that bubbles mean inverters + - Can be applied to any gate/inverter combo + +![diagram](3.2.png) + +### A note about inversions + +- To be clear: inverting an inversion essentially cancels it out + - If you invert a value and then invert it again, you're back to where you started +- When applying DeMorgan's, inverting an inversion makes it go away + +![diagram](3.3.png) + +### Applying DeMorgan + +- Inversions can be added in pairs + +![diagram](3.4.png) + +- Inversions can "slide" to the other end of a wire + +![diagram](3.5.png) + +--- + +## Other Synthesis Approaches: solving for 0's, POS, reducing with Boolean Algebra + +- Say we had f(x1,x2,x3) = ∑m(1,4,5,6) + - What does the truth table look like? + - What is the canonical SOP equation? + - What does the matching circuit look like? +- What are some other ways we can synthesize this function? + - Synthesize the inverse function, then invert + - Simpler circuit if more 1's than 0's in truth table (which is actually not the case here) + - Reduce the equation using Boolean algebra + +### Truth table for inverse function + +- If F(x1,x2,x3) = ∑m(1,4,5,6), then !F = ∑m(0,2,3,7) + +|x1x2x3|F|!F| +|------|-|--| +|000 |0|1 | +|001 |1|0 | +|010 |0|1 | +|011 |0|1 | +|100 |1|0 | +|101 |1|0 | +|110 |1|0 | +|111 |0|1 | + +### Synthesizing the inverse + +- Create equation for !f by adding minterms that evaluate to 0 + - !f = m0 + m2 + m3 + m7 + - f = !(m0 + m2 + m3 + m7) (a valid answer) +- A step further would apply deMorgan's + - f = !m0 * !m2 * !m3 * !m7 +- One step further would use maxterms + - ex. !m0 = M0 = !(!x1 * !x2 * !x3) = x1 + x2 + x3 + - f = M0 * M2 * M3 * M7 (yet another valid answer) + - Called product of sums (POS) form + +### Another POS example + +- Say F(A,B,C) = ∑m(0,2,3,4,6,7) + - !F = ∑m(1,5) + +![diagram](3.6.png) + +### Reduction w/ Boolean Algebra + +- f = `(!x1 * !x2 * x3) + (x1 * !x2 * !x3) + (x1 * !x2 * x3) +(x1 * x2 * !x3)` (canonical SOP) +- f = `((!x1 + x1) * !x2 * x3) + (x1 * (!x2 + x2) * !x3)` +- f = `(!x2 * x3) + (x1 * !x3)` +- The best answer yet, but it can be hard to see these reductions in equation form + +![diagram](3.7.png) -- cgit