truth table to boolean algebraic equation

[daxxin2002]

I have corrected a few errors,the code compiles and excutes for sure.

how do one convert a truth table to boolean equation,I can convert the other way round like below;

//Suppose Z = (A.B + C)'
  public class Boolean
      {

      public static void main(String[] args)

{       
        int    a,b,c,z;

         System.out.println("A B C Z"); 
           for(a = 0;a<=1;a++)
           for(b = 0;b<=1;b++)
           for(c = 0;c<=1;c++)
     }
           z = ~((a & b|c)  & 1;    

System.out.println(a +" "+b+" "+c+" "+ z); 
}
      }
         }

OutPut

A B  C Z
0 0  0 1
0 0  1 0
0 1  0 1
0 1  1 0
1 0  0 1
1 0  1 0
1 0  0 0
1 1  1 0

Just want to convert the table back to boolean equation

[iamthwee]

Couldn't u use karnaugh mapping, or apply the axioms for boolean simplification?

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[iamthwee]

Google for ...

Quine-McCluskey algorithm

me thinks. It's hardly trivial tho, especially if you have an arbitary number of input variables. Tee he he

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[iamthwee]

Not sure if you're still pondering this, but I am ;)

Essentially, there are two steps to using the Quine-McClusky
Al-Gore-it-him.

http://en.wikipedia.org/wiki/Quine-McCluskey_algorithm

Step 1: finding prime implicants

Step 2: prime implicant chart

I've managed to find the source code for step one.

Qmc.java

/**
 * Quine und McCluskey
 *
 */

// exception class
class ExceptionQuine extends Exception {
  ExceptionQuine(String str) {
    super(str);
  }
}

// einschlägiger index
class MinTerm {

  // externe daten repräsentation
  public static final char NOT_CH = '0';
  public static final char SET_CH = '1';
  public static final char ANY_CH = '*';

  // interne daten repräsentation
  protected static final int NOT =  0;
  protected static final int SET =  1;
  protected static final int ANY = -1;

  // attribute
  protected int count;
  protected int[] term;

  // konstruieren & einlesen
  public MinTerm(String str) {
    term = new int[str.length()];
    for (int i = 0; i < str.length(); i++) {
      switch (str.charAt(i)) {
        case NOT_CH: term[count++] = NOT; break;
        case SET_CH: term[count++] = SET; break;
        case ANY_CH: term[count++] = ANY; break;
      }
    }
  }

  // konvertierung in string
  public String toString() {
    StringBuffer buf = new StringBuffer(count);
    for (int i = 0; i < count; i++) {
      switch (term[i]) {
        case NOT: buf.append(NOT_CH); break;
        case SET: buf.append(SET_CH); break;
        case ANY: buf.append(ANY_CH); break;
      }
    }
    return buf.toString();
  }

  // vergleiche minterm
  public boolean isSame(MinTerm a) throws ExceptionQuine {
    if (count != a.count) throw new ExceptionQuine("MinTerm::isSame()");
    for (int i = 0; i < count; i++) {
      if (term[i] != a.term[i]) return false;
    }
    return true;
  }

  // anzahl der unterschiede
  public int resolutionCount(MinTerm a) throws ExceptionQuine {
    if (count != a.count) throw new ExceptionQuine("MinTerm::resolutionCount()");
    int resCount = 0;
    for (int i = 0; i < count; i++) {
      if (term[i] != a.term[i]) resCount++;
    }
    return resCount;
  }

  // position des ersten unterschiedes
  public int resolutionPos(MinTerm a) throws ExceptionQuine {
    if (count != a.count) throw new ExceptionQuine("MinTerm::resoutionPos()");
    for (int i = 0; i < count; i++) {
      if (term[i] != a.term[i]) return i;
    }
    return -1;
  }

  // kombinieren zweier min-terme
  public static MinTerm combine(MinTerm a, MinTerm b) throws ExceptionQuine {
    if (a.count != b.count) throw new ExceptionQuine("MinTerm::combine()");
    StringBuffer buf = new StringBuffer(a.count);
    for (int i = 0; i < a.count; i++) {
      if (a.term[i] != b.term[i]) buf.append(ANY_CH);
      else buf.append(a.toString().charAt(i));
    }
    return new MinTerm(buf.toString());
  }

}

class Quine {

  // konstanten
  protected static final int MAX_TERMS = 0xff;

  // attribute
  public MinTerm[] terms = new MinTerm[MAX_TERMS];
  public int count = 0;

  // min-term hinzufügen
  public void addTerm(String str) throws ExceptionQuine {
    if (count == MAX_TERMS) throw new ExceptionQuine("Quine::addTerm()");
    terms[count++] = new MinTerm(str);
  }

  // konvertierung in string
  public String toString() {
    StringBuffer buf = new StringBuffer();
    for (int i = 0; i < count; i++) {
      buf.append(terms[i] + "\n");
    }
    return buf.toString();
  }

  // ist ein bestimmtes element vorhanden
  public boolean hasTerm(MinTerm a) throws ExceptionQuine {
    for (int i = 0; i < count; i++) {
      if (a.isSame(terms[i])) return true;
    }
    return false;
  }

  // vereinfachen der funktion
  public void simplify() throws ExceptionQuine {
    while (reduce() > 0);
  }

