A glance at formal logic

Here we introduce formal logic. After briefly describing basics of propositional logic we proceed to predicate logic and summarize rules of negation. At the end we talk about applicability of logic.

Propositional logic, statements and connectives

What is formal logic? From the point of view of a practical user it is an attempt to identify situations in which we can use knowledge of some facts to deduce knowledge of other facts. It also shows that in some situations certain deductions are not possible, which is of great importance as well. It should be said right from the start that logic is not capable of deciding which claims are true on their own merit. So if you just ask whether triangles have three sides, then do not expect logic to help you. Logic does something else. You provide it with input data (checking their validity is up to you), and based on their mutual relationship, logic can help you decide whether some other things are true (or untrue) as well. If you decide to start by assuming that the sentence "Earth is cube-shaped" is true, then logic will see nothing wrong with it—it is not its role to judge. It can only help you see what consequences would follow if you start from such an assumption. This essentially means that logic is only interested in structure formed by individual pieces of data, not in the data by themselves.

The basic object in formal logic is statements (propositions), sentences that can be assigned truth value (True/False). Examples: "13 > 10." "1 + 1 = 3." "Earth is flat." "February comes after January." "Shakespeare ate apples on Nov. 15, 1593." Note that we do not really know whether the last sentence is true or not but it is a statement nevertheless, since its truth value is determined (although unknown). It is traditional to use letters p, q, r etc. for statements. Some examples that are not statements: "Hello." "Blue is nice." "13." "So there." "It rains." Note that the last one is not a statement since it cannot be even hypothetically determined whether it is true or not. Only when we specify place and time we are able to tell — "Now and here it rains" is either true or false, therefore it is a statement.

The real fun comes when we try putting statements together, that's where logic starts. There are many ways one can put statements together and modify them, but from practical point of view five operations are sufficient.

• Negation of a statement reverses its truth value, in other words, the outcome is a statement that is true exactly if the original statement is false and vice versa. The negation of a statement p is denoted ¬ p. Example: The negation of "We have at least two apples" is the statement "We have less than two apples".
• Conjunction of two statements is denoted "p ∧ q", we read it "p and q" and this compound statement is valid exactly if both p and q are true. In other words, to make this compound statement false it is enough to make one of the two components (or both) untrue. Example: In order to log in, you need to know your login name and your password.
• Disjunction of two statements is denoted "p ∨ q", we read it "p or q" and this compound statement is valid exactly if least one of p, q is true. In other words, to make this compound statement false it is necessary to make both its components untrue. Example: An airplane falls down if it loses its wings or its tail. (Losing both still makes the condition valid and the plane falls.)
• Implication of two statements is denoted "p => q" or "p → q", we read it "p implies q", "if p then q", "q if p", and some other ways as well. There are two situations when such a compound statement is true. First, if the assumption p is true and also the conclusion q is true. Second, if p is false, then the validity of q does not matter and this implication is always true. Example: If it rains on me, then I get wet.
  We will return to implications below.
• Equivalence of two statements is denoted "p <=> q" or "p ↔ q", we read it "p if and only if q", "p and q are equivalent", and some other ways as well. This compound statement is true when both parts have the same validity, that is, when p and q are both true or when they are both false.

It is customary to use 1 for true and 0 for untrue and capture situations using truth tables. If you know validity of p and q, you find them in the first two columns of the table and then you see values of various compound statements in the corresponding row.

We can further combine such composed statements into more complicated ones, just like with algebraic expressions we use parentheses to determine precedence. In order to simplify notation, it was agreed that negation has priority over the other logical operations, so we do not have to put a term ¬ p into parentheses to force evaluating negation first.

With compound statements we usually investigate how their truth value changes depending on validity of the basic facts p, q,..., that is, we can view such composed expressions as mappings with variables p, q,... and we try to see how their values depend on values of these variables. One possible way to see this is to construct an appropriate truth table. A typical expression is sometimes true and sometimes false, depending on the row we look at. However, there are exceptions.

