• Support PF! Buy your school textbooks, materials and every day products Here!

De Morgan's Law

  • #1
1,654
2
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

  • #2
33,513
5,195
I'm pretty sure that you are intended to use induction on these.
 
  • #3
1,654
2
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?
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #5
chiro
Science Advisor
4,790
131
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.
 
  • #6
1,654
2
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.
 
  • #7
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • #8
chiro
Science Advisor
4,790
131
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.
 
  • #9
chiro
Science Advisor
4,790
131
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.
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #11
33,513
5,195
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.
 
  • #12
33,513
5,195
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?
[tex](\cup_n A_n)^C = \cap_n A_n^C[/tex]
 
  • #13
Dick
Science Advisor
Homework Helper
26,258
618
How do you get an uncountable infinity of sets?
[tex](\cup_n A_n)^C = \cap_n A_n^C[/tex]
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.
 

Related Threads on De Morgan's Law

  • Last Post
Replies
13
Views
943
  • Last Post
Replies
0
Views
4K
Replies
24
Views
3K
Replies
1
Views
7K
Replies
1
Views
2K
Replies
1
Views
4K
Replies
14
Views
59K
  • Last Post
Replies
1
Views
874
Replies
3
Views
12K
Top