Boolean Expressions and Logical Operators | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 13.3 Free with a free account

Boolean Expressions and Logical Operators

Discrete Mathematics · Chapter 13: Boolean Algebra and Logic CircuitsSection 13.3 · lesson 83 of 879 min · free with a free account

← Boolean Algebra: Laws and PropertiesNext lesson: Karnaugh Maps →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Write down what a circuit should do, then say it with fewer parts.

  • Translate a description into a Boolean expression
  • Simplify one named law at a time
  • Build canonical sum-of-products and product-of-sums forms
  • Reduce the majority function algebraically

Transcript

Everything said in the video, section by section (1,335 words). Read along, or search it.

Boolean Algebra and Logic Circuits

Boolean Expressions and Logical Operators

This section is about writing down what a circuit should do, and then saying it with fewer parts. We'll translate descriptions into Boolean expressions, simplify them one named law at a time, and build two standard forms straight from a truth table. Every simplification here uses algebra alone. A visual shortcut comes in section thirteen point four.

The Opening Problem

Let Two Out of Three Decide

Spacecraft and other safety-critical systems often run the same computation on three independent processors. A voting circuit then decides the output. If at least two of the three agree, that agreement becomes the system's answer. So a single processor glitch can never corrupt the result. This design is called triple modular redundancy. The voting circuit at its center is a Boolean function of three inputs. Writing that function down, and writing it as compactly as possible, are two separate skills. Both matter, because every extra logic gate in the final circuit costs real silicon, power and delay.

13.3.1

From Words to an Expression

First, the notation. Writing A B side by side, or with a dot, means A AND B. A plus sign means OR. And a trailing prime, A prime, means NOT A. Translating a description means finding the connective behind each piece of it, in the order the description combines them. Here's a secure door. It unlocks when a valid keycard is presented, together with either manager approval or the correct PIN. But only when the facility isn't in lockdown. Let A be the keycard, B manager approval, C the correct PIN, and D lockdown. Either manager approval or the correct PIN is an OR: B plus C. A valid keycard together with that is an AND: A times the quantity B plus C. And only when the facility is not in lockdown brings in the complement, D prime, ANDed with everything before it. So Y equals A, times B plus C, times D prime.

A Recurring Pattern

Unless, Only When, Provided That

The phrase only when is worth flagging. It's easy to misread as needing a separate clause. But it just restricts an expression that's already built, by ANDing in a condition, possibly complemented. Here's a shorter case. A smoke alarm sounds when smoke is detected, unless the alarm is in test mode. With S for smoke detected and T for test mode, unless becomes AND with a complement. Y equals S T prime. Whether the restriction says only when, unless, or provided that, the translation is the same pattern.

13.3.2

A Full Simplification, Step by Step

Simplifying works like simplifying an algebraic fraction. Apply one named law at a time, never skipping a step, until nothing shortens the expression further. Simplify A B, plus A times B plus C, plus B times B plus C. First, the distributive law expands both products, giving A B plus A B plus A C plus B B plus B C. The idempotent law says B B is just B. And again, the two copies of A B collapse to one. Now absorption. B plus B C is just B. That leaves A B plus A C plus B. And absorption once more. A B plus B is just B. So the whole expression equals B plus A C. Three terms and five literals became two terms and three literals, with every step justified by a single law.

13.3.3

Sum-of-Products and Product-of-Sums

Two standard shapes for expressions are worth naming. A literal is a variable or its complement, like A or A prime. A sum-of-products expression is an OR of product terms, where each product term is an AND of literals. A product-of-sums expression is an AND of sum terms, where each sum term is an OR of literals. The words sum and product name the outermost operation, not what the literals are doing. So A times the quantity B plus C, plus D, is neither. A sum is nested inside what would need to be a pure product term.

Table 1

The Majority Function

A truth table pins down one specific sum-of-products for any function, called its canonical form. Take the majority function M of A, B and C, the triple redundancy vote. It's one exactly when at least two of the three inputs are one. Each row where M is one contributes a minterm. That's an AND of all three variables, each uncomplemented if it's one in that row, and complemented if it's zero. The four one-rows give A prime B C, A B prime C, A B C prime, and A B C. OR them together, and that's the canonical sum-of-products. Each minterm is one on exactly one row, so the OR is one on exactly the four rows where M is one.

