-------------------------------------------------------------------------------------------------- Logic in Computer Science, January 11st, 2024. 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) For each one of the following statements, indicate if it is true or false for propositional logic. Answer T (true) or F (false) on each dotted line ... Give no explanations why. Below always F,G,H are formulas and I is an interpretation. Note: Wrong answers subtract 0.2 points. Unanswered questions subtract 0.1 points. 1) ... It is decidable in polynomial time whether a given formula in DNF is satisfiable. 2) ... Given a set of Horn clauses S, we can find in linear time a minimal model I of S, that is, a model I with the minimal |{ p | I(p)=1 }|. 3) ... If F is unsatisfiable, then -F |= F. 4) ... Given a formula F, the Tseitin transformation of F is a set of clauses that is logically equivalent to F. 5) ... The closure under resolution Res(S) of a finite set of clauses S is always a finite set of clauses. 6) ... There are formulas F and G such that F |= G and F |= -G. 7) ... There are infinitely many different formulas, even if there is only one predicate symbol. 8) ... F is satisfiable if, and only if, all logical consequences of F are satisfiable formulas. 9) ... There are infinitely many different formulas that are not logically equivalent, even if there is only one predicate symbol. 10) ... Given I and F, it is decidable in linear time whether I |= F. 11) ... Given a formula F, the Tseitin transformation of F always has a number of clauses that is linear in the size of F. 12) ... The closure under resolution Res(S) of a finite set of clauses S is always a DNF. 1b) You have three closed boxes in front of you, two of them empty and one full of gold. The lid of each box contains a statement regarding its contents. Box A says "The gold is not here", box B says "The gold is not here" and box C says "The gold is in box B." If we know that one and only one statement is true, which box contains the gold? Define the necessary predicate symbols, formalize the statements, and decide which is the correct interpretation. Answer: ... -------------------------------------------------------------------------------------------------- Problem 2. (4 points). 2a) Let F and G be two formulas. Prove that F |= G if and only if F & -G is unsatisfiable. Prove it as simply as you can using only the definitions of propositional logic, filling the dots ... below (use as many lines as you need). F |= G iff [ by def. of logical consequence ] A I, I |= F implies I |= G iff [ by def. of implies ] A I, I \|= F or I |= G ... ... 2b) Let F be a formula. Prove that the formulas F and --F (double negation) are logically equivalent: Prove it as simply as you can using only the definitions of propositional logic, filling the dots ... below (use as many lines as you need). F === --F iff [ by def. of logical equivalence ] A I, I |= F if and only if I |= --F iff [ by def. of if and only if, and |= ] A I, eval_I(F) = eval_I(--F) ... ... 2c) Let F,G,H be three formulas. Prove that F & G |= H if and only if F |= G -> H Prove it as simply as you can using the definitions of propositional logic, but in THIS section you can use (as a step of the proof) the following: * the result of exercise 2a): F1 |= F2 iff F1 & -F2 is unsatisfiable * the result of exercise 2b) -double negation-: --F1 === F1 * the logical equivalence of associativity of &: (F1 & F2) & F3 === F1 & (F2 & F3) * the Substitution lemma * the logical equivalence of De Morgan law of &: -(F1 & F2) === (-F1 v -F2) F & G |= H iff [ by exercise 2a) ] (F & G) & -H is unsatisfiable ... ... -------------------------------------------------------------------------------------------------- Problem 3. (3 points). Consider the following particular case of the resolution ("unitary" resolution): p -p ∨ C -------------- C where p is a propositional symbol. 3a) Prove that the unitary resolution is correct. Answer: ... 3b) Prove that the "unitary" resolution is not refutationally complete for clauses that are not Horn. Answer: ... -------------------------------------------------------------------------------------------------- _____________________________________________________________________________________ _____________________________________________________________________________________ FIRST-ORDER LOGIC: _____________________________________________________________________________________ _____________________________________________________________________________________ Problem 4. (4 points). 4a) Let F and G be two FOL formulas. The formulas Ex (F -> G) and Ex F -> Ex G are logically equivalent? Answer: ... 4b) Prove that resolution without factorization in FOL is not refutationally complete. Hint: give a counterexample of two clauses with two literals each. Answer: ... 4c) Write a formula F in FOLE that expresses that for every model I of F there are at most n elements in the domain of I, for a given natural n Answer: ... ------------------------------------------------------------------------------------ Problem 5. (3 points). 5a) Is the formula Ax Ey ( p(f(x),y) & -p(x,y) ) satisfiable? Prove it. Answer: ... 5b) Let f be a binary function symbol. Consider the two first-order interpretations I1 and I2: D_I1 = N (the natural numbers) f_I1(n,m) = n*m D_I2 = Z (the integers) f_I2(n,m) = n*m Write a formula F in first-order with equality (FOLE), with NO other function or predicate symbols than f and equality, such that F distinguishes I1 and I2, that is, such that F is true in one of I1 or I2 and false in the other. Give NO explanations. Hint: express "for every non-zero x there is another number y with the same square". But express "non-zero" using only f! Answer: ... ------------------------------------------------------------------------------------ Problem 6. (3 points). "The footbridge over the river" A sign at the beginning of the footbridge states the following: A. The passage of more than one person is not allowed simultaneously on the footbridge. B. If x and y are the same person and x is adult, then y is adult C. Minors will be accompanied by an adult. Prove in **FOL** that: D. Minors cannot cross the footbridge. Use these predicats: p(x): "x pass through the footbridge" a(x): "x is adult" e(x,y): "x and y are the same person" Answer: A. The passage of more than one person is not allowed simultaneously on the footbridge ... B. If x and y are the same person and x is adult, then y is adult ... C. Minors will be accompanied by an adult. ... D. Minors cannot cross the footbridge. ... the negation: -D. ... We have to see that the set of clauses: A. ... B. ... ... is unsatisfiable Applying resolution: 1. ... + ... ... with mgu(..., ...) = {...} 2. ... + ... ... with mgu(..., ...) = {...} ... ------------------------------------------------------------------------------------