Fast small truth tables

by Manfred von Thun

Abstract: This note describes how small Joy sets (of up to 32 members) can be used to encode the lines in a truth table for up to five propositions. This results in a surprisingly simple method of providing truth table tests for the modal status of formulas (or other modal predicates).

Contents:

Truthfunctional and set-theoretic operations

Truth tables are the simplest way to determine the modal status of a formula: if it is true in all lines then it is a tautology, if it is false in all lines then it is a contradiction, and if it is true in some lines and false in others then it is contingent. The truthfunctional connectives are normally taken to operate on the two truth values, true and false. There is an obvious relationship between the connectives in a formula and the set of lines in the truth table in which the formula is true: The set of lines in which the negation of a formula is true is just the set-theoretic complement of the lines in which the formula itself is true, the set of lines in which the conjunction of two formulas is true is just the set-theoretic intersection of the lines in which both component formulas are true, and so on.

Hence, instead of evaluating a formula line by line in the truth table, one could just use the set-theoretic operations to determine the set of lines in which the formula is true. Whether this is efficient depends on the relative speed of the truthfunctional (one-bit) operations and the set-theoretic (many-bit) operations. Most computers now have word-wide Boolean operations and 32 or even more bits per word. And so, set-theoretic operations on sets of up to 32 or even more members are as efficient as the truthfunctional operations. This can be exploited for truth tables, and it has the potential of improving performance of small truth tables by a factor of up to 32, and even higher for larger size words. With 32 bits per word, a single word can codify the set of lines of a truth table generated by five propositions .

Of course nothing can escape the eventual exponential explosion. For six propositions the truth table has 64 lines, and, as always, any additional proposition doubles the size. So, a six proposition truth table would need to be encoded in two words, and then it doubles. However, the 32-fold increase in speed will hold no matter how many words are needed for the truth table. Moreover, computers with 64-bit words are already becoming more common, and 128-bit words are not far off. Indeed, some machines already have 128-bit registers, and a few can operate on several such registers in one cycle.

The rest of this note illustrates the general principle, using just one 32-bit word per truth table, and hence is restricted to a maximum of 5 propositions per table.

Set operations in Joy

The language Joy has small sets of (generally 32) integers from 0 onwards (generally up to 31). These integers can be taken to be the line numbers of a truth table, starting with line number 0.

What is needed, for each atomic proposition, is the set of line numbers of the lines in which that proposition is true. In the usual way of writing truth tables, these are the five guide columns. In setlib.joy, the standard Joy library for (small and large) sets, there is a module ss for small (32-bit) sets which contains, among others, just the right definitions for the current purpose. These definitions are here reproduced for convenience:

    s1  == { 0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 };
    s2  == { 0  1  4  5  8  9 12 13 16 17 20 21 24 25 28 29 };
    s4  == { 0  1  2  3  8  9 10 11 16 17 18 19 24 25 26 27 };
    s8  == { 0  1  2  3  4  5  6  7  8 17 18 19 20 21 22 23 };
    s16 == { 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 };

The names for these sets have been chosen because they are descriptive for general use, but they are not customary in logic. Moreover, since these sets are defined inside a module, they would have to be referenced as ss.s1, ss.s2, ss.s4 and so on. But this is easily overcome by some definitions, chosing p, q, r and so on. Also, it is necessary to load the setlib.joy library:

"setlib" libload.

DEFINE
  p == ss.s1; q == ss.s2; r == ss.s4; s == ss.s8; t == ss.s16.

Joy has the Boolean operators and, or and not, and they are defined for the two Boolean types of truth values and (small) sets. So these three can already be used for the operations on sets of lines.

But in logic one frequently uses material implication and material equivalence, and these operations will be needed. In the definition below they have been chosen as say, imp and iff. Also, a set of lines represents a tautology if and only if it comprises all lines if and only if it is the universal set. In the definition below the predicate 'tautology' is defined to be true if the complement of the set is empty:

DEFINE
  imp == [not] dip or;
  iff == [imp] [swap imp] cleave and popd;
  tautology == not null
END

Truth tables for Joy postfix formulas

No further definitions are needed. The Joy interpreter can now read formulas in Joy postfix notation and determine whether they are tautologies. It does so simply by executing them and then use the 'tautology' predicate to determine whether what is on top of the stack is the universal set:

p q imp p and  q  imp tautology.
true
p q imp q and  p  imp tautology.
false
p q or  p r imp  q s imp  and and   r s or   imp  tautology.
true
p q or  p r imp  q s imp  and and   r s and  imp  tautology.
false

A formula that is not a tautology is either contingent or it is a contradiction. It might be useful to have two more predicates for this. But simpler still is to have a function 'modality' which simply determines which of the three possibilities obtains:

DEFINE
  modality == 
    [ [ [null] "contradiction" ]
      [ [not null] "tautology" ]
      [ "contingent" ] ]
    cond
    popd
END

The use of this predicate is illustrated by the following three similar looking stock examples:

p p not and   modality.
"contradiction"
p q not and   modality.
"contingent"
p p not  or   modality.
"tautology"

Here are some more examples:

p q imp p and  q  imp modality.
"tautology"
p q imp p and  q  imp not  modality.
"contradiction"
p q imp q and  p  imp modality.
"contingent"
p q imp q and  p  imp not  modality.
"contingent"
p q imp  p not q imp  iff  modality.
"contingent"
p q imp  q not p not imp  iff  modality.
"tautology"
p q or  p r imp  q s imp  and and   r s or   imp  modality.
"tautology"
p q or  p r imp  q s imp  and and   r s or   imp  not  modality.
"contradiction"
p q or  p r imp  q s imp  and and   r s and  imp  modality.
"contingent"
p q or  p r imp  q s imp  and and   r s and  imp  not  modality.
"contingent"

Using minimally parenthesised infix notation

Reverse Polish notation may be second nature to Joy programmers, but it is not to logicians who would prefer a more familiar notation. The Joy system has a library symlib.joy for symbolic manipulation. It includes many translators from various notations to others. One familiar notation is infix, with precedences for the binary operators to minimise the need for parentheses. The translating function to reverse Polish is called Min2Rev. But the library has to be loaded, and it needs to be told which operators are to be used, and what their precedences are:

"symlib"  libload.

DEFINE
  unops == [not];
  bin3ops == [and];
  bin2ops == [or];
  bin1ops == [imp iff];
END

In the following the first item is a Joy tree representing a formula in minimally parenthesised infix notation. This is then translated into a quotation of the same formula in Joy notation. The i combinator then executes the quotation, with the result that the top of the stack is now the set of lines in the truth table in which that formula is true. The tautology predicate then determines whether that set is the set of all lines, just as before:

[ [p imp q] and p  imp  q ] Min2Rev i tautology.
true
[ [p imp q] and q  imp  p ] Min2Rev i tautology.
false

But it is more convenient not to have to specify the translation operator and the i combinator every time:

DEFINE
  Mtautology == Min2Rev i tautology;
  Mmodality  == Min2Rev i modality
END

[ [p imp q] iff [not p or q] ]  Mtautology.
true
[ [p imp q] iff [not q or p] ]  Mtautology.
false
[ [p or q] and [p imp r] and [q imp s]  imp  [r or s] ]  Mmodality.
"tautology"
[ [p imp q] iff [q imp p] ]  Mmodality.
"contingent"

[ [ [p imp q] and [q imp r] and [r imp s] and [s imp t] ]
  imp [p imp t] ]
Mmodality.
"tautology"

[ [[p imp q] and [q imp r] and [s imp r] and [s imp t]]
  imp  [p imp t] ]
Mmodality.
"contingent"

Using Cambridge notation

In the symlib.joy library there is also a translator from Cambridge (or Lisp) style notation to Joy notation. The translator is called Cam2Rev, and it is useful to define the following operators straight away:

DEFINE
  Ctautology == Cam2Rev i tautology;
  Cmodality  == Cam2Rev i modality
END

Here are a few tests:

[ iff [not [or p q]]  [and [not p] [not q]] ]  Ctautology.
true
[ imp [and [imp p q] [imp q r]]  [imp p r] ]  Cmodality.
"tautology"
[ imp [and [imp p q] [imp r q]]  [imp p r] ]  Cmodality.
"contingent"

Other applications

Testing whether the modal status of a single formula is not the only thing one might do. Another obvious application would be a fixed database as a premise, and then several queries as conclusions to determine whether certain facts can be deduced from the database. Not so obvious would be a reverse example, which tests, for several inputs, whether a fixed conclusion follows – and even gives advice accordingly.

For the advice to be at all meaningful, the usual single letter atomic formulas are not so intuitive. It is preferable to use multi-letter formulas, and their lines in the truth table now have to be defined as before:

DEFINE 

  raining == ss.s1; windy == ss.s2; cold == ss.s4; 
  hot == ss.s8; humid == ss.s16; 

  badweather == 
    [ raining and windy  or  cold and windy  or 
      raining and cold  or  hot and  humid ] 
END

Since from inconsistent data anything follows, no advice should be given at all and an appropriate warning should be supplied. Also, a warning should be given if the information was not sufficient to give any kind of advice:

DEFINE
  takeadvice == 
    Min2Rev i 
    [ null ] 
    [ "inconsistent data" ] 
    [ badweather Min2Rev i 
      [ [ [and null] "go out" ] 
        [ [imp not null] "stay home" ] 
        [ "insufficient data" ] ] 
      cond ] 
    ifte 
    popd 
END

Finally then, here is the glorious application:

[ raining and not cold and not [humid or raining] ]     takeadvice. 
"inconsistent data"
[ windy and hot and not [hot and not windy] and not raining ]   takeadvice. 
"insufficient data"
[ cold and windy ]                      takeadvice. 
"stay home"
[ not [windy or raining or humid] ]             takeadvice. 
"go out"