- PDF version (good for viewing in your browser)
- PostScript version (good for sending to your printer)
- LaTeX source (good for editing yourself)

- PDF version (good for viewing in your browser)
- PostScript version (good for sending to your printer)
- LaTeX source (good for editing yourself)

- Give an example of a binary relation that is both symmetric and antisymmetric.
- State the definition of
**total order**, or**linear order**. How many linear orders are there on an*n*-element set*A*? - Find an example of a set
*X*and binary relations*R*and*S*on*X*such that*R*and*S*are symmetric but*R*_{°}*S*is not symmetric. - The symmetric difference of two sets
*A*and*B*is the set*A*⊕*B*consisting of the elements of*A*or*B*which are not in both*A*and*B*. Define a relation ~ on sets so that*A*~*B*if and only if*A*⊕*B*is the empty set.- Is ~ reflexive?
- Is ~ symmetric, antisymmetric, both, or neither?
- Is ~ transitive?
- Is ~ an equivalence relation, a partial order, both, or neither?

- On the set
**Z**of integers, consider the relations ≡_{4}and ≡_{6}, respectively the relations for modular arithmetic modulo 4 and modulo 6. Thinking of these relations as sets, find:- ≡
_{4}∪ ≡_{6}. - ≡
_{4}∩ ≡_{6}.

- ≡
- Let
*R*be the binary relation on the set of people given by*R*(*a*,*b*) iff*a*is a parent of*b*. Then we know that*R*^{2}=*R*_{°}*R*is the relation "*a*is a grandparent of*b*". Similarly describe:*R*^{3}.- the transitive closure of
*R*.

- [
*Preorders.*] A**preorder**on a set*X*is a binary relation on*X*that is both reflexive and transitive. If « is a preorder on*X*, then define an equivalence relation ≡ on*X*by saying that*x*≡*y*if both*x*«*y*and*y*«*x*. Then define a relation ≤ on*X*/≡ by saying that [*x*] ≤ [*y*] if*x*«*y*.- Show that ≤ is really well-defined.
That is, if
*x*≡*x*′ and*y*≡*y*′, then*x*«*y*if and only if*x*′ «*y*′. Thus, whether [*x*] ≤ [*y*] or not won't depend on which representatives you choose for the equivalence classes. - Show that ≤ is a partial order on
*X*/≡.

- Show that ≤ is really well-defined.
That is, if
- Let
*X*be a set. Show that ⊆ is a partial order on the power set of*X*. What condition must*X*satisfy for ⊆ to be a total (or linear) order? - Consider the poset (partially ordered set)
described by the following Hasse diagram:
*A**B*|/|*C**D*|/|*E**F*- What are the maximal elements of the poset?
- What are the minimal elements of the poset?
- Which is true:
*A*≤*D*,*D*≤*A*, both, or neither?

- Consider the recurrence equation
*a*_{n+2}= 4*a*_{n+1}− 4*a*_{n}. Show that*a*_{n}= 2^{n}(1 +*n*) is a solution of this recurrence equation.

- PDF version (good for viewing in your browser)
- PostScript version (good for sending to your printer)
- LaTeX source (good for editing yourself)

- Suppose that you're picking out an outfit for the day. You can choose the green pants, the blue pants, or the black pants: 3 possible choices of pants. You can also choose the green shirt, the blue shirt, the white shirt, or the grey shirt: 4 possible choices of shirt. But you know that mixing a green item with a blue item will look bad. Does the product rule for counting directly apply to tell you how many different outfits you could wear? If not, how can you figure this number out anyway?
- Suppose that you know the sum rule for only 2 options.
Use induction to prove that the sum rule also holds
for any natural number
*k*≥ 2 of options. [Hint:*Break up*]*n*+*1*options into*n*options and 1 option. - [
*Binomial theorem.*] This question explains why the binomial coefficients are called that. Use induction to prove that

