Universal Decision Elements in 4-valued Logic

That was the question my tutor John Loader invited me to help him answer in 1972 - the final year of my Computer Science course at Brighton Polytechnic, now aggrandised Brighton University. Little did I imagine I would try and complete the challenge forty years later.

It was quite a challenge fitting it all into an IBM 1130, but the program worked and found lots of universal decision elements (UDEs), and it seemed that only a lack of run time prevented the program getting to the answer. I left Brighton Poly, worked for IBM for many years and eventually retired.

Roll the clock on 40 years. One day I chanced upon a carbon copy (remember them?) of the thesis I'd written in 1972.

With plenty of time on my hands I thought it might be interesting to rewrite the program and run it on my infinitely more powerful laptop and after all these years get the answer. The thesis included a summary of the program logic, though not the code itself, and fortunately also the initial UDE that John Loader had provided.

It had been a long time since I'd written any Fortran, but I downloaded the Silverfrost Fortran Compiler (thank you) and, like riding a bike, it soon came back.

1. The Theory

For anyone unfamiliar with them, what Universal Decision Elements (UDEs) are and John Loader's method for discovering them.

2. The Program

3. The Results

So, how many first order universal decision elements of four argument places are there in 4-valued logic?

The Theory

A first order universal decision element (UDE) in m-valued logic is a formula that can simulate all of the unary functors that exist in that m-valued logic.

In 2-valued logic unary functors are easy to understand. For example NOT(0) is 1 and NOT(1) is 0. "NOT" is a unary functor: a function that acts on one operand. If we choose P to represent the operand, when P is 0, NOT(P) is 1; when P is 1, NOT(P) is 0. If we write this as a "truth table" we get:

In 4-valued logic each operand can have 4 values, say 0,1,2,3. Unary functor number 6, for example, which we will write as U₆, has this truth table:

In 4-valued logic there are 256 unary functors. The output of each unary functor is simply one of the 256 possible combinations of 0,1,2,3. The first few and the last of the 256 unary functors are:

A first order Universal Decision Element of 4 argument places is a formula containing 4 variables F(P₁,P₂,P₃,P₄) (where the Ps can have the values 0,1,2,3 or P, and there must be at least one P) which can simulate all 256 unary functors.

For example, say F(0,3,1,P) gives the result 0,0,0,2 when P takes the values 0,1,2,3 respectively. I.E:

F(0,3,1,0) is 0
F(0,3,1,1) is 0
F(0,3,1,2) is 0
F(0,3,1,3) is 2.

This is the same result as U₃(P). And let's say that substituting F(P,P,3,1) in this same formula gives the result 0,0,2,1 as P takes the values 0,1,2,3, which is the same result as U₁₀(P). If this formula F(P₁,P₂,P₃,P₄) can thus simulate all 256 unary functors it is called a Universal Decision Element (UDE).

The question is: how many of these Universal Decision Element formulae are there?

One way to find out would be to test the truth table for every possible formula and see if it can simulate all 256 unary functors. The trouble is there are rather a lot of them:

Each formula F(P₁,P₂,P₃,P₄) has 256 lines (we will call the lines "entry points") in its truth table:

P₁ P₂ P₃ P₄
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 1 0
0 0 1 1
0 0 1 2
0 0 1 3
0 0 2 0
0 0 2 1
0 0 2 2
0 0 2 3
etc until line 256 where P₁,P₂,P₃,P₄ all have the value 3.

Now, the result of line (entry point) 1 could be 0, 1, 2 or 3, so the first line in the truth table could be:

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 0
or
0 0 0 0 1
or
0 0 0 0 2
or
0 0 0 0 3

Since each of the 256 results in the truth table can take the value 0,1,2 or 3, the number of possible truth tables is 4x4x4... 256 times. I.E. there are 4²⁵⁶ possible truth tables. That is a huge number - more atoms than there are in the universe - and testing each one to see if it is a UDE would take for ever: the calculations would still be running long after the end of the universe. So a faster method is required.

Suppose, for one of these 4²⁵⁶ F(P₁,P₂,P₃,P₄) formulae, we substitute 0,0,0,P in place of P₁,P₂,P₃ and P₄. This substitution uses entry points 1,2,3 and 4 in the truth table: as P takes the values 0,1,2,3, F(0,0,0,P) becomes F(0,0,0,0), F(0,0,0,1), F(0,0,0,2), F(0,0,0,3). Further, suppose for illustration that this substitution gives the result 1,3,2,0 for values 0,1,2,3 of P. (Which, by the way, is the same result as unary functor number 120.) The first 4 of the 256 lines in the truth table for this particular formula F(P₁,P₂,P₃,P₄) would be:

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 1
0 0 0 1 3
0 0 0 2 2
0 0 0 3 0

Clearly, every substitution will give the same result as some unary functor or other, but for the formula to qualify as a Universal Decision Element (UDE) each of the 256 unary functors must be simulated by at least one of the substitutions.

However, there are 369 possible substitutions of 0,1,2,3,P in F(P₁,P₂,P₃,P₄) such that there is always at least one P, e.g. F(0,0,0,P), F(P,P,3,1), F(P,P,P,P). But there are only 256 unary functors. So a UDE will simulate some of the unary functors (UFs) with more than one substitution. Again, for illustration:

