Showing all boolean functions can be expressed by only conjunctions or negations

Question

Let $f:$ {T,F}$^n \rightarrow$ {T,F}, i.e a function of n boolean variables.

Show that each $f$ can be expressed as a formula of only conjunctions and negations, and give an upper bound for the number of conjunctions aswell as a lower bound.

For example n=2 has 2^4=16 different functions and I can express them all using only conjunctions and negations. But, for the general case I'm really lost on how to proceed.

Answer 1

Welcome to MSE!

Hint:

You mention in the comments that you're proceeding by brute force for the $16$ functions when $n=2$... What's preventing you from doing this in the general case?

Given $n$ variables you have a (big) truth table with $2^n$ rows.

• Can you find a way to implement any particular row? That is, can you find a combination of $\land$s and $\lnot$s which gets a fixed row correct?
• Can you then modify each row function to be $0$ if you plug in a different row of the truth table, but still give the correct answer on your row of interest?
• Once you have these, can you show that "or-ing" all of the rows together will give you the function you want?

You might take inspiration from the Lagrange Interpolation Formula. In fact, the problem you're describing is exactly showing that every boolean function is a polynomial over $\mathbb{Z}/2$!

---

I hope this helps ^_^