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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.