Homeworks
Homework 10.
- Exercises 3.2: 2; 3.
- Exercises 3.4: 7; 8.
- Exercises 3.5: 1; 6(a), 6(c), 6(e).
Homework 9.
- Exercises 5.4: 1(b), 1(e); 2(a), 2(b).
- Exercises 5.5: 4(e), 4(f), 4(h); 10(d).
- Using the natural deduction system of KT45^n, and Kripke models of KT45^n, show the validity of C-ind axiom, and Fixed-point axiom (Theorem 2 item 3).
Homework 8. (due sunday, May 12)
- Exercises 5.2: 2; 4.
- Exercises 5.3: 6.
- Let F=(W,R) be a frame. Prove that: (a) F validates axiom scheme B iff R is symmetric; (b) F validates axiom scheme D iff R is serial; (c) F validates axiom scheme 5 iff R is Euclidean.
Homework 7. (due sunday, May 5)
[pdf]
Homework 6. (due Saturday, April 13)
- Exercises 2.6: 2; 5(c), 5(d); 9(b), 9(e).
- Suppose R is a predicate symbol of arity 2, and P is the reflexive-transitive closure of R. Show that if P(x,y) then there is an R-path from x to y.
- Find a term s such that the formula "s: ∀x (ψ → φ) → (ψ → ∀xφ)" is provable in the typed term calculus (typed lambda-calculus), where x is not free in ψ.
- Find Gentzen-style proofs for the following sequents:
1) ∀x P(a, x, x), ∀x ∀y ∀z (P(x, y, z) → P(f(x), y, f(z))) |− P(f(a), a, f(a)).
2) ∀x P(x) → S |− ∃x (P(x) → S), where S is a propositional atom.
Homework 5.
- Exercises 2.3: 4; 9(k), 9(m), 9(n), 9(p); 11(a), 11(b).
- Exercises 2.4: 5; 6; 11(b); 12(a), 12(b), 12(e).
- Prove that formula A is true in model M with respect to l iff A is true in M with respect to l', whenever l and l' are two environments which are identical on the set of free variables of A.
- Complete the proof of completeness theorem of first order logic: (1) show that all natural deduction rules are sound, (2) the set of formulas Delta is maximal and consistent, and (3) prove the Truth Lemma.
Homework 4.
- Exercises 2.1: 3.
- Exercises 2.2: 1; 5.
- Write the inductive definition of substitution A[t/x], where term t is free for variable x in formula A.
Homework 3.
- Exercises 1.4: 11; 15.
- Exercises 1.5: 3; 7(b) and its DNF; 8; 9; 13; 15(a), 15(b), 15(e); 16; 17.
- Give an example of a tautology, and apply the technique of the proof of completeness theorem to obtain a natural deduction proof for it.
Homework 2.
- Exercises 1.2: 1(i),1(n); 2(f) and its converse; 6; 9.
Homework 1.
- Exercises 1.1: 1(a),1(d),1(h),1(i); 2(a),2(c),2(e),2(g).
- Exercises 1.3: 1(b),1(d),1(f); 2(a).
- Exercises 1.4: 9; 12(a),12(c).
- Write an algorithm which requires a string of symbols in the language of propositional logic as input and decides if it is a well-formed formula.