Chapter 1

Logic Notions
1.1 Notions

Definition 1.1.1
— We call any relation P that is either true or false a "logical proposition".
— When the proposition is true, it is assigned the value 1.
— When the proposition is false, it is assigned the value 0.
— These values are called "Truth values of the proposition".

Example 1.1.2
r
1. "I am taller than you", is a proposition.
2. "2 + 2 = 4" is a proposition.
3. "2 × 3 = 7" is a proposition.
4. "For all x ∈ R ; we have x2 ≥ 0" is a proposition.
5. "How are you today ?" is not a proposition.

Thus, to define a logical proposition, it suffices to give its truth values. Generally, these values are put into a
table called a "Truth table".

1.1.1 Logical Operations

Definition 1.1.3 Negation : "P "

Given a logical proposition P , we call the negation of P the logical proposition P , which is false when P
is true and true when P is false, so we can represent it as follows :

P P
1 0
0 1

Definition 1.1.4 Conjunction : "∧"

Let P and Q be two logical propositions, we call "conjunction" of P and Q the proposition "P ∧ Q ", which

5
1.1. Notions CHAPITRE 1. LOGIC NOTIONS

is true when both P and Q are true and false otherwise. Its truth table :

P Q P ∧Q
1 1 1
0 0 0
1 0 0
0 1 0

Definition 1.1.5 Disjunction "∨"

Let P and Q be two logical propositions, we call "disjunction" of P and Q the proposition "P ∨ Q ", which
is true if either of the logical propositions P or Q is true. Its truth table :

P Q P ∨Q
1 1 1
0 0 0
1 0 1
0 1 1

Definition 1.1.6 Implication "⇒"

Consider two logical propositions P and Q, we denote "P ⇒ Q" the logical proposition that is false if P
is true and Q is false. The proposition P ⇒ Q reads "P implies Q ".

P Q P ⇒Q
1 1 1
0 0 1
1 0 0
0 1 1

Given two logical propositions P and Q, the truth table of P ∨ Q is as follows :

P P Q P ∨Q
1 0 1 1
0 1 0 1
1 0 0 0
0 1 1 1
We see that this table is identical to that of P ⇒ Q, so we say that the proposition P ⇒ Q is equivalent
to the proposition P ∨ Q :

Definition 1.1.7 Equivalence "⇔"

We say that the two logical propositions P and Q are logically equivalent if they are true simultaneously
or false simultaneously, and we denote "P ⇔ Q ", its truth table is :

P Q P ⇔Q
1 1 1
0 0 1
1 0 0
0 1 0

Algebra 1 Y. SOULA 6
1.2. Quantifiers CHAPITRE 1. LOGIC NOTIONS

1.1.2 DeMorgan’s Rules

Proposition 1.1.8
Let P and Q be two logical propositions, then :
1. P ∧ Q ⇔ P ∨ Q.
2. P ∨ Q ⇔ P ∧ Q.

Proof
We establish the proof of these rules by giving the truth values of the corresponding logical propositions.
1.
P Q P Q P ∧Q P ∧Q P ∨Q P ∨Q P ∨Q P ∧Q
1 1 0 0 1 0 1 0 0 0
0 0 1 1 0 1 0 1 1 1
1 1 0 1 1 0 1 0 1 0
1 0 0 1 0 1 1 0 1 0
0 1 1 0 0 1 1 0 1 0
1 0 0 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0 1 0
0 0 1 1 0 1 0 1 1 1
2.
P Q P Q P ∨Q P ∨Q P ∧Q
1 1 0 0 1 0 0
0 0 1 1 0 1 1
1 0 0 1 1 0 0
0 1 1 0 1 0 0

1.2 Quantifiers
1.2.1 Universal Quantifier ∀, or "for all"
A proposition P may depend on a parameter x. For example : "x2 ≥ 1 " the assertion P (x) is true or false
depending on the value of x.

Definition 1.2.1
∀x ∈ E, P (x), is true when the propositions P (x) are true for all elements x in the set E. We read "For
all x belonging to E, P (x)".

