Multi-Page Printing

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