Disrete Structure Lesson 1

CSE/IT/IS 214/Math E 211 – DISCRETE STRUCTURES ( Math 217 old)
References:
R1 Kolman, Bernard and Busby, Robert . ( 1987 ) .Discrete Mathematical Structures for
Computer Science, 2nd ed. . London : Prentice Hall International
R2 Johnsonbaugh, Richard . ( 1993 ) . Discrete Mathematics, 3rd ed.. Macmillian Publishing Company
R3 Kolman, Bernard , Busby, Robert C. and Ross, Sharon Cutler . ( 2000 ) . Discrete
Mathematical Structures, 4th ed. . Upper Saddle River, New Jersey : Prentice-Hall Inc.

CHAPTER I. LOGIC AND PROOFS
LOGIC is the discipline that deals with reasoning. On an elementary level, logic provides rules and techniques for determining whether a given argument is valid. Logical reasoning is used in mathematics to prove theorems, in computer science, to verify the correctness of programs and to prove theorems, in natural and physical sciences to draw conclusions from experiments, in social sciences, and in our everyday lives, to solve a multitude of problems

A STATEMENT or a PROPOSITION is a declarative sentence that is either true or false but not both. It is typically expressed as a declarative sentence (as opposed to question or command ). Propositions are the basic building blocks of any theory of logic.

Which of the following are statements or proposition ?
1. The only positive integer that divide 7 are 1 and 7 itself.
2. 2 + 4 = 6
3. The earth is round.
4. 4 – x = 7.
5. Do you speak Chinese ?
6. Take two paracetamol.
7. Buy three tickets for the Manny Pacquiao bout on June 29, 2008.
8. The only positive integer that divide 12 are 3, 4 and itself.
9. A square is a rectangle having all sides equal.
10. Please come on time everyday to avoid being late.
11. Why is it required to enroll prerequisite subjects first ?
12. The rock samples from the moon were studied in the NASA laboratory.

Answers :
1. true, n is prime if n > 1 and can only be divided by 1 and itself ( statement )
2. true. 3. true ( statement )
4. is a declarative sentence, but not a statement, since it is true or false depending on the
value of x that is used.
5. is a question, so it is not a statement.
6. it is not a statement, it is a command.
7. is neither true nor false, it is a command.

LOGICAL CONNECTIVES AND COMPOUND STATEMENTS
The Connectives are AND, OR, NOT, IF...THEN, and IF and ONLY IF
Let us define the meaning of these connectives by showing the relationship between the truth value (i.e. true or false) of composite propositions and those of their component propositions. They are going to be shown using truth table In the tables P and Q represent arbitrary propositions, and true and false are represented by T and F, respectively.

In mathematics, the letters x, y, z . . . denote variables that can be replaced by real numbers, and they can be combined by the operations + , x , – , and . In logic, the letters p, q, r . . . denote propositional variables, that is, variables that can be replaced by statements. Statements or propositional variables can be combined by logical connectives to obtain compound statements or propositions..

Definition 1.1.1 : Let p and q be propositions.
The conjunction of p and q, denoted by p  q, is the proposition p and q.
The disjunction of p and q, denoted by p V q, is the proposition p or q.
The negation of p, denoted by p or ( P), is the proposition not p.
Propositions such as p  q and p V q that result from combining propositions are called compound propositions. The compound statement p  q is true when both p and q are true; otherwise, it is false. The compound statement p V q is true if at least one of p or q is true, it is false when both p and q are false.
The truth values of propositions such as conjunctions and disjunctions can be described by truth tables. The truth table of a proposition p made up of the individual propositions p1. . . pn, lists all possible combinations of truth values for p1. . . pn, T denoting true and F denoting false and for each such combination lists the truth value of p.


Truth Tables

P AND Q ( P  Q ) P OR Q (P V Q ) not p (  p or P )

P Q P  Q P Q P V Q p ( P)

T T T T T T T F
T F F T F T F T
F T F F T T
F F F F F F


AND. The table shows that (P Q) is true if both P and Q are true, and that it is false in any other case.
NOT: The table shows that if P is true, then (~P) is false, and that if P is false, then (~P) is true.

