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? Write the first two lines of your proof.
Assume that a and b are odd integers. By definition of an odd number, let a = 2k + 1 and b = 2j + 1 for some integer k and some integer j.
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}
Determine the values of the following:
a. 11110000 ⋁ 10101010
b. 11110000 ⋀ 10101010
c. 11110000 ⊕ 10101010
a.) 11111010
b.) 10100000
c.) 01011010
State the converse, contrapositive, and inverse for the following statement. Which one (converse, contrapositive, or inverse) is equivalent to the original statement?
I walk to class only if it is sunny.
Converse: If it is sunny, then I walk to class.
Contrapositive: If it is not sunny, then I do not walk to class.
Inverse: If I do not walk to class, then it is not sunny.
Contrapositive is equivalent to original statement.
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.
Proof by contrapositive.
Assume that n is odd, such that by definition of an odd number, n = 2k +1 for some integer k.
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}
Construct the boolean circuit.
¬(p ∧ (q ∨ ¬r))
See slides.
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.
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 such that, by definition of an odd number, n = 2k + 1 for some integer k.
Proof by contradiction: Assume by contradiction that 3n + 2 is even and that n is odd.
Find |{a, {a}, {a, {a}}}|
3.
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 statements:
a. “There is somebody who nobody knows."
b. “There is somebody whom Hank does not know.”
a. “There is somebody who nobody knows.”
∃x∀y (¬K(y, x))
b. “There is somebody whom Hank does not know.”
∃x (¬K(Hank, x))
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) (power set of A) for A = {a, b, {a, b}}.
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}, {{a, b}}, {a, b}, {a, {a, b}}, {b, {a, b}}, {a, b, {a, b}}}.
If |B| = n, then |P(B)| = 2n
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.