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.

      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
  • E-mail the authors
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

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.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

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 ¬a∨b a b a∧(¬a∨b) a a b a∧b 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 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.

Comments, questions, feedback, criticisms?

Send feedback