Example 1.2.2
1. ∀x ∈ [1; +∞[ ; x2 ≥ 1 is a true proposition.
2. ∀x ∈ R ; x2 ≥ 1 is a false proposition.
3. ∀n ∈ N ; n(n + 1) is divisible by 2 is true.

1.2.2 Existential Quantifier ∃, or "there exists"

Definition 1.2.3
∃x ∈ E; P (x), is true when we can find at least one x from E for which P (x) is true. We read "there exists
x belonging to E such that P (x) is true".

Algebra 1 Y. SOULA 7
1.3. Types of Reasoning CHAPITRE 1. LOGIC NOTIONS

Example 1.2.4
1. ∃x ∈ R ; x(x − 1) < 0 is true.
2. ∃n ∈ N ;n2 − n > n is true.
3. ∃x ∈ R ; x2 = −4 is false.

1.2.3 Negation of Quantifiers

Definition 1.2.5
1. The negation of "∀x ∈ E; P (x)" is "∃x ∈ E; P (x)".
For example, the negation of "∀x ∈ R; x2 ≥ 1 " is the assertion "∃x ∈ R; x2 < 1".
2. The negation of "∃x ∈ E; P (x)" is "∀x ∈ E; P (x)".
For example, the negation of "∃n ∈ N; n2 − n > n" is the assertion "∀n ∈ N; n2 − n ≤ n".
3. Negation of complex sentences : for example, the proposition "∀x ∈ E, ∃y ∈ E ; P (x; y)"
its negation is "∃x ∈ E, ∀y ∈ E ; P (x; y)".
For example, the negation of "∀x ∈ R, ∃y ∈ R, x + y > 0" is "∃x ∈ R, ∀y ∈ R, x + y ≤ 0".

Note 1.2.6
The order of quantifiers is very important. For example, the two logical sentences

∀x ∈ R, ∃y ∈ Rx + y > 0,

and
∃ x ∈ R, ∀ y ∈ Rx + y > 0,
are different.
The first one is true, the second one is false. Indeed, the first sentence asserts that "For every real number
x, there exists a real number y (which may depend on x) such that x + y > 0" (for example, for a given
x we can take y = −x + 1). So, it is a true sentence. On the other hand, the second one reads : "There
exists a real number y, such that for every real number x, x + y > 0." This sentence is false, it cannot be
the same y that works for all x.

1.3 Types of Reasoning

Definition 1.3.1 Direct Reasoning

We want to show that the proposition "P ⇒ Q" is true. We assume that P is true and then show that Q
is true.

Example 1.3.2
Show that
x+y
∀x, y ∈ R+ , x≤y⇒x≤ ≤ y.
2

Proof
We have
x+y
x ≤ y ⇒ x + x ≤ x + y ⇒ 2x ≤ x + y ⇒ x ≤ . (1.1)
2
x+y
y ≥ x ⇒ y + y ≤ x + y ⇒ 2y ≥ x + y ⇒ y ≥ . (1.2)
2
From (1.1) and (1.2) we have :
x+y
x≤ ≤ y.
2

Algebra 1 Y. SOULA 8
1.3. Types of Reasoning CHAPITRE 1. LOGIC NOTIONS

So
x+y
∀x, y ∈ R+ , x≤y⇒x≤ ≤ y,
2
is true.

Definition 1.3.3 Case by Case

If we want to verify a proposition P (x) for all x in a set E, we show the proposition P (x) for x ∈ A ⊂ E,
and then for x ∈
/ A.

Example 1.3.4
Show that : ∀x ∈ R ; |x − 1| ≤ x2 − x + 1.

Proof
1. If
x ≥ 1, |x − 1| = x − 1.
Then,
x2 − x + 1 − |x − 1| = x2 − x + 1 − x + 1 = x2 − 2x + 2 = (x − 1)2 + 1 ≥ 0.
So
x2 − x + 1 ≥ |x − 1| .
2. If
x < 1, |x − 1| = −(x − 1).
Then,
x2 − x + 1 − |x − 1| = x2 − x + 1 − (−x + 1) = x2 − x + 1 + x − 1 = x2 ≥ 0.

So
x2 − x + 1 ≥ |x − 1| .

Conclusion, in all cases

∀x, ∈ |x − 1| ≤ x2 − x + 1.

Definition 1.3.5 Contrapositive

Reasoning by "contraposition" is based on the following equivalence :

(P ⇒ Q) ⇔ (Q ⇒ P ).

So, if we want to show the assertion ”P ⇒ Q” we actually show that if Q is true. Then, P is true.

Example 1.3.6
Show that : ∀n ∈ N ; n2 is even then n is even.

Proof
We want to show that if n2 is odd ⇒ n is odd.
′
∀ n is odd, then there exists k ∈ N such that n = 2k+1 Then, n2 = 4k 2 +4k+1 = 2(2k 2 +2k)+1 = 2k +1.
2
So, n is odd.

Algebra 1 Y. SOULA 9
1.3. Types of Reasoning CHAPITRE 1. LOGIC NOTIONS

Definition 1.3.7 Absurd

Reasoning by "absurd" to show that "P ⇒ Q" is based on the following principle : we assume both that
P is true and Q is false. We seek a contradiction. Thus if P is true then Q must be true and therefore
"P ⇒ Q" is true.

Example 1.3.8
Show that : ∀x, y ∈ R+ . If,
x y
= .
1+y 1+x
Then, x = y.

Proof
x y
We assume that = and x ̸= y.
1+y 1+x
Since
x y
= .
1+y 1+x
Then,
x(1 + x) = y(1 + y).
So
x + x2 = y + y 2 .
Hence
x2 − y 2 = −x + y.
So,
(x − y)(x + y) = −(x − y).
Since x ̸= y. Then, x − y ̸= 0 and so by dividing by x − y we get x + y = −1 this is a contradiction(the
sum of two positive numbers is positive). Conclusion, ∀x, y ∈ R+ . If,
x y
= .
1+y 1+x
Then, x = y.

Definition 1.3.9 Counterexample

By counterexample to show that "∀x ∈ E ; P (x)” is false. It suffices to find x ∈ E, such that P (x) is false.

Example 1.3.10
Show that "every positive integer is the sum of three squares" is false.

Proof
Let’s take a counterexample. Consider the integer n = 7, the squares less than 7 are 0; 1; 4 but 0+1+4 ̸= 7.

Definition 1.3.11 Recurrence

The principle of "recurrence" allows us to show that a proposition P (n) depending on n, is true for all n
∈ N. The proof by recurrence proceeds in three steps :
1. Initialization : we verify that P (0) is true.
2. Heredity : we assume n > 0 given with P (n) true. Then, we demonstrate that the proposition
P (n + 1) at the next rank is true.

Algebra 1 Y. SOULA 10
1.3. Types of Reasoning CHAPITRE 1. LOGIC NOTIONS

3. Conclusion : we recall that by the principle of recurrence P (n) is true for all n ∈ N.

Example 1.3.12
Show that
n
X n(n + 1)(2n + 1)
∀n ∈ N, P (n) = k2 = .
6
k=0

Proof
1. Initialization : For n = 0, we have 02 = 0. So, P (0) is true.
2. Heredity : For n > 0, we assume that P (n) is true, i.e
n
X n(n + 1)(2n + 1)
k2 = ,
6
k=0

is true, and we show that

n+1 n+1
X (n + 1)(n + 2)(2(n + 1) + 1) X 2 (n + 1)(n + 2)(2n + 3)
P (n + 1) = k2 = = k = ,
6 6
k=0 k=0

is true.
P (n) is true so
n
X n(n + 1)(2n + 1)
k 2 = 02 + 12 + 22 + .... + n2 = .
6
k=0

We have :
n+1
X
k2 = 02 + 12 + 22 + .... + n2 + (n + 1)2 ,
k=0
n(n + 1)(2n + 1) n(n + 1)(2n + 1)
= + (n + 1)2 = + (n + 1)2 ,
6 6
(n + 1)(n + 2) + (2n + 3)
= ,
6
(n + 1)(n + 2)(2n + 3)
= .
6
Hence P (n + 1) is true.
3. Conclusion,
n
X n(n + 1)(2n + 1)
∀ n ∈ N, k2 = .
6
k=0

Algebra 1 Y. SOULA 11