■ To verify that two sets A and B are equal, written A = B, show that for every x, if x ∈ A, then x ∈ B, and if x ∈ B, then x ∈ A.
■ To verify that two sets A and B are not equal, written A ≠ B, find at least one element that is in A but not in B, or find at least one element that is in B but not in A. One or the other conditions sufces; you need not (and may not be able to) show both conditions.
■ To verify that A is a subset of B, written A ⊆ B, show that for every x, if x ∈ A, then x ∈ B. Notice that if A is a subset of B, it is possible that A = B.
■ To verify that A is not a subset of B, find at least one element that is in A but not in B.
■ To verify that A is a proper subset of B, written A ⊂ B, verify that A is a subset of B as described previously, and that A ≠ B, that is, that there is at least one element that is in B but not in A.
■ To visualize relationships among sets, use a Venn diagram. A Venn diagram can suggest whether a statement about sets is true or false.
■ A set of elements is determined by its members; order is irrelevant. On the other hand, ordered pairs and n-tuples take order into account.
Although there may be a shorter way to determine the truth values of a proposition P formed by combining propositions p1,..., pn using operators such as ¬ and ∨, a truth table will always supply all possible truth values of P for various truth values of the constituent propositions p1,..., pn.
■ In formal logic, “if” and “if and only if” are quite diferent. The conditional proposition p → q (if p then q) is true except when p is true and q is false. On the other hand, the biconditional proposition p ↔ q (p if and only if q) is true precisely when p and q are both true or both false.
■ To determine whether propositions P and Q, made up of the propositions p1,..., pn, are logically equivalent, write the truth tables for P and Q. If all of the entries for P and Q are always both true or both false, then P and Q are equivalent. If some entry is true for one of P or Q and false for the other, then P and Q are not equivalent.
■ De Morgan’s laws for logic ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q give formulas for negating “or” (∨) and negating “and” (∧). Roughly speaking, negating “or” results in “and,” and negating “and” results in “or.”
■ Example 1.3.13 states a very important equivalence ¬(p → q) ≡ p ∧ ¬q, which we will meet throughout this book. This equivalence shows that the negation of the conditional proposition can be written using the “and” (∧) operator. Notice that there is no conditional operator on the right-hand side of the equation.
■ To prove that the universally quantified statement ∀x P(x) is true, show that for every x in the domain of discourse, the proposition P(x) is true. Showing that P(x) is true for a particular value x does not prove that ∀x P(x) is true.
■ To prove that the existentially quantified statement ∃x P(x) is true, find one value of x in the domain of discourse for which the proposition P(x) is true. One value sufces.
■ To prove that the universally quantified statement ∀x P(x) is false, find one value of x (a counterexample) in the domain of discourse for which the proposition P(x) is false.
■ To prove that the existentially quantified statement ∃x P(x) is false, show that for every x in the domain of discourse, the proposition P(x) is false. Showing that P(x) is false for a particular value x does not prove that ∃x P(x) is false.
■ To prove that ∀x∀y P(x, y) is true, where the domain of discourse is X × Y, you must show that P(x, y) is true for all values of x ∈ X and y ∈ Y. One technique is to argue that P(x, y) is true using the symbols x and y to stand for arbitrary elements in X and Y.
■ To prove that ∀x∀y P(x, y) is false, where the domain of discourse is X × Y, find one value of x ∈ X and one value of y ∈ Y (two values sufce—one for x and one for y) that make P(x, y) false.
■ To prove that ∀x∃y P(x, y) is true, where the domain of discourse is X × Y, you must show that for all x ∈ X, there is at least one y ∈ Y such that P(x, y) is true. One technique is to let x stand for an arbitrary element in X and then find a value for y ∈ Y (one value sufces!) that makes P(x, y) true.
■ To prove that ∀x∃y P(x, y) is false, where the domain of discourse is X × Y, you must show that for at least one x ∈ X, P(x, y) is false for every y ∈ Y. One technique is to find a value of x ∈ X (again one value sufces!) that has the property that P(x, y) is false for every y ∈ Y. Having chosen a value for x, let y stand for an arbitrary element of Y and show that P(x, y) is always false.
■ To prove that ∃x∀y P(x, y)is true, where the domain of discourse is X×Y, you must show that for at least one x ∈ X, P(x, y) is true for every y ∈ Y. One technique is to find a value of x ∈ X (again one value sufces!) that has the property that P(x, y) is true for every y ∈ Y. Having chosen a value for x, let y stand for an arbitrary element of Y and show that P(x, y) is always true.
■ To prove that ∃x∀y P(x, y) is false, where the domain of discourse is X × Y, you must show that for all x ∈ X, there is at least one y ∈ Y such that P(x, y) is false. One technique is to let x stand for an arbitrary element in X and then find a value for y ∈ Y (one value sufces!) that makes P(x, y) false.
■ To prove that ∃x∃y P(x, y) is true, where the domain of discourse is X × Y, find one value of x ∈ X and one value of y ∈ Y (two values sufce—one for x and one for y) that make P(x, y) true.
■ To prove that ∃x∃y P(x, y) is false, where the domain of discourse is X × Y, you must show that P(x, y) is false for all values of x ∈ X and y ∈ Y. One technique is to argue that P(x, y) is false using the symbols x and y to stand for arbitrary elements in X and Y.
■ To negate an expression with nested quantifiers, use the generalized De Morgan’s laws for logic. Loosely speaking, ∀ and ∃ are interchanged. Don’t forget that the negation of p → q is equivalent to p ∧ ¬q.