Is the 3-CNF format used for the 3SAT problem able to represent any truth table(i.e. any other boolean formula)?
I am having trouble understanding how this can be the case. If there are 100 unique variables then the number of possibilities for truth tables would be:
(2^100 choose 1) -- One True Value
+ (2^100 choose 2) -- Two True values
+ (2^100 choose 3) -- Three True values
...
+ (2^100 choose (2^100 -1)) -- One False Value
+ (2^100 choose 2^100) -- All True
However the number of possible combinations of clauses would be:
((100 choose 3) * 8) choose 1 -- All single clauses
+ ((100 choose 3) * 8) choose 2 -- all 2 set clauses
...
+ ((100 choose 3) * 8) choose (((100 choose 3) * 8)-1)
+ ((100 choose 3) * 8) choose ((100 choose 3) * 8)
There is a much smaller number of sets of clauses than there is possible truth tables. How can they represent all of them if there all less possible values(Pigeonhole principle) and if they can't, what things cannot be represented using 3-CNF?
You cannot represent every Boolean function as a 3-CNF formula.
One concrete function that can't be expressed is $x\lor y\lor z\lor w$, where only one of the 16 possible inputs should produce "false" as an output. But each 3-atom clause that is not a tautology will force at least two results in the truth table to be false, and adding more clauses cannot change that.
The reason why 3-CNF is important in complexity theory is that every satisfiability problem can be converted into an equivalent 3SAT problem in polynomial time. Here "equivalent" means that you get a new formula that is satisfiable exactly if the original formula was. However, the new formula generally contains variables that were not present in the original one (the usual construction invents a new variable to contain the result of each subformula in the original formula). So it will not compute the same Boolean function as the one you started with.