Computer Science Mojo

~ David's Notes on coding, software and computer science




Post

What are the types of Proofs methods, Rules of inference, Propositional equivalence

Category: Math     Tag: Discrete Math   Proofs  
By: David     On: Sat 05 September 2015      Pageviews: 12

Confusing terminology aside, this is a summary of the most important stuff needed for doing proof problems in Discrete Mathematics

Reading

Simple Definition

  • Proof methods: ways of augment
  • Rules of inference: ways of transforming the premise into a conclusion (Premise → Conclusion)
  • Propositional equivalence: propositions that are the equal though they look different (A \( \Leftrightarrow \) B)

1. Proof methods

  • Direct: p → q
  • Construction: example
  • Controposition
  • Contradiction
  • Induction
    • Weak
    • Strong
    • Well ordering

2. Rules of inference

(Premise → Conclusion)

Name Premise Conclusion
Modus ponens p ∧ ( p → q ) q
Modus tollens ¬q ∧ ( p → q ) ¬p
Hypothetical syllogism ( p → q ) ∧ ( q → r ) p → r
Disjunctive syllogism ( p ∨ q ) ∧ ¬p q
Addition p p ∨ q
Simplification p ∧ q p
Conjunction ( p ) ∧ ( q ) p ∧ q
Resolution ( p ∨ q ) ∧ ( ¬p ∨ r ) q ∨ r

3. Propositional equivalence

(A \( \Leftrightarrow \) B)

Name A B
Controposition p → q ¬q → ¬p
Implication p → q ¬p ∨ q
Double Negation ¬¬p p
Distributive p ∨ ( q ∧ r ) p ∧ ( q ∨ r )
( p ∨ q ) ∧ ( p ∨ r ) ( p ∧ q ) ∨ ( p ∧ r )
De Morgan's Law ¬ ( p ∧ q ) ¬ ( p ∨ q )
¬p ∨ ¬q ¬p ∧ ¬q
Identity p ∨ False p
p ∧ True p
Domination p ∧ False False
p ∨ True True
Idempotent p ∧ p p
p ∨ p p
Absorption p ∨ ( p ∧ q ) p
p ∧ ( p ∨ q ) p