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
_____________________________________________

Advanced Topics in Symbolic Logic

Date: 10/28/2002 at 19:41:21
From: Tim Huff
Subject: Symbolic Logic

I've searched all over your site and all over the Internet but I 
cannot find any unsolved proofs that I can just solve for fun. I was 
wondering if you knew any sites I could go to to find some. If not, 
could you give me a few to figure out?


Date: 10/29/2002 at 19:10:53
From: Doctor Achilles
Subject: Re: Symbolic Logic

Hi Tim,

Thanks for writing to Dr. Math.

All introductory types of logic problems (at least all that I've ever 
heard of) which can be solved, have already been solved by one of the 
thousands of people in the world who make their careers out of logic. 
I doubt if I can provide you with any unsolved symbolic logic 
problems. However, I can show you a few more advanced topics in logic, 
which get closer to unsolved problems.

If you haven't already done so, check out the rules of derivation that 
I use for symbolic logic, available at:

   A Crash Course in Symbolic Logic
   http://www.mathforum.com/dr.math/faq/symbolic_logic.html 

There are things you can do with symbolic logic that go beyond simply 
proving tautologies. For instance, can you construct a proof that 
every sentence you derive using the rules of derivation is in fact a 
tautology? For an even more difficult challenge: can you prove that 
every tautology is derivable using these rules?

Additionally, symbolic logic is just the beginning. There are many 
more places to go. You can pick up a logic text. The book I learned 
with was _The Logic Book_ by Merrie Bergmann, but there are many texts 
available, and any of them would be helpful. They range in difficulty; 
_The Logic Book_ is a decent, mid-difficulty text.

One extension to symbolic logic that is very well studied is called 
"predicate logic." In symbolic logic, you use capital letters to stand 
for simple sentences, and then you make complex sentences by combining 
sets of capital letters with connectives. Predicates add a new twist.  
Simple sentences are no longer necessarily just a single letter. Let 
me work through how it goes:

Let's say we have a few English sentences that we want to translate 
into logical notation.  They are as follows:

  Sam is doing homework.
  Joe is doing homework.
  Mike is doing homework.
  The ocean is cold.
  The air is cold.
  The ground is cold.

Now, if we are doing symbolic logic, we will have to translate each of 
those sentences as a separate capital letter of the alphabet.  But if 
we do that, we lose some important information. The first three 
sentences are all about someone doing homework. But that similarity is 
no longer apparent if we translate these sentences into symbolic 
logic. The last three sentences are all about something being cold, 
but again that similarity is lost if we use simple symbolic logic.

So, what logicians have done is to borrow a term you may have heard in 
English class: "predicate." In the English sentence "Sam is doing 
homework" the subject of the sentence is "Sam" and the predicate is 
"is doing homework."  There can be multiple subjects in a sentence, 
but only one predicate (unless you use a logical connective, such as 
"and").

In predicate logic, predicates are written with a capital letter. So 
the predicate "[blank] is doing homework" could be written:

  H

And the predicate "[blank] is cold" could be written:

  C

In predicate logic, proper nouns (such as "Sam" and "Mike"), as well 
as specific objects (such as "that tree there" and "my cat"), are 
written using lower case letters.

So the noun "Sam" could be written:

  s

The noun "the ground" could be written:

  g

Etc.

(Just as an aside, only the letters a through t can be used as 
specific nouns; the letters u, w, x, y, and z will be used later as 
variables, and the letter v looks too much like the symbol for "or.")

Notice that there is a HUGE difference between capital letters 
(predicates) and lower case letters (specific nouns).

In many English sentences, the noun comes before the predicate. In 
logic the convention is reversed. So if we want to say "Sam is doing 
homework" we write:

  Hs

Which roughly means "The predicate 'H' [is doing homework] is true of 
the specific noun 's' [Sam]."

Let's go back to our example sentences:

  Sam is doing homework.
  Joe is doing homework.
  Mike is doing homework.
  The ocean is cold.
  The air is cold.
  The ground is cold.

Let's use the following key:

  H = "[blank] is doing homework
  C = "[blank] is cold

  s = Sam
  j = Joe
  m = Mike
  o = The ocean
  a = The air
  g = The ground

So we can write our sentences:

  Hs
  Hj
  Hm
  Co
  Ca
  Cg

Notice that we can easily construct several new sentences without 
making up new letters. For example:

  Cj
  Joe is cold.

The predicates that I've shown so far are only what are called "one-
place predicates." That is, they are designed to have only one noun 
applied to them. But predicates do not need to be only one-place. You 
can have two-place predicates. For example, you can have these 
sentences:

  Sam is going to meet Joe.
  Joe is going to meet Sam.
  Mike is going to meet Joe.

Etc.

You can create a new two-place predicate:

  M

Such that:

  Mxy

