Tautologies and Concluding Rules

In the excursus on formal languages in the last blog post, we already got to know the signs and more general expressions of propositional logic. We have seen that there are special character strings, so-called tautologies, which are always true, i.e. independent of the truth values of the individual characters. We had also already introduced such a tautology, namely (A ∧ (A → B)) → B.

Here we will show how logically correct reasoning rules can be formulated with the help of tautologies. But let’s first ask which simple tautologies still exist and how to generate tautologies in general. Interesting in this context are also character strings, which are always false, because from their negation one can also gain a tautology.

Tautologies

Let us first introduce prominent tautologies:

            A ∨¬A is in any case true,

because either A is true or ¬A. There is no such thing as a third according to our requirements. This statement is called the statement on the excluded third.

On the other hand, A ∧ ¬A is wrong in any case, because the statement A and the statement ¬A cannot be true at the same time. For example, it cannot be that it is raining and not raining at the same time. A and ¬A contradict each other. One generally calls a compound expression, which is false regardless of the truth values of the individual statements, a contradiction. Then, the following applies to the negation:

¬(A ∧ ¬A) is true in any case.

This statement is called the principle of contradiction.

Here we should now also list the tautology from the last blog post again.

(A ∧ (A → B)) → B is in any case true.

How do we find further tautologies in order to be able to form further rules of inference?

It can be shown that the propositional logic can be regarded as an axiomatic-deductive system. Axioms can be all tautologies of the form (by Kutschera & Breitkopf, Alfred, 2007, p. 69).

 A → (B → A),

(A → (B → C)) → ((A → B) → (A → C)),

(¬A → ¬B) → (B → A)

and as a rule of inference or concluding rule the modus ponens, which we already mentioned in an earlier blog post. In a moment, we will really introduce this concluding rule by deriving it from a tautology.

All logical expressions, that can now be derived from these axioms using the modus ponens, are tautologies again. So you can set up as many concluding rules as you want. Only a few will be needed.

Now we understand why Wittgenstein says: The propositions of logic are tautologies. So the propositions of logic say nothing (Wittgenstein, 2006, pp. No. 6.1, 6.11).

From Tautologies to Concluding Rules

Let’s have a look at the truth table for the tautology (A ∧ (A → B)) → B again:

A B A B A ∧ ( A B) (A(A B))B
1 1 1 1 1
1 0 0 0 1
0 1 1 0 1
0 0 1 0 1

Let us first consider the first line, in which both premises A and A → B are true. From the second column of this first row we then infer that B is true. The statement B must therefore necessarily be true if both A and A → B is true. Only in this way can the character of tautology be respected.

This is now a conclusion that results from inspection of the truth table of a tautology. No reasoning can be more elementary. This is also the conclusion with which all other concluding rules can be won. So here we have the origin of logical reasoning before us, the “mother” of all reasoning rules.

You write, with the sign “⊨” for a logical conclusion:

A ∧ (A → B) ⊨ B,

but frequently also in a form in which the individual premises are separated only by a comma:

A, (A → B) ⊨ B.

The symbol “⊨” is not a sign of propositional logic, but an abbreviation for the phrase “follows logically from this” in colloquial language. Otherwise we should be able to count with this symbol like with “∧” or “∨”. It only expresses the relationship between the statements A ∧ (A → B) and B in the meta language, our colloquial language:  In the case that the statement A is true, and in the case that the statement B follows from A, then B is true.

You may be confused at first and ask why all the effort.  They knew that a long time ago. It is indeed trivial, in the truest sense of the word, because in the Middle Ages the word “trivial” was coined from insights gained in trivium, the lowest level of education in a monastic school. This trivium, in turn, was named in ancient times for a place to which three paths lead, and where many who share the same opinion can gather.

Here, however, in a formal language, what Aristotle has already defined is very concretely realized: “A conclusion is thus a speech in which, with certain assumptions, something other than the presupposed follows with necessity on the basis of the presupposed”. (after Schupp, I, p.267). The emphasis is on “necessity”.

This is the modus ponens. It is the most prominent logical conclusion, was already known in ancient times by the philosophers of the Stoa and subject of many discussions in the Middle Ages (see “the Logic of the Stoics”).

