Logical Foundations of Computer Science, 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 cr / c of the concentration cr of the radioactive carbon C14 to the total concentration c of carbon remains the same as in the atmosphere, equal to a known constant r0. Once the plant dies, no new carbon is getting into it, so the proportion rc = crc / c of the radioactive C14 decreases as rc = r0 * 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 crc and c, and we want to find the age t. For that, we can use the relations crc / c = rc and rc = r0 * 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.
11. Suppose that in Prolog, we have equality and multiplication, so that we can describe X = Y * Z and X =/= 1 as Prolog predicates. Write down Prolog rules that describe composite(X) and prime(X) in these terms. (Hint: use negation as failure to describe prime numbers.) Show how this can be used to prove that 4 is a composite number and not a prime number.

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".
The statement says that if, whenever it rains, you wear an umbrella until it stops raining, you will not get wet. In the history below, -- means that a property was not satisfied at a given moment of time, while X means that the corresponding property was satisfied. The history is as follows:
```  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.