Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 260

Fall 2021

Version A

Total points: 48

For Questions 1-11, use the multiple choice answer sheet given at the end.

a. It is not a proposition

b. It is a proposition and it has truth value true

c. It is a proposition and it has truth value false

d. It is a proposition but there is not enough information to determine the truth value

1. (1pt) How is the weather today?

2. (1pt) ∃x (2x + 18 = 25)

3. (1pt) Prof. Kulkarni went to Ann Arbor on Oct 1, 2021.

4. (1pt) 9 + 10 = 21

5. (1pt)  (The current year is 2077) → (1+1 = 3)

6. (1pt)  2 is a prime number ⊕ 3 is a prime number

7. (1pt)

8. (1pt)

9. (1pt) (5+6=10)→(7+8>16)

10. (1pt) 2x = 7

11. (1pt) Do leaves change color in Spring

12. (1pt) is a tautology. Use a to answer true and b to answer false.

13. (1pt) If you create a truth table for , how many rows would the truth table have? Give a brief explanation. Do not create a truth table for this formula.

14. (1pt) Write the negation of `Everyone in this class plays violin’  in English (do not use propositions). Do not use `It is not the case that…’

15. (2pts) Negate the following formula using duality law.

16. (2pts) Identify an UoD so that the formula evaluates to true. And, identify an UoD so that the formula evaluates to false. Give a brief explanation.

17. (2pts) Let be a wff involving variables . It was determined that the formula is equivalent to .  If we write the truth table of , how many rows in it will result in truth value true. Give a brief explanation.

18. (8pts) Let x, y, z, w be positive integers.

Using the primitives of + and * and >, < and = (equal),

boolean connectives and quantifiers ∀ and ∃, define proposition functions for

a. f(x, y) is true if the remainder is 3 when x is divided by y. (Assume that x and y are greater than 3.)

b. g(x, y) : is true if x and y share a common factor other than 1

c. Let r be a real number. Define f(r) : r is a rational (Note that rational is defined as it can be expressed as p/q where p and q are integers and the denominator is non-zero.)

d. f(x) is true if 5 is a factor of x but 3 is not a factor of x

19. (4pts) Write the proof of

20. (4pts) Everyone who reads likes Harry Potter.

Everyone who likes Harry Potter owns a fake wand.

Someone in this class reads. Show that someone in this class owns a fake wand.

Proposition functions

Premises

Conclusion

21. (3pts) Show that the following formula is a tautology by only using substitution rules

22. (3pts) Convert the following truth table into an equivalent formula.

23. (5pts) Let H(x, y) denote that x scored more points in CSE 260 Exam 1 than y.

Use quantifiers to express the following statements.

Assume that the universe of discourse is students in CSE 260 class

a. Jane got more points than everyone else

b. John and Jane got the same points. (Note that this is same as John did not get more points than Jane and Jane did not get more points than John)

c. No two students got the same points

d. Exactly two students got the highest points in the exam. (Note that this question is not talking about whether they got 100%. It is just saying that they got highest among the points)

e. Evaluate the truth value of Explain your answer.

24. (1pt) During the exam, you did not make use of any unauthorized resources. (If you did, we are granting you until 9am tomorrow to take responsibility. If you do, while you will receive 0 for any affected questions, there will be no other consequences.)

Mark b for Question 24 for multiple choice question for free bonus point

Note that this does not apply if TA had suspected cheating in your case already.

Use this space if you need additional space for any other question.