# Computer Science Mojo

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

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

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

### 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
• 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
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