_____________________________________________________________________________________ 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: ... _____________________________________________________________________________________