Examples :
1. p : 2 + 3 = 7 , q : A century is 100 years.
a) P is false and q is true. The conjunction p  q : 2 + 3 = 7 and a century is 100 years is false.
b) The disjunction p V q : 2 + 3 = 7 and a century is 100 years is true.
2. p : Kidapawan City is the capital of Cotabato. , q : Cotabato is in Mindanao.
a) P is true and q is true. The conjunction p  q : Kidapawan City is the capital of
Cotabato and Cotabato is in Mindanao is true.
b) The disjunction p V q : The conjunction p  q : Kidapawan City is the capital of
Cotabato and Cotabato is in Mindanao is true.
3. p : i 2 = –1 , q : e = 2.7182818

4. P : i = √–1 , q : The seventh month is August.
5. P : The 2nd day of the week is Friday , q : June 12 is labor day.
6. p : Rizal is from Leyte. , q : Dagohoy is from Bohol
7. P : Snakes are reptiles. , q : Birds are mammals.


Example : P : Discrete mathematics is easy. Not P : Discrete mathematics is not easy.
P : The price of rice is increasing. Not P : The price of rice is not increasing.

Evaluate the truth value for each proposition if the statements p = F , q = T and r = F.
1. p V q 4. p V r 7. p  r 10. p  q
2. ~P V r 5. r V q 8. r  q 11. ~P  r
3. ~P V ~q 6. p V ~r 9. p ~r 12. ~P ~q

Write the truth table for each proposition.
1. p ~q 2. ( p V q )  ~ p 3. (~p V ~q ) V p 4. ( p  q ) V (~p V q )

Determine whether each statement is True or False.
1. 3 < 7 and 7 < 9 2. It is not the case that ( 3 < 7 and 7 < 9 )


Formulate the symbolic expression in words using p : Today is Friday,
q : It is sunny, and r : It is cold.

1. p V q 2. ~ ( p V q )  r 3. ( p  q )  (~ ( r V p ) ) 4. ( p  r ) V q

QUANTIFIERS
We used the notation P ( x ) to denote a sentence or a statement P concerning the variable object x. The set defined by P ( x ), written { x | P ( x ) }, is a collection of all objects for which P is sensible and true. For example, { x | x is a positive integer less than 4} is the set { 1, 2, 3 } described by listing its elements.
A sentence P ( x ) is also called predicate, because in English the property is grammatically a predicate. P ( x ) is also called a propositional function, because each choice of x produces a proposition P ( x ) that is either true or false. Another use of predicate is in programming. Two common constructions are “ if P ( x ), then execute certain steps”, and “ while Q( x ), do specified actions”. The predicates P ( x ) and Q ( x ) are called the guards for the block of programming code. Often the guard for block is a conjunction or disjunction.
Example : Let A = { x | x is an integer less than 6 }. Here P ( x ) is the sentence “ x is an integer less than 6.” The common property is “ is an integer less than 6”. Since P ( 3 ) is true, 3  A , P ( 7 ) is false, 7  A.

1. Universal Quantifier
The Universal Quantifier of a predicate P ( x ) is the statement “For all values of x, P ( x ) is true”. It is assumed that only values of x that make sense in P ( x ) are considered. The universal quantification P ( x ) is denoted by x P ( x ). The symbol  is called a universal quantifier. Universal quantification can also be stated as “For every x”, “Every x”, or “For any x”.
Example 2. The sentence P ( x ) : – ( – x ) = x is a predicate that make sense for real numbers x.
The universal quantification of P ( x ), x P(x), is a true statement, because for all real numbers, – ( – x ) = x.
Example 3. Let Q ( x ) : x + 3  7. Then x Q ( x ), is a false statement because Q ( 6 ), is not true.

A predicate may contain several variables. Universal quantification maybe applied to each of the variables. For example the commutative property can be expressed as x y x  y = y  x. The order in which the universal quantifier are considered does not change the truth value. Often mathematical statements contain implied universal quantification.
Example 4. Commutative property on sets:
1. A  B = B  A 2. A  B = B  A

2. Existential Quantifier
The Existential Quantification of a predicate P ( x ) is the statement “There exist a value of x for which P ( x ) is true”. The existential quantification of P ( x ) is denoted by x P ( x ). The symbol  is called the existential quantifier. x can also be read as “There exist an x”, “There is some x”, “There exist an x”, or “There is at least one x”.
Example 5. Let Q ( x ) : x + 2  5. The existential quantification of Q ( x ), x Q( x ) is a true
statement because Q (1) is a true statement. Q (4) is false.

Example 6. The statement y y + 4 = y is false. There is no value of y for which the proportional
function y + 4 = y produces a true statement.

