Logique et ensembles : exercices de maths Licence L1 à télécharger en PDF

1 Nier une phrase quantifiée ★★★

Écrire la négation de chacune des propositions suivantes, puis dire laquelle des deux (proposition ou négation) est vraie.

1. \(\forall x \in \mathbb{R},\ x^2 + 1 > 0\).
2. \(\exists n \in \mathbb{N},\ 2n + 1 = 100\).
3. \(\forall x \in [0, 1],\ x^2 \leqslant x\).

2 Table de vérité de l’implication ★★★

Dresser la table de vérité de \(P \Rightarrow Q\), de \(\neg P \lor Q\) et de \(\neg Q \Rightarrow \neg P\). Que constate-t-on ?

3 Vrai ou faux avec quantificateurs ★★★

Dire si chaque proposition est vraie ou fausse en justifiant (contre-exemple ou preuve).

1. \(\forall x \in \mathbb{R},\ x^2 \geqslant x\).
2. \(\exists x \in \mathbb{R},\ x^2 = x\).
3. \(\forall n \in \mathbb{N},\ n^2 + n \text{ est pair}\).

4 Opérations sur des ensembles de diviseurs ★★★

Soit \(A\) l’ensemble des diviseurs de \(24\) et \(B\) celui des diviseurs de \(36\), dans \(\mathbb{N}^*\). Écrire \(A\), \(B\), \(A \cap B\), \(A \cup B\), \(A \setminus B\) et \(B \setminus A\).

5 Couples et produit cartésien ★★★

Soit \(E = \{1, 2, 3\}\) et \(F = \{x, y\}\).

1. Écrire tous les éléments de \(E \times F\), puis de \(F \times E\).
2. Combien d’éléments ont \(E \times F\) et \(E \times E\) ?
3. A-t-on \(E \times F = F \times E\) ?

6 Contraposée et réciproque ★★★

Pour chaque implication, écrire la contraposée et la réciproque, puis dire si la réciproque est vraie.

1. « Si un quadrilatère est un carré, alors ses quatre côtés sont égaux. »
2. « Si \(n\) est un multiple de \(10\), alors \(n\) est un multiple de \(5\). »

7 Somme des premiers nombres impairs ★★★

Démontrer par récurrence que, pour tout \(n \geqslant 1\), \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\).

8 Les parties d’un ensemble à trois éléments ★★★

Soit \(E = \{a, b, c\}\).

1. Écrire toutes les parties de \(E\), rangées par nombre d’éléments.
2. Combien de parties possède un ensemble de \(5\) éléments ?
3. Les affirmations \(a \in \mathcal{P}(E)\) et \(\{a\} \in \mathcal{P}(E)\) sont-elles vraies ?

9 Inclusion-exclusion dans un club ★★★

Dans un club sportif de \(40\) adhérents, \(25\) pratiquent le football, \(18\) le basket et \(6\) ne pratiquent aucun de ces deux sports. Combien d’adhérents font à la fois du football et du basket ? Combien ne font que du football ?

10 Lois de De Morgan sur un exemple ★★★

Dans \(E = \{1, 2, \ldots, 10\}\), soit \(A\) l’ensemble des nombres pairs et \(B\) celui des multiples de \(3\). Vérifier que \(\overline{A \cup B} = \overline{A} \cap \overline{B}\) et que \(\overline{A \cap B} = \overline{A} \cup \overline{B}\).

11 Congruence modulo 5 ★★★

Sur \(\mathbb{Z}\), on pose \(x \sim y\) si \(5\) divise \(x - y\).

1. Montrer que \(\sim\) est une relation d’équivalence.
2. Écrire quelques éléments de la classe de \(3\). Combien de classes y a-t-il ?
3. Les entiers \(17\) et \(2\) sont-ils en relation ? et \(-4\) et \(1\) ?

12 Contraposée avec la parité ★★★

Démontrer, en passant par la contraposée, que pour tout entier \(n\) : si \(3n + 2\) est impair, alors \(n\) est impair.

13 Une contraposée sur une somme ★★★

Soit \(a\) et \(b\) deux entiers. Montrer que si \(a + b \geqslant 101\), alors \(a \geqslant 51\) ou \(b \geqslant 51\).

14 Une inégalité par récurrence ★★★

Montrer que, pour tout \(n \in \mathbb{N}\), \(3^n \geqslant 2n + 1\).

15 L’ordre des quantificateurs ★★★

On considère les deux propositions :

\(P_1 : \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x + 3\) et \(P_2 : \exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x + 3\).

Déterminer laquelle est vraie, justifier, et écrire la négation de l’autre.

16 Irrationalité de racine de 3 ★★★

Démontrer par l’absurde que \(\sqrt{3}\) est irrationnel. On pourra utiliser que, si \(3\) divise \(p^2\), alors \(3\) divise \(p\).

17 Divisibilité par 7 ★★★

Montrer par récurrence que, pour tout \(n \in \mathbb{N}\), \(7\) divise \(8^n - 1\).

18 Une équivalence sur les couples d’entiers ★★★

Sur \(\mathbb{N} \times \mathbb{N}\), on pose \((a, b) \sim (c, d)\) si \(a + d = b + c\).

1. Montrer que \(\sim\) est une relation d’équivalence.
2. Vérifier que \((3, 1) \sim (5, 3)\), puis décrire la classe de \((3, 1)\).
3. Quelle est la classe de \((0, 0)\) ?

19 Un ordre partiel sur les diviseurs de 30 ★★★

Soit \(D = \{1, 2, 3, 5, 6, 10, 15, 30\}\) l’ensemble des diviseurs de \(30\), ordonné par la divisibilité.

1. Montrer que la divisibilité est une relation d’ordre sur \(\mathbb{N}^*\).
2. Quels sont le plus petit et le plus grand élément de \(D\) ?
3. L’ordre est-il total ? Quels sont les éléments maximaux de \(D \setminus \{30\}\) ?
4. Représenter le diagramme de Hasse.

20 L’ordre lexicographique ★★★

Sur \(\mathbb{N} \times \mathbb{N}\), on définit \((a, b) \preceq (c, d)\) si \(a < c\), ou bien \(a = c\) et \(b \leqslant d\).

1. Ranger dans l’ordre \((2, 5), (1, 8), (2, 1), (1, 3)\).
2. Montrer que \(\preceq\) est une relation d’ordre total.

21 Suite à deux pas et récurrence forte ★★★

La suite \((u_n)\) est définie par \(u_0 = 1\), \(u_1 = 3\) et, pour tout \(n \in \mathbb{N}\), \(u_{n+2} = 3u_{n+1} - 2u_n\). Calculer \(u_2\) et \(u_3\), conjecturer une formule pour \(u_n\), puis la démontrer par récurrence forte.

22 Suite non bornée ★★★

Une suite \((u_n)\) est bornée si \(\exists M \in \mathbb{R},\ \forall n \in \mathbb{N},\ |u_n| \leqslant M\).

1. Écrire la négation de cette définition.
2. Montrer que la suite définie par \(u_n = (-1)^n n\) n’est pas bornée.
3. La suite \(v_n = (-1)^n\) est-elle bornée ?