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. 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) 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)

2 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. 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.

3 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. 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}.

4 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)}.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.

5 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).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).

6 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)}.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.

7 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. 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.

8 Rememberthat pick an arbitraryx means that you don t know anything aboutxexceptthat it belongs to the universe (here the integers).4 x y(x>y). This statement is false. Once you pick a particularxyou canfind integersy(such asx+ 1) that are not less thanx. Hence not every integeryis less thanx. x y(x6=y). This statement is true. You can pick a particular value ofxandthen pick a particularythat is not equal tox. x y(x6=y). This statement is false. Once you pick particular value ofx, youwill not be able to show that every integeryis different fromx(because one ofthe values forywill be equal tox).Negations of is important to understand how negation interactswith quantifiers.

9 Here are the basic rules. xP(x) is equivalent to x( P(x)). xP(x) is equivalent to x( P(x)).Example:To understand x y(x>y), we compute x y(x>y) is equivalent to x( y(x>y))is equivalent to x y (x>y))is equivalent to x y(x y)).The last statement is clearly true (for anyxtakey=x+1), so our original statementis true. This gives a clear way to see that x y(x>y) (the second example givenin Sequences of Quantifiers ) is Proof StrategiesAproofstarts with a list ofhypothesesand ends with aconclusion. The proof showsthe step-by-step chain of reasoning from hypotheses to conclusion. Every step needsto be justified. You can use any of the reasons below to justify a step in your proof: A hypothesis.

10 A definition. Something already proved earlier in the proof. A result proved previously. A consequence of earlier steps according to a rule of inference. Some rules ofinference are listed sure to proceed one step at a time. Writing a good proof requires knowing defi-nitions and previously proved results, understanding how the notation and the logicworks, and having a bit of insight. It also helps to be familiar with some commonstrategies for different types of of table below gives some general rules of inference. State-ments in the first two columns are thepremises; the statement in the third columnis called rules of inference say that if you know the premises are both true (eitherbecause you are assuming them as hypotheses or because you have already provedthem), then you can conclude that the consequence is true as well.