Search: id:A112535
Results 1-1 of 1 results found.

%I A112535
%S A112535 256,43146,120510132
%N A112535 Number of truth tables generated by 3-CNF expressions of n variables.
%C A112535 For n=5, computing the number of 3-CNF 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.
%H A112535 C. B. Barber, <a href="http://www.qhull.org/download/ttcnf-2005.1.zip">
               ttcnf 2005.1</a> (April 2005).
%H A112535 C. B. Barber, <a href="http://www.qhull.org/ttcnf">www.qhull.org/ttcnf</
               a>.
%o A112535 The following program generates all truth tables of k-CNF expressions 
               of n variables:
%o A112535 start with the truth table (2^2^n) - 1 //e.g., 0xFFFF for n=4
%o A112535 for each new truth table //e.g., 0xFFFF
%o A112535 for each (n choose k) variables //e.g., a, c, d
%o A112535 for each (2^k) clause of these variables //e.g., (a or not c or not d)
%o A112535 generate a truth table from the clause and previous truth table //e.g., 
               NewTT = PrevTT and (...)
%o A112535 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'.
%Y A112535 Cf. A109457, A112650, A000157, A000371, A000613, A000618, A003181.
%Y A112535 Sequence in context: A017212 A018798 A017320 this_sequence A132637 A114850 
               A017440
%Y A112535 Adjacent sequences: A112532 A112533 A112534 this_sequence A112536 A112537 
               A112538
%K A112535 bref,hard,nonn
%O A112535 3,1
%A A112535 C. Bradford Barber (bradb(AT)shore.net), Dec 13 2005

Search completed in 0.001 seconds