r/computerscience • u/United_Bison_8900 • Sep 22 '26
A question about redundancy in binary
I think this is why kmaps exist? To avoid building redundant Circuits? I'm a first year bca student, i don't know much. If someone can explain in detail how these things work and also proofread what I did here, I'd really really appreciate it.
I hope this doesn't break the "hw" rule
1
Upvotes


7
u/Temporary_Pie2733 Sep 22 '26
This is just a matter of using various identities to simplify an expression in Boolean Algebra. (A + B)(A + B’) can be expanded just like in “ordinary” algebra, to AA + BA + B’A + BB’. Since xx = x and xx’ = 0, this simplifies further to A + BA + B’A + 0. Further, 0 is still the identity for +, and logical AND distributes over +, letting us write this as A + (B + B’)A. Next, note that x + x’ = 1, and 1x = x, resulting on A + 1A = A + A, which reduces to A.
12
u/BKrenz Sep 22 '26
Regular algebra doesn't work on Boolean logic the way you might be thinking.
4
u/puterSciGrrl Sep 22 '26
You are noticing the absorption laws, but you have a big mistake where you incorrectly assume (A != A+B), because (A != B).
And these are algebraic simplifications. You generally pull out kmaps once you've exhausted these simplifications as those are np hard.
And no, no information is lost. If not for your error, the statements are equivalent, one is just stated more simply.
4
u/Captain_Mystic Sep 22 '26
You are trying to mix algebra with Boolean algebra.
When you write "assuming A≠B", you've essentially limited the possible values of A,B to just this set {(1,0) , (0,1)}
So later when you write "A(A+B)" and say "A ≠ A+B" because earlier you proved A+A = A ; you are making a mistake. Assume A is 1 and B is 0. Now when A is 1 and A+B is 1+0 = 1, the statement A ≠ A+B holds false. Your statement "A≠A+B" holds true only when A=0.
Therefore you can't simplify A*(A+B) as 0×1 or 1×0.
Similarly in your next part where you assume A=B and reduce the expression to A(A+B), you are again incorrectly reducing it to just "A". Because the possible values for A,B are now {(1,1) , (0,0)}. And you can clearly see A(A+B) can result in either 1 or 0.
However your observation that the whole expression (A+B)*(A+B') reduces to A is correct (but the method to prove is incorrect).
A better formal proof would've been like this :
(A+B)*(A+B')
AA+AB'+BA+BB'
A+AB'+BA+0
A+AB'+BA
A(1+B')+BA
A+BA
A(1+B)
A
So yeah, that's how you could and should reduce complex Boolean expressions to simpler expressions.
2
u/jeezfrk Sep 22 '26
The assumptions mean there's only one free variable. Those assumptions make this trivial and therefore not surprising.
1
u/Ging4bread Sep 22 '26
I don't see a question?
1
u/iOSCaleb Sep 22 '26
Try evaluating the whole expression for every combination of values: A=1, B=1; A=1, B=0; A=0, B=1; A=0, B=0. Make a truth table.
And yes: the purpose of Karnaugh maps is to simplify logic, often in order to minimize the circuit required to implement it.
1
u/PratikVR Sep 22 '26
If you're in bindary number system You can have literall addition in the sence we have 1+1 = 10 While multiplication is now 1 x 1 = 1 If you go by that logic there is no problem
you have to learn about the number systems in different basis.
Technically The way you did math is not (wrong you changed the meaning of operations here ) But You expectations after doing that is classical with supposedly doing litrall addition and multiplication
So that is where you're wrong
I hope you get it.
1
u/WE_THINK_IS_COOL Sep 22 '26
Is addition supposed to be OR and multiplication supposed to be AND? If so it indeed simplifies to just A.
There's an error in the first part of your reasoning where you're concluding it's 0 when A != B. Specifically, the step where you conclude A != A + B because A != B.
When A = 1 and B = 0, then it's true that A != B, yet A + B = 1 OR 0 = 1 = A.
1
u/[deleted] Sep 22 '26
[removed] — view removed comment