(Dredged up from the murky past...)
Designing control systems usually involves building a logic circuit that has several inputs and one or two outputs. Sometimes states are involved (sequencing of traffic lights, coin collectors for vending machines), sometimes not. In designing such control logic, many equations get written down which represent things like "If these three switches are off and these others are on, flip this switch over here".
Once one has the equations written down, (often as a Boolean function, a map from {0,1}^n to {0,1}) one has to build the circuit implementing these equations. Often times, the medium for implementation is a gate array, which may be a field of NAND logic gates that can be wired together, or a programmable logic device, which is like two or more gate arrays, some with ANDS, some with ORS, some NOT gates, flip-flops which are like little memory stores, and so on.
The major question is: are there enough gates on the device to build all the logic represented by the equations? To this end, computer programs called logic minimizers are used. They have certain definite rules (related to manipulation terms in Boolean logic) and certain heuristics (guidelines and methods for following the guidelines) to follow in order to minimize the number of, say, AND and OR gates used in representing the equations. The mathematics of representing any Boolean function as a series of AND and OR gates, and finding equivalent representations, has been developed and used since George Boole set down the algebraic form of what is now called Boolean Logic. Computer Science, abstract algebra, clone theory, all have played and continue to play an essential role in solving instances of this kind of problem. The fact that it is not completely solved is related to one of the Millenium Prize problems (P-NP) .
Gerhard "Ask Me About PLD Chips" Paseman, 2011.02.24
