Exercices supplémentaires

Ces exercices restent dans les objectifs de la séance (donc examinables) : à faire une fois le socle et le transfert bouclés, en séance ou à la maison.

Mise en garde✎ Exercice R.1 #Renforcement · O1 · ★★☆

On pose α\alpha : « le patient est malade » et β\beta : « le test est positif ». Traduire :

  1. « Le patient est malade mais son test est négatif. »
  2. « Si le test est positif alors le patient est malade. »
  3. ¬(α∨β)\lnot(\alpha \lor \beta) en français.
  4. « Le patient est malade ou son test est négatif. »

Retourne à la théorie du cours : Comment combiner des propositions ? Connecteurs logiques.

Question à te poser.

Quel connecteur porte la phrase (et / ou / si…alors / non) ? Attention au sens de l’implication : qui implique qui ?

  1. α∧¬β\alpha \land \lnot\beta.
  2. β⇒α\beta \Rightarrow \alpha (c’est le test qui implique la maladie).
  3. « Le patient n’est ni malade ni positif », soit ¬α∧¬β\lnot\alpha \land \lnot\beta.
  4. α∨¬β\alpha \lor \lnot\beta.

Traduire « mais » autrement que par ∧\land ; inverser le sens de l’implication en (b).

Mise en garde✎ Exercice R.2 #Renforcement · O2 · ★★☆

Soient A={a,b,c}A = \{a,b,c\} et B={c,d}B = \{c,d\}.

  1. Donner A∪BA\cup B, A∩BA\cap B, A\BA\setminus B, B\AB\setminus A.
  2. Donner A×BA\times B.
  3. Vrai ou faux : a∈Aa\in A ; {a}∈A\{a\}\in A ; {a}⊆A\{a\}\subseteq A ; ⌀⊆A\varnothing\subseteq A ; c∈A∩Bc\in A\cap B.
  4. Placer : −7-7, 14\tfrac14, 2\sqrt2 parmi les ensembles ℤ\ℕ\mathbb{Z}\setminus\mathbb{N}, ℚ\ℤ\mathbb{Q}\setminus\mathbb{Z}, ℝ\ℚ\mathbb{R}\setminus\mathbb{Q}.

Retourne à la théorie du cours : Ensembles : regrouper des objets, Ensembles de nombres et Opérations sur les ensembles.

Question à te poser.

Pour (c) : {a}\{a\} est-il un élément de AA, ou un sous-ensemble de AA ? Pour (d) : qui est entier non naturel ? qui est rationnel non entier ? qui est irrationnel ?

  1. A∪B={a,b,c,d}A\cup B=\{a,b,c,d\} ; A∩B={c}A\cap B=\{c\} ; A\B={a,b}A\setminus B=\{a,b\} ; B\A={d}B\setminus A=\{d\}.
  2. A×B={(a,c),(a,d),(b,c),(b,d),(c,c),(c,d)}A\times B=\{(a,c),(a,d),(b,c),(b,d),(c,c),(c,d)\}.
    • a∈Aa\in A est vraie. En effet, l’élément aa est dans l’ensemble A={a,b,c,d}A=\{a,b,c,d\}.
    • {a}∈A\{a\}\in A est fausse. En effet, {a}\{a\} désigne un ensemble dont l’unique élément est aa. Cet ensemble n’est pas un élément de l’ensemble A={a,b,c,d}A=\{a,b,c,d\}.
    • {a}⊆A\{a\}\subseteq A est vraie. En effet, {a}⊆A\{a\}\subseteq A signifie ∀x(x∈{a}⇒x∈A)\forall x\big(x\in\{a\}\Rightarrow x\in A\big). Cette phrase est vraie car le seul élément de l’ensemble {a}\{a\} est l’élément aa, qui est bien un élément de l’ensemble AA.
    • ⌀⊆A\varnothing\subseteq A est vraie. En effet, ⌀⊆A\varnothing\subseteq A signifie ∀x(x∈⌀⇒x∈A)\forall x\big(x\in\varnothing\Rightarrow x\in A\big). Cette phrase est vraie car il n’y a aucun élément dans ⌀\varnothing: la prémisse de l’implication étant fausse, l’implication est vraie.
    • c∈A∩Bc\in A\cap B est vraie. En effet, l’élément cc est un élément commun aux ensemble AA et BB: cc est donc dans l’intersection A∩BA\cap B.
  3. −7∈ℤ\ℕ-7\in\mathbb{Z}\setminus\mathbb{N} ; 14∈ℚ\ℤ\tfrac14\in\mathbb{Q}\setminus\mathbb{Z} ; 2∈ℝ\ℚ\sqrt2\in\mathbb{R}\setminus\mathbb{Q}.

