# De Morgan's Law

Shackleford
I'm reasonably certain about (b) since I found a proof online. However, I'm not sure about (a) and the part where I have "for all n." Sorry for the poor quality.

http://i111.photobucket.com/albums/n149/camarolt4z28/Untitled.png?t=1296529661

http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110131_210113.jpg?t=1296529704 [Broken]

Last edited by a moderator:

## Answers and Replies

Mentor
I'm pretty sure that you are intended to use induction on these.

Shackleford
I'm pretty sure that you are intended to use induction on these.

I don't know how that would work in this case. It's all new to me.

What's wrong with the way I did it?

Homework Helper
I'm pretty sure that you are intended to use induction on these.

Why? You don't know the index set is even ordered. And you don't need to.

Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

Shackleford
Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

I'm not familiar with induction.

Homework Helper
Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

Last edited:
I'm not familiar with induction.

Induction is basically a way to prove things by "domino theory".

When I say domino theory I mean that you prove it for the first case, then you assume its true for k cases and prove it for the (k+1)th case.

So in your example we know its true for NOT(A and B) = NOT(A) OR NOT(B).

Now assume its true for n = k

So lets say you have NOT(A(0) and A(1) and A(2) and ... and A(N-1)) = NOT(A(0)) or NOT(A(1)) or ... or NOT(A(N-1)).

Lets say LHS = B, RHS = C

D = NOT(NOT(B) AND A(N)) = NOT(NOT(B)) or NOT(A(N)) = B OR NOT(A(N)

But B = C so

D = B OR NOT(A(N)) = C OR NOT(A(N)) = RHS for term k + 1

Proved for term k+1 assuming true for term k.

Therefore proven by induction.

If you want to know more about induction pick up a book on discrete mathematics or if you are keen enrol in a course in discrete mathematics.

This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

I said induction is a good tool. I did not say induction is the only tool. With mathematics there will for most problems be more than one method that yields the correct solution.

Homework Helper
I said induction is a good tool. I did not say induction is the only tool. With mathematics there will for most problems be more than one method that yields the correct solution.

What's wrong the original proof? Why do you need induction?

Mentor
Why? You don't know the index set is even ordered. And you don't need to.
The index looks to be 1, 2, 3, ..., n.

Mentor
This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

How do you get an uncountable infinity of sets?
$$(\cup_n A_n)^C = \cap_n A_n^C$$

Homework Helper
How do you get an uncountable infinity of sets?
$$(\cup_n A_n)^C = \cap_n A_n^C$$

I'm saying it wouldn't make any difference to the proof if there were.

The index looks to be 1, 2, 3, ..., n.

n ISN'T the number of sets. It's an index. That's why it's a subscript on the A. And the index looks to me like n is an element of 1,2,3,... reading between the lines on the problem statement. I.e. perhaps there are an infinite number. Perhaps there aren't. It doesn't matter to the proof. Just because you see 1,2,3... in a problem doesn't mean it's solved by induction.