PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q3

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Propositional Logic, Rules of Inference & Predicate Logic

Question

Using principle of resolution show that the hypothesis "If it is raining then, Prem has his umbrella,". "Prem does not have his umbrella or he does not get wet,". "It is raining or Prem does not get wet" imply that " Prem does not get wet."

Solution

Propositional Formalization and Conversion to CNF Clauses: Define the atomic propositional variables:

Translate the given hypotheses (premises) into propositional logic:

  1. Premise 1: "If it is raining then Prem has his umbrella" .
  2. Premise 2: "Prem does not have his umbrella or he does not get wet" .
  3. Premise 3: "It is raining or Prem does not get wet" .

Conclusion to establish: "Prem does not get wet" .

Resolution Refutation Execution: In proof by resolution refutation, we negate the conclusion and show that the conjunction of all premises with the negated conclusion yields a contradiction (the empty clause ):

Negated conclusion: .

List of input clauses:

Derivation steps:

  1. Resolve with on literal :
  1. Resolve with on literal :
  1. Resolve with on literal :
  1. Resolve with on literal :

Since the set of clauses is unsatisfiable, the conclusion ("Prem does not get wet") is logically entailed by the hypotheses.

Answer:

By negating the conclusion to obtain clause and resolving sequentially with , , and , we derive the resolvents , , , and finally the empty clause . Thus, the premises validly imply that Prem does not get wet.

All past exam questions for Theory of Computation