Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Main Connectives in a Proof


Date: 10/28/2001 at 22:02:09
From: Elizabeth
Subject: Logic

Given
1. [~A^ ~(D^E)] ->(B -> ~D)
2. ~(D^E) ^ ~R
3. E -> F
4. ~A V (D^E)
5. ~(D^E) -> (B V E)

Prove
~D V F

^ means "and"
-> means "then"
V means "or"
~ means "not"

This is what I've done so far:

Statements                     Reasons
 1. [~A^ ~(D^E)] ->(B -> ~D)   1. Given
 2. ~(D^E) ^ ~R                2. Given
 3. E -> F                     3. Given
 4. ~A V (D^E)                 4. Given
 5. ~(D^E) -> (B V E)          5. Given
 6. (~D V ~E) ^ ~R             6. (5)De Morgans
 7. (~D V ~E)                  7. (6) Law of simplification
 8. ~R                         8. (6) Law of simplification
 9. ~(D^E)->(B->~D)            9. (1) Law of simplification
10.  ~A -> (B->~D)            10. (1) Law of simplification
11. ~A                        11. (4,7)Law of Disjunctive inference
12. (B->~D)                   12. (10, 11) Law of Detachment


Date: 10/29/2001 at 16:59:40
From: Doctor Achilles
Subject: Re: Logic

Hi Elizabeth,

Thanks for writing to Dr. Math.

Great start on the proof! You did exactly the right thing with lines 7 
and 8.

One thing to be careful about when doing proofs is not to apply rules 
to parts of a line, but only to the entire line. For example, you 
cannot go from:

 1. [~A ^ ~(D^E)] -> (B -> D)

to

10. ~A -> (B -> D)

Let's take a simpler example to see why. Going from:

 1.  P ^ Q -> R

to

 2.  P -> R

is like going from the English sentence "IF it is freezing out AND 
there are rain clouds THEN it will snow" to "IF it is freezing out 
THEN it will snow."  This is not a valid inference, because there have 
to be clouds before it can snow, no matter how cold it gets.

Similarly, you can't get your line 11 either.

The way I always approach proofs is looking for what I've been taught 
to call the "main connective" or the "main logical symbol."

You can identify the main connective by looking at the structure of 
the sentence. Most sentences are made by taking two smaller sentences 
and sticking a logical symbol between them.

For example, the sentence:

1. [~A ^ ~(D ^ E)] -> (B -> ~D)

is made by sticking a -> between the sentence A ^ ~(D ^ E) and the 
sentence B -> ~D.  The -> in the middle is therefore the main 
connective. BE CAREFUL, because the subsentence B -> D also has a -> 
in it, but this -> is NOT the main connective, the main connective is 
the -> that connects the two big sentences.

What is the main connective of this?

2. ~(D^E) ^ ~R

Well, that sentence is made by taking a ~(D ^ E) and combining it with 
a ~R.  In this case they're combined using an ^.  (Notice again that 
the ^ in the subsentence ~(D^E) is NOT the main connective).

I said before that MOST sentences are made by taking two smaller 
sentences and sticking a logical symbol between them. The only 
exception is when the main connective is ~. Take a look at this 
made-up sentence:

    ~[P v (F -> ~R)]

This sentence is made by starting with P v (F -> ~R) and just sticking 
a ~ on the whole thing. The main connective is therefore ~. (Once 
again, be careful to notice that the main connective is the ~ in front 
of the whole thing and it is not the ~ that's just in front of the R.)

One more made up sentence:

    ~P v (F -> ~R)

Notice here tha because there are NO parentheses around the whole 
sentence, the ~" in front only applies to the P and DOES NOT apply to 
the entire sentence. The main connective here is therefore the v that 
connects ~P with F -> R.

So what's the big deal about main connectives? Here is Dr. Achille's 
big number one MOST IMPORTANT RULE ABOUT DOING PROOFS:

  The ONLY thing you can work on when you're doing a proof 
  is the main connective of a sentence.

This means:

  When you're working on a proof, the first thing to do is 
  identify the main connective and figure out what you can do with it.

Here's a list of all the things you can do with a proof:

  When you are GIVEN a sentence whose main connective is ^, you are 
  entitled to each part by itself.

  When you are GIVEN a sentence whose main connective is <->, you  
  should find ONE of the two parts, and that entitles you to the 
  other.

  When you are GIVEN a sentence whose main connective is ->, you 
  should find the part BEFORE the -> and then you are entitled to the 
  part after.

  (This one is a little tricky): When you are GIVEN a sentence whose 
  main connective is v, you should first assume that the part before 
  the v is true, then derive some new sentence X, then assume that the 
  part after the v is true and derive THE SAME sentence X, and that 
  entitles you to X.

  When you are GIVEN a sentence whose main connective is ~, you can 
  usually apply one of these rules to it:

  DeMorgan's rule 1:

     ~(p ^ q)
     --------
      ~p v ~q

  DeMorgan's rule 2:

     ~(p v q)
     ---------
      ~p ^ ~q

  Disjunctive syllogism (DS):

     (p v q)
     ~p
     -------
      q

  Modus tollens:
     (p -> q)
     ~q
     ---------
      p

  (When using these rules, you can substitute entire subsentences for 
   the p's and q's, as long as you don't mess with their internal 
   structure while you're doing it.)

Here's a list of strategies for proving something:

  When you're trying to FIND a sentence whose main connective is ^, 
  you need to derive both parts separately.

  When you're trying to FIND a sentence whose main connective is <->, 
  you need to assume the left side, then derive the right, THEN assume 
  the right and derive the left.

  When you're trying to FIND a sentence whose main connective is ->, 
  you should assume the LEFT, then derive the RIGHT.

  When you're trying to FIND a sentence whose main connective is v, 
  you just need to derive one part or the other, it doesn't matter 
  which, and then you get the whole sentence for free.

  When you're trying to FIND a sentence whose main connective is ~, 
  you should assume the rest of the sentence without the ~ and then 
  derive a contradiction. For instance, one way to prove ~(p ^ ~p):

     1)  p ^ ~p          Assumption, for contradiction
     2)  p               simplification on the ^ in 1
     3)  ~p              simplification on the ^ in 1

  Since 2 and 3 contradict each other, you are entitled to conclude 
  that the assumption is false, and therefore that ~(p ^ ~p) is true.

