1 True-False
1 point for each if correct, 0 points if unanswered, -1 point if incorrect. Do be Careful: Some students for this section end up with 0 points because of guessing. The ended up with half correct and half incorrect, which results in 0 points!
1. An antisymmetric relation is a relation that is not symmetric.
2. Equivalent propositional statements have the same truth values for every truth value assignment to the component statements.
3. An Euler cycle is also a Hamilton cycle.
4. The sentence ?xP (x, y), y is a free variable.
5. The sentence ?xP (x, y) has a truth value
6. The sentence ?x(?yP (x, y)), has a truth value.
7. The inductive conclusion for an inductive proof for a sequence of sen- tences P (n),n = 1, 2, 3 ... is ?n, P (n) is a true statement.
8. In the statement of the theorem “twice an odd integer is even,” an existential quanti?er is understood.
9. To prove the conjecture that “If Denver is the capital, then Colorado is the state,” it is su?cient to prove that “If Colorado is the state, then Denver is the Capitol.”
10. The set of all subsets of a n-set has 2n elements.
11. The principle of inclusion-exclusion requires that the sets A and B should be disjoint in order to ?nd the number of elements in A ? B.
12. The number of combinations of r objects out of n, r > 1, is fewer than the number of permutations of r objects construct from n objects. Assume n > r.
13. The number of all functions from an n-set to a 2-set is 2n.
14. Let S = {0, 1} with the relation h = {(1, 1)}. This relation is transitive.
15. Every binary tree with n edges has 2n vertices.
16. Every relation is a function.
17. Any proof done by way of contradiction can be done by way of contra- position.
2 Problems with short answers
1. (2) Write the negation of the statement: ( ?x ? N, x2 = 2) in two ways, formally and then in plain English. Is the negation a true statement?
2. (4) The following binary relation is de?ned on the set A = {0, 1, 2, 4, 6}:
R = {(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)}
a) Draw the directed graph
b) Is the relation is re?exive?
c) Is the relation symmetric?
d) Is the relation is transitive?
Give a counter-example in each case in which the relation does not satisfy one of the speci?ed properties.
3.(1 point) A collection of numbers M is de?ned recursively by these two rules: 1) 2 and 3 belong to M and 2) If X and Y belong to M, then so does X*Y.
Which of the following numbers belong to M?
a.6 b.9 c.16 d.21 e.26 f. 54 g.72 h.218.
4. (1 point) How many injective functions are there from the set {a, b, c, d, e, f }
into {1, 2, 3} ?
5. (4 points) A club with 10 women and 7 men needs to form a committee of size 5. Answer the following being careful to show your answer in terms of the combinatorial functions you would use. Do not give a numerical answer.
1. How many committees are possible?
2. How many committees are possible if a committee must have 3 women and 2 men?
3. How many committees are possible if a committee must consist of all men?
4. How many committees are possible if a committee must have not less than two women?
5.(1 point) Is the following statement true, false or neither: “x is prime.” Give a reason for your answer.
6. (1 point) Write a formal statement in the predicate logic for the state- ment: “Some cats chase all squirrels.” Let the universe be all things. Use the following for your statements: C(x) = “x is a cat, S(x)= “ x is is a squirrel”, and Ch(x,y) = “x chases y”.
7. (1 point) There are implicit quanti?ers in the statement “The square of any odd integer is of the form 8m + 1.” Write the statement with the quanti?ers explicit. The universe is the set of integers N. Use O(n) for the sentence: “n is odd.” Caution: Make sure ALL variables are quantified in your statement.
8. (3 points) Use your newly developed translation powers to translate this argument into its predicate logic format, including all quanti?ers, so that you can see its logical structure. Then decide whether the following argument is valid and give your reason in terms of just the logical form of the argument for accepting or rejecting its validity. Use I(x) = “x is intelligible.” T(x) = “x troubles me.” Let c be the constant this course. (This problem was posed by Lewis Carroll) :
1. Nothing intelligible ever troubles me.
2. This course troubles me.
3. Therefore, this course is unintelligible.
9. (1) List the set of all subsets of: {{Ø}, Ø}.
3 Multiple Choice
(1 point for each question)
1. The negation of the statement “I missed the train but my watch was not slow” is:
a. I did not miss the train and my watch was not slow.
b. I missed the train or my watch was slow.
c. I did not miss the train or my watch was slow.
d. I missed the train or my watch was not slow.
e. None of the above.
2. The converse of “If I either misplaced my keys or forgot the combina- tions, then I cannot open my car door” is:
a. If I can open my car door, then I did not misplace my keys and I did not forget the combination.
b. If I did not misplace my keys and I did not forget the combination, then I can open my car door.
c. If I can open my car door, then I did not misplace my keys and I did not forget the combination.
d. If I cannot open my car door, then I did not misplace my keys and I did not forget the combination.
e. None of the above.
3. Let the universe be the positive integers. Given the statements: D2(x)
= “ x is divisible by 2” and D6(x) = “x is divisible by 6.” A formal
statement that states divisibility by 6 guarantees divisibility by 2 is:
a. ?x, D2(x) ? D6(x)
b. ?x, D6(x) ? D2(x)
c. ?x, D2(x) ? ¬D6(x)
d. ?x, D6(x) ? ¬D2(x)
e. None of the above
4. The negation of the statement ?x ? N, x2 = 2) is a. ?x ? N, x2 = 2
b. ?x ? N, x2 /= 2
c. ?x ? N, x2 /= 2
d. None of the above
5. ¬(p ? q) ? p is logically equivalent (=) to:
a. q
b. ¬q
c. c (symbol for a contradiction)
d. (p ? q)
e. None of the above
4 Truth Values
(1 point each) Determine the truth value of the following statements if the universe of discourse of each variable is the set of rational numbers.
1. ?x /= 0 ?y(xy = 1)
2. ?x(x2 = 2)
3. ?x?y(x + y = 1)
4. ?x(x2 = -1)
5. ?x(?y(?z(z = x+y )))
6. ?x?y((x + 2y = 2) ? (2x + 4y = 5))
7. ?x(?y(x2 = y))
8. ?x?y((x + y = 2) ? (2x - y = 1))
9. ?x(?y(x = y2))
10. ?x?(y /= 0(xy = 1))
11. ?x(?y(xy = 0))
12. ?x(?y(x + y /= y + x))