A.1 Mathematical logic 101
Logic and clear thinking lie at the very foundations of mathematics. But what are those? How would you explain what “logic” is?
Our thinking processes are formalized by the field of mathematical logic. In logic, we work with propositions, that is, statements that are either true or false. “It is raining outside.” “The sidewalk is wet.” These are both valid propositions.
To be able to reason about propositions effectively, we often denote them with roman capital letters, such as
Each proposition has a corresponding truth value, which is either true or false. These are often abbreviated as 1 and 0. Although this seems like no big deal, finding the truth value can be extremely hard. Think about the proposition
This is the famous P = NP conjecture, one of the longest-standing unsolved problems in mathematics. The statement is easy to understand, but solving the problem (that is, finding the truth value of the corresponding...
