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".

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.