Example theorems:
Complexity of proof derivations:
that is to say: there exists a decision procedure (algorithm)
s.t. it is always possible to prove or disprove a theorem
in finite time. However, the algorithmic complexity may
be exponential in the size of problem (e.g. truth tables).
that is to say: there exists a decision procedure s.t. it is possible
to demonstrate inconsistency in finite time, but the procedure
may not terminate if the set of sentences is consistent.
| Previous slide | Next slide | Back to first slide | View graphic version |