Some statements are always true; these are called tautologies and often denoted T, a simplest example would be the statement "p ∨ ¬ p" that is true regardless of what p is (the statement "I passed or did not pass that exam" is always true). On the other hand, the statement "p ∧ ¬ p" is always false ("2 + 2 is 4 and it is not 4"). Such statements are called contradictions and often denoted F.

However, in applications (e.g. natural sciences) we are more interested in statements whose truth does not stem from logic but from our knowledge of situation. That is, having some particular facts p, q,..., it may turn out that some combinations of their truth values are not possible within this world (or more importantly, within some theoretical framework). This means that we look not only at the structure of the statement (what logical operations are used and how), but also at its contents. For instance, if p means "somebody cut off my head last month" and q means "I am now sitting at a lecture and paying attention", then in the world of pure logic all four possibilities of 0 and 1 have to be considered (see the table above). However, we know that in our world some combinations (that is, some rows in the above table) cannot happen, namely, these two statements cannot be both simultaneously true, thus making the first row in our table virtual, not real. This for instance means that the statement "p ∧ q" is always false in our world (at present :-]).

Example: Consider the statement "p => ¬ q", where p and q are as above.

1. What is its translation into humanese?
If they cut me head off a month ago, then I am not sitting now at a lecture paying attention.

2. What are the truth values of this statement?
We construct a table for it, first we determine the value of the negation of q as a preparatory step and then we evaluate the implication using the values of p and our preparatory step.

Now we recall that in our real world the first row cannot happen. Thus only the last three can happen and we see that our implication is always true in this world.

In applications we therefore use the words true/false in the following way: A true statement is a statement that can never be falsified, that is, there is no situation (real situation) where it would fail. On the other hand, a false statement is a statement that fails to be true. This mean that there can be situations where it fails, for instance "After rain we see rainbow" is false, because I have already experienced rain after which there was no rainbow. It need not fail all the time, sometimes I did see a rainbow, but it does not help this statement to be considered true, since the rainbow appearance is not reliable and statements that are not totally reliable are useless in natural sciences. Thus it makes sense not to consider them true.

Sidenote: Even statements that are found to be false sometimes are not a total loss, because they often become a source of good questions (Can we identify conditions under which they fail? Is it possible to make them true just by tinkering with them a bit?). Questions are at the heart of all progress.

With a bit of simplification we can say that the main job of a mathematician is to find statements that are true within the world of mathematics and prove that they are indeed true. Essentially, proving a certain statement means that one has to show, beyond any doubt, that if we construct a truth table for such a statement, then rows where this statement has 0 cannot happen in mathematics. Once we identify such statements that are always true, we can use them to learn more about mathematical objects. What is the use of it? So far it seems that nature also obeys rules of mathematics, which makes math an extremely powerful tool for learning about the world around us. We will return to this later, first we will look closer at the most useful of all logical constructions, that is, the implication.

Implication is one of the most important structures,so it is crucial to understand how it works and what one can get out of it. Consider an implication p => q. Probably the most curious fact is that if the assumption p is false, then the implication as a whole is true regardless of what the conclusion q is. Some beginners find it funny or confusing, it may be helpful to think of implications as promises. Consider this: "If you are good, you get some candy." This promise is binding only in case the recipient is good. If the recipient was not good, then no matter what you do, the promise (implication) is not forfeit. Whether you give some candy or not, the statement is not falsified. We will see below that this behaviour makes sense in applications.

There are alternative ways to express an implication p => q. From a formal logic standpoint we can replace it with the expression "¬ p ∨ q", you can construct a truth table for it and see that this new statement has exactly the same truth values as the original implication, therefore they say the same thing.

There are also alternative ways to read an implication p => q. Instead of "If p then q" or "p implies q" we may say that "p is a sufficient condition for q" or that "q is a necessary condition for p". All these sentences have exactly the same truth value, that is, either all of them are true or all of them are false. An example will show it clearly.