Now, in the above illustration, unary functor 3 is simulated by substitution number 1 which is F(0,0,0,P). [* See Numbering.] This substitution uses entry points 1,2,3 and 4 in the truth table. I.E. the first 4 lines in the truth table for this particular UDE are:

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 0
0 0 0 1 0
0 0 0 2 0
0 0 0 3 2
etc to line 256

If we now mark as used all the entry points that are used by unary functors that are simulated by only one substitution, and we strike these unary functors from the list of unary functors, we would be left with a list of unary functors which are simulated by more than one substitution, and the list of entry points showing which has been used.

The remaining unary functors are simulated by two or more substitutions. Suppose we now simulate these remaining unary functors by choosing, wherever possible, substitutions that only use entry points that have already been used. When we have thus judiciously chosen a substitution for all of the 256 unary functors it could be that some entry points have not been used at all. And indeed this often turns out to be the case.

So let us suppose that for a particular formula F(P₁,P₂,P₃,P₄) we can simulate all the unary functors without using entry point 1. We can therefore put any value we like in entry point 1 and the resulting 3 additional formulae will all be UDEs:

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 0
0 0 0 1 2
0 0 0 2 3
0 0 0 3 3
etc to line 256

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 1
0 0 0 1 2
0 0 0 2 3
0 0 0 3 3
etc to line 256

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 2
0 0 0 1 2
0 0 0 2 3
0 0 0 3 3
etc to line 256

P₁ P₂ P₃ P₄ F(P₁,P₂,P₃,P₄)
0 0 0 0 3
0 0 0 1 2
0 0 0 2 3
0 0 0 3 3
etc to line 256

However, we can now take each of the 3 new formulae and start the process again, calculating which unary functor each substitution simulates. We know that all 3 of these new formulae can simulate all 256 unary functors, but let's say that one of the new formulae can do so using entry point 1 but leaving entry points 8 and 174 unused. That means we can now change the values at those two entry points in the new formula which will yield a further 16 formulae (one of which is the one we started with). Clearly, by repeating the above process we can generate more and more new UDEs.

Though it's a little more complicated than the above would suggested. Suppose unary functor 1 can be defined either by substitution 254 or 39. Further, suppose using substitution 254 leaves entry points 4 and 163 unused, and using substitution 39 leaves entry point 80 unused. Choosing to use substitution 254 means we can generate 16 UDEs by varying the values at entry points 4 and 163, and choosing substitution 39 means we can assign any of the values 0,1,2,3 to entry point 80. So that's 20 new UDEs in all - though two of these will be the formula we started with.

And of course it could well be that there are several unary functors each of which can be simulated by several substitutions. This implies many permutations of substitutions are possible to simulate those unary functors, each permutation potentially delivering a set of unused entry points.

Note. Strictly speaking, of course, what we are going to be finding are not the formulae that correspond to universal decision elements, but rather their truth tables.

2. The Program

Generate as many UDEs as possible from the first UDE, generate all possible UDEs from those, compare to those already generated and store any that are new, and so on until every UDE has been examined. This approach, although simple, is very time consuming. And it turns out that the number of UDEs is very large and even storing them all on a laptop would be difficult.

So, rather than adopt this 'brute force' method, the program takes another approach. It analyses the starting UDE and determines the sets of unused entry points it yields. Each of these UDE/unused-entry-point sets is stored. Then each stored UDE/unused-entry-point set is analysed to produce more UDE/unused-entry-point sets, each time comparing new UDE/unused-entry-point sets (UDE/EP sets) to those already stored to avoid storing duplicates.

One further wrinkle: a given formula F(P₁,P₂,P₃,P₄) will usually produce several sets of unused entry points, eg:

But the UDEs produced from set 4, which only contains entry point 172, will also be produced from set 2 (80, 172, 202). So the set consisting just of entry point 172 can be ignored. Similarly set 1 (80, 215) is a subset of set 3 (80, 94, 215). So only sets (80, 172, 202) and (80, 94, 215) need to be stored. I.E. for any given starting UDE we ignore subsets of unused entry points.

