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

CSE 260

Exam 1 A

Fall 2022

1. Unless specified otherwise, assume that UoD is {0, 1, 2, 3, …}

2. Unless the question asks to prove this, you can assume that

a. 1, 2, 3, … are integers

b. ½ 1/3, … are rationales

c. are irrationals

3. If you are asked to write a formula, the only acceptable UoDs are integers, reals, rationales or complex numbers. Identify the UoD you are using.

4. Please note that to prevent cheating, multiple choice orders (True, False, etc) may be out of order. Be sure to look at that in answering multiple choice questions.

Multiple Choice Questions. Answer in the bubble sheet at the end.

Q. 1 What time is it?

a) This is a proposition that evaluates to true

b) This is a proposition that evaluates to false

c) This is not a proposition

d) This is a proposition whose truth value is not known

Q. 2

a) This is a proposition that evaluates to true

b) This is a proposition that evaluates to false

c) This is not a proposition

d) This is a proposition whose truth value is not known

Q. 3 UoD = set of real numbers

a) This is a proposition that evaluates to true

b) This is a proposition that evaluates to false

c) This is not a proposition

d) This is a proposition whose truth value is not known

P(2)?

a) True

b) False

c) Not sufficient information

Q. 5 Determine the truth value of the statement ∀x∃y(xy = 1) if UoD is the set of positive integers.

a) True

b) False

c) Not sufficient information

Q. 6

a) True

b) False

c) Not sufficient information

Q. 7 Let P(x,y,z) be proposition that . What is the truth value of

a) True

b) False

c) Not sufficient information

Q. 8 Choose the correct statements

a) ∃xP(x) ∧ ∃xQ(x) and ∃x(P(x) ∧ Q(x)) are not logically equivalent.

b) ∃xP(x) ∧ ∃xQ(x) and ∃x(P(x) ∧ Q(x)) are logically equivalent.

c) ∀xP(x) ∧ ∀xQ(x) and ∀x(P(x) ∧ Q(x)) are not logically equivalent.

d) ∀xP(x) ∧ ∀xQ(x) and ∀x(P(x) ∧ Q(x)) are logically equivalent.

Q. 9 Consider the function

a) This is a one-to-one function that is not onto

b) This is an onto function that is not one-to-one

c) This is both one-to-one and onto function

d) This is neither one-to-one nor onto function

e) This is not a function

Q. 10 Consider the function

a) This is a one-to-one function that is not onto

b) This is an onto function that is not one-to-one

c) This is both one-to-one and onto function

d) This is neither one-to-one nor onto function

e) This is not a function

Q. 11 Select all true statements

a)  0 ∈ ∅

b) {∅} ⊆ {∅}

c) {∅} ∈ {∅}

d) ∅ ∈ {∅, {∅}}

Q. 12 What is the cardinality of the set }

a) 4

b) 5

c) 6

d) 7

e) 8

Q. 13 is same as

a)

b) - Correct

c)

d)

e)

Q. 14 Let . What is the inverse of this function

a)

b)

c) - Correct

d)

e) Inverse does not exist

Q. 15 (1pt) Let A = {a, b, c} and B = {1, 2, 3}. What is the cardinality of |A x B|?

(9)

Q. 16 (2pts) Write the truth table for

p	q
T	T	T	F
T	F	T	F
F	T	T	T
F	F	F	F

Q. 17 (3pts) How many rows in the truth table evaluate to true? Explain your answer.

Answer: 7

Explanation : There are 2^3, i.e., 8 rows in truth table. There is only one entry false when all variables are false. So, 7

Q. 18 (1pts) Negate the following

Q. 19 (2pts) Determine the truth value of the statement ∀x∃y(xy = 1) if UoD is the set of positive integers. Explain your answer

True/False    False

Explanation x and y both are positive integers. So, for all x > 1 there is no integer y for which this statement is True. For example, for x = 2 => xy = 1 => y = ½

Q. 20 (2pts) Let C(x, y) denote that x has communicated with y. Consider the statement: Sanjay has talked with everyone except Joseph. Determine if the translation

is correct? Explain.

Correct/Incorrect? Incorrect

Explanation The correct answer is .

Q. 21 (2pts) Using the primitives of + and * and >, < and = (equal), boolean connectives and quantifiers ∀ and ∃, define proposition functions for

NocommonFactors(x, y), 1 is the only common factor between x and y

Done so many times in class, so omitted.

Q. 22 (5pts) Let S(x, y) denote that x is smarter than y where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statements

a) Jane is smarter than John but not smarter than Jill.

S(Jane, John) AND Not (S(Jane, Jill))

b) None is smarter than themselves.

FOR ALL x. NOT S(x, x)

c) Let A, B, C be any three people. If A is smarter than B and B is smarter than C then A is smarter than C.

FOR ALL a, b, c (S(a, b) AND S(b, c)) -> S(a, c)

d) Let A, B be any two people. If A is smarter than B then B is not smarter than A

FOR ALL a, b S(a, b) IMPLIES (NOT S(b, a))

e) Jane is the smartest person in the world.

FORALL x  x!= jane IMPLIES S(jane, x)

Let us assume that √5 is rational that means it can be written as √5 = p/q, where p and q are integers and q is not equal to 0. Also, p and q are co-primes with no common factor except for 1. √5 = p/q =>  p = √5q =>  p^2 = 5 q^2         —- (1) (1) means 5 divides p. So, it can be written as p = 5x =>  q^2 = (p^2)/5 =>  q^2 = ((5x)^2)/5 => q^2 = 5x^2           —- (2) (2) means that 5 also divides q. This contradicts the assumption. Hence, √5 is irrational

Q. 24 (2pts) Prove that there exist x and y such that x and y are rational but is irrational.

x = 2, y = ½ (2)^(½) = √(2) which is irrational Answers may vary

Q. 25 (2pts) Express the following  statements using existential and universal quantifiers and propositional logic, where ∃n means there exist exactly n of those things.

∃2 P(x)

∃x∃,y(x!=y and P(x) and P(y) and !∃z(x!=z and y !=z and P(z))) or ∃x∃,y(x!=y and P(x) and P(y) and ∀ z(x!=z and y !=z → NOT P(z)))

Q. 26 (2pts)  Use rules of inference to show that the hypotheses “Randy works hard,” “If Randy works hard, then he is a dull boy,” and “If Randy is a dull boy, then he will not get the job” imply the conclusion “Randy will not get the job.”

Statements: p: Randy works hard; q: Randy is a dull boy; r: Randy will not get the job To Prove: We need to prove that the proposition “r” is true. Steps (also an alternate easy way to do using MP): 1.  p    [premise] 2. p [premise] 3. q [premise] 4. not p V q [logically equivalent to 2] 5. q [simplification from 4] 6. not q V r [logically equivalent to 3] 7. r [simplification from 6]

Q. 27 (5 pts) Anyone who joins MSU improves their life. If someone improves their life, they earn lots of money. Those that earn a lot of money are happy. Jane has joined MSU. Show that Jane is happy.

Proposition functions M(x) : x has joined MSU, I(x) : x improves their life, L(x) : x gets lot of money, H(x) : x is happy
Hypothesis, M(Jane)
Conclusion: H (Jane)
Seq #	Statement	Justification
1		hypothesis
2		hypothesis
3		hypothesis
4	M(Jane)	hypothesis
5		UI on 1
6	I(Jane)	MP on 4 and 5
7		UI on 2
8	L(Jane)	MP 6 and 7
9		UI on 3