Not every boolean function is constructed from $\wedge$ (and) and $\vee$ (or)

Question

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$.

Here is my solution, can I ask for a feed back on my solution please?

$p∧q$

$0 0 0 1 $

$p∨q$

$0 1 1 1$

Not every boolean function is the same when using $ ∨ $ and $∧.$

Edited part!

$p\vee q$

$0111$

$(p\vee q)\wedge p = p$

$0 = 0$

$0 = 0$

$1 = 1$

$1 = 1$

$(p\vee q)\vee p = p\vee q$

$0 = 0$

$1 = 1$

$1 = 1$

$1 = 1$

here is my edited answer , can I ask for more feed back , thanks

Answer 1

I'm not sure you understood what was asked in this problem. The aim is to find a function $f$ that cannot be built with the symbols $∨$ or $∧$ only.

Your first solution is the function $f: (p, q) \mapsto p∧q$ which is constructed exactly with the symbol $∧$, so it does not answer the problem. You have the same problem with the second solution you provided.

Try to find other logical symbols you could use to construct a function, and with a good choice, prove that it can not be expressed solely with $∨$ and $∧$.

Answer 2

To start with you need some property which all Boolean functions built using only $\land$ and $\lor$ have in common. One that works is this: any such Boolean function evaluates to $1$ ("true") provided all the variables in it are given the value $1$.

Once the above property has been shown, any simple particular Boolean expression without the above property, such as $r=p \land \lnot q$ is seen not to be constructible from $\land,\lor$ since (for this example) $r$ comes out $0$ (false) when $p,q$ are each $1$.

Establishing the property mentioned above can be done either by common sense based on properties of $\land,\lor$ or else more rigorously by use of strong induction on the length of the Boolean expression, together with the recursive description of how longer Boolen "and/or" expressions are built up from shorter ones. For example a single variable is an "and/or" Boolean expression, and if $A,B$ are "and/or" Boolean expressions so are each of $A\land B$ and $A \lor B.$ How much detail to give in such a proof depends on the rigor level for whatever course the exercise is for.