Flashcard: Raisonnement et vocabulaire ensembliste — 61 carte

Que montre une table de vérité pour une proposition composée ?

Si la proposition est vraie ou fausse selon les valeurs de vérité des propositions élémentaires.

Comment est définie l'implication A ⇒ B ?

Par la proposition non A ou B.

Dans A ⇒ B, que représente A ?

Une condition suffisante pour B.

Dans A ⇒ B, que représente B ?

Une condition nécessaire pour A.

Comment s'exprime l'équivalence A ⇔ B ?

Par (A ⇒ B) et (B ⇒ A).

Quand l'équivalence A ⇔ B est-elle vraie ?

Lorsqu'A et B sont simultanément vraies ou fausses.

Quelle formule exprime la contraposition ?

A ⇒ B est équivalent à non B ⇒ non A.

Que signifie le quantificateur existentiel ∃x ∈ E, A(x) ?

Au moins un élément de E vérifie A(x).

Que signifie le quantificateur universel ∀x ∈ E, A(x) ?

Tous les éléments de E vérifient A(x).

Pourquoi ∃x ∀y A(x,y) et ∀y ∃x A(x,y) ne signifient pas la même chose ?

Parce que x peut dépendre de y dans la seconde proposition.

Quelle est la négation d’un énoncé universel ∀x A(x) ?

C’est ∃x ¬A(x).

Quelle est la négation d’un énoncé existentiel ∃x A(x) ?

C’est ∀x ¬A(x).

Comment démontre-t-on une proposition A directement ?

On établit une condition suffisante B puis on démontre B ⇒ A.

Quelle hypothèse fait-on pour démontrer une proposition par l’absurde ?

On suppose que la proposition A est fausse.

Que déduit-on de l'hypothèse qu'A est fausse en démonstration par l’absurde ?

On en déduit une contradiction.

Quelle implication est équivalente à P ⇒ Q ?

Sa contraposée ¬Q ⇒ ¬P est équivalente.

Que faut-il démontrer pour prouver une équivalence P ⇔ Q ?

Il faut démontrer séparément P ⇒ Q et Q ⇒ P.

Qu'affirme le principe de récurrence sur une partie A de N ?

A égale N si elle contient 0 et est stable par passage de n à n+1.

Quelles étapes sont nécessaires pour démontrer P(n) par récurrence simple ?

Établir P(n₀) puis P(n) implique P(n+1) pour tout n ≥ n₀.

Que suppose l'analyse dans une analyse-synthèse ?

Elle suppose le problème résolu et cherche des conditions nécessaires.

Que vérifie la synthèse dans une analyse-synthèse ?

Elle vérifie si les conditions nécessaires sont aussi suffisantes.

Qu'est-ce que la réunion A ∪ B d'ensembles A et B ?

L'ensemble des éléments appartenant à A ou à B, avec un « ou » inclusif.

Qu'est-ce que l'intersection A ∩ B d'ensembles A et B ?

L'ensemble des éléments appartenant à la fois à A et à B.

Qu'est-ce que le complémentaire E \ A d'un ensemble A dans E ?

L'ensemble des éléments de E qui n'appartiennent pas à A.

Quand dit-on qu'un ensemble A est inclus dans un ensemble B ?

Lorsque tout élément de A est un élément de B.

Quelle est la formule de De Morgan pour le complémentaire de l'intersection ?

Le complémentaire de A ∩ B est égal à complémentaire A ∪ complémentaire B.

Quelle est la formule de De Morgan pour le complémentaire de la réunion ?

Le complémentaire de A ∪ B est égal à complémentaire A ∩ complémentaire B.

Quelles conditions définissent une partition (Xᵢ)ᵢ∈I de E ?

Sa réunion est E, les ensembles distincts sont disjoints, et aucun Xᵢ n’est vide.

Qu'est-ce qu'une application f : E → F ?

Une application associe à chaque x de E un unique élément f(x) de F.

Comment se définit la composition g∘f de f : E → F et g : F → G ?

Par g∘f(x) = g(f(x)).

Que vaut la fonction caractéristique 1_A d'un sous-ensemble A de E ?

Elle vaut 1 sur A et 0 sur E A.

Quelles conditions définissent une application injective ?

Deux images égales impliquent l'égalité des antécédents.

Quelles conditions définissent une application surjective ?

