## Proving One of Demorgan's Law

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jewish_scientist
Posts: 895
Joined: Fri Feb 07, 2014 3:15 pm UTC

### Proving One of Demorgan's Law

I know that this is technically not a math question, but I am way to annoyed to care. My logic homework is P /\ Q |- -( -P v -Q)

This is how far I got:

1 . . . 1 . . . P /\ Q . . . . . . A
1 . . . 2 . . . P . . . . . . . . 1/\E
1 . . . 3 . . . Q . . . . . . . . 1/\E
4 . . . 4 . . . -P v -Q . . . . . A
5 . . . 5 . . . -P . . . . . . . . A

For the life of me I cannot figure out where to go from here.

Spoiler:
I imagine that there is a million conventions on how to format a proof, so this is the one we are using:

Assumptions line rests on . . . . . Line number . . . . . Line . . . . . Lines this line is derived from + rule used

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5393
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Somerville, MA
Contact:

### Re: Proving One of Demorgan's Law

Writing out the table for the four cases is likely your best angle.
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

jewish_scientist
Posts: 895
Joined: Fri Feb 07, 2014 3:15 pm UTC

### Re: Proving One of Demorgan's Law

I know, but I am not allowed to use truth tables. I have to derive it.

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5393
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Somerville, MA
Contact:

### Re: Proving One of Demorgan's Law

If you can't assume that truth tables are a valid proof mechanism, include a chapter 0 page in your problem set where you prove that they are valid.
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Proving One of Demorgan's Law

What are your available rules? I'm assuming A stands for "Assumed", but why are you assuming (-P v -Q)?
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

ATCG
Posts: 470
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

### Re: Proving One of Demorgan's Law

It looks like you are writing a natural deduction proof (ala Gentzen.)[/Clippy] If so, you are on the right track.

Cauchy wrote:...why are you assuming (-P v -Q)?

@j_s, take Cauchy's question seriously. In fact, turn it into two questions:
• How do you intend to discharge this assumption? Hint: What will the last two lines of your proof be, and what is the inference rule by which you arrive at the very last line? I suspect you know the answer to this question, or you would not have introduced the assumption in the first place.
• I'm guessing that what is hanging you up involves the answer to my second question: What inference rule does ¬P v ¬Q enable? Big hint: Think disjunction. Furthermore, think about how that inference rule leads to the next-to-the-last line of your proof.
Believe it or not, you've collected all the pieces. Now it's just a matter of putting them together.

ADDENDUM: The first three chapters of Logic and Proof are a good introduction to natural deduction and section 3.1 lists the applicable inference rules. Proof formatting differs from that in the original post ("I imagine that there is a million conventions on how to format a proof...", imagines j_s, correctly), but the mechanics of inference ought to be equivalent.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

Return to “Mathematics”

### Who is online

Users browsing this forum: No registered users and 6 guests