Homeworks for the course

CS 5303, Spring 2012

1. (Due January 23) Exercise 1.1 from the book.

2. (Due January 25) Prove that the square root of 3 is irrational.

3. (Due January 25) Prove that there exists an irrational number x for which x raised to the square root of 3 power is rational.

4. (Due January 30) Exercise 1.2, Part 3, (a)-(e); Exercise 1.5, Part 2, Part 3(a), and Part 5.

5. (Due February 8) Use the Horn clauses and wave algorithm to
solve the following problem: we know that V = V_{1} +
V_{2}, V_{1} = I * R_{1}, V_{2}
= I * r_{2}, V = I * R, we know the values of I,
R_{1}, and R_{2}, we need to find R.

6. (Due February 8) Exercise 2.1, Part 1)-4).

7. (Due February 20) Use resolution to prove the following two statements: (a → b) → (¬b → ¬a) and (a & b → c) → (a & ¬b → ¬c).

8. (Due February 20) Use resolution to prove that if we have ∀x∀y∀z (x > y & y > z → x > z) and ∀x (¬x > x), then ∀x∀y (x > y → ¬y > ¬ x).

9. (Due February 27) Use the Prolog website to derive a simple fact about your own relative.

10. (Due March 21) For the case of interval uncertainty, come up with simple algorithms for checking the validity of modal logic formulas [](a < b) and ◊(a < b).

11. (Due March 21) Solve the following tolerance problem: Let us assume that 9 ≤ a ≤ 11. Find all the values b for which [](18 ≤ a+b ≤ 21).

12. (Due March 21) Solve the following control problem: Let us assume that −5 ≤ b ≤ 5. Find all the values a for which ◊(−3 ≤ a+b ≤ 4).

13. (Due March 28) select a project.

14. (Due April 2) Write a program that implements a
multi-valued logic approach to expert-based control that we
covered in class (and which is described in the handouts). This
program should take, as input, the difference ΔT between
the actual temperature T and the ideal temperature
T_{0}, and return the angle φ to which we need to
turn the knob of the temperature controlling device to
compensate for this difference. Submit a printout of the
program, a printout of the results, and be ready to show how
your program works.

15. (Due April 9) Finish what we started in class: use the given history to check, step-by-step, that the formula []((p & ¬o) → X(s & (s U o)) & [](o → []0) is satisfied at moment t = 2. In this formula:

- p stands for "push the button",
- s stands for "the garage door is opening", and
- o stands for "the garage door is open".

1 2 3 4 5 6 7 8 9 10 p - - X - - - - X - - s - - - X X X - - - - o - - - - - - X X X X

16. (Due April 9) Use the given history to check, step-by-step, that the formula [](t → X◊p) & [](p → ¬Xp) is satisfied at moment t = 2. In this formula:

- t stands for "a slice of bread is placed in the toaster", and
- p stands for "the ready toast pops up".

1 2 3 4 5 6 7 8 t - - X - - X - - p - - - - X - X -

17. (Due April 11) Similarly to what we did in class, write a
program for computing a^{n}, and use program logic
to prove this program's correctness.

18. (Due April 16) Come up with two ambiguous English phrases, and propose a reasonable translation of each of these phrases from English to predicate logic.