# Connexions

You are here: Home » Content » Intro to Logic » using truth tables

• #### First-Order Logic

• ##### Reasoning with inference rules
• Exercises for First-Order Logic

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• Rice Digital Scholarship

This collection is included in aLens by: Digital Scholarship at Rice University

Click the "Rice Digital Scholarship" link to see all content affiliated with them.

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

# using truth tables

Summary: How to use truth tables to determine whether a formula is a tautology, and how to tell if two formulas are equivalent.

Seeing how we can express some concepts as some formulas, and how some formulas are tautologies while others might be true or false depending on the truth assignment, we come to a question: how can we determine when a formula is a tautology? How can we tell if two different formulas are equivalent for all truth assignments? We'll look at three different methods of answering these questions:

## Using Truth Tables

Is associative? In other words, is a(bc) a b c always equivalent to abc a b c ? What is a methodical way of answering questions of this type? We can make a truth table with two output columns, one for each formula in question, and then just check whether those two columns are the same.

### Exercise 1

Use truth tables to show that a bc a b c and ab c a b c aren't equivalent.

#### Solution

Table 1: Truth table to check associativity of implication
aabbcc(a(bc))(a(bc))((ab)c)((ab)c)
falsefalsefalsetruefalse
falsefalsetruetruetrue
falsetruefalsetruefalse
falsetruetruetruetrue
truefalsefalsetruetrue
truefalsetruetruetrue
truetruefalsefalsefalse
truetruetruetruetrue

By inspecting the two right-most columns, we see that the formulas are indeed not equivalent. They have different values for two truth-settings, those with a=falsea and c=falsec .

Thus we see that truth tables are a method for answering questions of the form “Is formula φφ equivalent to formula ψψ?” We make a truth table, with a column for each of φφ and ψψ, and just inspect whether the two columns always agree. A bit of a brute-force solution, but certainly correct.

What about the related question, “Is formula θθ a tautology?”. Well, obviously truth tables can handle this as well: make a truth table for the formula, and inspect whether all entries are true. For example, in the above problem, we could have made a truth table for the single formula a bc ab c a b c a b c . The original question of equivalence becomes, is this new formula a tautology?

The first approach is probably a tad easier to do by hand, though clearly the two approaches are equivalent. Another handy trick is to have three output columns you're computing: one for φ=a bc φ a b c , one for ψ= ab c ψ a b c , and one for φψ φ ψ; filling out the first two helper columns makes it easier to fill out the last column.

### Tip:

When making a truth table for a large complicated WFF by hand, it's helpful to make columns for sub-WFFs; as you fill in a row, you can use the results of one column to help you calculate the entry for a later column.

### Exercise 2

Is it valid to replace the conditional


int do_something(int value1, int value2)
{
bool a = …;
bool b = …;

if (a && b)
return value1;
else if (a || b)
return value2;
else
return value1;
}


with this conditional?


int do_something(int value1, int value2)
{
bool a = …;
bool b = …;

if ((a && !b) || (!a && b))
return value2;
else
return value1;
}


After all, the latter seems easier to understand, since it has only two cases, instead of three.

#### Solution

In the original code, we return value2 when the first case is false, but the second case is true. Using a WFF, when ¬(ab)(ab) a b a b . Is this equivalent to the WFF a¬b¬ab a b a b ? Here is a truth table:

Table 2: Truth table for comparing conditionals' equivalence
aabb¬(ab)¬(ab)(ab)(ab)(¬(ab)(ab))(¬(ab)(ab))(a¬b)(a¬b)(¬ab)(¬ab)((a¬b)(¬ab))((a¬b)(¬ab))
falsefalsetruefalsefalsefalsefalsefalse
falsetruetruetruetruefalsetruetrue
truefalsetruetruetruetruefalsetrue
truetruefalsetruefalsefalsefalsefalse

Yes, looking at the appropriate two columns we see they are equivalent.

So, how would do we use truth tables to reason about WaterWorld? Suppose you wanted to show that G-safeG-safe was true on some particular board. Clearly a truth table with the single column G-safeG-safe alone isn't enough (it would have only two rows — false and true — and just sit there and stare at you). We need some way to incorporate both the rules of WaterWorld and the parts of the board that we could see.

We can do that by starting with a huge formula that was the conjunction of all the WaterWorld domain axioms; call it ρρ. We would encode the board's observed state with another formula, ψψ. Using these, we can create the (rather unwieldy) formula that we're interested in: ρψG-safe ρ ψ G-safe . (Notice how this formula effectively ignores all the rows of the the truth-table that don't satisfy the rules ρρ, and the rows that don't correspond to the board we see ψψ: because of the semantics of , whenever ρψρ ψ is false, the overall formula ρψG-safe ρ ψ G-safe is true.)

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks