Building Truth Tables with Propositional Logic, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.3 Free with a free account

Building Truth Tables with Propositional Logic

Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.3 · lesson 41 of 6913 min · free with a free account

← Logic and Computation in Intelligent SystemsNext lesson: Expressing Knowledge Through First-Order Logic →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How connectives, truth tables and equivalence laws check what follows.

  • Translate English sentences into propositional formulas using the five connectives
  • Build a truth table and classify a formula as a tautology, contradiction or contingent
  • Test logical equivalence and entailment using truth table rows
  • Simplify formulas with equivalence laws such as De Morgan and absorption

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

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

Opening Question

Should the Smart Light Turn On

A smart-home system holds a rule: if motion is detected and it's night, turn on the light. Then it learns that motion was detected, and that it's night. Should the light go on? To a person, obviously. For a computer to reach it reliably, the rule and the facts need a language with exact meaning, and a mechanical way to check what follows. Propositional logic is the simplest such language. And the truth table is its simplest check: list every possible situation, and see what happens in each.

Definition

What Counts as a Proposition

A proposition is a statement that's either true or false, and not both. It doesn't matter whether we know which. The door is locked: a proposition. 7 is greater than 10: false, but still a proposition. Is the door locked? A question, not a proposition. Close the door: a command. And x is greater than 3 isn't one either, until x has a value. A basic statement is an atomic proposition, named with a capital letter, like P, Q, or R. Connectives build compound ones from them.

Five Connectives

Negation, Conjunction, Disjunction, Implication, Biconditional

There are five connectives. In print, each has its own symbol. On this board we write them as words and arrows. Negation, NOT P, is true when P is false. Conjunction, P AND Q, is true only when both are true. Disjunction, P OR Q, is true when at least one is true. Implication, if P then Q, drawn as an arrow, is false only when P is true and Q is false. And the biconditional, P if and only if Q, a double arrow, is true when both have the same value. Here's every case, row by row. Notice the implication column: its only false row is P true, Q false.

Common Confusions

Inclusive Or and Implication as Promise

Two connectives cause confusion. First, or is inclusive. For dessert, you may have cake or ice cream, usually means one or the other. But in logic, or also allows both. Second, implication is a promise. If you finish the project, I'll buy you lunch. The promise is broken in one case only: you finish, and I don't buy lunch. If you don't finish, I've broken nothing, whatever I do. That's why if P then Q is true whenever P is false. It says nothing about causes. It only rules out, P true with Q false.

Syntax Rules

Well-Formed Formulas and Precedence

Not every string of symbols is a sensible formula. A well-formed formula follows four rules. Every proposition symbol is a formula. If A is a formula, so is NOT A. If A and B are formulas, so are A AND B, A OR B, A implies B, and A if and only if B, each in parentheses. And nothing else is a formula. So, P AND OR Q, or P implies with nothing after it, are not well formed. To save parentheses, connectives bind in order, strongest first: NOT, then AND, then OR, then implies, then if and only if. So NOT P AND Q means, NOT P, AND Q. When unsure, add parentheses.

Translation

Turning English Words into Connectives

Translating English into logic: choose a symbol for each basic statement, then look for the connective words. P and Q, P but Q, P although Q: all are AND. But adds contrast, not meaning. If P then Q, P implies Q, and Q whenever P: all are, P implies Q. And watch out: P only if Q, also means P implies Q, because Q is needed for P. P unless Q means: if not Q, then P. Neither P nor Q is NOT P AND NOT Q. And not both P and Q is NOT, P AND Q, which is different. Example: the robot moves if the path is clear and the battery isn't low. With C, L and M, that's: C AND NOT L, implies M. Its main connective is the implication.

Quick Check

Only If Names a Requirement

Quick check. Let O mean the door opens, and B mean the badge is valid. Translate: the door opens only if the badge is valid. Which formula is it? Pause, and decide. O implies B. Only if names a requirement: if the door opened, the badge must have been valid. A valid badge is needed for opening. B implies O is the tempting reading, but it would promise that a valid badge always opens the door, and the sentence doesn't say that. And if and only if claims both directions at once.

