-------------------------------------------------------------------------------------------------- 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: ... Constant time. Just output: "no, John is not right". not (F_i === F_j) means that F_i and F_j represent two different Boolean functions with 4 inputs, of which only 2^(2^4) = 2^16 =~ 64000 exist. 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: ... Different clauses: 4^n No tautologies: 3^n So, the number of tautologies is: 4^n - 3^n -------------------------------------------------------------------------------------------------- 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: ... F unsatisfiable and G tautology implies [by def. of tautology and unsatisfiable] AI, not(I |= F) and I |= G implies [by def. of |=] AI, eval_I(F) = 0 and eval_I(G) = 1 implies [by arithmetic] AI, 1-eval_I(F) = 1 and eval_I(G) = 1 implies [by def. eval_I(-)] AI, eval_I(-F) = 1 and eval_I(G) = 1 implies [by def. of min] AI, min(eval_I(-F), eval_I(G)) = 1 implies [by def. eval_I(&)] AI, eval_I(-F & G) = 1 implies [by def. of |=] AI, I |= -F & G implies [by def. of tautology] -F & G is a tautology. 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: ... No (unless P = NP). If such a similar transformation existed, then we could solve an NP-complete problem (is F SAT?) by transforming F in linear time into the DNF T′(F), and then deciding whether the DNF T′(F) is satisfiable (which, as we know, can be done in linear time for DNFs) -------------------------------------------------------------------------------------------------- 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: ... Use the linear-time Horn-SAT algorithm (positive unit propagation). If it finds a model, it is minimal, because each propagated positive unit must be true in all models of S. 3b) What is the complexity of deciding whether S has only one model or more than one? Answer: ... Any other model must extend the unique minimal model I with at least one more true symbol q with I(q) = 0. We can try each q, adding it to S as a new unit clause and solve the resulting Horn-SAT problem. This is quadratic, since we try at most |P| (linear) Horn-SAT -------------------------------------------------------------------------------------------------- _____________________________________________________________________________________ _____________________________________________________________________________________ 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: ... Reflectivity: Ax p(x,x) Symmetry: Ax Ay (p(x,y) -> p(y,x)) Transitivity: Ax Ay Az (p(x,y) & p(y,z) -> p(x,z)) Reflectivity is not a logical consequence of symmetry and transitivity: the interpretation I whose domain is D_I = N, and where p_I(n,m) is always 0, is a counterexample. Symmetry is not a logical consequence of reflexivity and transitivity: the interpretation I whose domain is D_I = N, and where p_I(n,m) = 1 if and only if n <= m, is a counterexample. Transitivity is not a logical consequence of reflexivity and symmetry: the interpretation I whose domain is the natural numbers greater or equal than 2, i.e., D_I = {2,3,4,5,...}, and where p_I(n,m) = 1 iff n and m have some common prime factor, is a counterexample. Another counterexample: D_I = N, p_I(n,m) = 1 iff abs(n-m) < k (with k > 1) -------------------------------------------------------------------------------------------------- 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: ... ... Prop FOL A: T T B: T T C: T T D: T F E: T F F: F F G: T F 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): ... Yes, this is decidable: evaluating a given F in a given first order interpretation I is obviously a finite process if D_I is finite. About the complexity: it is NP-hard even for this simple set of symbols. Let I be the interpretation where D_I = {a,b}, f_I(a) = b, f_I(b) = a, and p_I(x, y, z) = 1 iff at least one of its arguments is a. Then we can express 3-SAT as a problem of checking I |= F, in the following way: (-x7 v x8 v -x2) & ... is satisfiable IFF I |= Ex1 Ex2 ... Exn (p(f(x7), x8, f(x2)) & ... ) Hence checking I |= F cannot be easier than 3-SAT. Here a and b act as true and false, f_I as negation, and p_I says if a clause is true. Note: in fact checking I |= F is P-space-complete, i.e., it is believed to be even harder than NP-complete problems. ------------------------------------------------------------------------------------ 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: ... F: Ax (sh(b,x) <-> m(x) & -sh(x,x)) 6b) The sentence "the barber is a woman (not a man)" becomes the formula: Answer 6b): G: ... G: -m(b) 6c) We need to prove that F |= G, that is, F & -G is unsatisfiable. Transformed into clausal form, we obtain the clauses: Answer 6c): ... Ax (sh(b,x) <-> m(x) & -sh(x,x)) definition of <-> Ax ( ( sh(b,x) -> m(x) & -sh(x,x) ) & ( sh(b,x) <- m(x) & -sh(x,x) ) ) definition of -> Ax ( ( -sh(b,x) v (m(x) & -sh(x,x)) ) & ( sh(b,x) v -(m(x) & -sh(x,x)) ) ) De Morgan Ax ( ( -sh(b,x) v (m(x) & -sh(x,x)) ) & ( sh(b,x) v -m(x) v --sh(x,x) ) ) doble negation Ax ( ( -sh(b,x) v (m(x) & -sh(x,x)) ) & ( sh(b,x) v -m(x) v sh(x,x) ) ) distributivity Ax ( ( -sh(b,x) v m(x) ) & ( -sh(b,x) v -sh(x,x) ) & ( sh(b,x) v -m(x) v sh(x,x) ) ) F: Ax ( -sh(b,x) v m(x) & -sh(b,x) v -sh(x,x) & sh(b,x) v -m(x) v sh(x,x) ) -G: m(b) Set of clauses: 1. -sh(b,x) v m(x) 2. -sh(b,x) v -sh(x,x) 3. sh(b,x) v -m(x) v sh(x,x) 4. m(b) 6d) By resolution and factoring, we obtain the empty clause as follows: Answer 6d): ... From: 4 + 3, resolution with mgu(m(b), m(x)) = {x=b} 5. sh(b,b) v sh(b,b) From: 5, factoring with mgu(sh(b,b), sh(b,b)) = {} 6. sh(b,b) From: 6 + 2, resolution with mgu(sh(b,b),sh(b,x)) = {x=b} 7. -sh(b,b) From: 6 + 7, resolution with mgu(sh(b,b),sh(b,b)) = {} 8. []