Some Exercises in Logical Reasoning

There are no formal prerequisites for Computability beyond intermediate algebra. However, it will be assumed that students taking the program are capable of thinking logically and analytically and are comfortable in dealing with symbolic languages and abstract ideas.

The following problems are an admittedly crude way of letting you know what sort of reasoning ability will be expected of students taking the program. Consequently, your answers will be judged not only in terms of whether you got the "correct" answer but also the quality of the reason you give. The questions are of different levels of difficulty. It is unlikely that you will be able to do all of these problems in an hour or two. In order to do some of the harder ones a good strategy is to work on them for a while and then come back to them the next day.

Some students taking Computability will be taking a variety of threads (check with the faculty). If you think that this test is not representative of your interests, then you may write a 2-3 page paper describing your background, your technical experience, your academic experience, and your goals for the coming academic year. Your faculty may ask for a reference as well.

Even if you have difficulty with one or two of the more difficult questions, you might be able to successfully complete the program. Further discussions with the faculty about your background, interests, and future goals will be useful in determining whether the program is appropriate for you. If you are unable to answer most of the questions or hate doing this sort of thing, you should NOT consider taking the program. If, on the other hand, you still want to enroll after doing these problems, please email your completed exam to OR you can bring or send your solutions to:

Sherri Shulman
Office: Sem 3163
Address: Sem I, 1009, The Evergreen State College, Olympia WA 98505
Phone: (360)-867-6721
email: sherri@evergreen.edu

Questions

1. Which of the following arguments are valid? (An argument is valid if and only if the conclusion follows logically from the premises.)
   1. Some arps are not blops.
      Some blops are not clugs.
      Therefore, some arps are not clugs.

   2. All arps are blops.
      No arps are clugs.
      Therefore, no blops are clugs.

   3. Some arps are not blops.
      All clugs are blops.
      Therefore, some arps are not clugs.

   4. If Alfred is an arp, then Betty is a blop.
      It is not the case that both Betty and Clyde are blops.
      Therefore, if Clyde is a blop, then Alfred is not an arp.

   5. Alfred likes anyone who likes him.
      Therefore, Alfred likes himself.

   6. Alfred does not like anyone who likes him.
      Therefore, Alfred does not like himself.

   7. Everyone likes anyone who likes someone.
      Alfred like Betty.
      Therefore, Clyde likes Doris.

2. Two players, A and B, play the following game:
   1. Initially there are 300 coins on the table.
   2. Each player, in turn, removes either 1, 3, or 4 coins.
   3. Player A makes the first move.
   4. The player who removes the last coin(s) wins.

   One of the two players will always win if he plays intelligently. Which player is it and what is his winning strategy?

3. In Computability we will spend considerable time studying formal systems. Here is a problem about a formal system that can be used to generate a formal language L.

   This formal system uses just three symbols: a,b, and -. Any sequence of one or more of these symbols is called a word.
   Example: the following are words: -a--b-, aa, and -. If X and Y are any two words, the XY denotes the word that consists of the symbols in X followed by the symbols in Y. For example, if X and Y are the first two words in the above example, then XY is the word -a--b-aa.

   The language L is defined as the set of words that can be generated by the following axioms and rules:

   Axioms:
   A1. a- is in L.
   A2. - is in L.

   Rules:
   R1. If X is a word in L, then aXb is in L.
   R2. If X and Y are words in L, then X-Y is a word in L.
   R3. If X and X-Y are both words in L, then Y is a word in L.

   One can show that a given word is in the language L by constructing a diagram like the one on the right which demonstrates how that word can be generated from the axioms by the rules. The diagram on the rights shows that the word -b-- is in L. (The words at the top of each branch are axioms, and the remaining words follow by one of the rules from the word or words immediately above them). Such a diagram is called a "derivation".

   - - \ / --- | a---b \ a- a---b-- \ / -b--

   The best way of proving that a given word is not in L is by finding a property which every word of the language has, but which the given word does not have. For example, consider the word a--b--. This is not in the language because it contains an even number of dashes; whereas it can be shown that in any word of the language the number of dashes must be odd.

   1. Prove that every word of the language has an odd number of dashes. (One can prove that every word of the language has a certain property by showing that the axioms have that property and that all of the rules preserve that property.)

   2. For every word of the language one can say something interesting about the total number of dashes that occur to the left of any a. What is this property and why is it true?

   3. determine which of the following words are in L. For those that are, construct a derivation of the word; for those that are not, prove that they are not.
      aa-b--   ---a--b   --a--b-   -b

   4. At first glance it would appear that rule R3 serves no useful purpose since it seems merely to undo what rule R2 did. Show that R3 is not redundant, by finding a word in L which could not be generated if R3 were removed from the list of rules. Prove that it could not be so generated.

   5. Prove that if X is any word of the language L, then so is Xb.

   These problems concerning language L illustrate the fact that it is not all that easy to determine whether or not a given word can be generated by the axioms and rules of a formal system. You might think that this is the sort of problem that could be solved by a computer. Unfortunately (or fortunately, depending on your point of view), this is not always the case. There are formal languages for which no mechanical procedure (algorithm) exists for determining whether or not any given word is in that language. Such languages are said to be "undecidable". For example, the first question on this test dealt with the problem of deciding whether or not a given argument was valid. In Computability during fall quarter we will see that there exist axioms and rules for generating any valid argument. Later in the year we will see that this language is undecidable - there is no algorithm for deciding whether any given argument is or is not valid.

