Logical Foundations of Computer Science,
Test 2 for the course
CS 5303, Spring 2016

Name ___________________________________________________

5 pages of handwritten notes allowed.

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

2. Solve the following tolerance problem. We are designing a two-layer pavement. The thickness of the first layer a is between 30 and 40 cm, the overall thickness of the two-layer pavement should be between 50 and 65 cm. What are the possible thicknesses of the second layer for which we can guarantee the desired bounds on the overall thickness? In other words, we know that 30 ≤ a ≤ 40. We need to find all the values b for which [](50 ≤ a+b ≤ 65).

3. Solve the following control problem. We are designing a two-layer pavement, in which the thickness of the second layer can be adjusted based on the first layer result. The machine for laying the second layer can provide thicknesses between 10 and 30 cm. What are the thicknesses a of the first layer for which we can achieve the overall thickness between 50 and 65 cm? In other words, we know that 10 ≤ b ≤ 30. Find all the values a for which ◊(50 ≤ a+b ≤ 65).

4. Assume that the property "normal body temperature" is described by a triangular membership function, for which this property is absolutely true for 36.5 degrees and absolutely false for 35.5 and 37.5. Describe an explicit formula for this function. What is the degree to which the temperature 37.2 is a normal? If we use the product as "and", what is the degree to which both values 37.2 and 37.4 are normal?

5. Use the given history to check, step-by-step, that the formula []((k \/ (¬ k & sUt)) → [](t → k)) is satisfied at moment t = 3. In this formula:
  • k stands for "student knows the material",
  • s stands for "student studies the material", and
  • t stands for "there is a test".
The statement says that if a student either knows the material already or studies all the way to the test, then on the day of the test, the student will know the material. 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
k -  -  -  -  -  -  X  X  X  X
s -  X  X  X  X  X  X  -  -  -
t -  -  -  -  -  -  X  -  -  X

6. Is its possible to compute the difference of two computable numbers? If yes, describe the algorithm; if not, explain why such an algorithm is not possible.

7. Is it possible to algorithmically check whether two computable numbers are equal? If yes, describe the algorithm; if not, explain why such an algorithm is not possible.

8. What does it mean that a logic is non-monotonic? To give an example of non-monotonicity, transform the following knowledge base into a Prolog program. This knowledge base consists of two statements: "Normally, it is warm in El Paso", "Cold days are exceptions (i.e., abnormal)".
  • Assume first that we have no additional information about today. If we want the Prolog program a query -- asking whether it is warn today in El Paso -- what will be the answer?
  • Assume now that we also know that today is a cold day. What will be the answer now?
  • Explain why this shows that Prolog implements a non-motononic logic.

9. Translate the following English phrases into first order logic. Try to convey the meaning. If appropriate, use modal and/or temporal logic as well.
  • It is possible to survive in this world, but for that, it is necessary to be resourceful.
  • I will continue giving you quizzes until you learn the material.