Confondre ∈\in et ⊆\subseteq : écrire {a}∈A\{a\}\in A (faux) au lieu de {a}⊆A\{a\}\subseteq A (vrai).

Mise en garde✎ Exercice R.3 #Renforcement · O2 · ★★☆

Voici la table de vérité de deux propositions aa et bb et d’une proposition cachée « ? ». Parmi les propositions proposées, laquelle a correspond à cette colonne ?

aa bb ?
V V V
V F V
F V F
F F V

Choix : (A) a⇒ba \Rightarrow b ; (B) b⇒ab \Rightarrow a ; (C) a∧ba \land b ; (D) a∨ba \lor b.

Retourne à la théorie du cours : Comprendre l’implication.

Question à te poser.

Repère l’unique ligne où « ? » vaut F. Sur cette ligne, quelle proposition atomique est vraie (la prémisse) et laquelle est fausse (la conclusion) ?

« ? » vaut F seulement à la ligne a=F,b=Va=F,\ b=V. Une implication est fausse quand sa prémisse est vraie et sa conclusion fausse : ici la prémisse est bb (V), la conclusion aa (F). Donc « ? » =b⇒a=\,b\Rightarrow a — réponse (B).

Choisir a⇒ba\Rightarrow b (la réciproque) : la direction est inversée. Vérifie toujours sur quelle ligne l’implication doit être fausse.

Mise en garde✎ Exercice R.4 #Renforcement · O1 · ★★☆

On pose α\alpha : « l’animal est un mammifère » et β\beta : « l’animal allaite ses petits ». Traduire :

  1. « L’animal est un mammifère mais il n’allaite pas. »
  2. « Si l’animal est un mammifère alors il allaite. »
  3. ¬(α∧β)\lnot(\alpha\land\beta) en français.
  4. « L’animal n’est pas un mammifère ou il allaite. »

« mais » se traduit comme « et » (∧\land) ; attention au sens de ⇒\Rightarrow (qui implique qui ?). Pour (c), appliquer De Morgan : ¬(α∧β)⇔¬α∨¬β\lnot(\alpha\land \beta)\Leftrightarrow\lnot \alpha\lor\lnot \beta.

  1. α∧¬β\alpha\land\lnot\beta.
  2. α⇒β\alpha\Rightarrow\beta.
  3. « L’animal n’est pas un mammifère ou il n’allaite pas » =¬α∨¬β=\lnot\alpha\lor\lnot\beta.
  4. ¬α∨β\lnot\alpha\lor\beta — qui est justement une écriture de α⇒β\alpha\Rightarrow\beta.
Mise en garde✎ Exercice R.5 #Renforcement · O2 · ★☆☆

Construire la table de vérité de ¬α\lnot\alpha, ¬β\lnot\beta, α∨β\alpha\lor\beta, puis vérifier que ¬(α∨β)⇔¬α∧¬β.\lnot(\alpha\lor\beta)\ \Leftrightarrow\ \lnot\alpha\land\lnot\beta.

Dans ton tableau, il y a 5 lignes. La proposition α∨β\alpha\lor\beta n’est fausse que lorsque α\alpha et β\beta sont fausses, donc ¬(α∨β)\lnot(\alpha\lor\beta) n’est vraie que sur cette ligne.

α\alpha β\beta α∨β\alpha\lor\beta ¬(α∨β)\lnot(\alpha\lor\beta) ¬α∧¬β\lnot\alpha\land\lnot\beta
V V V F F
V F V F F
F V V F F
F F F V V

Les deux dernières colonnes coïncident : ¬(α∨β)⇔¬α∧¬β\lnot(\alpha\lor\beta)\Leftrightarrow\lnot\alpha\land\lnot\beta. Autrement dit : nier « α\alpha ou β\beta », c’est n’avoir « ni l’un ni l’autre ».

Mise en garde✎ Exercice R.6 #Renforcement · O2 · ★★☆

