What are the types of Proofs methods, Rules of inference, Propositional equivalence
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
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 |