Complete generators in 4-valued logic and Rousseau's results

Abstract

One of central problems of $k$-valued logic is identification and construction of complete generators (Sheffer functions). This problem is solved in 3-valued logic but is not solved in 4-valued logic. We prove Slupecki's theorem for functions with partial ranges and use it to construct complete generators of the functions. We use Rousseau's theorem to construct complete generators of functions with all ranges. For both cases we calculate the numbers of generators for every diagonal of the generators and give the minimal and maximal generators. We find that the number 9 of one-ary functions used by Rousseau can be decreased to 3. The number of generators of functions with ranges of cardinal 2 equals 41 760, the number of generators of functions with ranges of cardinal 3 equals 32 969 664, and the number for cardinal 4 equals 942 897 552.