Soit α\alpha l’implication : « si nn est multiple de 66, alors nn est multiple de 33 ».

  1. Écrire la réciproque et la contraposée de α\alpha.
  2. Dire lesquelles des trois sont vraies, par un contre-exemple si nécessaire.

Réciproque = on échange ; contraposée = on nie chaque proposition puis on les échange. Pour tester la réciproque, cherche un multiple de 33 qui n’est pas multiple de 66.

Implication : vraie (tout multiple de 66 est multiple de 33).

Réciproque : « si nn multiple de 33 alors nn multiple de 66 » : fausse (n=3n=3).

Contraposée : « si nn n’est pas multiple de 33 alors nn n’est pas multiple de 66 » : vraie car équivalente à α\alpha.

Mise en garde✎ Exercice R.7 #Renforcement · O2 · ★★☆

Soient A={1,2,3}A=\{1,2,3\} et B={3,4}B=\{3,4\}.

  1. Donner A∪BA\cup B, A∩BA\cap B, A\BA\setminus B, B\AB\setminus A.
  2. Vrai ou faux : 2∈A2\in A ; {2}∈A\{2\}\in A ; {2,3}⊆A\{2,3\}\subseteq A ; ⌀∈A\varnothing\in A ; 3∈A∩B3\in A\cap B.

Distingue élément (∈\in) et sous-ensemble (⊆\subseteq). Piège : ⌀⊆A\varnothing\subseteq A est toujours vrai — mais ⌀∈A\varnothing\in A demande que ⌀\varnothing soit listé parmi les éléments de AA.

  1. A∪B={1,2,3,4}A\cup B=\{1,2,3,4\} ; A∩B={3}A\cap B=\{3\} ; A\B={1,2}A\setminus B=\{1,2\} ; B\A={4}B\setminus A=\{4\}.
    • 2∈A2\in A est vraie ;
    • {2}∈A\{2\}\in A est fausse ({2}\{2\} est un sous-ensemble, pas un élément) ;
    • {2,3}⊆A\{2,3\}\subseteq A est vraie ;
    • ⌀∈A\varnothing\in A est fausse (AA ne contient pas ⌀\varnothing comme élément) ; -3∈A∩B3\in A\cap B est vraie.
Mise en garde✎ Exercice R.8 #Renforcement · O2 · ★★☆

Pour chaque proposition : dire si elle est vraie ou fausse, écrire sa négation, puis l’évaluer.

  1. ∀n∈ℕ,n+1>n\forall\, n\in\mathbb{N},\ n+1 > n.
  2. ∃x∈ℝ,x2=2\exists\, x\in\mathbb{R},\ x^2 = 2.
  3. ∀x∈ℝ,x2≠x\forall\, x\in\mathbb{R},\ x^2 \ne x.

Nier : échanger ∀\forall\, et ∃\exists\,, puis nier l’intérieur. Négation de « >> » : « ≤\le » ; de « == » : « ≠\ne » ; de « ≠\ne » : « == ». Un seul contre-exemple réfute un ∀\forall\,.

  1. Vraie. Négation : ∃n∈ℕ,n+1≤n\exists\, n\in\mathbb{N},\ n+1\le n — fausse.
  2. Vraie (x=2x=\sqrt2). Négation : ∀x∈ℝ,x2≠2\forall\, x\in\mathbb{R},\ x^2\ne 2 — fausse.
  3. Fausse (x=0x=0 donne 02=00^2=0, et x=1x=1 aussi). Négation : ∃x∈ℝ,x2=x\exists\, x\in\mathbb{R},\ x^2=x — vraie (x=0x=0 ou x=1x=1).
Mise en garde✎ Exercice R.9 #Renforcement · O2 · ★★☆

Voici la table de vérité de aa, bb et d’une proposition cachée « ? ». Parmi les choix, laquelle a exactement cette colonne ?

aa bb ?
V V V
V F F
F V V
F F V

Choix : (A) a⇒ba\Rightarrow b ; (B) b⇒ab\Rightarrow a ; (C) a∨ba\lor b ; (D) a∧ba\land b.

Repère l’unique ligne où « ? » vaut F. Sur cette ligne, quelle proposition est vraie (la prémisse) et laquelle est fausse (la conclusion) ?

