5
$\begingroup$

Given three sets: $X, Y, Z$ and the two set operations: union and intersection. What is the maximum length of a 'formula' which is not reducible to a shorter formula.

Eg. the formula $(X \cap Y) \cup X$ can be reduced to the formula $X$.

However the formula $Y \cap(X \cup Z)$ is not reducible in length.

I've been thinking about this problem for a while now, but can't seem to get past a length of 3. (the length being the amount of set symbols).

$\endgroup$
3
+50
$\begingroup$

All possible combinations (I think):

$X$

$Y$

$Z$

$X \cup Y$

$Y \cup Z$

$X \cup Z$

$X \cap Y$

$Y \cap Z$

$X \cap Z$

$(X \cap Y) \cup Z$

$(Y \cap Z) \cup X$

$(Z \cap X) \cup Y$

$(X \cup Y) \cap Z$

$(Z \cup X) \cap Y$

$(Y \cup Z) \cap X$

$X \cap Y \cap Z$

$X \cup Y \cup Z$

$\{(X \cup Z) \cap Y\} \cup (X \cap Z)$

Venn says:

enter image description here

$\endgroup$
2
  • $\begingroup$ Note that by using only union and intersection operations it is impossible to get rid of the $X \cap Y \cap Z$ region. $\endgroup$ – Maazul Apr 30 '13 at 20:21
  • $\begingroup$ Thank you very much! This is a great help! $\endgroup$ – 13Tazer31 May 1 '13 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.