-------------------------------------------------------------------------------------------------- Logic in Computer Science, June 17th, 2025. Time: 2h30min. No books or lecture notes allowed. -------------------------------------------------------------------------------------------------- Note on evaluation: eval(propositional logic) = max(eval(Problems 1,2,3), eval(midterm exam)). eval(first-order logic) = eval(Problems 4,5,6). - Insert your answers on the dotted lines ... below, and ONLY there. - Do NOT modify the problems. - When finished, upload this file with the same name: "exam.txt". - Use the text symbols: & v - -> |= A E === for AND OR NOT IMPLIES "SATISFIES" FORALL EXISTS LOGICAL EQUIV. like in: I |= p & (q v -r) ( the interpretation I satisfies the formula p & (q v -r) ). You can write subindices using "_". For example write x_i to denote x-sub-i. -------------------------------------------------------------------------------------------------- Problem 1. (3 points). 1a) My friend John has a list L = {F_1,F_2,...,F_100000} of one hundred thousand formulas over the symbols {p,q,r,s}. He says that they are all logically non-equivalent, that is, not (F_i === Fj) for all i,j with 1 <= i < j <= 100000. What is the most efficient way to check whether John is right for a given L? Why? Your answer cannot be longer than 20 words. Answer: ... 1b) Given n propositional symbols, how many different clauses (as sets of literals) that are tautologies are there? You can consider that for each of the n symbols p, in a clause exactly one of the following 4 situations will hold: a) p and -p are in the clause b) only p is in the clause c) only -p is in the clause d) neither p nor -p are in the clause Answer: ... -------------------------------------------------------------------------------------------------- Problem 2. (4 points). 2a) Let F be an unsatisfiable formula, and let G a tautology. Is it true true that -F & G is a tautology? Prove your answer using only the formal definitions of propositional logic. Answer: ... 2b) The Tseitin transformation T transforms an arbitrary propositional formula F into a CNF (a set of clauses with auxiliary variables) T(F) that is equisatisfiable: F is SAT iff T(F) is SAT. Moreover, the size of T(F) is linear in the size of F. Answer briefly: Is there any known transformation T′ into an equisatisfiable linear-size DNF? If yes, which one? If not, why? Answer: ... -------------------------------------------------------------------------------------------------- Problem 3. (3 points). 3) Let S be a satisfiable set of propositional Horn clauses. Answer the following two questions, explaining briefly why. 3a) What is the complexity of finding the minimal model of S, that is, the model I with the minimal number of symbols p such that I(p) = 1? Answer: ... 3b) What is the complexity of deciding whether S has only one model or more than one? Answer: ... -------------------------------------------------------------------------------------------------- _____________________________________________________________________________________ _____________________________________________________________________________________ FIRST-ORDER LOGIC: _____________________________________________________________________________________ _____________________________________________________________________________________ Problem 4. (3 points). 4) Express with three formulas the properties of reflexivity, symmetry, and transitivity of a binary predicate p and show that none of the three formulas is a logical consequence of (the conjunction of) the other two. In the counterexamples, you have to use interpretations with infinite domains. Answer: ... -------------------------------------------------------------------------------------------------- Problem 5. (4 points). 5a) For each one of the following statements, indicate if it is true (T) or false (F) in propositional logic and also for first-order logic. Give no explanations why. Below always F and G are formulas and I is an interpretation. A) There are infinitely many different formulas, even if there is only one predicate symbol. B) F |= G iff F & -G is unsatisfiable. C) F is a tautology iff -F unsat. D) Given I and F, it is decidable in linear time whether I |= F. E) Given I and F, it is decidable whether I |= F. F) Given F, it is known it is decidable in polynomial time whether F is satisfiable. G) Given F, it is decidable whether F is satisfiable. Answer 5a): Prop FOL A: ... ... B: ... ... C: ... ... D: ... ... E: ... ... F: ... ... G: ... ... 5b) Consider a 1-ary function symbol f and a 3-ary predicate symbol p, and a first-order interpretation I with a finite domain D_I = {a,b}, and with a the (finite) definition of the functions f_I and p_I. Answer in a few words: Is it decidable whether I satisfies a given formula F (over f and p)? If so, what do you think is the complexity of this? Hint: any relationship with 3-SAT?. Answer 5b): ... ------------------------------------------------------------------------------------ Problem 6. (3 points). Let us consider the sentence: "In a certain village, the barber shaves all men that do not shave themselves, and only these men." Let the constant b represent "the barber", let sh(x,y) mean "x shaves y", and let m(x) mean "x is a man". Formalize the sentence in first-order logic, and prove by resolution that "the barber is a woman (i.e., not a man)." 6a) The sentence "... the barber shaves ..., and only these men" becomes the formula: Hint: use the connector <-> Answer 6a): F: ... 6b) The sentence "the barber is a woman (not a man)" becomes the formula: Answer 6b): G: ... 6c) We need to prove that F |= G, that is, F & -G is unsatisfiable. Transformed into clausal form, we obtain the clauses: Answer 6c): ... 6d) By resolution and factoring, we obtain the empty clause as follows: Answer 6d): ...