Boolean Algebra: Laws and Properties | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Boolean Algebra: Laws and Properties

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

← Foundations of Boolean LogicNext lesson: Boolean Expressions and Logical Operators →

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

The rewriting toolkit, each law proved by a complete truth table.

  • State the commutative, associative and distributive laws
  • Verify identity, complement and idempotent laws
  • Apply absorption to delete gates
  • Use duality to get every law's partner free

Transcript

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

Boolean Algebra and Logic Circuits

Boolean Algebra: Laws and Properties

This section builds the toolkit for rewriting Boolean expressions. We'll state each law precisely, and prove each one completely, with a truth table. Section thirteen point three puts the tools to work together. Here, the goal is to know each one on its own.

The Opening Problem

Shrinking a Chip Safely

Modern chip-design software routinely handles circuits with millions of logic gates. Before manufacturing, an automated process called logic synthesis shrinks the design. It finds smaller, cheaper circuits that compute exactly the same output. That isn't magic. It's built entirely from repeatedly applying a small set of algebraic laws, each guaranteeing that one arrangement of gates can replace another with no change in the result. But every equivalence it relies on must be certain. A tool that occasionally produces a smaller but different circuit is worse than no optimization at all. That certainty is exactly what a truth table provides. Since every variable takes only the value zero or one, checking every combination isn't an approximation. It's a complete proof.

13.2.1

Commutative, Associative, Distributive

First, three familiar families. The commutative laws say order doesn't matter. A and B equals B and A, and the same for or. The associative laws say grouping doesn't matter. A and B, then and C, equals A and the group B and C. The same holds for or. The distributive laws come as a pair. A and the quantity B or C, equals A and B, or A and C. And A or the quantity B and C, equals A or B, and A or C. Because the variables take only zero or one, each law can be checked over all eight combinations of A, B and C. It's a finite case analysis, not an appeal to intuition.

Table 13.2.1

Verifying 2 Laws for AND

This table verifies two laws for and, over all eight combinations. The columns A and B, and B and A, agree in every row. That confirms the commutative law. The two rightmost columns, grouping A and B first, or B and C first, also agree in every row. That confirms the associative law. Notice they're one only in the very last row, where all three inputs are one. The same laws for or can be verified by an identical table, with every and replaced by or. We'll see exactly why that's guaranteed to work.

Table 13.2.2

Verifying a Distributive Law

Here's the first distributive law, checked over all eight combinations. The left column is A and the quantity B or C. The right column is A and B, or A and C. They match in every row. They're both one in exactly the last three rows, where A is one and at least one of B or C is one. And here's something that surprises people coming from arithmetic. In ordinary arithmetic, multiplication distributes over addition, but addition doesn't distribute over multiplication. In Boolean algebra, both distributive laws hold at once. And distributes over or, and or distributes over and.

Figure 13.2.1

One Region, Described 2 Ways

The same fact can be seen with sets, reading and as intersection, and or as union. The first panel shades B or C, everything in either circle. The middle panel shades the part of that region inside A. That's A and the quantity B or C. The right panel shades A and B, together with A and C. It's exactly the same region. One region, described two equivalent ways. That's the distributive law made visible. And it already pays off in circuits. Expanding gives two ANDs and an OR, which isn't obviously smaller. But read it backwards. Collect the expanded form back into A, and the quantity B or C. That replaces two AND gates and an OR gate, with a single OR feeding a single AND.

13.2.2

Identity, Complement and Idempotent Laws

Next, three laws about constants, and about a variable meeting itself. The identity laws say A and one is A, and A or zero is A. The complement laws say A and not A is zero, and A or not A is one. The idempotent laws say A and A is A, and A or A is A. Each equation has a single variable, so a complete truth table needs only two rows, A equals zero and A equals one. Reading across confirms every claim. The identity and idempotent columns match A exactly. A and not A is zero in both rows, and A or not A is one in both rows.

In Circuit Terms

Each Law Is a Deletion

Each of these laws has a direct reading in circuit terms. The identity laws say an AND gate with one input permanently tied to one, or an OR gate with an input tied to zero, can be deleted and replaced by a plain wire. The complement laws say that combining any signal with its own inverse always gives a constant, no matter what the signal is doing. And the idempotent laws say this. Feeding the same signal into both inputs of an AND or an OR gate, is the same as not having that gate at all. Each is a single deletion. That's not yet the multi-step process of section thirteen point three, but it's exactly the kind of atomic fact that process draws on.