Method

Building a Truth Table Step by Step

An interpretation, or model, gives each symbol a value, true or false. A truth table lists every interpretation, one per row. With n symbols, there are 2 to the n rows. To build one: list the symbols. Count the rows, 2 to the n. Fill the input columns systematically: the first is half true, then half false, the next alternates in blocks half that size, and so on. Then add one column for each sub-formula, from the innermost parts outward. And read the last column: it's the formula's value in every situation.

Worked Example

Exclusive Or from Basic Connectives

Work out: P OR Q, AND NOT, P AND Q. Two symbols, so four rows. First P OR Q: true, true, true, false. Then P AND Q: true only in the first row. Then NOT, P AND Q: false, true, true, true. The last column ANDs those two: false, true, true, false. It's true exactly when one of P and Q is true, and the other false. That's exclusive or, built from the connectives we already have.

Worked Example

Eight Rows for the Robot Rule

Now three symbols: the robot rule, C AND NOT L, implies M. Two to the three is eight rows. Work out NOT L, then C AND NOT L, then the implication. Seven rows make the rule true. Only one row makes it false: the path is clear, the battery isn't low, and yet the robot doesn't move. That's the promise idea again: broken only when its condition holds, and its result is missing.

Scaling Problem

Every New Symbol Doubles the Rows

Tables grow fast: every new symbol doubles the rows. At a million rows a second, 20 symbols take about a second. Thirty take about 18 minutes. Forty, about 13 days. And fifty, about 36 years. Truth tables are perfect for learning and for small problems. But real knowledge bases can hold hundreds of symbols, so faster methods come later in the course.

Classification

Tautology, Contradiction or Contingent

The last column classifies a formula. All true: a tautology, or valid. P OR NOT P is true in every situation. All false: a contradiction, or unsatisfiable, like P AND NOT P. A mix of true and false: contingent, like P implies Q. And any formula with at least one true is satisfiable. A bigger one: if P implies Q, and Q implies R, then P implies R. Check all eight rows, and every row comes out true. This chain rule is a tautology.

Equivalence

Contrapositive, Converse and Inverse

Two formulas are logically equivalent when they have the same value in every row. Compare P implies Q with four others. NOT P OR Q matches it in every row. So does the contrapositive: NOT Q implies NOT P. But the converse, Q implies P, and the inverse, NOT P implies NOT Q, differ in the row where P is false and Q is true. So, if it rains, the ground is wet, does not mean, if the ground is wet, it rained.

Entailment

Checking Only the Knowledge Base Rows

A knowledge base is a set of formulas assumed true. It entails a formula when, in every row where all the knowledge base is true, that formula is true too. Rows where the knowledge base is false don't matter. Test it: mark the rows where every knowledge base formula is true, and check the question formula there. One marked row where it's false is a counterexample. Modus ponens: P implies Q, and P. Only the row P true, Q true makes both hold, and Q is true there. Entailed. But P implies Q, and Q, doesn't entail P: the row P false, Q true is a counterexample. And the smart home: motion AND night implies light, motion, and night. Only one of eight rows makes all three true: the light row. So the light goes on.

Connections

Equivalence, Entailment and Contradiction Linked

These ideas connect. A is equivalent to B exactly when, A if and only if B, is a tautology. A knowledge base entails alpha when, the knowledge base implies alpha, is a tautology. And the knowledge base entails alpha when the knowledge base AND NOT alpha is a contradiction. That's a common trick: to prove a conclusion follows, add its negation, and look for a contradiction. Common mistakes: implication read as a cause, or as false when P is false; assuming the converse; an exclusive or; and checking every row for entailment, not just the knowledge base rows.

Quick Check

Rain or Snow, but Not Rain

Quick check. A knowledge base holds two formulas: Rain OR Snow, and NOT Rain. Does it entail Snow? Pause, and decide. Yes. Of the four rows, NOT Rain keeps only the two where Rain is false. Rain OR Snow then keeps only the one where Snow is true. So in every knowledge base row, Snow holds. No row breaks it, because the rows that would, have Rain false and Snow false, and they fail Rain OR Snow. And Rain being true is ruled out by the knowledge base itself.

Equivalence Laws

De Morgan, Absorption and Implication Elimination

Rebuilding a table every time is tedious, so the most useful equivalences were collected into laws, applied again and again. Double negation: NOT NOT P is P. Commutative: P AND Q is Q AND P. Distributive: P AND, Q OR R, is, P AND Q, OR, P AND R. And De Morgan: NOT, P AND Q, is NOT P OR NOT Q. Absorption: P AND, P OR Q, is just P. Implication elimination: P implies Q is NOT P OR Q. And contrapositive: P implies Q is NOT Q implies NOT P. Any part of a formula can be replaced by an equivalent, without changing the whole. That's substitution, and it lets us apply laws inside bigger formulas.

Worked Example

Simplifying Formulas with the Laws

Simplify NOT, P implies Q, OR P. Eliminate the implication: NOT, NOT P OR Q, OR P. De Morgan: NOT NOT P AND NOT Q, OR P. Double negation gives, P AND NOT Q, OR P. Commute it to P OR, P AND NOT Q. And absorption leaves just P. A second one: P implies Q, AND, P implies NOT Q. Eliminate both implications. Distribute in reverse: NOT P OR, Q AND NOT Q. That's NOT P OR false, which is just NOT P. A four-row truth table confirms each. And that's why the laws matter in AI: a rewrite costs a few steps, however many symbols there are, while a table doubles with each one.

Worked Example

Proving the Sensor Did Not Fail

Put it together. If the sensor fails, the alarm sounds. If the alarm sounds, the guard is called. The guard was not called. So the sensor did not fail. Is that valid? With S, A and G, the knowledge base is: S implies A, A implies G, and NOT G. The conclusion is NOT S. Build eight rows. Only one row makes all three true: S false, A false, G false. And there, NOT S is true. So the argument is valid. In words: no guard call means no alarm, which means no sensor failure. It's the contrapositive, used twice.

Key Takeaways

Connectives, Tables and Laws

To sum up. Formulas are built from propositions with five connectives, and implication is false only when the first part is true and the second false. A truth table has a row for each of the 2 to the n assignments, and a column for each sub-formula. It grows very quickly. The last column shows a tautology, a contradiction, or a contingent formula. Equivalent formulas have matching columns, and entailment checks only the knowledge base rows. And the equivalence laws rewrite formulas symbolically, without building a table.

Think About It

Two Rules for the Account Page

Something to think about. A rule-based assistant has two rules. If the user is signed in, show the account page. And if the user is not signed in, show the account page. Using the laws, what do the two rules together say about the account page? And is that what the designer intended?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 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 All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 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

Introduction to Artificial Intelligence 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 Building Truth Tables with Propositional Logic

When is an implication P implies Q false?
An implication P implies Q is false only when P is true and Q is false; in every other row it is true. Think of it as a promise: if you finish the project, I will buy you lunch is broken only if you finish and lunch never comes. When P is false, the implication is true whatever Q is, and it says nothing about causes.
How many rows does a truth table have?
A truth table has 2 to the n rows, where n is the number of distinct proposition symbols, so two symbols give 4 rows and three give 8. Each new symbol doubles the table. At a million rows per second, 20 symbols take about a second, 30 about 18 minutes, and 50 about 36 years, which is why large knowledge bases need faster methods.
What is the difference between the converse and the contrapositive?
The contrapositive of P implies Q is NOT Q implies NOT P, and it is logically equivalent to the original, while the converse, Q implies P, is not. A truth table shows the converse differs in the row where P is false and Q is true. So if it rains, the ground is wet means a dry ground rules out rain, but a wet ground does not prove it rained.
How do you use a truth table to check entailment?
Mark the rows where every formula in the knowledge base is true, then check the conclusion in those rows only. If it is true in all of them, the knowledge base entails it; one marked row where it is false is a counterexample. From Rain OR Snow and NOT Rain, the only marked row has Snow true, so Snow is entailed. Checking every row instead is a common mistake.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 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 Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 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 Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 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 3 credits in Introduction to Artificial Intelligence.

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

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →