Democratic and Popular Republic of Algeria

Ministry of Higher Education and Scientic Research

University of Hassiba Benbouali Chlef

Faculty of Exact Sciences & Computer Science
Common Core Department of Exact Sciences and
Computer Science

Algebra 1
Chapter 1 : Logic concepts

Presented by

Dr. Meryem Abdelaziz

University year : 2023/2024

Contents

0.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.1.1 Logical connectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.1.2 Quantiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2 Type of Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.2.1 Direct reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.2.2 disjunction reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.2.3 Reasoning by Contrapositive: . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.2.4 Reasoning by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.2.5 Reasoning by counter example . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.2.6 Reasoning by recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1
CONTENTS 2

0.1 Generalities
Denition 1. (Logical proposition)

A logical proposition (or assertion ) is any statement that can be answered unambiguously as either

true or false, but never both. Propositions are often denoted P; Q; R; ...etc.

Remark 1. Every proposition has an associated truth value: True (abbreviated T or 1) or False

(abbreviated F. or 0).

Example 1. ˆ "Chlef is an Algerian town" is a true assertion. So, it's a logical proposi-

tion.

ˆ π is an integer: is a false proposition (truth value F=0).

ˆ The assertion "24 is a multiple of 2" is true and "19 is a multiple of 2" is a false assertion.

Denition 2. Two propositions P and Q are logically equivalent if they always have the same

truth value at the same time. This is called P ≡ Q.

0.1.1 Logical connectors

In logical reasoning, several propositions are used at the same time, and these are linked together
called "logical connectors". which are noted

ℸP, P ∧ Q, P ∨ Q, P =⇒ Q, P ⇔ Q

ˆ The negation:
the negation of a proposition P is the proposition denoted P or (ℸP ), which is true if P is
false and is false if P is true.

ˆ The disjunction :
the disjunction of the two propositions P and Q is the proposition P ∨ Q, also noted (P or
Q). which is false if P and Q are simultaneously false and true otherwise.

ˆ The conjunction :
The conjunction of the two propositions P and Q is the proposition P ∧ Q, also noted (P
and Q) which is true if P and Q are simultaneously true and false otherwise.

2 M.Abdelaziz
CONTENTS 3

ˆ The implication :
the implication of two propositions P and Q is the proposition P ⇒ Q, which is also read if
P then Q, it is false if P is true and Q is false and true otherwise.

ˆ The equivalence :
The equivalence of two propositions P and Q is the proposition P ⇔ Q, which is also read
P if and only if Q, and it is true if P and Q are simultaneously true or simultaneously false
and false otherwise.

We note that the tables below, which are called truth tables allow us to associate ve new assertions
with them
P ℸP

1 0
0 1

P Q P ∧Q P ∨Q P =⇒ Q P ⇔Q
1 1 1 1 1 1
1 0 0 1 0 0
0 1 0 1 1 0
0 0 0 0 1 1

Proposition 1. (Properties of connectors) Let P, Q and R be three logical propositions, we

have:

ˆ (P ∧ P ) ≡ P ≡ (P ∨ P ); P ≡ P.

ˆ (P ∨ Q) ≡ (Q ∨ P ).

ˆ (P ∧ Q) ≡ (Q ∧ P ).

ˆ (P ∨ P ) is still true.

ˆ (P ∧ Q) ≡ (P ∨ Q), and (P ∨ Q) ≡ (P ∧ Q) (Morgan's laws).

ˆ (P ∧ (Q ∨ R)) ≡ (P ∧ Q) ∨ (P ∧ R).

3 M.Abdelaziz
CONTENTS 4

ˆ (P ∨ (Q ∧ R)) ≡ (P ∨ Q) ∧ (P ∨ R).

ˆ (P ≡ Q) ≡ (P ≡ Q).

ˆ The proposition P ⇒Q ( P implies Q) is also dened by P ⇒ Q ≡ P ∨ Q.

ˆ The reciprocal of a logical implication P ⇒Q is the proposition Q ⇒ P.

ˆ The contrapositive of a logical implication P ⇒Q is the proposition Q⇒P

(i.e P ⇒ Q ≡ Q ⇒ P ).

ˆ The proposition P ⇔ Q (P is equivalent to Q) is also dened by

P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P );

for proof, just use the table of truths

Proof. ˆ (P ∧ P ) ≡ P ≡ (P ∨ P ); P ≡ P.

P P ∧P P ∨P P P
1 1 1 0 1
0 0 0 1 0

ˆ (P ∧ Q) ≡ (P ∨ Q);

P Q P Q P ∧Q (P ∧ Q) P ∨Q
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1

ˆ P ⇒ Q ≡ P ∨ Q and P ⇒ Q ≡ Q ⇒ P .

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

4 M.Abdelaziz
CONTENTS 5

0.2 Quantiers
Denition 3. ( predicate)

A predicate is any statement that depends on one or more variables and becomes a proposition

when the variables are replaced by the correct values, and is expressed as x has a property P; note

P (x).

Example 2. P (x); x is an integer (an integer: is called the predicate). If x = 2, 2 is an integer

(is a true proposition), and if x=π is an integer( is a false proposition).

Denition 4. Let P (x) be a predicate dened on a set E.

ˆ The quantier  Whatever (also called for all) noted ∀ ,denes the quantied assertion

 ∀x ∈ E : P (x) which is true when all elements x of E satisfy P (x).

ˆ The quantier  there exists, noted ∃, denes the assertion quantied assertion  ∃x ∈E:
P (x) which is true when we can nd (at least) one element x of E veries P (x).
The quantier whatever is qualied as universal and the quantier there exists as ex-

istential.

Example 3. ˆ The statement x2 + 2x − 3 ≤ 0 is a predicate. It can be true or false depending

on the value of x.
The statement x2 + 2x + 3 ≥ 0 is a (quantied) assertion. It is true because the quantity

x2 + 2x + 3 is positive for all x belong to R

ˆ The quantied assertion  ∃x ∈ R : x2 = 9. This is the case for the two real numbers −3
and 3.

5 M.Abdelaziz
CONTENTS 6

Rules for using quantiers

1. If the same quantier is used twice, the order is irrelevant. Quantiers can be
swapped in scripts such as :

(∀x ∈ E, ∀y ∈ F : P (x, y)) ≡ (∀y ∈ F ; ∀x ∈ E, : P (x, y))

(∃x ∈ E, ∃y ∈ F : P (x, y)) ≡ (∃y ∈ F ; ∃x ∈ E, : P (x, y))

2. if the quantiers are dierent, their order is important

∀x ∈ E, ∃y ∈ F : P (x, y) y depends on x

∃x ∈ E, ∀y ∈ F : P (x, y) y is independent of x

Example 4. ˆ ∀x ∈ R, ∃y ∈ R : y > x (we take y = x + 1).

ˆ ∃x ∈ R, ∀y ∈ R : x2 > y (for y = 0).

ˆ The following statments are dierent. The rst is true, the second is false

∀x ∈ R, ∃y ∈ R : (x + y = 0)

∃x ∈ R, ∀y ∈ R : (x + y = 0)

Proposition 2. (Negation of quantiers)

ˆ (∀x ∈ E : P (x)) ≡ (∃x ∈ E : P (x)).

ˆ (∃x ∈ E : P (x)) ≡ (∀x ∈ E : P (x)).

Example 5. ˆ the negation of (∀x ∈ R, ∃y ∈ R : y > x) is (∃x ∈ R, ∀y ∈ R :

y ≤ x).

ˆ the negation of (∃x ∈ R, ∀y ∈ R : x2 > y) is (∀x ∈ R, ∃y ∈ R : x2 ≤ y).

6 M.Abdelaziz
CONTENTS 7

0.3 Type of Reasoning

0.3.1 Direct reasoning

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

Example 6. Let n ∈ N; Let's show that if n is even then n2 is even. Indeed, if n

is even,
then ∃k ∈ N ; n = 2k; Which implies ∃k ∈ N ; n2 = (2k)2 = 4k2 = 2(2k2); Thus
∃k ∈ N ; n2 = 2k ′ , k ′ = 2k 2 ; So, n2 is even.

0.3.2 disjunction reasoning

If we wish to verify an assertion P (x) for all x in a set E , we show the assertion
for x in a part A of E , then for x not belonging to A. This is the disjunction or
case-by-case method.

Example 7. Prove that for all x ∈ R, |x| ≤ x2 − x + 1

Proof 1. Let x ∈ R. We distinguish two cases.

ˆ The rst case: x ≥ 0; Then |x| = x, one can write

x2 − x + 1 − |x| = x2 − x + 1 − x

= x2 − 2x + 1

= (x − 1)2 ≥ 0;

Thus x2 − x + 1 − |x| ≥ 0, so, x2 − x + 1 ≥ |x|,

7 M.Abdelaziz
CONTENTS 8

ˆ The second case: x < 0; Then |x| = −x, which follows:

x2 − x + 1 − |x| = x2 − x + 1 + x

= x2 + 1 ≥ 0;

So, x2 − x + 1 ≥ |x|, we conclude that for all x ∈ R, |x| ≤ x2 − x + 1.

0.3.3 Reasoning by Contrapositive:

Reasoning by contrapositive is based on the following equivalence:

P ⇒ Q ≡ Q ⇒ P.

Example 8. ∀n ∈ N, Let's prove that

n2 is uneven ⇒ n is uneven.

To do this, let's show that:

n is even ⇒ n2 is even,

which was demonstrated in the previous example.

0.3.4 Reasoning by Contradiction

Reasoning by the absurd to show P ⇒ Q is based on the following principle: we

assume a both that P is true and that Q is false, and we look for a contradiction.
If P is true, then Q must be true and therefore P ⇒ Q is true.

Example 9. Prove that ln2

ln3 is irrational.
We reason by the absurd. Let's assume ln 2
ln 3 ∈ Q. Then, there exists p ∈ Z and
q ∈ Z∗ such that
ln 2 p
=
ln 3 q
8 M.Abdelaziz
CONTENTS 9

or
p ln 3 = q ln 2 =⇒ ln 3p = ln 2q

Passing to the exponential, we obtain

3p = 2q

Since ln 2
ln 3 > 0 then necessarily p and q are of the same sign and non-null.
1st case : p, q ∈ N∗. In this case 2q is even ( product of even integers) while 3p is
uneven (product of uneven integers).
2nd case : p, q ∈ Z⧹N. Then −p and −q ∈ N. Also, 2−q is even (product of even
integers) which implies 3−p is uneven (product of even integers).

In both cases, therefore, the equality 3p = 2q gives an absurdity. So ln 2

ln 3 ∈
/ Q.

0.3.5 Reasoning by counter example

If you want to show that an assertion of the type ∀x ∈ E; P (x) is true, then for
each x in E you must P (x) is true. On the other hand, to show that this assertion
is false, all we need to nd x ∈ E such that P (x) is false.

Example 10. The proposition : ∀ a; b ∈ R : |a + b| = |a| + |b| is false because: For

example, we take: a = 4 and b = 7, we have : |4 + (−7)| =
̸ |4| + |7|.

0.3.6 Reasoning by recurrence

Many results can be expressed as n0 ∈ N

”∀n0 ∈ N ; P (n)”.

9 M.Abdelaziz
CONTENTS 10

A demonstration by recurrence shows that such a quantied assertion is true. The

principle of recurrence is used to show that a proposition P (n), dependent on n is
true for all n natural numbers such that n ≥ n0 with n0 ∈ N . The demonstration
proceeds in 3 steps:

ˆ Initialization: We prove that P (n0) is true.

ˆ Heredity: Assume that P (n) is true and prove the proposition P (n + 1) is

true.

ˆ Conclusion: Recall that, by the principle of recurrence, P (n) is true for all n
natural numbers.

Example 11. We will prove by recurrence the proposition:

P (n) : ∀n ∈ N, 9 divise 4n + 6n − 1 ;

We show that: ∃k ∈ N, 4n + 6n − 1 = 9k

ˆ Initialization: We have, P (0) : 4 × 02 + 6 × 0 − 1 = 9(0). Then P (0) is true.

ˆ Heredity: We assume that P (n) is true and we show that P (n + 1) is true.

We have

4n+1 + 6(n + 1) − 1 = 4 × 4n + 6n + 5

= 4(9k − 6n + 1) + 6n + 5

= 36k − 18n + 9

= 9(4k − 2n + 1)

= 9k ′ avec k ′ = 4k − 2n + 1 ∈ N;

Thus, P (n + 1) is true.
10 M.Abdelaziz
CONTENTS 11

ˆ Conclusion: Since P (0) and P (n) ⇒ P (n + 1); are true, then,

