Propositional logic

Propositional (mathematical) logic is a tool for expressing ideas in maths. You will come across it in all sorts of terminology and in all kinds of mathematical theorems.

What logic is for

Logic is the science of reasoning, truth, provability and refutability. In logic we care only about the form of a statement, not about what it actually says, and we are not interested in psychological interpretations and the like.

For example, take the sentence “the number 2 is even and odd at the same time”. We can conclude that the whole sentence is not true, because the number 2 is not odd. This is the kind of thing logic deals with.

Statement

The basis of propositional logic is, of course, the statement. A statement is any declarative sentence whose truth value we can determine. Examples of simple statements:

• Mount Everest is the highest mountain in the world.
• The positive integer five is an odd number.
• HTML is a programming language.
• Two plus three is six.

All of these are statements, whether they are true (the first two) or false (the last two). A question is not a statement, and neither is a sentence whose truth value we cannot determine unambiguously. Here is another example:

• Will Mount Everest still be the highest mountain in the world next year?
• Green is the most beautiful colour.

The first sentence cannot be a statement because it is a question. For the second sentence we cannot decide whether it is true or false. Such a sentence is called a hypothesis (a conjecture).

Classical mathematical logic cannot cope very well with vague sentences such as “Tommy is tall” or “Amelia is a good singer”. Statements like these are better handled by, for example, fuzzy logic, which is designed for vagueness.

Atomic statement

In the first section we had the example of the statement “the number 2 is even and odd at the same time”. We can call such a statement compound, because it really joins two shorter statements: “the number 2 is even” and “the number 2 is odd”. These two statements are joined by the logical connective “and” or “and at the same time”.

An atomic statement is therefore a statement that we cannot divide any further; in a sense it is the simplest claim we can make. The earlier examples of statements were in fact atomic statements:

• Mount Everest is the highest mountain in the world.
• The positive integer five is an odd number.
• HTML is a programming language.
• Two plus three is six.

From now on we will write atomic statements with lower-case letters of the alphabet, as usual p, q, r, …, and call them propositional variables.

Logical connectives

Mathematical logic commonly works with a certain set of logical connectives. The basic ones are four binary connectives:

• p ∧ q is the conjunction of statements, read “statement p and (at the same time) statement q”
• p ∨ q is the disjunction of statements, read “statement p or statement q”
• p ⇒ q is the implication, read “if statement p, then statement q”
• p ⇔ q is the biconditional (equivalence), read “statement p if and only if statement q”

Some concrete examples of logical connectives:

• It is raining in the centre of Leeds and at the same time the sun is shining. (conjunction)
• It is raining in the centre of Leeds or the sun is shining. (disjunction)
• Isla’s band is the best in town and George is the coolest guitarist. (conjunction)
• If you take a laxative, then you will soon be sprinting to the lo… (implication)
• If the number x is divisible by four, then it is also divisible by two. (implication)
• Amelia is pretty and at the same time clever. (conjunction)
• Singers are successful if and only if they are pretty. (biconditional)
• If it doesn’t rain, we won’t get wet. (implication)
• If Tommy can sing, then I’m the king of comedy. (implication)

There is one more common connective: negation. Negation is written either with a prime p′ or with the symbol ¬p.

Formulae

Using propositional variables (atomic statements) and logical connectives, we can build a more complicated statement, which we will call a formula. All the examples in the previous list of sentences were in fact formulae, because we had two atomic formulae, for example “It is raining in the centre of Leeds” and “the sun is shining”, and we joined them with logical connectives. In the first case we joined them with the connective “and at the same time” and got the formula “It is raining in the centre of Leeds and at the same time the sun is shining”; in the second case we used “or” and got the formula “It is raining in the centre of Leeds or the sun is shining”.

We define a formula formally as follows:

• Every propositional variable (atomic statement) is a formula (more precisely, it is an atomic formula).
• If A and B are formulae, then so are ¬A, (A ∧ B), (A ∨ B), (A ⇒ B) and (A ⇔ B).

The definition makes sense: in the first point we say that every atomic statement is also a formula. So if we have two atomic statements, for example “It is raining in the centre of Leeds” and “the sun is shining”, then we also have two formulae. Now we can apply the second point and build a more complicated formula, for example like this:

• It is raining in the centre of Leeds and at the same time the sun is shining.
• It is raining in the centre of Leeds or the sun is shining.
• If the sun is shining in the centre of Leeds, then it is raining.
• The sun is shining in the centre of Leeds if and only if it is raining.

Formulae need not be true, of course. We have now got another set of formulae, so we can build even more complicated ones. Let A=“The sun is shining or it is raining in the centre of Leeds.” (we already know this is a formula) and B=“a rainbow is visible” (let’s assume again that this is in the centre of Leeds, so that we don’t have to keep repeating it). Then we can create further formulae. The brackets in the sentences just show which parts a connective applies to.

• A ∧ B: (The sun is shining or it is raining in the centre of Leeds) and at the same time (a rainbow is visible).
• A ∨ B: (The sun is shining or it is raining in the centre of Leeds) or (a rainbow is visible).
• A ⇒ B: (If the sun is shining or it is raining in the centre of Leeds), then (a rainbow is visible).
• A ⇔ B: (The sun is shining or it is raining in the centre of Leeds) if and only if (a rainbow is visible).

These are all formulae. So again we can take one of these formulae and attach another formula to it. For example, we can create the monstrosity “If the sun is shining or it is raining or a rainbow is visible in the centre of Leeds, then the sun is shining or it is raining if and only if a rainbow is visible.”

In the next part we will look at the truth of formulae.