More examples.
1. Let p: For all positive integers n, n2 + 41 n + 41 is a prime number.
Then ~p is : There is at least one positive integer n for which n2 + 41n + 41 is not prime.
2. Let q : There is some integer k for which 12 = 3k. Then ~q : For all integers k, 12  3k.

Exercises from reference R3.
P ( x ) : x is even, Q( x ): x is a prime number, R ( x , y ) : x + y is even. The variables x and y are
integers. Write an English sentence corresponding to the following :
[14/51] a) x P(x) b) x Q( x )
[15/51] a) x y R( x , y ) b) x y R( x , y )
[16/51] a) x (~Q( x ) ) b) y (~ P ( y ) )
[17/51] a) ~ ( x ( P ( x ) ) b) ~ (x Q( x ) )
CONDITIONAL PROPOSITIONS AND LOGICAL EQUIVALENCE
Definition 1.2.1 : Let p and q be propositions.
If p and q are propositions, the compound proposition if p then q is called a conditional
proposition or implication and is denoted by p q.
The proposition p is called hypothesis ( or antecedent ) and the proposition q is called the conclusion ( or consequent ). The truth value is defined by the following table :

p q p  q
T T T
T F F
F T T
F F T

In logic, implication is used in a much weaker sense. To say that the compound statement p  q is true simply asserts that if p is true, then q will also be found to be true. In other words, p  q says that we will not have p true and q false at the same time. The truth values in the table shows p  q in terms of the truth values of p and q. Observed that p  q is considered false only if p is true and q is false. In particular, if p is false, then p  q is true for any q.

Example :
1. p : I am thirsty 2. p : It is smoking.
q : I will drink. q : 4 + 5 = 9
Answers: 1. If I am thirsty, then I will drink.
2. If it is smoking, then 4 + 5 = 9.
In the English language, and in mathematics, each of the following expressions is an equivalent form of the conditional statement p  q :
p implies q
q, if p
p only if q
p is a sufficient condition for q
q is a necessary condition for q
If p  q is an implication, then the converse of p  q is the implication q  p, and the contrapositive of p  q is the implication q  p.

Examples :
1. Give the converse and contrapositive of the implication “If it is raining, then I get wet”.
Solution : p : It is raining
q : I get wet.
Converse : If I get wet, then it is raining.
Contrapositive : If I do not get wet, then it is not raining.

Definition 1.2.2 : Let p and q be propositions.
If p and q are propositions, the compound proposition p if and only if q denoted by p  q is called an equivalence or biconditional proposition. The truth value is defined by the truth table below. Observe that p  q is true only when both p and q are True or when both are False. p q is also stated as p is a necessary and sufficient condition for q. Truth table is :

P q p  q
T T T
T F F
F T F
F F T

Example : 1. Is the statement 5 > 3 if and only if 0 < 5 – 3 true ?
Let p : 5 > 3 , q : 0 < 5 – 3. Since p is true and q is true, then p  q is true.

In general, a compound statement may have many component parts, each of which is itself a statement, represented by some proportional variable. The statement
s : p  ( q  ( p  r ) )
involves three propositions, p, q, and r, each of which may independently be true or false. There are altogether 23 = 8 possible combinations of truth values for p, q, and r, and the truth value for s contains n components statements, there will be 2 n entries needed in the truth table for s.
Step 1. The first n columns of the table are labeled by the component propositional variables.
Further column are constructed for all intermediate combinations of statements,
culminating in the given statement.
Step 2. Under each of the first n headings, we list the 2 n possible n-tuples of truth values of
the component statement s. Each n-tuple is listed on a separate row.
Step 3. For each row we compute, in sequence, all remaining truth values.
Ex. 2 : Compute the truth table of the statement ( p  q )  (~ q  ~p ). Also ( p  q)  ( p V q).

Solution : Using steps 1,2 and 3, construct the following table.

p q p  q  q  p  q   p ( p  q)  ( q   p) p V q ( p  q)  ( p V q)
T T T F F T T T T
T F F T F F T T F
F T T F T T T T T
F F T T T T T F F

A statement that is true for all possible values of its propositional variables is called a tautology (as in the truth table above).
A statement that is always false is called a contradiction or an absurdity.
A statement that can be either true or false, depending on the truth values of its propositional variables, is called a contingency.
In the example above :
a) The statement ( p  q )  ( q   p ) is a tautology.
b) The statement p   p is an absurdity.
c) The statement ( p  q )  ( p V q ) is a contingency.

