algorithm - Propositional Logic - Reducing the Number of Operations -

algorithm - Propositional Logic - Reducing the Number of Operations -

in short, i'm wondering if, given 2 propositional formulas, whether there standard method finding shortest sequence of operations still have same output 2 formulas. illustration if have next formulas:

and

we can cut down number of operations introducing new proposition:

and q becomes:

this reduced number of operations (unary , binary) 19 14. new logic circuit q is:

ideally there negations , disjunctions. there algorithm converting proposition ideal simplified one? , there algorithm introducing new propositions above?

there - after 50 years of research - still no standard method multi-level logic synthesis. two-level case can decently tackled using karnaugh maps or quine mccluskey method. here, number of minterms minimized. not straight correspond number of logical operations required determine function value.

the university of california @ berkeley developed several tools generate heuristic solutions. of these tools nicely packaged in logic fri 1.

input function q:

entered: q:=(a & ((b & c) + (b' & c'))) + (a' & ((b & c) + (b' & c'))');

minimized: q: = b c + a' b' c + a' b c' + b' c';

output after "mapped gates" operation:

note: more recent synthesis suite clifford wolf's yosys.

algorithm optimization boolean logic