How to get truth table of function (( c + ~d ) * b ) * ~( d + a * e )

Question

SO I have the equation (( c + ~d ) * b ) * ~( d + a * e ) of which I'm trying to generate a truth table but I'm unsure how I would even start with getting the program to compute whether or not the the variable should be equal to true or false according to the truth table. Any suggestions as how to do this? Thank you in advance.

#include<iostream>

using namespace std;

bool checkBoolTF(int a){
    bool TF;
    if(a == 0){
        TF = false;
    }
    else{
        TF = true;
    }
    return TF;
}

int main()
{
  int a,b,c,d,e;
  bool aBool, bBool, cBool, dBool, eBool;

  string equation = "(( c + ~d ) * b ) * ~( d + a * e )";
  bool equationTF;


  //LOOP TO TRUTH TABLE - FINAL VALUES
  cout << "----------------------------------------------------------------------" << endl;
  cout << "|  a  |  b  |  c  |  d  |  e  |  " << equation << "  |" << endl;
  cout << "----------------------------------------------------------------------" << endl;
    for(a=0;a<=1;a++){
        checkBoolTF(a);
            for(b=0;b<=1;b++){
                checkBoolTF(b);
                    for(c=0;c<=1;c++){
                        checkBoolTF(c);
                            for(d=0;d<=1;d++){
                                checkBoolTF(d);
                                    for(e=0;e<=1;e++){
                                        checkBoolTF(e);
                                        cout << "|  " << a << "  |  " << b <<  "  |  " << c <<  "  |  " << d <<  "  |  " << e << "  |                   "  << equationTF << "                |" << endl;
                                        cout << "----------------------------------------------------------------------" << endl;
                                    }
                            }
                    }
            }
    }
    return 0;
}

Answer 1

I would like to show an additional, already existing solution. It is well structured and commented. It is published at github. Please see here

The intended purpose of this program is to calculate MCDC test pairs. But it does of course also all that you want. I do not recommend to copy and paste, but you could read and learn, how to do your implementation.

This code reads exactly the strings that you specified. It also creates a truth table. But this is only a minor part of the whole functionality.

So, what you need to do, is, to compile the string in something that could can be evaluated as a boolean expression.

For that, I first defined the input alphabet and the language, described by a grammar. Then, I created a compiler, consisting of a scanner (lexer), parser and code generator. Actually I created 2 compilers, with the same front end and 2 different back ends. So, 2 different code generators. One, for a virtual machine that can evaluate the boolean expression for any combination of input variables. And, the 2nd backend, will create an abstract syntax tree, with which I evaluate all possible MCDC test pairs.

As said, the first code generator creates Op code for a virtual machine. With this machine, the truth table and with that all minterms are calculated. Then Quine and McCluskey is used (2 different implementations) to minimize the boolean expression. And at the end, and optimzed version of Petricks method is used to solve the unate coverage problem and identify the minimum set of prime implicants.

The MCDC part is maybe a little bit too complex to explain here.

But the main message is, that you first need to parse your string and convert it in something executable.

Then you can evaluate whatever you want.

Answer 2

Step 1: Tokenize.

enum class TokenType {
  bracket, binop, binaryop, var, literal
};
struct Token {
  TokenType type;
  char value;
 };

convert the string to a vector of token.

You aren't using literal yet: it is the values 0 or 1. You'll use it later.

Write code that pretty prints a vector of tokens.

Step 2: make a simple tree.

struct Tree {
  bool is_token=true;
  Token token;
  std::vector<Tree> tree;
};

change your first code to generate a tree, containing a vector of tokens.

Write code that pretty prints it. Test.

Step 3: Reduce the tree

Step 3a: Brackets

Now do a reduction step; walks a vector of trees and generates one. It copies everuthing that isn't a bracket blindly to the output. If it sees a ( it copies everything until the matching ) (count open and closed) into a sub-tree, then copies that sub-tree into the output.

It takes "a ( b c )" and makes it a then b c in a subtree.

Write code that can pretty print subtrees. Test.

Step 3b: nested brackets

Next, recurse on the subtree you make, so its nested brackets also get put into subtrees.

Step 3c: operators

Next, work on operators. ~ is easy: it swallows the next tree in the vector. As + binds loser than *, for each + make two subtrees; one for everything before, one for everything after. Then do a pass dping the same for *.

After all this, you turn

a+(b+c)*~(d+e)

into