« ? » vaut F seulement à la ligne a=V,b=Fa=V,\ b=F : prémisse aa (V), conclusion bb (F). C’est donc a⇒ba\Rightarrow b — réponse (A). (Cette fois la direction est a⇒ba\Rightarrow b, l’inverse de l’exercice S.7 du socle : c’est toujours la ligne fausse qui tranche.)

Mise en garde✎ Exercice R.10 #Renforcement · O2 · ★★☆

On veut relier l’implication aux connecteurs ¬\lnot, ∨\lor, ∧\land.

  1. Dresser la table de vérité de α⇒β\alpha\Rightarrow\beta et celle de ¬α∨β\lnot\alpha\lor\beta, et constater qu’elles coïncident.
  2. En déduire une écriture de ¬(α⇒β)\lnot(\alpha\Rightarrow\beta) sans le symbole ⇒\Rightarrow.

La table aura 5 lignes et une colonne par proposition. Pour (b), nie ¬α∨β\lnot\alpha\lor\beta et applique De Morgan : ¬(α∨β)⇔¬α∧¬β\lnot(\alpha\lor \beta)\Leftrightarrow\lnot \alpha\land\lnot \beta.

  1. Les deux colonnes valent F uniquement sur la ligne α=V,β=F\alpha=V,\ \beta=F, et V sur les trois autres : elles sont identiques, donc α⇒β⇔¬α∨β\alpha\Rightarrow\beta\Leftrightarrow\lnot\alpha\lor\beta.

  2. ¬(α⇒β)⇔¬(¬α∨β)⇔α∧¬β\lnot(\alpha\Rightarrow\beta)\Leftrightarrow\lnot(\lnot\alpha\lor\beta)\Leftrightarrow\alpha\land\lnot\beta : « nier une implication », c’est affirmer l’hypothèse et nier la conclusion.

Mise en garde✎ Exercice R.11 #Renforcement · O2 · ★★☆

Pour chaque proposition, dire si c’est une tautologie (vraie quelles que soient les valeurs), une contradiction (jamais vraie), ou une contingence (ni l’une ni l’autre).

  1. α∨¬α\alpha\lor\lnot\alpha
  2. α∧¬α\alpha\land\lnot\alpha
  3. (α⇒β)⇒(¬β⇒¬α)(\alpha\Rightarrow\beta)\Rightarrow(\lnot\beta\Rightarrow\lnot\alpha)
  4. (α∨β)⇒α(\alpha\lor\beta)\Rightarrow\alpha

Une table de vérité tranche à coup sûr : tautologie = colonne finale tout V, contradiction = tout F. Pour (b), regarde ce que ¬β⇒¬α\lnot\beta\Rightarrow\lnot\alpha représente par rapport à α⇒β\alpha\Rightarrow\beta.

  1. Tautologie.
  2. Contradiction.
  3. Tautologie : ¬β⇒¬α\lnot\beta\Rightarrow\lnot\alpha est la contraposée de α⇒β\alpha\Rightarrow\beta, donc les deux membres sont équivalents et l’implication est toujours vraie.
  4. Contingence : fausse pour α=F,β=V\alpha=F,\ \beta=V (l’hypothèse est vraie, la conclusion fausse), vraie ailleurs.
Mise en garde✎ Exercice R.12 #Renforcement · O2 · ★★★

On travaille dans ℝ\mathbb{R}. (⋆)∀x,∃y,x+y=0.(\star)\qquad \forall\, x,\ \exists\, y,\ x+y=0.

  1. (⋆)(\star) est-elle vraie ? Justifier.
  2. Écrire ∃y,∀x,x+y=0\exists\, y,\ \forall\, x,\ x+y=0 et dire si elle est vraie.
  3. Écrire la négation de (⋆)(\star).

Traduis (⋆)(\star) en français pour juger de sa vérité.

Dans (b), un même yy doit convenir pour tous les xx.

Pour la négation, n’oublie pas de nier l’égalité.

  1. Vraie : pour xx donné, prends y=−xy=-x ; alors x+y=0x+y=0. Cette proposition dit que tout nombre réel a un opposé.

  2. « Il existe un réel yy tel que, pour tout xx, x+y=0x+y=0. » Fausse : un yy fixé ne peut annuler x+yx+y que pour le seul x=−yx=-y, pas pour tous.

  3. ¬(⋆)⇔∃x,∀y,x+y≠0\lnot(\star)\Leftrightarrow\exists\, x,\ \forall\, y,\ x+y\neq 0 (« il existe un xx que aucun yy n’annule »).

