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

1 Nier une phrase quantifiée ★★★

1. Négation : \(\exists x \in \mathbb{R},\ x^2 + 1 \leqslant 0\). Comme \(x^2 \geqslant 0\), on a \(x^2 + 1 \geqslant 1 > 0\) pour tout réel : la négation est fausse et la proposition est vraie.
2. Négation : \(\forall n \in \mathbb{N},\ 2n + 1 \neq 100\). Or \(2n + 1\) est impair et \(100\) est pair, donc l’égalité est impossible : la négation est vraie, la proposition est fausse.
3. Négation : \(\exists x \in [0, 1],\ x^2 > x\). Pour \(x \in [0, 1]\), \(x^2 - x = x(x - 1) \leqslant 0\) car \(x \geqslant 0\) et \(x - 1 \leqslant 0\) : la négation est fausse, la proposition est vraie.

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

Les trois colonnes sont identiques : les trois propositions sont équivalentes. En particulier \(P \Rightarrow Q\) équivaut à \(\neg P \lor Q\) et à sa contraposée.

3 Vrai ou faux avec quantificateurs ★★★

1. Faux. Contre-exemple : \(x = \tfrac12\), \(x^2 = \tfrac14 < \tfrac12\).
2. Vrai. \(x = 0\) convient (\(0^2 = 0\)), de même \(x = 1\).
3. Vrai. \(n^2 + n = n(n+1)\) est le produit de deux entiers consécutifs, dont l’un est pair : le produit est pair.

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

\(A = \{1, 2, 3, 4, 6, 8, 12, 24\}\) (8 éléments) et \(B = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}\) (9 éléments).

\(A \cap B = \{1, 2, 3, 4, 6, 12\}\) (diviseurs de \(12\), le PGCD). \(A \cup B = \{1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36\}\), soit \(8 + 9 - 6 = 11\) éléments.

\(A \setminus B = \{8, 24\}\) et \(B \setminus A = \{9, 18, 36\}\).

5 Couples et produit cartésien ★★★

1. \(E \times F = \{(1,x), (1,y), (2,x), (2,y), (3,x), (3,y)\}\) et \(F \times E = \{(x,1), (x,2), (x,3), (y,1), (y,2), (y,3)\}\).
2. \(|E \times F| = 3 \times 2 = 6\) et \(|E \times E| = 3 \times 3 = 9\).
3. Non : \((1, x) \in E \times F\) mais \((1, x) \notin F \times E\), car sa première composante \(1\) n’est pas dans \(F\). Les couples sont ordonnés.

6 Contraposée et réciproque ★★★

1. Contraposée : « si les quatre côtés ne sont pas égaux, alors ce n’est pas un carré » (vraie, comme l’implication). Réciproque : « si les quatre côtés sont égaux, alors c’est un carré » : fausse, un losange non rectangle est un contre-exemple.
2. Contraposée : « si \(n\) n’est pas un multiple de \(5\), alors \(n\) n’est pas un multiple de \(10\) ». Réciproque : « si \(n\) est un multiple de \(5\), alors c’en est un de \(10\) » : fausse, \(n = 15\).

7 Somme des premiers nombres impairs ★★★

Initialisation. Pour \(n = 1\) : \(1 = 1^2\).

Hérédité. Supposons \(1 + 3 + \cdots + (2n - 1) = n^2\). Alors \(1 + 3 + \cdots + (2n - 1) + (2n + 1) = n^2 + 2n + 1 = (n + 1)^2\) : la propriété est vraie au rang \(n + 1\).

Conclusion. La formule est vraie pour tout \(n \geqslant 1\). Exemple : \(1 + 3 + 5 + 7 = 16 = 4^2\).

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

1. Aucun élément : \(\varnothing\). Un élément : \(\{a\}, \{b\}, \{c\}\). Deux éléments : \(\{a,b\}, \{a,c\}, \{b,c\}\). Trois éléments : \(E\). Soit \(1 + 3 + 3 + 1 = 8 = 2^3\) parties.
2. \(2^5 = 32\) parties.
3. \(a \in \mathcal{P}(E)\) est fausse : \(a\) est un élément de \(E\), pas une partie. \(\{a\} \in \mathcal{P}(E)\) est vraie car \(\{a\} \subset E\).

9 Inclusion-exclusion dans un club ★★★

Notons \(F\) et \(B\) les ensembles des footballeurs et des basketteurs. Les adhérents qui pratiquent au moins un des deux sports sont \(40 - 6 = 34 = |F \cup B|\).

Comme \(|F \cup B| = |F| + |B| - |F \cap B|\), on obtient \(|F \cap B| = 25 + 18 - 34 = 9\).

Seulement football : \(25 - 9 = 16\) ; seulement basket : \(18 - 9 = 9\). Vérification : \(16 + 9 + 9 + 6 = 40\).

