Colorado State University

Recitation R9 - Inference Rules
Fall 2014

CS160: Foundations in Programming

The purpose of this lab is to:

Review

 The TA will review the following topics in recitation:

Problem set

Create a file called R9.txt and write your solution in it to each of the following problems, one at a time. When everyone has had a chance to go through the problems, your TA will show you how to work each problem correctly.

  1. Use truth tables to verify the equivalence:

    p ∧ F is equivalent to F

  2. Show the the following conditional statement is a tautology by using a truth table.

    (p ∧ q) → (p → q)

  3. Write the converse, contrapositive, and inverse of p → q.

    Solution:

For problem 4, you are not allowed to use all the laws in the Logic Sheet. You are allowed only the laws of Identity, Domination and Negation (from the bottom section), and only DeMorgan's Laws, Distributive Laws, Double Negation (from the middle section). You are not allowed the "Rules of Inference."
  1. Prove that
    p ∨ (¬p ∧ q) ≡ (p ∨ q)
    using only algebraic simplicfication. You must state the specific rule for each step.

    Solution:
    p ∨ (¬p ∧ q)
    ≡ (p ∨ ¬p) ∧ (p ∨ q)   Distributive Law (1st version)
    ≡ (true) ∧ (p ∨ q)       Negation Law
    ≡ (p ∨ q)                     Identity Law



For problems 5 and 6, prove the following, but now using the Rules of Inference from the Logic Sheet. As before, State the specific rule for each step.
  1. Given: Prove: q

    The problem as specified cannot be solved, since the Logic Sheet has no information about the ⊕ and none of the inference rules has anything about ↔ (though the Logical Equivalences section has the Biconditional Laws).

    So we allow you to use the Logical Equivalences as well as the other laws. But even that has nothing about ⊕, so we also give you the following equivalence rule about the ⊕ operator: (Call it XOR Definition)

    x ⊕ y ≡ (x ∧ ¬y) ∨ (¬x ∧ y)

    There are two alternative answers.

    Solution a:

    1. p ⊕ q axiom
    2. p ↔ r axiom
    3. ¬ r axiom
    4. p → r ∧ r → p Biconditional Laws (1)
    5. p → r Simplification (4)
    6. ¬p Modus Tollens (3, 5)
    7. (p ∧ ¬q) ∨ (¬p ∧ q) XOR Definition (1)
    ≡ ((p ∧ ¬q) ∨ ¬p) ∧ ((p ∧ ¬q) ∨ q) Distributive Law 1 (left-to-right)
    ≡ (p ∨ ¬p) ∧ (¬q ∨ ¬p) ∧ (p ∨ q) ∧ (¬q ∨ q)   Distributive Law 1, twice (left-to-right), and also commutative law four times)
    ≡ (¬q ∨ ¬p) ∧ (p ∨ q) Negation Law 1 (twice) and Identity Law 1 (twice)
    8. (p ∨ q) Simplification (last version of 7)
    9. q Disjunctive Syllogism (6, 8)



    Solution b:
    An alternative solution would use "common sense reasoning" and extend the disjunctive syllogism rule of inference to the &xor; case (this would be another theorem that you could prove separately). Or you could simply show that (x⊕y) →(x∨y), and then use disjunctive syllogism.
    1. p ↔ r axiom
    2. ¬ r axiom
    3. ¬ p definition of double implication (1, 2)
    4. p ⊕ q axiom
    5. q disjunctive syllogism (3, 4)

  2. Given: Prove: (q ∧ p)

    Solution:
    1. r → p axiom
    2. r axiom
    3. p modus ponens (1, 2)
    4. p → q axiom
    5. q modus ponens (3, 4)
    6. q ∧ p conjunction (3, 5)

Submit your R9.txt to RamCT to verify your attendance.
© 2014 CS160 Colorado State University. All Rights Reserved.