Also, you can chain some min/max terms to get better optimization at the cost of propagation delay. You'll also often generate transient states (runt pulses, glitches) from such logic, as the signals propagate through different depths of gates on their way through. So be careful. It doesn't look like these signals are edge-triggered? So that's probably not an issue, just something to keep in mind.
The least possible gate delay, with the most general approach, is to form all min-terms, then all max-terms (or vice-versa). Which is what the PAL does: it's an array of inverters (so each input and its complement is available), crosslinks (to wire some combination of inputs and min/max gates), AND or OR gates, then OR or AND gates. Exactly which combination is used, depends on the technology, some use minterms (AND then OR), some the other way. I forget if one or the other is more common? Also there's a certain fanout, a certain supply of each, so if you need like 20-goddamn minterms and the PAL only has 12 inside, you'll have to invert it (use maxterms, which probably won't need as many), or whatever.
Put another way: for every combination of inputs that should yield an active (or inactive) output, collect that combination of normal/complemented inputs together. For inputs A, B, C, etc., form the product A * /B * C * ..., inputs complemented as needed. Then add together all these terms, A*/B*C + /A*B*C + ..., whatever it is. Clearly the gate delay is at most one inverter, one AND and one OR, which if they're equal is a total of three gate delays, simple.
But with such a small space, this is easy to solve.
Specifically, let's see, with as many as 16 possible input states, up to half as many min/max terms might have to be formed and collected -- that would require four inverters (one for each input), and for each output, eight 4-input ANDs and one 8-input OR). I suppose about 9 chips absolute worst case.
It looks like it's going to be much simpler than that, and plus you can use standard functions to optimize certain convenient (or pathological) patterns. Namely, AND-OR-INVERT gates are a thing; muxes are wonderful; and, XOR implements the checkerboard pattern that otherwise requires worst-case min and max terms. Probably, using standard logic, the worst-case is closer to 1/4th the total number of states, or 4 terms? Worst case gate delay might be a few more than canonical minimum, not sure.
Tim