Logic
Let p, q, and r be the following propositions:
p: Grizzly bears have been seen in the area.
q: Hiking is safe on the trail.
r: Berries are ripe along the trail
Translate the following to logic using p, q, and r and logical connectives (including negations).
If berries are ripe along the trail, hiking is safe if and only if grizzly bears have not been seen in the area.
r → (q ↔ ¬p)
Suppose we want to use a direct proof to show that the sum of two odd integers is even. What would we assume?
Assume that a and b are odd integers.
Define A = {0, 3, 6, 8, 9} and B = {1, 3, 9}. Find...
a. A ⋃ B
b. A ⋂ B
a. {0, 1, 3, 6, 8, 9}
b. {3, 9}
Let f : A → B where A = { 1, 2, 3, 4} and B = {a, b, c, d}. Determine which of the following are functions.
1. f = {(a, 1), (b, 3), (c, 2), (d, 4)}
2. f = {(1, d), (2, b), (3, d), (4, a)}
3. f = {(1, a), (2, d), (3, b)}
Only 2.
Let an = 3an-1 – an-2 , a0 = 1, and a1 = 1. What is a5?
a5 = 34
Determine if (¬p → (q → r)) is logically is equivalent to ((¬q ∨ r) → p). Must show work to get points!
No, they are not logically equivalent because the bicondition of (¬p → (q → r)) and ((¬q ∨ r) → p) is not a tautology.
Determine what method of proof you would use to prove the following. What would the first line of your proof be?
Let n be a positive integer. n is even if 7n + 4 is even.
Consider the contrapositive statement: if n is odd, then 7n + 4 is odd.
Proof by contrapositive. Assume that n is odd.
Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find A – B and B – A.
A – B = {1, 2, 4, 5}
B – A = {0, 6}
Decide whether the function is 1-1, onto, both, or neither. Let f:{1, 2, 3} → {a, b, c, d}.
f = {(1, d), (2, b), (3, c)}
1-1 only.
Construct the boolean circuit.
¬(p ∧ (q ∨ ¬r))
See slides.
State the converse, inverse, and contrapositive for the following statement. Please use traditional "If..., then..." phrasing.
There is a quiz only if I go to class.
Converse: If I go to class, then there is a quiz.
Inverse: If there is not a quiz, then I do not go to class.
Contrapositive: If I do not go to class, then there is not a quiz.
Identify two methods we could use to prove the following statement AND what we would assume for each method.
Let n be an integer. If 3n + 2 is even, then n is even.
Proof by contrapositive: Assume n is odd.
Proof by contradiction: Assume by contradiction that 3n + 2 is even and that n is odd.
Find |{a, {a}, {a, {a}}}|
3
Decide whether the function is 1-1, onto, both, or neither. Let f: 𝑍 → 𝑍 (integers).
f(x) = 2x
1-1, but not onto
Let K(x, y) be the statement “x knows y,” where the domain for both x and y consists of all people in the world. Use quantifiers to express the following statement:
“There is somebody who nobody knows."
∃y∀x (¬K(x, y))
Suppose there are three trunks with inscriptions. Trunk 1 says “The treasure is in Trunk 3,” Trunk 2 says “The treasure is in Trunk 1,” and Trunk 3 says “This trunk is empty.” A Queen who never lies says "Exactly two of the inscriptions are true." Which trunk is the treasure in?
Treasure is in Trunk 1.
Prove the following statement:
Let x, y 𝜖 ℝ. If xy is irrational, then x is irrational or y is irrational.
Proof by contrapositive or contradiction.
Construct P(A) for A = {a, b, {c}}.
Bonus question: What is |P(B)| if |B|=n?
P(A) = {{}, {a}, {b}, {{c}}, {a, b}, {a, {c}}, {b, {c}}, {a, b, {c}}}.
If |B| = n, then |P(B)| = 2n
Let f: R → R and f(x) = 5x - 7.
Does f have a valid inverse? If yes, find it and prove your solution.
*You do NOT need to prove that f has an inverse.
f-1(x) = (x + 7)/5
Proof: show f(f-1(x)) = x = f-1(f(x)).
Find a solution (explicit formula) to the recurrence relation an=2n * an-1 when a0 = 1.
an = 2n * n!