1. ˆ

h(Q) = h(Q) for atomic sentences Q.

2. ˆ

h(¬Q) = true if and only if ˆ

h(Q) = false;

3. ˆ § R) = true if and only if h(Q) = true and ˆ

ˆ

h(Q h(R) = true;

4. ˆ ∨ R) = true if and only if h(Q) = true or ˆ

ˆ

h(Q h(R) = true, or both.

5. ˆ ’ R) = true if and only if h(Q) = false or h(R) = true, or

ˆ ˆ

h(Q

both.

6. ˆ ” R) = true if and only if ˆ ˆ

h(Q h(Q) = h(R).

A truth assignment h assigns values to every atomic sentence in the lan-

guage. But intuitively, to compute the truth table for a sentence S, we need

only ¬ll out the reference rows for the atomic sentences that actually appear

in S. In Exercise 17.3, we ask you to prove that the only values of h that

matter to ˆ h(S) are those assigned to the atomic constituents of S.

With this precise model of a truth assignment, we can give a mathematically modeling tautology

and consequence

precise version of our de¬nitions of a tautology and a tt-satis¬able sentence.

Namely, we say that S is a tautology if every truth assignment h has S coming

out true, that is, ˆ

h(S) = true. More generally, we say that a sentence S is a

tautological consequence of a set T of sentences provided every truth assign-

ment that makes all the sentences in T true also makes S true. Similarly, we

say that a sentence S is tt-satis¬able provided there is a truth assignment h tt-satis¬able

such that ˆh(S) = true. Similarly, a set T of sentences is tt-satis¬able if there

is a single assignment h that makes each of the sentences in T true.

Proposition 1. The sentence S is a tautological consequence of the set T if

and only if the set T ∪ {¬S} is not tt-satis¬able.

The proof of this result is left as an exercise.

Note that if T is ¬nite, we can reduce the question of whether S is a

tautological consequence of T to the question of whether a single sentence is

not tt-satis¬able, namely the conjunction of the sentences in T and ¬S.

Remember

A truth assignment is simply a function from the atomic sentences into

the set {true, false}. It models a single row of a complete truth table

for the language.

Section 17.1

470 / Advanced Topics in Propositional Logic

Exercises

17.1 Recall the three place symbol ™ discussed on page 192. Suppose we had included it as a

basic symbol of our language. Write out the clause for ˆ

h(™(P, Q, R)) that would be needed to

complete the de¬nition given above.

17.2 Recall the She¬er stroke symbol from Exercise 7.29, page 195. Suppose we had included it as

ˆ

a basic symbol of our language. Write out the clause for h(Q | R).

17.3 Let h1 and h2 be truth assignments that agree on (assign the same value to) all the atomic

ˆ ˆ

sentences in S. Show that h1 (S) = h2 (S). [Hint: use induction on w¬s.]

Section 17.2

Completeness for propositional logic

We are now in a position to prove the Completeness Theorem for propositional

logic ¬rst stated on page 219. Recall that we used the notation FT to stand

for that part of F that uses only the introduction and elimination rules for

§, ∨, ¬, ’, ” and ⊥. Given a set T of sentences and another sentence S, we

write T T S to mean that there is a formal proof of S in the system FT with

premises drawn from T . It is not assumed that every sentence in T is actually

used in the proof. For example, it might be that the set T is an in¬nite set of

sentences while only a ¬nite number can be used in any one proof, of course.

Notice that if T T S and T is a subset of some other set T of sentences, then

T T S. We restate the desired result as follows:

Theorem (Completeness of FT ) If a sentence S is a tautological consequence

Completeness of FT

of a set T of sentences then T T S.

You might think that the way to prove the Completeness Theorem would

be to assume that S is a tautological consequence of T and then try to con-

struct a proof of S from T . But since we don™t know anything about the

meaning of S or of the sentences in T , this strategy would get us nowhere.

In fact, the way we will prove the theorem is by proving its converse: that if

T T S (that is, if there is no proof of S from T ), then S is not a tautological

consequence of T . That is to say, we will show that if T T S, then there is

a truth assignment h that makes all of the sentences in T true, but S false.

In other words, we will show that T ∪ {¬S} is tt-satis¬able. The following

lemma will be helpful in carrying out this proof.

Chapter 17

Completeness for propositional logic / 471

Lemma 2. T ∪ {¬S} ⊥ if and only if T S.

T T

Proof: Assume that T ∪ {¬S} T ⊥, i.e., that there is a proof of

⊥ from premises ¬S and certain sentences P1 , . . . , Pn of T . By re-

arranging these premises, we can suppose the formal proof has the

following form:

P1

.

.

.

Pn

¬S

.

.

.

⊥

We can use this proof to construct a formal proof of S from T . Start

a proof with premises P1 , . . . , Pn . Immediately begin a subproof with

assumption ¬S. In that subproof, repeat the original proof of ⊥. End

the subproof and use ¬ Intro to conclude ¬¬S from P1 , . . . , Pn . Then

apply ¬ Elim to get S. The resulting proof will look like this:

P1

.

.

.

Pn

¬S

.

.

.

⊥

¬¬S

S

This formal proof shows that T T S, as desired. Proving the other

direction of this lemma is simple. We leave it as Exercise 17.13.

This lemma shows that our assumption that T T S is tantamount to

assuming that T ∪ {¬S} T ⊥. We can state our observations so far in a more

positive and memorable way by introducing the following notion. Let us say

that a set of sentences T is formally consistent if and only T T ⊥, that is, if formal consistency

and only if there is no proof of ⊥ from T in FT . With this notion in hand,

Section 17.2

472 / Advanced Topics in Propositional Logic

we can state the following theorem, which turns out to be equivalent to the

Completeness Theorem:

Theorem (Reformulation of Completeness) Every formally consistent set of

sentences is tt-satis¬able.

The Completeness Theorem results from applying this to the set T ∪ {¬S}.

The remainder of the section is devoted to proving this theorem. The proof is

outline of proof

quite simple in outline.

Completeness for formally complete sets: First we will show that this

theorem holds of any formally consistent set with an additional property,

known as formal completeness. A set T is formally complete if for any

formally complete set

of sentences sentence S of the language, either T T S or T T ¬S. This is really an

unusual property of sets of sentences, since it says that the set so strong

that it settles every question that can be expressed in the language,

since for any sentence, either it or its negation is provable from T .

Extending to formally complete sets: Once we show that every formally

consistent, formally complete set of sentences is tt-satis¬able, we will

show that every formally consistent set can be expanded to a set that

is both formally consistent and formally complete.

Putting things together: The fact that this expanded set is tt-satis¬able

will guarantee that the original set is as well, since a truth value assign-

ment that satis¬es the more inclusive set will also satisfy the original

set.

The rest of this section is taken up with ¬lling out this outline.

Completeness for formally complete sets of sentences

To prove that every formally consistent, formally complete set of sentences is

tt-satis¬able, the following lemma will be crucial.

Lemma 3. Let T be a formally consistent, formally complete set of sentences,

and let R and S be any sentences of the language.

1. T (R § S) i¬ T R and T S

T T T

2. T (R ∨ S) i¬ T R or T S

T T T

3. T ¬S i¬ T S

T T

4. T (R ’ S) i¬ T R or T S

T T T

Chapter 17

Completeness for propositional logic / 473

5. T (R ” S) i¬ either T R and T S or T R and T S

T T T T T

Proof: Let us ¬rst prove (1). Since it is an “i¬,” we need to prove that

each side entails the other. Let us ¬rst assume that T T (R § S).

We will show that T T R. The proof that T T S will be exactly

the same. Since T T (R § S), there is a formal proof of (R § S) from

premises in T . Take this proof and add one more step. At this step,

write the desired sentence R, using the rule § Elim.

Next, let us suppose that T T R and T T S. Thus, there are proofs

of each of R and S from premises in T . What we need to do is “merge”

these two proofs into one. Suppose the proof of R uses the premises

P1 , . . . , Pn and looks like this:

P1

.

.

.

Pn

.

.

.

R

And suppose the proof of S uses the premises Q1 , . . . , Qk and looks

like this:

Q1

.

.

.

Qk

.

.

.

S