Propositions, Truth Values, and Truth Tables | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Propositions, Truth Values, and Truth Tables

Discrete Mathematics · Chapter 1: Logic and Mathematical ProofSection 1.3 · lesson 3 of 8711 min · free with a free account

← Types of Logical Fallacies and How to Recognize ThemNext lesson: Logical Connectives: AND, OR, NOT, and More →

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

Listing every combination - none missed, none checked twice.

  • Decide whether a sentence is a proposition
  • Distinguish simple from compound propositions
  • Count and enumerate the rows of a truth table
  • Build a complete truth table with sub-columns

Transcript

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

Logic and Mathematical Proof

Propositions, Truth Values, and Truth Tables

This section builds the truth table, the tool that makes sure no combination of conditions is ever missed, or checked twice. We'll start with the sentences logic can work on, called propositions. Then we'll separate simple propositions from compound ones. And then we'll count and list the rows of a truth table, and build a complete one, step by step.

The Opening Problem

3 Checks, 8 Combinations

Every time a card is charged, a payment processor's fraud system has a fraction of a second to decide whether the transaction looks legitimate. It never relies on a single signal. It checks several independent conditions at once. Does the amount exceed what's typical for this account? Does the purchase come from a country other than the billing address? Has this device ever been used on the account? Each check reduces to a single yes-or-no fact about the transaction. Before the team can trust the rule, they need to test it against every combination those checks could produce. Not just the two or three scenarios that come to mind first. With three independent checks, there are eight combinations. Miss one, and the rule ships with an untested blind spot. A truth table guarantees nothing is missed, and nothing is checked twice. It's a disciplined bookkeeping device, listing every combination in a fixed, repeatable order.

What Is a Proposition?

Exactly One Truth Value

Every statement in formal logic must first pass a basic test. Can it be given a truth value at all, and exactly one? A proposition is a declarative sentence with exactly one truth value. It's either true, written T, or false, written F. Never both, and never neither. That rules out three kinds of sentence. First, the sentence must be declarative. It asserts that something is, or isn't, the case, rather than asking, commanding, or exclaiming. Second, it must have a truth value at all. A sentence can be perfectly declarative in grammar, and still not have one. Third, it must have exactly one truth value. A sentence that could reasonably be read as both true and false also fails. So declarative form is necessary for a proposition, but it isn't sufficient. Both conditions must hold at once.

Table 1.3.1

Testing 6 Sentences

This table tests six sentences against the definition. New Delhi is the capital of India is declarative, and true. So it's a proposition. Close port eighty eighty on the firewall is a command. And is the server currently online is a question. Neither is declarative, so neither is true or false. x squared equals nine is declarative. But its truth depends on a variable, x, whose value hasn't been fixed. So it's not a proposition. This sentence is false is declarative too, but it's a self-referential paradox, with no consistent truth value. And this transaction exceeds one thousand dollars, said of one specific, known transaction, is a proposition. It refers to one fixed case with a known amount.

Rows 4 and 5

2 Different Ways to Fail

Rows four and five fail the definition in different ways, and the difference matters. x squared equals nine is grammatically declarative. But its truth value depends entirely on a value of x that hasn't been supplied. Logicians call this an open sentence, or a predicate. It becomes a proposition once every free variable is replaced by a specific value. When x equals three, x squared equals nine. That's a proposition, and it's true. This sentence is false has no free variable at all. Yet assigning either truth value produces a contradiction. If it's true, then what it asserts must hold, so it's false. If it's false, then what it asserts is true, so it's true. No stable truth value exists, so the sentence is excluded from propositional logic entirely. It isn't an open sentence waiting to be filled in. One is missing information that can be supplied. The other can't be repaired by supplying anything at all.

Simple and Compound

Building Blocks and Variables

Once a sentence is confirmed as a proposition, it can be classified further. A simple, or atomic, proposition can't be broken down into smaller propositions. A compound proposition combines two or more simple propositions using a logical connective. A propositional variable is a symbol, commonly p, q, r, or s, standing for an unspecified simple proposition. It lets us study an argument's structure apart from its content. Formal logic uses five common connective symbols, for and, or, not, implies, and if and only if. Section one point four defines exactly what each one does. For now, the rule joining propositions is simply given, as a table. That way the mechanics of recording truth values can be studied on their own. In the fraud example, p, the transaction amount exceeds one thousand dollars, is a simple proposition.

Theorem 1.3.1

How Many Rows a Truth Table Needs

Before any values are filled in, the table's shape must be settled. How many rows does it need? Here's the theorem. A complete truth table with n propositional variables has exactly two to the n rows, one for every possible assignment of truth values. The proof is short. Each variable independently takes one of two values, T or F. The value chosen for one doesn't restrict any other. So assigning all n variables is a sequence of n independent choices, each with two options. By the multiplication principle, which chapter five develops fully, the total is two times two, n times over. That's two to the n. And since the table needs one row for every assignment, and no two are the same, it has exactly two to the n rows. Check it with three variables. Two cubed is eight, matching the eight combinations the fraud system needed to test.