We have defined a new mathematical structure with two binary operations and one unary operation, [ proposition,  , V,  ]. It makes no sense to say two propositions are equal; instead we say p and q are logically equivalent, if p  q is a tautology. When an equivalence is shown to be a tautology, it means that its two component parts are always either both true or both false, for any values of the proportional variables. Thus the two sides are simply different ways of making the same statement and can be regarded as “equal”. We denote that p is equivalent to q by p  q, now we can adopt our properties for operations to say this structure has a property if using equivalent in place of equal gives a true statement, thus we say that they are logically equivalent.

The binary operation V has the commutative property that is p V q  q V p. The truth value for
( p V q )  ( q V p ) shows the statement is a tautology.

p q p V q q V p ( p V q )  ( q V p )
T T T T T
T F T T T
F T T T T
F F F F T

OPERATIONS FOR PROPOSITIONS
Theorem 1. The operations for propositions have the following properties.
Commutative properties Distributive properties
1. p V q  q V p 5. p V ( q  r )  ( p V q )  ( p V r )
2. p  q  q  p 6. p  ( q V r )  ( p  q ) V ( p  r )

Associative properties Idempotent properties
3. p V ( q V r )  ( p V q ) V r 7. p V p  p
4. p  ( q  r )  ( p  q )  r 8. p  p  p
Properties of Negation
9. ~ ( ~ p )  p 10. ~ ( p V q )  ( ~ p )  ( ~ q ) 11. ~ ( p  q )  ( ~ p ) V ( ~ q )

Theorem 2 :
a) ( p  q )  ((~ p ) V q ) d) ~ ( p  q )  ( p  ~ q )
b) ( p  q )  (~ q  ~ p ) e) ~ ( p  q )  [ ( p  ~ q ) V (q ~ p ) ]
c) ( p  q )  [ ( p  q )  (q  p ) ]

Proof of Theorem 2a using truth table Proof of Theorem 2b using truth table

p q ~p p  q ~ p V q ~q ~p p  q ~ q ~ p
T T F T T F F T T
T F F F F T F F F
F T T T T F T T T
F F T T T T T T T



Theorem 3 :
a) ~ (  x P( x ) )   x ~ P( x )
b) ~ (  x P( x ))   x ~ ( P( x ) )
c)  x P( x )  Q( x )   x P( x )   x Q ( x )
d)  x P( x )   x Q ( x )   x P( x )  Q ( x )
e)  x ( P( x ) V Q ( x ) )   x P( x ) V  x Q ( x )
f)  x P( x )  Q ( x )   x P( x )   x Q ( x )
g) ( (  x P( x ) ) V ( x Q ( x )) )   x P( x ) V Q ( x ) ( is a tautology )
h)  x ( P( x )  Q ( x ) )   x P( x )   x Q ( x ) ( is a tautology )

Theorem 4 : Each of the following is a tautology.
a) p  q  p f) ~ ( p  q )  p
b) p  q  q g) ( p  ( p  q ) )  q
c) p  p V q h) ( ~ p  ( p V q )  q
d) q  ( p V q ) i) ( ~ q  ( p  q ) )  ~ q
e) ~ p  ( p  q ) j) ( ( p  q ) )  ( q  r ))  ( p  r )

Methods of proof
If an implication p  q is a tautology, where p and q maybe compound statements involving any number of propositional variables, we say that q logically follows from p. Suppose an implication of the form ( p1  p2  p3  …  pn )  q is a tautology, this implication is true regardless of the truth values of any of its components. Then we can say that q logically follows from p1, p2, . . . , pn. When q logically follows from p1, p2, . . . , pn then we write
p1
p2
.
.
.
pn .
 q

Virtually all mathematical theorems are composed of implications of the type ( p1  p2  p3  …  pn )  q. The pi’s are called the hypotheses, or premise and q is called the conclusion. To prove the theorem means to show that the implication is a tautology.
Note that we are not trying to show that q is true, but only that q will be true if all the Pi’s are true. For this reason , mathematical proofs often begin with the statement “ Supposed that p1, p2, . . . and pn are true ” and conclude with the statement “ Therefore, q is true.” The proof does not show that q is true but simply show that q has to be true if the Pi’s are all true.
Arguments based on tautologies represent correct methods of reasoning. Their validity depends only on the form of the statements involved and not on the truth values of the variables that they contain. Such arguments are called rules of inference. The various steps in the mathematical proof of a theorem must follow from the use of various rules of inference, and a mathematical proof of a theorem must begin with the hypotheses, proceed through various steps, each justified by some rule of inference, and arrive at the conclusion.
Ex. 1: According to Theorem 4 j [ ( p  q )  ( q  r ) ]  ( p  r ) is a tautology.
Thus the argument
p  q
q  r .
 p  r is universally valid, and so is a rule of inference.

