Mathematics : How to Prove Things

From bitrary
Jump to: navigation, search


This section is TOTAL CRAP that needs to be rewritten. Sorry.

Introduction

The activity called "proving" is always ultimately based on Propositional Logic. The scheme is that there is a disjunction of formulae, like , $X_1 \vee X_2 \vee ... \vee X_n$ where $X$ denotes a formula, and then a "complete proof" shows that according to "axioms" (tautologies) all of the formulae, $X$, are true. Sometimes only one of the formulae, $X$, is shown to be true, because that's enough to show that the whole disjunction, the $X_1 \vee X_2 \vee ... \vee X_n$, is true, and it might be difficult to show that the other formulae within the disjunction have a value of "true".

The formulae, $X$, can be very complex and are usually derived from an original problem, which might, but does not have to be, a propositional formula.

The propositional parts of proofs are automated by "theorem provers" (SAT solvers), which take propositional formula $X$ as an input and try to find, if there exists any set of boolean constants that guarantee the formula $X$ to have a boolean value of "true".


Some Classical Heuristics

Find at Least one Instance of a Contra Example

Theorem (tautology) candidate: "All cats on planet Earth are white."

To show that the theorem candidate is not a tautology, an existence of a single non-white cat must be shown.