Slides from class: class7.pdf (video is available for students in collab)
Problem Set 3 (Overleaf, Jupyter) is due Monday, 13 February, 9:59pm.
As was pointed out to me by an intrepid student after class, what I said about { OR, NOT } being not universal since we included AND in our AON Circuits is badly wrong! One easy way to see this is we know we can convert between { AND, NOT } and { OR, NOT } using De Morgan’s laws, so we can construct AND from { OR, NOT }. Although it seems disturbing that we are focusing on { AND, OR, NOT }, and it is not a minimal universal gate set, we already knew this from showing that { NAND } is univeral (and obviously, we can build NAND with just { AND, NOT }).