Skip to content Skip to navigation

Connexions

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

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

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

      What is in a lens?

      Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the authors

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

Summary: The soundness and completeness of a system.

Are we done yet?

We have shown procedures1 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 (say) 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 1

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 the Redundancy of ∧∧: φ∧¬φ∨ψ≡φ∧ψ φ φ ψ φ ψ

Solution 2

Compare the last two columns in the following:

Truth table to prove Redundancy valid
aabb(¬a∨b)(¬a∨b)(a∧(¬a∨b))(a∧(¬a∨b))(a∧b)(a∧b)
falsefalsetruefalsefalse
falsetruetruefalsefalse
truefalsefalsefalsefalse
truetruetruetruetrue

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 a∧ba b and b∧ab 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.

Footnotes

  1. We have shown two procedures for each problem: by using truth tables, or by using Boolean algebra (propositional equivalences).

Comments, questions, feedback, criticisms?

Send feedback