Hi,
I am unsure under what category to post this question, as it relates more to logic (and computational theory) than straight mathematics.
Here it is:
Let G be the set of Propositional Formulas that can be built from the set of Propositional Variables {x_0, x_1, .....,x_236) and the connectives ~, <->. Prove that there is a boolean function from {0,1}^237 -> {0,1} that cannot be represented by a formula in G.
I am unsure under what category to post this question, as it relates more to logic (and computational theory) than straight mathematics.
Here it is:
Let G be the set of Propositional Formulas that can be built from the set of Propositional Variables {x_0, x_1, .....,x_236) and the connectives ~, <->. Prove that there is a boolean function from {0,1}^237 -> {0,1} that cannot be represented by a formula in G.