-
[8 points]
Let A :=
{1,2}, B := {a,b,c},
C := {α,β},
and D := {$}.
Give concise list representations
of each of the following sets.
Be careful to use correct notation
(appropriate parentheses, braces).
- A × B
- A × A
- A × C × D
- A × D × D
- A × A × A
-
-
[2 points]
Which of these collections of sets are partitions of
{1,2,3,4,5,6}?
- { {1,2}, {2,3,4}, {4,5,6} }
- { {1}, {2,3,6}, {4}, {5} }
- { {2,4,6}, {1,3,5} }
- { {1,4,5}, {2,6} }
Explain when a collection is not a partition.
-
[2 points]
Which of these collections of sets are partitions of
{-3,-2,-1,0,1,2,3}?
- { {-3,-1,1,3}, {-2,0,2} }
- { {-3,-2,-1,0}, {0,1,2,3} }
- { {-3,3}, {-2,2}, {-1,1}, {0} }
- { {-3,-2,2,3}, {-1,1} }
Explain when a collection is not a partition.
-
Here are some axioms and identities which you can use:
∀S1∀S2[S1 ⊆ S2 ↔ ∀x(x ∈ S1 → x ∈ S2)]
∀S1∀S2[S1 = S2 ↔ ∀x(x ∈ S1 ↔ x ∈ S2)]
∀S1∀S2[S1 = S2 ↔ (S1 ⊆ S2 ∧ S2 ⊆ S1)]
∀S1∀S2∀x[x ∈ S1 ∪ S2 ↔ (x ∈ S1 ∨ x ∈ S2)]
∀S1∀S2∀x[x ∈ S1 ∩ S2 ↔ (x ∈ S1 ∧ x ∈ S2)]
∀S1∀S2∀x[x ∈ S1 - S2 ↔ (x ∈ S1 ∧ x ∉ S2)]
∀S∀x[x ∈ ~S ↔ x ∉ S]
∀S1∀S2[~(S1 ∩ S2) = ~S1 ∪ ~S2]
∀S1∀S2[S1 - S2 = S1 ∩ ~S2]
∀S1∀S2∀S3[S1 ∩ (S2 ∪ S3) = (S1 ∩ S2) ∪ (S1 ∩ S3)]
Using
ProofBuilder,
produce proofs of the formulas below.
Use the axioms and identities above —
and further,
in your proofs of the numbered formulas below,
you are allowed to use
lower-numbered
formulas.
Thus,
the proof of Example 14 of page 126
used 'earlier' formulas, not just axioms.
Rem. you can copy material from here
and lecture notes and paste such
into ProofBuilder.
- [3 points]
∀S[S ∪ S = S]
- [2 points]
∀S[∅ ⊆ S]
See
the manual
for ProofBuilder —
not to mention
our textbook's Theorem 1 on page 115.
- [7 points]
A ⊆ B ∧ B ⊆ C → A ⊆ C
(2.1.15)
-
-
[1 homework point]
Express 3-4
as a fraction a/b,
with a and b being integers (literals).
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of (-3)4 ?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of 110 ?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of 10000 ?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of lg(512)?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of lg(1/128)?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of lg(2)?
Try to do this exercise without using a calculator.
-
[1 homework point]
What is the value
of lg(21000)?
Try to do this exercise without using a calculator.
Rem. "lg(z)" means "log2(z)".
-
[5 homework points]
Give the complete, thorough prime factorizations of
each of the following numbers:
1980,
2009, 2010, 2011, and 2012.
Your final answers for this exercise should appear like the following:
-
2000 := 24 * 53
-
2001 := 3 * 23 * 29
-
2002 := 2 * 7 * 11 * 13
-
2003 is prime considering that it's not evenly divisible
by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, nor 43,
and the squares of further primes (47 etc.)
are larger than 2003.
-
2004 := 22 * 3 * 167
167 is prime considering that it's not evenly divisible
by 2, 3, 5, 7, or 11
and the squares of further primes (13 etc.)
are larger than 167.
You can do the factoring however you want;
you do not need to use the algorithm(s) for factorization
specified in our textbook.
Rem. the primes less than 100 are listed
near the bottom of page 210 of our textbook.
Try to do this exercise without using a calculator.
Show intermediate steps/explanations for obtaining answers.
-
[3 homework points]
Show that
for every value of n,
5n + 4*5n =?= 5(n+1)
is true,
regardless of what n's value may be.
Incidentally, note that substituting a few values for n
such as 2
and/or 3
and/or 5
would
show only that the equation is true for the specific values that you test;
it
wouldn't
show that the equation is true for other values of n
which you haven't tested.
What you need to do here is
apply algebra to the left-hand side of that
equation, "5n + 4*5n";
collect terms, etc....
Show intermediate steps/explanations for obtaining answers.
-
[4 homework points]
Using algebra, show that the following is true, regardless
of what value may be used for
a:
(a-1)*2(a+1) + 2 + [a+1]*2[a+1] =?= ([a+1]-1)*2([a+1]+1) + 2
Incidentally, note that substituting a few values for a
such as 2
and/or 3
and/or 5
would
show only that the equation is true for the specific values that you test;
it
wouldn't
show that the equation is true for other values of a
which you haven't tested.
What you need to do here is
apply algebra to the terms in that
equation:
maybe multiply things out,
collect terms, etc....
Show intermediate steps/explanations for obtaining answers.
-
[8 homework points]
-
Express 0.0375
as a fraction a/b in lowest terms,
with a and b being integers (literals).
Suggestion:
One way to do this is to
use your knowledge of what decimal
floating-point
representation means.
For example, "0.6" means "6/10",
which reduces to lowest terms 3/5.
Try to do this without using a calculator.
-
Give the complete prime factorizations
of 30 and 6561,
and also
of
the values a and b
that you determine in Part (i) (above).
Try to do this without using a calculator.
-
Express
lg(30),
lg(6561),
and
lg(0.0375)
as simplified sums/differences of integers and multiples
of lg(3)
and lg(5).
(Rem. "lg(z)" means "log2(z)".)
For examples:
• lg(250) == lg(2*5³) == lg(2) + lg(5³) == 1 + 3*lg(5)
• lg(0.6) == lg(3/5) == lg(3) - lg(5)
Try to do this without using a calculator.
Show intermediate steps/explanations for obtaining answers.
Acknowledgement:
Some of these exercises are derived from Richard Johnsonbaugh.
-
[2 homework points]
Give the prime factorization of 11! (note the "!").
Try to do this without using a calculator.
Suggestion (to facilitate doing the work without using a calculator):
don't calculate the value of 11! —
don't do any multiplication at all;
write out 11!
as 11*10*9*···*3*2*1
and then work on obtaining prime factors from there....
Show intermediate steps/explanations for obtaining answers.
-
[3 homework points]
Use algebra, including properties of factorial ("x!"),
to reduce the following expression to an equivalent one that is as
simple as possible:
n!
------*(n+1)*(k+1)
(k+1)!
Show intermediate steps/explanations for obtaining answers.
- [3 homework points]
-
Exhibit a pair of decimal floating-point numbers x and y
for which
|¯x + y¯|
≠ |¯x¯| + |¯y¯|.
Show all the intermediate values:
x + y,
|¯x + y¯|,
|¯x¯|,
|¯y¯|,
and
|¯x¯| + |¯y¯|.
-
Exhibit a pair of decimal floating-point numbers x and y
for which
|_x + y_| ≠ |_x_| + |¯y¯|.
Show all the intermediate values:
x + y,
|_x + y_|,
|_x_|,
|¯y¯|,
and
|_x_| + |¯y¯|.
- [4 homework points]
Calculate the value of the expression
|¯L/2¯| + |¯L/2¯| - 1
for
each of the following values
for L: 0, 1, 2, 3, 4, 5.
In your intermediate work here,
include showing the decimal values of L/2.
Try to do this without using a calculator.
You should see that
it appears that in each case,
no matter what the value of L is,
|¯L/2¯| + |¯L/2¯| - 1 ≤ L.
Write an English explanation of why this appears to always be true
for every nonnegative integer value for L.
This
condition "|¯L/2¯| + |¯L/2¯| - 1 ≤ L"
arises in connection with B+-trees,
which are data structures
with good properties of efficient access —
databases use them.
-
[5 homework points]
For each of following values of n and d,
find the integer quotient q := |_n/d_|
and the integer remainder r := n - d*q i.e. r := n mod d:
- n := 53, d := 6
- n := -53, d := 6
- n := 3, d := 6
- n := 0, d := 6
- n := 6, d := 6
- n := 53, d := 53
Try to do this without using a calculator.
- [4 homework points]
The months with Friday the 13th in year y are found in row #f13(y) in
the table below, where f13(y) is calculated from y as follows:
f13(y) := ( y + |_(y-1)/4_| - |_(y-1)/100_| +
|_(y-1)/400_| ) mod 7
Here's the table:
f13(y) if y is not a leap year if y is a leap year
------ ----------------------- -------------------
0 January, October January, April, July
1 April, July September, December
2 September, December June
3 June March, November
4 February, March, November February, August
5 August May
6 May October
For example for next year, 2010:
f13(2010)
:= ( 2010 + |_(2010-1)/4_| - |_(2010-1)/100_| + |_(2010-1)/400_| ) mod 7
:= ( 2010 + 502 - 20 + 5 ) mod 7
:= 2497 mod 7
:= 5,
and 2010 is not a leap year;
so looking at the appropriate entry in the table above,
in the year 2010
(only)
the month of August will have a
Friday the 13th.
Determine the months with Friday the 13th
in 2001,
in 2004,
in the year before our current one,
and
in our current year right now.
Try to do this without using a calculator.
Show intermediate steps/explanations for obtaining answers.
-
- [4 homework points]
Perform the following integer divisions a/d,
obtaining in each case an integer quotient q
and a remainder r:
6!/4!, 5!/2!, 3!/1!, 7!/6!, 4!/0!, 8!/5!, 9!/7! .
Try to do this without using a calculator.
Suggestion (to facilitate doing the work without using a calculator):
write out each of these expressions n!/k!
as follows:
n*(n-1)*(n-2)*···*3*2*1
k*(k-1)*(k-2)*···*3*2*1
and then cancel common factors (that appear in both the numerator
and the denominator) —
before really multiplying any numbers together
and finally dividing.
Definitely report the remainders,
even if they seem trivial
(in the past some students neglected to report them).
- [2 homework points]
You should see that
it appears that in each case,
no matter what the values
of n
and k are,
as long as 0 ≤ k ≤ n,
then
k! evenly
divides n! .
Write an explanation of why it should always be true
that
k! evenly
divides n!
for any values
of n
and k —
as long as 0 ≤ k ≤ n.