# Minimum number of perceptrons for an n-bit truth table?

Suppose I have a Boolean function that maps N bits to one bit. If I understand correctly, this function will have 2^2^N possible configurations of its truth table.

What is the minimum number of neurons and hidden layers I would need in order to have a multi-layer perceptron capable of learning all possible truth tables? I found one set of lecture notes here that suggests that "checkerboard" shaped truth tables (which is something like an N-input XOR function) are hard to learn, but do they represent the worst-case scenario? The notes suggest that such tables require 3(N-1) neurons arranged in 2 log_2(N) hidden layers

Now, I varied the hidden layer nodes from 64 to 1024. The cost decreased, indicative of correct learning but the accuracy did not change, howsoever I tried (changing learning rates, using momentum, etc). It was either giving all 1's or all 0's, even though I was using the same set for training and validation. The reason I hypothesized for this behavior was:
• Due to the 1 and 0 nature of the input the NN was not able to create a correct boundary. Since if it created an equivalent feature of x^3 using its nodes, it'll just output the same constant value again and again f(0) and f(1), where it should have been a nice little curve