Truth Tables & 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)}
4. {(1, a), (1, b), (2, c), (3, d), (4, a)}
Only 2.
Determine the value of the following:
11110000 ⊕ 10101010
01011010
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 each function is 1-1, onto, both, or neither. Let f:{1, 2, 3} → {a, b, c, d}.
1. f = {(1, a), (2, c), (3, a)}
2. f = {(1, d), (2, b), (3, c)}
1. Neither
2. 1-1
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 each function is 1-1, onto, both, or neither. Let f: 𝑍 → 𝑍 (integers).
1. f(x) = 2x
2. f(x) = x + 5
3. f(x) = |x|
1. 1-1, but not onto
2. Bijective
3. Neither
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 the treasure is 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}}.
What can you say about the number of elements in a power set of a set with n elements? (Ex: |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)).
There are three types of people: knights who always tell the truth, knaves who always lie, and spies who can either lie or tell the truth. You encounter three people, A, B, and C. You know one of these people is a knight, one is a knave, and one is a spy. What can you determine about these three people if A says “I am the knight,” B says “I am the knave,” and C says “B is the knight.”
A is the knight, B is the spy, and C is the knave.