0.3 Discrete structures logic  (Page 20/23)

a. (1) You get promoted only if you have worked hard.

(2) If you have worked hard, you get promoted

b. (1) To get promoted you must work hard.

(2) If you work hard, then you get promoted

c. (1) Whenever there is a noreaster, the beach erodes

(2) If there is a noreaster, the beach erodes.

d. (1) I will stay home, if it snows tonight.

(2) If it snows tonight, I stay home.

7. Indicate which of the following sentences are translated correctly.

Let S represent “It is snowing”, F represent “It is below freezing” and G represent “I go outside”.

a. “If it is snowing or below freezing, then I don’t go outside.”

translates to (S ⋁ F) → ¬G

b. “I go outside only if it is neither snowing nor below freezing.”

translates to (¬S ⋀ ¬F) → G

c. “Whenever I go outside, it is snowing.”

translates to S → G

d. “It is either snowing or below freezing.”

translates to S ⋁ F

8. For each of the following propositions, indicate what they are (Tautology, Contingency or Contraction).

a. P → P

b. ¬P → P

c. [[P → Q] ⋀ P]⋀ ¬Q

d. [P ⋁ [P⋀ Q] → P

e. [P ⋀ [P⋁ Q] ↔ ¬P

10. Indicate which of the following statements are correct and which are not.

a. [R ⋀ ¬S] ↔ [¬S ⋀ R]

b. ¬[P ⋁ [Q ⋀ R]] ↔ [¬P ⋀ ¬[Q ⋀ R]]

c. [[P ⋀ S] ⋁ R]↔ [[P ⋀ R] ⋁ S]

d. [¬¬P ⋁ Q] ↔ [P → Q]

e. [[Q ⋁ R] ⋀ ¬[R ⋀ Q]]↔ [Q ⋁ R]

11. Indicate which of the following statements are correct and which are not. If it is correct, what implications are used?

a. If it snows, the schools will be closed. It is snowing.

Therefore, the school is closed.

b. Tom is healthy and (Tom is) happy.

Therefore, Tom is happy

c. John will work at a software company this summer.

Therefore, this summer John will work at a software company and a grocery store.

d. If I work all night, I can finish this project.

But I did not work all night. Therefore, I did not finish the project.

e. If I eat spicy food, it upsets my stomach. If my stomach is upset, I get a bad a dream.

Therefore, if I eat spicy food, I get a bad dream.

12. Indicate which of the following statements are correct and which are not.

Let G(x,y) represent the predicate x>y.

a. G(6, 13) means 13 is greater than 6.

b. G(2, 0) is true.

c. G(7, 1) means 7 is greater than 1.

d. “4 is less than 5) can be represented by G(5,4).

13. Indicate which of the following statements are correct and which are not.

Let E(x) mean x is even and G(x,y) mean x>y. Let the universe be the set of naturals.

a. ∀x ∃y G(y, x) is true, but ∃x ∀y G(y, x) is false.

b. ∃y E(x) is true.

c. ∀x ∀y G(x, y) is true.

d. ∀x G(∃y, x) is a proposition.

14. Indicate which of the following statements are correct and which are not.

a. ∃x [P(x, y) ∀x ⋀ Q(x,y)] is a wff.

b. ∀x [P(x) → ∀y [ Q(y) → ∃z R(z) ]] is a wff.

c. 2>1 ⋀ 3<5 is a wff.

15. Indicate which of the following statements are correct and which are not.

Let P(x) mean x is happy.

a. {Tom} is an interpretation for [∃x P(x) ⋀ P(y)].

b. ∀x P(x) is unsatisfiable.

c. {P(Tom) ⋁ ∃x ¬P(x)] is valid.

d. ∀x P(x) is equivalent to ∀y P(y)

16. Indicate which of the following statements are correct and which are not.

Let H(x) mean x is happy.

Let the universe be the set of people