Discrete Structures


Last Update: 7 December 2010

Note: NEW or UPDATED material is highlighted

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

      2. On the truth-table for material conditional:

      3. Logical Equivalences (from Rosen)

      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

      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?

        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. NEW
          Could propositions be both true and false at the same time?

    2. Automated Theorem Proving
    3. Syntax vs. Semantics

  2. Lewis Carroll, Logican

  3. Chaitin, Gregory J. (2002), "Computers, Paradoxes and the Foundations of Mathematics", American Scientist 90 (March-April): 164-171.

  4. John McCarthy's research on knowledge representation using FOL:

  5. Russell, Bertrand (1905), "On Denoting", Mind 14: 479-493.

  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.

  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.

  10. Malik, Sharad; & Zhang, Lintao (2009), "Boolean Satisfiability: From Theoretical Hardness to Practical Success", Communications of the ACM 52(8) (August): 76–82.

Copyright © 2008–2010 by William J. Rapaport (rapaport@buffalo.edu)