Example: Consider the implication "If I am over 21, then I am over 18" (we mean age here). Hopefully you will agree that this implication is true in our world, regardless of who says this statement, because the situation ["over 21" true — "over 18" false] cannot happen to one particular person, which rules out the only row in implication's truth table that yields 0. Thus we have ourselves a true implication. Now we look at the alternative ways to express it.

First, "Being over 21 is sufficient for being over 18" makes sense, so far so good. To emphasize that logic only cares about validity, not contents, we embellish it a bit: "Knowing that somebody is over 21 is sufficient for knowing that this person is over 18." This is exactly how we use implications. We know that some information is valid and we use a true implication to also determine validity of another piece of information. We can express our reasoning as follows.

True: If I am over 21, then I am over 18.
Assuming true: I am over 21.
Conclusion: I am over 18.

This is the basic way in which we use true implications and the way we wrote it goes all the way back to middle ages. A typical scenario goes like this. We are curious whether some statement q is true or not, but for some reason we do not want (or are not able) to check directly. Fortunately, we have a true implication "p => q" available, where p is much easier to investigate than q. So we check on p and if it comes up true, then without any further work we know for sure that also q is true. Splendid. However, there is a big drawback here. What if we check on p and it comes up negative? Then we do not know anything about q, formal logic does not allow us to reach any conclusion. After all, in our example it is obvious.

True: If I am over 21, then I am over 18.
Assuming true: I am not over 21.
Conclusion: ???

This shows that a true implication is a nice tool for passing information, but an imperfect tool, it can only pass one kind of information. This feature of implications shows up also in another way. Having a true implication "p => q", it is not necessarily true that q is a sufficient condition for p. Again, we try it on our example.

True: If I am over 21, then I am over 18.
Assuming true: I am over 18.
Conclusion: ???

This shows that we cannot just turn an implication around. Formally speaking, an implication "p => q" and its converse "q => p" are two different animals and their truth values are not the same in general. Thus having a true implication we can only use it in the right way.

Now we try the other point of view. Theory says that with a true implication, q is a necesary condition for p, which in our example means that "Being over 18 is necessary for being over 21". This definitely seems to work here. Again, note that logic deals with information, not nature, so a more proper way of expressing this would be "Truthfulness of somebody being over 18 is necessary for truthfullness of that person being over 21." How do we use such a statement? As a negative test that can save us some work. Imagine that we are investigating some property p and as usual we are not too happy about it. However, we have a true implicaion "p => q" and we decide to check on q instead. We already know that finding q true is of no help, but what if we find that q is false? Since q is necessary for p, it follows that p must be also false. Now this may be a good news or a bad news, but the important thing is that we know, so we do not have to work on p any more.

True: If I am over 21, then I am over 18.
Assuming true: I am not over 18.
Conclusion: I am not over 21.

Note that we are in fact passing information here, negative information in this case. In other words, we have a new implication.

True: If I am over 21, then I am over 18.
Therefore true: If I am not over 18, then I am not over 21.

This can be expressed easily using negations. Having an implication "p => q" we define its contrapositive as the implication "¬ q => ¬ p". We have just argued (and formal logic agrees) that validity of a contrapositive and validity of the original implication are always the same: If one is true, so is the other and vice versa. Counterpositives are quite useful in mathematics, see Indirect proof in the next section.

We close this example with a remark you can safely skip to the next paragraph. You surely appreciate that we could have taken just any numbers in our example (as long as the first one is larger). We took those particular two because they have a meaning. In some countries, 21 is the legal age for drinking. In many more countries, 18 is the legal age for acquiring driving licence, state ID card, voting rights, and generally it is considered the age when one becomes adult. One particular way to express our model implication is therefore this: If you can (legally) drink, then you can drive. This is a true implication, but a funny one, it is a good example that there need not be any real, material connection between the two parts of a true implication, it is just a matter of how true/false values of those parts interact.

In mathematics we work a lot with sufficient and necessary conditions. In a typical case we are interested in whether some property P is satisfied, but the property is rather complicated and thus we cannot decide directly whether it works or not. Therefore we instead try to identify other conditions that are easier to check, we definitely prefer sufficient conditions (if we find that they are true, then also P is true), but we are also quite happy with necessary conditions (these restrict the range of situations under which we should look at P, since in situations when necessary conditions fail, also P must fail).

