First Order Logic

36 flashcards · Other · by Martin Gegenbauer

  1. Of which symbols does a first-order alphabet consist?

  2. Function and predicate symbols are called non-logical symbols. The other symbols are logical symbols.

    Function and predicate symbols are called non-logical symbols. The other symbols are logical symbols.

  3. Give the definition of a term in first-order logic!

    Where aaa is a constant.

  4. By what are first-order formulas defined?

  5. What are atomic formulas, and what are compound formulas? Which connective binds stronger?

  6. What is the scope of quantifiers?

  7. What are free and bounded variables?

  8. How can the set of free variables be computed?

  9. Translate that sentence into first-order logic: Every man is mortal. Since Socrates is a man, he is mortal.

  10. Translate that sentence into first-order logic: All that glistens is not gold. This pot glistens. Therefore, it is not gold.

  11. How is the semantics of a first-order language obtained? What is a structure in semantics?

  12. What is an interpretation function in semantics?

  13. What is a variable assignment?

  14. What is the semantics of a term?

  15. What are the semantics of formulas?

  16. When is a formula called valid, satisfiable, unsatisfiable, or refutable? What is a model?

  17. What are logical consequences and logical equivalences?

  18. What is an existential closure, and what is a universal closure?

  19. When is a structure valid, satisfiable, unsatisfiable, or refutable?

  20. When is a formula in prenex normal form (PNF)? What is the prefix, and what is the matrix?

  21. Which steps must be taken, to reduce a first-order formula into a set of clauses?

  22. What are the transformation rules for PNF?

  23. What are the rules for skolemization?

  24. What are the rules for clausification?

  25. Is first-order logic decidable?

  26. What is a substitution in first-order logic? What is the range of a substitution? What is the variable range of a substitution?

  27. What is a contraction of a substitution?

  28. What is a substitution application to a term?

  29. What is an instance of a term?

  30. What is a substitution composition?

  31. When is a substitution more general or more specific?

  32. What is a substitution application to a formula?

  33. What is a variable capture in first-order logic?

  34. When is a substitution free for a formula?

  35. When is a substitution called permutation?

  36. When is a substitution idempotent?