¨

% r

j

2 3

r ¨

r ¨

r ¨

r¨

j¨

r%

4

5

¨r

¨ r

¨¨ rr

¨

% j

rc

6 7

r ¨

r ¨

r ¨

r¨

j¨

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