You have six kinds of gate and you know what each costs. Today: find out whether that is enough, and for what.
Three inputs, eight rows, and I chose every output by flipping a coin.
It computes nothing. It is not a known function. Nobody has ever needed it, and there is no pattern in it to find.
Build me the circuit.
Take any function of any n inputs. Whatever it does, however it was described to you.
It has a truth table, because it must produce some output for each of the 2n input combinations. There is nowhere else for a definition to live.
Every row of that table is either a 0, which you discard, or a 1, which becomes one AND gate.
/* 04-cost.c */ #include <stdio.h> int main(void) { printf("inputs rows in the table " "worst case AND gates\n"); for (int n = 1; n <= 16; n++) { long rows = 1L << n; if (n <= 6 || n == 8 || n == 12 || n == 16) printf("%4d %17ld %19ld\n", n, rows, rows / 2); } return 0; }
/* 01-compile.c */ #include <stdio.h> int main(void) { /* the function you want, one entry per row */ int want[8] = { 0, 1, 0, 1, 1, 0, 0, 1 }; int terms = 0; printf("out = "); for (int row = 0; row < 8; row++) { if (!want[row]) continue; int a = row >> 2 & 1, b = row >> 1 & 1, c = row & 1; if (terms) printf(" + "); printf("%s%s%s", a ? "a" : "a'", b ? "b" : "b'", c ? "c" : "c'"); terms++; } if (!terms) printf("0"); printf("\n\n%d AND gates, then one OR gate with %d inputs\n", terms, terms); return 0; }
Read a table from a file, with any number of inputs. Emit the sum of products expression, the gate count, and a netlist you can load into Logisim.
Then test it the way the machine tested itself: generate a random table, compile it, simulate the result, and check every row against what you asked for.
The procedure is correct at every size and unusable past about six inputs. Both are true, and the second half is now the interesting one.
Next session: what to do when the table is too big to write down.