Fall 2014

The purpose of this lab is to:

- Review basics of propositional logic
- Using truth tables to prove statements and equivalences
- Write mathematical proofs using the Rules of Inference

- Truth tables and using them to prove statements and equivalences
- The terms
*tautology*,*contradiction*, and*contingency*. - Implication: p → q, its truth table, and its negation ¬(p → q)
- The
*converse*,*contrapositive*, and*inverse*of p → q. - Writing a mathematical proof for the following:
- Given:
- p ∨ q
- p → r
- ¬r
- Prove: q

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.

- Use truth tables to verify the equivalence:
p ∧ F is equivalent to F

- Show the the following conditional statement is a tautology by
using a truth table.
(p ∧ q) → (p → q)

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

**Solution:**

- Converse: q → p
- Contrapositive: ¬q → ¬p
- Inverse: ¬p → ¬q

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."

- 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.

- Given:
- p ⊕ q
- p ↔ r
- ¬ r

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)

- Given:
- p → q
- r → p
- r

**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)