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.
Asked
Active
Viewed 121 times
0
-
You may alread have learned, that all boolean functions can be combined from $\land$, $\lor$, $\neg$. So what boolean function should be tested as not being combinablefrom $\land$ and $\lor$? – Hagen von Eitzen Aug 08 '14 at 14:11
2 Answers
0
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.
orb
- 21
0
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.
DanielV
- 23,556