login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A112535 Number of truth tables generated by 3CNF expressions of n variables. 4
2, 4, 16, 256, 43146, 120510132, 4977694100656 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,1
COMMENTS
For n=5, computing the number of 3CNF truth tables took 2^32 bytes and 2^38 iterations. Computing the same number for n=6 may require 2^64 bits and 2^71 iterations.
I calculated a(6) using a different method; a(7) looks a lot harder. - Don Knuth, Dec 10 2012
REFERENCES
Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 148 and 220, Problem 191.
LINKS
C. B. Barber, ttcnf 2005.1 (April 2005).
C. B. Barber, www.qhull.org/ttcnf.
PROG
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'.
CROSSREFS
Cf. A034472, A109457 (corresponding sequences for 1CNF and 2CNF), A112650, A000157, A000371, A000613, A000618, A003181.
Sequence in context: A220169 A178077 A218148 * A001146 A114641 A152690
KEYWORD
nonn,hard
AUTHOR
C. Bradford Barber (bradb(AT)shore.net), Dec 13 2005
EXTENSIONS
a(6) from Don Knuth, Dec 10 2012
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:19 EDT 2024. Contains 370954 sequences. (Running on oeis4.)