Ein Aspekt der Untersuchungen der mathematischen Logik ist das Studium der Ausdrucksstärke von formalen Logiken und formalen Beweissystemen. Eine Möglichkeit die Komplexizität solcher Systeme zu messen, besteht darin, festzustellen was damit bewiesen oder definiert werden kann.
Früher wurde die mathematische Logik auch symbolische Logik (als Gegensatz zur philosophischen Logik) genannt, wobei dieser Name mittlerweile nur noch für gewisse Aspekte der Beweistheorie verwendet wird.