10 2. Background

are ϕ & ψ and ψ & ϕ, though in natural language there are some

differences in connotation.

The disjunction of ϕ and ψ is written “ϕ or ψ” or “ϕ ∨ ψ.” It

is false when both ϕ and ψ are false, and true otherwise. That is,

ϕ ∨ ψ is true when at least one of ϕ and ψ is true; it is inclusive or.

English tends to use exclusive or, which is true only when exactly one

of the clauses is true, though there are exceptions. One such: “Would

you like sugar or cream in your coffee?” Again, ϕ ∨ ψ and ψ ∨ ϕ are

equivalent.

The negation of ϕ is written “not(ϕ),” “not-ϕ,” “¬ϕ,” or “∼ϕ.”

It is true when ϕ is false and false when ϕ is true. The potential

difference from natural language negation is that ¬ϕ must cover all

cases where ϕ fails to hold, and in natural language the scope of a

negation is sometimes more limited. Note that ¬¬ϕ = ϕ.

How does negation interact with conjunction and disjunction?

ϕ & ψ is false when ϕ, ψ, or both are false, and hence its negation

is (¬ϕ) ∨ (¬ψ). ϕ ∨ ψ is false only when both ϕ and ψ are false, and

so its negation is (¬ϕ)&(¬ψ). We might note in the latter case that

this matches up with English’s “neither...nor” construction. These

two negation rules are called De Morgan’s Laws.

Exercise 2.1.1. Simplify the following formulas.

(i) ϕ & ((¬ϕ) ∨ ψ)

(ii) (ϕ & (¬ψ) & θ) ∨ (ϕ & (¬ψ) & (¬θ))

(iii) ¬((ϕ & ¬ψ) & ϕ)

There are two classes of special formulas to highlight now. A

tautology is always true; the classic example is ϕ∨(¬ϕ) for any formula

ϕ. A contradiction is always false; here the example is ϕ & (¬ϕ). You

will sometimes see the former expression denoted T (or ) and the

latter ⊥.

To say ϕ implies ψ (ϕ → ψ or ϕ ⇒ ψ) means whenever ϕ is true,

so is ψ. We call ϕ the antecedent, or assumption, and ψ the conse-

quent, or conclusion, of the implication. We also say ϕ is suﬃcient

for ψ (since whenever we have ϕ we have ψ, though we may also have

ψ when ϕ is false), and ψ is necessary for ϕ (since it is impossible to