Mathematics for Computer Science

Chapter 4 Mathematical Data Types100

using the fact that the propositional formula.PANDQ/OR.PANDQ/is equivalent
toP.
State a similar propositional equivalence that would justify the key step in a proof
for the following set equality organized as a chain of iff’s:

A\B\CDA[.BA/[C:

(You arenotbeing asked to write out an iff-proof of the equality or to write out
a proof of the propositional equivalence. Just state the equivalence.)

Problems for Section 4.2

Homework Problems

Problem 4.12.
Prove that for any setsA,B,C, andD, if the Cartesian productsABandCD
are disjoint, then eitherAandCare disjoint orBandDare disjoint.

Problem 4.13. (a)Give a simple example where the following result fails, and
briefly explain why:
False Theorem.For setsA,B,C, andD, let

LWWD.A[B/.C[D/;

RWWD.AC/[.BD/:

ThenLDR.

(b)Identify the mistake in the following proof of the False Theorem.

Bogus proof.SinceLandRare both sets of pairs, it’s sufficient to prove that
.x;y/ 2 L !.x;y/ 2 Rfor allx;y.

The proof will be a chain of iff implications:

.x;y/ 2 R

iff .x;y/ 2 .AC/[.BD/

iff .x;y/ 2 AC, or.x;y/ 2 BD

iff (x 2 Aandy 2 C) or else (x 2 Bandy 2 D)

iff eitherx 2 Aorx 2 B, and eithery 2 Cory 2 D

iff x 2 A[Bandy 2 C[D

iff .x;y/ 2 L.