We still want to investigate what this conclusion tells us if one of the premises or both are wrong. In any case, the entire premise is then wrong, because the individual premises are linked by a “∧”. We extract the two relevant columns from the table above and arrange them somewhat differently:

A (A B) B
1 1
0 0
0 1
0 0

So, if the total premise is false (2nd to 4th line), B can be true, but also false, i.e. nothing can be said about the truth value of B. Everything can be deduced from a false premise. At first this is surprising, and in the history of logic it has been discussed for a long time. But if one can derive both B and ¬B, then the conclusion is meaningless.

From the derivation of the modus ponens we can learn how to create a general final rule: From every tautology that can be found in the form

M → B, you can use the final rule

M ⊨ B

because then it follows immediately from the truth table for “M → B” that under the condition that M is true, also B must be true, because this implication M → B is a tautology after assumption and therefore true.

This is a statement on the meta level, not in the calculation of the syntactic level. However, we know that because M → B is a tautology, we can go from the character string M to the character (string) B on the syntactic level without leaving the realm of true statements on the semantic level. We write this in the form of

M ⊢ B,

and call this operation a derivation at the syntactic level. That what is a conclusion on the semantic level is called a derivation on the syntactic level.

At the syntactic level, we can therefore pass from the character string M to the character or character string B without leaving the realm of true statements at the semantic level.

But now one knows how to “calculate” on the syntactic level, namely according to the rules for the formation of character strings and according to the concluding rules, by which one may transform certain character strings into others, which are also usually shorter. Such a system of calculation rules is called a “calculus”.

The calculus of propositional logic therefore has nothing to do with any meaning of the statements in terms of content. To a certain extent, it only provides the tracks on which truth of statements can be safely transported from premises to conclusion. Wrong statements on such tracks lead to arbitrariness. Without the truth of the premises “everything is nothing”. That’ll still occupy us.

Two remarks are in place here:

Let us consider the premises:

A: = „2 + 2 = 4“,

B: ≔ “Freiburg is located in the south of Germany”. 

The statements A and B are true, thus also the implication A → B, i.e. if 2 + 2 = 4, then Freiburg lies in the south of Germany”. Thus, the expression A → B is well formed, but futile. Then the logical conclusion

A, A → B ⊨ B

is also meaningless. That doesn’t have to be irritating. Even in our colloquial language we can form grammatically correct sentences that are meaningless: “The moon babbles red suit.” The tracks are not responsible for what goes on them. Incorrectly formed sentences or not well formulated expressions are senseless anyway.

You often hear people say: “It’s logical, isn’t it?” and the speaker means that the conclusion immediately makes sense to him. This feeling, however, probably does not refer to the concluding rule, but to the implication, which is of course true for the speaker. The speaker thus confuses the logical conclusion with his assumption that his premise is true. He should say, “It’s a plausible assumption for the modus ponens, isn’t it?” He would be met with venerable understanding.

Important Concluding Rules in Applications

The modus ponens is probably the most prominent concluding rule, even in generalized form, which reads:

(A1 ∨ A2 ∨ …   ∨ AnA) (¬A B1 ∨ B2 ∨ …   ∨ Bm)

  ⊨ A1 ∨ A2 ∨ …  ∨ AnB1 ∨ B2 ∨ …   ∨ Bm.

The underlined portion of the premise represents exactly the simple modus ponens. This term then also appears accordingly as B1 in the conclusion.

The premise here is based on a character string in normal or standard form, into which each character string can be brought by a systematic transformation process. In general, this is the normal form:

(A1 ∨ A2 ∨ …   ∨ An) ∧ (B1 ∨ B2 ∨ …   ∨ Bm).

Such procedures and applications of inference rules as the generalized modus ponens are implemented in so-called resolution algorithms. The length of the character string can be successively reduced. Within the “Prolog” program, for example, such an algorithm can be processed on a computer.

A particularly popular inference rule in mathematics, already known in ancient times, is proof by contradiction:

If one wants to prove that a statement A implies another statement B, one first assumes for the proof that besides a premise A also ¬B is true premise. If then one can deduce a contradiction from it, ¬B cannot be true. So B must be true, because there’s no such thing as a third. Here it is shown that the negation of an assumption can be reduced to a contradiction. In the Middle Ages this form of proof was therefore also called “reductio ad adsurdum”.

