Tautologies and Contradictions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Tautologies and Contradictions

Discrete Mathematics · Chapter 1: Logic and Mathematical ProofSection 1.8 · lesson 8 of 878 min · free with a free account

← Writing Direct ProofsNext lesson: Sets and Set Notation →

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

Always true, always false - or a condition that actually means something.

  • Define tautology, contradiction, and contingency
  • Classify a compound proposition from its truth table
  • Explain why testing can't establish a tautology
  • Restate a logical equivalence as a tautology

Transcript

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

Logic and Mathematical Proof

Tautologies and Contradictions

This last section of chapter one sorts every compound proposition into one of three kinds. Some are true no matter what. Some are false no matter what. And most are somewhere in between. We'll define all three, classify propositions from their truth tables, and see why testing can never establish that something is always true. And we'll connect it all back to the logical equivalences of section one point six.

The Opening Problem

Always True, Never True

A guard clause in a web application's access-control code has been edited by three engineers over two years. By the time a security review reaches it, it reads, is admin, or not is admin, or has override. A static-analysis tool flags it at once. Condition is always true. That's not a style complaint. It means the guard provides no protection at all. It passes every request. Elsewhere in the same codebase, another condition reads, authenticated, and not authenticated, and has valid token. It's flagged as dead code. It's false for every request, so the branch behind it can never run. Both warnings rest on one idea. Some compound propositions are true whatever values their variables take, some are false whatever, and most are in between. That's what a meaningful condition should be.

Definitions 1.8.1-1.8.3

3 Possible Final Columns

Once a compound proposition's complete truth table is built, its final column can only look one of three ways. All true, all false, or a mixture. Each case has a name. A tautology is true under every possible assignment of truth values to its variables. Every entry in its final column is T. A contradiction is false under every possible assignment. Every entry in its final column is F. And a contingency is neither. Its final column contains at least one T and at least one F. The three cases are exhaustive, and mutually exclusive. So every compound proposition is exactly one of them. Never none, and never two at once.

What "Always True" Means

Every Assignment - Not Every Test

It's worth being precise about what always true means. A tautology isn't merely true for the values a programmer happened to test. It's true for every assignment, including combinations no one thought to check. That's exactly why the guard clause is dangerous. It looks like an ordinary condition. A handful of manual tests would show it returning true every time. But nothing in that testing distinguishes true for the cases I tried, from true for every case there is. Only an exhaustive method can. A complete truth table, or an equivalent symbolic argument.

Procedure 1.8.1

Classifying a Compound Proposition

The definitions turn classification into a mechanical procedure. First, construct the complete truth table, with a sub-column for every intermediate expression. Second, examine only the final column, the one for the overall expression. Not any intermediate sub-column. Third, read it. If every entry is T, it's a tautology. If every entry is F, it's a contradiction. If it has both, it's a contingency. Now the guard clause. Let p be the user is an administrator, and q be the user has an override flag. The flagged condition is p, or not p, or q.

Table 1.8.1

The Guard Clause Is a Tautology

Here's its truth table. Not p is the opposite of p in every row. So p or not p is true in every row, whatever p is. The final column is true in all four rows, regardless of q. By the procedure, that makes the guard clause a tautology. Once p or not p guarantees true on its own, or-ing anything else with it can't change the result. That's precisely why the guard clause passes every request, whoever is asking.

Tables 1.8.2 and 1.8.3

A Contradiction, and a Real Condition

The dead-code condition works the same way, in reverse. Let r be the request is authenticated, and t be it includes a valid session token. The branch is guarded by r, and not r, and t. r and not r is false in every row. So the final column is false in all four rows, and it's a contradiction. No value of t matters. The branch is unreachable, whatever a request looks like. For contrast, here's the condition those two were presumably meant to resemble. p and q. The user is an administrator, and has an override flag. Its final column has one T and three F's. It's a contingency, true for some assignments and false for others. That's what a meaningful access-control condition should look like.

Figure 1.8.1

Procedure 1.8.1 as a Flowchart

This figure turns the procedure into a decision flowchart. Build the table and read the final column. Is it all true? If yes, it's a tautology. If not, is it all false? If yes, it's a contradiction. If not, it's a contingency. The final columns read three different ways in the tables each route to exactly one label here. Every compound proposition reaches exactly one box, with no case left over.

Theorem 1.8.1

Equivalence as a Tautology

Section one point six established logical equivalences by showing two expressions share the same final column. Tautologies give a second way to state exactly the same fact. Here's the theorem. P is logically equivalent to Q if and only if P if and only if Q, the biconditional, is a tautology. The proof is short. P equivalent to Q means P and Q have the same truth value in every row. And by the definition of the biconditional, P if and only if Q is true in a row, exactly when P and Q agree in that row. So the biconditional is true in every row exactly when P and Q agree in every row. And true in every row is the definition of a tautology.

Table 1.8.4

The Laws of 1.6, Restated

So every equivalence from section one point six is a tautology, once it's restated with the biconditional. Not not p if and only if p. p and p, if and only if p. p or false, if and only if p. p and false, if and only if false. And one of De Morgan's laws. Not the quantity p and q, if and only if not p or not q. This is a restatement, not a new fact. The truth-table work for each law was already done in section one point six. But it's more than bookkeeping. Recognizing a tautology doubles as a way to check a claimed equivalence. If a proposed law's biconditional turns out to be a contingency, the law is simply false. And the table shows exactly which assignment breaks it.

Takeaways

Read the Whole Final Column

To summarize. Every compound proposition is exactly one of three things. A tautology, with a final column all true. A contradiction, all false. Or a contingency, mixed. Classification is mechanical. Build the complete truth table, and read only the final column. A tautology is true for every assignment, not just the ones tested. Sampling a few rows can suggest a tautology, but never establish one. And P is equivalent to Q exactly when P if and only if Q is a tautology. That's the bridge between equivalence and tautology. Here's something to think about. A developer tests a guard against three sample accounts, and it's true every time. A teammate says, good, it's a tautology. Is that sound? What would testing have to cover? And why might a tool that reasons about the formula's structure, settle it better than more testing ever could?

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 Tautologies and Contradictions

What is the difference between a tautology, a contradiction, and a contingency?
A tautology is a compound proposition that is true under every assignment of truth values, a contradiction is false under every assignment, and a contingency is true for some and false for others. Each one shows up in the final truth-table column: all T, all F, or a mix. For example, p \lor \neg p is a tautology, and p \land \neg p is a contradiction.
How do you tell from a truth table whether a proposition is a tautology, contradiction, or contingency?
Build the complete truth table, then read only the final column for the whole expression, ignoring intermediate columns. All T means tautology, all F means contradiction, and at least one T and one F means contingency. For p \land q, the final column has one T and three F's, so it is a contingency.
Why can't testing a few cases prove that a statement is a tautology?
A tautology must be true for every assignment, including ones nobody tried, and a few passing tests cannot distinguish "true for the cases I tried" from "true for every case." Sampling rows can suggest a tautology but not establish one. Only an exhaustive method, such as a complete truth table or an equivalent symbolic argument, can settle it.
How can a logical equivalence be written as a tautology?
P is logically equivalent to Q exactly when the biconditional P \leftrightarrow Q is a tautology. The biconditional is true in a row exactly when P and Q have the same truth value there, so it is true in every row exactly when they agree in every row. For example, De Morgan's law becomes \neg(p \land q) \leftrightarrow (\neg p \lor \neg q).

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 →