Homework 3: Logic Toolkit
Truth tables, first-order logic, CNF, unification, and resolution
hw3submission.pdf
Upload one PDF named hw3submission.pdf to Canvas. Include every requested intermediate step. A final expression without the supporting truth table, substitutions, or resolution steps will not receive full credit. No starter download is required for this written assignment.
Required work: complete Problems 1-5 below. The reference sheet at the end is supporting material, with no additional questions to submit.
1. Truth tables and classification
For each formula, construct the complete truth table and classify it as exactly one of the following:
- tautology: true under every truth assignment;
- contradiction: false under every truth assignment; or
- contingent: true under at least one assignment and false under at least one assignment.
Analyze these formulas:
- (P \lor Q) \rightarrow R
- \neg(P \lor Q) \leftrightarrow (\neg P \land \neg Q)
- ((P \rightarrow Q) \land (Q \rightarrow R)) \rightarrow (P \rightarrow R)
Include columns for the useful subexpressions, not only the final result.
2. First-order logic translation
Translate each sentence into first-order logic (FOL). State the domain and define every predicate or constant you introduce. Your domain must include all objects your encoding refers to, such as people and courses.
- Everyone who studies AI is intelligent.
- Some student loves logic but does not love probability.
- Every professor teaches at least one course.
Use quantifier scope and parentheses carefully. Equivalent, well-defined predicate names are acceptable.
3. Conversion to clause form
Convert each formula to conjunctive normal form (CNF) and give the final set of clauses. Show implication elimination, movement of negations, variable renaming or Skolemization when needed, and distribution into clauses. If a step is unnecessary, say so briefly.
- \forall x\, ((P(x) \lor Q(x)) \rightarrow R(x))
- \neg \exists y\, \forall x\, (\text{Loves}(x,y) \lor \text{Hates}(x,y))
Here P,Q,R are unary predicates, \text{Loves},\text{Hates} are binary predicates, and x,y are variables. For the second formula, explain which universal variables any fresh Skolem function depends on. Use the same Skolem term for every occurrence of the existential variable it replaces. In the final clause set, universal quantifiers may be left implicit.
Skolemization preserves satisfiability rather than logical equivalence in the original vocabulary. Label that step separately from equivalence rewrites.
4. Unification
Find a most general unifier (MGU) for each pair, or explain why no unifier exists. Show the bindings in the order you derive them, give the combined substitution at the end, and verify that applying it to both expressions makes them identical.
- P(A,x,f(y)) and P(A,B,f(z))
- \text{Knows}(\text{John},x) and \text{Knows}(y,\text{Bob})
The variables are x,y,z. The constants are A,B,\text{John},\text{Bob}. The symbol f is a unary function. The symbols P and \text{Knows} are predicates. Write bindings as x\mapsto t, meaning “replace x with term t.” Equivalent MGUs that differ only in variable renaming are acceptable.
5. Resolution proof
Use refutation resolution to prove that query Q follows from this knowledge base (KB). In this problem, P,Q,R are propositional atoms:
P \lor Q \neg P \lor R \neg R
Your proof must:
- negate the query;
- list the initial clause set;
- identify the parent clauses and resolved literal at every step; and
- end with the empty clause \square and explain why it establishes \text{KB}\models Q.
The symbols \square and \bot both denote the empty clause here. Either is acceptable. Keep the original clauses when adding a resolvent.
Presentation checklist
- Every variable and predicate is defined.
- Parentheses make quantifier and connective scope unambiguous.
- Each truth table includes all assignments exactly once.
- CNF work distinguishes a formula from its clause-set representation.
- The unifier is applied consistently to both expressions.
- The resolution proof states why deriving \square establishes entailment.
End of HW3. Submit your answers to Problems 1-5 and check the list above. Everything below is reference material, not an additional task.
Reference Sheet (Supporting Material)
Background
Propositional logic treats each symbol such as P or Q as one truth-valued statement. First-order logic adds objects, predicates, variables, and quantifiers. State a nonempty domain and use parentheses to make each quantifier’s scope clear.
| Form | Read as | Useful equivalence |
|---|---|---|
| \neg P | not P | flips the truth value |
| P\land Q | P and Q | true only when both are true |
| P\lor Q | P or Q | false only when both are false |
| P\rightarrow Q | if P, then Q | \neg P\lor Q |
| P\leftrightarrow Q | P exactly when Q | (P\rightarrow Q)\land(Q\rightarrow P) |
Classification: a tautology is always true, a contradiction is always false, and a contingent formula has both true and false assignments. A formula is satisfiable if at least one assignment makes it true. Both tautologies and contingent formulas are satisfiable.
Equivalence Laws
De Morgan’s laws:
\neg(P\land Q)\equiv\neg P\lor\neg Q, \qquad \neg(P\lor Q)\equiv\neg P\land\neg Q.
Quantifier negation:
\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).
OR over AND, the distribution used to form CNF:
X\lor(Y\land Z)\equiv(X\lor Y)\land(X\lor Z).
Clause-Form Workflow
- Eliminate \leftrightarrow and \rightarrow.
- Move negations inward with De Morgan’s laws, double negation, and quantifier negation.
- Rename bound variables to avoid collisions. For example, (\forall x\,P(x))\land(\exists x\,Q(x)) can use y in the second part.
- If moving quantifiers to the front, preserve scope: do not capture a variable that was free in another part of the formula.
- Skolemize each existential with a fresh constant or function. Record its dependencies on surrounding universal variables. This step preserves satisfiability.
- Distribute OR over AND.
- Write the result as a set of clauses, with universal quantifiers implicit. A clause is an OR of literals. The whole clause set requires all clauses to hold.
For instance, \forall u\,\exists v\,R(u,v) uses a fresh g(u) for v, while \exists v\,\forall u\,R(u,v) uses a fresh constant k.
Unification and Resolution
A substitution replaces variables with terms and applies consistently throughout each expression. An MGU avoids unnecessary bindings. The occurs check rejects a binding such as x\mapsto f(x) because the replacement contains x itself. Different constant symbols do not unify syntactically.
Resolution combines clauses containing one complementary pair. In FOL, first rename variables in different parent clauses apart if needed, then find a unifier for the atoms. Apply that substitution to the entire parent clauses, remove the complementary literals, and join the remaining literals with OR.
For a refutation proof, add the negated query to the KB. Deriving the empty clause shows that the KB together with the negated query is unsatisfiable:
\text{KB}\models\alpha\quad\Longleftrightarrow\quad \text{KB}\land\neg\alpha\text{ is unsatisfiable}.
The empty clause has no literals and is false. It is different from an empty clause set, which has no requirements and is true.