I was learning how to build a computer ALU, online, and the tutor comes up with a truth table which works perfectly and seems magical.
One of the tasks was to find x-y (both x and y are 16-bit boolean buses)
'+' sign anywhere is the normal boolean addition operator and not the OR operator
On implementing boolean algebra on the truth table x-y = NOT(NOT(x)+y).
It works perfectly and I am not able to understand how it was derived.
I tried deriving the boolean logic myself and I came up with these steps:-
'+' anywhere is normal binary addition and not 'OR'
x-y = x+(-y)
-y = NOT(y) + 1 //2's complement
therefore,
x-y= x+(NOT(y) + 1)
and according to the truth table
x-y = NOT(NOT(x)+y)
How is this working?? Can anyone please tell me how to think on these steps to derive such booleans functions?
Any help will be greatly appreciated.
If you’re doing $n$-bit arithmetic, $\neg x$ is $2^n-1-x$, the one’s complement of $x$. Thus,
$$\neg(\neg x+y)=2^n-1-(2^n-1-x+y)=x-y\;.$$
If you want to compare this with subtraction using the two’s complement, note that the two’s complement of an integer $x$ is $2^n-x$, so that
$$x+\neg y+1=x+2^n-1-y+1=x-y+2^n\;,$$
and you throw away the $2^n$ bit.
Using the example in my comment, for instance, with $n=6$, $x=11=001011_{\text{two}}$, and $y=6=000110_{\text{two}}$, we have
$$\begin{align*} \neg(\neg 001011+000110)&=\neg(110100+000110)\\ &=\neg111010\\ &=000101\;, \end{align*}$$
while
$$001011+\neg 000110+1=001011+111001+1=(1)000101\;.$$