"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Wednesday, December 26, 2012

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 = 2i 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

1 comment:

china clay teapot said...

When the surfacCheap Ceramic Teapotse of the pot is finished (the needle), the water will dry faster, and vice versa.
2. It is related to the number of mud materials. The size of the mud of the pot itself (the higher the mesh is, the finer the sand is), the higher the soil of the pot is, the better the water will evaporate, and the slower the evaporation.
3, related to the type of the device. For example, Xi Shi pot, dragon egg pot, Authentic Purple Clay TeapotSiting pot, these pots basically do not have the opportunity