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)).