The contradiction can show itself e.g. in the fact that one can deduce from A ∧ ¬B a statement C, and in addition, the statement ¬C. In order to show that this strategy can also be represented as a concluding rule, one only needs to find the corresponding form M → B. This is

((A ∧ ¬B) → C) ∧ ((A ∧ ¬B) → ¬C) → (A → B).

This is indeed a tautology and therefore the concluding rule:

((A ∧ ¬B) → C) ∧ ((A ∧ ¬B) → ¬C) ⊨ (A → B).

In a somewhat different form one uses the proof by contradiction if one wants to know whether a statement B is contained in a knowledge base W and thus also true. So, you’re asking whether

W ⊨ B

applies. This is the case if W → B, i.e. ¬W ∨ B is a tautology. Since ¬W ∨ B can be transformed into ¬(W ∧ ¬B), we must therefore ask whether ¬(W ∧ ¬B) is a tautology and thus W ∧ ¬B is a contradiction. So, we can see that a statement B can be deduced from a knowledge base W if

W ∧ ¬B

is a contradiction. That is also plausible: If the information of B is contained in W, the contradiction B ∧¬B must show up somehow with the evaluation of the expression W ∧ ¬B.

In order to now show that W ∧ ¬B leads to a contradiction, the expression W ∧ ¬B is transformed into the disjunctive normal form within the framework of the calculus and then the receiving expression is successively reduced with the help of the generalized modus ponens until an expression is shown that represents a contradiction – or not, depending on whether the statement B is contained in the knowledge base W or not. 

The proof of the Pythagoreans that there are infinitely many prime numbers is e.g. of this form. The statement B is then: There are infinitely many prime numbers. The statement ¬B is: There are only finitely many prime numbers. The knowledge base consists of the rules of arithmetic for integers.

On this basis of ¬B and with the knowledge of W one shows then that one can always find a new prime number to every set of finitely many prime numbers, thus ¬B is false, in contradiction to the assumption that W ∧ ¬B is true.

The formal language of propositional logic

After briefly introducing Aristotle’s syllogistics in the last blog post, I should now actually explain how it were received and elaborated in antiquity, the Middle Ages and into modern times. In particular, the work of Gottfried Wilhelm Leibniz (1646 to 1716), in which important approaches to modern logic can already be found, should be honoured. It would also be his great project to describe a “Scientia generalis” based on the model of mathematics, in order to “bring about in all scients what Cartesius and others did by algebra and analysis in Arithmetica et Geometria”. (All writings II,1. p.160, after Schupp III, p.238). For this purpose Leibniz wanted to develop a “lingua characteristica” with suitable characters (characteristica universalis). But this and other developments in this direction can be better assessed in retrospect. Therefore, I want to skip this and talk about modern logic.

The mathematician and philosopher Gottlob Frege (1848-1925) founded modern logic with a book entitled “Begriffsschrift – Eine der arithmetischen nachgebildete Formelsprache des reinen Denkens” (“Conceptual writing – one of the arithmetic formula languages of pure thought”). The foreword says: In this “small script I have now tried a rapprochement with the Leibniz thought of a lingua characteristicistica”. Leibniz is thus the godfather of the modern formal logic (Wille, 2018, p. 96).

Gottlob Frege was a philosopher and mathematician, his father had written a New High German grammar (Wikipedia: Gottlob Frege). So Frege probably knew the power of a formal language; with such a language he then raised logic to a new level, on which one could lead proofs as in mathematics. He thus discovered a “new science” for logic, as Galileo had done for natural research. And again one can see how formalization leads to an accelerated development of a field of knowledge, then “emigrating” from philosophy.

The final form of a “propositional logic” was then created somewhat later by Alfred North Whitehead (1981 to 1947) and Bertrand Russell (1872 to 1970). The “term logic”, as the philosophers had always practiced until then, was soon replaced by this propositional logic; logic developed into a predominantly mathematical discipline. Its mathematical form made it possible to transfer logical reasoning rules to machines, which has led, among other things, to the now flourishing field of “artificial intelligence” research.

Since one experiences again and again, which shyness most contemporaries have at mathematical formulas, one has to exercise great caution with the representation of a formal language for the logic. The best thing to do is to look at the structure of a formal language in analogy to the structure of our mother tongue and to demonstrate the similarity of a formal language with our colloquial language. It’s just all so much easier, and so simple, that at first you feel yourself as a stranger. The language of mathematics may serve as an intermediate station between the formal language of logic and our colloquial language, because it is already formal and the contemporary has at least some experience with it.

