Laws of Logic and Logical Equivalence | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Laws of Logic and Logical Equivalence

Discrete Mathematics · Chapter 1: Logic and Mathematical ProofSection 1.6 · lesson 6 of 879 min · free with a free account

← Conditional Statements: If-Then, Converse, Inverse, and ContrapositiveNext lesson: Writing Direct Proofs →

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

Proving 2 expressions identical - without building a truth table.

  • Define logical equivalence
  • State and apply the basic, commutative, associative, and distributive laws
  • Apply De Morgan's Laws to push a negation inward
  • Chain named laws into a complete equivalence proof

Transcript

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

Logic and Mathematical Proof

Laws of Logic and Logical Equivalence

This section builds a toolkit of algebraic laws for logic. With them, you can prove that two expressions are identical without building a truth table at all, which matters enormously once there are many variables. We'll define logical equivalence, work through the laws one family at a time, and then chain them into a complete proof.

The Opening Problem

Too Many Rows to Check

A cloud provider's firewall checks every incoming packet against a policy built from dozens of independent true-or-false conditions. Source IP range, destination port, protocol, time of day, account tier, and more. A policy with only twenty such conditions has a truth table with two to the twenty rows. That's over one million, far too many to check by hand. So security engineers prove equivalences algebraically instead. They rewrite one expression into another with a small set of named laws, justifying each step. A database query optimizer does the same kind of rewriting, when it restructures a filter so an index can use it. So does an automated theorem prover.

Definition 1.6.1 and Laws 1.6.1-1.6.4

Equivalence and 4 Basic Laws

Two propositions are logically equivalent when they have the same truth value, for every possible assignment of truth values to their variables. Equivalence is symmetric. If p is equivalent to q, then q is equivalent to p. So every law in this section can be applied in either direction. Here are four basic laws. Double negation says not not p is equivalent to p. The identity laws say p and true is just p, and p or false is just p. The domination laws say p or true is true, and p and false is false. And the idempotent laws say p and p is p, and p or p is p. Here, T means a proposition fixed as true, like a permanently enabled flag. F means one fixed as false, like a permanently disabled maintenance switch.

Removing Redundancy

A Legacy Rule, Simplified

Each of these laws removes something redundant, without changing what an expression computes. Suppose a legacy access rule, written defensively years ago, tests not not h and always on. h is the request uses HTTPS, and the always-on flag has been permanently true since a migration. Double negation turns not not h into h. So the rule becomes h and true. Then the identity law drops the constant, leaving just h. The rule engine can check that single condition, guaranteed to give identical results for every request. When two rule files are merged and happen to test the same condition twice, the idempotent law reduces it to one. And if a rule is ever or-ed with a permanently enabled emergency override, the domination law says the whole rule collapses to that override. Worth knowing before assuming the rest still matters.

Laws 1.6.5-1.6.7

Order, Grouping, and Distribution

The commutative and associative laws say that and, and or, don't care about the order or grouping of their operands. That matters operationally. Suppose a rule engine evaluates conditions left to right, and stops as soon as the result is known. The commutative law guarantees that checking the cheapest condition first changes only how fast the rule runs. It never changes what it evaluates to. The distributive laws are more powerful. p and the quantity q or r is equivalent to p and q, or p and r. And unlike ordinary arithmetic, it works the other way too. p or the quantity q and r is equivalent to p or q, and p or r. They let you pull a shared factor out of two terms, or push it into a compound term.

Table 1.6.1

Factoring a Firewall Rule

Here's a firewall rule. Grant access when the request comes from a trusted subnet, p, and uses either HTTPS, q, or SSH, r. Compactly, that's p and the quantity q or r. But a rule engine that can only store simple two-condition rules needs the expanded form, p and q, or p and r. Two separate rules, one per protocol. This table checks all eight combinations of p, q, and r. The compact form and the expanded form match in every single row. So both forms of the access rule are identical for every possible request.

Law 1.6.8

De Morgan's Laws

De Morgan's laws describe exactly what happens when a negation sits in front of a parenthesized and, or or. Not the quantity p and q is equivalent to not p or not q. And not the quantity p or q is equivalent to not p and not q. The negation distributes across both operands, and the connective flips. And becomes or, and or becomes and. Take the access rule allow equals p and q, where p is a trusted subnet and q is HTTPS. The block rule is its negation, not the quantity p and q. By De Morgan, that's not p or not q. Block the request if it's not from a trusted subnet, or if it doesn't use HTTPS. Either condition alone is enough. And there's no need to compute p and q first, and then negate it.

