In this introductory chapter some mathematical notions are presented rapidly

implication, where is the 'hypothesis' or 'assumption', the 'consequence'
or 'conclusion'. By definition, the formula is false if p is true and false,
otherwise it is always true. In other words the implication does not allow to deduce
a false conclusion from a true assumption, yet does not exclude a true conclusion
being implied by a false hypothesis. Thus the statement 'if it rains, I'll take the
umbrella' prevents me from going out without umbrella when it rains, but will not
interfere with my decision if the sky is clear.
Using p and q it is easy to check that the formula has the same truth
value of Therefore the connective can be expressed in terms of the basic
connectives and
Other frequent statements are structured as follows: 'the conclusion is true
if and only if the assumption is true', or 'necessary and sufficient condition for a
true is a true '. Statements of this kind correspond to the formula ( is

6 1 Basic notions

(logically) equivalent to ), called logic equivalence. A logic equivalence is true

if and are simultaneously true or simultaneously false, and false if the truth
values of and differ. An example is the statement 'a natural number is odd if
and only if its square is odd'. The formula is the conjuction of and
in other words and ( ) ) have the same truth value.
Thus the connective can be expressed by means of the basic connectives
and .
The formula p ⇒ q (SL statement like 'if , then ) can be expressed in various
other forms, all logically equivalent. These represent rules of inference to attain
the truth of the implication. For example, p ⇒ q is logically equivalent to the
formula , called contrapositive formula; symbolically

This is an easy check: is by definition false only when is true and false,
i.e., when is true and false. But this corresponds precisely to the falsehood
of ,. Therefore we have established the following inference rule: in order
to prove that the truth of implies the truth of , one may assume that the
conclusion is false and deduce from it the falsehood of the assumption . To
prove for instance the implication 'if a natural number is odd, then 10 does not
divide it', we may suppose that the given number is a multiple of 10 and (easily)
deduce that the number must be even.
A second inference rule is the so-called proof by contradiction, which we will
sometimes use in the textbook. This is expressed by

In order to prove the implication one can proceed as follows: suppose p is
true and the conclusion is false, and try to prove the initial hypothesis false.
Since is also true, we obtain a self-contradictory statement.
A more general form of the proof by contradiction is given by the formula

where is an additional formula: the implication is equivalent to assuming
true and false, then deducing a simultaneously true and false statement (note
that the formula is always false, whichever the truth value of r).