We have seen that having a true implication does not in general mean that we can reverse its direction and obtain a true implication. However, sometimes we get lucky and also the converse is true. Then we have an equivalence. Actually, do we? A true equivalence was defined as a situation when validities of expressions on both sides always agree. We will show that a two-way implication and equivalence are the same.

First, we will assume that we have true implications "p => q" and "q => p". Then also their contrapositives must be true and thus we have the following four statements.

  • If p is true, then q is true.
  • If q is true, then p is true.
  • If p is false, then q is false.
  • If q is false, then p is false.

But this means that p and q must have the same validity. Conversely, having an implication we also have the above four statements, in particular we have implications in both directions. The fact that equivalence is a two-way implication is suggested also by its notation "p <=> q".

Equivalences are great. Again, assume that we want to learn about some property q but we prefer not to mess with it. If we also have a true equivalence "p <=> q" available, then we simply check on p and whatever we learn will then be also true about q, which is great. This makes equivalences very desirable, but also rare, they are much harder to come by.

Since equivalence is a two-way implication, the statement on the left is both a necessary and sufficient condition for the statement on the right and vice versa. Equivalence is symmetric by its very nature. When working with equivalences we often replace them with implications and sometimes even those get expressed using disjunction as mentioned earlier.

[p <=> q]  =  [(p => q) ∧ (q => p)]  =  [(¬ p ∨ q) ∧ (¬ q ∨ p)].

Consider the following thingie: "x > 7". This is not a logical statement, since it cannot be assigned its truth value. However, it does become a statement if we specify what we mean by x. This is very useful, one can consider "statements with variable", logicians have fancy names for all of this of course and the reader is invited to dive into some nice book on predicate logic. As usuall, we will just look at the basics.

Consider the above comparison "x > 7". The easiest way to turn it into a statement is to fix some value for the variable. For instance,

for x = 3, x > 7

is a false statement, while

for x = 13, x > 7

is a true statement. However, this is too simple, we get more out of this when we start considering sets of values and we also specify how we choose from such a set. This is called quantifiers. Let M be some set of objects and let P be some property that can be applied to objects from M. For x from M we will denote by P(x) that P is true for this particular x. We use the following quantifiers:

General quantifier: ∀x∈M: P(x)   we read this "For every x from M, the property P is true for this x."

Obviously, this statement (as a whole) is true exactly if P is true for all x from the specified set.

Examples:
  • ∀n∈ℕ: n² + 1 > 0.
This is true, every natural number, when squared and then increased by 1, is positive.
  • ∀n∈{x∈ℕ; x is a prime}: n is odd.
This is not true, since 2 is a prime, so it lieas in the set we are considering, but it is not odd. This statement can be also stated in this way:
  • ∀n∈ℕ: (if n is a prime, then n is odd).

Existential quantifier: ∃x∈M: P(x)   we read this "There exists x in M such that the property P is true for this x."

Obviously, this statement (as a whole) is true exactly if P is true for at least one x from the specified set.

Examples:
  • ∃n∈ℕ: (n − 3)² > 1.
This is true, the condition is true for, say, n = 5, it is also true for n = 1. Just one would be enough, those extra is irrelevant, but it does not hurt.
  • ∃n∈ℕ: n² = 13.
This is not true, no natural number gives 13 when squared.

If P has more variables, then more quantifiers are needed. If they are not of the same kind, the the order is crucial. Consider the following examples:

  • ∀x∈ℝ ∃y∈ℝ:  y > x.
This says: Whenever somebody gives me a number, then I can find another that is larger. This is true. With this order of quantifiers, every x has its own y.
  • ∃y∈ℝ ∀x∈ℝ:  y > x.
This says: There is a number y such that all real numbers are smaller than this number. This is false. Here one y should work universally for all x.

