PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q1(b)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Propositional Logic, Rules of Inference & Predicate Logic

Question

Using rules of inference, show that the premises "If you send me an e-mail message, then I will finish writing the program," "If you do not send me an e-mail message, then I will go to sleep early," and "If I go to sleep early, then I will wake up feeling refreshed" lead to the conclusion "If I do not finish writing the program, then I will wake up feeling refreshed."

Solution

Propositional Formalization of Hypotheses and Conclusion: Define the atomic propositions:

The given premises are formalized as:

  1. Premise 1:
  2. Premise 2:
  3. Premise 3:

The desired conclusion to deduce is:

Formal Deduction Using Rules of Inference: We derive the conclusion step by step using standard rules of inference:

  1. (Premise 1)
  2. (Contrapositive of line 1: )
  3. (Premise 2)
  4. (Hypothetical Syllogism from lines 2 and 3: )
  5. (Premise 3)
  6. (Hypothetical Syllogism from lines 4 and 5)

Thus, the premises validly lead to the conclusion: "If I do not finish writing the program, then I will wake up feeling refreshed."

Answer:

Formalizing , , and : Taking the contrapositive of premise 1 gives . Applying hypothetical syllogism with yields , and a second hypothetical syllogism with derives the conclusion .

All past exam questions for Theory of Computation