Ecole Supèrieure en Informatique de Sidi Bel Abbès
Première année Cycle Préparatoire Intégré
TD N o1 d’Algèbre 1
Eléments de Logique et méthodes de raisonnement
2024/2025
Exercice 1 : Soient P, Q et R trois propositions logiques :
1. Dresser dans deux tableaux différents les valeurs de vérités des propositions suivantes :
(P ∨Q), (P ∧Q), (P ∨Q), (P ∧Q), (P ∨ Q), (P ∧ Q) et ((P ∨ Q) ∧ R) , ((P ∧ Q) ∨ R) , ((P ∨ R) ∧ (Q ∨ R))
((P ∧ R) ∨ (Q ∧ R)). Donner parmi ces propositions celles qui sont logiquement équivalentes.
2. Donner les valeurs de vérités de ((P ⊕ Q) ∧ R) , ((P ⊕ Q) ∨ R) , ((P ∧ Q) ⊕ R) , ((P ∨ Q) ⊕ R),
((P ∧ R) ⊕ (Q ∧ R)) , ((P ∨ R) ⊕ (Q ∨ R)) ((P ⊕ R) ∧ (Q ⊕ R)) , ((P ⊕ R) ∨ (Q ⊕ R)). Que peut-
on conclure par rapport à la distributivité ?
3. Les propositions suivantes sont-elles des tautologies ? :
[(P =⇒ Q) ∧ P ] =⇒ Q et [(P ∨ P ) ∨ Q] =⇒ [(P ∧ P ) ∧ Q]
Exercice 2 h Connecteurs NAND (NON ET ) et NOR ( NON OU ) i
Pour deux propositions P et Q, on définit les connecteurs N AN D (↑) et N OR (↓) par
P N AN D Q ⇐⇒ P ↑ Q ⇐⇒ P ∧ Q, P N OR Q ⇐⇒ P ↓ Q ⇐⇒ P ∨ Q
1. Dresser les tables de vérité des deux connecteurs N AN D et N OR.
2. Déterminer P ↑ P, P ↓ P, P ↑ Q et P ↓ Q
3. Exprimer P , P ∧ Q, P ∨ Q et P =⇒ Q à l’aide des connecteurs N AN D et N OR.
Exercice 3 Sachant que (P ∧ Q) ⇐⇒ (P ∨ Q), montrer sans passer par les tables de vérités que
(P ∨ Q) ⇐⇒ (P ∧ Q)
De même sachant que ((P ∧ Q) ∨ R) ⇐⇒ ((P ∨ R) ∧ (Q ∨ R)) peut-on montrer que :
((P ∨ Q) ∧ R) ⇐⇒ ((P ∧ R) ∨ (Q ∧ R))
Exercice 4 En utilisant les quantificateurs, ecrire les propositions suivantes
1. Le carré de tout réel est positif. 2. Certains réels sont strictement supérieurs à leur carré.
3. Il n’y a pas d’entier supérieur à tous les autres. 4. Les réels ne sont pas tous des quotients d’entiers.
5. Il existe un entier multiple de tous les autres. 6. Entre deux réels distincts, il existe un rationnel.
7. Etant donnés trois réels, il y en a au moins deux de même signe.
Exercice 5 1. Donner les négations des propositions suivantes :
[∀x, Q], [∃x, Q], [∀x, ∃y, Q], [∃x, ∀y, Q], [∀x, ∀y, Q], [∃x, ∃y, Q]
2. Donner les négations, les réciproques ainsi que les contraposées des propositions suivantes :
[(∀x, Q) =⇒ (∃x, P )], [(∀x, Q) =⇒ (∀x, P )], [∀x, (Q =⇒ ∃x, P )], [∃x, (P =⇒ ∀x, Q)]
1
Exercice 6 Donner les négations et les contarposées des formules mathématiques suivantes :
1. ∀ > 0, ∃N ∈ N, ∀n ∈ N, ∀p ∈ N, [(n ≥ N ) =⇒ |un+p − un | ≤ ]
2. Soit x0 ∈ R et f : R → R :[∀ > 0, ∃η > 0, ∀x ∈ R, ((|x − x0 | ≤ η) =⇒ (|f (x) − f (x0 )| ≤ ))]
Exercice 7 1. Peut-on intervertir les quantificateurs 00 ∀n ∈ N00 et 00 ∃m ∈ N00 dans les propositions
suivantes.
a) ∀n ∈ N, ∃m ∈ N; m ≥ n. b) ∀n ∈ N, ∃m ∈ N; n2 ≥ m
2. Laquelle des implications suivantes est vraie :
[(∀x, ∃y, P ) =⇒ (∃y, ∀x, P )] ou bien [(∃y, ∀x, P ) =⇒ (∀x, ∃y, P )]
Exercice 8 Donner les négations des assertions suivantes puis dire si elles sont vraies ou fausses ?
1. [∀x ∈ R, ∃y ∈ R, (x + y > 0)] 2. [∃x ∈ R, ∀y ∈ R, (x + y > 0)]
3. ∀ε > 0, ∃α > 0, [(|x| < α) =⇒ (x2 < )] 4. ∀n ∈ N, n+1
2
∈ N.
Exercice 9 Ecrire les contraposées des implications suivantes et démontrer ces dernières. n est un
entier naturel, x et y sont des nombres réels
1. [( n premier) alors ( n = 2 ) ou ( n est impair)],
2. [(xy 6= 0) alors (x 6= 0) et (y 6= 0)] 3. [x 6= y alors (x + 1)(y − 1) 6= (x − 1)(y + 1)]
Exercice 10 Soient l1 , l2 ∈ R. Considérons les deux propositions suivantes :
P : ∀ > 0, |l1 − l2 | ≤ ⇒ l1 = l2 , Q : l1 6= l2 ⇒ ∃ > 0, |l1 − l2 | >
1. Montrer que les propositions P et Q sont équivalentes.
2. Montrer que la proposition Q est vraie et en déduire que la proposition P est vraie.
(Indication l1 6= l2 ⇒ |l1 − l2 | > 0)
Exercice 11 En utilisant un raisonnement par l’absurde, démontrer que :
1. La somme et le produit d’un nombre rationnel (non nul pour 00 ×00 ) et d’un nombre irrationnel
sont des nombres irrationnels.
2. La racine carré d’un nombre irrationnel positif est un nombre irrationnel.
3. Un rectangle a pour aire 170m2 . Montrer que sa longueur est supérieure à 13m.
Si n est le carré d’un nombre entier non
4. √ √ nul alors 2n n’est pas le carré d’un nombre entier.
p
5. 2 est un nombre irrationnel ( écrire 2 sous forme d’une fraction irréductible q puis discuter la
parité de p et q
6. Soit a ∈]1, 2[. Montrer que ∀x ∈
√ R, x2 + ax + 1 6= 0.
7. Montrer que pour tout n ∈ N∗ , n2 + 1 ∈ /N
Exercice 12 Montrer par récurrence les énoncés suivants :
Pn Pn
k n+1 2 n(n+1)(2n+1)
3. ∀n ≥ 1, (n + 1)! ≥ nk=1 k!
P
1. k=0 2 = 2 − 1 2. k=0 k = 6
4. 4n + 6n − 1 est divisible par 9 5. ∀x ∈ R+ , ∀n ∈ N∗ , (1 + x)n ≥ 1 + nx
