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 sufficient
for ψ (since whenever we have ϕ we have ψ, though we may also have
ψ when ϕ is false), and ψ is necessary for ϕ (since it is impossible to
