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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.