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 S_{0} of the set S which
is sufficient? Prove that your subset S_{0} is sufficient,
and that no proper subset of S_{0} 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
R_{1} and R_{2} working in parallel:

- We
know the resistances R
_{1}and R_{2}, and we know the overall voltage V. - The following formulas relate these
quantities and the currents I
_{1}, I_{2}, and I: I = I_{1}+ I_{2},

V = R_{1}* I_{1}, V = R_{2}* I_{2}, and V = R * I.

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.

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

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.