4. The following passage is taken from Stephen Barker's Philosophy of Mathematics . After reading it answer the questions at the end.

   Let us first consider some distinctions that have been important to philosophers and that have underlain much discussion in the philosophy of mathematics. The first of these is a distinction to which philosophers have long given attention, that between what they have called a priori knowledge and what they have called empirical (or a posteriori) knowledge.

   Suppose someone knows that hydrogen molecules always consist of two atoms, or that there will be a gale tomorrow. These are examples of what philosophers have meant by empirical knowledge. Each of these pieces of knowledge is based on experience in this sense: to know any of these facts a person must not only understand what is meant but must also possess evidence drawn from sense experience -- that is, evidence regarding what has been seen or heard or felt or smelled or tasted. Summing up, we may define empirical knowledge as knowledge that requires justification from experience.

   There are other examples of knowledge, however, which do not depend upon experience in this way. Suppose that someone knows that hydrogen molecules are molecules, or that there will be a storm tomorrow if there is a gale. These are clear-cut examples of what philosophers have meant by a priori knowledge. A person does not need to have watched physicists' experiments with hydrogen to know that hydrogen molecules are molecules; nor need he have seen tomorrow's weather map to know that there will be a storm tomorrow if there is a gale. In these cases the only experience that is required is whatever experience may be needed to understand the words in which the knowledge is expressed: no sense experience beyond this is necessary to justify this claim that he knows. Summing up, we may define a priori knowledge as knowledge that does not need to be justified by experience.

   In addition to the distinction between a priori and empirical knowledge, philosophers have also concerned themselves with another related distinction, that between analytic and synthetic knowledge. This distinction was introduced into philosophy by the eighteenth century German philosopher, Immanuel Kant.

   According to Kant, a true statement is analytic if and only if it is true by virtue of its logical form, or if, through appeal to definitions, it can be translated into a statement true by virtue of its logical form. A false statement would be analytic if and only if it is false by virtue of its logical form, or if, through appeal to definitions, it could be translated into a statement false by virtue of its logical form. And a statement is synthetic if and only if it is not analytic.

   Kant felt that analytic knowledge (that is, knowledge expressible in analytic statements or judgments) poses no worrisome problems for philosophy. Kant thought it obvious how the mind is able to attain analytic knowledge, all of which is of course a priori knowledge. In knowing, for instance, that all bachelors are unmarried, a person possesses a piece of knowledge that merely reflects the nature of his own concepts, or as we might prefer to say, reflects the way he understands his own language. In order to know this, the person need only detect that the second concept is a component of the first; he need not possess information about the world outside of his own mind itself. Everything is obvious, Kant felt; employing the concept of bachelor that we do employ, simple consistency is our justification for maintaining that whoever falls under the concept of bachelor also falls under the concept of being unmarried. This is something that we know with perfect certainty and clarity; its only drawback is that it is something so empty and trivial that it barely seems to deserve to be called a piece of knowledge.

   Synthetic knowledge, on the other hand, seemed to Kant to pose problems for the philosopher. Synthetic judgments have the advantage of being neither empty nor trivial; by linking together concepts that are not intrinsically related, they express important conjectures about the world. But how can we know that they are true? Mere consistency alone is not enough to entitle me to link together concepts in a synthetic judgment; there must be something else, a tertium quid (a third thing, in addition to the minimum of two concepts) which entitles me to synthesize the separate concepts in a synthetic judgment. With regard to synthetic judgments that are empirical, Kant was satisfied with the answer that sense experience constitutes the 'third thing' that can justify my judging, say, that no pigs fly. I have seen pigs and have observed how they differ in design and behavior from birds and blimp, and this sense experience is the 'third thing' on the basis of which I can be entitled to make the judgment.

   But what about synthetic a priori judgments? Here the deep philosophical problem seemed to Kant to arise. Suppose there is some knowledge that is both a priori (that is, not justified by sense experience) and synthetic (not justified merely by the intrinsic connections of the concepts involved -- or if you prefer, not justified by the way the terms are understood). Such synthetic a priori knowledge would have to be justified by some remarkable 'third thing.' If there is such synthetic a priori knowledge, it would be a matter of great importance to understand how we attain it. Kant felt that mathematics provided the very clearest instances of such synthetic a priori knowledge.

   Questions.

   1. Is the knowledge that no bachelor in California is married empirical? a priori? synthetic? analytic? Briefly explain your answers.

   2. The author asserts the proposition that all analytic knowledge is "of course a priori knowledge". Is this proposition itself an analytic truth. Why or why not?

   3. How might Kant respond to the following argument which was advanced by the British philosopher, A.J.Ayer, and is this argument valid?

      Mathematical propositions are necessary truths, but empirical propositions are not. All synthetic propositions are empirical. Therefore, mathematical propositions are neither synthetic nor empirical.