CSE 260 Exam 1 Fall 2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Exam 1
CSE 260
Version A
Total points: 50
For questions 1-24 answer the questions using the bubble sheet provided.
(Total Points: 22)
For True, fill in the bubble for a.
For False, fill in the bubble for e.
Part 1 (2pts): Which of the following are propositions?
Q1: 3 is an even number.
Q2: There are 45 students enrolled in CSE 260 this semester.
Q3: How much does it cost?
Q4: This statement is false.
Part 2 (4pts) What is the truth value of the following propositions?
Q5: (1 = 2) ↔ Lansing is the capital of Michigan
Q6: (1 + 1 = 3) → Capital of Eritrea is Asmara
Q7: 3 is a prime number V 4 is a prime number
Q8: 3 is a prime number ⊕ 4 is a prime number
Part 3 (9pts) What is the truth value of the following propositions?
Q9: 3 x EVEN (x) ^ PRIME(x), where EVEN(x) is true iff x is even and PRIME (x) is
true iff x is prime. The universe of discourse is the set of positive integers {1, 2, 3, 4, …}
Q10: ∀x3y(x ≠ 0 → xy = 1) if the universe of discourse is the set of all integers.
Q11: 3x∀y(xy = 0) if the universe of discourse is the set of all integers.
Q12: ∀x3y(x = y2) if the universe of discourse is the set of all integers.
Q13: ∀x(2x > x) if the universe of discourse is the set of all integers
For the next two questions, let P(x) be the statement “2x = x 2 ”
Q14: P(0)
Q15: 3x P(x) if the universe of discourse is the set of odd integers.
Q16: ∀x3y x < y, where the universe of discourse is the set of positive integers
Q17: ∀x3y x < y where the universe of discourse is the set of negative integers
Part 4 (4pts) Which of the following are tautologies (bubble A), contradictions (bubble B) or cou在!uaeuc!e2 (pnppIe C)
Q18: [b ∧ (p → q)] → q
Q19: (p → q) ↔ (q → p)
Q20: (b ∧ ㄱb) V (b Vㄱb)
Q21: (b V q) → p
bgL在 Q (3b在2)
Q22: Which formula(s) are equivalent to p → q? (Fill in all 在pg在 gbbI入)
g) b V d p) b V ㄱd c) ㄱb V d d) q → p e) ㄱq → ㄱb
Mp!cp is/are the negation of the statement“All cities in Michigan are small” (上!II !u all 在pg在 gbbI入)
a) All cities in Michigan are large
p) eo山e c!在!e2 !u W!cp!agu gLe 2山gII
c) eo山e c!在!e2 !u W!cp!agu gLe IgLae
q) Vo c!在入 !u W!cp!agu !2 2山gII
e) Vo c!在入 !u W!cp!agu !2 IgLae
Q24: Mp!cp LoL山nIge gLe edn!^gIeu在 在o:
(((p ∧ q) → (r ∨ s)) ↔ ((p ∨ s) → (r ∧ q))) ↔ (((s ∧ q) → (r ∨ p)) ↔ (((p ∧ (¬s ∨ r)) ∨ (¬r ∧ q)))) (eeIec在 all 在pg在 gbbI入. n2e 在pe ---- 在o !qeu在!L入 cpguae2 qoue 在o 在pe oL!a!ugI LoL山nIg.)
A:¬(((p ∧ q) → (r ∨ s)) ↔ ((p ∨ s) → (r ∧ q))) ↔ (((s ∧ q) → (r ∨ p)) ↔ (((p ∧ (¬s ∨ r)) ∨ (¬r ∧ q))))
----
B:((¬(p ∧ q) ∨ (r ∨ s)) ↔ (¬(p ∨ s) ∨ (r ∧ q))) ↔ ((¬(s ∧ q) ∨ (r ∨ p)) ↔ (((p ∧ (¬s ∨ r)) ∨ (¬r ∧ q))))
------------------------
C:(((p ∧ q) → (r ∨ s)) ↔ ((p ∨ s) → (r ∧ q))) ↔ (((s ∧ q) → (r ∨ p)) ↔ (((p ∧ ¬(s ∧ ¬r)) ∨ ¬(r ∨ ¬q))))
------------
D:¬(((p ∧ q) → (r ∨ s)) ↔ ((p ∨ s) → (r ∧ q))) ⊕ (((s ∧ q) → (r ∨ p)) ↔ (((p ∧ (¬s ∨ r)) ∨ (¬r ∧ q))))
--- -----
For questions 25-42 answer the questions in the boxes provided.
(30pts) Other questions
Q25: (1pt) How many rows are in the truth table of p ↔ q → r V (s V p)?
Q26: (1pt) Negate the following formula using the Duality Law (Do not simplify):
(p ∧ ㄱq) V (r Vㄱs)
For the next two questions, translate these statements into English, where
R(x) is “x is a rabbit”,
H(x) is “x hops”, and the domain consists of all animals.
Q27: (1pt) ∀x (R(x)→ H(x))
Q28: (1pt) 3x (R(x)∧H(x))
For the next 3 problems, let L(x, y) be the statement “x loves y,” where the domain for both x and y consists of all people in the world. Use quantifiers to express the statement
Q29: (1pt) There is somebody whom everybody loves.
Q30: (1pt) Everyone loves himself or herself.
Q31: (1pt) There is somebody whom no one loves.
For the next 2 questions: let x, y, z, w be positive integers.
Using only the primitives of + and *, = and >, define proposition functions for
Q32: (1pt) IsFactor(x, y): True iff x is a factor of y
Q33:
1.
(3pts) CommonFactors(x, y): True iff x and y share a common factor other than
For the next two questions, using the following proposition functions, convert the following sentences into predicate logic. The universe of discourse is the set of positive integers {1, 2, 3, 4, …}
PRIME(x) : True iff x is prime
Factor(x, y): True iff x is a factor of y
Q34: (1pt) If a number is divisible by 10 then it is divisible by 5
Q35: (1pt) No prime number other than 3 is divisible by 3
Q36: (3ptrs) Prove the following formula is a tautology by using substitution rules
(p ∧ q) → (p ∨ q)
|
(p ∧ q) → (p ∨ q) |
Justification |
≡ |
|
|
≡ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
Q37: (3pts) Convert the following truth table into an equivalent formula.
p |
q |
r |
Formula |
T |
T |
T |
T |
T |
T |
F |
F |
T |
F |
T |
F |
T |
F |
F |
T |
F |
T |
T |
F |
F |
T |
F |
F |
F |
F |
T |
F |
F |
F |
F |
F |
Q38: (3pts) Write the proof h1 ∧ h2 ∧ h3 ⇒ c, where
h1 = (p → (q → (s ∧ t))
h2 = p
h3 = q
c = s
Q39: (4pts) Write the following proof
Let m be a (fixed) integer
h1 = 3x m = 15x
c1 = 3x m = 5x
c2 = 3x m = 3x
Show that h1 ⇒ (c1 ^ c2) using proof chain method
Q40: (4pts) Convert the following statements into predicate logic to identify the
hypothesis and conclusion. Then, show that the conclusion follows from the hypothesis. (You can write the hypothesis and conclusion in the proof itself.)
Each student in this class owns a personal computer.
Everyone who owns a personal computer can use a word processing program. Zeke is a student in this class.
Therefore Zeke can use a word processing program.
Q41: (1pt) (Bonus/Challenge Question: Convert the following statement into predicate
logic without using any proposition functions). For any variable, the universe of discourse should be the set of positive integers {1, 2, 3, 4, …}:
There are infinitely many primes
Q42: (1pt) How many distinct formulae exist with n propositions? Explain (Note two
formulae are equivalent if their truth tables are identical.)
2023-06-06