MHB How is binary addition performed?

[evinda]

Hello! (Wave)

According to some notes of computability theory:

Addition of binary numbers

$$10011\\ +11111 \\ ------ \\ 110010$$

View attachment 5766

I haven't understood how they do the addition, since it holds that $1+1=0$... (Sweating)

Could you explain it to me?

 

[Evgeny.Makarov]

I haven't understood how they do the addition, since it holds that $1+1=0$...

I am not sure if you mean "I don't understand addition, in particular, why 1 + 1 = 0" or "I don't understand addition. I understand that 1 + 1 = 0, and this does not square with what the notes have".

In decimal system we also have 5 + 5 = 0 plus a carry into the next (more senior) position.

 

[evinda]

I am not sure if you mean "I don't understand addition, in particular, why 1 + 1 = 0" or "I don't understand addition. I understand that 1 + 1 = 0, and this does not square with what the notes have".

I meant this: " I understand that 1 + 1 = 0, and this does not square with what the notes have".

So you mean that we are not in the binary system?

 

[I like Serena]

I meant this: " I understand that 1 + 1 = 0, and this does not square with what the notes have".

So you mean that we are not in the binary system?

Don't we have 1 + 1 = 10 in the binary system? (Wondering)

And for instance 11 + 01 = 100?
That is, starting from the right we have 1 + 1 = 0 with 1 to carry over.
And then we have 1 + 0 + carry-over = 0 with again 1 to carry over. (Nerd)

 

[Evgeny.Makarov]

I meant this: " I understand that 1 + 1 = 0, and this does not square with what the notes have".

Then you'll have to point out exactly what you don't understand in the notes.

So you mean that we are not in the binary system?

No, I was pointing out that sometimes the sum of two positive integers is 0 (modulo the base).

 

[evinda]

Don't we have 1 + 1 = 10 in the binary system? (Wondering)

And for instance 11 + 01 = 100?
That is, starting from the right we have 1 + 1 = 0 with 1 to carry over.
And then we have 1 + 0 + carry-over = 0 with again 1 to carry over. (Nerd)

Oh, I didn't know so... So this is the only rule we have to take into consideration in the binary system? (Thinking)

For example, it holds that $10+1=11$, right?

 

[I like Serena]

Oh, I didn't know so... So this is the only rule we have to take into consideration in the binary system? (Thinking)

For example, it holds that $10+1=11$, right?

Right. (Nod)

 

[evinda]

Right. (Nod)

Nice... Thank you very much! (Smirk)

 

[evinda]

How can we prove that the dfa of my initial post indeed represents the addition in the binary system?

 

[I like Serena]

How can we prove that the dfa of my initial post indeed represents the addition in the binary system?

How does binary addition work? (Wondering)

Once we know how it works, we can see what kind of dfa covers it. (Thinking)

 

[evinda]

How does binary addition work? (Wondering)

Once we know how it works, we can see what kind of dfa covers it. (Thinking)

As you said in post 4. http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/addition-binary-numbers-19097.html#post87326

We have to take into consideration that $1+1=10$, we start from the right and if we have 1+1 we write 0 and have to remember a 1.

 

[evinda]

In general, given a language and having drawn a dfa that recognizes it, how can we formally prove that the dfa is the right one? (Thinking)

 

[evinda]

Also I think that a transition is missed at the automaton of my initial post, namely the [m](0,1)/0[/m] at the second state. I think it should be as follows.View attachment 6123

Like that we just don't get the first number of the result of the addition. But this cannot be done by the automaton since the number of the input symbols must be equal to the number of the output symbols. Right?

 

[I like Serena]

As you said in post 4. http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/addition-binary-numbers-19097.html#post87326

We have to take into consideration that $1+1=10$, we start from the right and if we have 1+1 we write 0 and have to remember a 1.

Exactly.
Additionally, we need to specify all addition rules with and without carry.

So we add from right to left and apply the following rules:
0+0+(no carry)=0
0+1+(no carry)=1
1+0+(no carry)=1
1+1+(no carry)=0+(carry)
0+0+(carry)=1
0+1+(carry)=0+(carry)
1+0+(carry)=0+(carry)
1+1+(carry)=1+(carry)

If the DFA implements those rules and stops when it is complete, I believe we have our proof. (Wink)

In general, given a language and having drawn a dfa that recognizes it, how can we formally prove that the dfa is the right one? (Thinking)

We start from the definition, and check if every part of the definition is covered by our DFA. (Nerd)

Also I think that a transition is missed at the automaton of my initial post, namely the [m](0,1)/0[/m] at the second state. I think it should be as follows.

Like that we just don't get the first number of the result of the addition. But this cannot be done by the automaton since the number of the input symbols must be equal to the number of the output symbols. Right?

You're right and I think (1,0)/0 is missing in the second state as well. (Thinking)

 

