Boolean Algebra question

Thread Starter

bibble235

Joined May 29, 2018
63
Started on the road to FPGAs and looking at boolean algrebra. I was doing the full adder example and wanted to confirm my assumption. There answer was used the expression (A ^ B) and mine used (!A ^ !B).

Are these equivalent and therefore negation does not matter for XOR if the same?

Here is my full solution

Code:
module full_adder (

    // Inputs
    input   [2:0]   pmod,
    
    // Output
    output  [1:0]   led
);
    wire A;
    wire B;
    wire C;

    // Set A, B, and C  to buttons and off
    assign A = ~pmod[0];
    assign B = ~pmod[1];
    assign C = ~pmod[2];

    // Taken from above working
    // led[0] C (A̅ ⊕ B̅) + AB
    // led[1] C ⊕ A ⊕ B

    // Cout
    assign led[0] = (C & (!A ^ !B) ) | (A & B);

    // S
    assign led[1] = C ^ A ^ B;

    
endmodule
Please be kind
Thanks,
 

Papabravo

Joined Feb 24, 2006
21,225
You also know that A ^ B = A!B + !AB
And therefore !A ^ !B = !A!!B + !!A!B = !AB + A!B
So yes, they are the same because '+' (the inclusive OR operator) is commutative.
 

WBahn

Joined Mar 31, 2012
30,057
Started on the road to FPGAs and looking at boolean algrebra. I was doing the full adder example and wanted to confirm my assumption. There answer was used the expression (A ^ B) and mine used (!A ^ !B).

Are these equivalent and therefore negation does not matter for XOR if the same?
Does not matter if WHAT is the same?

You should be able to quickly convince yourself whether or not the two expressions are the same by preparing a truth table for both.

But since you specifically mention Boolean algebra in the thread title, it might be more educational for you to see if you can prove they are the same using Boolean algebra. It only takes about three lines of algebra.

A sometimes useful takeaway is that each inversion at either the input or the output of an XOR toggles it between an XOR and an XNOR. This extents to multi-input XOR gates. This is useful because if you need an XNOR and all you have is XOR, you don't have to put the additional inverter in the output path. Instead, you have the option of trying to remove an inversion in the longest input path, or add an inversion in a shorter input path and thereby not slow down the logic at all. Also, removing an inversion in one of the input paths reduces the gate count and the power consumption.
 

Thread Starter

bibble235

Joined May 29, 2018
63
You also know that A ^ B = A!B + !AB
And therefore !A ^ !B = !A!!B + !!A!B = !AB + A!B
So yes, they are the same because '+' (the inclusive OR operator) is commutative.
This is what I arrived at, but confidence drains when you are working different realm for the first time. The language is also new too (e.g. commutative - probably a poor education). Top that with operators all re-symbolized (loving + means OR) and shot of dyslexia

We are getting there though. Onto chapter 5. And this is immensely helpful with my actual electronics. Love there is a real purpose to binary algebra which is tangible.

Still cannot get u+0305 to work on Chrome Android so keeping notes on my wiki is hard too. e.g. A̅ ⊕ B̅ shows up incorrectly.
 

Papabravo

Joined Feb 24, 2006
21,225
This is what I arrived at, but confidence drains when you are working different realm for the first time. The language is also new too (e.g. commutative - probably a poor education). Top that with operators all re-symbolized (loving + means OR) and shot of dyslexia

We are getting there though. Onto chapter 5. And this is immensely helpful with my actual electronics. Love there is a real purpose to binary algebra which is tangible.

Still cannot get u+0305 to work on Chrome Android so keeping notes on my wiki is hard too. e.g. A̅ ⊕ B̅ shows up incorrectly.
Interesting because basic abstract algebra was part of the "New Math" that I was "subjected" to in 1959 when I started the 7th grade. I keep forgetting that other people have different pathways to get where they are. I applaud your industry – keep it up.
 

Thread Starter

bibble235

Joined May 29, 2018
63
Interesting because basic abstract algebra was part of the "New Math" that I was "subjected" to in 1959 when I started the 7th grade. I keep forgetting that other people have different pathways to get where they are. I applaud your industry – keep it up.
I did not finish school, but I did do algebra but not with booleans only quadratic, a small amount of calculus. I had to relearn how to eat and walk last year so I do not see any shame learning or re-learning something.

It is FSM next, Did not understood a single word about regarding Q, q0, δ, λ, X, Y. Like boolean algebra recognise some elements, heard of tuples and state machines implemented them in assembly, c++, C#, blah blah blah, but most of the text on https://www.javatpoint.com/finite-state-machine means nothing so it is off to youtube tonight.

Good news is I can ask questions on forums like this. I do not mind being of lesser intelligence, instead grateful for what I can learn. Each according to their gifts as they say.
 

panic mode

Joined Oct 10, 2011
2,749
There answer was used the expression (A ^ B) and mine used (!A ^ !B).

Are these equivalent and therefore negation does not matter for XOR if the same?
they are equivalent...

