---

4.1 Homework 0

                        Homework Assignment 0
                               CS 389r
                         Unique Number: 53119
                             Fall, 2021

                       Given:     August 26, 2021
                        Due:    September 7, 2021

The lecture notes for this class contains over 100 problems. We will address many of these problems during the course of this semester. The student who eventually solves all of these problems will be a successful student.

Part 1:

To refresh your memory (and reclaim your skills) at constructing proofs, prove the following propositional formulas are theorems (or show why they are not). You may use the equation sheet vega-equations-new.pdf, if that helps.

1. Prove: p /\ (p \/ q) ≡ p
2. Prove: ¬(p => q) ≡ ¬ q => ¬ p
3. Prove Monotonicity of \/ : (p => q) => (p \/ r => q \/ r)
4. Prove Pierce formula: ((p => q) => p) => p ≡ ¬ p \/ p
5. Prove Case analysis (3 cases): (4.6)   (p \/ q \/ r) /\ (p => s) /\ (q => s) /\ (r => s) => s

Part 2:

Prepare solutions for problems 1, 2, 3, 4, and 5 from the lecture notes.

Your solutions may be prepared either by hand or using a text editor. If prepared by hand, make sure that your hand writing is legible.