CSCI-C 241 Test 2 Review (HW 12.5)
Instructor: Wennstrom
Assigned Monday, April 12th, 2021
Due Tuesday, April 20th 2021
This assignment contains a small amount of new material (the very last problem), but
is primarily meant to be a review assignment, intended to help you study for the test that
will be held this week (Thursday 4/15 - Saturday 4/17). I recommend trying to do all
of these problems except the last one before the review lecture on Wednesday/Thursday.
The assignment itself isn’t due until next Tuesday (4/20), so you can worry about the last
mini-homework-style problem after the test is over.
Note that this is not a comprehensive review assignment; it’s only intended to touch on
some of the trickier material that will be on the second test.
For grading purposes, this assignment will be treated like a mini-homework: it is worth
6 points, and you can turn it in up to a week late with a 3-point penalty.
1. For this problem, the universe is some set of books. T (x) means “x is a textbook.” E(x)
means “x is in English.” R(x, y) means “x references y.”
Translate the following sentences into formulas of first-order logic.
(a) Every textbook has a reference to a book written in English.
(b) No book has references to all textbooks.
(c) No English book has references to any textbooks.
(d) There is a book that doesn’t reference every English book.
Translate the following first-order logic formulas into English.
(e) ∀x(T (x)→∃yR(y, x)) (Note the order of x and y.)
(f) ∃x∀y(T (y)→¬R(x, y))
(g) ∀x∃y(T (y) ∧ ¬R(x, y))
2. Give a toy model that fits the given requirements. If you think no such model exists,
explain why not. For your toy models, let the universe be some set of real numbers.
Draw a picture of your universe with arrows between all, some, or none of the numbers.
Use the following definitions. Z(x) means “x is an integer.” N(x) means “x is negative.”
P (x, y) means “x points to y.” Note that the members of your universe are real numbers,
and they don’t all have to be integers.
(a) Give a toy model that satisfies ∀x∃yP (x, y) and ¬∃y∀xP (x, y). Your universe must
contain at least three numbers.
(b) Give a toy model that satisfies ∀x(Z(x)→∃yP (x, y)) and ∀x(Z(x)→∃y ¬P (x, y)).
There must be at least two integers and at least two numbers that are not integers.
(c) Give a toy model that satisfies ∀x∃y(N(y)∧P (x, y)) and ¬∃x∀y(N(y)→P (x, y)).
There must be at least two negative numbers and at least two positive numbers.
(d) Give a toy model that satisfies ∃x∀y(N(y)→P (x, y)) and ∃x∀y(N(y)→¬P (x, y)).
There must be at least two negative numbers and at least two positive numbers.
3. Give an example of a relation on the set of text strings that is not reflexive, not antire-
flexive, not symmetric, not antisymmetric, and not transitive.
4. Prove that for any sets A, B, C, D, and E, if D∩B ⊆ A\C, then D∩E ⊆ E \ (B∩C).
5. Prove that the cube of an odd number is always odd.
6. Let R be a relation on R defined by {(x, y) | x− y > 1}.
(a) Is R reflexive? Justify your answer with a counterexample or a short explanation
as appropriate.
(b) Is R antireflexive? Justify your answer with a counterexample or a short explanation
as appropriate.
(c) Is R symmetric? Justify your answer with a counterexample or a short explanation
as appropriate.
(d) Is R antisymmetric? Justify your answer with a counterexample or a short expla-
nation as appropriate.
(e) Prove that R is transitive.
7. Use induction to prove the following claim:
For all natural numbers n, if n ≥ 2, then 3n > 2n+1.
Page 2

欢迎咨询51作业君