0

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

Kit lai
  • 49
  • You still have not given a specific Boolean which is not constructible from $\land, \lor$. Also there are many which can, and you in the above have only looked at a few of them. – coffeemath Mar 18 '14 at 01:40
  • So I have to make one that isnt constructible with $\wedge$ ,$\vee$ but how am I suppose to do that? Can I have some Hints? Thanks – Kit lai Mar 18 '14 at 02:31
  • The simplest which cannot be constructed is the one variable Boolean $\lnot p$. For this one variable case there is only one Boolean which can be constructed using $\land,\lor$ namely $p$. (just try various possibilities, they all are equivalent to $p$ for example $p \land p = p, p \lor (p \land p)=p,...$ – coffeemath Mar 18 '14 at 04:56
  • 1
    sorry im a very slow learner, bear with me if i cant really understand, I'll try again and get back with you – Kit lai Mar 19 '14 at 09:04

2 Answers2

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 $∧$.

Mx Glitter
  • 156
  • I see, so i have to construct a function f and compare it to the function p∧q? e.g f = 0 0 1 0 – Kit lai Mar 10 '14 at 23:02
  • @Kitlai You have to construct an $f$, and then not only compare it to and, or but need to show your $f$ is not equivalent to any function $g$ which may be made using and,or. – coffeemath Mar 10 '14 at 23:45
0

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.

coffeemath
  • 29,884
  • 2
  • 31
  • 52