Proof of DeMorgan's Laws


by ranjha
Tags: demorgan, laws, proof
ranjha
ranjha is offline
#1
Oct25-05, 12:06 PM
P: 5
Can someone tell me how to prove DeMorgan's Laws using the basic rules?

~(A & B) = ~A v ~B

Please help
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
honestrosewater
honestrosewater is offline
#2
Oct25-05, 12:18 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Welcome to PF, ranjha!

Well, there's more than one set of rules and more than one proof. Is this homework, or are you just curious? Do you have some rules in mind?
ranjha
ranjha is offline
#3
Oct25-05, 12:41 PM
P: 5
This is homework...we are expected to know this. It's just that we have been taught a certain number of rules of inference. So the examples I have seen don't make sense to me. We have to know how to prove his Law by using the rules we have learned: Modus Ponens, Tollens, Simplification, Conjunction, Disjunction, Conjunctive and Disjunctive Arguments, Conditional Proofs, Chain Rule, Dilemmas, Reductio, Double Negation, Transposition, and Material Implication. These are the only ones we have learned so far and I am completely lost as to how to start. Please help.

honestrosewater
honestrosewater is offline
#4
Oct25-05, 01:11 PM
PF Gold
honestrosewater's Avatar
P: 2,330

Proof of DeMorgan's Laws


Quote Quote by ranjha
This is homework...we are expected to know this. It's just that we have been taught a certain number of rules of inference. So the examples I have seen don't make sense to me. We have to know how to prove his Law by using the rules we have learned: Modus Ponens, Tollens, Simplification, Conjunction, Disjunction, Conjunctive and Disjunctive Arguments, Conditional Proofs, Chain Rule, Dilemmas, Reductio, Double Negation, Transposition, and Material Implication. These are the only ones we have learned so far and I am completely lost as to how to start. Please help.
Well, you are given no premises, so you will have to use conditional proof or reductio, right?

Try (~A v ~B) => ~(A & B).

1) ~A v ~B [assumption]
2)) A & B [assumption -- for reductio]
3)) can you change (1) into an implication?

Oh, sorry, an implication is another name for a conditional: p -> q
ranjha
ranjha is offline
#5
Oct25-05, 01:26 PM
P: 5
ok:

1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)

is this what you mean?? but where do I go from here?
honestrosewater
honestrosewater is offline
#6
Oct25-05, 02:11 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by ranjha
ok:
1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)
is this what you mean?? but where do I go from here?
Yes, that's what I meant.
Do you understand why I made those assumptions? I want to prove

(~A v ~B) => ~(A & B)

So I assume (~A v ~B) and try to derive ~(A & B). I will try to derive ~(A & B) by assuming (A & B) and trying to derive a contradiction so that I can infer ~(A & B) by reductio. You just want to derive a contradiction -- (A & ~A) or (B & ~B). Use simplification and modus ponens.
ranjha
ranjha is offline
#7
Oct25-05, 02:27 PM
P: 5
ok I kind of understand what you are trying to do. I get that you are going to use Reductio to prove the law. But can you please get me started? I don't know what the next step should be.

1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)
4)) A (2 simplification)
5)) ~B (3,4 MP)
6)) B (2 simplification)
7)) B & ~B (5,6 Conjunction)
8)) ~B (7 RA)
9)) how would you go from here? and is this right so far?
honestrosewater
honestrosewater is offline
#8
Oct25-05, 02:55 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by ranjha
ok I kind of understand what you are trying to do. I get that you are going to use Reductio to prove the law. But can you please get me started? I don't know what the next step should be.
1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)
4)) A (2 simplification)
5)) ~B (3,4 MP)
6)) B (2 simplification)
7)) B & ~B (5,6 Conjunction)
That's right, except that I forgot to nest the first assumption.

1)) ~A v ~B (assume)
2))) A & B (assume)
3))) A --> ~B (1 M Implication)
4))) A (2 simplification)
5))) ~B (3,4 MP)
6))) B (2 simplification)
7))) B & ~B (5,6 Conjunction)

(7) allows you to infer

8)) ~(A & B) [2-7, reductio ad absurdum]

Just apply conditional proof and you're done with this half. You still need to prove the other half of the equivalence:

~(A & B) => (~A v ~B)

How would you begin?


Register to reply

Related Discussions
Demorgan's Theorem General Math 3
Demorgan's Theorem Engineering, Comp Sci, & Technology Homework 5
deMorgan's Laws Calculus & Beyond Homework 1
Demorgan's Theorem Problem Engineering, Comp Sci, & Technology Homework 4
DeMorgan's theorem, What does it logically mean? I missed it on a test! Calculus & Beyond Homework 3