Means: "x is going to meet y"

So you now can use the names we introduced before to make sentences 
like:

  Msj
  Sam is going to meet Joe.

  Mjs
  Joe is going to meet Sam.

  Mmj
  Mike is going to meet Joe.

Notice the difference between Msj and Mjs. Notice also the difference 
between the upper- and lower-case M's in the last sentence.

You can have three-, four-, five-, eight-, hundred six-place 
predicates. Whatever number of places you need, you can create a 
predicate with that many places.

You can even have zero-place predicates. A zero-place predicate is 
just a simple sentences in regular old symbolic logic.

We've managed to introduce this notion of "predicates" but in the 
process we've made things a whole lot more complicated than they used 
to be. What good has that done us? So far, all it has done is make our 
system of symbols a little more flexible. But the notion of predicates 
now means we are ready for one of the most interesting concepts in 
logic: quantifiers.

There are two quantifiers: Existence and Universal. The symbol for 
existence is a backwards E. Since my keyboard doesn't do that, I'll 
just use a 3.  The symbol for Universal is an upside-down A.  Since my 
keyboard doesnít do that, Iíll just use a capital V (if you remember 
from the crash course in symbolic logic, I said that V was not allowed 
as a sentence letter).

Recall that earlier I said that you use the lower-case letters: u, w, 
x, y, and z to stand as noun-variables. So the lower-case a-t are used 
for proper nouns or specific nouns, but the letters u, w, x, y, and z 
are variables that can stand for ANY noun.

The way to use quantifiers is to put them in front of noun-variables.  
So for example:

  (Vx)

is a universal quantifer applied to x.  What it means is "For all x."

So if I want to say this sentence in logic:

  Everything is cold.

I would write:

  (Vx)Cx

Which reads: "For all x, x is cold."

If I want to say:

  Something is cold.

I would write:

  (3x)Cx

You can make more complicated sentences. For example, if I want to 
say:

  Everyone who is doing homework is cold.

I would write:

  (Vx)(Hx -> Cx)

"For all x, if x is doing homework, then x is cold."

Or I can say:

  (3x)(Hx ^ Cx)

"X is someone who is both doing homework and cold."

I can also come up with tautologies.

  Hs -> (3x)Hx

"If Sam is doing homework, then there is at least one person doing 
homework."

  (Vx)Cx -> Cg

"If everything is cold, then the ground is cold."

Here is something to work on: Go back to the crash course in symbolic 
logic. There are rules there for how to introduce and eliminate 
connectives. Can you come up with rules for introducing and 
eliminating quantifiers? Can you prove that those rules are valid 
(that is, that you can only get tautologies if you use them properly)?

I also recommend that you read _Godel, Esher, Bach_ by Douglas 
Hofstadter for a great look into the power (and limits) of what logic 
can prove. I personally consider this a must-read for anyone who wants 
to learn about advanced logic. It is a very challenging book at 
points, but well worth it.

I hope this is helpful and interesting.  Iíd love to discuss these 
problems with you some more, so if you have any questions about the 
exercises Iíve given you or about the (very difficult) concepts Iíve 
(very quickly) introduced, please write back.

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


Date: 10/30/2002 at 07:52:06
From: Tim Huff
Subject: Symbolic Logic

Sorry for bothering you again but you said that all the logic proofs 
there are have been solved. I just went through a course in logic and 
we were given a book. In the book were several logic problems that we 
had to figure out such as (not this simple) 

P, P=>Q |- Q
1. P             1. Hyp
2. P=>Q          2. Hyp
3. Q             3. MP 1,2 (according to your crash course 
                            that would be =>elim 1,2)

and since there is an infinite number of tautologies (not main ones) 
there must be an infinite number of proofs, right?

Thank you for your time, 
Tim


Date: 10/30/2002 at 10:02:23
From: Doctor Achilles
Subject: Re: Symbolic Logic

Hi again Tim,

Thanks for writing back to Dr. Math.

You are correct that there is an infinite number of tautologies in 
symbolic logic, so I was wrong when I said that they've all been 
solved.

What I should have said is that I don't know exactly which have and 
have not been solved (there isn't a list kept of every proof everyone 
has ever done). Also, symbolic logic is much more limited than 
predicate logic, and people have done proofs about symbolic logic that 
show that all tautologies can be proven in a finite number of steps 
using the rules outlined in the Dr. Math crash course. So even though 
not every proof has been done, there is a mechanical method that can 
be done for any proof, so symbolic logic isn't terribly exciting.

I could make up sentences and ask you to derive them, but you can do 
that on your own. If you want advice from me for how you can expand 
your understanding of logic and not just mechanically crank out 
proofs, I recommend you try a few of the challenge exercises I 
suggested in the last letter.

If you'd like to talk about this some more, please write back.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Logic
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/