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

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.