There are (roughly) two ways to make sense of the world: the proof and the experiment.

Proofs are the language of mathematics and are rooted in logic, the subject of this chapter. Logic studies the rules that govern how we can draw conclusions from premises.

Experiments are the language of science and are rooted in probability theory, the subject of the next chapter. Probability theory studies the rules that govern how we can draw conclusions from evidence¹.

Logic and probability theory codify what it means to reason. As such, they’ve been the basis of artificial intelligence since day one. Since that time, the field has shifted its attention more towards probability theory and away from logic. Today’s state-of-the-art AI systems are not the symbolic systems of the past.

But even if current ML techniques scale to full generality and explicit logical reasoners prove to be unnecessary, logic remains central to understanding much of the subsequent mathematics we’ll need to study AI (in particular, computational complexity theory). It’s also key to alignment agendas tackling foundational questions of agency, intelligence, self-reference, causality, and reflective stability.

Propositional Logic

Propositional logic begins with propositions, which are statements that can be either true or false, and combines them using logical operators. The most basic operators are the logical connectives (in order of precedence):

• Negation (“not”): $\neg P$ is true if and only if $P$ is false.
• Conjunction (“and”): $P \wedge Q$ is true if and only if both $P$ and $Q$ are true.
• Disjunction (“or”): $P \vee Q$ is true if and only if either $P$ or $Q$ are true.
• Material Implication (“if…then”, “implies”): $P \rightarrow Q$ is true unless $P$ is true and $Q$ is false.
• Biconditional (“if and only if”, “iff”): $P \leftrightarrow Q$ is true if and only if $P \rightarrow Q$ and $Q \rightarrow P$ are both true.

These rules are summarized in the following truth table:

First-Order Logic

Computability

Incompleteness