Thus, we now look at three languages: logic, mathematics and our colloquial language. In all three languages there is a certain set of characters with which you can form strings. In colloquial language this set represents the usual alphabet, strings are words and several strings represent sentences. So you learn to write the letters first, then the words and then the sentences.
Here the important difference between syntax and semantics has to be discussed. Syntax is what is called grammar in natural languages. It shows, for example, how words are declined or conjugated in a sentence regardless of their meaning, depending on their function and position, and in which order they can occur in a sentence. The syntax or grammar thus regulates the formal structure of a language. Semantics, on the other hand, deals with the meaning of words and sentences.

In formal languages, the distinction between syntax and semantics becomes even clearer. The syntax specifies exactly what should be allowed with regard to the formation of character strings. At the syntactic level, therefore, we are only dealing with strings of different complexity, without these having already been assigned a meaning.

Even a rudimentary knowledge of mathematics gives us an indication of the usefulness of a formal language. One can “calculate” in it, i.e. formally argue, in such a way that one does not have to know the meaning of the characters and character strings, which one changes, generates or removes there according to certain rules. The whole thing happens on the syntactic level and the rules are made in such a way that true statements are transformed into true statements – completely independent of the meaning of the signs and strings of signs. Only in this way is it understandable that we can transfer the calculating and logical closing to a machine, that we can develop algorithms to solve tasks that would require a certain intelligence from ourselves.

The syntax of the language for a propositional logic

In general, a construction of a formal language begins by first providing a character set, a certain set of symbols, i.e. defining an alphabet.
In propositional logic, the alphabet consists of a stock of

– Variables A, B, …, i.e. capital letters of our everyday language.
– the characters ‘¬’ and ‘→’, ‘∧’ and ‘∨’.
– the sign “≡”,
– the brackets “(“” and “)”; these should always be used, if you want to see a couple of strings as a unit, to keep an overview. Also, sometimes a space is used to increase the clarity, and finally
– the constants “0” and “1”.

With the help of these characters or “letters” you can form character strings. We will see that in the formal language of propositional logic there is no need to distinguish between letters, words and sentences. You only know characters and strings, and these are uniformly called expressions.
How character strings, i.e. more complex expressions, can be formed from the characters of the alphabet is regulated by certain laws, namely:

– If A is an expression, then ¬A is also an expression.
– If A and B are expressions, so are A ∧ B and A ∨ B.

You can always create new expressions in this way, e.g. ¬A ∨ B or A ∧ (¬A ∨ B). The expression ¬A ∨ B will later play a major role, so we will introduce the abbreviation A → B for him. This is another sign at our disposal. Any expression of the form A → B will always be understood as ¬A ∨ B.
With A and A → B and A ∧ (A → B) we can e.g. get also (A ∧ (A → B)) → B. We will deal with this expression later.

One calls expressions, which are formed according to these rules, well formed. So A → B and A ∧ B ∧ C C are well-formed, but ABA or AB→ are not.

Comments:
Our natural languages also have an alphabet. We are most familiar e.g. with the alphabet of the German language. Other alphabets deviate more or less from it. These characters are also used to form strings, which we call words. These words are formed by the way people deal with the things of the environment. This is a historical process, and through the experience of always new things in this world, new words are always invented. Here there are hardly any rules, at most the condition that the word must be pronounceable. For example, the string mjk?a will not be regarded as a meaningful candidate for a word. So the word formation happens on the semantic level: “The thing must get a name”. A rule is then formed for how the accepted words must be written. Orthography is the teaching of “correct writing”, the correct representation of “accepted character strings”. Words are used to form sentences in colloquial language, which can then each represent a statement. The words are then modified, declined or conjugated depending on their position in the sentences.

In contrast, in a formal language “words” are formed at the syntactic level, and according to only a few rules. “Orthography” here means respecting the rules for the formation of strings. There’s no such thing as sentences.

