CSE 2315 Exam Notes – Part I

Equivalence Rules

• RVS is equivalent to SVR (Commutative - comm).
• RΛS is equivalent to SΛR (Commutative).
• (R V S) V Q is equivalent to R V (S V Q) (Associative - assoc).
• (R Λ S) Λ Q is equivalent to R Λ (S Λ Q) (Associative).
• De Morgan’s Laws state that (R V S)′ is equivalent to R′ Λ S′ and (R Λ S)′ is equivalent to R′ V S′.
• R→S translates to R′ V S (Implication - imp).
• The double negation states R is equivalent to (R′)′ (Double negation - dn).
• P↔Q is defined as (P → Q) Λ (Q → P) (Equivalence - equ).

Inference Rules

• From R and R → S, S can be derived (Modus ponens - mp).
• From R → S and S′, R′ can be derived (Modus tollens - mt).
• R and S lead to RΛS (Conjunction - con).
• RΛS allows simplification to R or S (Simplification - sim).
• From R, RVS can be derived (Addition - add).

Additional Inference Rules

• P → Q and Q → R allow derivation of P→R (Hypothetical syllogism - hs).
• From P V Q and P′, Q can be derived (Disjunctive syllogism - ds).
• Contraposition allows the transformation of P→Q to Q′ → P′ (Contraposition - cont).
• Self-reference: from P, one can derive PΛP (Self-reference - self).
• For (P Λ Q) → R, the equivalent form is P → (Q → R) (Exportation - exp).
• P and P′ lead to Q (Inconsistency - inc).
• Distributive laws: P Λ (Q V R) is equivalent to (P Λ Q) V (P Λ R) and P V (Q Λ R) equals (P V Q) Λ (P V R).

Inference Rules – Instantiation/Generalization for Quantifiers

• Universal Instantiation allows P(t) to be derived from (∀x)P(x), where t is a variable or constant symbol, ensuring t is not within a quantifier's scope.
• Existential Instantiation infers P(a) from (∃x)P(x) using a constant symbol not already referenced in the proof sequence.
• Universal Generalization states that if P(x) is true, then (∀x)P(x) holds, under specific conditions about free variables.
• Existential Generalization allows deriving (∃x)P(x) from P(x) or P(a), ensuring x does not appear in P(a).