80-110 The Nature of Mathematical Reasoning

Thursday, August 3 2000

Quiz 8

      Name: _______________________________

  1. Give a syntactic proof (using the Natural Deduction rules) of "A" from the premises "B -> A" and "B & C". Say what rules you are using.

  2. B & C
    ------ and-Elim
        B                     B --> A
    --------------- ->-Elim


  3. Determine (using a truth table) whether the propositional formula `( A v B ) -> A' is a tautology or not.

  4. A  B   |   (A v B) -> A
    T    T  |   T
    T    F  |   T
    F    T  |   F
    F    F  |   T

    The propositional formula is not a tautology.


  5. What is the meaning of the following: "Gamma |= S", where Gamma is a set of propositional formulas, and S a propositional formula.

  6. Gamma entails S, i.e., whenever all formulas in Gamma are true, S is also true.

  7. Who is the "father of modern logic"?

  8. Gottlob Frege (1848 - 1924).

  9. What does the sentence "there exits x forall y ( x <= y)" mean, if the domain of the bound variables are the natural numbers? Is the sentence true or false?

  10. It means, "there exists a natural number which is less or equal all natural numbers". The sentence is true since there is a smallest natural number, namely 1.