0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – coffeemath Mar 18 '14 at 1:40
  • $\begingroup$ 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 $\endgroup$ – Kit lai Mar 18 '14 at 2:31
  • $\begingroup$ 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,...$ $\endgroup$ – coffeemath Mar 18 '14 at 4:56
  • 1
    $\begingroup$ sorry im a very slow learner, bear with me if i cant really understand, I'll try again and get back with you $\endgroup$ – Kit lai Mar 19 '14 at 9:04
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Kit lai Mar 10 '14 at 23:02
  • $\begingroup$ @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. $\endgroup$ – coffeemath Mar 10 '14 at 23:45
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I understand a portion of what you included Thank heaps $\endgroup$ – Kit lai Mar 12 '14 at 0:27
  • $\begingroup$ @Kitlai If you let me know some part you don't get yet, I can add something about that. $\endgroup$ – coffeemath Mar 12 '14 at 1:02
  • $\begingroup$ I have edited my answer, please provide some feed back, thanks $\endgroup$ – Kit lai Mar 17 '14 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.