Register to reply 
Prove De Morgan's LAw 
Share this thread: 
#1
Jun1504, 09:43 AM

P: 133

I hope someone can help me prove one of De Morgan's Law:
(A intersection B)' = A' U B' 


#2
Jun1504, 12:47 PM

Sci Advisor
HW Helper
P: 2,586




#3
Jun1504, 12:55 PM

P: 618

franz32,
Draw truth tables for both expressions. The expressions are equivalent if and only if their truth tables are the same. 


#4
Jun1504, 01:00 PM

Emeritus
Sci Advisor
PF Gold
P: 5,532

Prove De Morgan's LAw
S=A U B means, "Every element of S is either an element of A or an element of B (or of both)", and T=A ^ B means, "Every element of S is an element of both A and B".
We can write this using set builder notation: A U B={xxεA or xεB} Take the complement: (A U B)'={xxεA or εB}' Taking the complement of the statement on the RHS is the same as logically negating the "or" statement inside. Thus, (A U B)'={x~(xεA or xεB)} Now apply DeMorgan's law for logical connectives to fit this to the definition of A'^B'. You can justify the use of DeMorgan's law for logic by using truth tables. 


#5
Jun1504, 01:03 PM

Sci Advisor
HW Helper
P: 2,586

Proposition: [itex](A \cap B)' \subseteq (A' \cup B')[/itex]
Proof: (by contradiction) Assume: [itex](A \cap B)' \not\subseteq (A' \cup B')[/itex]Proposition: [itex](A' \cup B') \subseteq (A \cap B)'[/itex] Proof: (by contradiction) Assume: [itex](A' \cup B') \not\subseteq (A \cap B)'[/itex]By (1) and (2), [itex](A' \cup B') = (A \cap B)'[/itex] 


#6
Jun1504, 11:09 PM

P: 133

Oh.. I see
Well, thanks for all your helps. I got it. 


#7
Jun1604, 02:39 PM

Emeritus
Sci Advisor
PF Gold
P: 11,155

Draw a Venn Diagram.
It becomes painfully obvious. 


#8
Jun1604, 08:03 PM

Emeritus
Sci Advisor
PF Gold
P: 5,532

It's true though, franz32, you can show that both statements have the same Venn diagram, and are therefore equivalent. 


#9
Jun1704, 03:38 PM

P: 948

Let x be in (A intersection B)'. Then x is NOT in A intersection B <=> x not in A AND x not in B (use logical connectors, negations, etc) <=> x in A' OR x in B' <=> x in A' U B' That's one of them, hope it makes sense... you do the other one. (it's exactly the same) 


#10
Jun2404, 04:41 PM

P: 95

doing a truth table would be difficult, but a venn diagram would be the least painful way. i know you have the answer but still for further problems like this, venn is the way to go.



#11
Jun2404, 05:07 PM

Emeritus
Sci Advisor
PF Gold
P: 5,532

~(p and q) Since (p and q) is true only when (p,q)=(T,T), the negation is false only when (p,q)=(T,T). (~p or ~q) Since (p or q) is only false when (p,q)=(F,F), the statement (~p or ~q) is false only when (p,q)=(T,T). Since the two statements have the exact same truth table, they are equivalent. 


#12
Mar2310, 02:35 PM

P: 1

hello
can some one Plz explain to me my task: Prove De Morgan Law with the appropriate explanation were p and q are sentence meaning (proposition) ~(p ^ ( it s OR i dnt knw how to type on comuter) (if) (~p) ^ (~q) and which font should i use so that i can type the symbols and if some one will prove it i will be glad 


#13
Mar2410, 07:03 AM

Emeritus
Sci Advisor
PF Gold
P: 9,415




#14
Aug2711, 06:46 PM

P: 1

Venn Diagrams for De Morgan's Law at
http://guideocom.blogspot.com/2011/0...msproofs.html 


#15
Aug2711, 08:43 PM

PF Gold
P: 6,353

Not to sidetrack the thread, but when did DeMorgan's Theorem become DeMorgan's Law ? I had never heard it called that but when I googled it, I got about 59,000 hits for law, 49,000 for theorem. I don't think when I learned it about 50 years ago it was every called anything but DeMorgan's Theorem.



Register to reply 
Related Discussions  
How to proove De Morgan's Law for Logic?  Calculus & Beyond Homework  14  
Please prove this  Differential Geometry  6  
Siobhan Morgan's cosmology calculator has a new url  Cosmology  5  
Prove ( a + b + c )^2 <= 4( ab + bc + ca )  Calculus & Beyond Homework  13  
Prove the following:  Introductory Physics Homework  3 