Propositional Logic - Reducing the Number of Operations

3
votes

In short, I'm wondering if, given two propositional formulas, whether there is a standard method for finding the shortest sequence of operations that still have the same output as the two formulas. For example if we have the following formulas:

enter image description here

and

enter image description here

we can reduce the number of operations by introducing a new proposition:

enter image description here

and then Q becomes:

enter image description here

This reduced the number of operations (unary and binary) from 19 to 14. The new logic circuit for Q is:

enter image description here

Ideally I would like there to be only negations and disjunctions. Is there an algorithm for converting any proposition into my ideal simplified one? And is there an algorithm for introducing new propositions like above?

2
algorithmoptimizationbooleanlogic
I suspect you might have more luck getting this answered on one of the other SE sites (probably math.stackexchange.com). Interesting question though. - Aidan Kane
Use De' Morgan's laws and negate all conjunctions - smac89
@AidanKane Yes, I wasn't sure which one to post it on. I think I will just do both and see which one provides an answer first. - Scorpion_God
I've favourited it on here so I can see what people come up with. - Aidan Kane
Checking whether a circuit always returns "false" is called "circuit-SAT" and is a prototypical NP-hard problem. - tmyklebu

2 Answers

2
votes

There is - after some 50 years of research - still no standard method for multi-level logic synthesis. The two-level case can be decently tackled using Karnaugh maps or the Quine McCluskey method. Here, the number of minterms is minimized. But this does not directly correspond to the number of logical operations required to determine the function value.

The University of California at Berkeley developed several tools to generate heuristic solutions. Some of these tools are nicely packaged in Logic Friday 1.

Input for your function Q:

Entered: Q:=(A & ((B & C) + (B' & C'))) + (A' & ((B & C) + (B' & C'))');

Minimized: Q: = A B C + A' B' C + A' B C' + A B' C';

Output after "mapped to gates" operation:

enter image description here

Note:
A more recent synthesis suite is Clifford Wolf's Yosys.

0
votes

Yes there is a standard way of logic equation simplification

  • it is the use of Karnaugh Maps
  • here is Karnaugh Maps for 4 inputs example
  • the idea behind is to encode logic/circuitry truth table into rectangle matrix
  • Karnaugh Maps
  • this is example of 3 Karnaugh maps from this answer
  • one map represents single output
  • each represent its own logic circuit/equation
  • as you can see set1 and set2 are the same
  • X means output = 1
  • empty space means output = 0
  • sides are binary encoding of all inputs combinations

The simplification

  • is done by extracting the equation from map
  • so find minimal count of areas to cover all X or spaces
  • which one depends either on used logic or which are simpler to select
  • for example set1 is active only if both a and b are active
  • so: set1=a.b
  • set3 can be extracted like this:
  • set3=a+b by selecting x
  • set3=!((!a).(!b)) by selecting the spaces

[notes]

  • . AND
  • + OR
  • ! NOT
  • selections can overlap borders