A standard/popular class to easily manage truth tables in C++?

Question

Given a truth table with 5 inputs and one output, with a function prototype like:

bool compute(bool in1, bool in2, bool in3, bool in4, bool in5);

Is there somewhere, in the STL or other library, a class that allows to easily and efficiently manage the implementation of such a function?

In particular, the idea would be to be able to easily code the truth table with a kind of array like this:

some_type truth_table = [[0,0,0,0,0,0],
[0,0,0,0,1,1],
[0,0,0,1,0,1]
...];

Ideally, the class could "optimize" the truth table by avoiding unnecessary row evaluation.

This post and this post start to answer the question but using custom macros/implems.

Answer 1

If you want to check if all the supplied values are true, you could make a variadic function template and do a fold over logical AND:

template<class... Args>
constexpr bool compute(Args&&... bools) {
    return (... && static_cast<bool>(bools));
    //     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  fold over &&
}

bool result = compute(true, true, true, true);

A 1D array version could look like this:

template<class some_type, std::size_t N>
constexpr bool compute(const some_type(&arr)[N]) {
    return [&]<std::size_t... Is>(std::index_sequence<Is...>) {
        return (... && static_cast<bool>(arr[Is]));
    }(std::make_index_sequence<N>());
}

bool result = compute({true, true, true, true});

For arrays with an arbitraty number of dimensions:

template <class some_type, std::size_t N>
constexpr bool compute(const some_type (&arr)[N]) {
    if constexpr (std::rank_v<some_type> == 0) {
        // The same 1D array fold expression as above
        return [&]<std::size_t... Is>(std::index_sequence<Is...>) {
            return (... && static_cast<bool>(arr[Is]));
        }(std::make_index_sequence<N>());
    } else {
        // More than 1 dimension:
        return [&]<std::size_t... Is>(std::index_sequence<Is...>) {
            // recursively unwrap dimensions
            return (... && compute(arr[Is]));
        }(std::make_index_sequence<N>());
    }
}

some_type truth_table[2][3][6] = {{
                                        {1, 1, 1, 1, 1, 1},
                                        {0, 0, 0, 0, 1, 1},
                                        {0, 0, 0, 1, 0, 1},
                                    },
                                    {
                                        {1, 1, 1, 1, 1, 1},
                                        {0, 0, 0, 0, 1, 1},
                                        {0, 0, 0, 1, 0, 1},
                                    }};

std::cout << compute(truth_table) << '\n';

Ideally, the class could "optimize" the truth table by avoiding unnecessary row evaluation.

All of the above makes use of short-circuit evaluation and will stop the comparison at the first false encountered.

Answer 2

Is there somewhere, in the STL or other library, a class that allows to easily and efficiently manage the implementation of such a function?

Yes. The input to your function can construct a std::array<bool, 5>, and your truth table a std::set<std::array<bool, 5>>. Wrapped up in a class, to hide the modifiers of table:

class TruthTable
{
public: 
    TruthTable(std::set<std::array<bool, 5>> table = {}) : table(table) {}

    bool compute(bool in1, bool in2, bool in3, bool in4, bool in5) { return table.contains({ in1, in2, in3, in4, in5, }); }
private:
    std::set<std::array<bool, 5>> table;
};

To generalise this, you could extract the 5 out into a template parameter:

template <size_t N>
class TruthTable
{
public: 
    TruthTable(std::set<std::array<bool, N>> table = {}) : table(table) {}

    template <typename... Args>
    requires (sizeof...(Args) == N)
    bool compute(Args... args) { return table.contains({ args... }); }
private:
    std::set<std::array<bool, N>> table;
};

Or as bitmask suggests, you can represent it with std::bitsets

template <size_t N>
class TruthTable
{
public: 
    TruthTable(std::initializer_list<std::bitset<N>> strings = {}) 
    {
        for (auto string : strings) table.set(string.to_ullong());
    }

    bool compute(std::bitset<N> string) { return table.test(string.to_ullong()); }
private:

    std::bitset<1<<N> table;
};

Answer 3

If you have a set of only five input bits, there can be only 2^2^5 = 2^32 different functions.

The encoding of a binary function taking five bool inputs is therefore -- std::uint32_t. More generally, std::bitset<1<<N>.

---

What does that mean?

For example if you have only two boolean values you have 2^2^2 = 16 different functions being encodable in 4 bits (instead of 32). How do we decode the function? Easy, take the numerical representation of the input values (as bits) and access that bit in the function's number:

Input: (1,0), Function: 0110b
10b = 2
0110b
 ^--- bit 2 == 10b

The same applies to five bits, but the number is just longer:

Input (0,0,1,0,1), Function: 10101011101110101110110101010101b
                                                       ^-- bit 5 == 00101b

The implementation is trivial, branch-free and minimal with respect to required memory.

If you have hand-implemented constexpr functions you could even extract the binary representation at compile-time and build a database this way.

Answer 4

Just to mention, the tool on this website implements the basic algorithm to generate a binary formula from the output values of a truth table with an arbitrary number of inputs. You enter the boolean sequence of outputs and the formula is visible in the upper left corner. You can then select the "PROGRAMMING" mode to have the correct operators. Then you just have to substitute the names of the given inputs (a,b,c etc...) by the name of the parameters of your function (in1, in2, in3...).

For instance the output sequence 00110101 gives

f(a,b,c)= (a && c) || ( ~a && b)

then after manual substitution you can have the code (for three inputs only):

return (in1 && in3) || ( ~in1 && in2);