Tout élément du codomaine possède un antécédent.

Quelle formule donne le nombre d'applications de E dans F si E et F sont finis ?

Card(F^E) = (Card F)^{Card E}.

Quelle est la formule du nombre de p-combinaisons d'un ensemble de cardinal n ?

C'est binom{n}{p} = n! / (p!(n-p)!) pour 0 ≤ p ≤ n.

Quelles propriétés caractérisent une relation d'équivalence ?

Elle est réflexive, symétrique et transitive.

Comment exploiter un schéma logique de la forme A⇒(B⇒C) ?

On part de l’hypothèse B et on utilise A pour établir C.

Qu'est-ce qu'une implication A⇒B en logique ?

C'est une proposition pouvant être vraie ou fausse indépendamment de A et B.

Quelle est la première étape pour démontrer une propriété par récurrence simple ?

Démontrer l’initialisation.

Quelle étape suit l'initialisation dans une démonstration par récurrence simple ?

Établir que P(n) implique P(n+1) pour tout n≥n₀.

Comment prouver que deux ensembles A et B sont égaux ?

Il faut montrer qu'A est inclus dans B et B est inclus dans A.

Quelle propriété la fonction caractéristique transforme-t-elle en calcul algébrique ?

Elle transforme les opérations ensemblistes en calculs algébriques.

Quelle est la formule de la fonction caractéristique de l'intersection de A et B ?

C'est le produit des fonctions caractéristiques : 𝟙_{A∩B} = 𝟙_A × 𝟙_B.

Quelle est la formule de la fonction caractéristique de l'union de A et B ?

C'est 𝟙_{A∪B} = 𝟙_A + 𝟙_B − 𝟙_A × 𝟙_B.

Comment se définit la différence symétrique de deux ensembles A et B ?

C'est (A 5 B) 7 (B 5 A).

Quelle est la formule d'inclusion-exclusion pour deux ensembles finis A et B ?

Card(A∩B) + Card(A∪B) = Card(A) + Card(B).

Que peut-on dire du cardinal de deux ensembles finis en bijection ?

Ils ont le même cardinal.

Quelles propriétés sont équivalentes pour une application entre deux ensembles finis de même cardinal ?

L'injectivité, la surjectivité et la bijectivité.

Que compte le coefficient binomial \(\binom{n}{p}\) ?

Les parties de cardinal p d'un ensemble de cardinal n.

Quelle relation vérifie le coefficient binomial \(\binom{n}{p}\) ?

\(\binom{n}{p} + \binom{n}{p-1} = \binom{n+1}{p}\).

Quelle formule donne le coefficient binomial \(\binom{n}{p}\) pour \(0<p<n\) ?

\(\binom{n}{p} = \frac{n!}{p!(n-p)!}\).

Quelle est la formule de la somme des carrés de 0 à n ?

La somme des carrés est 9sum_{k=0}^{n}k^2=9frac{n(n+1)(2n+1)}{6}.

Quelle est la formule de la somme des cubes de 0 a0e0 n ?

La somme des cubes est 9sum_{k=0}^{n}k^3=9left(9frac{n(n+1)}{2}9right)^2.

Quelle formule relie la somme des coefficients binomiaux e0 e0 n ?

La somme 9sum_{k=p}^{n}9binom{k}{p}=9binom{n+1}{p+1} pour n>pa0e0 0.

Comment est de9finie la suite de Fibonacci ?

Par F_0=0, F_1=1 et F_{n+2}=F_{n+1}+F_n pour tout n naturel.

Combien de parties a un ensemble de cardinal n ?

Il a 2^n parties.

Quelle somme de coefficients binomiaux égale 2^n ?

La somme de k=0 à n de C(n,k) égale 2^n.

Quelle formule exprime la convolution des coefficients binomiaux ?

La somme de k=0 à n de C(p,k)C(q,n-k) égale C(p+q,n).

Comment calcule-t-on le nombre de partitions d’un ensemble de cardinal np en sous-ensembles de cardinal p ?

C'est (np)! divisé par (p!)^n fois n!.

Que fait la formule du crible pour une famille de p ensembles ?

Elle alterne les sommes des cardinalités des intersections de 1 à p ensembles.

Quel signe accompagne les intersections de r ensembles dans la formule du crible ?

Le signe est (-1)^{r+1}.