Logical Foundations of Computer Science,
Final Exam for the course
CS 5303, Spring 2016

Name ___________________________________________________

5 pages of handwritten notes allowed. Use extra sheets of paper if needed.

1. Sufficiency of propositional connectives:

1a. Show that the set S = {∨, &, ¬} is sufficient, i.e., that all other propositional connectives can be described in terms of these connectives.

1b. Use the general algorithms for transforming formulas into CNF and DNF to describe negation-of-implication ¬(p → q) in terms of ∨, &, and ¬.

1c. What is the smallest subset S0 of the set S which is sufficient? Prove that your subset S0 is sufficient, and that no proper subset of S0 is sufficient.

2. Derivation in propositional logic: show that from p & q, we can conclude that p → q:

2a. by using natural deduction;

2b. by using resolution: and

2c. by using truth tables.

3. Logic for program synthesis: Use program synthesis to compute the equivalent resistance R of the two resistors R1 and R2 working in parallel: Use the wave algorithm to synthesize the program for computing R.

4. First order logic:

4a. Use a general algorithm to translate the following first order formula F into a normal form:
∃x P(x) → ∃x Q(x).

4b. Use natural deduction to prove that the formula F indeed implies its normal form;

4c. Translate the following phrase into first order logic: "A family that prays together stays together". Use the following three basic predicates:

  • "pray_with(x, y)",
  • "stay_with(x, y)", and
  • "in_family(x, y)" (meaning that a person x is in family y).

5. Prolog:

5a. Suppose that we have predicates parent(X, Y), male(X), and female(X). Use Prolog rules to describe cousin(X,Y).

5b. Give an example when the Prolog result differs from formal logic, but the Prolog result is more intuitive than formal logic.

5c. Explain what is meant when people say that Prolog describe a non-monotonic logic. Give an example of the corresponding non-monotonicity.

6. Modal logic:

6a. Come up with simple algorithms for checking the validity of modal logic formulas [](a = b) and
◊(a = b).

6b. A students knows that he has got between 55 and 60 points so far. In other words, for the number of points a that the student got, we have 55 ≤ a ≤ 60. How many points b the student needs to get on the final exam to get an A for the class, i.e., to have [](90 ≤ a + b ≤ 100).

6c. How many points b does this student need on the final exam to have a chance to get an A, i.e., to have ◊(90 ≤ a + b ≤ 100).

7. Fuzzy logic: Blood pressure is characterized by two numbers: top number and bottom number (e.g., 120/80). For a persin to be healthy, both numbers have to be normal.
  • When the top number is 120 or below, it is definitely normal. When the top number is 140 or above, it is definitely not normal.
  • When the bottom number is 80 or below, it is definitely normal. When the bottom number is 90 or above, it is definitely not normal.
Do the following:
  • Use linear interpolation to describe the corresponding membership functions.
  • If a person has blood pressure 135/90, what is the degree to which this person is healthy if we use min as an "and"-operation?
  • what if we use product as an "and"-operation?

8. Temporal logic: In El Paso, it is important to wear sunscreen. The idea is that if you wear sunscreen until the sun is out, you protect yourself against the sun-imposed harm. This idea can be described as follows: [](s → wU(¬s)) → ¬ h, where:
  • s stands for "the sun is shining";
  • w stands for "I am wearing the sunscreen"; and
  • h stands for "I am harmed by the sun".
In the history below, X means that the property is satisfied, while - means that this property is not satisfied: 
   1  2  3  4  5  6  7  8  9 10
 s -  -  X  X  X  -  -  X  X  X
 w X  X  X  X  -  -  -  X  X  X
 h X  -  -  -  -  -  -  -  -  -

Use the general algorithm to check at which moments of time the above statement is true.

9. Constructive logic: prove that for every computable number x, the numbers y = 2 * x and z = 4 * x are also computable.

10. Paradoxes: Formulate the following paradoxes, explain why they are paradoxical, and how we can resolve these paradoxes:

10a. the heap paradox;

10b. the smallest natural number that cannot be described by fewer than twenty words.

11. Projects:

11a. Briefly describe your project for this class.

11b. Briefly describe someone else's project for this class.