ex1_notes.pdf

CSE 2315 Exam Notes – Part I Equivalence Rules Expression Equivalent to Abbreviation for rule RVS SVR Commutative - comm RΛS SΛR...

CSE 2315 Exam Notes – Part I Equivalence Rules Expression Equivalent to Abbreviation for rule RVS SVR Commutative - comm RΛS SΛR (R V S) V Q R V (S V Q) Associative- assoc (R Λ S) Λ Q R Λ (S Λ Q) (R V S)′ R′ Λ S′ De Morgan’s Laws (R Λ S)′ R′ V S′ De Morgan R→S R′ V S Implication - imp R (R′)′ Double negation- dn P↔Q (P → Q) Λ (Q → P) Equivalance - equ Inference Rules From Can Derive Abbreviation for rule R, R → S S Modus ponens- mp R → S, S′ R′ Modus tollens- mt R, S RΛS Conjunction-con RΛS R, S Simplification- sim R RVS Addition- add Addl. Inference Rules From Can Derive Name / Abbreviation P → Q, Q → R P→R Hypothetical syllogism- hs P V Q, P′ Q Disjunctive syllogism- ds P→Q Q′ → P′ Contraposition- cont Q′ → P′ P→Q Contraposition- cont P PΛP Self-reference - self PVP P Self-reference - self (P Λ Q) → R P → (Q→ R) Exportation - exp P, P′ Q Inconsistency - inc P Λ (Q V R) (P Λ Q) V (P Λ R) Distributive - dist P V (Q Λ R) (P V Q) Λ (P V R) Distributive - dist  Inference Rules – Instantiation/Generalization for Quantifiers From Can Derive Name / Abbreviation Restrictions on Use (∀x)P(x) P(t) where t is a variable Universal Instantiation- ui If t is a variable, it must not fall within the scope or constant symbol of a quantifier for t (∃x)P(x) P(a) where a is a Existential Instantiation- ei Must be the first rule used that introduces a constant symbol not previously used in a proof sequence P(x) (∀x)P(x) Universal Generalization- ug P(x) has not been deduced from any hypotheses in which x is a free variable nor has P(x) been deduced by ei from any wff in which x is a free variable P(x) or P(a) (∃x)P(x) Existential Generalization- eg To go from P(a) to (∃x)P(x), x must not appear in P(a)