Questions and Answers (2)

Here are additional questions with answers that you might help you to prepare for the final exam.

Questions regarding the first half of the course are here.


  1. Every syllogism was given a particular name to identify it. Give an example of such a name that was given to a syllogism.
  2. Barbara. (Lecture).

  3. What is the biggest drawback of Aristotle's theory of syllogisms?
  4. It is not expressively complete. There are many valid inferences that cannot be expressed using syllogisms. (Lecture).

  5. What is the arity of a predicate?
  6. The arity of a predicate is the number of terms that it applies to, e.g., mother(x,y) has arity two. (Lecture).

  7. What is the difference between a sentence and a term?
  8. A sentence can be true or false, a term refers to an object. (Lecture).

  9. Is (1+1+1) a term in the first order language of arithmetic?
  10. No. ((1+1)+1) or (1+(1+1)) would be terms, since they are built up from the recursive rules for terms. (Lecture).

  11. What is a propositional formula of propositional logic? (2 points)
  12. 1. Variables: X, Y, Z, ...
    2. If A and B are propositional formulas, so are not A, A v B, A & B, A -> B.
    3. Nothing else is.
    This is a recursive definition. (Lecture).

  13. 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. (4 points)
  14. B  & B  C
    ----- & Elim
       B         B --> A
    ---------------------- ->ELim (Modus Ponens)

  15. Determine (using a truth table) whether the propositional formula `( A v B ) --> A' is a tautology or not. (4 points)
  16. A  B  | A v B -> A
    T  T  |   T     T
    T  F  |   T     T
    F  T  |   T     F
    F  F  |   F     T

    Since the colum under the arrow is not completely T, the formula is not a tautology. (Lecture).

  17. What is the meaning of the following: "Gamma |= S", where Gamma is a set of propositional formulas, and S a propositional formula.
  18. It means "Gamma entails S", i.e., when all the formulas in Gamma are true, also S is true. (Lecture).

  19. What is the difference between propositional logic and predicate logic?
  20. Predicate logic is propositional logic plus predicates and quantifiers, (Lecture).

  21. What does the sentence "there exits x forall y ( x <= y)" mean, if the domain of the bound variables are the natural numbers and "<=" stands for "is less or equal than"? Is the sentence true or false?
  22. It means that there is a number x, such that all numbers (including itself) is less or equal than it. This is true, since 0 is such a number. (Lecture).

  23. Name one non-classical logic.
  24. Intuitionistic, constructive, modal, fuzzy, linear... (Lecture).

  25. What does a recursive definition consist of?
  26. 1. Base clause(s).
    2. Recursive clause(s).
    3. Final clause. (Lecture).

  27. Who is the founder of modern set theory?
  28. Georg Cantor (1845-1918)

  29. What does ZF stand for?
  30. The modern axioms of set theory, due to Zermelo and Fraenkel.

  31. What does it mean for a function f:A->B to be 1-1 (one-to-one, injective)?
  32. No two different elements of the set A are mapped to the same element in B.

  33. Which of the following two sentences of predicate logic can be true in a finite domain, and which in an infinite domain of objects: "forall x exists y ( x < y )" and "exists x forall y ( x < y )"?
  34. "forall x exists y ( x < y )" is true if for all numbers there exists a greater number. This can be true only with infinite sets and it certainly the case for the natural numbers.

    "exists x forall y ( x < y )" is true if there is one number such that all numbers are greater than it. This sentence is false, since no number is greater than itself. If would be true if the relation were "greater or equal", because in this case there is a number such that all numbers are greater or equal, namely 1.

© Dirk Schlimm, Last modified: 5/3/02