USA: +1(669)289-8683 
Sign in
1
Week 3: Section 1.4 Predicates and Quantifiers
Assume that the universe of discourse is all the people who are participating in
this course. Also, let us assume that we know each person in the course. Consider the
following statement: “She/he is over 6 feet tall”. This statement is not a proposition
since we cannot say that it either true or false until we replace the variable (she/he) by a
person’s name. The statement “She/he is over 6 feet tall” may be denoted by the symbol
P(n) where n stands for the variable and P, the predicate, “is over six feet tall”. The
symbol P (or lower case p) is used because once the variable is replaced (by a person’s
name in this case) the above statement becomes a proposition.
For example, if we know that Jim is over 6 feet tall, the statement “Jim is over six
feet tall” is a (true) proposition. The truth set of a predicate is all values in the domain
that make it a true statement. Another example, consider the statement, “for all real
numbers x, x2 –5x + 6 = (x – 2) (x – 3)”. We could let Q(x) stand for x2 –5x + 6 = (x – 2)
(x – 3). Also, we note that the truth values of Q(x) are indeed all real numbers.
Quantifiers:
There are two quantifiers used in mathematics: “for all” and “there exists”. The
symbol used “for all” is an upside down A, namely, . The symbol used for “there
exists” is a backwards E, namely, . We realize that the standard, every day usage of the
English language does not necessarily coincide with the Mathematical usage of English,
so we have to clarify what we mean by the two quantifiers.
For all For every For each For any
There exists at least one There exists There is Some
The table indicates that the mathematical meaning of the universal quantifier, for
all, coincides with our everyday usage of this term. However, the mathematical meaning
of the existential quantifier does not. When we use the word “some” in everyday
language we ordinarily mean two or more; yet, in mathematics the word “some” means at
least one, which is true when there is exactly one.
The Negation of the “For all “Quantifier:
Consider the statement “All people in this course are over 6 feet tall.” Assume it
is false (I am not over six feet tall). How do we prove it is false? All we have to do is to
point to one person to prove the statement is false. That is, all we need to do is give one
counterexample. We need only show that there exists at least one person in this class
who is not over 6 feet tall. Here is a more formal procedure.
Example 1:
Let P(n)stand for “people in this course are over 6 feet tall”, then the sentence
“All people in this course are over 6 feet tall” can be written as: “ n P(n)”. The negative,
“ ( n P(n))”, is equivalent to: “ n( P(n))”. So, in English the negative is, “There is
(there is at least one/ there exists/ some) a person in this room who is not over 6 feet tall.”
2
Example 2:
How would one negate the sentence: “Every person in this course is over six feet
tall and is taking the course C Programming”.
Answer:
Let P(n) stand for “people in this course are over 6 feet tall” and let Q(n) stand for
“person n is taking the course C Programming”. Then, the given sentence in symbolic
form is n( P(n) Q(n)).
Next, ( n( P(n) Q(n))) n( (P(n) Q(n))) Why?
n( P(n) Q(n)) [Note: the use of DeMorgan’s law]
In English we have:
There is a person in this course who is not over six feet tall or who is not taking
the course C Programming OR Some people in this course are not over six feet tall or are
not taking the course C Programming.
The Negation of the “There exists” Quantifier:
Example 3:
How would you prove that the statement “ There is a person in this course over 7
feet tall.” is false?
Answer:
Surely, one would have to demonstrate that no one in the room is over seven feet
tall. In other words in logical symbols we have:
( (nP(n))) is equivalent to n( P(n)) .
Can you write the negatives of the following expressions using logic?
1. All people in this course are interesting and informative.
2. Some people in this course are having fun. (Note, the word “some” in
mathematics means there is at least one, or there exists.)
3. All people in this course are over 6 feet tall or wear glasses.
4. For all real numbers x, the equation x2 + 6x + 5 = 0 is true.
Some thoughts on using multiple quantifiers
In week 1 we reviewed some of the basic laws we saw in high school algebra. For
example, we saw that for all real numbers a and b, a + b = b + a (the commutative law
for addition). Of course, what this means is that for every real number a and for every
real number b, we have a + b = b + a. If it is understood that a and b are real numbers, we
could use quantifier notation and say a and b, a + b = b + a. So, using the “for all”
quantifier multiple times is a easy process. The following two examples illustrate that
“mixing” quantifiers makes life more difficult.
3
Example 4.
In the following assume a and b are real numbers:
“ a, b where a + b = 1”.
In English this says: “For all real numbers a there exists a real number b such that
a + b = 1.” This statement is true since, for example, if a = 5 there does exist a real
number b, which makes a + b = 1 true. Just take b = -4 the 5 + (-4) = 1. Of course this
can be done for any real number a, just take b = -(a -1). and a + b = 1 becomes
a + (-(a – 1)) = 1, which is of course true.
Example 5.
In the following assume a and b real numbers.
“ b, a where a + b = 1”.
In English this says “There exists a real number b, such that, for all real numbers
a we have a + b = 1”. This statement is false since, for example, if b = 4 then a + b = 1
becomes a + 4 = 1. Is this true for every single real number a? The equation a + 4 = 1 is
not true for all real numbers a it is true only for the real number a = -3
Methods of Proving Theorems
Why??
Almost nothing in undergraduate, and some graduate, mathematics courses
creates FEAR more than when an instructor announces that the students will be required
to do proofs. Yet, we all prove statements frequently. To illustrate, we may be required to
explain some fact to a child, a high school student, or a colleague. Our explanation is
going to vary depending on what that person knows. When you have successfully
explained the fact you have “proven it”. All a proof is, is a logical, detailed explanation
of why a statement is true. Our explanation will vary depending on to whom we are
speaking. Just like there can be multiple correct directions for going from one location to
another, there are often different proofs for the same mathematical statement.
In any course we take, we are always trying to improve our problem-solving
abilities. In order to solve a problem, we must first make sure we have a clear idea of
what the problem is, what the assumptions are (ie. the “givens”), and what we are trying
to accomplish. This is precisely what we do in mathematical proofs. Spending some time
thinking about proof techniques will enhance our problem solving abilities.
Another purpose of these notes is to help us to be able to read proofs contained in
a textbook that we might be studying. Since a proof is a logical, detailed explanation of a
statement, it helps to clear up any ambiguity we may have on the concept. It gets right to
“the basics”, the core definitions, of what we are studying. If we can read and understand
a proof, we have mastered the key ideas of that concept. The ACM/IEEE
recommendation on Discrete Structures recommends 12 lecture hours on proofs. In the
material that follows I try to make the topic easy to follow.
4
Methods of Proving If … then … types of Theorems
All theorems in mathematics, or any application of mathematics, can be expressed
as a “If … then …” statement(s). Therefore, the text and the notes below discuss
methods of proving “If … then …” statements.
Example 6:
The distributive law for numbers should really read as follows:
If a, b and c are any three real numbers then, a(b + c) = ab + ac.
Example 7:
The commutative law for sets ( under the operation of ) should be stated as:
If A and B are any two sets then A B = B A. [Note: This example will make more
sense after you have studied sets].
Example 8:
The basic matrix algebra law A(BC) = (AB)C should really read as follows:
If A, B and C are matrices whose entries are real numbers of orders m x n, n x p and p x l
respectively then, A(BC) = (AB)C. [Note: This example will make more sense after you
have studied matrices].
You should be able to take each of the logic and set laws given in the notes and write
them in “If … then …” format.
Warning, before you proceed here are a few definitions that we need to know because
they will be used in virtually all of our examples. It is important that you learn the
definitions as given, not some alternate form of the definitions. They will be repeated
again as we need them.
Even integer: An even integer is any integer that can be expressed in the form
2n for some integer n.
Odd integer: An odd integer is any integer that can be expressed in the form
2n + 1 for some integer n.
Divides: Let x and y be integers with x 0. We say that x divides y
(notation x | y) if there exists an integer k such that y = kx.
Some examples:
1) Is 6 an even integer?
Yes, 6 is an even integer since 6 = 2 times 3.
2) Is -8 an even integer?
Sure, since -8 = 2 times (some integer, namely, -4).
5
3) Is 0 an even integer?
Yes, because 0 = 2 (some integer, which is???).
4) Comments on the definition of Divides . Note: in elementary school, if we were
asked whether 3 divides evenly into 15, we would think of
15
3
= what number?
Since
15
3
= 5, we would say yes, 3 divides 15. This gives us the above definition of
Divides: 3 divides 15 because 15 = 3 x (the integer, 5). When you see
x | y, think of
y
x
. That is, x divides evenly into y iff
y
x
= k for some integer k.
The Direct Method of proof of P C Statements.
As we know from our discussions in logic “If P then C” statements or “P implies
C” statements are frequently written in logical notation as P C.
Recall that P stands for the premise (or hypothesis) of the statement and C stands
for the conclusion. The Direct Method of proof of P C statements is based on the
definition of P C. Look at the two cases where P is true in the definition. If P is true
then the complete statement P C is true when C is true. So to prove a statement of
the type P C true assume P is true and prove C is true. To do this start with P
being true and end with C being true. This is called the direct method of proof of a
P C statement. So, to use the direct method we start with the assumption P is true and
we show that it (naturally) follows that C is true using axioms, definitions, previously
established results, and rules of inference.
Example 8.
Prove the following: If x is any even integer and if y is any even integer then xy
is an even integer.
First, I will comment on some key ideas in proof techniques and then proceed with the
proof.
Comments:
Most proofs depend on basic definitions and concepts. Do not proceed any
further until you truly understand these essential ideas. A major reason for
wanting to prove something is because it will force us to learn these key
concepts. (Certainly, people probably smarter than us did the proof of this
statement many years ago.) In this example, the key definition is that of an even
integer. What is the definition of an even integer? I am not asking what we think
the definition may be but, what is the definition. We may have to look it up. Here
is a form of the definition of even integer: An even integer is any integer that
can be expressed in the form 2n for some integer n.
6
Next do you truly understand the definition? Can you give some examples and
explain them? For example, 6 is an even integer. Why? Is 0 an even integer?
Why? (Answer: yes, because 0 = 2(0), that is, 0 can be written as 2 times an
integer.)
What method of proof will you try? Usually try the direct method first.
What is the process for this method? What is the assumption, the premise? What
are you trying to prove? Write the assumption(s) and the conclusion(s) out. This
will focus you attention on what you are trying to do.
Give reasons for each step in your proof. If you cannot give a reason for a
particular step it is most likely wrong.
Relax, with practice you will get most proofs most of the time.
Now I will repeat the statement and prove it. Before you look at my proof try one of
your own.
Example 8 (the proof):
If x is any even integer and if y is any even integer, then xy is an even integer.
Answer:
Proof: (Direct)
Assume x and y are even integers is true (this is the premise, P). Start with this.
Next, write down specifically what you want to do. To prove: xy is an even integer is
true. You want to prove that xy is an even integer, so you must show that xy can be
expressed as 2 times some integer. End with this.
Start with P being true
x and y are even integers implies that x = 2n and y = 2m for some integers n and m.
Why?
this implies that xy = (2n)(2m) Why?
this implies that xy = 2(2nm) Why?
this implies that xy is an even integer. Why? End with C is true
DONE.
Some people like to use logical notation so they would write the above as:
x and y are even integers x = 2n and y = 2m for some integers n and m. Why?
xy = (2n)(2m) Why?
xy = 2(2nm) Why?
xy is an even integer. Why?
DONE.
Example 9.
Prove the following: Let a, b, and c be integers. Then if a | b and a | c, then
a |(b + c).
Comments.
7
The sentence “Let a, b, and c be integers” is just another way of saying let a, b,
and c be any integers or for all integers a, b, and c. The statement we are trying to
prove is “if a | b and a | c, then a |(b + c)”. What is the premise? What is the
conclusion?
Before we begin, we need to understand what x | y means. Assume x and y are
integers where x 0. Read x | y as x “divides” y, which means x divides evenly
into y, no remainder. So, 2 | 8 and 3 | 36 but 2 does not divide 5. Therefore, x | y
means
y
x
= some integer, say k, that is y = kx. A formal definition follows.
Definition: Let x and y be integers with x 0. We say that x divides y if there
exists an integer k such that y = kx.
Example 10:
Let a, b, and c be any integers (a not equal to 0). If a | b, then a | bc. (This is
exercise 6 below).
First, I will outline the direct proof of this statement and then I’ll repeat the
outline and do the proof.
Proof: (Direct):
Assume: P is true, namely, a | b. Start here.
To prove: C is true, namely, a | bc End here
Outline:
Start a | b
bc = a (some integer). How did I know to write this? See below in green.
a | bc END
Since this is the last step, then what is the most likely second last step? By
definition of divides it is bc = a (some integer). I’ll put this in the above and see if it
helps me to get where I’m going.
Now I’ll do the proof, that is, fill in the blanks in the above
Start a|b b = ak for some integer k. This is the definition of “divides”.
How can I go from here to the statement in red below? Simple just
multiple both sides by c. to get
bc = (ak)c. OR bc = a(kc). Note: I’ve rearranged the terms a bit and used
parentheses, ( ). Is it clear I have the form below so I’m done.
bc = a (some integer).
a|bc END
Example 10:
Let a, b, and c be integers. Then if a | b and a | c, then a |(b + c).
Try it yourself first like the outline above. What is the first step, the last, the second last?
Proof: (Direct)
Assume a | b and a | c is true.
8
To prove a |(b + c) (is true). That is, we want to prove that (b + c) = a (some integer).
a | b and a | c b = ak for some integer k and
c = al for some integer l. This is the definition of divides.
b + c = ak + al Simply add both sides of the above equations.
b + c = a(k + l) The distributive law.
b + c = a(some integer) The sum of 2 integers is an integer.
a |(b + c) This is the definition of divides.
So in summary the direct method of proof of P C Statements can be outlined the
following way. All you have to do is know basic definitions and fill in the blanks as
illustrated below.
Proof: (Direct)
Assume: P is true. Start here.
To prove: C is true End here
Outline:
Start P is true means
Once you know the last step, C is true, you frequently can write the
2nd last step and maybe even the 3rd last step
C is true END
Exercises:
Prove the following using the direct method of proof:
1. If x is any even integer and if y is any even integer then x + y is an even integer.
2. If x is any odd integer and if y is any odd integer then xy is an odd integer.
3. If n is an even integer then n2 is an even integer.
4. If n is an odd integer then n2 is an odd integer.
5. If n is an even positive integer then 7n + 4 is an even integer.
6. Let a, b, and c be any integers. If a | b, then a | bc.
7. Let a, b, and c be any integers. If a | b and b | c, then a | c.
8. Let a, b, and c be any integers . If ac | bc, then a | b.
9. If a is an odd integer then 8|(a2 – 1)
9
The “Proof by Contradiction” method of proof of P C Statements.
An If … then … (that is an P C) statement is either true or false. If a P C
statement is not false then it must be true. So if we assume that a P C statement is false
and find that this cannot happen (get a contradiction) then the given P C statement
must be true. In the following identity I will use the conventional P C in place of
P C.
The proof by contradiction method of proof is based on the identity:
( )P C P C . How? To use the “proof by contradiction” method of a proof on a
P C statement, we assume P is true, C is false, and prove that this gives a contradiction.
Note: The usual place to start using this method is generally the false part of the
“assumption” that C is false. Why?
Example 11:
Let n be an integer. Use the proof by contradiction method of proof to prove the
following: “If n3 + 5 is an odd integer then n is an even integer”.
Answer:
So to prove a statement of the form P C using the proof by contradiction method the
process is:
Assume (1) P is true and assume (2) C is false (note this is 2 different assumptions) and
then show that this gives a contradiction. The usual contradiction is to the assumption
that P is true
So the outline of any proof by contradiction usually is:
START with C is false
.
.
.
this contradicts the assumption that P is true
END
Now I will outline the proof of this example. To do so I must understand what C
is (n is a even integer) and what P is (n3 + 5 is an odd integer).
Proof: (by contradiction)
Assume n is even is false and also assume n3 + 5 is odd is true and show that this
gives a contradiction (the contradiction will most likely be to the assumption that n3 + 5
is odd is true)
10
Outline:
Start n is even is false
n3 + 5 = 2(some integer) (c)
n3 + 5 is an even integer (b)
this contradicts the assumption that n3 + 5 is odd is true (a)
END
NOTE I wrote the “start line” first then I knew what I wanted to prove,
namely, line (a) so I wrote this at the bottom. For line (a) to be contradicted n3 + 5
had to be even so line (b) had to occur so I wrote this down and for line (b) to
happen line(c) had to happen.
Now I’ll do the proof using the above outline
Start n is even is false
n is an odd integer
n = 2x + 1 for some integer x (definition of odd integer)
n3 + 5 = (2x + 1)3 + 5 (this is a key step. Line (b) tells me I want to talk
about n3 + 5 so I wrote what n3 + 5 is)
n3 + 5 = 8×3 + 12×2 + 6x + 1 + 5
n3 + 5 = 2(4×3 + 6×2 + 3x + 3)
Note: I did this to get the above expression in the form of the next line (line (c)).
n3 + 5 = 2(some integer) (c)
n3 + 5 is an even integer (b)
this contradicts the assumption that n3 + 5 is odd is true (a)
END
Now try to put reasons next to each step. The reason for step b is simply the definition
of even integer. The reason for another step might be simply basic algebra.
Example 12:
Assume that n is an integer. Use the “proof by contradiction” method of proof to
prove: “If 3n + 4 is even then n is even”.
11
Outline
Proof: (by contradiction)
Assume n is even is false and also assume 3n + 4 is even is true and show that this gives
a contradiction (the contradiction will most likely be to the assumption that 3n + 4 is even
is true)
Outline
Start n is even is false
3n + 4 = 2(some integer) + 1 (c)
3n + 4 is an odd integer (b)
this contradicts the assumption that 3n + 4 is even is true (a)
END
NOTE I wrote the “start line” first then I knew what I wanted to prove,
namely, line (a) so I wrote this at the bottom. For line (a) to be contradicted 3n + 4
had to be odd so line (b) had to occur so I wrote this down and for line (b) to
happen line(c) had to happen.
Can you fill in the steps to the above?
More exercises:
Use the proof by contradiction method of proof to prove the following:
1. If n2 is an even integer then n is an even integer.
2. If n2 is an odd integer then n is an odd integer.
3. If n is an integer and 3n + 2 is even then n is even.
4. If n is any integer and n3 + 7 is odd then n is even.
5. If n2 is not divisible by 3, then n is not divisible by 3.
6. If xy is an odd integer then (both) x and y are odd integers. Some hints for this
one. When you assume that x and y are odd integers is false this means (by
DeMorgan’s law) that x is not odd or y is not odd, that is, x is even or y is even.
So use three situations/cases.
Case 1. x even, y odd, Case 2. x odd, y even and Case 3. x even and y even.
In each case there is a contradiction to xy is odd.
7. If n is any integer then n2 – 4 is not divisible by 4.
12
How to prove iff Theorems.
From the material in logic we know that “iff” means “if and only if” and the
logical symbol, or is often used in place of iff. From the chart Common
Implications and Equivalences (notes week 2, table 4), we know that
( ) ( ) ( )p q p q q p is a tautology, a statement, that is always true. In other
words:
p iff q is equivalent to saying if p then q and if q then p or
p iff q is equivalent to saying if p then q and conversely.
That is, to prove an iff theorem one must prove two if … then … theorems.
In exercise 3 page 8 you proved: If n is an even integer then n2 is an even integer
and for exercise 1 page 11 you proved the converse of this statement namely, “ If n2 is an
even integer then n is an even integer”. The two statements combined could be expressed
as: “n is an even integer iff n2 is an even integer”.
Example 13.
Prove: n is an even integer iff n2 is an even integer.
Proof:
I will outline the proof. To do this I will state each part of the proof and skip
enough space to do each part, so I will not forget each part.
I must prove two statements:
1. If n is an even integer then n2 is an even integer (You proved this in exercise 3 page 8
using the direct method of proof) AND
2. If n2 is an even integer then n is an even integer (You proved this part in exercise 1
page 11 using the proof by contradiction method of proof).
Note: sometimes both parts of an iff statement can be proved using the same method of
proof and sometimes different methods must be used.
Example 14.
Let a and b be any two real numbers. Prove the following:
ab = 0 iff a = 0 or b = 0.
Proof:
We must prove the following two statements:
(a) If ab = 0 then a = 0 or b = 0
and
(b) If a = 0 or b = 0 then ab = 0.
To prove part (a) we use the direct method of proof.
13
Assume that ab = 0 and prove that a = 0 or b = 0. To prove a = 0 or b = 0 we
need only show that one of the two parts of this or statement is true. Why? To do this
assume that a 0 show that when this happens b must be equal to 0. Why does this
work? Since a 0 then 1/a exists. Why? Now multiply both sides of ab = 0 by 1/a to
obtain b = 0. This proves part (a).
To prove part (b) we use the direct method of proof.
Assume a = 0 or b = 0 To prove ab =0. Here we have to show that whether we
assume that a = 0 or we assume that b = 0 the conclusion, ab =0 follows. So we have two
cases/situations.
Case I.
Assume that a = 0 and prove that ab = 0. This follows from the definition of the
multiplication of a number by 0 that we all learned in elementary algebra.
Case II.
Assume that b = 0 and prove that ab = 0. Again, this follows from the definition
of the multiplication of a number by 0.
Here are some additional exercises.
1. n is an odd integer iff n2 is an odd integer.
2. Let n be a positive integer. Prove: n is an odd integer iff n3 + 6 is an odd
integer.
3. Let n be a positive integer. Prove: n is odd iff 5n + 6 is odd.
4. Prove the following: The equation ax2 + bx + c = 0 has a unique solution if and
only if the discriminant b2 – 4ac = 0. Hint. First express the iff statement as two if …
then… statements and then prove each using the direct method of proof. For each if
… then … statement carefully write down your assumption and what you are trying to
prove.
5. x is an odd integer iff x2 + 2x + 1 is even
Proof by contraposition
Another valid method of proof is that where one proves the contrapositive. We
know that the statement (P C) ( C P) is a tautology. So for this method,
instead of proving P C true, we prove C P true. Use the direct method of proof
to do this. That is, assume C true and then prove that P is true.
How do we prove a statement is false?
Finally how does one show/prove that a statement is false? Consider the following
sentence: “Every person taking this course is over six feet tall”. To prove this statement is
incorrect we need only show that there is at least one person taking the course who is not
over six feet tall. This is called giving a counterexample (to the given statement). Look
up this term in the index of the text for more examples.
14
Warning: (Counter) examples are used to prove theorems/statements false but examples
cannot be used to prove theorems true.
Some “do’s” and “don’ts” for proofs:
1. Always try the direct method of proof first. It usually works.
2. Always outline carefully what your assumptions are and what you are trying to
prove. This will focus your attention on what you are given and where you are
going.
3. Clearly specify the method of proof you are using, again this will focus your
attention on the correct process.
4. Keep in mind that a proof is only a detailed explanation. If you don’t understand
what you have written then it is most likely wrong.
5. Above all else, RELAX; the worst that can happen is that you cannot complete
the proof. That’s OK, hopefully by writing down part of the proof you have
focused you attention on the basic definitions and or concepts that you are
studying.
6. If you are stuck partly through a proof, again that’s OK; in fact, it is good to
realize that you are stuck. Try another approach.
In section 1.8 of the text skip to the material titled Methods of Proving
Theorems. Read this material carefully. Concentrate on the examples and the two
principle methods of proving If … then … theorems. These methods are: the direct
method and the proof by contradiction method. After you have studied the material in
the text continue to read the following. Since any if … then …statement is equivalent to
its contrapositive another approach would be to write the contrapositive of the given
statement and to prove it using one of the above two methods.
Warning: the literature is a little confusing concerning the names of the above two
methods. In some texts the proof by contradiction method is called the indirect
method. I will stick to the terms used in our text.
5. Prove the following: If n is an odd integer then n2 is an odd integer. (This is #4, pg. 8, week 3 of the notes.)
6. Assume that n is a positive integer. Use the proof by contradiction method to prove and explain:
If 3n + 2 is an even integer then n is an even integer. (This is #3, pg. 11, week 3 of the notes.)
7. Let A = {1,2,3,5} and B = {2,6}, with the universal set U = {1,2,3,4,5,6,7,8,9}.
Compute
(a) A – B
(b) A2 (this is the cross product)
(c) A B ⊕
(d) A (B – A) ∩
(e) A
8. (10 pts.) A bit string is a string of bits (0’s and 1’s). The length of a bit string is the number of bits in the string. An example, of a bit string of length four is 0010. An example, of a bit string of length five is 11010. Use the Rule of Products to determine the following:
(a) How many bit strings are there of length eight? Explain
(b) How many bit strings are there of length eight which begin with a 1 and end with a 0? Explain
(c) How many bit strings are there of length eight with even parity (an even number of 1’s)? Explain
For your information question 8 part a could have been stated the following way. Computers use bit strings of length 8, called bytes, to represent the characters (letters both upper case and lower case, punctuation symbols, [, {, the integers 0 through 9 etc) on a key board. The Extended ASCII code is one such coding system. Some examples of this code are: “a” is represented by 01100001, “A” is represented by 01000001 and “{“ is represented by 01111011 and the number 1 is represented by 00000001. How may such symbols can be described using a byte?
9. (10 points) “If a < .7 and b < .7 then a + b <1”
a. Write the converse of this statement. Is the converse true? Explain.
b. Write the contrapositive of this statement. Is the contrapositive true? Explain.
10. (10 points ) Express the following in English and then determine if each statement is true: Explain fully.
(a) ∃x∈Z (x2 = 4).
(b) ∀ y∈R (y 5) ≥
(c) ∀x∈R ∃y∈R x + y = 3.
11. How many bit strings of length n are palindromes? Hint: Consider two cases n is even and n is odd. Note a palindrome is a “string” of letters or numbers which read the same “frontwards” and backwards”. Examples: MOM, 1101011, 10111101 are palindromes.
