See discussions, stats, and author profiles for this publication at: [Link]

net/publication/384441716

Chapter1: Mathematical Logic

Chapter · September 2024

CITATIONS READS

0 621

1 author:

Beldjilali Gherici
University Mustapha Stambouli of Mascara
83 PUBLICATIONS 206 CITATIONS

SEE PROFILE

All content following this page was uploaded by Beldjilali Gherici on 29 September 2024.

The user has requested enhancement of the downloaded file.

 ici
Faculty of exacte sciences Department of Mathematics

her
Mathematics Lessons First Year University 2024-2025
Scale: Algebra 1 Professor: Beldjilali Gherici

Chapter I: Mathematical logic

iG
1 Proposition and Compound proposition Tb•rm˜ TySq˜ ¤ TySq˜
Definition 1 Statement or proposition:
A statement or proposition is declarative sentence (T§rb Tlm) which is either true (Ty}) or false (T·VA), and
cannot be true and false at the same time. If the sentence is neither true nor false, we say that it is an open sentence
(Twtf› Tlm).
Examples 1 1) Mecca is the capital of the Kingdom of Saudi Arabia.
l
- This is a proposition and it is false because the capital of the Kingdom of Saudi Arabia is Riyadh.
jila
2) The sum of two odd numbers (Ÿy§ r Ÿ§ dˆ) is even (¨¤E).
- This is a proposition and it is true because if a = 2n + 1 and b = 2m + 1 with n, m ∈ N then

a + b = 2(n + m + 1) = 2k, where k = n + m + 1.

3) All birds fly (ryW CwyW˜ ™•).