Mise en garde✎ Exercice R.13 #Renforcement · O2 · ★★★

Soient AA, BB, CC des ensembles.

  1. Démontrer A∩(B∪C)=(A∩B)∪(A∩C)A\cap(B\cup C)=(A\cap B)\cup(A\cap C).
  2. L’égalité A\(B∩C)=(A\B)∩(A\C)A\setminus(B\cap C)=(A\setminus B)\cap(A\setminus C) est-elle vraie ? Sinon, donner un contre-exemple et écrire l’identité correcte.
  1. Montre x∈x\in membre de gauche ⇔x∈\Leftrightarrow x\in membre de droite, en traduisant ∩\cap par « et », ∪\cup par « ou ».

  2. Teste sur de petits ensembles.

  1. x∈A∩(B∪C)⇔x∈Aet(x∈Boux∈C)⇔(x∈Aetx∈B)ou(x∈Aetx∈C)⇔x∈(A∩B)∪(A∩C)x\in A\cap(B\cup C)\ \Leftrightarrow\ x\in A\ \text{et}\ (x\in B\ \text{ou}\ x\in C)\ \Leftrightarrow\ (x\in A\ \text{et}\ x\in B)\ \text{ou}\ (x\in A\ \text{et}\ x\in C)\ \Leftrightarrow\ x\in(A\cap B)\cup(A\cap C) (distributivité du « et » sur le « ou »).

  2. Fausse. Contre-exemple : A={1,2}A=\{1,2\}, B={1}B=\{1\}, C={2}C=\{2\}. Alors B∩C=⌀B\cap C=\varnothing, donc A\(B∩C)=A={1,2}A\setminus(B\cap C)=A=\{1,2\} ; tandis que A\B={2}A\setminus B=\{2\}, A\C={1}A\setminus C=\{1\}, dont l’intersection est ⌀\varnothing. L’identité correcte est A\(B∩C)=(A\B)∪(A\C)A\setminus(B\cap C)=(A\setminus B)\cup (A\setminus C).

Mise en garde✎ Exercice R.14 #Renforcement · O2 · ★★☆

À l’aide de tables de vérités, dire si les équivalences sont vraies (les deux membres de l’équivalence ont la même colonne dans la table de vérité) ou fausse (une des lignes de la table de vérité distingue les deux membres).

  1. (α⇒β)⇔(¬β⇒¬α)(\alpha\Rightarrow\beta)\ \Leftrightarrow\ (\lnot\beta\Rightarrow\lnot\alpha)
  2. (α⇒β)⇔(β⇒α)(\alpha\Rightarrow\beta)\ \Leftrightarrow\ (\beta\Rightarrow\alpha)

Retourne à la théorie du cours : Réciproque, contraposée, équivalence et Outil : table de vérité.

Question à te poser.

Les deux membres de l’équivalence ont-elles la même colonne finale?

(a) Vraie : c’est le lien implication / contraposée.

α\alpha β\beta ¬α\lnot\alpha ¬β\lnot\beta α⇒β\alpha\Rightarrow\beta ¬β⇒¬α\lnot\beta\Rightarrow\lnot\alpha
V V F F V V
V F F V F F
F V V F V V
F F V V V V

Les deux dernières colonnes sont identiques ligne à ligne : l’équivalence est vraie.

(b) Fausse : à la ligne α=V,β=F\alpha=V,\ \beta=F, α⇒β\alpha\Rightarrow\beta vaut F tandis que β⇒α\beta\Rightarrow\alpha vaut V — c’est la réciproque, pas équivalente.

α\alpha β\beta α⇒β\alpha\Rightarrow\beta β⇒α\beta\Rightarrow\alpha
V V V V
V F F V
F V V F
F F V V

Aux lignes 2 et 3, les colonnes diffèrent : l’équivalence est fausse.

Prendre une coïncidence sur une ligne pour une équivalence (il faut toutes les lignes) ; oublier qu’une seule ligne de différence réfute.

Mise en garde✎ Exercice R.15 #Renforcement · O1 · ★★☆

