Logic, Sets, and Proofs - Amherst

1 logic , Sets, and ProofsDavid A. Cox and Catherine C. McGeochAmherst College1 LogicLogical statementis a mathematical statement that can beassigned a value eithertrueorfalse. Here we denote logical statements with capitallettersA,B. Logical statements be combined with the following operators to formnew logical nameNotation I Notation II JavaAND (Conjunction)A BA BA&&BOR (Disjunction)A BA+BA||BNOT (Negation) A A!AIMPLIES (Implication)A BifAthenBIF AND ONLY IF (Equivalence)A BAiffB== is a list of tautologies.

2 In any proof, you can replace a statementin the first column with the corresponding statement in the second column, and viceversa. All of these can be proved by truth statement DescriptionA BB A is commutativeA BB A is commutative(A B) CA (B C) is associative(A B) CA (B C) is associativeA (B C) (A B) (A C) distributes over A (B C) (A B) (A C) distributes over A falseAfalse is identity for A trueAtrue is identity for A Atruelaw of excluded middleA AfalsecontradictionA AA is idempotentA AA is idempotent AAdouble negative (A B) A BDe Morgan s law for (A B)

3 A BDe Morgan s law for A B A Brewriting implicationA B B AcontrapositiveA (B C) (A B) Cconditional proofA B(A B) (B A) definition of 12 SetsAsetis a collection of objects, which are calledelementsormembersof the set. Twosets areequalwhen they have the same are three important sets: The set of allintegersisZ={.., 3, 2, 1,0,1,2,3,..}. The set of allreal numbersisR. The set with no elements is , theempty important set is the set ofnatural numbers, denotedNorN. Unfortunately,the meaning ofNis not consistent.

4 In some books,N={1,2,3,..},while in other books,N={0,1,2,3,..}.Basic Definitions and Notation. x S:xis an element or member :2 Z. x/ S:xis not an element ofS, , (x S).Example:12/ Z. S T: Every element ofSis also an element ofT. We say thatSis asubsetofTand :Z RandZ Z. S6 T: This means (S T), , some element ofSis not an element :R6 Z. S T: This means (S T) (S6=T). We say thatSis aproper subsetofTand thatTproperly containsorproperly :Z thatS=Tis equivalent to (S T) (T S).Describing are two basic ways to describe a set.

5 Listing elements: Some sets can be described by listing their elements insidebrackets{and}.Example:The set of positive squares is{1,4,9,16,..}. Whenlisting the elements of a set, order is unimportant, as are repetitions. Thus{1,2,3}={3,2,1}={1,1,2,3}since all three contain the same elements, namely 1, 2 and Set-builder notation: We can sometimes describe a set by the conditions itselements :The set of positive real numbers is{x R|x>0}.This can also be written{x|(x R) (x>0)}. A common alternativenotation uses the colon instead of the vertical bar, as in{x: (x R) (x>0)}.

6 Operations on sets. TheunionS Tis the setS T={x|(x S) (x T)}.Thus an element lies inS Tprecisely when it lies inat least oneof the :{1,2,3,4} {3,4,5,6}={1,2,3,4,5,6}{n Z|n 0} {n Z|n<0}=Z. TheintersectionS Tis the setS T={x|(x S) (x T)}.Thus an element lies inS Tprecisely when it lies inbothof the :{1,2,3,4} {3,4,5,6}={3,4}{n Z|n 0} {n Z|n<0}= . Theset differenceS Tis the set of elements that are inSbut not :{1,2,3,4} {3,4,5,6}={1,2}.A common alternative notation forS TisS\ Predicates and QuantifiersAvariablelikexrepresents some unspecified element from a fixed setUcalled theuniverse.

7 Apredicateis a logical statement containing one or more : xis even and x>y are predicates. The truth of the predicate depends onwhich particular members of the universe are plugged in for the combinequantifierswith predicates to form statements about members are two basic types:3 x U(P(x)). Thisuniversal quantifiermeansfor all (orfor everyorfor eachorfor any) value ofxin the universe,the predicateP(x) is : x R(2x= (x+ 1) + (x 1)). x U(P(x)). Thisexistential quantifiermeansthere exists a (orthere is at least one) value ofxin the universefor which the predicateP(x) is : x Z(x>5).

8 If the universe is understood, it may be omitted from the quantifier. For example,assuming that the universe isZ, the above predicate can be written x(x>5).A general strategy for proving things about predicates with quantifiers is toworkwith their elements one at a time. Even when we are dealing with universal quantifiersand infinite universes, we proceed by thinking about the properties that a particularbut arbitrary element of the universe would and predicateP(x) is often used to describe a set in terms ofthe set-builder notationS={x U|P(x)}.

9 This means that the setSconsists of all elements of the universe for which thepredicate is :The definitionS={n Z|n>5}meansn Sif andonly ifnis an integer greater than 5. If the universe is assumed to beZ, it can beleft out of the definition, so thatS={n|n>5}.We can recast claims about set inclusions using quantifiers and predicates. Thus:S Tis equivalent to x((x S) (x T))is equivalent to x S(x T)S6 Tis equivalent to x((x S) (x/ T))is equivalent to x S(x/ T).As a general rule, we prove things about sets by working with the predicatesthat define them.

10 We will see later that the equivalences forS Tlead to a usefulproof strategy. As with the case of quantifiers and predicates, provingS Tmeansworking with elements one at a of sequence of quantifiers may appear in front of apredicate. The order in which the quantifiers appear is very important to the meaningof the statement. Here are some examples, usingZas universe. x y(x>y). This statement is true. Once you pick an arbitraryx, you canfind a particular value fory(such asx 1) that is smaller thanx. Rememberthat pick an arbitraryx means that you don t know anything aboutxexceptthat it belongs to the universe (here the integers).