XOR returns TRUE when inputs are different (one is TRUE and other is FALSE).
if you invert both inputs, you get still the same thing, just inputs a and b have swapped places but that makes no difference to outcome.
 

panic mode

Joined Oct 10, 2011
2,749
state machines are simple and can be implemented in any logic or programming language.
the bottom line is that there could be several states (a finite number) and transitions or change of state. change of states only occurs when specific conditions are met. one can associate different conditions to each transition and this can be as simple or complex as needed. then FSM will blindly follow the path of different stated based on configuration, current state and conditions encountered.
 

Thread Starter

bibble235

Joined May 29, 2018
63
state machines are simple and can be implemented in any logic or programming language.
the bottom line is that there could be several states (a finite number) and transitions or change of state. change of states only occurs when specific conditions are met. one can associate different conditions to each transition and this can be as simple or complex as needed. then FSM will blindly follow the path of different stated based on configuration, current state and conditions encountered.
Thanks for this, A day on and a day further down the road. Did the Digi-key tutorial for my FPGA and some of it made sense but the eye opener for me was the youtube
by Intermation which made the Digi-key one make more sense. Key for me was the phrase directed graph which helped me understand the diagrams.

None of it is too much of a challenge but tieing it back to things you already know is the key for me. He did bring up karnaugh maps which will be for tonight but I think they look like an alternative to rationalisation of boolean algebra. - love learning.
 

MrAl

Joined Jun 17, 2014
11,474
Started on the road to FPGAs and looking at boolean algrebra. I was doing the full adder example and wanted to confirm my assumption. There answer was used the expression (A ^ B) and mine used (!A ^ !B).

Are these equivalent and therefore negation does not matter for XOR if the same?

Here is my full solution

Code:
module full_adder (

    // Inputs
    input   [2:0]   pmod,

    // Output
    output  [1:0]   led
);
    wire A;
    wire B;
    wire C;

    // Set A, B, and C  to buttons and off
    assign A = ~pmod[0];
    assign B = ~pmod[1];
    assign C = ~pmod[2];

    // Taken from above working
    // led[0] C (A̅ ⊕ B̅) + AB
    // led[1] C ⊕ A ⊕ B

    // Cout
    assign led[0] = (C & (!A ^ !B) ) | (A & B);

    // S
    assign led[1] = C ^ A ^ B;


endmodule
Please be kind
Thanks,

Why dont you start with the equivalent logic statement for an XOR gate and go from there.

In words, and XOR gate has output that is high when EITHER input is high, but NOT BOTH.

EITHER means an OR circuit, NOT BOTH means an INVERTED AND, ANDing those two creates an XOR gate:

EITHER:
A+B

NOT BOTH:
(A*B)'

THOSE TWO COMBINED WITH AN AND GATE:
C=(A+B)*((A*B)')

Now there are several ways to show an equivalence here.

For one, just follow the math and expand that expression...
first expand (A*B)' and i'll use a lower case 'n' to show inversion:
(A*B)'=An+Bn

and now replace that part with this new form and we end up with:
C=(A+B)*(An+Bn)

Now expand that:
C=Bn*B+An*B+Bn*A+An*A

and here Bn*B equates to 0, and An*A equates to 0, so we are left with:
C=An*B+Bn*A

which is the same thing as saying "EITHER ONE BUT NOT BOTH".

You can find other forms too, should be at least one more maybe others also.

The main point though is that once you have it down to the fundamental logic gates you can more easily tell if inverting anything changes anything.
For example, now that we have it down to that last statement:
C=An*B+Bn*A

we can invert all the inputs and see what happens:
C = An'*B' + Bn'*A'

An' comes out to A,
B' comes out to Bn,
Bn' comes out to B,
A' comes out to An,
replacing those in that last expression we get:
C=A*Bn+B*An

and that's the same expression with variables flipped around a little.

Note here i inverted BOTH inputs, you can now investigate what happens if you just invert ONE input, or perhaps the OUTPUT, or perhaps both the two inputs and the output at the same time, or just either input alone and the output.
If you care to, you can investigate XOR gates with more than two inputs using the same idea. First write the expression using fundamental gates then go from there.

It's also a little interesting to note that an XOR (or XNOR) gate is also a digital comparator. You can use several two input XOR gates to compare two digital words if you OR all the outputs.
 
Last edited:

Thread Starter

bibble235

Joined May 29, 2018
63
Thanks for the reply and a great explanation. For me, Karnaugh maps and now #62 David Tarnoff videos has made things clearer.
 

MrAl

Joined Jun 17, 2014
11,474
Thanks for the reply and a great explanation. For me, Karnaugh maps and now #62 David Tarnoff videos has made things clearer.
I guess i always depended on Boolean Logic algebra because i knew it was harder to make a mistake with that, and it's always quite straightforward.
You can even convert 'if...then...else..." programming statements into Boolean logic statements. That idea i got from a study of automated reasoning.
 
Top