1
$\begingroup$

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

  • 1
    Your expressions appear sound and correct.2012-10-24

1 Answers 1

1

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.
  • 0
    Oh I see, thanks.2012-10-24