Boolean function construction

Question

I need some proof on this statement that not every boolean function is equal to a function constructed by only using ∨ and ∧. I need a boolean function that does not constructed using ∧ and ∨ which I am assuming that it is p⊕q but I need help on this.

Answer 1

If I didn't make a wrong definition on boolean function, I think it is possible.

By listing a true-false table, the boolean function should be accepting n boolean inputs and giving only 1 boolean output.

The function could always be constructed by using "and" to connect every elements within a row, and using "or" to connect the statements constructed before.

Answer 2

Lots on questions on this lately.

Every function constructed with only $\land$ and $\lor$ has the property that $f(\text{true}, \text{true}, \text{true}...) = \text{true}$, call this property $P(f)$.

Provable inductively:

$$\text{case 1:}\quad g_1(...) = g_2(...) \land g_3(...)$$ $$\text{case 2:}\quad g_1(...) = g_2(...) \lor g_3(...)$$

In both case (1) and case (2) , $P(g_2) \land P(g_3) \rightarrow P(g_1)$.

$P(g_2)$ and $P(g_3)$ are the inductive assumptions.