1Proofs and logic

IA Numbers and Sets



1.3 Logic
Mathematics is full of logical statements, which are made of statements and
logical connectives. Usually, we use shorthands for the logical connectives.
Let
P
and
Q
be statements. Then
P Q
stands for
P
and
Q
”;
P Q
stands
for
P
or
Q
”;
P Q
stands for
P
implies
Q
”;
P Q
stands for
P
iff
Q
”;
¬P
stands for “not
P
”. The truth of these statements depends on the truth of
P and Q . It can be shown by a truth table:
P Q P Q P Q P Q P Q ¬P
T T T T T T F
T F F T F F F
F T F T T F T
F F F F T T T
Certain logical propositions are equivalent, which we denote using the
sign.
For example,
¬(P Q) (¬P ¬Q),
or
(P Q) (¬P Q) (¬Q ¬P ).
By convention, negation has the highest precedence when bracketing. For
example, ¬P ¬Q should be bracketed as (¬P ) (¬Q).
We also have quantifiers. (
x
)
P
(
x
) means “for all
x
,
P
(
x
) is true”, while
(x)P (x) means “there exists x such that P (x) is true”.
The quantifiers are usually bounded, i.e. we write
x X
or
x X
to mean
“for all x in the set X and “there exists x in the set X respectively.
Quantifiers are negated as follows:
¬(x)P (x) (x)(¬P (x));
¬(x)P (x) (x)(¬P (x)).