On se place dans un ensemble de référence EE. Pour chaque relation entre ensembles, écrire l’énoncé logique équivalent (avec ∀\forall\,, ⇒\Rightarrow, ∈\in) puis représenter la situation sur un diagramme de Venn.

  1. A⊆BA \subseteq B
  2. A∩B=⌀A \cap B = \varnothing

Retourne à la théorie du cours : Formaliser l’inclusion et Opérations sur les ensembles.

Question à te poser.

« Être dans AA » se note x∈Ax\in A. Une relation entre ensembles se lit comme un énoncé « pour tout élément xx… ». Que dit-elle de la position des disques dans le diagramme de Venn ?

(a) ∀x,x∈A⇒x∈B\forall\, x,\ x\in A \Rightarrow x\in B — le disque AA est entièrement contenu dans BB.

E B A

(b) ∀x,¬(x∈A∧x∈B)\forall\, x,\ \lnot(x\in A \land x\in B) — les disques AA et BB ne se recouvrent pas (disjoints).

E A B

Écrire une égalité d’ensembles là où il faut une implication (inclusion) ; confondre ∩=⌀\cap=\varnothing (disjoints) et ⊆\subseteq (inclus).

Mise en garde✎ Exercice R.16 #Renforcement · O1 · ★★☆

Pour chaque ligne, écrire le membre de droite en fonction de « x∈Ax\in A » et « x∈Bx\in B » et les connecteurs logiques ∧\land, ∨\lor et ¬\lnot.

  1. x∈A∩B⇔…x \in A\cap B\ \Leftrightarrow\ \ldots
  2. x∈A∪B⇔…x \in A\cup B\ \Leftrightarrow\ \ldots
  3. x∈A\B⇔…x \in A\setminus B\ \Leftrightarrow\ \ldots

Retourne à la théorie du cours : Opérations sur les ensembles et Comment combiner des propositions ? Connecteurs logiques.

Question à te poser.

Comment traduire en français A∩BA \cap B avec un connecteur logique? Comment traduire l’union avec un connecteur logique? etc.

  1. (x∈A)∧(x∈B)(x\in A)\ \land\ (x\in B).
  2. (x∈A)∨(x∈B)(x\in A)\ \lor\ (x\in B).
  3. (x∈A)∧¬(x∈B)(x\in A)\ \land\ \lnot(x\in B).

Traduire ∪\cup par « et » ; oublier le non du complément ou du « \\setminus ».

Mise en garde✎ Exercice R.17 #Renforcement · O3 · ★★★

Dans chaque paire, les deux énoncés utilisent les mêmes symboles, mais dans un ordre différent (ou avec des parenthèses placées ailleurs).

  1. Traduis chaque énoncé en français courant.
  2. Dis s’il est vrai ou faux.
  1. ∀n∈ℕ,∃m∈ℕ,n<m\forall\, n\in\mathbb{N},\ \exists\, m\in\mathbb{N},\ n< m et ∃m∈ℕ,∀n∈ℕ,n<m\exists\, m\in\mathbb{N},\ \forall\, n\in\mathbb{N},\ n< m

  2. ∀n∈ℕ,∃m∈ℕ,n+m=10\forall\, n\in\mathbb{N},\ \exists\, m\in\mathbb{N},\ n+m=10 et ∃m∈ℕ,∀n∈ℕ,n+m=10\exists\, m\in\mathbb{N},\ \forall\, n\in\mathbb{N},\ n+m=10

  3. ∀n∈ℕ,(n est pair∨n est impair)\forall\, n\in\mathbb{N},\ (n \text{ est pair}\ \lor\ n \text{ est impair}) et (∀n∈ℕ,n est pair)∨(∀n∈ℕ,n est impair)\big(\forall\, n\in\mathbb{N},\ n \text{ est pair}\big)\ \lor\ \big(\forall\, n\in\mathbb{N},\ n \text{ est impair}\big)

  4. ∃n∈ℕ,(n est pair∧n est impair)\exists\, n\in\mathbb{N},\ (n \text{ est pair}\ \land\ n \text{ est impair}) et (∃n∈ℕ,n est pair)∧(∃n∈ℕ,n est impair)\big(\exists\, n\in\mathbb{N},\ n \text{ est pair}\big)\ \land\ \big(\exists\, n\in\mathbb{N},\ n \text{ est impair}\big)

