Ask QuestionAsked 3 days agoActive todayViewed 114 times1The bounty expires in 6 days. Answers to this question are eligible for a +50 reputation bounty. Ski Mask is looking for an answer from a reputable source.
I want to simplify the following boolean function:Z=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCiZ=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi
Here’s my attempt:Z=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi=Ci¯(AB¯+A¯B)+Ci(A¯B¯+AB)=C¯i(A⊕B)+Ci(A≡B)Z=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi=Ci¯(AB¯+A¯B)+Ci(A¯B¯+AB)=C¯i(A⊕B)+Ci(A≡B)
I thought this was the end of it but in my textbook it continues and has:Z=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi=Ci¯(AB¯+A¯B)+Ci(A¯B¯+AB)=C¯i(A⊕B)+Ci(A≡B)=A⊕B⊕Ci=A≡B≡CiZ=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi=Ci¯(AB¯+A¯B)+Ci(A¯B¯+AB)=C¯i(A⊕B)+Ci(A≡B)=A⊕B⊕Ci=A≡B≡Ci
I’m confused about what happened between the third and fourth step. What boolean algebra rules are being used here?digital-logiclogic-gatesboolean-algebraaddershareedit follow flagedited Sep 2 at 20:11asked Sep 2 at 18:14Ski Mask8377 bronze badges
- You need a double dollar sign for your title. – DKNguyen Sep 2 at 19:34
- A≡BA≡Bis the same as NOT(A⊕B)(A⊕B)(sorry not very good at formulas) – jcaron Sep 2 at 21:05
- @jcaron Yes but I’m trying to figure out whyC¯i(A⊕B)+Ci(A≡B)=A⊕B⊕CiC¯i(A⊕B)+Ci(A≡B)=A⊕B⊕Ci. – Ski Mask 2 days ago
- It’s another instance of (X AND NOT Y) OR (NOT X AND Y) = X XOR Y, with X being Ci here and Y being A XOR B. – jcaron 2 days ago
- Wouldn’t it be (NOT X AND Y) OR (X AND Y)? – Ski Mask 2 days ago
- 2By X≡YX≡Y, what do you mean exactly? I’ve never seen this notation so far. – edmz yesterday
- 1Seems likeA≡BA≡Bis the same as(A⊕B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(A⊕B)¯. In that case,Z=Ci¯¯¯¯¯(A⊕B)+Ci(A≡B)=Ci¯¯¯¯¯(A⊕B)+Ci(A⊕B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=Ci⊕(A⊕B)=A⊕B⊕CiZ=Ci¯(A⊕B)+Ci(A≡B)=Ci¯(A⊕B)+Ci(A⊕B)¯=Ci⊕(A⊕B)=A⊕B⊕Ci– cjferes yesterday
- Are there any solver tools that can brute-force (or use other heuristics to obtain) a solution to this sort of problem? – Sean 6 hours ago
HenceZ=Ci¯¯¯¯¯(A⊕B)+Ci(A≡B)=Ci¯¯¯¯¯(A⊕B)+Ci(A⊕B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=Ci⊕(A⊕B)=A⊕B⊕CiZ=Ci¯(A⊕B)+Ci(A≡B)=Ci¯(A⊕B)+Ci(A⊕B)¯=Ci⊕(A⊕B)=A⊕B⊕Cishareedit follow flagedited 12 hours agoKingDuken2,04022 gold badges88 silver badges2020 bronze badgesanswered 15 hours agoShashank V M44711 silver badge1616 bronze badgesadd a comment
(1) Boolean algebra – Wikipedia
(2) Canonical Normal Form – Wikipedia
(3) De Morgan’s Laws – Wikipedia
(4) Venn Diagram – Wikipedia
(5) Karnaugh Map – Wikipedia
(6) George Boole – Wikipedia
(7) Maurice Karnaugh – Wikipedia
(8) Augustus De Morgan – Wikipedia
Appendix A – Canonical Normal Form – Wikipedia
Normal form (CCNF) or maxterm canonical form.
Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables. These concepts are dual because of their complementary-symmetry relationship as expressed by De Morgan’s laws.
Two dual canonical forms of any Boolean function are a “sum of minterms” and a “product of maxterms.”
The term “Sum of Products” (SoP or SOP) is widely used for the canonical form that is a disjunction (OR) of minterms.
Its De Morgan dual is a “Product of Sums” (PoS or POS) for the canonical form that is a conjunction (AND) of maxterms. These forms can be useful for the simplification of these functions, which is of great importance in the optimization of Boolean formulas in general and digital circuits in particular.
De Morgan’s Laws – Wikipedia
In propositional logic and Boolean algebra, De Morgan’s laws are a pair of transformation rules that are both valid rules of inference.
The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.
The rules can be expressed in English as:
the negation of a disjunction is the conjunction of the negations; and
the negation of a conjunction is the disjunction of the negations;
the complement of the union of two sets is the same as the intersection of their complements; and
the complement of the intersection of two sets is the same as the union of their complements.
not (A or B) = not A and not B; and
not (A and B) = not A or not B
In set theory and Boolean algebra, these are written formally as
In formal language, the rules are written as
Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan’s laws are an example of a more general concept of mathematical duality.
Karnaugh Map – Wikipedia
After the Karnaugh map has been constructed, it is used to find one of the simplest possible forms — a canonical form — for the information in the truth table.
Adjacent 1s in the Karnaugh map represent opportunities to simplify the expression. The minterms (‘minimal terms’) for the final expression are found by encircling groups of 1s in the map.
Minterm groups must be rectangular and must have an area that is a power of two (i.e., 1, 2, 4, 8…). Minterm rectangles should be as large as possible without containing any 0s.
Groups may overlap in order to make each one larger.