That's a lot of information to get started on. Let's look at what 
you're given now for the problem:

 1. [~A^ ~(D^E)] ->(B -> ~D)   1. Given

The main connective here is ->, so we're going to want to find the 
first part ~A ^ ~(D^E) so that we can get the second part. We don't 
have any way to find the first part yet, so for now we'll just keep in 
the back of our heads that we want to find it.

 2. ~(D^E) ^ ~R                2. Given

The main connective here is ^, so you did the right thing by 
simplifying.

 3. E -> F                     3. Given

Just as in line 1, we want E, but we don't have it yet, so we'll be on 
the lookout.

 4. ~A V (D^E)                 4. Given

It's tricky to work with v sentences. Maybe we'll get lucky and be 
able to apply a disjunctive syllogism to this one. We'll keep our eyes 
open for A or for ~(D^E).

 5. ~(D^E) -> (B V E)          5. Given

We don't have ~(D^E) yet, but just as in 1 and 3, we'll keep our eyes 
peeled.

The easiest thing to work with looks like line 2, so let's start 
there.

 6. ~R                         6. Simplification of 2

 7. ~(D^E)                     7. Simplification of 2

Hold on, we were on the lookout for ~(D^E). (Check back at line 5).  
So now what?  Well we have ~(D^E) (7) and we have ~(D^E) -> (BvE) (5), 
so that means we are entitled to:

 8. B v E                      8. Detachment on 5 and 7

Look back at number 4; we can ALSO use ~(D^E) for a disjunctive 
syllogism on 4.

 9. ~A                         9. DisSyll on 4 and 7

Now check back at line 1. We were looking for ~A ^ ~(D^E), and we can 
get it now by combining line 7 with line 9.

10. ~A ^ ~(D^E)               10. Combining 7 and 9

So now we are entitled to the second part of line 1.

11. B -> ~D                   11. Detachment on 1 and 10

What use is this line? Well, if we had B, we could get ~D, and then 
getting to ~D v F (which is what we're after) would be easy. The only 
other places B appears is on lines 5 and 8. 5 is pretty ugly, but we 
might be able to do something with 8. The main connective of 8 is v, 
so we have to assume one side, derive a new sentence, then assume 
the other side and derive the same sentence again. If we can do that, 
then we can keep the sentence we derive.

12. B                         12. NEW ASSUMPTION

This combines nicely with 11.

13. ~D                        13. Detachment on 11 and 12 
                                 (still under assumption on 12)

This is very close to our goal, and introducing v is free. That is, 
since we have ~D we can make a new sentence ~D v X, where X is 
WHATEVER WE WANT. Since our goal here is ~D v F, let's make that.

14. ~D v F                    14. v introduction on 13
                                 (still under assumption on 12)

BUT WE'RE NOT DONE YET. We're still under the assumption on 12.  
Remember, we started with B v E and we agreed that we would just 
assume for a minute that B was true and then do some work from there, 
and then we would assume that E is true and work from there. Now it's 
time to finish the second part of our agreement.

15. E                         15. NEW ASSUMPTION

Where else do we see E? It's tied up in a lot of things, but take a 
look at line 3.  We've been waiting for E alone.

16. F                         16. Detachment on 3 and 15
                                 (still under assumption on 15)

Now, we can introduce F v X, where X is anything we want. We can also, 
using the same rule, introduce X v F, where X is anything we want.  
The goal of this whole proof has been to find ~D v F, so let's do 
that.

17. ~D v F                    17. v introduction on 16
                                 (still under assumption on 15)

Now, we fulfilled our agreement with line 8. We assumed each part and 
independently derived ~D v F. So we can now write:

18. ~D v F                    18. v removal line 8 (see sub-proofs on
                                  11-14 and on 15-17)

And thus we've derived our goal.

This is a lot of information to digest, and it requires thinking in 
new ways about logic.  If I went over anything too quickly or you have 
more questions, please write back. Good luck and I hope this was 
helpful.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/   


Date: 10/29/2001 at 21:30:14
From: Elizabeth
Subject: Re: Logic

I just wanted to say thank you very much.
    
Associated Topics:
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/