COMPSCI 250: Homework 1 Solved

Description

(10 points) Problem 1.1.3

Let A be the set {1, 2, 3}. Give explicit descriptions (lists of elements) of each of the following sets of sets:

1. {B:B⊆A}

2. {B : B ⊆ A and |B| is even } (Remember that 0 is an even number.)

3. {B : B ⊆ A and 3 ∈/ B}

4. {B : B ⊆ A and A ⊆ B}

5. {B : B ⊆ A and B ̸⊆B}

(10 points) Problem 1.2.10

Let Σ be an alphabet with k letters and let n be any natural. How many strings are in the language Σⁿ? Justify your answer as best you can, though we won’t have formal tools to prove this until Chapter 4.

(12 points) Problem 1.4.9

Choosing variables for the base propositions as needed, translate these English statements into compound propositions.

1. If you don’t eat your meat, you can’t have any pudding.

2. If I’m wearing the antlers, I am dictating, and if I’m not wearing the antlers, I’m not dictating.

3. If this penguin was from the zoo, it would have “Property of the Zoo” stamped on it, and if penguins molt, this penguin could not have “Property of the Zoo” stamped on it.

4. It is not true that if I am arguing, then you must have paid.

(12 points) Problem 1.5.7

Any subset statement may be interpreted as saying that some particular set is empty. Let D be a set of dogs, and let B, R, and F be three subsets of D containing the black dogs, the retrievers, and the female dogs respectively. The statement B ⊆ R, for example, can be interpreted as “all the black dogs are retrievers”, or “there are no black dogs who are not retrievers”, that is, B ∩ R = ∅. For each of the following subset statements, identify the set that is claimed to be empty, both in English and in symbols:

1. B∩F ⊆R

2. F ⊆R∩B

3. B⊆R∪F

(12 points) Problem 1.5.10

Let X = {1, 2, 3, . . . , 10} and let I be the set of all intervals in X, that is, subsets of the form {a, . . . , b} for some naturals a and b.

1. How many intervals are in the set I? (Don’t forget the empty set.)

2. How many of the intervals are subsets of {2, 3, 4, 5, 6}?

3. How many of the intervals are disjoint from {2, 3, 4, 5, 6}?

(10 points) Problem 1.7.9

Here we have another islander problem as in Problem 1.6.9. There are three islanders: A says “If B and I are both telling the truth, then so is C”, B says “If C is telling the truth, then A is lying”, and C says “It is not the case that all three of us are telling the truth.” Using propositional variables a, b, and c to represent the truth of the statements of A, B, and C respectively, we can represent the problem by the three premises a ↔ ((a ∧ b) → c), b ↔ (c → ¬a), and c ↔ ¬(a ∧ b ∧ c). Determine the conclusion as a conjunction of three literals, and give a deductive sequence proof of this conclusion from the premises.

(10 points) Problem 1.8.3

Suppose that you have proved 0 from the premise P ∧ ¬Q. Show how you can use Proof By Cases and this proof to construct a direct proof of P → Q.

(12 points) Problem 1.8.4

√

Here you will complete a famous proof, known to the ancient Greeks, that the number 2

is irrational (that it cannot be expressed as p/q where p and q are naturals). Suppose that √

2 = p/q and that the fraction p/q is in lowest terms. Then by arithmetic, p² = 2q². Now

use Proof By Cases, where the new proposition is “p is even”. Derive a contradiction in each

√

case. amd argue using Proof By Contradiction that 2 is irrational. (Remember, as we will show formally in Chapter 3, that a natural is even if and only if its square is even.)

(12 points) Problem 1.10.1

Let Σ = {a, b}. Using the same string predicates defined in Exercises 1.10.2 and 1.10.3 above, express the following sets in set builder notation (that is, determine their predicate form):

1. {aa, bb}.

2. {a, aa, aaa, aba, aaaa, aaba, abaa, abba, aaaaa, aaaba, aabaa, aabba, · · · }.

3. {aaaa, aaab, abaa, abab, baba, babb, bbba, bbbb}. (You will also need the concatenation op-eration here.)

Extra credit:

(10 points) Problem 2.3.3

Let A and B be two types such that A is a proper subset of B (so that B contains all the elements of A plus at least one other element). Let P be a unary predicate on A, and let Q be a unary predicate on B. Suppose that ∀a : ∀b : P (a) → Q(b) is true. Which of the following four statements is guaranteed to be true? For each statement, explain why it is always true or give an example where it is false. (Hint: Consider the case where A is empty.)

1. (∀a : P (a)) → (∀b : Q(b))

2. (∀b : Q(b)) → (∀a : P (a))

3. (∃a : P (a)) → (∃b : Q(b))

4. (∃b : Q(b)) → (∃a : P (a))

3