Sentence logic

Propositional (mathematical) logic is a means of expressing mathematics that can be encountered in a variety of terminology and in all sorts of mathematical theorems.

What is logic for?

Logic is the science that deals with inference, truth, provability and refutability. Yet logic is all about the form of the message; we are not interested in what is being communicated, just as we are not interested in various psychological interpretations and the like.

For example, if we have the sentence "the number 2 is both even and odd", we can conclude the whole sentence is not true because the number 2 is not odd. These are things that are generally dealt with by logic.

The statement

The basis of propositional logic is, of course, the proposition. A statement is any announcement sentence for which we can determine its truth value. Examples of simple statements:

• Bill Gates was the richest man in the world.
• The natural number five is an odd number.
• HTML is a programming language.
• Two plus three is six.

These are all statements. Either they are true (the first two) or they are false (the last two). A statement is not, for example, an interrogative sentence or a sentence for which we cannot unambiguously determine its truth value. Example again:

• Will Bill Gates still be the richest man in the world next year?
• The color green is the most beautiful.

The first sentence cannot be a statement because it is an interrogative sentence, and for the second sentence we cannot determine whether it is a true statement or a false statement. Such a sentence is then called a hypothesis (conjecture).

Classical mathematical logic cannot cope very well with vague sentences like "Honza is tall" or "Britney Spears is a good singer". These statements are better dealt with, for example, in fuzzy logic, which is tailored for vagueness.

Atomic statement

In the first chapter, we had an example of the statement "the number 2 is both even and odd". We can call such a statement a compound statement because it actually combines two shorter statements, "the number 2 is even" and "the number 2 is odd". These two statements are then joined by the conjunction "and" or also "and at the same time".

The atomic statement is thus a statement that we can no longer divide, it is in a sense the simplest statement. The previous examples of statements were in fact atomic statements:

• Bill Gates was the richest man in the world.
• The natural number five is an odd number.
• HTML is a programming language.
• Two plus three is six.

Atomic statements will henceforth be denoted by lowercase letters of the alphabet, classically p, q, r, …, and will be called propositional symbols.

Utterance connectors

Mathematical logic commonly operates with a certain set of propositional conjunctions. Among the basic ones are the four binary conjunctions:

• p ∧ q is a conjunction of propositions, reading "proposition p and (at the same time) proposition q"
• p ∨ q is a disjunction of statements, we read "statement p or statement q"
• $p \Rightarrow q$ is an implication, we read "if statement p, then statement q"
• p ⇔ q is equivalence, we read "statement p just if statement q"

Concrete examples of propositional conjunctions:

• It is raining in the centre of Opava and the sun is shining at the same time. (conjunction)
• It is raining or the sun is shining in the centre of Opava. (disjunction)
• Apple is the coolest company and Steve Jobs is the biggest dude.
• If you take a laxative, then you'll soon sit... (implication)
• If the number x is divisible by four, then it is divisible by two. (implication)
• Agatha is both pretty and smart.
• Singers are successful when they 're pretty. (equivalence)
• If it doesn't rain, we won't get wet. (implication)
• If Leoš Mareš can sing, then I am the Chinese god of fun. (implication)

We know another common propositional conjunction: negation. Negation is marked either by a comma $p^\prime$ or by the symbol $\neg p$.

The formula

Using propositional symbols (atomic statements) and propositional conjunctions, we can compose a more complex statement, which we will call a formula. All of the examples in the previous list of sentences were actually formulas because we had two atomic formulas, for example, "It is raining in the centre of Opava" and "The sun is shining", and we joined them together using propositional conjunctions. In the first case we joined them with the conjunction "and at the same time" and got the formula "It is raining in the centre of Opava and the sun is shining at the same time", in the second case we used "or" and got the formula "It is raining or the sun is shining in the centre of Opava".

Formally we define the formula as follows:

• Each propositional symbol (atomic proposition) is a formula (more precisely, we can say that it is an atomic formula).
• If A and B are both formulas, then $\neg A$, (A ∧ B), (A ∨ B), $(A \Rightarrow B)$, (A ⇔ B) are also formulas.

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 center of Opava" and "The sun is shining", then we also have two formulas. At this point we can apply the second point and construct a more complex formula like this:

• It is raining in the centre of Opava and the sun is shining at the same time.
• In the centre of Opava it is raining or the sun is shining.
• If the sun is shining in the centre of Opava, then it is raining.
• The sun is shining in the centre of Opava when it is raining.

Of course, the formulas are not necessarily true. At the moment we've got another set of formulas so we can make even more complicated formulas. If we mark A="The sun shines in the centre of Opava or it rains." (we already know that this is a formula) and B="a rainbow is visible" (let's assume again that it is in the center of Opava, so we don't have to repeat it over and over again), then we can create more formulas. The parentheses in the sentences just indicate which parts the conjunction refers to.

• A ∧ B: (It's sunny or raining in the centre of Opava) and at the same time (you can see a rainbow).
• A ∨ B: (The sun is shining or raining in the centre of Opava) or (a rainbow can be seen).
• $A \Rightarrow B$: (If the sun is shining or raining in the centre of Opava), then (a rainbow is visible).
• A ⇔ B: (The sun is shining or raining in the centre of Opava) just when (a rainbow is visible).

These are all formulas. So again, we can take one of these formulas and add some other formula to it. So we can create a patvar like "If the sun is shining or raining or a rainbow is seen in the centre of Opava, then the sun is shining or raining just when a rainbow is seen."

In the next section we will examine the truth of the formulas.