Retourne à la théorie du cours : Quantificateurs imbriqués et Portée des quantificateurs.

Question à te poser

Dans quel ordre est-ce que je choisis mes nombres — et le second a-t-il le droit de dépendre du premier ?

  • Si je lis ∀n∈ℕ,∃m∈ℕ,…\forall\, n\in\mathbb{N},\ \exists\, m\in\mathbb{N},\ \ldots : on me donne nn d’abord, puis je cherche un mm adapté. Ai-je le droit de changer de mm quand nn change ?
  • Si je lis ∃m∈ℕ,∀n∈ℕ,…\exists\, m\in\mathbb{N},\ \forall\, n\in\mathbb{N},\ \ldots : je dois annoncer mon mm avant de voir les nn. Un seul et même mm peut-il convenir à tous les nn à la fois ?

(a)

  • ∀n∈ℕ,∃m∈ℕ,n<m\forall\, n\in\mathbb{N},\ \exists\, m\in\mathbb{N},\ n<m : « Quel que soit le naturel choisi, il en existe un plus grand. »  Vrai (prendre m=n+1m=n+1, qui dépend de nn).
  • ∃m∈ℕ,∀n∈ℕ,n<m\exists\, m\in\mathbb{N},\ \forall\, n\in\mathbb{N},\ n<m : « Il existe un naturel plus grand que tous les naturels. »  Faux : ce mm devrait notamment être plus grand que lui-même, et de toute façon m+1m+1 le dépasse. Il n’y a pas de plus grand naturel.

(b)

  • ∀n∈ℕ,∃m∈ℕ,n+m=10\forall\, n\in\mathbb{N},\ \exists\, m\in\mathbb{N},\ n+m=10 : « Tout naturel peut être complété à 1010. »  Faux dans ℕ\mathbb{N} : pour n=12n=12, il faudrait m=−2m=-2, qui n’est pas un naturel.
  • ∃m∈ℕ,∀n∈ℕ,n+m=10\exists\, m\in\mathbb{N},\ \forall\, n\in\mathbb{N},\ n+m=10 : « Il existe un naturel qui, ajouté à n’importe quel naturel, donne toujours 1010. »  Faux (il faudrait m=10m=10 pour n=0n=0 et m=9m=9 pour n=1n=1).

(c)

  • ∀n∈ℕ,(n est pair∨n est impair)\forall\, n\in\mathbb{N},\ (n \text{ est pair}\ \lor\ n \text{ est impair}) : « Tout naturel est pair ou impair. »  Vrai.
  • (∀n∈ℕ,n est pair)∨(∀n∈ℕ,n est impair)\big(\forall\, n\in\mathbb{N},\ n \text{ est pair}\big)\ \lor\ \big(\forall\, n\in\mathbb{N},\ n \text{ est impair}\big) : « Ou bien tous les naturels sont pairs, ou bien tous sont impairs. »  Faux (33 contredit la première, 44 la seconde).

(d)

  • ∃n∈ℕ,(n est pair∧n est impair)\exists\, n\in\mathbb{N},\ (n \text{ est pair}\ \land\ n \text{ est impair}) : « Il existe un naturel à la fois pair et impair. »  Faux (impossible pour un même nombre).
  • (∃n∈ℕ,n est pair)∧(∃n∈ℕ,n est impair)\big(\exists\, n\in\mathbb{N},\ n \text{ est pair}\big)\ \land\ \big(\exists\, n\in\mathbb{N},\ n \text{ est impair}\big) : « Il existe un naturel pair, et il existe un naturel impair. »  Vrai (par exemple 44 et 77 : ce ne sont pas les mêmes).

Permuter des quantificateurs change une proposition : ∀n∈ℕ,∃m∈ℕ\forall n\in\mathbb{N},\exists m\in\mathbb{N} autorise un mm différent pour chaque nn, alors que ∃m∈ℕ,∀n∈ℕ\exists m\in\mathbb{N},\forall n\in\mathbb{N} exige un seul mm valable partout. En (a), c’est toute la différence entre « il y a toujours un naturel plus grand qu’un autre » (vrai) et « il y a un naturel plus grand grand que tous les autres» (faux).

Et surveille les parenthèses : dans (c) et (d), le même symbole placé à l’intérieur ou à l’extérieur change complètement l’énoncé.