(The formula "*n*( *x*+*y*)^{n}=Σ C( *n*,*i*)*x*^{i}*y*^{n−i}.*i*=0*x*+*y*" is a**binomial**.) - Prove that if
*n*is a natural number, then C(2*n*,2) = 2C(*n*,2) +*n*^{2}:- using algebra and the formula for the binomial coefficient in terms of factorials.
- using a combinatorial argument applied to the meaning of the binomial coefficient in terms of sets.

- Let
*A*and*B*be sets of sizes*m*and*n*, respectively.- Give a formula for the number of functions from
*A*to*B*. Briefly explain why it's correct. - Give a formula for
the number of one-to-one functions from
*A*to*B*. Briefly explain why it's correct. - Give a formula for
the number of invertible functions from
*A*to*B*. Briefly explain why it's correct.

- Give a formula for the number of functions from
- Prove that if
*n*,*r*, and*k*are natural numbers, with*k*≤*r*≤*n*, then C(*n*,*r*) C(*r*,*k*) = C(*n*,*k*) C(*n*−*k*,*r*−*k*). - How many different strings can be made
by rearranging the letters in the word "MISSISSIPPI"?
[Hint:
*Don't solve this problem by listing them all!*] - A bookshelf contains 12 books in a row. How many ways can you choose 5 of these books subject to the condition that you never choose a pair of books that are right next to each other on the shelf?
- Generalise this to the case of
*n*books on the shelf and choosing*k*books. Given a value of*n*, what condition on*k*is necessary so that the answer doesn't just come out to zero?

- A hideous alien being with 3 feet is searching for socks in the dark. The monster has 27 black socks, 33 grey socks, and 12 navy blue socks. How many socks must it pull out of the drawer to be sure that it has 3 socks of the same colour?
- Consider a Cartesian plane (that is, with coordinates) and a pentagon in it whose vertices all have integer coordinates. Show that there is a pair of distinct vertices such that the midpoint of the line joining these two vertices also has integer coordinates.

- PDF version (good for viewing in your browser)
- PostScript version (good for sending to your printer)
- LaTeX source (good for editing yourself)

- Suppose that
*f*:*A*→*B*and*g*:*B*→*C*are functions, and consider their composition*g*_{°}*f*:*A*→*C*.- If
*f*and*g*are one-to-one, does it follow that*g*_{°}*f*is one-to-one? If not, give a counterexample. - If
*f*and*g*are onto, does it follow that*g*_{°}*f*is onto? If not, give a counterexample. - If
*f*and*g*are invertible, does it follow that*g*_{°}*f*is invertible? If not, give a counterexample. - Show that, if
*g*_{°}*f*is one-to-one, then*f*is one-to-one. Give an example where*g*_{°}*f*is one-to-one but*g*is not. - Show that, if
*g*_{°}*f*is onto, then*g*is onto. Give an example where*g*_{°}*f*is onto but*f*is not. - Show that, if
*g*_{°}*f*is invertible, then*f*is one-to-one and*g*is onto. Give an example where*g*_{°}*f*is invertible, but*f*is not onto and*g*is not one-to-one.

- If
- Let
*f*be a function from*A*to*B*. Suppose that if*f*^{−1}(*S*) =*f*^{−1}(*T*), then*S*=*T*, whenever*S*and*T*are subsets of*B*. Such a function is called an**epimorphism**. Show that epimorphisms and surjections are the same thing; that is, every epimorphism is a surjection, and evey surjection is an epimorphism. - Suppose that
*p*implies*q*. That is, if you know*p*, then you can deduce*q*. What is the**converse**of this implication? What is the**contrapositive**? Which of these can you assume to be correct? - [
*Disjunctive syllogism.*] Show that (*p*∨*q*) and ¬*p*together imply*q*. That is, if you know*p*∨*q*and you know ¬*p*, then you can deduce*q*. - [
*Resolution.*] Show that*p*∨*q*and ¬*p*∨*r*together imply*q*∨*r*. - [
*Modus tollens.*] Show that*p*→*q*and ¬*q*together imply ¬*p*. - [
*Hypothetical syllogism.*] Show that*p*→*q*and*q*→*r*together imply*p*→*r*. - Show that ∀
*x**P*(*x*) ∨ ∀*y**Q*(*y*) implies ∀*x*(*P*(*x*) ∨*Q*(*x*)). Is the converse also correct? - Prove that the square of an even number is even:
- using a direct proof.
- using an indirect proof.
- using a proof by contradiction.

- Prove that if
*n*is an integer not divisible by 3, then*n*^{2}− 1 is divisible by 3. Mention all properties of numbers and all rules of inference that you use in your proof. - [
*Telescoping sums.*] Prove by induction that

[Hint:*n*Σ ( *a*_{i}−*a*_{i−1}) =*a*_{n}−*a*_{0}.*i*=1*Use the recursive definition of summation (Σ).*] - Prove by induction that
the sum of the first
*n**odd*positive integers is*n*^{2}. [Hint:*Use summation and a formula for the*]*k*th odd positive integer. - Prove by induction
that the sum of the angles of a polygon with
*n*sides is (*n*− 2)180°, for*n*≥ 3 an integer. You may use the fact from geometry that the sum of the angles of a triangle is 180°. [Hint:*You can divide a polygon with*]*n*sides into a triangle and a polygon with*n*− 1 sides, if*n*− 1 ≥ 3. - If
*F*_{n}is the*n*th Fibonacci number, show that*F*_{n}^{2}− F_{n−1}F_{n+1}= (−1)^{n}. - Give a recursive definition
of the set of all polynomials in a single variable
*x*.

- PDF version (good for viewing in your browser)
- PostScript version (good for sending to your printer)
- LaTeX source (good for editing yourself)
- Victoria's Venn diagram

- State De Morgan's laws. Use truth tables to show why they're correct.
- Assume that
*P*is a compound proposition obtained from*p*_{1},...,*p*_{n}by using only negation (NOT, or ¬), disjunction (OR, or ∨), and conjunction (AND, or ∧). State the definition of the**dual***P*^{*}of*P*. - Assume that
*P*and*Q*are logically equivalent compound propositions obtained from*p*_{1},...,*p*_{n}by using only negation, disjunction, and conjunction. Show that the duals*P*^{*}and*Q*^{*}are also logically equivalent. [Hint:*You may want to use De Morgan's laws.*] - State the definitions of
**tautology**and**contradiction**. - Show that
(
*p*∧ (*p*→*q*)) →*q*is a tautology using:- truth tables.
- logical equivalences.

- [
*Disjunctive normal form.*] A compound proposition is in**disjunctive normal form**if it obtained by taking the disjunction of conjunctions of the variables and their negations, with one conjunction for each combination of truth values for which the proposition is true. [Hint:*Consider individual rows of the truth table.*]- Let
*p*_{1},...,*p*_{n}be propositions. Given arbitrary truth values*t*_{1},...,*t*_{n}, find a compound proposition which is true exactly when the proposition*p*_{i}has the truth value*t*_{i}. [Hint:*This can be done using only conjunctions (AND, or ∧) of the propositions*]*p*_{i}and their negations. - Suppose now that
a truth table in
*n*propositional variables is specified. Use part 1 to construct a compound proposition with this truth table. [Hint:*This can be done using only disjunctions (OR, or ∨) of compound propositions of the form you found in part 1.*] - Use parts 1 and 2 to explain why the disjunctive normal form of a truth table always exists.
- What is the disjunctive normal form
of
*p*→*q*?

- Let
- We define the logical operators NAND, or ↑, and NOR, or ↓,
by
*p*↑*q*:= ¬(*p*∧*q*) and*p*↓*q*:= ¬(*p*∨*q*).- Find a proposition equivalent to ¬
*p*using only ↓. - Find a proposition equivalent to
*p*∧*q*using only ↑.

- Find a proposition equivalent to ¬
- [
*Functional completeness.*] A collection of logical operators is called**functionally complete**if every truth table in*n*propositional variables is the truth table of a compound proposition which uses only those logical operators.- Show that ¬, ∧, and ∨
form a functionally complete collection of logical operators.
[Hint:
*Use disjunctive normal form.*] - Show that ¬ and ∧ alone
form a functionally complete collection of logical operators.
[Hint:
*Use De Morgan's laws.*] - Show that ↑ by itself
forms a functionally complete collection of logical operators.
[Hint:
*Use problem 7.*]

- Show that ¬, ∧, and ∨
form a functionally complete collection of logical operators.
[Hint:
- How many different truth tables of compound propositions
are there involving
*n*propositional variables? List those involving two propositions*p*and*q*. Do you have descriptive names (such as "*p*AND*q*") for all of them? - Show that
∀
*x*P(*x*) ∨ ∀*x*Q(*x*) and ∀*x*∀*y*(P(*x*) ∨ Q(*y*)) are logically equivalent. [Hint:*The new variable*]*y*is necessary to combine the quantifications correctly. - Show that ∀
*x*P(*x*) ∨ ∃*x*Q(*x*) and ∀*x*∃*y*(P(*x*) ∨ Q(*y*)) are logically equivalent.

- Show that
∀
- [
*Prenex normal form.*] A proposition is in**prenex normal form**if it consists of a string of quantifiers (universal or existential) followed by a compound proposition involving no quantifiers.- Put the following statements in prenex normal form:
- ¬∀
*x*P(*x*); - ¬∃
*x*P(*x*); - ∀
*x*P(*x*) ∧ ∀*x*Q(*x*); - ∀
*x*P(*x*) ∧ ∃*x*Q(*x*); - ∃
*x*P(*x*) ∧ ∃*x*Q(*x*); - ∀
*x*P(*x*) ∨ ∀*x*Q(*x*); - ∀
*x*P(*x*) ∨ ∃*x*Q(*x*); - ∃
*x*P(*x*) ∨ ∃*x*Q(*x*).

*Use problem 10 for some of these.*] - ¬∀
- Show how to transform an arbitrary statement
into a statement in prenex normal form.
[Hint:
*Use disjunctive normal form.*] - Express ∃!x P(
*x*) ("There exists a unique*x*such that ...") in prenex normal form. [Hint:*You will need to use the statement "*]*x*=*y*".

- Put the following statements in prenex normal form:
- Describe a procedure for listing all the subsets of a finite set.
- If
*A*,*B*,*C*are finite sets, then |*A*∪*B*∪*C*| = |*A*| + |*B*| + |*C*| − |*A*∩*B*| − |*B*∩*C*| − |*C*∩*A*| + |*A*∩*B*∩*C*|. Draw a Venn diagram illustrating this; then explain in words why it is true without using the diagram. - Let
*A*_{k}:= {1,2,...,*k*} for*k*= 1,2,3,.... In terms of*n*, find:*A*_{1}∪*A*_{2}∪*A*_{3}∪ ··· ∪*A*_{n};*A*_{1}∩*A*_{2}∩*A*_{3}∩ ··· ∩*A*_{n};*A*_{2}∪*A*_{3}∪ ··· ∪*A*_{n}(assuming*n*≥ 2);*A*_{2}∩*A*_{3}∩ ··· ∩*A*_{n}(assuming*n*≥ 2).

- State the definitions of
**domain**,**codomain**and**range**of a function. - State the definitions of when a function is
**injective**(or one-to-one),**surjective**(or onto), and**bijective**(or invertible):- in words;
- in logical notation (with quantifiers).

Go back to the MATH 112 homepage.

This web page was written in 2003 by Toby Bartels. Toby reserves no legal rights to it.

Although the page has been preserved in its original form, the files linked from it have been converted to DjVu using Any2DjVu; they can be viewed on almost any operating system using DjVuLibre.

The permanent URI of this web page
is
`http://tobybartels.name/MATH112/2003/homework/`

.