_____________________________________________________________________________________
LOGIC IN COMPUTER SCIENCE (LI). THEORY EXAM. JUNE 23 2020.
IMPORTANT:
-Time: 3h.
-Use only your own knowledge. No help (notes, books, webs, experts, etc.) allowed.
-Only insert your answers on the dotted lines ... below (the number of dots in a
dotted line does NOT indicate the number of items to fill in).
-Do NOT modify the questions or the @nota lines.
-We use the text notation: A E & v - to denote: forall exists and or not.
_____________________________________________________________________________________
PROPOSITIONAL LOGIC. QUESTION 1. 3.5 POINTS. @nota PL1:
Let F, G, H denote arbitrary propositional formulas.
Is -(F & -F) v G a tautology? satisfiable? unsatisfiable?
Prove your answer providing a proof or a counterexample using only the definitions
of propositional logic.
Use |= to denote the symbol of "satisfies": I |= F means "I satisfies F".
ANSWER: ...
_____________________________________________________________________________________
PROPOSITIONAL LOGIC. QUESTION 2. 3.5 POINTS. @nota PL2:
Let F be the formula ( p & -q v r & p ) & -(r v p), defined over the symbols p,q,r.
Is F a tautology? satisfiable? unsatisfiable?
Prove your answer by applying the Tseitin transformation (indicate the intermediate result)
and then using the resolution method.
Use auxiliary variables named a2 a1 a3 a0 a4 for the & and v symbols counted from
left to right in F. Use no other auxiliary variables.
Hint for resolution: start with the unit clause a0.
ANSWER:
a0 <-> a1 & -a4. Clauses: -a0 v a1, ...
a1 <-> ... Clauses: ...
...
Resolution:
GET a1 FROM a0 AND -a0 v a1
GET ... FROM ... AND ...
...
_____________________________________________________________________________________
PROPOSITIONAL LOGIC. QUESTION 3. 3 POINTS. @nota PL3:
We are interested in the optimization problem called "minOnes": given a set S of clauses over
variables {x1...xn}, finding a "minimal" model I (if it exists), that is, a model of S with the minimal
possible number of ones I(x1)+...+I(xn). Explain very briefly your answers to the following questions:
3a) Does every S have a unique minimal model, or can there be several minimal models?
3b) Given the set S and an arbitrary natural number k, what is the computational complexity of deciding whether
S has any model I with at most k ones, that is, such that I(x1) +...+ I(xn) <= k?
3c) Same question as 3a, if S is a set of Horn Clauses.
3d) Same question as 3b, if S is a set of Horn Clauses.
ANSWER: ...
_____________________________________________________________________________________
FIRST-ORDER LOGIC. QUESTION 1. 3 POINTS. @nota FOL1:
Formalize the following sentences in first-order logic and prove by resolution that C
is a logical consequence of A & B. Use --> to denote implication.
A) St. Francis is loved by everyone who loves someone.
B) No one loves nobody. (Spanish: "no hay nadie que no ame a nadie")
C) St. Francis is loved by everyone.
First, for each predicate, constant (or other function) symbol you use in
your formalization, write its meaning and arity, as in the example below.
ANSWER:
predicate symbol: loves(...) meaning "...."
...
F_A: ...
F_B: ...
...
Clauses:
1. ...
2. ...
...
Resolution:
NEW CLAUSE 4. ... FROM CLAUSENUM ... AND CLAUSENUM ... WITH MGU= ...
NEW CLAUSE 5. ... FROM CLAUSENUM ... AND CLAUSENUM ... WITH MGU= ...
_____________________________________________________________________________________
FIRST-ORDER LOGIC. QUESTION 2. 4 POINTS. @nota FOL2:
A) (1 point) Write a formula F of FOL with equality, built only over the equality predicate
(use NO other function, constant or predicate symbols)
such that any model I of F has a domain D_I with either 2 or 3 elements, that is,
I |= F iff 2 <= |D_I| <= 3.
Only write the formula F, giving NO explanations (same for B,C,D below).
B) (1 point) Write a formula F of FOL with equality,
built only over the equality predicate and one unary predicate symbol p,
("unary" means that the arity of p is 1; use NO other function, constant or predicate symbols)
such that I |= F iff p is true for AT MOST 2 elements of D_I.
C) (1 point) Like B) but now iff p is true for AT LEAST 2 elements of D_I.
D) (1 point) Like B) but now use the equality predicate and one BINARY (i.e. arity=2) predicate symbol p
to express that any finite model of F has a domain with an even number of elements.
Hint: express that the domain has two halves: each element is related by p to exactly one
element in the other half.
ANSWER: ...
_____________________________________________________________________________________
FIRST-ORDER LOGIC. QUESTION 3. 3 POINTS. @nota FOL3:
John has written a C++ program P that takes as input two arbitrary first-order formulas F
and G. He says that, if F and G are logically equivalent, P always outputs "yes" after a
finite amount of time, and if F and G are NOT logically equivalent, P outputs "no" or it
does not terminate. Is this possible? If this is not possible, explain why. If it is
possible, explain how P would work.
ANSWER: ...
_____________________________________________________________________________________