1
$\begingroup$

I have some question about DFA Language properties.

Does closure under intersection and complementation imply closure under union?

Does closure under intersection and union imply closure under complementation?

Thank you

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to CS.SE! What are your thoughts? Have you tried to prove those claims? If so, what do your attempts look like, and at what stage did you get stuck? These look like exercise-style problems. While we're happy to help you understand concepts, doing exercises for you probably won't achieve that. $\endgroup$
    – D.W.
    Jan 28, 2017 at 13:04
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Jan 28, 2017 at 14:50

1 Answer 1

3
$\begingroup$

Does closure under intersection and complementation imply closure under union?

This is immediate from De Morgan's laws.

Does closure under intersection and union imply closure under complementation?

This one is slightly trickier. The answer is no.

Both intersection and union are what is called "monotone". That means that, if you make $X$ or $Y$ bigger then $X\cup Y$ and $X\cap Y$ can't get smaller. By induction, you can prove that any operator defined using only intersections and unions must also be monotone. But complement is not monotone: when you make $X$ bigger, its complement definitely gets smaller. So complement cannot be defined using only intersection and union.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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