Propositional logic – "Math for Non-Geeks"

Why is logic used in mathematics?

Logic, being the study of reasonable conclusions, is the primary language of mathematics. Using this language, we can construct mathematical theorems and their proofs. This language satisfies the most basic tenet of mathematics - namely, that all expressions (claims, theorems, proofs) contained within this language have a clear, precise meaning. Because of this precision, it is not always as easy to draw the correct conclusions from logical expressions as one might initially think. Often, conclusions that are drawn from intuition are actually formally incorrect within mathematical logic. In order to understand and master mathematics, it is essential to be able to correctly interpret logical expressions. For this reason, in this article, we will lay down the groundwork concerning logical expressions and how to recognize and interpret them.

Ambiguity of Natural Language

We use the term "natural language" to describe any language intuitively spoken by some group of people for everyday communication. Oftentimes, natural language isn't suitable for mathematical discourse due to the lack of absolute clarity in certain phrases and sentences. We will see some examples in English of why everyday English doesn't capture the mathematical precision we desire.

Question: What do the following claims mean?

Claim: Every man loves a woman.

1. Every man loves at least one woman.
2. Every man loves exactly one woman.
3. Every man loves the same woman.

Claim: You can find your address or your phone number in the list.

1. You can find your address and/or your phone number in the list.
2. You can find either your address or your phone number in the list.

Claim: I can see Robert on the roof with the binoculars.

1. I'm on the roof and can see Robert by using my binoculars.
2. I can see Robert while I am on the roof, and Robert is using binoculars.
3. I can see Robert and Robert is on the roof with a pair of binoculars.
4. I can see Robert by using my binoculars and Robert is on the roof.

With the examples above, you can see that many sentences in everyday language are ambiguous, whether this is intentional or not. Surely you can also find examples of sentences that are ambiguous, and you probably have had miscommunications with people in the past that resulted from ambiguous statements.

Because of ambiguity, natural languages should not be used as the regulated language of mathematics. Otherwise, each individual mathematician could have a different understanding of the same mathematical object. This means that mathematical interpretations and conclusions would be both individual-dependent and language-dependent, which would make a practical mathematical effort amongst an international community impossible. Therefore, it is vital to have a toolkit in which only clearly defined claims can be formulated and there are explicit rules for how one can derive new claims from extant ones. For mathematics, this system is the study of logic, which we will investigate further in the rest of the chapter.

Classical logic

There are multiple systems of logic in use today. The most important one for our purposes is called "classical logic". The word "classical" is not used in a context with time here. Classical logic is definitely not obsolete and should rather be seen as the "default". Two important properties of classical propositional logic are:

• The principle of binarity: A statement is either true or false.
• Truth-functionality of propositional connectives: The truth value of a statement formed with propositional connectives is determined by the truth values of its component statements.

Logical systems that depart from these principles include non-classical logics. An example is many-valued logic which has more than two truth values. However, classical logic is used in most areas of mathematics. Classical logic is also separated into two parts:

• logic of statements - statements and their combinations, producing new statements.
• logic of predicates - the inner structure of statements.

Basic Definitions

Statements

The most basic concept of the logic of statements is - you guessed it - the statement.

Definition (Statement)

A statement is an expression consisting of words and/or mathematical symbols. It has a definite truth value, even if we do not know that value.

Statements are expressions that can be assigned a meaningful truth-value. This means you can use them to replace the dots in the following sentence:

"Is it true that ... ?"

The expression "5 is prime" for example is a statement because the question "Is it true that 5 is a prime number?" is meaningful and can be answered. The expression "Is 5 prime?" is not a statement, because the question "Is it true that is 5 prime? ?" doesn't make sense. Questions, instructions and sentences that aren't complete are not statements.

Expressions that include free variables like $x\ge 5$ aren't statements either, because whether it is true or not depends on the value assigned to the variable. $x\ge 5$ for example is true for $x=42$, but not for $x=1$. Expressions like this that contain free variables are not called statements, even if the expression is always true. $x+x=2x$ for example is not a statement, even though it holds true for any value of x. Later on, we will learn about "predicates" for expressions that contain free variables.

Sadly, not every expression that contains one or more variables is a predicate. The expression " $x\ge 5$ is true for all real numbers $x$ " for example is a statement and not a predicate. This is because $x$ is bound by the so-called quantifier "for all" and not free. What exactly free and bound variables are will be explained in the chapter "Predicates And Substitution"

Note that the definition from above is not very precise. It doesn't, for example, describe exactly what a meaningful expression is. Intuition works fine in most cases, but a certain subjectivity can't be ruled out like this. But this definition is completely adequate for the purposes of this book. You will probably be using a more precise definition of "statement" in your lectures.

A statement can only be assigned the truth values "true" or "false". This is called the "Law of Bivalence".

Definition (Law of Bivalence)

A statement is either "true" or "false".

The symbols $\mathrm{W}$, $w$ or $1$ are often used for the truth-value "true", the symbols $\mathrm{F}$, $f$ or $0$ for "false".

Expression	Is this expression a statement?	Comment
10 is an even number.	Statement	True statement
5 is divisible by 3 without remainder	Statement	False statement
There is always at least one prime between the squares of two consecutive positive integers.	Statement	This statement is called Legendre's conjecture. It's still unknown whether it is true or not.
Are you asleep?	Not a statement	—
Go to school!	Not a statement	—
$5+4-7x=0$	Not a statement	Without a value for x, this expression has no truth value.
$x>0$ or $x=0$ or $x<0$	Not a statement	Although this is true for every real number x, the free variable x makes the expression a predicate rather than a statement.
Whoa, dude....	Not a statement	—

You will always come into contact with statements while studying maths. All axioms, theorems and helping theorems (lemmas) are formulated as true statements. A proof is a series of statements that build on one another and have some (logical) connection. A statement can be a conclusion made from a different statement, for example. In short, it is important for everyone who is interested in mathematics to have a good grasp of statements.

Question: Which of the following expressions are statements?

1. All ravens are white.
2. $5+7$
3. $5\ge 7$
4. $5+7=6$
5. Is $5+7=12$?

Answer:

1. Statement
2. Not a statement (Term)
3. Statement
4. Statement
5. Not a statement (question)

Paradoxical self-referential expressions

There are expressions that look like statements at first glance, but that cannot be assigned a truth-value. One of these expressions is the self-referencing sentence "This sentence is false". One can ask the meaningful question "Is this expression true or false?", but one cannot consistently assign it a truth value. No matter what truth-value you assign to it, you will always end up in a paradox. Try it! In turn, this expression is not a statement.

Such paradoxical expressions often involve self-reference. Another example is:

"The following sentence is true. The previous sentence is false"

Question: Why does the pair of sentences "The following sentence is true. The previous sentence is false" lead to a paradox?

If the first sentence were to be true, the second sentence would be true. The second sentence is "The previous sentence is false", which would in turn mean that the first sentence cannot be true.

If the first sentence were false, the second sentence would also be false, which would mean that the first sentence would have to be true.