<<

. 85
( 107 .)



>>

the truth tables:
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

<<

. 85
( 107 .)



>>