Prove De Morgan's LAw


by franz32
Tags: morgan, prove
franz32
franz32 is offline
#1
Jun15-04, 09:43 AM
P: 134
I hope someone can help me prove one of De Morgan's Law:

(A intersection B)' = A' U B'
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
AKG
AKG is offline
#2
Jun15-04, 12:47 PM
Sci Advisor
HW Helper
P: 2,589
Quote Quote by franz32
I hope someone can help me prove one of De Morgan's Law:

(A intersection B)' = A' U B'
I can suggest a way to prove it, although I've never formally done any of this stuff so I don't know if this approach is "acceptable." Anyways, it's a proof by contradiction. Assume the equation were false. That would mean that there exists and element, x, such that it is not in (A' U B') but is in (A intersection B)'. Now, if it is not in (A' U B'), then it is not in A' and it is not in B' (if it were in either of those, it would be in A' U B'). So, if it is not in A', it is in A, and if it is not in B', it is in B. Therefore, this element, x, is in A and it is in B, so it is in (A intersection B). Therefore, it is not in (A intersection B)'. This contradicts, the assumption, therefore the equation must be right.
jdavel
jdavel is offline
#3
Jun15-04, 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.

Tom Mattson
Tom Mattson is offline
#4
Jun15-04, 01:00 PM
Emeritus
Sci Advisor
PF Gold
Tom Mattson's Avatar
P: 5,540

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={x|xεA or xεB}

Take the complement:

(A U B)'={x|xε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.
AKG
AKG is offline
#5
Jun15-04, 01:03 PM
Sci Advisor
HW Helper
P: 2,589
Proposition: [itex](A \cap B)' \subseteq (A' \cup B')[/itex]

Proof: (by contradiction)
Assume: [itex](A \cap B)' \not\subseteq (A' \cup B')[/itex]
[itex]\therefore \exists x \mbox{ such that } x \in (A \cap B)',\ x \notin (A' \cup B')[/itex]
[itex][x \notin (A' \cup B')] \Longrightarrow (x \notin A' \wedge x \notin B')[/itex]
[itex]\Longrightarrow (x \in A \wedge x \in B)[/itex]
[itex]\Longrightarrow [x \in (A \cap B)][/itex]
[itex]\Longrightarrow [x \notin (A \cap B)'][/itex]
[itex]\oplus \mbox{ (contradiction)}[/itex]
[itex]\therefore (A \cap B)' \subseteq (A' \cup B')\ \dots \ (1)[/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]
[itex]\therefore \exists x \mbox{ such that } x \notin (A \cap B)',\ x \in (A' \cup B')[/itex]
[itex][x \notin (A \cap B)'] \Longrightarrow [x \in (A \cap B)][/itex]
[itex]\Longrightarrow (x \in A \wedge x \in B)[/itex]
[itex]\Longrightarrow [x \notin A' \wedge x \notin B')][/itex]
[itex]\Longrightarrow [x \notin (A' \cup B')][/itex]
[itex]\oplus \mbox{ (contradiction)}[/itex]
[itex]\therefore (A' \cup B') \subseteq (A \cap B)'\ \dots \ (2)[/itex]
By (1) and (2), [itex](A' \cup B') = (A \cap B)'[/itex]
franz32
franz32 is offline
#6
Jun15-04, 11:09 PM
P: 134
Oh.. I see

Well, thanks for all your helps. I got it.
Gokul43201
Gokul43201 is offline
#7
Jun16-04, 02:39 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Draw a Venn Diagram.

It becomes painfully obvious.
Tom Mattson
Tom Mattson is offline
#8
Jun16-04, 08:03 PM
Emeritus
Sci Advisor
PF Gold
Tom Mattson's Avatar
P: 5,540
Quote Quote by Gokul43201
Draw a Venn Diagram.

It becomes painfully obvious.
Ha! The last time I responded to a request for help in proving a set-theroetic statement, I said the same thing. But the poster said it wasn't allowed, so I did it "the hard way" this time.

It's true though, franz32, you can show that both statements have the same Venn diagram, and are therefore equivalent.
fourier jr
fourier jr is offline
#9
Jun17-04, 03:38 PM
P: 943
Quote Quote by franz32
I hope someone can help me prove one of De Morgan's Law:

(A intersection B)' = A' U B'
I haven't really looked at the LATEX stuff, so I'll have to do it with words.
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)
1+1=1
1+1=1 is offline
#10
Jun24-04, 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.
Tom Mattson
Tom Mattson is offline
#11
Jun24-04, 05:07 PM
Emeritus
Sci Advisor
PF Gold
Tom Mattson's Avatar
P: 5,540
Quote Quote by 1+1=1
doing a truth table would be difficult,
It's no more difficult than the Venn diagram. Once you reduce DeMorgan's law for sets to DeMorgan's law for logic, all you have to do is show that ~(p and q) has the same truth table as (~p or ~q).

~(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.
jonsina
jonsina is offline
#12
Mar23-10, 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
Fredrik
Fredrik is offline
#13
Mar24-10, 07:03 AM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 8,989
Quote Quote by jonsina View Post
which font should i use so that i can type the symbols
The best way is to use LaTeX. Click the quote button in post #5 to see how AKG did it. (tex tags will produce slightly larger output than itex tags). You will like the LaTeX codes \lnot,\lor and \land. There are lots of lists of LaTeX symbols online that you can find using Google. I also recommend that you use the preview button to check that everything looks OK before you submit your post.
Aryabatta
Aryabatta is offline
#14
Aug27-11, 06:46 PM
P: 1
Venn Diagrams for De Morgan's Law at
http://guideocom.blogspot.com/2011/0...ms-proofs.html
phinds
phinds is offline
#15
Aug27-11, 08:43 PM
PF Gold
phinds's Avatar
P: 5,674
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