Mux - Karnaugh map 3 variables

[Losey]

Hello nand2tetris team,

First of all thank you for all your work. I am new to almost everything related to coding and computer related things. I started this Nand2Tetris course for curiosity and I am enjoying it although I am already having questions on Project 1!

Second of all, I do not know if I can post this or not here so feel free to take it off if it does not fulfill a rule here.

I am currently stuck in the Mux gate. I have searched through the forum and found some helpful information that I have complimented with some of the stuff I found on the slides and in google but I am still struggling to understand some things so if anyone can help me I would really appreciate it.

I read in another thread that Karnaugh maps are helpful to simplify the boolean expressions. I searched the table for 3 variables and applied what I understood for the Mux truth table. I got this:

a b s - o
0 0 0 - 0
0 0 1 - 0
0 1 0 - 0
0 1 1 - 1
1 0 0 - 1
1 0 1 - 0
1 1 0 - 1
1 1 1 - 1

When translated into the Karnaugh map I got this:

s\ab
   00  01  11  10
0  0    0    1    1
1  0    1    1    0

When I translated this into a formula I got this:

f (a,b,s) = AB + BS + AS (this last "S" with a line over it)

So my questions are:
 1. This is the first time I use the Karnaugh map and was not sure if I implemented it well. So, is this correct? Where did I go wrong?
 2. I was putting trying to represent this on a diagram but was not successful, I checked google and found there is an OR gate at the end of the design, where does this come from?


Sorry if these are very beginner questions and thank you in advance!

With best wishes.

[cadet1620]

Losey wrote

When translated into the Karnaugh map I got this:

s\ab
   00  01  11  10
0  0    0    1    1
1  0    1    1    0

This is the correct k-map for Mux.

When I translated this into a formula I got this:

f (a,b,s) = AB + BS + AS (this last "S" with a line over it)

You can write Not(x) as ~x or !x when typing, as in
    f (a,b,s) = AB + BS + A ~S
(I like to put a space before it as shown so that it stands out a bit.)

When simplifying using the k-map, you only need the minimum number of minterms (the rectangles of 1s) that produce the required 1s, so in this case the two minterms A ~S and BS are sufficient.
    f (a,b,s) = BS + A ~S

The "+" is the Or function, so
    f (a,b,s) = Or (And (B, S), And (A, Not (S)))

--Mark

[Losey]

I see! Thank you Mark, I had read that you had to overlap the miniterms but I can see that if the 2 rectangles already cover the other 1's then there is no need!

Your help is much appreciated!

Have a nice day.

[cadet1620]

Losey wrote

I had read that you had to overlap the miniterms but I can see that if the 2 rectangles already cover the other 1's then there is no need!

When one moves beyond idealized logic into the physical world, there are times that you need to overlap minterms to eliminate glitches. I've written an article about hazard glitches that you might find this interesting.
  http://marksmath.com/tecs/glitch/
If it doesn't make sense, don't worry.  It's not something you'll need to know unless you get deeper into hardware design.

--Mark