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 {}{}{}{}
functional completeness of $\{\not\to$, ¬}
1
$\begingroup$
logic
-
1Your expressions appear sound and correct. – 2012-10-24
1 Answers
1
Yes, correct.
Note also, that
- $\lnot$ can also be obtained assuming instead the constant $1$ (alias 'true').
- Every function on a Boolean algebra $B$ can be expressed by using constants and the boolean connectives.
-
0Oh I see, thanks. – 2012-10-24