- This is a proposition and it is false because the chicken is a bird but it does not fly.
4) 5x + 1 is is a natural number (¨`ybV dˆ).
eld

- This is not a proposition because x is an unknown that cannot be determined. Hence, it is an open sentence.

Notation: We usually use the letters "P, Q, R,..." to denote propositions. Also, if the proposition is true, we will attach
it to the number "1", and if it is false, we will attach it to the number "0". Thus, we can create a table that includes all
possible cases of the proposition called the truth table (Tqyq˜ š¤d), as follows:

P
f. B

1
0

Definition 2 tautology and contradiction: ({’Ant˜ ¤ wK˜ )

. A proposition which is always true is called a tautology and is denoted by "T".
. A proposition which is always false is called a contradiction and is denoted by "F".

T F
1 0
1 0
Pro

Definition 3 Negation of proposition: (TyS’ ¨fž)

The negation of a proposition P (read: not P) is the proposition P.
The negation of a proposition P is a proposition that we symbolize P and its truth value is the opposite of the truth
value of the proposition itself.
P P
1 0
0 1

Examples 2 1) P : ”3 + 5 = 8”, is a true proposition. P : ”3 + 5 6= 8”, is a false proposition.

1
 2) Q : ”3 > 5”, is a false proposition. Q : ”3 ≤ 5”, is a true proposition.

Definition 4 Compound proposition: (Tb•r› TyS’)

A compound proposition is a proposition formed by joining other propositions together with logical connectives X ¤C)

ici
(TyqWn›.
Below we know some logical connections. Let P and Q be two propositions:
• The conjunction: (™}w˜ )
The conjunction of P and Q (read: P and Q) is the proposition P ∧ Q which is true if P and Q are both true.

her
• The disjunction: (™Of˜ )
The disjunction of P and Q (read: P or Q) is the proposition P ∨ Q which is false if P and Q are both false.

• The implication: ( zltF¯ )

P implies Q, is the proposition P ⇒ Q which is false if P is false and Q is true. Here, the proposition P is called
the hypothesis of the implication, and the Q is called the conclusion of the implication.

iG
• The equivalence or double implication: (¥Akt˜ )
P is equivalent to Q or (P if and only if Q), is the proposition P ⇒ Q which is true if P and Q are both true or both
false.
A truth table gives the truth values of a proposition for all possible combinations of truth values of the other propositions
from which it is made.
P
1
l Q
1
P∧Q
1
P∨Q
1
P⇒Q
1
P⇔Q
1
jila
1 0 0 1 0 0
0 1 0 1 1 0
0 0 0 0 1 1

Properties 1 We now set out to develop an algebra of propositions. To do so, we need some basic operations (logical
equivalences) that can be used. Each of the following can be verified (proved) with a truth table. It is a good idea to
memorize them, so that they are at your fingertips when needed.
eld

1) Idempotence: P ∧ P ⇔ P and P ∨ P ⇔ P.
2) Commutative: P ∧ Q ⇔ Q ∧ P and P ∨ Q ⇔ Q ∨ P.
3) Associative: (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) and (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R).
4) Distributative: P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) and P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)

5) Double Negation: P ⇔ P.
f. B

6) DeMorgan’s Laws: P ∧ Q ⇔ P ∨ Q and P ∨ Q ⇔ P ∧ Q.

7) Absorbtion: P ∧ T ⇔ P and P ∧ F ⇔ F.
8) Dominance: P ∨ T ⇔ T and P ∨ F ⇔ P.
9) tautology and contradiction: (P ∧ P) ⇔ F and (P ∨ P) ⇔ T .

9) Equivalence: (P ⇔ Q) ⇔ (P ⇒ Q) ∧ (Q ⇒ P).
Pro

10) Implies: (P ⇒ Q) ⇔ (P ∨ Q). (see Exerici 2).

Exercise 1 Compute the truth table of (P ∨ Q) ∧ P ∧ Q.

Solution.

P Q P∧Q P∧Q P∨Q (P ∧ Q) ∧ P ∧ Q

1 1 1 0 1 0
1 0 0 1 1 1
0 1 0 1 1 1
0 0 0 1 0 0

2
Exercise 2 Use the truth tables method to determine whether (P ⇒ Q) ∧ (P ⇒ Q) is valid.

Solution.

ici
P Q P P⇒Q P⇒Q (P ⇒ Q) ∧ (P ⇒ Q)
1 1 0 1 1 1
1 0 0 0 0 1
0 1 1 1 1 1
0 0 1 1 1 1

her
This means that the propositions P ⇒ Q and P ⇒ Q are equivalent i.e.,

P ⇒ Q ⇔ P ⇒ Q.

Exercise 3 Use truth tables to prove the following statements:

1): P ∨ (P ∧ Q) ⇔ P ⇔ P ∧ (P ∨ Q).
2): P ∧ (P ∧ Q) ⇔ Q ⇔ P ∨ (P ∨ Q).

Solution.

iG
P Q p∧Q P∨Q P ∨ (P ∧ Q) P ∧ (P ∨ Q) P ∧ (P ∧ Q) P ∨ (P ∨ Q)
1 1 1 1 1 1 1 1
1 0 0 1 1 1 0 0
0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0
l
Exercise 4 Use two methods to show that (P ⇒ Q) ∨ (P ⇒ Q) is valid.
jila
Solution.
First method: The truth table
P Q Q P⇒Q P⇒Q (P ⇒ Q) ∨ (P ⇒ Q)
1 1 0 1 0 1
1 0 1 0 1 1
0 1 0 1 1 1
0 0 1 1 1 1
eld

The formula is valid since it is satisfied by every interpretation.

Second method: Connections properties
With the help of the Exercise 2, we have

(P ⇒ Q) ∨ (P ⇒ Q) ⇔ (P ∨ Q) ∨ (P ∨ Q)
⇔ (P ∨ P) ∨ (Q ∨ Q)
⇔ P∨T
f. B

⇔ T.

Exercises 1 1) Use the truth table method to verify whether the following formulas are valid, satisfiable or unsatisfi-
able:
a) (P ⇒ Q) ∧ (P ⇒

Q).
b) (P ∨ Q) ⇒ R) ∨ P ∨
Q.
c) (P ⇒ Q) ∧ (Q ⇒ R) ⇒ (P ⇒ R).

2) Write the following propositions without the implication symbol, then give the negation of each.
Pro

a) (P ⇒ Q) ⇒ (P
⇒ Q.
b) P ⇒ (Q ⇒ R) ⇒ (P ⇒ Q) ⇒ (P ⇒ R).

2 Quantifiers (AmÌmkm˜ )
2.1 Quantifiers (AmÌmkm˜ )
If an assertion contains one or more variables (open sentence), it isn’t possible to know its truth value until something
about the variables is known. There are two options:
1. If values are given to the variables, then the assertion will be either true or false for those particular values.

3
 2. Specify the quantity (that is, number) of allowed replacements for each variable that result in the assertion being
true. This specification is an assertion that is either true or false, that is, it is a proposition.

Examples 3 .

ici
1) "x > 3" is an open sentence but for x = 5 we obtain 5 > 3, is a proposition and it is true.
2) There is a natural number where "x > 3" is a proposition and it is true (take for example x = 7).
3) " All natural numbers are not negative" is a proposition and it is true.
4) "All prime numbers are even". is a proposition and it is false ( 2 is a prime number and it is even).

Notation:

her
1. Every expression that includes a generalization, such as "all", "for all", "every" and "for each", we use the symbol
∀ and we call it the universal quantifier (¨lk˜ œmkm˜ ).
2. Every expression that includes existence, such as, "there exists", "there is", "there are" and "some", we use the
symbol ∃ and we call it the existential quantifier (© ww˜ œmkm˜ ).

Examples 4 .

iG
1) " All natural numbers are either positive or negative. (True)

∀n ∈ N, n ≥ 0.

2) There is a real number where "x2 + x + 1 = 0". (False)

∃x ∈ R, x3 + x2 + x + 1 = 0.

3) For every real number x there exists a real number y such that "x + y = 0". (True)
l ∀x ∈ R, ∃y ∈ R, x + y = 0.
jila
4) There exist two two integers x and y such that for every natural number z we have "x2 + y2 = z". (False: z = 3)

∀(x, y) ∈ Z2 , ∃z ∈ N, x2 + y2 = z.

From these examples we can conclude that we can express any declarative sentence using the symbols ∀ and ∃ and vice
versa. Let us explain this through the following example:
Consider the following true proposition: The product of every two consecutive natural numbers is even.
eld

We denote an bitrary natural number by " n", so the product of any two consecutive natural numbers is expressed by the
expression "n(n + 1)". Thus we have
∀n ∈ N, ∃k ∈ N, n(n + 1) = 2k.

Remark 1 The order of the quantifiers is very important.

Example 1 .
f. B

∀x ∈ R, ∃y ∈ R, x + y = 0, is true
∃y ∈ R, ∀x ∈ R, x + y = 0, is f alse

2.2 Negating Statements Involving Quantifiers (TmÌmk› TyS’ ¨fž)

Definition 5 Let p(x) be an open sentence involving the variable x.
1. The negation of the proposition "∀x, p(x)" is the proposition "∃x, p(x)".
2. The negation of the proposition "∃x, p(x)" is the proposition "∀x, p(x)".
Pro

In other words, The negation of the universal quantifier is the existential quantifier and vice versa.
Examples 5

1. Negation of "All Algerians are Arabs" is " There is an Algerian who is not an Arab".
2. Negation of "There is a bird that does not fly" is " All birds fly".
3. Negation of "∃x ∈ R, ∀y ∈ R, x + y = 0," is

∀x ∈ R, ∃y ∈ R, x + y 6= 0.

4
 4. Negation of "∀z ∈ N, ∃(x, y) ∈ Z2 , x2 + y2 = z," is
2
∃z ∈ N, ∀(x, y) ∈ Z , x2 + y2 6= z.

Exercise 5 Before a court judge, the doctor, the pharmacist and the patient each stated the following:

ici
Doctor: The patient is guilty and the pharmacist is innocent.
Pharmacist: I am innocent, but at least one of them is guilty.
Patient: If the doctor is guilty, the pharmacist is guilty too.
We denote by:
"D": "The doctor is innocent".
"P": "The pharmacist is innocent"

her
"M": "The patient is innocent".
1) Write the three statements using D, F, P and logical conjunctions.
2) Assuming all the statements are true, who is guilty?
3) Assuming they are all innocent, who lied to the judge?.
4) Assuming they were all guilty, whose confession was true?
Solution:
1) Doctor: " P ∧ F," Pharmacist: "F ∧ (D ∨ P)", Patient: "D ⇒ F."

iG
To answer the remaining two questions, we create a truth table.
Note: Given three simple propositions D, F and P, the table contains 8 cases. In general, if we have n simple proposi-
tions, the number of cases is 2n .
D F P D F P D∨P Doctor: P ∧ F Pharmacist: F ∧ (D ∨ P) Patient: D ⇒ F
1 1 1 0 0 0 0 0 0 1
1 1 0 0 0 1 1 1 1 1
1 0 1 0 1 0 0 0 0 1
1 0 0 0 1 1 1 l 0 0 1
0 1 1 1 0 0 1 0 1 0
jila
0 1 0 1 0 1 1 1 1 0
0 0 1 1 1 0 1 0 0 1
0 0 0 1 1 1 1 0 0 1
2) All the statements are true it means that the truth value of all statements is "1" and this condition is found in the
second row of the truth table. Hence, only the patient is guilty.
3) "They are all innocent" this means that the truth value of each of D, F and P is "1". this case is in the first row of the
table. So the ones who lied to the judge were the doctor and the pharmacist.
4) "They are all guilty" this means that the truth value of each of D, F and P is "0". this case is in the last row of the
eld

table. So, the only one who was honest was the patient.
Exercise 6 Three friends met: Samir, Ahmed and Khaled.
Khaled said, “I am 18 years old, two years younger than Ahmed and one year older than Samir".
Ahmed said, "I am not the youngest. There are three years between me and Samir, and he is 21 years old."
Samir said, "I am younger than Khaled. He is 19 years old, and Ahmed is three years older than Khaled."
- Knowing that each one lied in a third of his speech, determine the age of each one of them.
f. B

3 Types of Mathematical Proofs ( A¡rb˜ ªAmž
)

What is a proof? A proof is a logical argument that tries to show that a statement is true. Suppose we wish to prove an
implication P ⇒ Q. Here are some strategies we have available to try

3.1 Direct Proof (Proof by Construction)(AtntF¯ )

Assume P, and then use the rules of inference, axioms, definitions, and logical equivalences to prove Q.
Example 2 . Prove the statement: For all integers m and n, if m and n are odd integers, then m + n is an even integer.
Pro

Assume m and n are arbitrary odd integers. Then m and n can be written in the form
m = 2a + 1 and n = 2b + 1.
where a and b are also integers. Then
m+n = (2a + 1) + (2b + 1)
= 2(a + b + 1)
= 2k with k = a + b + 1,
Therefore, m + n is an even integer.
Exercise 7 Give a careful proof of the statement: For all integers m and n, if m is odd and n is even, then m + n is odd.

5
3.2 Proof by Contrapositive ({yqn˜ Hk` A¡rb˜ )
The idea of this proof depends on the validity of the following equivalence:
(P ⇒ Q) ⇔ (Q ⇒ P).

