Introduction to Mathematical Logic

Sections A, B, C, D
September 23, 2023

1 Propositional Calculus
1.1 Definition
Definition: A proposition is a declarative sentence (or statement) that can be true (T) or false
(F) but not both at the same time.

Notation We use capital letters to denote a proposition ; for example: P , Q or R...

"T" stands for "true".

"F" stands for "False".

T and F are called truth values of P .

Examples

1. "2 is a natural number": is a proposition (simple).

1
2. " is an irrational number": is proposition.
2
3. " Where are you?": is not a proposition.

4. "Close the door": is not a proposition.

1.2 Logical connectives (Propositional connectives)

1.2.1 Logical negation or negation

Definition: Let P be a proposition; "not" P , denoted P , is a proposition which has the

following truth table:
P P
T F
F T

1.2.2 Logical Disjunction

1
 Definition: Disjunction of P and Q, denoted P ∨ Q, is a proposition which has the
following truth table:
P Q P ∨Q
T T T
T F T
F T T
F F F

P ∨ Q is read P or Q.

1.2.3 Logical conjunction

Definition: Conjunction of P and Q, denoted P ∧ Q, is a proposition which has the

following truth table:
P Q P ∧Q
T T T
T F F
F T F
F F F

P ∧ Q is read P and Q.

1.2.4 Logical implication

Definition: Let P and Q be propositions; we denote by P =⇒ Q a proposition whose

truth table is as follows:

P Q P =⇒ Q
T T T
T F F
F T T
F F T

Remark
1. P =⇒ Q is read "if P then Q ".
2. P is called assumption ; Q is called conclusion.

Definition:

1 The proposition Q =⇒ P is called the converse of P =⇒ Q .

2 The proposition Q =⇒ P is called the contrapositive of de P =⇒ Q.

2
1.2.5 Logical equivalence

Definition: Let P and Q propositions.

We designe by P ⇐⇒ Q a proposition whose truth table is as follows:

P Q P ⇐⇒ Q
T T T
T F F
F T F
F F T

P ⇐⇒ Q is read P if and only if Q or P is equivalent to Q.

1.3 Tautology

Definition: Tautology is a compound proposition which is true for every truth value of the
individual propositions.

Examples Prove that these propositions are tautologies:

1. (P ⇐⇒ Q) ⇐⇒ ((P =⇒ Q) ∧ (Q =⇒ P ))
Denote this proposition α; then construct its truth table.

P Q P =⇒ Q Q =⇒ P (P =⇒ Q) ∧ (Q =⇒ P ) P ⇐⇒ Q α
T T T T T T T
T F F T F F T
F T T F F F T
F F T T T T T

All the truth values of α are true then α is tautology.

2. (P =⇒ Q) ⇐⇒ (Q =⇒ P )
Denote this proposition β; construct its truth table.

P Q P =⇒ Q Q =⇒ P β
T T T T T
T F F F T
F T T T T
F F T T T

All the truth values of β are true then α is tautology.

Remark Let α and β be compound propositions;

α ⇐⇒ β is a tautology if and only if α and β have the same truth values.

1.4 Exercice
Prove that these propositions are tautologies:

1. P ⇐⇒ P

3
 2. (P =⇒ Q) ⇐⇒ (Q =⇒ P )
 
3. (P =⇒ Q) ⇐⇒ P ∨Q .
 
4. P =⇒ Q ⇐⇒ P ∧Q .
 
5. P ∧ Q ⇐⇒ P ∨Q . De Morgan’s laws
 
6. P ∨ Q ⇐⇒ P ∧Q . De Morgan’s laws

7. (P ⇐⇒ Q) ⇐⇒ ((P =⇒ Q) ∧ (Q =⇒ P ))

8. (P ∧ Q) ⇐⇒ (Q ∧ P ), ∧ is commutative

9. (P ∨ Q) ⇐⇒ (Q ∨ P ) , ∨ is commutative

10. (P ∧ (Q ∨ R)) ⇐⇒ ((P ∧ Q) ∨ (P ∧ R)), ∧ is distributif with respect to ∨

11. (P ∨ (Q ∧ R)) ⇐⇒ ((P ∨ Q) ∧ (P ∨ R)), ∨ is distributif with respect to ∧

1.5 Logical equivalence

If two propositions P and Q have the same truth values , they are called logically equivalent
and we denote this by P ≡ Q.

Remark
1. Warning : ≡ is not a connective.
2. We can see that P ≡ Q if and only if P ⇐⇒ Q is a tautology.

2 Quantified expression
2.1 Introduction to Predicate calculus

Definition: In literature, a predicate is the part of sentence that tells us something about
the subject. It contains the verb.

Exemple
1. The lighthouse was damaged in the storm.
"was damaged in the storm" is the prédicat".
2. Birds are chirping outside the windows .
"are chirping outside the windows" is the predicat.

Definition:In mathematics, a predicate is a statement that contains variables and it may

be true or false depending on the values of theses variables.
The domainof a predicate variable is the set ,E, of all values that may be subtituted for the
variables.

4
Examples

1. E = The set of real numbers..

P (x) :" x > 5".
For x = 1 ,P (1) is false.
For y = 7 ,P (7) is true.

2. E = the set of integers.

P (x, y) :" x + y is odd".
P (2, 6) is false.
P (3, 4) is true.

2.2 Quantifiers
2.2.1 Universal quantifier

The universal quantifier is denoted ∀ , it is read "for all" or "for every" or "for each" .
Let E be a non empty set, and a predicate P (x)

∀x ∈ D P (x)

is a proposition which is true if and only if P (x) is true for all values of x in E.
∀x ∈ D P (x) means every x in E has property P .

Example

D=R.

P (x) :" x + 1 > x".

∀x ∈ R P (x) is a true proposition.

Remark

1. (∀x ∈ D P (x)) is false if and only if we find a value of x in E that P (x) is false.

2. An element x0 in E for which P (x0 ) is false is called a counterexample of ∀x ∈

D P (x).

2.2.2 Existential quantifier

Existential quantifier is denoted ∃ , it is read "there exists" or "there is" or "for at least
one" .
Let E be a non empty set, and a predicate P (x)

∃x ∈ D P (x)

is a proposition which is true if and only if there is an x for which P (x) is true .

Example

5
 1. D = R.
P (x) :" x > 0".
∃x ∈ R P (x) is true proposition.

2. E = N
Q(x, y) :" x divides y".
∃x ∈ N∗ ∀y ∈ N∗ Q(x, y) is a true proposition.

Remark
∃x ∈ D P (x) is false if and only if P (x) is false for every x in E.

2.2.3 Negating quantified expression

∗ The negating of ∀x ∈ E P (x) is ∃x ∈ E P (x)

∗ The negating of ∃x ∈ E P (x) is ∀x ∈ E P (x)

Example Prove that these propositions are true:

1. ∀x ∈ R x2 + x + 1 > 0.

2. ∀x ∈ Q ∀y ∈ Q (x + y) ∈ Q.

3 Analysing proof techniques

3.1 Proof by contrapositive

To prove that P =⇒ Q is true , we prove that Q =⇒ P is true since P =⇒ Q and

Q =⇒ P are logically equivalent .

Example : Prove that  

∀n ∈ N n2 is even =⇒ n is even

3.2 Proof by contradiction

The general structure of a proof by contradiction is:

To show that P is true

assume P is false.

Show that P being false implies something that cannot be true.

Conclude therefore that P is true.

√
Exemple Prove that 2 is irrational.