Réponse : 9 adhérents pratiquent les deux sports et 16 seulement le football.

10 Lois de De Morgan sur un exemple ★★★

\(A = \{2, 4, 6, 8, 10\}\), \(B = \{3, 6, 9\}\), \(A \cup B = \{2, 3, 4, 6, 8, 9, 10\}\), \(A \cap B = \{6\}\).

\(\overline{A \cup B} = \{1, 5, 7\}\). D’autre part \(\overline{A} = \{1, 3, 5, 7, 9\}\) et \(\overline{B} = \{1, 2, 4, 5, 7, 8, 10\}\), d’où \(\overline{A} \cap \overline{B} = \{1, 5, 7\}\) : première égalité vérifiée.

\(\overline{A \cap B} = E \setminus \{6\} = \{1, 2, 3, 4, 5, 7, 8, 9, 10\}\) (9 éléments) et \(\overline{A} \cup \overline{B} = \{1, 2, 3, 4, 5, 7, 8, 9, 10\}\) : seconde égalité vérifiée.

11 Congruence modulo 5 ★★★

1. Réflexive : \(x - x = 0 = 5 \times 0\). Symétrique : si \(x - y = 5k\), alors \(y - x = 5(-k)\). Transitive : si \(x - y = 5k\) et \(y - z = 5l\), alors \(x - z = 5(k + l)\).
2. La classe de \(3\) est \(\{\ldots, -7, -2, 3, 8, 13, \ldots\}\) : les entiers de reste \(3\) dans la division par \(5\). Il y a \(5\) classes, de restes \(0, 1, 2, 3, 4\).
3. \(17 - 2 = 15 = 5 \times 3\) : oui. \(-4 - 1 = -5 = 5 \times (-1)\) : oui.

12 Contraposée avec la parité ★★★

La contraposée est : « si \(n\) est pair, alors \(3n + 2\) est pair ».

Supposons \(n = 2k\) avec \(k \in \mathbb{Z}\). Alors \(3n + 2 = 6k + 2 = 2(3k + 1)\), qui est pair.

La contraposée est vraie, donc l’implication « \(3n + 2\) impair \(\Rightarrow\) \(n\) impair » l’est aussi.

13 Une contraposée sur une somme ★★★

Contraposée : si \(a < 51\) et \(b < 51\) (donc \(a \leqslant 50\) et \(b \leqslant 50\) puisque ce sont des entiers), alors \(a + b < 101\).

En effet, \(a + b \leqslant 50 + 50 = 100 < 101\). La contraposée est démontrée, donc l’implication de départ est vraie.

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

Initialisation. Pour \(n = 0\) : \(3^0 = 1 \geqslant 1\).

Hérédité. Supposons \(3^n \geqslant 2n + 1\). Alors \(3^{n+1} = 3 \times 3^n \geqslant 3(2n + 1) = 6n + 3\). Or \(6n + 3 \geqslant 2n + 3 = 2(n+1) + 1\) car \(4n \geqslant 0\). Donc \(3^{n+1} \geqslant 2(n+1) + 1\).

Conclusion. L’inégalité est vraie pour tout \(n \in \mathbb{N}\).

15 L’ordre des quantificateurs ★★★

\(P_1\) est vraie : pour un réel \(x\) donné, \(y = x + 4\) convient, car \(x + 4 > x + 3\). Ici \(y\) dépend de \(x\).

\(P_2\) est fausse : un seul \(y\) devrait dépasser \(x + 3\) pour tous les \(x\), y compris \(x = y\), ce qui donnerait \(y > y + 3\), absurde.

Négation de \(P_2\) : \(\forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ y \leqslant x + 3\) (prendre \(x = y\)). Cette négation est vraie.

16 Irrationalité de racine de 3 ★★★

Supposons \(\sqrt{3} = \dfrac{p}{q}\) avec \(p, q\) entiers strictement positifs premiers entre eux. Alors \(p^2 = 3q^2\), donc \(3 \mid p^2\), donc \(3 \mid p\) (si \(p = 3k \pm 1\), alors \(p^2 = 3(3k^2 \pm 2k) + 1\) n’est pas divisible par \(3\)).

Écrivons \(p = 3k\). Alors \(9k^2 = 3q^2\), soit \(q^2 = 3k^2\), donc \(3 \mid q^2\) puis \(3 \mid q\).

Ainsi \(3\) divise à la fois \(p\) et \(q\), ce qui contredit le fait qu’ils soient premiers entre eux. L’hypothèse est absurde : \(\sqrt{3}\) est irrationnel.

17 Divisibilité par 7 ★★★

Initialisation. \(8^0 - 1 = 0\), qui est divisible par \(7\).

