![[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 defines the truth table and the corresponding boolean function. In the previous 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. CNF 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. This does not appear to be the case.
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
By algorithmic complexity, the vast majority of truth tables are random (i.e., the shortest representation of the truth table, is the truth table itself).
The 3-SAT problem is a mapping problem from 3-CNF expressions to truth tables (Does the expression map to the zero truth table?). As shown for five variables, the number of unique 3-CNF expressions is much less than the total number of truth tables.
What happens with more than five variables? What is the number of unique truth tables for 3-CNF of n variables?
If 3-SAT must test each enumeration, then the mapping has a random component (i.e., there does not exist efficient rules for the mapping). Is randomness then a property of even relatively small subsets (e.g., the subset of truth tables of 3-CNF expressions). Is the boundary between randomness and non-randomness the same as the boundary between 3-SAT and 2-SAT?
