It is advantageous to write matematical statements in an abbreviated form using the symbolism of predicate logic. This area of mathematics will be discussed in detail in the Mathematical logic course (BIE-MLO). Using this approach, logical structure of statements that might otherwise be hidden from the reader behind sentences of natural (in our case English) language will emerge. At this point we will only briefly summarize the basics that are already known to the reader.
An elementary proposition is a sentence for which we can decide whether or not it is true. We denote propositions by capital letters $A, \ B, \ C, \ldots$ We often meet propositions which depend on a parameter $x$. We call them predicates and denote by $A(x)$. Different values of $x$ therefore yield different predicates $A(x)$. Here are a couple of examples.
Let $x$ be an inhabitant of the Earth. $A(x)$ denotes the statement „$x$ is a man“. If $a$ denotes the author of this text then $A(a)$ is false.
Let $x$ be a natural number. $B(x)$ denotes the statement „$x$ is even“. Then for instance $B(2)$ and $B(4)$ are true but $B(99)$ is not.
Let's recall basic propositional connectives (operations), which serve to construct more complex propositions from simpler ones. They are:
$\neg A$, negation, $A$ is false.
$A \wedge B$, conjunction, $A$ and $B$ are true at the same time.
$A \vee B$, disjunction, $A$ is true or $B$ is true.
$A \Rightarrow B$, implication, if $A$ is true then so is $B$, $A$ implies $B$.
$A \Leftrightarrow B$, equivalence, $A$ is true if and only if $B$ is true, $A$ is equivalent to $B$.
The truth values of propositional connectives are determined by the truth table below depending on truth values of elementary propositions $A$ and $B$.
| \(A\) | \(B\) | \(\neg A\) | \(A \wedge B\) | \(A \vee B\) | \(A \Rightarrow B\) | \(A \Leftrightarrow B\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
In order to quantify variables in propositional formulas, we introduce three quantifiers
$\forall$, universal quantifier, for every, for all.
$\exists$, existential quantifier, there exists, for some.
$\exists!$, $\exists_1$, there exists just one.
If a variable $x$ ranges over all real numbers, we write $\forall x \in \R$. Similarly, if we say there exists an integer $k$, we write $\exists k \in \Z$. For clarity, we separate quantifiers in a formula by parentheses.
A natural number $p$ greater than $1$ is a prime number, if every natural number $k$ which is a factor of $p$ is equal to $1$ or to $p$ itself. When we write it using quantifiers and propositional connectives we get this formula
here we use $k|p$ to denote the predicate with the meaning „$k$ is a factor of $p$“.
Goldbach's conjecture is a simple mathematical statement which has been numerically tested for milions of cases but which has not been proved yet. This conjecture says that every even natural number greater than 2 can be expressed as the sum of two primes. If we denote the set of all primes by $P$ and the set of all even numbers by $2\N$ then we can write Goldbach's conjecture as a formula
At the end of this section we will clarify one term frequently used (not only) in mathematical literature, which is that of a „sufficient“ and a „necessary“ conditions. If $A \Rightarrow B$ is true then $A$ is a sufficient condition for $B$ and $B$ is a necessary condition for $A$.
The reason to use these names should be obvious. If $A \Rightarrow B$ is true and if we know that $A$ is true then $B$ must be true as well! Therefore $A$ is sufficient for $B$ to be true. On the other hand, if $A \Rightarrow B$ is true and if we know that $B$ is false then $A$ must be false as well. I.e. for $A$ to be true $B$ must necessarily be true.