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
                      A
     
     

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


    3. 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.
     
     

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


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

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


    5. Gottlob Frege (1848 - 1924).
     
     

  5. 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?


    6. 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.