Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello I need to proove that $\{\not\to$, ¬} is functional complete concerning {not, or, and}. The definition: x $\not\to$ y : x and not y. My attempt is to show that {not, or, and} can be also replaced by $\not\to$. not x = already given; LOGIC OR: x or y = not(not(x or y)) = not(not x and not y) = not(not x $\not\to$ y); LOGIC AND: x and y = x $\not\to$ not y Is this correct? -Freddy {}{}{}{}

share|cite|improve this question
Your expressions appear sound and correct. – Lord_Farin Oct 24 '12 at 21:10

Yes, correct.

Note also, that

  1. $\lnot$ can also be obtained assuming instead the constant $1$ (alias 'true').
  2. Every function on a Boolean algebra $B$ can be expressed by using constants and the boolean connectives.
share|cite|improve this answer
Mind giving an example for 1.? (You don't have to) – Freddy Oct 24 '12 at 21:18
I meant $\lnot x =1\not\to x$. – Berci Oct 24 '12 at 21:23
Oh I see, thanks. – Freddy Oct 24 '12 at 21:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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