Worked Proof

Chaining the Laws

Now we can chain laws together. Every step is justified by naming its law, so the chain proves the two ends equivalent without listing a single row. Before deploying a rewritten firewall policy, a team must confirm that a faster rule, not p or the quantity not q and not r, behaves exactly like the audited original. The original is not the quantity, p and q, or r and p. First, the commutative law rewrites r and p as p and r. Second, the distributive law, applied right to left, factors out p. That gives not the quantity p and the quantity q or r. Third, De Morgan's law gives not p, or not the quantity q or r. Fourth, De Morgan again, on that last part, gives not q and not r. That's exactly the faster rule. Four named steps, whether the policy has three conditions or twenty.

Negation Normal Form

Every Negation on a Single Variable

Notice what the rewritten form accomplishes. Every negation now sits directly in front of a single variable, p, q, or r, rather than a compound expression. An expression in this shape is said to be in negation normal form. It's exactly the preprocessing step that SAT solvers and automated theorem provers require, before they search for a satisfying assignment. And a query optimizer does the same negation-pushing rewrite on a filter, so that a not can be evaluated one column at a time. The chain scales because each step is already proven correct for every possible assignment. So together, they prove the whole equivalence.

Figure 1.6.1

2 Equivalent Circuits

This figure shows the two rules from the worked proof as circuits. Panel A implements the original audited rule directly. p feeds two separate AND gates, their outputs go into an OR gate, and a final NOT gate negates the combined result. Panel B implements the rewritten rule. Every NOT gate applies to a single input, which is negation normal form. The two circuits reach their output through different sequences of gates. But they compute the same block signal for every possible combination of p, q, and r.

Table 1.6.3

Choosing a Law to Apply

This table is a quick decision guide. It matches a pattern you notice in an expression to the law that applies. A double negation calls for double negation, which removes both symbols. A term with a fixed constant calls for identity or domination. A repeated proposition calls for the idempotent law. Awkward order or grouping calls for the commutative or associative law. A shared factor calls for the distributive law, to factor or expand. And a negation in front of a parenthesized and, or or, calls for De Morgan. It pushes the negation inward, and flips the connective.

Takeaways

Algebra Instead of Enumeration

To summarize. Two propositions are equivalent exactly when they share a truth value under every assignment. That can be shown by a truth table, or by an algebraic proof. The basic laws remove redundant negations and fixed-value operands. Order and grouping can change freely, and the distributive laws factor or expand. De Morgan's laws are the standard tool for pushing a negation down toward individual variables. And chaining named laws proves an equivalence in a fixed number of steps, avoiding the two-to-the-n blowup of a truth table. Here's something to think about. In arithmetic, multiplication distributes over addition, but addition doesn't distribute over multiplication. In logic, both directions hold. So why might thinking of and as multiplication, and or as addition, lead a student astray?

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 Laws of Logic and Logical Equivalence

What does it mean for two logical statements to be logically equivalent?
Two propositions are logically equivalent when they have the same truth value for every possible assignment of truth values to their variables. A truth table can show this, or an algebraic proof using named laws. Equivalence is symmetric, so if p \equiv q then q \equiv p, and each law can be applied in either direction.
How do you use De Morgan's Laws to push a negation inward?
Distribute the negation over both operands and flip the connective: \neg(p \land q) \equiv \neg p \lor \neg q, and \neg(p \lor q) \equiv \neg p \land \neg q. For example, the negation of "trusted subnet and HTTPS" becomes "not trusted subnet or not HTTPS." Repeat until every negation sits directly on a single variable.
How do you prove two logical expressions are equivalent using laws instead of a truth table?
Rewrite one expression step by step into the other, naming the law that justifies each step. For \neg((p \land q) \lor (r \land p)): commutative gives p \land r, distributive factors out p, De Morgan gives \neg p \lor \neg(q \lor r), and De Morgan again gives \neg p \lor (\neg q \land \neg r).
How do I decide which law of logic to apply to an expression?
Match the pattern you see to the law. Use double negation for \neg\neg p, identity or domination for a fixed constant T or F, and idempotent for a repeated proposition. Use commutative or associative to reorder or regroup, and distributive for a shared factor to expand or factor. Use De Morgan for a negation in front of a parenthesized \land or \lor.

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 →