Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Propositional Logic: soundness and completeness

Navigation

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? tag icon

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

This content is ...

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 module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "Intro to Logic"

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

Recently Viewed

This feature requires Javascript to be enabled.
 

Propositional Logic: soundness and completeness

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen. E-mail the authors

Summary: The soundness and completeness of a system.

Are we done yet?

We have shown procedures, using both truth tables and equivalences, for solving two different logic problems:

  • Equivalence: Show whether or not two WFFs φφ and ψψ are equivalent (the same under any truth assignment);
  • Tautology: Show whether or not a given WFF φφ is a tautology (true under all truth assignments).

Exercise 1

Which of these two logic problems seems harder than the other? That is, suppose you have a friend who can solve any Equivalence problem efficiently. But you want to open a business which will solve any Tautology problem efficiently. Can you open your business and, by subcontracting out specific Equivalence problems to your friend, really solve any Tautology problem brought to you? This question is sometimes phrased as “ Does Tautology reduce to Equivalence? ” Or, does it work the other way: does Equivalence reduce to Tautology?

Solution

We can indeed reduce the question of Tautology to the question of Equivalence: if somebody asks you whether φφ is true, you can just turn around and ask your friend whether the following two formulas are equivalent: φφ, and true. Your friend's answer for this variant question will be your answer to your customer's question about φφ. Thus, the Tautology problem isn't particularly harder than the Equivalence problem.

But also, Equivalence can be reduced to Tautology: if somebody asks you whether φ is equivalent to ψ, you can construct a new formula (φψ)(ψφ) φ ψ ψ φ . This formula is true exactly when φ and ψ are equivalent. So, you ask your friend whether this bigger formula is a tautology, and you then have your answer to whether the two original formulas were equivalent. Thus, the Equivalence problem isn't particularly harder than the Tautology problem!

Given these two facts (that each problem reduces to the other), we realize that really they are essentially the same problem, in disguise.

But we have a more fundamental question to ask, about the method of using Boolean algebra (propositional equivalences) to prove something: Where does the initial list of allowable equivalences come from, and how do we know they're valid? The answer is easy each equivalence can be verified by a truth table!

Exercise 2

Using a truth table, show the validity of conjunctive Redundancy: φ(¬φψ)φψ φ φ ψ φ ψ

Solution

Compare the last two columns in the following:

Table 1: Truth table to prove validity of conjunctive Redundancy
aa bb ¬ab a b a(¬ab) a a b ab a b
false false true false false
false true true false false
true false false false false
true true true true true

This is called soundness of Boolean algebra: If, using our propositional equivalence rules, we derive that φ and ψ are equivalent, then truly they are equivalent. (Whew!)

By the way, there is one subtle point: our truth table tells us that aba b and bab a are equivalent. But then suddenly we generalize this to saying that for any formulas φ and ψ, φψφ ψ and ψφψ φ are also equivalent. What lets us justify that step? It's because any given formula will be either true or false, so we can reduce the entire formula to a single true/false proposition.

Is Boolean algebra enough? Does our list of allowable propositional equivalences include everything you'll need? That is, could I have asked as a homework problem to show some two formulas equivalent (using Boolean algebra), and even though they really are equivalent, there aren't enough rules to on our list to let you finish the homework? Hmm, good question! The property we desire here is called the completeness of Boolean algebra: any equivalence which is true can be proved.

It turns out that, given any two formulas which really are equivalent, Boolean algebra is indeed sufficiently powerful to show that. Put both formulas into CNF (or, DNF); if the truth tables are equal then the CNF formulas will be equal. (Well, there are a few details to take care of: you have to order the clauses alphabetically, eliminate any duplicate clauses, and include all variables in each clause. This might be tedious, but not difficult.) Thus, Boolean algebra is complete, since (we state without proof) this procedure can always be carried out.

The concepts of soundness and completeness can be generalized to any system.

Definition 1: soundness
If the system (claims to) prove something is true, it really is true.
Definition 2: completeness
If something really is true, the system is capable of proving it.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

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

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add 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? tag icon

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