![[ttcnf-3-new]](eg/ttcnf-3-new.jpg)
ttcnf - Truth Table CNF URL: http://www.qhull.org/ttncf
ttcnf - Truth Table CNF Ttcnf computes all truth tables of CNF boolean expressions with one to five variables. It counts these truth tables in a number of ways. These results may be useful in understanding CNF expressions.
The following sections define the ttcnf program and summarize the results for 1-CNF, 2-CNF, 3-CNF, 4-CNF, (n-1)-CNF, n-CNF, and CNF.
The ttcnf program is a C/assembler program compiled for Windows. For a list of options, run 'ttcnf'. For five variables, it needs a gigabyte of data. It runs well on a two gigabyte computer. The output of ttcnf is comma-delineated text. View the output with Excel using Window>FreezePanes to keep the header visible.
A truth table is a enumeration of n boolean variables and the result of executing a boolean function of these variables. For example, the truth table for x and y is:
x y x and y 0 0 0 0 1 0 1 0 0 1 1 1
Since the input enumeration is mechanical, the result column, x and y, defines the truth table and the corresponding boolean function. For this truth table, the result column is the number 0x8 in hexadecimal or 0b1000 in binary.
Conjunctive normal form (CNF) is a canonical representation of boolean functions. Conjunctive normal form is the conjunction of disjunctive clauses. Disjunctive clauses use the not and or operators, while conjunction is the and operator. A CNF expression is k-CNF if each clause contains k variables. An example of 2-CNF is (a or b) and (not c or d).
A CNF expression is satisfiable if there exists an assignment of variables for which the expression is true. For example, (a or b) and (not c or d) is true if a and d are true.
k-SAT is the problem of testing satisfiability for k-CNF expressions. Clearly k-SAT can be solved by testing each possible assignment of the variables. Is there a faster way? There is a faster way if k<3, but it appears to be false for other k.
Ttcnf explored the possibility that 3-CNF produced so many truth tables that it had to include random truth tables. If so, the mapping from 3-CNF to truth table would have to be random, requiring exhaustive testing of the inputs.
The results indicate that 3-CNF expressions generate a relatively small number of truth tables. If, as is widely believed, 3-SAT is intrinsicly hard to compute, then 3-CNF truth tables may be incompressible and hence random. If so, randomness may be a pervasive property of the natural numbers.
The following program generates all truth tables of k-CNF expressions of n variables:
start with the truth table (2^2^n) - 1 //e.g., 0xFFFF for n=4 for each new truth table //e.g., 0xFFFF for each (n choose k) variables //e.g., a, c, d for each (2^k) clause of these variables //e.g., (a or not c or not d) generate a truth table from the clause and previous truth table //e.g., NewTT = PrevTT and (...)
Bit operations allow an efficient implementation of the last step. If you represent each variable by its truth table, A, B, ..., in 1-CNF, then the last step is 'NewTT = PrevTT and (A or B or C ...)'. For example, with four variables a, b, c, and d, the 1-CNF truth table for 'a' is 0xFF00, 'not c' is 0x3333, and 'not d' is 0x5555. The corresponding step is 'NewTT = PrevTT and 0xFFBB'.
If the last step takes unit time, the space and time complexity is O(2^2^n) and O(2^2^n * (n choose k) * 2^k) respectively, For 3-CNF truth tables of n variables, the space and time complexity is
n Space Time 3 2^8 2^11 4 2^16 2^21 5 2^32 2^38 6 2^64 2^71
For 1-CNF, two clauses always produces a contradiction and hence a non-satisfiable expression (e.g., a and not a).
The first column is the number of unique truth tables generated by 1-CNF expressions. The second column is the total number of truth tables (i.e., 2^2^n). The first column of the second table is the maximum number of clauses in a 1-CNF expression that generates a unique truth table. The second column is the minimum number of clauses in a non-satisfiable 1-CNF expression. The last column is the number of clauses that generates at least half of the unique truth tables.
n 1-CNF truth tables All truth tables 1 2 2 2 10 16 3 28 256 4 82 65,536 5 244 4,294,967.296
n 1-CNF clauses clauses to
first non-SATclauses to half of
the truth tables2 2 2 1 3 3 2 2 4 4 2 3 5 5 2 3
n 2-CNF truth tables All truth tables 2 16 16 3 166 256 4 4,170 65,536 5 224,716 4,294,967.296
n 2-CNF clauses clauses to
first non-SATclauses to half of
the truth tables2 4 4 2 3 5 4 3 4 6 4 4 5 10 4 5
n 3-CNF truth tables All truth tables 3 256 256 4 43,146 65,536 5 120,510,132 4,294,967.296
n 3-CNF clauses clauses to
first non-SATclauses to half of
the truth tables3 8 8 4 4 8 8 5 5 12 8 7
n 4-CNF truth tables All truth tables 4 65,536 65,536 5 2,805,252,934 4,294,967.296
n 4-CNF clauses clauses to
first non-SATclauses to half of
the truth tables4 16 16 8 5 16 16 9
In (n-1)-CNF, each clause has n-1 variables.
n (n-1)-CNF truth tables All truth tables 2 10 16 3 166 256 4 43,146 65,536 5 2,805,252,934 4,294,967.296
n (n-1)-CNF clauses clauses to
first non-SATclauses to half of
the truth tables2 2 2 1 3 4 4 3 4 8 8 5 5 16 16 9
In n-CNF, each clause has n variables. An n-CNF expression is a simple transformation of a truth table. Each distinct clause of an n-CNF expression corresponds to a 0-bit of the truth table. For example, bit 1 of the truth table for four variables is zero if and only if the n-CNF expression includes the clause 'a or b or c or not d'. Since a satisfiable expression contains at least one 1-bit in its truth table, n-CNF is satisfiable if and only if it is not 2^n distinct clauses.
As expected for n-CNF, ttcnf generates every truth table in 2^n clauses. The last clause generates truth table 0x0.
n n-CNF truth tables All truth tables 1 2 2 2 16 16 3 256 256 4 65,536 65,536 5 4,294,967.296 4,294,967.296
n n-CNF clauses clauses to
first non-SATclauses to half of
the truth tables2 4 4 2 3 8 8 4 4 16 16 8 5 32 32 16
n CNF truth tables All truth tables 1 2 2 2 16 16 3 256 256 4 65,536 65,536 5 4,294,967.296 4,294,967.296
n CNF clauses clauses to
first non-SATclauses to half of
the truth tables2 2 2 1 3 4 2 2 4 8 2 4 5 16 2 7
To test mixed 3-CNF and 2-CNF expressions, the 'keep' option for ttcnf can generate all 2-CNF expressions followed by one or more 3-CNF clauses. Pre-loading the truth tables with 2-CNF allows 3-CNF to converge slightly faster. Instead of generating all truth tables from 0xFFFFFF..., it has many starting points, one for each 2-CNF truth table.
For four and five variables, the 2-CNF clauses do not make a big difference. The same number of 3-CNF clauses are required to generate all of the truth tables. To generate half of the truth tables, two fewer clauses are required for four variables and one fewer clause for five variables.
Allowing any mix of 3-CNF and 2-CNF clauses behaves like 3-CNF alone (options 'kcnf 0x0305' and 'kcnf 0x0306' for n=4 and n=5 respectively). For five variables, it requires one fewer clause to generate half of the truth tables.
The ttcnf program has several bucketing options for counting truth tables. For example, 'nibble 3' divides the truth tables into 16 buckets by the nibble starting at bit 3. None of these options were helpful. The most interesting was 'lownibble'.
Consider a nibble of the bit string representing a truth table. For example, for 4 variables, a,b,c,d, consider nibble 'F' of 0x000F (the truth table for 'not a and not b').
With (n-1)-CNF the first n-2 variables can isolate a nibble, allowing the remaining variable to set the nibble to 0x3, 0x5, 0xa, 0xc. With two such clauses, the nibble may be set to 0x0, 0x1, 0x2, 0x4, and 0x8. With no clause, the nibble may be left at 0xf. Call these nibbles, the low nibbles (0x0,0x1,0x2,0x3,0x4,0x5,0x8,0xa,0xc,0xf). So, (n-1)-CNF can create any truth table composed of the low nibbles (e.g., 0x3cf2).
The option 'lownibble' shows the effect of low nibbles on truth tables. If a truth table contains a high nibble, it is assigned to the highest bucket, otherwise it is assigned to bucket i if it contains i non-zero low nibbles. For example, the truth table 0x3c02 is assigned to bucket 3.
For (n-1)-CNF there are 2^(n-2) nibbles with each nibble having one of ten values. So the number of low nibble truth tables is 10^(2^(n-2)). For four variables, low nibbles accounts for 23% of the (n-1)-CNF truth tables (10,000 out of 43,146). For five variables, low nibbles accounts for 3.6% of the truth tables (100,000,000 out of 2,805,252,934). It appears that low nibbles are decreasingly important as the number of variables increases. For (n-2)-CNF, the same construction applies to bytes instead of nibbles. While low-bytes can be identified, they only account for about 100,000 truth tables when n=5.
The number of new truth tables fits a Gaussian distribution. For 3-CNF, GraphPad computed the fit with an R^2 of 0.999 (see the previous links). The Gaussian distribution is visibly apparent, e.g. for 3-CNF of four variables:
num. clauses new truth tables 1 1 2 32 3 472 4 3392 5 11204 6 15184 7 9568 8 2928 9 365 10 0
Many problems are easy to test but expensive to solve. For example, the traveling salesman problem minimizes the distance travelled in visiting a set of cities. Computing the total distance for any particular route is easy: sum the distance for each leg of the trip. But computing the minimum distance appears to require a test for every possible route.
The travelling salesman problem, and many other problems, are equivalent to testing for satisfiability of a 3-CNF boolean expression. These problems are called NP-complete. It is widely believed that their solution requires more than polynomial time (abbreviated "P != NP"), but no one has been able to prove this statement.
Often the first step in understanding a problem is to analyze specific cases. Ttcnf provides the details for five or fewer variables. It generates the truth tables for every 3-CNF expression. A 3-CNF expression is satisfiable if its truth table is not zero (i.e., 0x000000...).
A sequence is incompressible if the shortest program to generate a sequence is the sequence itself. For example, '01010101....' is easily compressed (e.g., 'a thousand pairs of 0 and 1'). A simple proof shows that at least half of the numbers of n-bits are incompressible (search for Kolmogorov Complexity). A similar proof holds for any fixed number of additional bits (e.g., at least three quarters of the numbers of n-bits require a program of at least n-1 bits).
It is unlikely that a similar proof applies to 3-CNF expressions. As shown by ttcnf, the number of truth tables for 3-CNF expressions appears to grow much slower than the number of possible truth tables. Are these truth tables as incompressible as the incompressible numbers identified above?
[from news:comp.theory]
