Simplify the boolean functionZ=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCiZ=AB¯Ci¯+A¯BCi¯+A¯B¯Ci+ABCi

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

add a comment

1 Answer

ActiveOldestVotes2

Observe that
A¯¯¯¯⋅B¯¯¯¯+A⋅B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=(A¯¯¯¯⋅B¯¯¯¯)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯⋅(A⋅B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=(A+B)⋅(A¯¯¯¯+B¯¯¯¯)=A⋅B¯¯¯¯+A¯¯¯¯⋅BA¯⋅B¯+A⋅B¯=(A¯⋅B¯)¯⋅(A⋅B)¯=(A+B)⋅(A¯+B¯)=A⋅B¯+A¯⋅B

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
https://en.wikipedia.org/wiki/Boolean_algebra

(2) Canonical Normal Form – Wikipedia
https://en.wikipedia.org/wiki/Canonical_normal_form

(3) De Morgan’s Laws – Wikipedia
https://en.wikipedia.org/wiki/De_Morgan%27s_laws

(4) Venn Diagram – Wikipedia
https://en.wikipedia.org/wiki/Venn_diagram

(5) Karnaugh Map – Wikipedia
https://en.wikipedia.org/wiki/Karnaugh_map

(6) George Boole – Wikipedia
https://en.wikipedia.org/wiki/George_Boole

(7) Maurice Karnaugh – Wikipedia
https://en.wikipedia.org/wiki/Maurice_Karnaugh

(8) Augustus De Morgan – Wikipedia
https://en.wikipedia.org/wiki/Augustus_De_Morgan

Appendices

Appendix A – Canonical Normal Form – Wikipedia
https://en.wikipedia.org/wiki/Canonical_normal_form

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
https://en.wikipedia.org/wiki/De_Morgan%27s_laws

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;

or

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.

or

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
https://en.wikipedia.org/wiki/Karnaugh_map

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.

.END