Procedure 1.3.1 - Block-Halving

The Standard Row Order

The rows also need a fixed order, so none is missed or repeated. The block-halving method provides one. List the variables left to right. Column i is filled in blocks of two to the power n minus i. That many T's, then that many F's, repeating to the bottom. With p, q, and r, that means p uses blocks of four, q uses blocks of two, and r alternates every row. So p is true for the first four rows and false for the last four. q alternates in pairs. And r flips every row. The leftmost variable changes slowest, and the rightmost changes fastest. Every assignment appears exactly once. And no compound expression has been introduced yet. This is the table's skeleton.

Figure 1.3.1

Enumeration as a Branching Tree

This figure shows the same enumeration as a branching tree. Each level fixes the truth value of one variable. First p, then q, then r. Every node splits into two, one branch for true and one for false. That's why the number of leaves doubles with each added variable. Follow any path from top to bottom, and you get one row. Read the eight leaves left to right, and you get all eight rows, in exactly the standard order.

The Same Method in Code

Precise Enough for a Computer

The block-halving method is precise enough to hand straight to a computer. This short Python function uses the standard library's product generator. Product with repeat equal to n produces every combination of true and false across n positions. It varies the last position fastest and the first slowest. That's exactly the block-halving pattern, expressed as code. Called with three, it prints eight tuples, from all true down to all false. They match the hand-built table row for row.

Procedure 1.3.2

Building a Complete Truth Table

A table with only the simple propositions filled in is just scaffolding. A useful truth table also records every compound expression built from them. Here's the general procedure. First, identify every simple proposition, and fix their left-to-right order. They become the leftmost columns. Second, with n simple propositions, compute two to the n rows. Third, fill those columns by block-halving. Fourth, add one sub-column for each intermediate compound expression, from the simplest, built first, to the most complex, built last. Fifth, fill each sub-column using its rule, looking only at columns already filled to its left. The rightmost column holds the expression under study. One subtlety. A sub-column may depend on only some of the variables. Its values then repeat, as another variable changes beneath it. That's expected, not an error.

Table 1.3.5

The Fraud Alert, Row by Row

Back to the fraud system, with all three signals. p is that the amount exceeds one thousand dollars. q is that the purchase comes from a different country. r is that the device is unrecognized. The specification supplies two rules as data. They're stand-ins, not the named connectives of the next section. Rule A defines an elevated-risk flag, M. M is true exactly when p and q are both true. Rule B defines the final alert. It's true when M is true, or r is true, or both. Take row one, where p, q, and r are all true. Rule A gives M true. Rule B, applied to M and r, gives the alert true. Every other row follows the same two steps, using only values already placed to the left. Read the final column. The alert fires in five of the eight combinations. Every row where the device is unrecognized, plus row two. In row two, the device is recognized, but the amount and location are both suspicious at once.

Takeaways

Mechanical Discipline

To summarize. A proposition is a declarative sentence with exactly one truth value. Declarative form is necessary but not sufficient, as open sentences and paradoxes show. Simple propositions can't be broken down. Compound propositions are built from them by a connecting rule. A truth table for n variables has exactly two to the n rows, by the multiplication principle. And block-halving lists every combination exactly once. A complete table puts the simple propositions first, then sub-columns in the order they're built, and the final expression last. Here's something to think about. x is an even integer, and this sentence is false, both fail the definition, for different reasons. Which one can be repaired by supplying missing information? And is there any comparable fix for the other?

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 Propositions, Truth Values, and Truth Tables

Is "x squared equals 9" a proposition?
No, x^2 = 9 is not a proposition, because its truth depends on a value of x that has not been fixed. A proposition must be a declarative sentence with exactly one truth value, T or F. This open sentence becomes a proposition once x is given a value. With x = 3, it is true. Questions and commands also fail the test.
What is the difference between a simple and a compound proposition?
A simple (atomic) proposition cannot be broken into smaller propositions, while a compound proposition joins two or more simple ones with a logical connective. For example, "the amount exceeds one thousand dollars" is simple. Propositional variables such as p, q, and r stand for simple propositions, so you can study an argument's structure apart from its content.
How many rows does a truth table have, and how do you list them?
A truth table with n propositional variables has exactly 2^n rows, because each variable independently takes T or F. Three variables give 2^3 = 8 rows. To list every row once, fill column i in blocks of 2^{n-i} T's, then that many F's, repeating. For p, q, r, the blocks have sizes 4, 2, and 1.
How do you build a complete truth table with sub-columns?
List the simple propositions as the leftmost columns, fill them in 2^n rows by block-halving, then add one sub-column for each compound piece, simplest first. Each sub-column uses only columns already filled to its left. For example, let M be true when p and q are both true, and let the alert be true when M or r is true. The alert column then has T in five of eight rows.

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 →