For a set $S\subseteq\{0,1\}^n$, I want to make a CNF boolean formula $\phi$ such that for $ a=( x_1,...,x_n)$ we have $\phi(a)=1$ if and only if $a\in S$. I would also like to know what the size of this formula will be as a function of $n$.
So far I only know how to construct a DNF, by letting the clauses correspond to each of the elements in $S$, and it is of size $n|S|$, but I'm not sure how to get a CNF from this.
I would greatly appreciate any suggestions on how to proceed.
Concerning the DNF, you are entirely correct, but I'll write $a = (a_1,\dots,a_n)$. Now, consider a DNF $\psi$ such that we have $\psi(a) = 1 \Longleftrightarrow a \in \{0; 1\}^n \setminus S$.
It is easy to put $\varphi := \neg \psi$ into its CNF $\phi$ :
with the convention $\neg^x := \epsilon$ (the empty word) if $x$ is even and $\neg^x := \neg$ if $x$ is uneven we have $$\psi = \bigvee_{a \notin S} \Big( \bigwedge_{1 \leqslant i \leqslant n} \neg^{a_i + 1} X_i \Big) $$ $$\varphi = \neg \psi \equiv \bigwedge_{a \notin S} \Big( \bigvee_{1 \leqslant i \leqslant n} \neg^{a_i + 2} X_i \Big) =: \phi $$
$\phi$ has the required property and is roughly of the same size as $\psi$, namely of size $n (2^n - |S|)$.