We can basically build anything with DNF
Basically, we can use the Disjunctive Normal Form to get a Boolean function that can be later simplified to well-known gates. The crux is that we simplify our implementation process by relying on simpler things that we built in the past.
How exactly can we prove that everything can be built using NAND gates?
If we try to apply DNF to truth tables, we can deduce that every Boolean function can be represented using only AND, OR and NOT gates.
We can also derive OR using AND and NOT gates. (I am not going to tell you how. Hint: De Morgan's Law)
And by the power of combination, we have the NAND gate which can be used as an elementary gate to build every other gate and implement all Boolean functions that we want to.
What is a Chip?
A chip or a gate provides an interface for the user. It specifies a set of input wires and the output wire(s). This is defined in an HDL stub file. The chip developer/builder has a contract that they will not change this. The chip designer decides what this interface will be.
A chip has to be implemented. The black box has to be defined by someone, that someone is the builder. They now use the magic of Boolean logic and the various gates available to them to implement the chip as defined by the interface and the truth table stated by the Designer.
Before we move to other stuff, we have to also make a note that hardware construction projects for these chips are made by two kinds of people.
- System Architect / Designer who creates the Chip API, test script, compare file for the chip interface.
- Developers who implement the chip interface and develop the implementation for the chip defined.
More about HDL
HDL is a functional/declarative language so order doesn't matter.
These HDLs are much more complex and have advanced functions like loops to ease the chip implementation process.