– Mathematics is also a formal language. Here the character set usually consists of the set of symbols {0,1, … ,9}, i.e. the numbers from 0 to 9, and the characters {+, -,  ∙, :, =}. Depending on the mathematical theory, further characters are added. Furthermore, you still need symbols as placeholders for numbers that are not further specified at first. Often one takes letters of the alphabet of the colloquial language. There are also clear rules here for the formation of “words” and “sentences”. “Words” are then such strings as x + 0 or 5-4, which are also called “terms”. “Sentences” are equations like x + 2 = 0, and they are also formulated according to certain rules.

Herewith we have described the syntax of three languages. It regulates which character strings may be formed on the basis of a character set.

The semantics respectively the evaluation

In semantics we must now say what we want to understand by the characters we have introduced in syntax, what meaning we want to give them.

In propositional logic, the variables A, B, … should stand for statements in our colloquial language that are either true or false. Note that this is not about the content of the statement and its meaning, but only about an evaluation: true or false. In this respect one should actually only talk about evaluation instead of semantics. But we don’t have to become that exact in our colloquial language, in which we construct the formal language and in which we later talk about it. The colloquial language we call the “meta language”, the language of the propositional logic is then here the “object language”. We have to be very specific in this one. But in our colloquial language, however, we may have enough vague terms.

This condition that we only want to consider statements that are either true or false is constitutive for the entire propositional logic. So it’s not about interrogative sentences or exclamations. We also disregard the fact that there may be statements where you can never decide whether they are true or false. The fact that this limitation is not self-evident for some mathematicians does not need to be discussed here.

Let’s look at some simple statements. Be, for example.
A:= “It’s raining.”
B:= “The road’s wet.”
So e.g. A is true exactly when it rains. Truth is given when the statement is consistent with the facts.

In order to evaluate all the expressions that we can form with such statements according to the rules of syntax, we must now say what we intend to do with the other characters from the character set:

We interpret the “1” as true, the “0” as false.

The sign “¬” before a statement should negate it:
¬A = It is not the case that A, i.e. in our example: “It does not rain”.
It’s the same:
¬1 = 0, “not true” means “false”,
¬0 = 1, “not wrong” means “true”.

The expression A ∧ B represents a combination of two statements, reminiscent of 5 + 4 or 5 – 4. We determine the meaning of the sign “∧ ” by saying when this expression should be true depending on the truth values A and B and when it should be false. In principle, we have 16 possibilities there. The default choice is shown in the following truth table:

A B A B
1 1 1
1 0 0
0 1 0
0 0 0

This assignment is done in such a way that the symbol “∧” corresponds to the colloquial “and”. We’ll test this against our example:
A ∧ B = “It’s raining” and “the road is wet”.
We obviously perceive this statement as true exactly when both statements A and B are true, as it is also stated in the table.

We define the meaning of the sign “∨” in such a way that in the expression A ∨ B it resembles the colloquial “or”:

A B A B
1 1 1
1 0 1
0 1 1
0 0 0

The expression A ∨ B only has the rating 0, i.e. is only false, if both statements A and B are false. So with this “or” the statement “A or B” is true, if either A or B are true, but also if both, A like B, are true. This corresponds to the inclusive “or”. When we use the “or” in colloquial language, we sometimes mean, however, the exclusive “or”, i.e. the “either-or”. This is a typical example of the ambiguity of our colloquial language.

These three rules are actually sufficient to construct arbitrary strings.
The expression ¬A ∨ B with the truth tablet is particularly important and useful:

A ¬A B ¬A B
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 1

The link ¬A ∨ B, also written as A → B, is called implication. This applies to this:
If A, then B. The statement A is therefore a sufficient condition for B: Always, if A is true, B is also true.
The implication is only false if B is false.
If A is false, then the implication A → B according to the truth table is always true, no matter if B is true or false. That means: If the statement A is not sufficient, then one cannot say anything about the truth value of B in the case of a true implication.

In this way, the truth value can always be determined for longer character strings. We would like to give an example here of what will still concern us in the future. We’re looking at the string:

(A ∧ (A → B)) → B.

For these one receives the following truth table:

A B A B A (A B) (A (A B))B
1 1 1 1 1
1 0 0 0 1
0 1 1 0 1
0 0 1 0 1

So there are expressions in propositional logic that are true in every case, regardless of the truth value of the individual statements. Such expressions are called tautologies. We will see in the next blog post what important role such expressions play in the formation of conclusions.