ropositional logic – Serlo „Math for Non-Geeks“

Why is logic used in mathematics?

Logic, being the study of reasonable conclusions, is the primary language of mathemics. 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 ground work concerning logical expressions and how to recognize and interpret them.

Ambiguity of Natural Langauge

We use the term "natural language" to describe any language intuitively spoken by some group of people for everyday communication. Often times, natural langauge 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 using my binoculars and Robert is on the roof.
3. I can see Robert and Robert is on the roof with a pair of binoculars.
4. I can see Robert by using my binculars 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 langauge 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 how one can derive new claims from pre-existing 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. The classical logic is definitely not obsolete and should rather be seen as the "default". It is defined through these two properties:

• The principle of binarity: A statement is either true or false.
• The principle of extensionality. The truth value of any combined statement is defined through the truth values of its components.

If a logical framework doesn't fulfill both of the above principles it is called non-classical logic. An example is many-valued logic which has more than two truth values. However, classical logic is used in most areas of mathematics. The 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 is possible and meaningful to decide whether it is true or not.

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:

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\geq 5$ aren't statements either, because whether it is true or not depends on the value assigned to the variable. $x\geq 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\geq 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 just 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 a square number and its successor.	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 further information on x we can't decide whether it's true or not.
$x>0$ or $x=0$ or $x<0$	Not a statement	Although this is true for all real numbers x we can't decide whether it is true or not, because we don't know whether x is a real number or not.☃☃☃☃
Whoa, dude....	Not a statement	—

You will always come into contact with statements while studying maths. All axioms, theorems and helping theorems (lemmata) 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 that 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\geq 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)

Undecidable 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 a the meaningful question "Is this expression true or false", but one can not meaningfully decide on it. 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.

Undecidable expressions occur especially often with self-referencing expressions. Another example for an undecidable expression is:

Question: Why is the theorem "The following sentence is true. The last sentence is false" undecidable?

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

If the first sentence was false, the second sentence would be false as well. Which would mean that the first sentence would have to be true.