UDE/unused-entry-point (UDE/EP) sets are read from file (the udefile) into an in-memory array. [** See Initialisation.] Each UDE/EP set is held as 20 integers, each integer storing 13 values of 0-4, where 4 represents an unused EP. (There's quite a bit of MOD 5 arithmetic in the program.)

The first as yet unprocessed UDE/EP set in the array is found. From this starting UDE/EP set, new UDEs are generated by assigning all possible combinations of values to its unused entry points. For example, if entry points 132 and 319 are unused, we will generate 16 UDEs.

Each of the 369 substitutions is examined to see which unary functor it makes the UDE simulate. For example, let us look at substitution F(1,P,0,P). Assigning each value of P yields:
1 0 0 0
1 1 0 1
1 2 0 2
1 3 0 3

We look up what the value of the UDE is at each of these entry points. Let us suppose that for the UDE being examined the values at these four entry points are 0,0,0,3. That corresponds to unary functor number 4. I.E. for this UDE, this particular substitution simulates unary functor number 4.

By examining all 369 substitutions we build a table showing, for each unary functor, which substitution(s) simulate it.

(We then check that all 256 unary functors have at least one substitution, i.e. that this UDE is indeed a UDE. This is always the case. However this was a useful check during program development and serves as an always-on regression test.)

The table of unary functors and substitutions is examined. For unary functors that have only one substitution, the entry points used by its substitution are marked as used, and those unary functors are marked as defined.

Next, each of the unary functors which have more than one substitution is checked to see if any of its substitutions use only entry points that have already been used. If so, those unary functors are also marked as defined.

For each unary functor that is still undefined, all of its substitutions are examined to see if they all use one of the as yet unused entry points. If they do, clearly that entry point will have to be used, so it is marked as used. The step described in the previous paragraph is then repeated to see if any of the as yet undefined unary functors can now be defined using the enlarged list of used entry points. If so, they are marked as defined. (Performing this paragraph's action before the action of the previous paragraph would avoid repeating the previous paragraph's step, but that way actually requires more calculations and runs slower: many more UFs would have to be examined in this step.)

We are now left with a number of as yet undefined unary functors and a list of as yet unused entry points.

For example. Let us suppose that the process above has defined all but three unary functors, 27, 34 and 217, and that they could be defined by the following substitutions:

These 3 last 'hardcore' unary functors could be defined using substitutions 2, 67 and 15; or 2, 67 and 34, for example. Clearly, there are 24 (3x4x2) ways these last unary functors can be defined.

Each permutation of substitutions is examined to see which of the as yet unused entry points it would use. If, after defining these last few unary functors with one of the permutations, there are still some entry points unused we have found a UDE/unused-entry-point (UDE/EP) set. So say, in our example, the first of the 24 permutations leaves entry points 57 and 255 unused.

This set of unused EPs is compared to sets of unused EPs previously found for this starting UDE, and this set of unused EPs is added to an array if it is not already there and it is not a subset of one already there. If it's a superset of previously discovered set(s) of unused EP for this starting UDE, those subset are deleted. The process is repeated for each of the (in our example 24) permutations of substitutions.

Then, each set of unused EPs in the table is used to make a UDE/EP set by taking the starting UDE and putting 4s into the unused EPs. This new UDE/EP set is added to an array of new UDE/EP sets generated in this superloop. (This two step process - maintaining a table of unused EP sets for the starting UDE and then generating UDE/EP sets and then checking for duplicate UDE/EP sets - is a lot faster than generating a UDE/EP set as soon as a set of unused EPs is produced.)

We then return to Point A above to generate the next UDE from our starting UDE/EP set.

When all (16 in our example) UDEs generated from the starting UDE/EP set have been examined we return to the paragraph just above Point A where the next as yet unprocessed UDE/EP set is selected from the in-memory array.

After processing a certain number (set by a parameter) of new UDE/EP sets, the array of new UDE/EP sets generated in this superloop is sorted and duplicates are deleted. Remaining UDE/EP sets are checked against old UDE/EP sets (held in an array) and any that are duplicates of old UDE/EP sets are deleted. The remaining UDE/EP sets are examined to eliminate subsets within them - subsets are deleted. Remaining UDE/EP sets are checked against old UDE/EP sets to see if any is a subset of an old UDE/EP set, or indeed whether any old UDE/EP sets are subsets of a new one. Subsets are deleted. (The sequence of these operations may seem odd, but has been found to be the fastest: finding subsets is slow.)

UDE/EP sets from both the old and new arrays are then written to the udefile, UDE/EP sets with the most unused EPs are written first. At the start of the next loop, the file is read into the in-memory array and the first as-yet-unprocessed UDE/EP set from the array will be processed, as we described above at the start of this "The Process" section. In this way, UDE/EP sets with the highest number of unused EPs will be processed first. Writing to the file every so often also provides a checkpoint restart capability.

Eventually, when all the UDE/EP sets on the file have been processed, we can calculate how many UDEs these stored UDE/EP sets represent.

Universal Decision Elements In Four Valued Logic

Webpages written: May 9th 2012 - December 2016 (on and off)

*Numbering: The numbering of entry points, unary functors and substitutions is arbitrary. We have chosen entry point 0000 to be number 1, unary functor 0000 to be number 1 and substitution 000P to be number 1.

**Initialisation: The process was initialised by using an initial known UDE supplied by J.Loader. It was J.Loader who originally devised the method of discovering UDEs that this program implements.

P	U₁(P)	U₂(P)	U₃(P)	U₄(P)	U₅(P)	...	U₂₅₆(P)
0	0	0	0	0	0		3
1	0	0	0	0	0		3
2	0	0	0	0	1		3
3	0	1	2	3	0		3

UF	Substitutions that simulate it
1	27 3
2	72 91 151
3	1
4	156 207 319
:
256	7 14 298

P	U₆(P)
0	0
1	0
2	1
3	1

Universal Decision Elements in 4-valued Logic

How many formulae corresponding to first order universal decision elements are there in 4-valued logic?

1. The Theory

2. The Program

3. The Results

The Theory

2. The Program