Could one do this directly with transistors or standard cells? Seems very useful for ASICs, particularly structured ASICs which are mapped from FPGA lookup tables of size 4-6.
This isn't quite as useful in practice as it seems, since NOT isn't always free, you almost always can eliminate common subexpressions, and gates with more than two inputs are often cheaper than doing everything with two-input gates.