CS157: Computational Logic

Fall 2010

Assignment 1, Due Thursday October 7 at 11:59pm

Please see the course website for collaboration policy, and regrade policy. You may use Logica with acknowledgement. You may work in groups of up to three. Acknowledge all aid and collaboration. Please abide by the Honor Code.

Submission Instructions: Mail your assignment to cs157assignments1011@gmail.com. No hard copies will be accepted.

File Name instructions: Please name your files as [first name]-[lastname]-[assignment #].[file format]. If you are John Doe submitting Assginment 1, you should name your file John-Doe-1 .

1. Which of the following sentences are valid, contingent, or unsatisfiable? [10 points]
(no explanation required)

(a)      p => (q => p)

(b)      (q => p) => p

(c)      (~p => ~q) => (q => p)

(d)      (p => (q => r)) => ((p => q) => (q => r))

(e)      (((p ^ q) <=> p) => q)

(f)      ((p v (p ^ q)) => (p ^ (p v q)))

(g)      (((p v q) ^ (~q v r)) => (p v r))

(h)      (((p ^ q) ^ (~q v r)) => (p ^ r))

(i)      ((p <=> q) <=> r) <=> ((p <=> q) ^ (q <=> r))

(j)      ((p ^ q => r) ^ (p ^ ~q => r)) <=> (p => (q <=> r))

2. Entailment [10 points]

Let Γ and Δ be sets of sentences in Propositional Logic, and let φ and ψ be individual sentences in Propositional Logic. State whether each of the following statements is true or false. No explanation necessary.

(a)      If Δ |= φ and Δ|= ψ, then Δ |= (φ⇔ψ).

(b)      Δ |= (φ⇒ψ) if and only if Δ∪{φ} |= ψ.

(c)      If Γ |= φ and Δ |= φ, then Γ∪Δ |= φ.

(d)      If Γ |= φ and Δ |= φ, then Γ∩Δ |= φ.

(e)      If Γ |= (φ⇒ψ) and Δ |= (ψ⇒φ),then Γ∩Δ|= (φ⇒ψ)∨(ψ⇒φ).

3. Axiom schemata [10 points]

Recall Mendelson's axiom schemata.

φ => (ψ => φ)

(φ => (ψ => χ)) => ((φ => ψ) => (φ => χ))

(¬φ => ψ) => ((¬φ => ¬ψ) => φ)

In his book Introduction to Mathematical Logic, Mendelson asserts that the following schema (called contraposition) holds in this system.

(¬φ => ¬ψ) => (ψ => φ)

Moreover, he claims that, if contradiction realization (the third schema above) is replaced by this schema, the set of sentences that can be proved remains unchanged.

(a)      Show that contraposition follows from Mendelson's original axioms. In other words, show that any instance of of the contraposition axiom scheme must be provable using the original Mendelson Axiom Schemata. Hint: Use the deduction theorem.

(b)      Using the modified set of axiom schemata, show that there is a proof of ((¬p ⇒ p) ⇒ p). You may use the deduction theorem and the chaining theorem in your argument. (The chaining theorem states that, if there is a proof of (p ⇒ q) and a proof of (q ⇒ r), then there is a proof of (p ⇒ r).)

4. Interpretations [8 points]
Are the following arguments valid? (No explanation is required for valid sentences. If an argument is not valid, provide a counter-example)

(a)     If A is a knight, then B is a knight. If C is a knave, then B is a knight. Therefore, if A is a knight or C is a knave, then B is a knight.

(b)     If A is a knave, then B is a knave. If C is a knight, then B is a knave. Therefore, if A is a knave and C is a knight, then B is a knave.

(c)     If Sam was at the fair, then his father was negligent or his mother was not at home. If his mother was not at home, then his father was not negligent. His mother was at home. Therefore, Sam was at the fair.

(d)     If the initialization is correct and the loop terminates, then the required output is obtained. The output has been obtained. Therefore, if the initialization is correct, the loop must terminate.

5. Resolution [10 points]
Given the following, can you prove that the unicorn is mythical? How about magical? Horned?

If the unicorn is mythical, then it is immortal. But if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned. Formalize this problem in propositional logic and solve it using Resolution.

6. Propositional Proof [10 points]

Give a formal proof of the sentence p from the single premise ~~p using ONLY Modus Ponens and the standard axiom schemata (II / ID / CR). Any other proof shall receive 0 credit.

7. Resolution step [10 points]

In the following questions, a set of premises is given in clausal form. In each question, give all the resolvents that may be obtained using exactly one resolution step from the set of premises. If there are no such resolvents, write "none".

  1. Premises: { {p,q,~r}, {r,p,s} }
  2. Premises: { {~p,q}, {r,q,s} }
  3. Premises: { {p,q,r}, {r,~s, ~t} }
  4. Premises: { {~q, q} }
  5. Premises: { {~p,q,r}, {p,~q,~r} }

8. Discover the Gold! [12 points]

Three boxes are presented to you. One contains gold, the other two are empty. Each box has imprinted on it a clue as to its contents; the clues are:

[Box 1] "The gold is not here"
[Box 2] "The gold is not here"
[Box 3] "The gold is in Box 2"

Only one clue is true; the other two are false. Which box has the gold? Formalize the puzzle in PL and find the solution using a truth table. (otherwise you shall receive 0 credits)

9. Davis-Putnam procedure [10 points]

(a)     Show that, if we remove tautology elimination, the Davis-Putnam algorithm can, in one step (one iteration of the outer-most loop), create more than (n/2)2 resolvents, where n is the number of input clauses for that step. Note: it is sufficient to show one input instance on which this happens.

(b)     Show that, with tautology elimination, the Davis-Putnam algorithm generates at most (n/2)2 resolvents on each step.

10. Horn clauses [10 points]

Recall from lecture 4 the definition of a Horn clause.

(a)     Given a set of clauses C such that each clause in C contains at most one negative literal. C may not be Horn. Describe a procedure which takes C as input and outputs a set D of Horn clauses such that C is satisfiable if and only if D is satisfiable. Additionally, the procedure must not introduce new propositional constants. Furthermore, the procedure must have a worst-case running time (in terms of the sum of the lengths of the clauses in C) that is at most polynomial.

(b)     Given a set of clauses C as input, does your procedure always give an output set of clauses D that is logically equivalent to C? That is, treating C and D as sentences, is it the case that |= (C⇔ D)? Justify briefly.

Feedback (Optional) [0 points]

  1. Was this problem set too easy, too hard, or somewhere in between? Rank 1-10 with 1 being way too easy and 10 being way too hard.
  2. How much time did you spend on this assignment?
  3. Did you use Logica? Was it useful?
  4. Other comments.

Back to course page