∀n ∈ N, 9 divise 4n + 6n − 1.

0.4 Exercises
Exercise 1. Are the following assertions true or false, and give their negation ?

ˆ ∃x ∈ R; ∀y ∈ R : x + y > 0.

ˆ ∀x ∈ R; ∃y ∈ R : x + y > 0.

ˆ ∀x ∈ R; ∀y ∈ R : x + y > 0.

ˆ ∃x ∈ R; ∀y ∈ R : y 2 > x.

Solution 1. 1. True or false statements:

ˆ ∃x ∈ R; ∀y ∈ R : x + y > 0 : False. It suces to take y = −x − 1 so that

x + y > 0. be false. Indeed, x + (−x − 1) = −1 < 0.

ˆ ∀x ∈ R; ∃y ∈ R : x + y > 0 : True. Because for a xed x, we choose

y = x + 1 so that x + (−x + 1) = 1 > 0.

ˆ ∀x ∈ R; ∀y ∈ R : x + y > 0 : False.
ˆ ∃x ∈ R; ∀y ∈ R : y 2 > x : True.
Just take x = −1; so for all y ∈ R, y 2 > −1.

2. The negation:

ˆ ∀x ∈ R; ∃y ∈ R : x + y ≤ 0;

ˆ ∃x ∈ R; ∀y ∈ R : x + y ≤ 0;

11 M.Abdelaziz
CONTENTS 12

ˆ ∃x ∈ R; ∃y ∈ R : x + y ≤ 0;

ˆ ∀x ∈ R; ∃y ∈ R : y 2 ≤ x;
√
Exercise 2. show that 2 is an irrational number.
√
Solution 2. First, suppose that 2 is a rational number. This would imply that
√
there exist integers p and q with q ̸= 0 such that p/q = 2. In fact, we can further
assume that the fraction p/q is irreducible. That is, p and q are coprime integers
√
(they have no common factor greater than 1). From p/q = 2, it follows that
√
p= 2q , and so p2 = 2q 2 . Thus p2 is an even number, which implies that p itself
is even (only even numbers have even squares). Because p is even, there exists an
integer r satisfying p = 2r. We then obtain the equation (2r)2 = 2q 2, which is
equivalent to 2r2 = q 2 after simplication. Because 2r2 is even, it follows that q 2
is even, which means that q is also even. We conclude that p and q are both even.
This contradicts the fact that p/q is irreducible. Hence, the initial assumption that
√ √
2 is a rational number must be false. That is to say, 2 is irrational.

Exercise 3. Let n be an integer. Show that if n2 − 1 is not divisible by 8, then n

is even.

Solution 3. We use the contrapositive reasoning:

n is uneven ⇒ (n2 − 1) is divisible by 8;

Then we have

n is uneven ⇒ n = 2k + 1 with k ∈ N;

⇒ n2 − 1 = 4k 2 + 4k

⇒ n2 − 1 = 4k(k + 1)

12 M.Abdelaziz
CONTENTS 13

k(k+1) is an even number. Therefore, k(k+1) = 2k ′ with k ′ ∈ N: Then n2 −1 = 8k ′

Thus, n2 − 1 is divisible by 8.
Conclusion: (n2 − 1) is not divisible by 8, so n is even.

Exercise 4. Prove that for all n ≥ 5; P (n) : 2n2 > (n + 1)2.

Solution 4. By using recurrence reasoning, we have

ˆ For n = 5, P (5) : 2(5)2 > (5 + 1)2. Then, P (5) is true.

ˆ We assume that P (n) is true and prove that P (n + 1) is true. We have

2(n + 1)2 = 2n2 + 4n + 2

≥ (n + 1)2 + 4n + 2

≥ n2 + 6n + 3

≥ (n + 2)2 + (2n − 1).

We have ∀n ≥ 5; 2n − 1 > 0. Then,

2(n + 1)2 ≥ (n + 2)2 .

So, P (n + 1) is true.

Since P (5) and P (n + 1) are true, hence : n ≥ 5, 2n2 > (n + 1)2.

13 M.Abdelaziz
Bibliography

[1] Cesar O. Aguilar , MATH 233 - Linear Algebra I. Department of Mathematics

SUNY Geneseo.

[2] Jim Heeron, Linear Algebra., http://joshua.smcvt.edu/linearalgebra

14