An innovative technique for logic minimization of combinatorial multiplexing circuits is introduced. It is targeted towards Product-Term (PT)-Based hardware, like PALs, PLAs, and CPLDs, though its usage is not limited to such hardware. The technique exploits the fact that, sometimes, circuit designers have no interest in unequivocally specifying the particular encoding of select control words in a multiplexer, if there is a unique correspondence between select words and multiplexer inputs. Our approach enables the HDL compiler to pick a particular encoding of the select words that favors logic minimization the most. We have developed a prototype of the optimization algorithm based on simulated annealing, which targets circuits implemented in a PT-based functional unit of a reconfigurable processor. Benchmark results show that considerable reduction in logic (up to ~46% in the number of PTs utilized, for the circuits studied) can be achieved.