+  (a , ( * (+ (b, c), ~(+(d,e))))

Step 4: substitute

Map a std::map that maps the variable to a value. Take a copy of a tree, and walk it replacing each variable with a literal equal to its value.

Step 5: evaluate

For each operator, evaluate the subtree(s) then apply the operator.

The result should be a 0 or a 1.

4 and 5 can be done independently by starting with a literal expression.

Answer 3

So I have a personal program that implements this for a strings with a form "Ab|c(d|E)|fa"

my full source code is a complete mess and contains serveral other things I'm trying to do at the same time (failling to simplify the expression by circling kmaps and stuff)

However I can walk through what I've done if it helps

its setup to be easier for me to parse with capitals representing positive and lower case letters representing negation/not () representing sub expressions and [] representing negated sub expressions so the input string `"ABC(DEF)G(HI(KK)S[as][ge])S" is converted into this .repr() structure

AND(
  A
  B
  C
  AND( D E F )
  G
  AND(
    H
    I
    AND( K K )
    S
    NAND( !A !S )
    NAND( !G !E )
  )
  S
)

and something like "Ab|cb" is

OR(
  AND( A !B )
  AND( !C !B )
)

I have a object (I call expression) that contains information about its type stored in something like the following

namespace xpr { //expression types
enum typ {
    identity_,
    negation_,
    and_,
    or_,
    nand_,
    nor_
};
}


class expression{
...

    xpr::typ type = xpr::identity_;
    char value = ' ';
    std::vector<expression> sub_expressions;
...
};

and either a char that is its value or a vector of expressions. (and or nor nand expressions)

Parsing it into this expression form is done through nested constructors that keep passing the current position in the string as well as its level.

finally to answer your question

std::vector<char> vars = trackUsed();
    // equivalent to a set but more efficent to do the sort/unique at the end one time.
removeDuplicates(vars);

const auto truth_table_width = vars.size();
const auto truth_table_size = (size_t)std::pow((size_t)2, truth_table_width); // 2^width
expression::test_type test; // abc through !a!b!c
test.reserve(truth_table_width);
for ( const auto &v : vars ) {
    // value_type is value: 6, sign: 2 so character has to fit in 6bits and sign in 2.
    // minus 'A' to make A-Z 0-26
    test.emplace_back(v - 'A', xpr::negative);
}   

for ( size_t i = 0; i < truth_table_size; i++ ) {
    for ( size_t j = 0; j < truth_table_width; j++ ) {
        // converts 0 to negative and 1 to positive
        test[j].sign = (xpr::sign_type)((i >> j) & 0x1);
    }
    bool valid = testValues(test);
    if ( valid ) {
        sum_of_products.push_back(test);
    }
}

I set up a truth table by extracting all the characters used removing duplicates and sorting them. making a vector<vector< implmentation defined object >> incrementing a value to the max truth table width and using the sign bit of that value to populate the truth table - 0 = [0, 0, ... 1 = [1, 0, ... 2 = [0, 1, ... etc and then looping through the outer vector and sending the inner vector to a "testValues" member function that is specialized for each expression type

// given A true B true C true see if whole expression evaluates to true. 
bool expression::testValues(const potion::test_type& values) const {
    if ( this->is_simple() ) {
        auto val = std::lower_bound(values.begin(), values.end(),
                                    this->value,
                                    [ ](potion::val_type lhs, char rhs) -> bool {return lhs < rhs; }
        );
        if ( type == xpr::identity_ ) return (*val).sign;
        if ( type == xpr::negation_ ) return !(*val).sign;
    }
    if ( type == xpr::and_ || type == xpr::nand_ ) {
        const bool is_and = type == xpr::and_; //used to combine and and nand expressions and return the oposite val for nand
        for ( const auto& e : sub_expressions ) {
            if ( e.testValues(values) == false ) return !is_and; // short circuit- if b is false then abc is false
        }
        return is_and;
    }
    if ( type == xpr::or_ || type == xpr::nor_ ) {
        const bool is_or = type == xpr::or_; //used to combine or and nor and return the oposite val for nor
        for ( const auto& e : sub_expressions ) {
            if ( e.testValues(values) == true ) return is_or; // short circuit- if b is true then a|b|c is true
        }
        return !is_or;
    }
    throw std::runtime_error("Expression can't be simplified. Type not valid"); //should never happen
    return false;
}

There's obviously tons and tons of boilerplate code/ parsing code that's probably not the best. And if you want to parse strings using the "custom language" you are defining "(( c + ~d ) * b ) * ~( d + a * e )" then the parsing code will obviously be a lot different.

Anyway I hope this is helpful for your project. TLDR: might be a bit harder to implement than you initially thought. Although everything I've done is functional the code isn't the cleanest and its heavly setup for my specific case- only obtaining the truth table entries that have are positive and storing them in a sum of product that can be processed further.

Answer 4

For a start, you can simplify the checkBoolTF function to something like:

bool checkBoolTF (int a)
{
    return !(a==0);
}

Secondly, it seems like in the for loops, the values returned by this function are not being assigned to anything and are therefore lost. So you probably want to define an aux variable:

bool auxA = checkBoolTF(a);

and so on..