13.2.3

The Absorption Law

The absorption laws say A and the quantity A or B equals A. And A or the quantity A and B equals A. The name describes exactly what happens. B is absorbed. It has no effect on the result at all, whether it's zero or one. The table checks all four combinations of A and B. In every row, the last two columns equal column A exactly. Think about what that means physically. A circuit computing A and the quantity A or B uses two gates. It also has a wire for B, which does work in the drawing, but none in the output. A bare wire carrying A computes the identical function, with no gates at all. That substitution is a complete saving, no matter what larger circuit surrounds it. Across millions of gates, opportunities like this are exactly what a synthesis tool searches for.

13.2.4

The Duality Principle

Every law so far has come in a matched pair. One statement uses and with zero, and its partner uses or with one. That's no accident. The dual of an expression swaps every and with or, every or with and, every zero with one, and every one with zero. Variables and complements are left alone. The duality principle says that if an equation holds for all values, then its dual holds too. Its full proof rests on and and or playing exactly symmetric roles in the underlying axioms. That's beyond this course, but the pattern is visible in every pair of laws. For example, start from the first absorption law, and swap and with or. Out comes the second absorption law. So that second truth table wasn't strictly necessary. Duality halves the verification work: prove one member of each pair, and the other is guaranteed.

Table 13.2.5

Every Law Pair, by Duality

Here's every law pair from this section, organized by duality. Commutative, associative and distributive. Identity, complement, idempotent and absorption. In each row, the dual statement comes from the first by the same mechanical swap. So the two distributive laws, which look like two unrelated facts, are really one fact, seen through the symmetry between and and or that runs through the whole subject.

Takeaways

A Toolkit, Proved Completely

To summarize. Because Boolean variables take only zero or one, a finite truth table is a complete proof, not just supporting evidence. The commutative, associative and distributive laws mirror arithmetic, except that in Boolean algebra both distributive laws hold. The identity, complement and idempotent laws cover constants, complements and repeated variables. Absorption shows a variable swallowing an expression that already contains it. And duality pairs every law for free. Here's something to think about. In ordinary arithmetic, a plus b c is not usually equal to a plus b, times a plus c. Yet in Boolean algebra, or distributes over and. Try a few ordinary numbers to see exactly where the analogy fails. And consider what role the complement laws, which have no arithmetic counterpart, might play.

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 Algebra: Laws and Properties

What are the commutative, associative, and distributive laws in Boolean algebra?
The commutative laws say order doesn't matter, A\cdot B=B\cdot A and A+B=B+A. The associative laws say grouping doesn't matter, (A\cdot B)\cdot C=A\cdot(B\cdot C), and likewise for OR. The distributive laws are A\cdot(B+C)=A\cdot B+A\cdot C and A+(B\cdot C)=(A+B)\cdot(A+C). Each can be proved with an eight-row truth table.
Does OR distribute over AND in Boolean algebra, and how is that different from ordinary arithmetic?
Unlike in ordinary arithmetic, OR does distribute over AND in Boolean algebra, so A+(B\cdot C)=(A+B)\cdot(A+C) holds for all values. In arithmetic, addition does not distribute over multiplication, since a+bc\neq(a+b)(a+c) in general. Boolean algebra has both distributive laws, and an eight-row truth table confirms the OR-over-AND version.
How does the absorption law help remove gates from a circuit?
The absorption law lets you replace A\cdot(A+B) or A+(A\cdot B) with just A, deleting the gates entirely. The input B has no effect on the output, whether it is 0 or 1, so a circuit with two gates can become a bare wire carrying A. A four-row truth table over A and B verifies both forms.
How does the duality principle give the partner of a Boolean law for free?
The duality principle says that if a Boolean equation holds for all values, its dual also holds. To form the dual, swap AND with OR and swap 0 with 1, leaving variables and complements alone. For example, swapping in A\cdot(A+B)=A gives A+(A\cdot B)=A. So you only need to prove one law in each pair.

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 →