Combinations, permutation matrices, and a solution to n-valued valuations (truth value assignments for many-valued logics).

This result can be interpreted as a solution to n-valued valuations (truth value assignments for many-valued logics). A detailed proof is given in a later post.

First we define and construct the extensional valuation function , (intuitively, it can be thought of as the generating function for the classical truth table). The valuation function θ will have dimensions (k = 2ⁱ rows by i columns), and the value of each binary entry is given by the following formula, as can easily be checked.

Example θ(7,2), represented on a truth table exhausting all valuations (truth value assignments) for 3 propositional variables (atomic formulae). CORRECTION --- the formula works for the table generated such that zeros come before ones, i.e. with the ones and zeros inverted, so the table below is generated incorrectly for this formula, as we should start with zeros first. (Consequently all the m-valued generalizations should be generated analogously --- starting with the smallest value.)

This map, i.e. θ can be generalized to m-ary truth values. The explicit formula is given below:

I've skipped examples here, naturally since the truth matrices get very large, very quick.

Those explicit solutions to the recursive definitions (truth tables) make computation significantly more efficient. They also turn out to be handy (they're both elegant and compact) when writing algorithms for k combinations on n sets, or k partitions on n sets. They should prove useful to anyone working in writing algorithms for systems based on multiple value assignments.

Proof (sketch) --- a detailed proof is given in a later post.
First we express the truth tables as recurrence relations of congruences modulo the number of truth values in that given logic, then solve them by iteration, i.e. see the pattern. Finally give the solutions an elegant form (ceiling notation) using some useful number theoretic identities. QED