Truth-tables

A \(k\)-ary truth-table represents an operation \(f:V^k \to \mathsf{Power}(V)\), where \(V\) is a a non-empty finite collection of values. For example, the truth-table for classical conjunction over the set of values \(\{\mathrm{F},\mathrm{T}\}\) (which plays the role of \(V\)) is presented below:

\(x\)

\(y\)

\(\land\)

F

F

F

F

T

F

T

F

F

T

T

T

In our library, each truth-table implements the interface ct4l::TruthTableI, holding a non-negative integer indicating its arity, and a pointer to a ct4l::Domain, intended to represent the collection \(V\). The template parameter determines what is the type of the values of the domain. Internally, only integers are stored and manipulated. To the user, we provide methods that allows to mention the domain values, but also the internal (integer) values.

Note

We opted to use a pointer to a domain instead of a plain object envisioning the possibility of considering groups of truth-tables sharing the same domain (as is the case of truth-tables representing interpretations in an algebra). To facilitate the creation of truth-tables, however, we have provided constructors which takes concrete objects and deals internally with the conversion to a pointer type.

The implementation of the truth-table interface provided for now follows the principles below:

  • instead of storing the truth-table mappings as correspondences between tuples and integers, we use the position of the tuples in the lexicographical order as indices;

  • not every mapping is stored, but only those whose output differs from a default output value, given by the user or somehow inferred by one of the constructors.

For instance, the classical truth-table for \(\land\) presented above would store only a single mapping: the value \(3\) mapping to \(1\) (since the tuple \((1, 1)\) is the fourth in the lexicographical ordering of pairs over \(\{0,1\}\)), in case it is informed that the default output is \(\{0\}\). Notice that we only mentioned integers, while the given table for \(\land\) has \(\{\mathrm{F},\mathrm{T}\}\) as values. This is not a problem as the pointer to the domain object allows us to perform translations between the representations.

Constructing truth-tables

We provide many ways to build truth-tables:

  • by specifying the domain, the arity and a default output, lefting the specification of the mapping for later:

    ct4l::TruthTable<std::string> and_table {
    {"F", "T"},             // domain
    2,                      // arity
    {"F"},                  // default output
};
and_table.set({"T","T"}, {"T"});
  • by specifying the domain, the arity, a default output and specific mappings:
    ct4l::TruthTable<std::string> and_table {
    {"F", "T"},             // domain
    2,                      // arity
    {"F"},                  // default output
    {
        {{"T","T"}, {"T"}}  // specific mapping
    }
};

  • by specifying the domain, the arity and specific mappings (the default output will be taken as the most frequent output in those mappings):

    ct4l::TruthTable<std::string> and_table {
    {"F", "T"},             // domain
    2,                      // arity
    {
        {{"T","T"}, {"T"}}  // specific mapping
        {{"F","F"}, {"F"}}  // specific mapping
        {{"F","T"}, {"F"}}  // specific mapping
    }
};

  • by specifying only the domain and specific mappings (the default output will be inferred as in the previous item, and the arity will be taken to be the size of the first input tuple in the specific mappings list):

    ct4l::TruthTable<std::string> and_table {
    {"F", "T"},             // domain
    {
        {{"T","T"}, {"T"}}  // specific mapping
        {{"F","F"}, {"F"}}  // specific mapping
        {{"F","T"}, {"F"}}  // specific mapping
    }
};

  • by specifying a domain, an arity and a function that takes input tuples over the domain values and indicates the outputs:

    ct4l::TruthTable<std::string> and_table {
    {"F", "T"},
    2,
    [](const std::vector<std::string>& args) -> std::set<std::string> {
        if (args[0] == "T" and args[1] == "T") return {"T"};
        else return {"F"};
    }
};

Note

The choice of which constructor you will use depends on whether you want to enforce some characteristic in the construction of the truth-table. For example, if you want to build a binary truth-table and the mappings are given by the user, you can specify the arity in the construction so that an error is thrown in case the user provides mappings with input tuples of sizes other than \(2\).

Let us fix the following truth-table for the next sections:

ct4l::TruthTable<std::string> or_table = {
    {"F", "T"},
    {
        {{"T","T"}, {"T"}}
        {{"T","F"}, {"T"}}
        {{"F","F"}, {"F"}}
    }
};

Manipulating truth-tables

We provide methods for manipulating truth-tables in terms of the domain values, via the methods ct4l::TruthTableI::at() and ct4l::TruthTableI::set():

or_table.at({"T","F"}); // returns the set {"T"}
or_table.set({"T", "T"}, {"T","F"}); // add non-determinism at input {"T", "T"}

Also, in terms of the internal values, via the methods ct4l::TruthTableI::ati() and ct4l::TruthTableI::seti():

or_table.ati({0,0}); // returns the set {0}
or_table.seti({1, 0}, {1, 0}); // add non-determinism at input {1, 0}

Iterating over truth-tables

The interface for truth-tables implements an iterator that produces the so-called determinants, which are objects intended to represent independently the rows of a truth-table. We use by default the internal representation (in terms of integers), but each determinant may hold a pointer to a domain, allowing for the translation of the internal values to the domain values during the iteration. A determinant also implements the unary operator operator*(), which performs this translation automatically if a domain in present.

Granted this iterator, we can use a forach loop to iterate over all determinants of a truth-table:

for (auto& det : or_table) {
    auto args = det.arguments; // the input tuple in the row in internal values
    auto output = det.output; // the output set in the row in internal values
    ...
}

Alternatively, we could use the structured binding syntax:

for (auto& [args, output, domain] : or_table) {
    ...
}

If we want to work with the domain values, we could just to the following:

for (auto& det : or_table) {
    auto [args, output] = *det;
    ...
}

API

template<typename T>
struct ct4l::Determinant

Represents a row of the truth-table in terms of the internal representation.

Used when iterating over the truth-table. Allows from converting the internal values into domain values by a call to the unary operator *.

Author

Vitor Greati

Public Functions

inline Determinant()

Empty constructor.

inline Determinant(decltype(domain) domain)

Constructor that takes only the domain of values.

Parameters

  • domain: a pointer to the domain

inline Determinant(const decltype(arguments) &arguments, const decltype(output) &output, decltype(domain) domain = nullptr)

Full contructor: takes the arguments, the output and a pointer to the domain.

Parameters

  • arguments: row input

  • output: row output

  • domain: pointer to the domain

inline bool operator==(const Determinant &other) const

Compare for equality.

Return

if both are equal

Parameters

  • other: rhs

inline bool operator!=(const Determinant &other) const

Compare for inequality.

Return

if both are not equal

Parameters

  • other: rhs

inline bool operator<(const Determinant &other) const

Compare for less.

Return

if lhs < rhs

Parameters

  • other: rhs

inline DomainDeterminant<T> operator*() const

Uses the information of the domain to translate the determinant to domain values.

Return

the translated determinant

Public Members

std::vector<int> arguments

Row inputs.

std::set<int> output

Row output.

std::shared_ptr<Domain<T>> domain

Pointer to the domain.

template<typename T>
class ct4l::TruthTableI

Interface for a truth-table with non-deterministic outputs.

It is assumed that values are internally represented as integers. A pointer to a ct4l::Domain is expected, allowing to represent truth-tables over non-integer values.

Author

Vitor Greati

Subclassed by ct4l::TruthTable< T >

Public Functions

TruthTableI(decltype(_domain) domain, const decltype(_arity) &arity)

Base constructor for truth-tables, which takes pointer to an already created domain.

Parameters

  • domain: a pointer to a domain

  • arity: the arity of the truth-table

TruthTableI(const std::vector<T> &domain_values, const decltype(_arity) &arity)

Base constructor for truth-tables, which takes a vector of domain values.

Internally, there must be the production of a pointer to a ct4l::Domain from the given domain values.

Parameters

  • domain_values: takes the domain values

  • arity: the arity of the truth-table

virtual std::set<int> ati(const std::vector<int> &input) const = 0

Access the output of the table in terms of the internal representation.

Return

the output in internal representation

Parameters

  • input: the input tuple in internal representation

virtual std::set<T> at(const std::vector<T> &input) const = 0

Truth-table image at the given input tuple.

Return

the truth-table image at the input tuple

Parameters

  • input: input tuple

inline std::set<T> operator[](const std::vector<T> &input) const

Truth-table image at the given input tuple.

Syntax sugar for ct4l::TruthTableI::at(const std::vector<T>&) const .

Return

the truth-table image at the input tuple

Parameters

  • input: input tuple

virtual void seti(const std::vector<int> &input, const std::set<int> &output) = 0

Allows to assign the output of the table in terms of the internal representation.

Parameters

  • input: the input tuple in internal representation

  • output: new output in terms of internal representation

virtual void set(const std::vector<T> &input, const std::set<T> &output) = 0

Set the truth-table image at the given input tuple.

Parameters

  • input: input tuple

  • output: desired output at the input tuple

inline decltype(_arity) arity() const

Truth-table arity.

Return

the arity of the truth-table

inline decltype(_domain) domain() const

Truth-table domain.

Return

the truth-table domain

inline Iterator begin()

Produces an iterator pointing to the first determinant of the truth-table.

Return

an iterator to the beginning of the truth-table

inline Iterator end()

Produces an iterator pointing to the last determinant of the truth-table.

Return

an iterator to the beginning of the truth-table

struct Iterator

A truth-table iterator.

Produces determinants (internal representation) at each iteration. Covers the entire truth-table.

Author

Vitor Greati

Public Types

using iterator_category = std::forward_iterator_tag

The category of the iterator.

using difference_type = std::ptrdiff_t

Difference type of the iterator.

using value_type = Determinant<T>

Value returned by the iterator.

using pointer = std::shared_ptr<Determinant<T>>

Type of pointer.

using reference = Determinant<T>&

Type of reference.

Public Functions

inline Iterator(int position, TruthTableI &tt)

Initialize the iterator.

Parameters

  • position: the row position

  • tt: the corresponding truth-table

inline void update(pointer current, int position)

Updates the current pointer according to a given position.

Parameters

  • current: pointer to the current determinant

  • position: the new position of the row

inline reference operator*() const

Return a reference to the current object.

inline pointer operator->()

Access the current current pointer.

inline Iterator &operator++()

Moves the iterator forward.

inline Iterator operator++(int)

Postfix moving operator.

Friends

inline friend bool operator==(const Iterator &a, const Iterator &b)

Test the equality of iterators.

inline friend bool operator!=(const Iterator &a, const Iterator &b)

Test the difference of iterators.

template<typename T>
class ct4l::TruthTable : public ct4l::TruthTableI<T>

A truth-table that stores its mappings as a map from integers into sets of integers.

It keeps the information of what value is to be taken as default, in case the map does not inform the output for a given input.

Author

Vitor Greati

Public Functions

TruthTable(std::shared_ptr<Domain<T>> domain, const int &arity, const std::set<T> &default_domain_output)

Base constructor for truth-tables.

Parameters

  • domain: pointer to a domain

  • arity: the arity of the truth-table

  • default_domain_output: an output to be given when no mapping was indicated for a given input

TruthTable(const std::vector<T> &domain_values, const int &arity, const std::set<T> &default_domain_output)

Base constructor for truth-tables.

Parameters

  • domain_values: the domain values

  • arity: the arity of the truth-table

  • default_domain_output: an output to be given when no mapping was indicated for a given input

TruthTable(std::shared_ptr<Domain<T>> domain, const int &arity, const std::set<T> &default_domain_output, const std::function<std::set<T>(std::vector<T>)> &initializer)

Constructor that accepts a pointer to a domain, an arity, a default output and an initilizer, which is a function that takes domain arguments and answer with an domain output corresponding to that arguments.

Parameters

  • domain: a pointer to a domain

  • arity: the truth-table arity

  • default_domain_output: default output

  • initializer: a mapping from arguments (in domain values) to outputs