Worked Example

Reducing the Canonical SOP

The canonical form is correct, but it isn't minimal. The laws of section thirteen point two reduce it directly. Here's the trick. By the idempotent law, A B C equals three copies of itself. So use one copy to pair with each of the other three terms. Then factor each pair with the distributive law. A prime B C plus A B C becomes A prime plus A, times B C. The same happens for the other two pairs. By the complement law, each factor like A prime plus A collapses to one. And by the identity law, multiplying by one changes nothing. So M equals A B plus A C plus B C. Four three-literal terms reduced to three two-literal terms. And it reads exactly as any two of the three agree, which is what a majority vote means.

Figure 1

Same Function, Smaller Tree

Here are both versions as expression trees. On the left, the canonical form. An OR gate combines four AND gates, each taking three literals. That's twelve leaves. On the right, the simplified form. An OR combines three AND gates, each taking just two literals. That's six leaves. Both trees compute the identical function. But the right one uses one fewer AND gate, and half the inputs.

13.3.4

Product-of-Sums, the Dual Way

The canonical product-of-sums is built the dual way. There's one maxterm for each row where the output is zero. In a maxterm, each variable is written uncomplemented if it's zero in that row, and complemented if it's one. The literals are ORed inside each term, and the terms are ANDed together. The majority function's four zero-rows give four maxterms. By the dual of the previous argument, pairing terms that share two variables, this simplifies to A plus B, times A plus C, times B plus C. And this isn't a separate recipe. M prime is one exactly on the rows where M is zero, so it has its own canonical sum-of-products. Complement both sides and apply De Morgan's law twice, once to the outer OR and once to each inner AND. Out comes exactly this product-of-sums.

Table 2

SOP Versus POS

Here are the two forms side by side. A sum-of-products is an OR of terms, each an AND of literals, built from one minterm per one-row. A product-of-sums is an AND of terms, each an OR of literals, built from one maxterm per zero-row. So which to start from depends on which set of rows is smaller. With only one or two one-rows, a sum-of-products is quicker. With only one or two zero-rows, a product-of-sums is. The majority function has four of each, so neither has an advantage. And once written, both simplify by exactly the same laws, with the roles of plus and times mirrored.

Takeaways

Translate, Then Shrink

To summarize. Writing an expression means matching each part of a description to AND, OR, or an unless-style complement, in the order the description combines them. Simplification applies one named law at a time, and never skips a justification. A sum-of-products is an OR of AND terms, and a product-of-sums is an AND of OR terms. The canonical forms are unique for a function, but rarely minimal. Karnaugh maps, in section thirteen point four, give a visual shortcut to the same minimal answers. Here's something to think about. A function's canonical form is unique, but you can simplify it in more than one order. Could a Boolean function then have more than one equally simplified expression? And what would have to be true of two different-looking expressions, for both to count as equally simple?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Boolean Expressions and Logical Operators

How do you translate "unless" or "only when" into a Boolean expression?
Treat the phrase as ANDing a condition, usually complemented, onto the expression you have already built. A smoke alarm that sounds when smoke is detected unless it is in test mode becomes Y = ST'. "Only when" and "provided that" follow the same pattern. A door needing a keycard plus approval or a PIN, and no lockdown, is Y = A(B+C)D'.
How do you simplify a Boolean expression one law at a time?
Apply a single named law per step until no law shortens the expression further. For AB + A(B+C) + B(B+C), distribute to get AB + AB + AC + BB + BC. Idempotence gives AB + AC + B + BC. Absorption turns B + BC into B, leaving AB + AC + B. Absorbing again gives B + AC.
How do you write the canonical sum-of-products and product-of-sums from a truth table?
For a sum-of-products, write one minterm for each row where the output is 1. Each minterm ANDs all variables, complementing those that are 0 in that row, and the minterms are ORed. For the majority function, this gives A'BC + AB'C + ABC' + ABC. A product-of-sums instead uses one ORed maxterm per 0-row, with variables that are 1 complemented.
How do you reduce the majority function algebraically?
Use the idempotent law to make three copies of ABC, then pair one copy with each of the other minterms. Factoring each pair gives, for example, A'BC + ABC = (A'+A)BC = BC by the complement and identity laws. The result is M = AB + AC + BC, which reads as "any two inputs agree."

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →