<<

. 2
( 11 .)



>>

¨ r
¨
% r
j
2 3
r ¨
r ¨
r ¨


r%
4


5
¨r
¨ r
¨¨ rr
¨
% j
rc
6 7
r ¨
r ¨
r ¨


r%
8

c
9
4 INTRODUCTION
Propositional Logic
CHAPTER 1


Language

Propositional logic (sometimes called sentential or predicate logic)
attempts to formalize the reasoning that can be done with connectives
like not, and , or , and if . . . then. We will de¬ne the formal language
of propositional logic, LP , by specifying its symbols and rules for as-
sembling these symbols into the formulas of the language.
Definition 1.1. The symbols of LP are:
1. Parentheses: ( and ).
2. Connectives: ¬ and ’.
3. Atomic formulas: A0, A1, A2, . . . , An , . . .
We still need to specify the ways in which the symbols of LP can
be put together.
Definition 1.2. The formulas of LP are those ¬nite sequences or
strings of the symbols given in De¬nition 1.1 which satisfy the following
rules:
1. Every atomic formula is a formula.
2. If ± is a formula, then (¬±) is a formula.
3. If ± and β are formulas, then (± ’ β) is a formula.
4. No other sequence of symbols is a formula.
We will often use lower-case Greek characters to represent formulas,
as we did in the de¬nition above, and upper-case Greek characters
to represent sets of formulas.1 All formulas in Chapters 1“4 will be
assumed to be formulas of LP unless stated otherwise.
What do these de¬nitions mean? The parentheses are just punc-
tuation: their only purpose is to group other symbols together. (One
could get by without them; see Problem 1.6.) ¬ and ’ are supposed to
represent the connectives not and if . . . then respectively. The atomic
formulas, A0, A1, . . . , are meant to represent statements that cannot
be broken down any further using our connectives, such as “The moon
is made of cheese.” Thus, one might translate the the English sen-
tence “If the moon is red, it is not made of cheese” into the formula
1
The Greek alphabet is given in Appendix B.
7
8 1. LANGUAGE

