Logic

Note: A username and password may be required for some online papers. Please contact Bill Rapaport.

"The greatest challenge to any thinker is stating the problem in a way that will allow a solution."         —Bertrand Russell

"Against logic there is no armor like ignorance."         — Laurence J. Peter




---

1. Logic & Automated Theorem Proving
   1. Propositional & First-Order Logic
      1. Translating from English to a First-Order Language
         • Representing English Sentences in FOL
         • Suber, Peter (2002), "Translation Tips"
           • Suber's guide converted to Rosen text's notation
           • Note: Some of the above documents may use different symbols for the logical connectives;
             please ask me if you can't figure them out.

         • On the Translation of "Some Dogs Are Pets"

      2. On the truth-table for material conditional:
         • Marcus, P.S. (1967), "Motivation of Truth Tables from Tautologies", American Mathematical Monthly 74(3) (March): 313–314.

         • Kraus, G.A. (1968), "Motivation for Defining the Conditional", American Mathematical Monthly "Motivation for Defining the Conditional", American Mathematical Monthly 75(10) (December): 1103–1104.

      3. Logical Equivalences (from Rosen)
         • PowerPoint slides (from Rosen)

         • On the logical equivalence of a conditional (p → q) and its contrapositive (¬q → ¬p) (humorous poetry version):

           Cooke, W.P. (1969), "‘Rye Whiskey’ in Contrapositive", American Mathematical Monthly 76(9) (November): 1051.

      4. "Propositional Logic and NP-Completeness"

      5. "The Barber Paradox"

      6. Distribution of Quantifiers over Conjunction and Disjunction

      7. Rules of Inference (from Rosen)

      8. The Addition Rule of Inference

         ---

      9. Understanding & Creating Proofs
         • [PPT]
         • [PDF]
         • [HTML]

         • See also:
           Bowling, J. Michael (1977), "Word Chains: A Simulation of Proof", Mathematics Teacher (September): 506–508, 560.

      10. Proof Strategies

          ---

      11. Some questions (and answers) about logic:

          1. Why are the laws of logic truth-preserving?

          2. Are there as many true propositions as false ones?

          3. Must a proposition be either true or false today? What if its truth or falsity is a correspondence to a future event?

          4. Can mathematics be reduced to formal logic?
             • Why not?

          5. Is it true that mathematics cannot be reduced to formal logic?

          6. Can a mathematical claim be true whether we know it or not?
             Can we know a mathematical claim without any proof?

          7. Is this argument valid?
             • The sky is blue; therefore, 2+2=4

             Try to answer it yourself before linking to this online answer :-)

          8. How does one prove that an informal fallacy is a fallacy?

          9. Could there be a logic in which there was a third possibility besides p or ¬p?

          10. What is the difference between inductive and deductive logic?

          11. Can two people reason differently? Even when given the exact same premises?

          12. Could there be more than a countably infinite number of propositions?

          13. Why is that if P entails not-Q and Q (a contradiction) do we conclude not-P?

          14. Is logic ever wrong?

          15. Is it possible to prove that something cannot be derived?

          16. 
              Could propositions be both true and false at the same time?

   2. Automated Theorem Proving
   3. Syntax vs. Semantics

   ---

2. Lewis Carroll, Logican
   Lewis Carroll, most well known as the author of "Alice in Wonderland" (more properly known as Alice's Adventures in Wonderland and Through the Looking-Glass), was also a professional logician. You might find the following of interest:
   1. Translation of Lewis Carroll into First-Order Logic

   2. "Lewis Carroll and Math/Logic/Games/Puzzles"

   3. "Lewis Carroll Puzzles"

   4. "Carroll's Paradox"
      • Original version:
        Carroll, Lewis (1895), "What the Tortoise Said to Achilles", Mind 4(14) (April): 278-280.

      • This cute story by the author of Alice in Wonderland, who was a professor of logic at Oxford University(!), has been interpreted in many ways.
        My understanding of it is that it clarifies the nature of rules of inference.

   ---

3. Chaitin, Gregory J. (2002), "Computers, Paradoxes and the Foundations of Mathematics", American Scientist 90 (March-April): 164-171.
   • Discusses the logicians and philosophers Bertrand Russell, David Hilbert, Kurt Gödel, Alan Turing, and how their work on logical paradoxes in the foundations of mathematics led to the development of computers.

   ---

4. John McCarthy's research on knowledge representation using FOL:
   • McCarthy, John (1959), "Programs with Common Sense", in D.V. Blake & A.M. Uttley (eds.), Proceedings of the ["Teddington"] Symposium on Mechanisation of Thought Processes (London: HM Stationary Office).

   ---

5. Russell, Bertrand (1905), "On Denoting", Mind 14: 479-493.
   • An answer to the question whether the present King of France is bald,
     written by one of the two philosophers (the other was Alfred North Whitehead)
     who developed the kind of logic that we are studying.

   ---

6. Smith, Peter (2003), "Validity and Arguments", Ch. 6 of An Introduction to Formal Logic (Cambridge, UK: Cambridge University Press).

7. Stewart, Ian (1997), "Turing's Train Set", Ch.6 of The Magical Maze: Seeing the World through Mathematical Eyes (New York: John Wiley & Sons): 157-187.
   • An introduction for a general audience to how and why logic is at the foundation of mathematics and computation; discusses Turing machines, Gödel's proof that there are true but unprovable propositions in mathematics, the Game of Life, etc. It begins with a story of what it might feel like to live inside a Turing machine!

8. Tropp, Henry S. (1984), "Origin of the Term Bit", [IEEE] Annals of the History of Computing 6(2) (April): 152-155. [PDF]

9. Tymoczko, Thomas (1979), "The Four-Color Problem and Its Philosophical Significance", Journal of Philosophy 76(2) (February): 57-83.
   • Has some interesting ideas on the nature of mathematical proofs by computer, and whether mathematics is an empirical science.

   • Also see:
     Gardner, Martin (1966), Martin Gardner's New Mathematical Diversions from Scientific American (New York: Simon & Schuster), Ch. 10: "The Four-Color Map Theorem", pp. 113-123, 250-251.

10. Malik, Sharad; & Zhang, Lintao (2009), "Boolean Satisfiability: From Theoretical Hardness to Practical Success", Communications of the ACM 52(8) (August): 76–82.
    • An interesting paper on the use of truth tables for propositional logic to solve scheduling problems, seating assignments, software verification, and other practical problems involved with the satisfaction of constraints.

    • For an interesting follow-up article, see:
      Vardi, Moshe Y. (2010), "On P, NP, and Computational Complexity", Communications of the ACM 53(11) (November): 5.