One should know how to negate logical statements properly, this is needed for instance when forming a contrapositive of an implication or when proving by contradiction. We start by listing negations of the basic five logical operations:

  • ¬ [¬ p]  =  p;
  • ¬ [p ∧ q]  =  ¬ p ∨ ¬ q;
  • ¬ [p ∨ q]  =  ¬ p ∧ ¬ q;
  • ¬ [p => q]  =  p ∧ ¬ q;
  • ¬ [p <=> q]  =  (p ∧ ¬ q) ∨ (q ∧ ¬ p).

For quantifiers we have the following rule:

  • ¬ [∀x∈M:  P(x)]  =  ∃x∈M:  ¬ P(x);
  • ¬ [∃x∈M:  P(x)]  =  ∀x∈M:  ¬ P(x);

When you think about it, you realize all these rules are just a common sense. For instance, the opposite of "There is a person with blue hair" is "All people fail to have blue hair", exactly as the last rule above says.

The property P or the statements p, q themselves may be more complicated including some other quantifiers, so given a complicated expression to negate, one simply starts with the operation that is done last and works his way as deep as needed. As an example we return to the above statement with two quantifiers and negate it step by step.

Statement: ∀x∈ℝ ∃y∈ℝ:  y > x.
Negation: ∃x∈ℝ  ¬ [∃y∈ℝ:  y > x],   that is,   ∃x∈ℝ  ∀y∈ℝ:  ¬ [y > x],   that is,   ∃x∈ℝ ∀y∈ℝ:  y ≤ x.

You will see some examples of negations in the next section.

How can logic be applied? People refer to logic quite often (This is not logical!), but there are some problems with applying it to real life. The first problem lies with language. Although we normally use the same words (and, or, if-then), their colloquial meaning is not quite the same as formal logic has it. Probably the most frequent problem arises with implication. When parents tell you "If you are good, you will get some candy," they in fact also mean that if you are not good, then you will not get anything. In other words, they say implication but mean equivalence: "You will get some candy if and only if you are good." This general confusion about implications and equivalences is widespread, which explains why quite a few students are surprised when they hear for the first time what an implication actually is.

Another problem is in the use of "or", since people sometimes understand it in a different way. Namely, it is sometimes meant in the way that the whole statement is true when exactly one of the two compound statements is true, definitely not when both are true (that is the big difference compared to the proper "logical or"). For instance, when parents say "You eat your veggies or it's no desert for you," then they definitely do not expect that both variants can happen. This is often emphasised by using "either—or". Thus we in fact talk of a different operation, in formal logic we call it "exclusive or" and write "p xor q".

As you can see, interpreting what people say using formal logic can be tricky, there is no reliable way to translate everyday human speech into proper logical statements (especially since often the speaker himself does not know what he actually meant).

Leaving aside the problem of translating humanese into logic, there is another catch. The whole formal logic setup can deal only with statements, that is, with potential facts that are either true or untrue. Without going into details, there are two things that must be true if we want to apply formal logic successfully. First, it cannot happen that something would be both true and false at the same time. Second, the pairs "something—not something" must always cover all possibilities, on other words, one of them is always true. Formally we can say that the following two rules must be true: For any statement a, the statement a ∧ ¬ a must be false and the statement a ∨ ¬ a must be true. These two requirements are obviously related and equally obviously not true in real life. We actually work most of the time with categories that defy these basic requirements. A person can be a little bit good and a little bit not good, and about some people you simply do not know. Formal logic only knows black and white, while life is all shades of gray. It is small wonder then that logic is of little help in those really important problems of human existence, although it does help a lot in cleaning up arguments and streamlining thoughts. This explains why philosophers and theologians play with logic a lot, they are among the heaviest users of it. But it also helps to explain why these two fields do not offer any definite answers to problems of life, only opinions.

There are worlds which can be turned into worlds of black and white, namely natural sciences that deal with things measurable and categorizable. Foremost among them is mathematics, because it actually does not deal with the real world at all, it investigates artificial worlds constructed of pure thought. In fact, mathematics is logic plus some algebra thrown in. Thus if you want to understand math, you need some working knowledge of logic, what we put here should be enough.

Logic in mathematics