All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Disjointification (Posted on 2004-04-04) Difficulty: 3 of 5
Given N possibly overlapping sets, give formulas that specify, using intersections and complements of the given sets, N disjoint sets with the same union as the original N sets. The sets that result are to be the same as the given sets in the case where the given sets are already disjoint.

See The Solution Submitted by Richard    
Rating: 3.1667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts thoughts | Comment 1 of 12

In the below please excuse the inability to get a CAP (intersection symbol) to look correct.

Let's call the sets A, B, C, etc.  Let represent intersection and ~ represent complement.

My first thought is to use just A, B~A, C~B~A, etc.

The only problem with this is that some of the sets may be empty.  This is OK if only one is empty, but if more than one is empty, then two of the sets are actually identical, and so we don't really have N sets--we have fewer.

Just to take a simple case, where I don't see any possibility of creating such a set of disjoint sets, take these 5 sets:
{1}, {2},{3},{4},{1,2},{3,4},{1,2,3,4}

That's seven sets.  We can't make seven disjoint sets with only those four elements.

Edited on April 4, 2004, 11:37 am
  Posted by Charlie on 2004-04-04 11:30:07

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information