[evinda]

Exactly.
Additionally, we need to specify all addition rules with and without carry.

So we add from right to left and apply the following rules:
0+0+(no carry)=0
0+1+(no carry)=1
1+0+(no carry)=1
1+1+(no carry)=0+(carry)
0+0+(carry)=1
0+1+(carry)=0+(carry)
1+0+(carry)=0+(carry)
1+1+(carry)=1+(carry)

I see...

If the DFA implements those rules and stops when it is complete, I believe we have our proof. (Wink)

You mean that we have to check all these rules and if they are implemented, we will have shown that the automaton is the right one?

We start from the definition, and check if every part of the definition is covered by our DFA. (Nerd)

You mean the definition of the desired function of the dfa?

You're right and I think (1,0)/0 is missing in the second state as well. (Thinking)

Yes, that's true. (Nod)In order to show that the definition makes correctly the addition of binary numbers, couldn't we also use induction on the length of the binary numbers?

 

[evinda]

I have thought that we could prove that the dfa is the right one using induction on the length of the given binary numbers.

Suppose that we symbolize with $n$ the length of the given binary numbers.Base case: Let $n=1$. Then we could have the input $(0,0), (0,1), (1,0), (1,1) $.

If the input is $(0,0)$ then the machine prints $0$ which is right, since $0+0=0$.
If the input is $(0,1)$ or $(1,0)$ then the machine prints $1$ which is right since $0+1=1+0=1$.
If the input is $(1,1)$ then the machine prints $0$, which is again right since $1+1=0$ with $1$ to carry over.Induction hypothesis: We suppose that the automaton makes correctly the addition of two binary numbers of length $n$.Induction step: We want to show that the automaton makes correctly the addition of two binary numbers of length $n+1$.
If we have two numbers of length $n+1$, we first add the last $n$ digits.
So we have from the induction hypothesis that the the result of the addition of the last $n$ digits will be right. So from each number, will one digit remain.

If after the addition of the last $n$ digits we are at the first state, it follows from the base case that the result of the addition of the remaining digits will be right.

If after the addition of the last $n$ digits we are at the second state, then we have to remember that we have carried over a 1.
The possible pairs of the remaining digits are these: $(0,0), (1,0), (0,1), (1,1)$.

Suppose that we have $(0,0)$. The machine will print $1$. This is right, since 0+0+carry over =1.

If we have (1,0) or (0,1), then the machine prints $0$, which is again right since 1+0+carry over =0+1+carry over=0+carry over.

If we have (1,1) then the machine prints 1, which is right since 1+1+carry over=1+carry over.
Is it right? Could I improve something?

 

[I like Serena]

I have thought that we could prove that the dfa is the right one using induction on the length of the given binary numbers.

Suppose that we symbolize with $n$ the length of the given binary numbers.Base case: Let $n=1$. Then we could have the input $(0,0), (0,1), (1,0), (1,1) $.

If the input is $(0,0)$ then the machine prints $0$ which is right, since $0+0=0$.
If the input is $(0,1)$ or $(1,0)$ then the machine prints $1$ which is right since $0+1=1+0=1$.
If the input is $(1,1)$ then the machine prints $0$, which is again right since $1+1=0$ with $1$ to carry over.Induction hypothesis: We suppose that the automaton makes correctly the addition of two binary numbers of length $n$.Induction step: We want to show that the automaton makes correctly the addition of two binary numbers of length $n+1$.
If we have two numbers of length $n+1$, we first add the last $n$ digits.
So we have from the induction hypothesis that the the result of the addition of the last $n$ digits will be right. So from each number, will one digit remain.

If after the addition of the last $n$ digits we are at the first state, it follows from the base case that the result of the addition of the remaining digits will be right.

If after the addition of the last $n$ digits we are at the second state, then we have to remember that we have carried over a 1.
The possible pairs of the remaining digits are these: $(0,0), (1,0), (0,1), (1,1)$.

Suppose that we have $(0,0)$. The machine will print $1$. This is right, since 0+0+carry over =1.

If we have (1,0) or (0,1), then the machine prints $0$, which is again right since 1+0+carry over =0+1+carry over=0+carry over.

If we have (1,1) then the machine prints 1, which is right since 1+1+carry over=1+carry over.
Is it right? Could I improve something?

It looks right to me. (Happy)
There's one thing left - the numbers do not have to have the same length.
We need that if one number is shorter, it is filled out with zeroes on the left.
And then the dfa will stop when both numbers have fully been processed, which we need as well. (Thinking)

 

[evinda]

It looks right to me. (Happy)
There's one thing left - the numbers do not have to have the same length.
We need that if one number is shorter, it is filled out with zeroes on the left.
And then the dfa will stop when both numbers have fully been processed, which we need as well. (Thinking)

I see... Thanks a lot! (Smirk)