Ex 2: Is the following argument valid ?

If you invest in the stock market, then you will get rich.
If you get rich, then you will be happy. .
 If you invest in the stock market, then you will be happy.

Solution : The argument is of the form given in Ex 1, hence the argument is valid, although
the conclusion may be false.

Ex. 3 : The tautology ( p  q )  [ ( p  q )  (q  p ) ] is Theorem 2c, thus both of the following
arguments are valid :
p  q
p  q q  p
 ( p  q )  (q  p )  p  q

Some mathematical theorems are equivalences, that is they are of the form p  q. They usually stated p if and only if q. By Ex 3, the proof of such theorem is logically equivalent with proving both p  q and q  p, and this almost always the way in which equivalences are proved. We first assume that p is true, and show that q must then be true; next we assume that q is true and show that p must then be true.
A very important rule of inference is :
p
p  q
 q That is, p is true, and p  q is true, so q is true.

Some rules of inference were given Latin names by classical scholars. Theorem 4g is referred to as modus ponens ( the method of asserting ). Theorem 4g is ( p  ( p  q ) )  q.

Ex 4: Is the following argument valid ?

Smoking is healthy.
If smoking is healthy, then cigarettes are prescribed by physicians .
 Cigarettes are prescribed by physicians.

The argument is valid since it is of the form modus ponens. However, the conclusion is false. Observed that the first premise p: smoking is healthy is false. The second premise p  q is then true and ( p  ( p  q ) ), the conjunction of the two premises, is false.

Ex. 5 : If taxes are lowered, then income rises.
Income rises .
 Taxes are lowered.
Solution : Let p : taxes are lowered and q : income rises
The argument is of the form p  q
q .
 p

Assume that p  q and q are both true. Now p  q may be true with p being false. Then the conclusion p is false. Hence the argument is not valid.

An important proof technique, called an indirect method of proof , follows from the tautology
( p  q )  ( ( ~ q )  ( ~ p ) ). This state, as previously mentioned, that an implication is equivalent to its contrapositive. Thus to prove p  q indirectly, we assume q is false ( the statement ~ q ) and show that p is then false ( the statement ~ p ).

Ex. 6. Let n be an integer. Prove that if n2 is odd, then n is odd.
Solution : Let p : n2 is odd and q : n is odd. We have to prove that p  q is true. Instead, we prove the contrapositive ~ q  ~ p. Suppose that n is not odd, so that n is even. Then n = 2k, where k is an integer . Then, n2 = ( 2k )2 = 4k2 = 2 ( 2k2 ), so n2 is even. Thus, we have shown that if n is even, n2 is even, which is the contrapositive of the given statement. Hence, the given statement has been proved.

Another important proof technique is proof by contradiction. This method is based on the tautology ( ( p  q )  ( ~ q ) )  ( ~ p ). Thus the rule of inference
p  q
~ q .
~ p is valid. Informally, this states that if a

statement p implies a false statement q, then p must be false. This is often applied to the case where q is an absurdity or contradiction, that is, a statement is always false. An example is given by taking q as the contradiction r  ( ~ r ). Thus any statement that implies a contradiction must be false. In order to use the proof by contradiction, suppose we wish to show that a statement q logically follows from statements p1, p2, . . ., pn. Assume that ~q is true ( that is, q is false ) as an extra hypothesis p1  p2  . . . pn  ( ~ q ) implies a contradiction, then at least one of the statements p1, p2, . . ., pn, ~ q must be false. This means that if all the pi’s are true, then ~ q must be true. Thus q follows from p1, p2, . . ., pn. This is proof by contradiction.

Ex. 7 : Prove there is no rational number p/q whose square is 2. In other words, show that the
 2 is rational.
Solution: This statement is good candidate for proof by contradiction., because we can check all possible rational numbers to demonstrate that none had a square equal to 2. Assume ( p/q )2 = 2 for some integers p and q, which have no common factors. Then p2 = 2q2 , so p2 is even. This implies that p is even, since the square of an odd number is odd. Thus, q2 is even, and so q is even. We now have that both p and q are even, and therefore have a common factor 2. This is a contradiction to the assumption. Thus the assumption must be false.

