Proving One of Demorgan's Law

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Proving One of Demorgan's Law

Postby jewish_scientist » Thu Mar 29, 2018 4:35 pm UTC

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

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

Re: Proving One of Demorgan's Law

Postby doogly » Thu Mar 29, 2018 5:18 pm UTC

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: 893
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Proving One of Demorgan's Law

Postby jewish_scientist » Thu Mar 29, 2018 6:06 pm UTC

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

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

Re: Proving One of Demorgan's Law

Postby doogly » Thu Mar 29, 2018 7:49 pm UTC

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: 601
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Proving One of Demorgan's Law

Postby Cauchy » Fri Mar 30, 2018 12:00 am UTC

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.

User avatar
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

Postby ATCG » Sat Mar 31, 2018 7:23 am UTC

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 10 guests