TruthTable(const std::vector<T> &domain_values, const int &arity, const std::set<T> &default_domain_output, const std::function<std::set<T>(std::vector<T>)> &initializer)

Constructor that accepts a vector of domain values, an arity, a default output and an initilizer, which is a function that takes domain arguments and answer with an domain output corresponding to that arguments.

Parameters

  • domain_values: the collection of domain values

  • arity: the truth-table arity

  • default_domain_output: default output

  • initializer: a mapping from arguments to outputs

inline TruthTable(std::shared_ptr<Domain<T>> domain, const int &arity, const std::function<std::set<T>(std::vector<T>)> &initializer)

Constructor that accepts a pointer to a domain, an arity, and a initilizer, which is a function that takes domain arguments and answer with an domain output corresponding to that arguments.

Parameters

  • domain: a pointer to a domain

  • arity: the truth-table arity

  • initializer: a mapping from arguments to outputs

inline TruthTable(const std::vector<T> &domain_values, const int &arity, const std::function<std::set<T>(std::vector<T>)> &initializer)

Constructor that accepts a vector of domain values, an arity, and a initilizer, which is a function that takes domain arguments and answer with an domain output corresponding to that arguments.

Parameters

  • domain_values: the collection of domain values

  • arity: the truth-table arity

  • initializer: a mapping from arguments to outputs

TruthTable(std::shared_ptr<Domain<T>> domain, const int &arity, const std::set<T> &default_domain_output, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts pointer to a domain, an arity, a default ouput and a map specifying the mappings of the truth table.

Parameters

  • domain: pointer to a domain

  • arity: the truth-table arity

  • default_domain_output: default output

  • initializer_map: a mapping from arguments to outputs

TruthTable(const std::vector<T> &domain_values, const int &arity, const std::set<T> &default_domain_output, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts vector with domain values, an arity, a default output and a map specifying the mappings of the truth table.

Parameters

  • domain_values: values of the domain

  • arity: the truth-table arity

  • default_domain_output: default output

  • initializer_map: a mapping from arguments to outputs

TruthTable(std::shared_ptr<Domain<T>> domain, const int &arity, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts pointer to a domain, an arity, and a map specifying the mappings of the truth table.

Parameters

  • domain: pointer to a domain

  • arity: the truth-table arity

  • initializer_map: a mapping from arguments to outputs

TruthTable(const std::vector<T> &domain_values, const int &arity, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts vector with domain values, an arity, and a map specifying the mappings of the truth table.

Parameters

  • domain_values: values of the domain

  • arity: the truth-table arity

  • initializer_map: a mapping from arguments to outputs

TruthTable(std::shared_ptr<Domain<T>> domain, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts a pointer to a domain and map indicating the mappings of the truth-table.

Infers the default mapping as the most frequent value in the mappings and the arity as the arity of the first input tuple in the mappings.

Parameters

  • domain: the collection of domain values

  • initializer_map: a mapping from arguments to outputs

TruthTable(const std::vector<T> &domain_values, const std::map<std::vector<T>, std::set<T>> &initializer_map)

Constructor that accepts a vector to domain values and a map indicating the mappings of the truth-table.

Infers the default mapping as the most frequent value in the mappings and the arity as the arity of the first input tuple in the mappings.

Parameters

  • domain_values: the collection of domain values

  • initializer_map: a mapping from arguments to outputs

virtual std::set<T> at(const std::vector<T> &input) const override

Truth-table image at the given input tuple.

Return

the truth-table image at the input tuple

Parameters

  • input: input tuple

virtual void set(const std::vector<T> &input, const std::set<T> &output) override

Set the truth-table image at the given input tuple.

Parameters

  • input: input tuple

  • output: desired output at the input tuple

virtual std::set<int> ati(const std::vector<int> &input) const override

Allows to assign the output of the table in terms of the internal representation.

Return

a reference to be receive the value

Parameters

  • input: the input tuple in internal representation

virtual void seti(const std::vector<int> &input, const std::set<int> &output) override

Access the output of the table in terms of the internal representation.

Return

the output in internal representation

Parameters

  • input: the input tuple in internal representation