STEPS IN THE PROOF . . . . .
To prove a theorem of the form ( p1  p2  . . .  pn )  q, begin with the hypothesis p1, p2, . . . pn and show that some result r1 logically follows. Then using p1, p2, . . . pn, r1 , show that some other statements r2 logically follows. Continue this process, producing intermediate statements r1, r2, . . ., rk called steps in the proof, until we can finally that the conclusion q logically follows from p1, p2, . . . pn, r1, r2, . . . , rk. Each logical step must be justified by some valid proof technique.

Ex. 8 : Prove or disprove the statement that if x and y are real numbers , ( x2 = y2 )  ( x = y ). Solution : The statement can be restated in the form x y R ( x, y ). To prove the statement, we need to provide steps, each of which would be true for all x and y. To disprove the statement, we
need to find one example for which the implication is false.
Since ( – 3 )2 = 32, but – 3  3, the result is false. This example is called a counterexample, and any other counterexample
would do just as well.
Hence, if a statement claims that a property holds for all objects, then to prove it, we must use steps that are valid for all objects of that type. To disprove such statement, we need only to show one counterexample, that is, one particular object for which the claim fails.

State whether the argument given is valid or not. If it is valid, identify the tautology on which it is based.
( 1/62 ) If I drive to work, then I will arrive tired.
I am not tired when I arrive at work . . Valid. (( drive )  tired )  ~ tired )  ( ~ drive )
 I do not drive to work.

( 3/62 ) If I drive to work, then I will arrive tired.
I do not drive to work. . Invalid. ( ( d )  t )  ( ~ d )  ( ~ t ) ( ? )
 I will not arrive tired.

( 5/62 ) I will become famous or I will not become a writer.
I will become a writer. . Valid ( ( f V ~ w )  w )  f
 I will become famous.

( 7/63 ) If I try hard and I have talent, then I will become a musician.
If I become a musician, then I will be happy. .
 If I will not be happy, then I did not try hard or I do not have talent.
Valid : [ ( ht  m )  ( m  hp )]  [ ~ hp  ~ ht ]

( 13/63 ) Prove that the sum of two odd numbers is even.
Solution : Suppose m and n are odd numbers. Then there exist integers j and k such that
m = 2j + 1 and n = 2k + 1. m + n = 2j + 1 + 2k + 1 = 2j + 2k + 2 = 2 ( j + k + 1 ).
Since j + k + 1 is an integer, m + n is even.

( 15/63 ) Prove that the structure [ even integers, + , * ] is closed with respect to *.
Solution : Suppose m and n are odd numbers. Then there exist integers j and k such that
m = 2j + 1 and n = 2k + 1. m . n = 2j . 2k + 2j + 2k + 1 = 2 ( 2 jk + j + k ) + 1.
Since 2 jk + j + k is an integer, m . n is odd and the system is closed with respect to multiplication.

( 17/63 ) Prove that A = B if and only if A  B and B  A.
Solution : If A = B, then, clearly, A  B and B  A. If A  B and B  A, then A  B  A
and B must be the same as A.

( 19/63 ) Show that a) A  B is necessary and sufficient condition for A  B = B.
b) A  B is necessary and sufficient condition for A  B = A.

Solution : a) If A  B, then A  B  B. But B  A  B. Hence A  B = B. If A  B = B, then
since A  A  B, we have A  B.

b) If A  B, then A  A  B. But A  B  A. Hence A  B = A. If A  B = A, then
since A  B  B, we have A  B.

( 21/63 ) Prove or disprove : the sum of any 5 consecutive integers is divisible by 5.
Solution : Any 5 consecutive integers can be represented by n, n + 1, n + 2, n + 3, n + 4.
Their sum is 5 n + 10 or 5 ( n + 2 ). This is clearly divisible by 5.

( 23/63 ) Determine if the following is a valid argument. Explain your conclusion.
Prove : x x3 > x2
Proof : x x2 > 0 so x x2 ( x – 1 ) > 0 ( x – 1 ) and x x3 – x2 > 0. Hence x x3 > x2.
Solution : Invalid. Multiplying by x – 1 may or may not preserve the order of the inequality.

( 27/63 ) prove that the sum of two prime numbers, each larger than 2, is not a prime number.
Solution : Let x and y be the prime numbers, each larger than 2. Then x and y are odd and
their sum is even ( Exer. 13 ). The only even prime is 2, so x + y is not prime.


More . . .

and more !