How To Do Propositional Logic

Or: how to prove stuff

Propositional Logic (PL) is a formal language which deals with very fundamental properties of truth.

Suppose I say to you: “It’s raining and the street is flooded.” How would you determine the truth of this statement?

Well, you’d probably look out the window to first observe whether or not it is raining, and second, to see whether the street is indeed flooded. And there is a simple, but crucial fact of Propositional Logic: the statement “it’s raining and the street is flooded” is true exactly when both “it’s raining” and “the street is flooded” are separately true.

I believe it is important to study PL to get a good grasp of how truth “works”, not in the least because it forms the basis for the more expressive First-Order Logic.

This essay is my attempt at explaining PL. We will start with the basic elements (proposition letters) of our formal language, and how they combine to form compound propositions with the use of connectives. We’ll then take a short look at tautologies before moving on to rules of inference and proofs.

Statements

As said before, statements are the basic propositions of the language of PL. “it’s raining”, “the grass is wet”, and “the street is flooding” are all examples of statements. However, PL doesn’t care about the content of a statement, but just about its truth; this is why we write statements as proposition letters: e.g. P, Q, R or…