Can AND, OR and NOT be used to represent any truth table?
Yes, any truth-function, no matter how complex, and no mater how many inputs, can be expressed with $\land$, $\lor$, and $\neg$.
We can prove this directly by generating a conjunction for each row where the function evaluates to true, and then disjuncting of all of those conjunctions, and a second of thought will make it clear that the resulting expression captures the truth-function (if there is no row where the function evaluates to $T$, then just use the expression $P \land \neg P$)
For example, suppose we have a truth-function whose truth-conditions are given by the following table:
\begin{array}{ccc|c} P&Q&R&f(P,Q,R)\\ \hline T&T&T&F\\ T&T&F&T\\ T&F&T&F\\ T&F&F&T\\ F&T&T&T\\ F&T&F&F\\ F&F&T&F\\ F&F&F&F\\ \end{array}
This function is true in rows 2,4, and 5, and thus we generate the terms $P \land Q \land \neg R$, $P \land \neg Q \land \neg R$, and $\neg P \land Q \land R$ respectively. Disjuncting them gives us:
$$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)$$
This formula is said to be in Disjunctive Normal Form (DNF): it is a generalized disjunction, where each disjunct is a generalized conjunction of literals, and where a literal is either an atomic variable or the negation thereof.
Now, I think it should be clear from this example that you can do this for any truth-function. That is, any function can be represented using a DNF formula by generating a disjunction for each row where the function evaluates to $T$. For example, if the row is one where $P$ is True, $Q$ is True, and $R$ is false, say, then generate the expression $P \land Q \lor \neg R$. Once you have an expression for all of these rows, then conjunct them all together for the final expression. And if there is no row where the function evaluates to $T$, then just use the expression $P \land \neg P$, which is in DNF (it can be seen as a generalized disjunction with only one disjunct ... which is a conjunction of literals).
Thus, for any truth-function, there is a DNF expression that captures that function, and DNF only uses $\neg, \land, and \lor$
Just for comeplteness, I also want to point out that there is something called the Conjunctive Normal Form (CNF): this is a generalized conjunction, where each conjunct is a generalized disjunction of literals.
Can we find an expression equivalent to this function that is in CNF? Yes. There are two ways to do this. First, we can take the existing DNF expression and transform it into an expression that is in CNF, using Distribution of $lor$ over $\land$. In this case, that would actually be a pretty sizeable formula, starting with:
$(P \lor P \lor \neg P) \land (P \lor P \lor Q) \land (P \lor P \lor R) \land (P \lor \neg Q \lor \neg P) \land (P \lor \neg Q \lor Q) \land (P \lor \neg Q \lor R) \land (P \lor \neg R \lor \neg P) \land ...$
(see what I do here? I systematically find all combinations of picking one literal from each of the three disjuncts .. it works like FOIL, if you are familiar with that)
However, another way to do this is to go back to the original truth-table, and to focus on the cases where the function evaluates to False, rather than True. That is, the function is False exactly when:
$$(P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land \neg Q \land \neg R)$$
is True, and that means that the function is true exactly when:
$$\neg [(P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land \neg Q \land \neg R)]$$
is True. By DeMorgan, this is equivalent to:
$$(\neg P \lor \neg Q \lor \neg R) \land (\neg P \lor Q \lor \neg R) \land (P \lor \neg Q \lor R) \land (P \lor Q \lor \neg R) \land (P \lor Q \lor R)$$
and that expression is in CNF, i.e. in Layer-Form.
Again, I think it should be clear from this example that you can do this for any truth-function. That is, any function can be represented using a CNF formula by generating a disjunction for each row where the function evaluates to $F$. For example, if the row is one where $P$ is True, $Q$ is True, and $R$ is false, say, then generate the expression $\neg P \lor \neg Q \lor R$ (for this is the negation of $P \land Q \land \neg R$). Once you have an expression for all of these rows, then conjunct them all together for the final expression. If there is no row where the function evaluates to $F$, then just use the expression $P \lor \neg P$), which is in DNF (it can be seen as a generalized conjunction with only one conjunct ... which is a disjunction of literals).
We can also give a proof on the basis of the expressively completeness of the $NAND$. Since $P \ NAND \ Q \Leftrightarrow \neg (P \land Q)$, we can simply take whatever expression built up from only $NAND$'s that captures some truth-function $f$, and change any of those $NAND$'s, with $\neg$'s and $\land$'s, and the result will be equivalent to the original, and thus also capture $f$. Notice that this in fact shows that $\{ \neg, \land \}$ is expressively complete, so we don't need any $\lor$'s (of course, that should be obvious: if $\{ \land, \lor, \neg \}$ is expressively complete, and given that $P \lor Q \Leftrightarrow \neg (\neg P \land \neg Q)$, we can change any $\lor$ in any expression capturing some truth-function $f$ by a bunch of $\land$'s and $\neg$'s, and capture that truth-function as well). And of course we can likewise show that $\{ \lor, \neg \}$ is complete, and that immediately follwos from the $NOR$ being complete as well, since $P \ NOR \ Q \Leftrightarrow \neg (P \lor Q)$
Yes, they can. Given any truth table with a certain number of variables just find every possible configuration for which the output is True, then combine them all with OR. As an example, a function of three variables that returns True if at least two of the inputs are True can be represented as
$$ab\overline c \,\lor\,a\overline bc\,\lor\,\overline abc\,\lor\,abc$$ with juxtaposition meaning AND and an overline meaning negation.
This is known as the disjunktive normal form.