Final exam for the course

CS 5303, Spring 2012

Name ___________________________________________________

5 pages of handwritten notes allowed.

1. Prove that the sets {∨, ¬} and {→, ⊥} are sufficient, i.e., that all other propositional connectives can be described in terms of these connectives.

2-4. Use natural deduction, resolution, and truth tables to prove that p ∧ q |− ¬(¬p ∨ ¬q).

5. Use program synthesis to help scientists estimate the age
of the fossilized plants. The algorithm for estimating the age
is based on the fact that while
a plant is alive and breathing, the ratio c_{r} / c
of the concentration
c_{r} of the radioactive carbon C^{14} to the
total concentration c of carbon remains the same as in the
atmosphere, equal to a
known constant r_{0}. Once the plant dies, no new
carbon is getting into it, so the proportion
r_{c} = c_{rc} / c of the radioactive
C^{14} decreases as r_{c} = r_{0}
* exp(− k * t), where k is a known constant, and t is the fossil's
age
(time since the plant's death). We measure the current values
c_{rc} and c, and we want to find the age t. For that,
we can use the relations c_{rc} / c = r_{c} and
r_{c} = r_{0}
* exp(− k * t). Use
Horn clauses to synthesize the corresponding program.

6. Prove that the square root of 1/2 is irrational.

7. Use resolution to prove that if we have ∀x ∃y (x < y), then ∀x ∃y ∃z (x < y & y < z).

8. Use the predicates S(x, y) (x sees y) and D(x) (x is done) to translate the following statements into predicate logic:

- I see what has been done.
- I see what is not yet done.

9. Use first order logic to describe the property "x is a prime number". Use equality and multiplication as basic predicates.

10. Translate the following ambiguous English phrases into first order logic. Try to convey the meaning.

- I never see what has been done; I only see what remains to be done.
- A jug fills drop by drop.

12. For the case of interval uncertainty, describe simple algorithms for checking the validity of modal logic formulas [](a = b) and ◊(a = b).

13. Solve the following tolerance problem. We are designing a two-part cell phone tower. The first part a is between 10 and 11 m long, the overall height of the tower should be between 19 and 21 m. What are the possible values of the second part for which we can guarantee the desired bounds on the height? In other words, we know that 10 ≤ a ≤ 11. We need to find all the values b for which [](19 ≤ a+b ≤ 21).

14. Assume that the property "medium height" is described by a triangular membership function, for which this property is absolutely true for 170 cm and absolutely false for 150 and 190 cm. Describe an explicit formula for this function. What is the degree to which 160 cm is medium height? 180 am? If we use product as "and", what is the degree to which both 160 cm and 180 cm correspond to medium height?

15. Use the given history to check, step-by-step, that the formula []((r → uU(¬r)) → ¬w) is satisfied at all moments of time. In this formula:

- r stands for "it rains",
- u stands for "I am wearing an umprella", and
- w stands for "I am wet".

1 2 3 4 5 6 7 8 9 10 r X X X - - X X - X - u - - - - - X X - X - w X X X - - - - - - -

16. Write a program for computing the sum of an array a[1] + ... + a[n], and use program logic to prove this program's correctness.

17. What does it mean that a logic is non-monotonic? Give an example of non-monotonicity in Prolog.

18. Briefly describe your project for this class.

19. Briefly describe somebody else's project for the class.