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.

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¬ Example: The negation of "We have at least two apples" is the statement "We have less than two apples".*p*.**Conjunction**of two statements is denoted" we read it*p*∧*q*"," and this compound statement is valid exactly if both*p*and*q*"*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" we read it*p*∨*q*"," and this compound statement is valid exactly if least one of*p*or*q*"*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" or*p*=>*q*"" we read it*p*→*q*"," *p*implies*q*","if *p*then*q*"," and some other ways as well. There are two situations when such a compound statement is true. First, if the*q*if*p*",**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" or*p*<=>*q*"" we read it*p*↔*q*"," *p*if and only if*q*"," 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 equivalent",*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.

p | q |
¬ p |
p ∧ q |
p ∨ q |
p => q |
p <=> q |

1 | 1 | 0 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 1 | 0 | 0 |

0 | 1 | 1 | 0 | 1 | 1 | 0 |

0 | 0 | 1 | 0 | 0 | 1 | 1 |

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*

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*"*p* is (the statement "I passed or
did not pass that exam" is always true).
On the other hand, the statement
*p* ∧ ¬ *p*"*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*"

**Example:**
Consider the statement
*p* => ¬ *q*",*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.

p | q |
¬ q |
p => ¬ q |

1 | 1 | 0 | 0 |

1 | 0 | 1 | 1 |

0 | 1 | 0 | 1 |

0 | 0 | 1 | 1 |

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*.*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*.*p* ∨ *q*",

There are also alternative ways to read an implication
*p* => *q*.*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*"*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*",*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*"**converse** *q* => *p*"

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*"*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*"**contrapositive** as the implication
*q* => ¬ *p*".

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*"*q* => *p*".

• 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*"*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*)*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*^{2} + 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*)*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)^{2} > 1.

This is true, the condition is true for, say, *n* = 5, it is also
true for *n* = 1.

•
*n*∈ℕ: *n*^{2} = 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*],*x*∈ℝ ∀*y*∈ℝ: ¬ [*y* > *x*],*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**a* ∨ ¬ *a*

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.