1. (10 points) Models.
True (Trivial because variable assignment for a ground sentence is empty, i.e. no variables).
False (the new assignment of variables may make the scope of the sentence false, could be free variables still)
Note that p is true of nothing. So, ¨p(x) ∨ q(x) is true for any x, and p(x) ∧ q(x) is false for any x.
Therefore, both sides of the biconditional are true for any x, and the sentence is true in this interpretation.
Everything satisfies q(x), so the left-hand side of the biconditional is true. Everything is true of p and q, so the right-hand side is false. The biconditional is therefore false, making the sentence false in this interpretation.
2. (10 points) Validity, Contingency, Unsatisfiability. For each of the following sentences, say whether it is valid, contingent, or unsatisfiable. Note, by convention, the universe of discourse is always non-empty. You do not need to justify your answers.
Valid. This should be intuitively clear. It's also an instance of the UI axiom.
Valid. Use the same reasoning for part 2, except that we only need p(x) to be true for one x, which is guaranteed if p(x) is true for some variable assignment. And if p(x) is false for that assignment, the implication is true anyhow.
Contingent. Clearly you can find interpretations that make this true under all assignments, and others that make it false under all assignments. (Note that no interpretation can make it true for some but false for other variable assignments. This is because there are no free variables.)
Valid. This should be intuitively clear. There are no free variables, so we don't need to worry about assignments. If the left-hand side is false, the implication is trivially true. If the left-hand side is true, then for every x in the universe, p(x) holds. Furthermore, since the domain is by definition non-empty, we know that there will be at least one object such that p(x) is true, thus making the right-hand side true.
Contingent. Consider:
Unsatisfiable. Note that the sentence is of the form φ ∧ φ, with φ = ∀x. (p(x) ⇒ q(x)).
3. (10 points) Entailment. Let Γ be a set of Relational Logic sentences, and let φ and ψ be individual Relational Logic sentences. For each of the following claims, state whether it is true or false. Briefly explain your answer.
True. Universal instantiation, basically.
True. Universal generalization, essentially.
True. If Γ entails φ ∧ ψ, then every model of Γ must be a model of φ ∧ ψ. But by the semantics of conjunction, φ ∧ ψ is true in an interpretation if both φ and ψ are true in that interpretation. But this is the desired result. (Note also that this is the and-elimintation rule.)
False. Consider Γ=∅, φ = p(a) and ψ = p(a). Then φ ∨ ψ is true in all interpretations, but neither φ nor ψ is true in all interpretations.
True. Suppose that i is an interpretation satisfying
∀x. φ. By definition, for all assignments v, t(iv)
(∀ x. φ) is true. By the universal quantifier semantics,
t(iv')(φ) is true for all assignments v'; therefore i
satisfies φ. QED.
It is not sufficient to merely state, for instance, that "every
interpretation that satisfies the premise also satisfies the conclusion",
because that is simply translating the meta-sentence into English.
True. (See 4a.)
False. Consider φ=p(x), |i| = { 0,1 } and i(p) = {0} . Then ¬∀x. p(x) is true in i (since 1 is not in p) but ¬p(x) is false under i and the assignment v(x) = 0; therefore i is not a model for ¬p(x) even though it was for ¬∀x. p(x).
True. Suppose that i is a model of Γ. Then because Γ |= φ, i is also a model of φ. Therefore it is a model of Γ ∪ { φ } . (If it models them both separately, it has to model them together.) Hence, because Γ ∪ { φ} |= ψ, i is a model of ψ.
False. Consider: Γ = p(a) ∧ p(a). Then Γ entails anything.
False. There could be objects in the universe for which we have no ground term. Consider for instance Γ = {p(a)}. Clearly Γ |= p(a). Let's consider the truth of Γ |= ∀x. p(x). Since Γ entails ∀x. p(x), it must be the case that every model of p(a) is a model of ∀x. p(x). But consider: |i| = {1,2}, i(a) = 1, i(p) = {1}. This is a model of p(a), but clearly not of ∀x. p(x).
4. (10 points) Entailment and Implication.
True. Suppose that i is an interpretation satisfying φ. By definition of satisfaction, for all assignments v, t(iv) (φ) is true. We want to check that ∀x. φ is true in i.
∀x. φ is true in i iff, for every assignment v, t(iv)(∀x. φ) is true. t(iv)(∀x. φ) is true iff φ is true for all versions v' of v in which we vary the value of x. But for any such version, we know that t(iv')(φ) is true by the above paragraph: t(iv)(φ) holds for every variable assignment v, and so in particular v'. Therefore, t(iv)(∀x. φ) is true; hence, ∀x. φ is true in i.
Therefore, whenever i is a model of φ, it is a model of ∀x. φ.
Note that it is not sufficient to merely state, for instance, that "every interpretation that satisfies the premise also satisfies the conclusion", because that is simply translating the meta-sentence into English.
Contingent. This might be surprising. Recall that for a valid sentence, every interpretation is a model. A model is an interpretation that makes the sentence true under all variable assignments. Consider the universe { 0, 1 } with p = {0}. Then, under variable assignment x=0, the antecedent is true but the consequent is false (since p is not true for 1).
5. (10 points) Skolemization and Herbrandization.
We show both directions of the "if and only if":
P.E.S. sat. → Skolemization sat.
Assume that some purely existential sentence is satisfiable. Then, we have that ∃x1. ... ∃xn. φ is true for some quantifier-free sentence φ. Consider x1. By definition of existential satisfaction, there is some object o in the universe such that ∃x2. ... ∃ xn. φ where x1 has been replaced by o. Let o1 be a new constant in the language (i.e., a constant that has no restrictions due to the current interpretation). Interpret o1 such that i(o1) = o. We have skolemized x1 and showed that satisfaction holds. We may continue "removing" existential quantifiers from the sentence, picking new constants at each iteration, and after they have all been removed, we are left with the Skolemization of the original sentence, which is satisfied by construction. QED.
Skolemization sat. → P.E.S. sat.
Assume that some quantifier-free sentence φ is satisfiable. For each constant term ci appearing in φ, replace it with a new variable and add "&exists;xi." to the beginning of the sentence. Note that every time we do this, &exists;xi. φ remains true because we may select xi = ci by construction. Since we may repeat this process until all constants are gone, we have shown that from a satisfiable Skolemized sentence we may go to a satisfiable purely existential sentence. QED.
Let c be a new constant that has no restrictions placed upon it by the current interpretation i (i.e., c is a new constant in the language). Interpret c such that i(c) = o for some arbitrary object o from the domain. Assume that we show p(c). Since we picked i(c) arbitrarily, we may pick another object. In fact, we may pick any object, and p(c) will be true (since we assumed no constraints on c). Therefore, we may state that p(x) is true for every object x, or in other words, ∀x. p(x).
This is what is meant when we say "without loss of generality": we picked something arbitrarily but could have picked anything else such that the dependent proof still holds. Therefore, we have not lost anything by temporarily picking some object, and can still conclude something about the entire set of objects based on our proof.
6. (10 points) Formal Proof. From these premises:
Conclusion:
using only the MP, MT, AI, AE, UI, UG, EI, EG, DN, and NI. (DN is double negation: from the sentence ¬¬φ, you may infer the sentence φ. NI is negation introduction: from φ, infer ¬¬φ.)
| Step | Proof | Justification |
|---|---|---|
| 1 | Ax:(logician(x) => coffee(x)) | Premise |
| 2 | Ax:(~theorems(x) => ~coffee(x)) | Premise |
| 3 | Ex:logician(friend(x)) | Premise |
| 4 | logician(friend(mike)) | Existential Instantiation: 3 |
| 5 | logician(friend(mike)) => coffee(friend(mike)) | Universal Instantiation: 1 |
| 6 | coffee(friend(mike)) | Modus Ponens: 5, 4 |
| 7 | ~~coffee(friend(mike)) | Negation Introduction: 6 |
| 8 | ~theorems(friend(mike)) => ~coffee(friend(mike)) | Universal Instantiation: 2 |
| 9 | ~~theorems(friend(mike)) | Modus Tolens: 8, 7 |
| 10 | theorems(friend(mike)) | Double Negation: 9 |
| 11 | logician(friend(mike)) & coffee(friend(mike)) | And Introduction: 4, 6 |
| 12 | (logician(friend(mike)) & coffee(friend(mike))) & theorems(friend(mike)) | And Introduction: 11, 10 |
| 13 | Ex:((logician(x) & coffee(x)) & theorems(x)) | Existential Generalization: 12 |
7. (10 points) Formal Proof. Give a formal proof of the tautology ∀x.p(x) ⇒ ∀y.p(y) using the Mendelson system as given in Mendelson's book.
| Step | Proof | Justification |
|---|---|---|
| 1 | Ax:p(x) => p(y) | Universal Instantiation |
| 2 | Ay:(Ax:p(x) => p(y)) | Universal Generalization: 1 |
| 3 | Ay:(Ax:p(x) => p(y)) => (Ax:p(x) => Ay:p(y)) | Universal Distribution |
| 4 | Ax:p(x) => Ay:p(y) | Modus Ponens: 3, 2 |
Using mendelson system as given in the lectures, we have the following proof:
| Step | Proof | Justification |
|---|---|---|
| 1 | Ax:p(x) => p(y) | Universal Instantiation |
| 2 | (Ax:p(x) => p(y)) => Ay:(Ax:p(x) => p(y)) | Universal Generalization |
| 3 | Ay:(Ax:p(x) => p(y)) | Modus Ponens: 2, 1 |
| 4 | Ay:(Ax:p(x) => p(y)) => (Ay:Ax:p(x) => Ay:p(y)) | Universal Distribution |
| 5 | Ay:Ax:p(x) => Ay:p(y) | Modus Ponens: 4, 3 |
| 6 | (Ay:Ax:p(x) => Ay:p(y)) => (Ax:p(x) => (Ay:Ax:p(x) => Ay:p(y))) | Implication Introduction |
| 7 | Ax:p(x) => (Ay:Ax:p(x) => Ay:p(y)) | Modus Ponens: 6, 5 |
| 8 | (Ax:p(x) => (Ay:Ax:p(x) => Ay:p(y))) => ((Ax:p(x) => Ay:Ax:p(x)) => (Ax:p(x) => Ay:p(y))) | Implication Distribution |
| 9 | (Ax:p(x) => Ay:Ax:p(x)) => (Ax:p(x) => Ay:p(y)) | Modus Ponens: 8, 7 |
| 10 | Ax:p(x) => Ay:Ax:p(x) | Universal Generalization |
| 11 | Ax:p(x) => Ay:p(y) | Modus Ponens: 9, 10 |
8. (10 points) Relational logic structures.
Ans: Use the symbol p to denote the binary relation in the structure. The two are distinguished by:∃ xyz.(p(x,y) & p(y,z))
Ans: Use the symbol p to denote the binary relation in the structure.
Let the two structures be s1 and s2.
Let i1 and i2 be the associated interpretations.
Under every version of every variable assignment, every relational sentence (p(x,y), p(x,x)) evaluates to true in both structures.
Structural induction 1:
Base case: Let i be i1 or i2. For any equality-free relational sentence A, tiv(A) = tiu(A) for any variable assignments v and u compatible with A. (tiv(A) is always true for any variable assigment)
Induction step: Let A,B be any equality-free FOL sentence.
Induction hypothesis: Let i be i1 or i2. Assume that for C = A or B, for any variable assigments v and u, tiv(C) = tiu(C).
Case: D \in {(A => B), ~A, A or B, A and B}.
For any variable assigments v and u, tiv(D) = tiu(D). (straightforward)
Case: D \in {Ex.A, forall x.A}
For any variable assigments v and u, tiv(D) = tiu(D). (straightforward)
Conclusion:
Lemma (*): Let A be any equality-free FOL sentence. Let i \in {i1,i2}. Let v,u be any compatible variable assigment. tiv(A) = tiu(A).
Structural Induction 2:
Base case: Let A be any equality-free relational sentence.
For any variable assigments v and u, ti1v(A) = ti2u(A). This is the case because, both are always true.
[Assuming v is compatible with A,i1 and u is compatible with A,i2]
Induction step: Let A,B be any equality-free FOL sentence.
Induction hypothesis: Assume that for C = A or B,
for any variable assigments v and u, ti1v(C) = ti2u(C).
Case: D \in {(A => B), ~A, A or B, A and B}.
For any variable assigments v and u, ti1v(D) = ti2u(D). (straightforward)
Case: D \in {Ex.A, forall x.A}
For any variable assigments v and u,
ti1v(D)
= ti1v(A) (by (*))
= ti2u(A) (by induction hypothesis)
= ti2u(D) (by (*))
Conclusion:
Let A be any equality-free FOL sentence. For any variable assigments v and u, ti1v(A) = ti2u(A).
Ans: Use the symbol product to denote the 3-ary relation in the structure. The two are distinguishde by: ∀x.∃y.product(x,y,y)
9.
10. (10 points) Decidability.
Let G denote the set of first-order logic sentences without variables or equality (relational constants, object constants, and function constants remain). Show that the entailment problem in G (that is, the problem of determining whether a sentence φ in G is entailed by a finite set of sentences Ψ contained in G) is decidable. Describe a procedure for deciding the problem and show the procedure is correct.
Ans: Here's a procedure for deciding it: 1. Consider assigning to each relational atom appearing in the input sentences one of {T, F}. Using the semantics of logical connectives, evaluate the truth value of Ψ and the truth value of φ under the assignment. If in every assignment, φ evaluates to true if all sentences in Ψ evaluate to true, then answer "YES". Otherwise answer "NO".
Correctness:
Suppose Ψ does not entail φ. Then there exists a first-order logic interpretation i which satisfies Ψ but not φ. Then the assignment {(s <- i(s)) : s a relational atom in Ψ and φ} makes Ψ evaluate to true and φ false by first-order logic semantics. This assignment would be checked in the given procedure and so the procedure answers correctly "NO".
Suppose the procedure answers "NO". Then there exists a truth assignment ta on the relational atoms in Ψ and φ such that Ψ evaluates to true and φ evaluates to false. Then there exists a first-order interpretation i that satisfies Ψ but not φ. For example, let i be as follows: U={t: t is a ground term in Ψ and φ}, i(c) = c for each object constant c, i(f(t)) = f(i(t)) for each element of U, i(p) = {o in U : ta(p(o)) = T} for each relational constant p.
Hence the procedure answers "NO" if and only if Ψ does not entail φ.
State whether logical entailment for existential logic is decidable. Explain in one or two sentences.
We reduce the entailment problem in full first-order logic to existential logic. We do this by replacing functions with new predicates while preserving the meaning of each sentence. Replace functions with new predicates and then add a single value restriction on the predicates.For example, Ax Ay p(f(x,y)) => p(f(y,x)) would turn into Ax Ay ((p(z1) => p(z2)) & p_f(x,y,z1) & p_f(y,x,z2) & Au1 Au2 Au3 Au4 (p_f(u1,u2,u3) & p_f(u1,u2,u4) => u3=u4 ))). One can argue semantically that the meaning is preserved and that Psi |= phi iff T(Psi) |= T(phi), where T is the transformation described.
Hence, if existential logic were decidable, then first-order logic is decidable, which we know to be false.
Ans: Not decidable. Every instance of the logical entailment problem in first-order logic can be reduced to the satisfiability of a first-order logic sentence. (For instance reduction in the propositional case. introduced with the propositional resolution method holds in the first-order case. Same argument applies. ) Suppose there was a procedure for deciding this problem, then there would be a procedure to decide logical entailment in first-order logic, that would contradict a theorem.