Can't prove generalized De Morgan's Law

In summary, the given statement regarding set B and its indexed family of subsets of set S shows that the complement of the union of the subsets is equal to the intersection of the complements of the subsets. This can be shown by considering an element a in the intersection of the complements and an element in the union's complement, and showing that they are both contained in each other.
  • #1
john562
8
0

Homework Statement


Let B be a non-empty set, and supose that {Sa : a[tex]\in[/tex]B} is an B- indexed family of subsets of a set S. Then we have,
([tex]\cup[/tex] a\in B Sa)c = [tex]\bigcapa\in B[/tex] Sac.


Homework Equations





The Attempt at a Solution


I tried to show that the two were both subsets of each other, but I'm not sure how to do that.
 
Physics news on Phys.org
  • #2
Suppose [tex]a\in \bigcap S_\alpha^c[/tex]. Then a is in all the sets [tex]S_\alpha ^c[/tex], and so it is not contained in any of [tex]S_\alpha[/tex]. Therefore, it is not contained in their union (by definition). It is therefore contained in union's complement.

Suppose a is in union's complement. No [tex]S_\alpha[/tex] contains a, so all the [tex]S_\alpha^c[/tex]'s contain a. Therefore, a is in their intersection.
 

FAQ: Can't prove generalized De Morgan's Law

What is De Morgan's Law?

De Morgan's Law is a fundamental principle in propositional logic that states that the negation of a conjunction (and) is logically equivalent to the disjunction (or) of the negations of the individual propositions. Similarly, the negation of a disjunction is logically equivalent to the conjunction of the negations of the individual propositions.

What is generalized De Morgan's Law?

Generalized De Morgan's Law is an extension of the original law that applies to more than two propositions. It states that the negation of a disjunction (or) of multiple propositions is logically equivalent to the conjunction (and) of the negations of those propositions. Similarly, the negation of a conjunction (and) of multiple propositions is logically equivalent to the disjunction (or) of the negations of those propositions.

Why is it important to prove generalized De Morgan's Law?

Proving generalized De Morgan's Law is important because it provides a formal proof of its validity and allows for its use in more complex logical expressions. It also helps to establish a deeper understanding of propositional logic and its principles.

What are some practical applications of generalized De Morgan's Law?

Generalized De Morgan's Law has practical applications in fields such as computer science, mathematics, and engineering. It can be used to simplify logical statements, optimize computer algorithms, and prove theorems in mathematics.

What are some common misconceptions about generalized De Morgan's Law?

One common misconception is that it only applies to binary (two-valued) logic. In reality, it can be applied to any number of propositions. Another misconception is that it is only applicable to negations of conjunctions and disjunctions, when in fact it can also be applied to other logical operators such as implication and equivalence.

Similar threads

Back
Top