Propositional Logic - Reducing the Number of Operations

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

enter image description here


enter image description here

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

enter image description here

and then Q


enter image description here

This reduced the number of operations (unary and binary) from 19

to 14

. New logic diagram for Q


enter image description here

Ideally, I would like there to be only negatives and disjunctions. Is there an algorithm to convert any sentence to my ideal simplified one? And is there an algorithm for introducing new proposals like the one above?


source to share

2 answers

There are about 50 years of research - there is still no standard method for multilevel logical synthesis. The two-level case can be successfully handled with Karnaugh maps or Quine McCluskey . Here the number of minterms is minimized. But this does not directly correspond to the number of logical operations required to determine the value of the function.

The University of California at Berkeley has developed several tools for generating heuristic decisions. Some of these tools are well packaged in Logic Friday 1


Input for your Q function:

Joined: Q: = (A and ((B and C) + (B 'and C'))) + (A 'and ((B and C) + (B' and C '))');

Minimization: Q: = ABC + A 'B' C + A 'BC' + AB 'C';

The result after the "matched to the gate" operation:

enter image description here

Note: The
later synth set is Clifford Wolf Yosys .



Yes there is a standard way to simplify the logical equation

  • this is the use of Karnaugh Map
  • here Karnaugh Maps for example 4 inputs
  • The idea is to encode the logic / circuit truth table into a rectangle matrix
  • Karnaugh Maps
  • this is an example of 3 Karnot cards from this one.
  • one card represents one pin
  • each presents its own logic / equation
  • as you can see set1 and set2 are the same
  • X

    means output = 1
  • empty space means output = 0
  • sides - binary coding of all combinations of inputs


  • performed by extracting the equation from the map
  • to find the minimum number of scopes to cover all X or spaces.
  • which depends either on the logic used or on which is easier to choose
  • For example, set1 is active only if a and b are active .
  • So: set1=a.b

  • set3 can be retrieved like this:
  • set3=a+b

    by choosing x
  • set3=!((!a).(!b))

    by selecting spaces


  • .

  • +

  • !

  • choices can overlap boundaries.


All Articles