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)

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

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.)