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

~[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

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search