(A0 ’ (¬A1)) of LP by using A0 to represent “The moon is red” and
A1 to represent “The moon is made of cheese.” Note that the truth
of the formula depends on the interpretation of the atomic sentences
which appear in it. Using the interpretations just given of A0 and A1 ,
the formula (A0 ’ (¬A1)) is true, but if we instead use A0 and A1
to interpret “My telephone is ringing” and “Someone is calling me”,
respectively, (A0 ’ (¬A1)) is false.
De¬nition 1.2 says that that every atomic formula is a formula and
every other formula is built from shorter formulas using the connectives
and parentheses in particular ways. For example, A1123, (A2 ’ (¬A0 )),
and (((¬A1) ’ (A1 ’ A7)) ’ A7) are all formulas, but X3 , (A5 ),
()¬A41, A5 ’ A7 , and (A2 ’ (¬A0 ) are not.
Problem 1.1. Why are the following not formulas of LP ? There
might be more than one reason . . .
1. A’56
2. (Y ’ A)
3. (A7 ← A4)
4. A7 ’ (¬A5))
5. (A8A9 ’ A1043998
6. (((¬A1 ) ’ (A ’ A7) ’ A7 )
Problem 1.2. Show that every formula of LP has the same number
of left parentheses as it has of right parentheses.
Problem 1.3. Suppose ± is any formula of LP . Let (±) be the
length of ± as a sequence of symbols and let p(±) be the number of
parentheses (counting both left and right parentheses) in ±. What are
the minimum and maximum values of p(±)/ (±)?
Problem 1.4. Suppose ± is any formula of LP . Let s(±) be the
number of atomic formulas in ± (counting repetitions) and let c(±) be
the number of occurrences of ’ in ±. Show that s(±) = c(±) + 1.
Problem 1.5. What are the possible lengths of formulas of LP ?
Prove it.
Problem 1.6. Find a way for doing without parentheses or other
punctuation symbols in de¬ning a formal language for propositional
logic.
Proposition 1.7. Show that the set of formulas of LP is count-
able.
Informal Conventions. At ¬rst glance, LP may not seem capable
of breaking down English sentences with connectives other than not
1. LANGUAGE 9

and if . . . then. However, the sense of many other connectives can be
captured by these two by using suitable circumlocutions. We will use
the symbols §, ∨, and ” to represent and , or ,2 and if and only if
respectively. Since they are not among the symbols of LP , we will use
them as abbreviations for certain constructions involving only ¬ and
’. Namely,
• (± § β) is short for (¬(± ’ (¬β))),
• (± ∨ β) is short for ((¬±) ’ β), and
• (± ” β) is short for ((± ’ β) § (β ’ ±)).
Interpreting A0 and A1 as before, for example, one could translate the
English sentence “The moon is red and made of cheese” as (A0 § A1 ).
(Of course this is really (¬(A0 ’ (¬A1 ))), i.e. “It is not the case that
if the moon is green, it is not made of cheese.”) §, ∨, and ” were not
included among the o¬cial symbols of LP partly because we can get
by without them and partly because leaving them out makes it easier
to prove things about LP .
Problem 1.8. Take a couple of English sentences with several con-
nectives and translate them into formulas of LP . You may use §, ∨,
and ” if appropriate.
Problem 1.9. Write out ((± ∨ β) § (β ’ ±)) using only ¬ and ’.
For the sake of readability, we will occasionally use some informal
conventions that let us get away with writing fewer parentheses:
• We will usually drop the outermost parentheses in a formula,
writing ± ’ β instead of (± ’ β) and ¬± instead of (¬±).
• We will let ¬ take precedence over ’ when parentheses are miss-
ing, so ¬± ’ β is short for ((¬±) ’ β), and ¬t the informal
connectives into this scheme by letting the order of precedence
be ¬, §, ∨, ’, and ”.
• Finally, we will group repetitions of ’, ∨, §, or ” to the right
when parentheses are missing, so ± ’ β ’ γ is short for (± ’
(β ’ γ)).
Just like formulas using ∨, §, or ¬, formulas in which parentheses have
been omitted as above are not o¬cial formulas of LP , they are conve-
nient abbreviations for o¬cial formulas of LP . Note that a precedent
for the precedence convention can be found in the way that · commonly
takes precedence over + in writing arithmetic formulas.
Problem 1.10. Write out ¬(± ” ¬δ) § β ’ ¬± ’ γ ¬rst with
the missing parentheses included and then as an o¬cial formula of LP .
2
We will use or inclusively, so that “A or B” is still true if both of A and B
are true.
10 1. LANGUAGE

The following notion will be needed later on.
Definition 1.3. Suppose • is a formula of LP . The set of subfor-
mulas of •, S(•), is de¬ned as follows.
1. If • is an atomic formula, then S(•) = {•}.
2. If • is (¬±), then S(•) = S(±) ∪ {(¬±)}.
3. If • is (± ’ β), then S(•) = S(±) ∪ S(β) ∪ {(± ’ β)}.
For example, if • is (((¬A1) ’ A7 ) ’ (A8 ’ A1)), then S(•)
includes A1 , A7, A8, (¬A1), (A8 ’ A1), ((¬A1 ) ’ A7 ), and (((¬A1 ) ’
A7) ’ (A8 ’ A1 )) itself.
Note that if you write out a formula with all the o¬cial parenthe-
ses, then the subformulas are just the parts of the formula enclosed by
matching parentheses, plus the atomic formulas. In particular, every
formula is a subformula of itself. Note that some subformulas of for-
mulas involving our informal abbreviations ∨, §, or ” will be most
conveniently written using these abbreviations. For example, if ψ is
A4 ’ A1 ∨ A4, then
S(ψ) = { A1 , A4, (¬A1 ), (A1 ∨ A4), (A4 ’ (A1 ∨ A4 )) } .
(As an exercise, where did (¬A1 ) come from?)
Problem 1.11. Find all the subformulas of each of the following
formulas.
1. (¬((¬A56) ’ A56))
2. A9 ’ A8 ’ ¬(A78 ’ ¬¬A0 )
3. ¬A0 § ¬A1 ” ¬(A0 ∨ A1)
Unique Readability. The slightly paranoid ” er, truly rigorous
” might ask whether De¬nitions 1.1 and 1.2 actually ensure that the
formulas of LP are unambiguous, i.e. can be read in only one way
according to the rules given in De¬nition 1.2. To actually prove this
one must add to De¬nition 1.1 the requirement that all the symbols
of LP are distinct and that no symbol is a subsequence of any other
symbol. With this addition, one can prove the following:
Theorem 1.12 (Unique Readability Theorem). A formula of LP
must satisfy exactly one of conditions 1“3 in De¬nition 1.2.
CHAPTER 2


Truth Assignments

Whether a given formula • of LP is true or false usually depends on
how we interpret the atomic formulas which appear in •. For example,
if • is the atomic formula A2 and we interpret it as “2+2 = 4”, it is true,
but if we interpret it as “The moon is made of cheese”, it is false. Since
we don™t want to commit ourselves to a single interpretation ” after
all, we™re really interested in general logical relationships ” we will
de¬ne how any assignment of truth values T (“true”) and F (“false”)
to atomic formulas of LP can be extended to all other formulas. We
will also get a reasonable de¬nition of what it means for a formula of
LP to follow logically from other formulas.
Definition 2.1. A truth assignment is a function v whose domain
is the set of all formulas of LP and whose range is the set {T, F } of
truth values, such that:
1. v(An ) is de¬ned for every atomic formula An .
2. For any formula ±,
T if v(±) = F
v( (±) ) =
F if v(±) = T .
3. For any formulas ± and β,
F if v(±) = T and v(β) = F
v( (± ’ β) ) =
T otherwise.

Given interpretations of all the atomic formulas of LP , the corre-
sponding truth assignment would give each atomic formula representing
a true statement the value T and every atomic formula representing a
false statement the value F . Note that we have not de¬ned how to
handle any truth values besides T and F in LP . Logics with other
truth values have uses, but are not relevant in most of mathematics.
For an example of how non-atomic formulas are given truth values
on the basis of the truth values given to their components, suppose
v is a truth assignment such that v(A0) = T and v(A1) = F . Then
v( ((¬A1) ’ (A0 ’ A1)) ) is determined from v( (¬A1) ) and v( (A0 ’
11
12 2. TRUTH ASSIGNMENTS

A1) ) according to clause 3 of De¬nition 2.1. In turn, v( (¬A1) ) is deter-
mined from of v(A1) according to clause 2 and v( (A0 ’ A1 ) ) is deter-
mined from v(A1) and v(A0) according to clause 3. Finally, by clause 1,
our truth assignment must be de¬ned for all atomic formulas to begin
with; in this case, v(A0) = T and v(A1) = F . Thus v( (¬A1) ) = T and
v( (A0 ’ A1) ) = F , so v( ((¬A1) ’ (A0 ’ A1)) ) = F .
A convenient way to write out the determination of the truth value
of a formula on a given truth assignment is to use a truth table: list all
the subformulas of the given formula across the top in order of length
and then ¬ll in their truth values on the bottom from left to right.
Except for the atomic formulas at the extreme left, the truth value of
each subformula will depend on the truth values of the subformulas to
its left. For the example above, one gets something like:
A0 A1 (¬A1) (A0 ’ A1 ) (¬A1 ) ’ (A0 ’ A1))
TF T F F
Problem 2.1. Suppose v is a truth assignment such that v(A0) =
v(A2) = T and v(A1) = v(A3) = F . Find v(±) if ± is:
1. ¬A2 ’ ¬A3
2. ¬A2 ’ A3
3. ¬(¬A0 ’ A1 )
4. A0 ∨ A1
5. A0 § A1
The use of ¬nite truth tables to determine what truth value a par-
ticular truth assignment gives a particular formula is justi¬ed by the
following proposition, which asserts that only the truth values of the
atomic sentences in the formula matter.
Proposition 2.2. Suppose δ is any formula and u and v are truth
assignments such that u(An ) = v(An ) for all atomic formulas An which
occur in δ. Then u(δ) = v(δ).
Corollary 2.3. Suppose u and v are truth assignments such that
u(An ) = v(An) for every atomic formula An . Then u = v, i.e. u(•) =
v(•) for every formula •.
Proposition 2.4. If ± and β are formulas and v is a truth assign-
ment, then:
1. v(¬±) = T if and only if v(±) = F .
2. v(± ’ β) = T if and only if v(β) = T whenever v(±) = T ;
3. v(± § β) = T if and only if v(±) = T and v(β) = T ;
4. v(± ∨ β) = T if and only if v(±) = T or v(β) = T ; and
5. v(± ” β) = T if and only if v(±) = v(β).
2. TRUTH ASSIGNMENTS 13

<<

. 2
( 11 .)



>>