Hérédité. Supposons \(8^n - 1 = 7k\) avec \(k \in \mathbb{Z}\). Alors \(8^{n+1} - 1 = 8 \times 8^n - 1 = 8(8^n - 1) + 8 - 1 = 8 \times 7k + 7 = 7(8k + 1)\), multiple de \(7\).

Conclusion. Pour tout \(n\), \(7 \mid 8^n - 1\). Vérification : \(8^2 - 1 = 63 = 7 \times 9\).

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

1. Réflexivité : \(a + b = b + a\). Symétrie : si \(a + d = b + c\), alors \(c + b = d + a\), c’est-à-dire \((c, d) \sim (a, b)\). Transitivité : si \(a + d = b + c\) et \(c + f = d + e\), l’addition donne \(a + d + c + f = b + c + d + e\) ; en simplifiant par \(c + d\), on obtient \(a + f = b + e\), c’est-à-dire \((a, b) \sim (e, f)\).
2. \(3 + 3 = 6 = 1 + 5\) : oui. La classe de \((3, 1)\) est l’ensemble des couples \((a, b)\) tels que \(a + 1 = b + 3\), soit \(a - b = 2\) : \(\{(2, 0), (3, 1), (4, 2), (5, 3), \ldots\}\).
3. \((a, b) \sim (0, 0)\) équivaut à \(a + 0 = b + 0\), soit \(a = b\) : la classe est \(\{(n, n) : n \in \mathbb{N}\}\). Chaque classe correspond à la différence \(a - b\), c’est la construction des entiers relatifs.

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

1. Réflexive : \(a = a \times 1\). Antisymétrique : si \(b = ak\) et \(a = bl\) avec \(k, l \geqslant 1\), alors \(a \leqslant b \leqslant a\), donc \(a = b\). Transitive : si \(b = ak\) et \(c = bl\), alors \(c = a(kl)\).
2. Plus petit élément : \(1\) (il divise tout). Plus grand : \(30\).
3. Non total : \(6\) et \(10\) ne sont pas comparables (\(6 \nmid 10\), \(10 \nmid 6\)). Dans \(D \setminus \{30\}\), les éléments maximaux sont \(6\), \(10\) et \(15\) : aucun autre élément de cet ensemble n’en est un multiple distinct.
4. Diagramme de Hasse (4 niveaux : \(1\) ; \(2, 3, 5\) ; \(6, 10, 15\) ; \(30\)) :

20 L’ordre lexicographique ★★★

1. On compare d’abord la première composante : \((1, 3) \preceq (1, 8) \preceq (2, 1) \preceq (2, 5)\).
2. Réflexivité : \(a = a\) et \(b \leqslant b\). Antisymétrie : si \((a,b) \preceq (c,d)\) et \((c,d) \preceq (a,b)\), alors \(a \leqslant c\) et \(c \leqslant a\), donc \(a = c\) ; puis \(b \leqslant d\) et \(d \leqslant b\), donc \(b = d\). Transitivité : si \((a,b) \preceq (c,d) \preceq (e,f)\), ou bien \(a < c\) ou \(c < e\) (l’autre comparaison étant au sens large) et alors \(a < e\), ou bien \(a = c = e\) et \(b \leqslant d \leqslant f\), donc \(b \leqslant f\). Totalité : deux couples \((a,b)\) et \((c,d)\) vérifient \(a < c\), \(a > c\) ou \(a = c\) ; dans le dernier cas, \(b \leqslant d\) ou \(d \leqslant b\). Ils sont donc toujours comparables.

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

\(u_2 = 3 \times 3 - 2 \times 1 = 7\) et \(u_3 = 3 \times 7 - 2 \times 3 = 15\). Les valeurs \(1, 3, 7, 15\) suggèrent \(u_n = 2^{n+1} - 1\).

Initialisation. \(u_0 = 1 = 2^1 - 1\) et \(u_1 = 3 = 2^2 - 1\).

Hérédité. Supposons la formule vraie aux rangs \(n\) et \(n + 1\). Alors \(u_{n+2} = 3(2^{n+2} - 1) - 2(2^{n+1} - 1) = 3 \times 2^{n+2} - 3 - 2^{n+2} + 2 = 2 \times 2^{n+2} - 1 = 2^{n+3} - 1\).

Conclusion. Pour tout \(n\), \(u_n = 2^{n+1} - 1\).

22 Suite non bornée ★★★

1. Négation : \(\forall M \in \mathbb{R},\ \exists n \in \mathbb{N},\ |u_n| > M\).
2. Ici \(|u_n| = n\). Soit \(M \in \mathbb{R}\) quelconque ; l’entier \(n = \lfloor |M| \rfloor + 1\) vérifie \(n > |M| \geqslant M\), donc \(|u_n| > M\). La négation est vérifiée : la suite n’est pas bornée.
3. Oui : \(|v_n| = 1 \leqslant 1\) pour tout \(n\), donc \(M = 1\) convient.