  // reduzieren der minterme
  private int reduce() throws ExceptionQuine {

    // variabeln
    int reducedCount = 0;
    MinTerm[] reducedTerms = new MinTerm[MAX_TERMS];
    boolean[] used = new boolean[MAX_TERMS];

    // alle minterme bearbeiten
    for (int i = 0; i < count; i++) {
      for (int j = i + 1; j < count; j++) {

        // terme suchen, die sich nur in einer position unterscheiden
        if (terms[i].resolutionCount(terms[j]) == 1) {
          reducedTerms[reducedCount++] = MinTerm.combine(terms[i], terms[j]);
          used[i] = true; used[j] = true;
        }

      }
    }

    // unveränderte minterme ebenfalls in die neue liste kopieren
    int totalReduced = reducedCount;
    for (int i = 0; i < count; i++) {
      if (used[i] == false) {
        reducedTerms[totalReduced++] = terms[i];
      }
    }

    // initialisieren
    count = 0;

    // liste speicher (ohne doubletten)
    for (int i = 0; i < totalReduced; i++) {
      if (!hasTerm(reducedTerms[i]))
        terms[count++] = reducedTerms[i];
    }

    // anzahl der reduzierungen liefern
    return reducedCount;

  }

}

public class Qmc {

  static public void main(String arg[]) throws ExceptionQuine {

    // test daten erstellen
    Quine quine = new Quine();

    // minterme hinzufügen

    
 //Using OP's example
 /*
  *OutPut
A B C Z
0 0 0 1 <--tag
0 0 1 0
0 1 0 1 <--tag
0 1 1 0
1 0 0 1 <--tag
1 0 1 0
1 0 0 0
1 1 1 0
  **/

quine.addTerm("000");
quine.addTerm("100");
quine.addTerm("100");


    // vereinfachen und ausgeben
    quine.simplify();
    System.out.println(quine);

  }

}

Step two shouldn't be that much more difficult to implement.

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[Lord Soth]

Hi,

Do you need the optimal (most simplified) equation ? If not you can easily write the equation as the sum of products : a'b'c'z+a'b'cz'+a'bc'z+...

Loren Soth

[iamthwee]

>Do you need the optimal (most simplified) equation

I think minimization is the key point here, otherwise the exercise is trivial.

:?:

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[Lord Soth]

Hi,

In case minimization is important then check http://www.c-sharpcorner.com/Code/2003/Feb/GAAdderDesign.asp . I have a more advanced GA implementation for logic circuit optimization, which uses total transistor count as part of evaluation function.

Loran Soth

[iamthwee]

>In case minimization is important...I have a more advanced GA implementation for logic circuit optimization

It's interesting that you say that. Since the Quine-McCluskey Al-gore-it-him is regarded as NP-complete, the runtime grows exponentially.

Using GAs (genetic Al-gore-it-hims)will yield potentially non-optimal solutions however, will significantly reduce runtime, especially when n, the number of input variables, is large.

In regards to the OP's problem, I'd say the QMC algo is the easiest way forward, if n is small. Although, he hasn't responded since he posted so I really don't no.

:sad:

I reckon the optimal answer to be z = b'c' + a'bc' [IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[iamthwee]

Oopsie I think the optimal solution is actually z = a'c' + b'c'

:)

I have a typo in the source, it should be...

quine.addTerm("000");
quine.addTerm("010");
quine.addTerm("100");

And the OP made a mistake here :)

A B C Z
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 0 0 0  <-- Should be 1 1 0 0
1 1 1 0

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[Lord Soth]

Hi,

I think a'c'+b'c' can further be simplified. Currently it consists of 7 boolean operators (4 not, 2 and, 2 or; but of course on circuit implementation you won't implement c' twice so you will use 6 gates)
Using DeMorgan's Rule a'c'+b'c' = (a+c)'+(b+c)' = ((a+c)(b+c))' (4 bool.op. 4 logic gates)
In actual implementation on PCB things change a lot, for example you might use NAND only or NOR only implementations (by emulating AND,OR and NOTs with them) which may result on fewer gates (less power consumption+delay) after optimization but on the formula (w/ and,or,not) looks like less optimized. Till here we assumed you are going to use stock IC gates (78xx TTL series) or xilinix like FPGA, so working on gate count basis.
But the optimization possibilities gets even deeper if you are dealing with VLSI design. At that point you have finer granularity by working on individual transistor basis and the distinct borders around the logic gates disappear. Now you can have direct optimization towards propagation delay, transistor count, power consumption, heat dissipation,die/waffer size or fan-in fan-out aspect. As you stated these all are NP-Complete problems; so only heuristics (less-optimal, too hard and time consuming), expert systems or GA can work.
Those are the real deal, but currently I have to deal with non-sense unrelated academics by memorizing no-good aaaaaaaaaaaaaadvanced math for proving things on queue delays on networks, which are already common sense and can be expressed with a single plain english sentence. How ironic is this ?

Lord Soth

[iamthwee]

>I think a'c'+b'c' can further be simplified. ..Using DeMorgan's Rule a'c'+b'c' = (a+c)'+(b+c)' = ((a+c)(b+c))' (4 bool.op. 4 logic gates)

I guess so, I assume step 2 of the QMC algo, which I left out would have established the same thing? In any case I was just looking into this on the fly.

>Till here we assumed you are going to use stock IC gates (78xx TTL series) or xilinix like FPGA, so working on gate count basis.
But the optimization possibilities gets even deeper if you are dealing with VLSI design. At that point you have finer granularity by working on individual transistor basis and the distinct borders around the logic gates disappear. Now you can have direct optimization towards propagation delay, transistor count, power consumption, heat dissipation,die/waffer size or fan-in fan-out aspect.

You sound like ur the life and soul of a party kiddo. Heh heh ;)

>Those are the real deal, but currently I have to deal with non-sense unrelated academics by memorizing no-good aaaaaaaaaaaaaadvanced math for proving things on queue delays on networks, which are already common sense and can be expressed with a single plain english sentence. How ironic is this ?

It's called math, they like to make it harder than it actually is. :rolleyes:

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[sammynove]

pls my project is about boolean function minimization and the resulting logic circuit diagram. can u help me on it. reply via [e-mail]