CSE311-Homework 4 Solved

1.     Cat On a Hot Tin Proof
Let the domain of discourse be foods, pets (including Garfield and Odie), and days of the week. We define the predicates Cat(x), Dog(x), and Lasagna(x) to mean that x is a cat, a dog, or a lasagna, respectively. We also define the predicates Loves(x,y) and Hates(x,y) to mean that x loves y and x hates y, respectively.

Prove the following claim:

∀x(Lasagna(x) →∃y (Cat(y)∧ Loves(y,x)∧ Hates(y, Monday)∧¬∀z (Dog(z) → Hates(z,y))))

Common-knowledge facts about about Garfield and Odie do not require any proof and may simply be stated. If you are unfamiliar with that comic, the Wikipedia article may be helpful.

2.     Teacher’s Set
Let A, B, and C be sets. Prove or disprove the following claims.

For the proofs, you may not cite the Meta Theorem. However, you should feel free to follow it as a template for how to write your own proof.

 

(a)     A ∩(B ∩ A) = A

(b)    (B \ A)∩(C \ A) = (B ∪ C)\ A

 

 

(c)     (B ∪ A)∩(B ∪ C) = B ∪(C ∪ A)

3.     April Showers Bring May Powers
Let S and T be sets. Prove or disprove the following claims.

(a)     P(S ∪ T) = P(S)∪P(T)∪P(S ∩ T)

(b)    P(S ∩ T) = {∅}∪(P(S)\P(S \ T))

(c)     P(S ∩ T) = P(S)∩P(T)

1

4.     Keeping Up With the Cartesians
Let A, B, and C be sets.

(a)      Prove that, if B ⊆∅, then A × B = B × C.

(If it helps, recall that ∅ is defined by the fact that ∀x(x /∈∅) holds.)

(b)    Prove that, if B 6⊆∅ and A × B ⊆ B × C, then A ⊆ B.

5.     A Good Prime Was Had By All
Prove that, if p > 2 is prime and p 6≡ 0 (mod 3), then p mod 12 ∈{1,5,7,11}.

Hint 1: Note that p mod 12 has only 12 possible values (0...11).

Hint 2: Consider the proof strategies discussed in lecture.

6.     Extra Credit: Match-22
In this problem, you will show that given n red points and n blue points in the plane such that no three points lie on a common line, it is possible to draw line segments between red-blue pairs so that all the pairs are matched and none of the line segments intersect. Assume that there are n red and n blue points fixed in the plane.

 

A matching M is a collection of n line segments connecting distinct red-blue pairs. The total length of a matching M is the sum of the lengths of the line segments in M. Say that a matching M is minimal if there is no matching with a smaller total length.

Let IsMinimal(M) be the predicate that is true precisely when M is a minimal matching. Let HasCrossing(M) be the predicate that is true precisely when there are two line segments in M that cross each other.

Give an argument in English explaining why there must be at least one matching M so that IsMinimal(M) is true, i.e.

∃MIsMinimal(M))

Give an argument in English explaining why

∀M(HasCrossing(M) →¬IsMinimal(M))

Then, use the two results above to give a proof of the statement:

∃M¬HasCrossing(M).