# functional completeness of $\{\not\to$, ¬}

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 {}{}{}{}

-
Your expressions appear sound and correct. –  Lord_Farin Oct 24 '12 at 21:10

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.
I meant $\lnot x =1\not\to x$. –  Berci Oct 24 '12 at 21:23