ici
Example 3 . Prove the proposition: For all integers m and n, if the product of m and n is even, then m is even or n is
even.
We can rewrite the proposition as follows:
P ⇒ (M ∨ N),
where P, M and N denotes "mn is even", "m is even" and "nis even" respectively.

her
We prove the contrapositive of the statement: If m and n are both odd integers, then mn is odd. i.e.,
M ∧ N ⇒ P.
So, suppose that m and n are arbitrary odd integers. Then m = 2a + 1 and n = 2b + 1, where a and b are integers. Then
mn = (2a + 1)(2b + 1)
= 4ab + 2a + 2b + 1
= 2(ab + a + b) + 1

iG
= 2k + 1 with k = ab + a + b,
Therefore, mn is an odd integer.
Exercise 8 Give a careful proof of this statement without assuming the result in the above Example.
For every integer n, if n2 is even, then n is even.

3.3 Proof by Contradiction (l˜ ¤
{’Ant˜A A¡rb˜ )

l
In this method of proof we assume the hypotheses are true and the conclusion is false and try to arrive at a contradiction.
The idea of this proof depends on the validity of the following equivalence:
jila
(P ⇒ Q) ⇔ P ∨ Q ⇔ P ∧ Q.
We can see that if P ∧ Q is false then P ⇒ Q is true.
Example 4 . Prove the statement is true: Let x and y be real numbers. If 5x + 25y = 2024, then x or y is not an integer.
Assume x and y are real numbers such that 5x + 25y = 2024, and assume that both x and y are integers. By the
distributive law,
5(x + 5y) = 2024.
eld

Since x and y are integers, this implies 2024 is divisible by 5. The integer 2024, however, is clearly not divisible by 5.
This contradiction establishes the result.
√ √
Exercise 9 For all positive real numbers a, b and c, if ab = c then a ≤ c, or b ≤ c.

3.4 Proof by Cases (¯A˜ ™Of A¡rb˜ )

Sometimes the hypothesis of a statement can be broken down into simpler cases that may be investigated separately. The
f. B

validity of a proof by cases rests on the equivalence

(P1 ∨ P2 ∨ ... ∨ Pn ) ⇒ Q ⇔ (P1 ⇒ Q) ∨ (P2 ⇒ Q) ∨ ... ∨ (Pn ⇒ Q) .
Example 5 a, b and c are three real numbers with different signs, one of which is completely positive, the second is
completely negative and the third is zero, so that the following implications are fulfilled.
a = 0 ⇒ b > 0, a>0⇒b<0 and b 6= 0 ⇒ c > 0.
Determine the signs of a, b and c.
This is a good example that illustrates the proof by cases well.
Case 1: Assume that a = 0 then b > 0 that is b 6= 0 from the third implication we get c > 0. This is a contradiction
Pro

because b and c have the same sign.

Case 2: Suppose now a > 0, from the second implication we get b < 0 i.e., b 6= 0 so, and from the third implication we
get c > 0. This is a contradiction too, hence a < 0.
From the third implication, if b 6= 0 then c > 0 and this is a contradiction because there is no zero number then, b = 0
and c > 0.
Answer: a < 0, b = 0 and c > 0
Exercise 10 Three friends met: Sameer, Ahmed and Khaled.
Khaled said, “I am 18 years old, two years younger than Ahmed and one year older than Sameer".
Ahmed said, "I am not the youngest. There are three years between me and Sameer, and he is 21 years old."
Sameer said, "I am younger than Khaled. He is 19 years old, and Ahmed is three years older than Khaled."
- Knowing that each one lied in a third of his speech, determine the age of each one of them.

6
 3.5 Proof by Induction (‰ rt˜A A¡rb˜ )
Proof by induction is a more advanced method of proving things, and to be honest, something that took me a while to
really grasp. This method is used to show that all elements in an infinite set have a certain property. This proof is based

ici
on two steps.
Step 1: Prove the validity of the proposition for an initial value.
Step 2: Assume the validity of the proposition for n and prove its validity for n + 1.

Example 6 . Prove that for all integers n, 1 + 2 + 3 + ... + n = n(n+1)

2 .
Step 1: For n = 1, from the left side it yields 1 and from the right side it yields f rac1(1 + 1)2 = 1. Then, the equality is
true for n = 1.

her
Note: For n = 2, from the left side it yields 1 + 2 = 3 (not 2) and from the right side it yields f rac2(2 + 1)2 = 3. Then,
the equality is true for n = 2.
Step 2: We suppose that 1 + 2 + 3 + ... + n = n(n+1)
2 and prove that 1 + 2 + 3 + ... + n + (n + 1) = (n+1)(n+2)
2 .
So, using the hypothesis

n(n + 1)
1 + 2 + 3 + ... + n + (n + 1) = + (n + 1)
2 
n 

iG
= (n + 1) + 1
2
n+2
= (n + 1)
2
(n + 1)(n + 2)
= .
2
This completes the proof.
l
Example 7 . Prove by induction that n3 + 2n is divisible by 3 for every non-negative integer n.
Let P(n) be the mathematical proposition "n3 + 2n is divisible by 3".
jila
Step 1: For n = 0, we have 03 + 2(0) = 0 = 03. So P(0) is correct.
Step 2: We suppose that P(n) is correct that is, n3 + 2n = 3k where k ∈ N. So, using the hypothesis

(n + 1)3 + 2(n + 1) = n3 + 3n2 + 3n + 1 + 2n + 2

= k3 + 2n + 3(n2 + n + 1)
= 3k + 3(n2 + n + 1) bytheinductionhypothesis
2
= 3(k + n + n + 1).
eld

That is what is required.

Exercises 2 Prove by induction that:

2 2
1) For all integers n, 13 + 23 + 33 + ... + n3 = n (n+1)
4 .
2) 9n − 1 is divisible by 8 for all non-negative integers.
3) For all positive integers,
f. B

n(n + 1)(n + 2)
(1 ∗ 2) + (2 ∗ 3) + (3 ∗ 4) + ... + n(n + 1) = .
3
4) 2n+1 > n2 for all positive integers.
Pro

7
View publication stats