Fiche de révision : Logique, ensembles et applications

📋 Plan du Cours

1. Assertions et prédicats
2. Connecteurs logiques
3. Quantificateurs logiques
4. Méthodes de raisonnement
5. Notions fondamentales sur les ensembles
6. Opérations et structures ensemblistes
7. Relations entre éléments
8. Fonctions et applications
9. Propriétés des applications
10. Composition et application inverse

📖 1. Assertions et prédicats

🔑 Notions clés & Définitions

• Assertion : Énoncé dont on peut dire sans ambiguïté s’il est vrai ou faux.

★ À maîtriser

📌 Un prédicat est un énoncé contenant une ou plusieurs variables qui devient une assertion lorsqu’on remplace ces variables par des éléments d’un ensemble donné.

Compléments

• Un axiome est une assertion déclarée vraie a priori, tandis qu’un théorème ou une proposition est une assertion démontrée.

💡 Astuce mémo

Assertion = vrai ou faux ; prédicat = variable à instancier

📖 2. Connecteurs logiques

🔑 Notions clés & Définitions

• Implication : Fausse lorsque P est vraie et Q est fausse, et vraie dans tous les autres cas.
• Conjonction : Vraie lorsque P et Q sont toutes deux vraies, et fausse sinon.
• Disjonction : Vraie lorsqu’au moins l’une de P ou Q est vraie, et fausse lorsqu’elles sont toutes deux fausses.
• Tautologie : Assertion toujours vraie quelles que soient les valeurs de vérité des assertions qui la composent.

📖 3. Quantificateurs logiques

📝 Points essentiels

• Le quantificateur universel ∀x∈E signifie que la propriété P(x) est vraie pour tout élément x de E.

• Le quantificateur existentiel ∃x∈E signifie qu’il existe au moins un élément x de E pour lequel P(x) est vraie.

📌 L’ordre de plusieurs quantificateurs peut changer le sens d’une proposition, car ∀x∃y P(x,y) n’est pas synonyme de ∃y∀x P(x,y).

📌 La négation de ∀x∈E, P(x) est ∃x∈E, non P(x), tandis que la négation de ∃x∈E, P(x) est ∀x∈E, non P(x).

💡 Astuce mémo

∀ signifie tous, ∃ signifie au moins un, ∃! signifie un seul

📖 4. Méthodes de raisonnement

★ À maîtriser

• Une démonstration par récurrence vérifie d’abord l’initialisation de P(n), puis démontre l’hérédité P(n) implique P(n+1).

• Un raisonnement par contre-exemple réfute une proposition universelle en exhibant un élément qui ne vérifie pas la propriété annoncée.

• Un raisonnement par l’absurde suppose la négation de la proposition et en déduit une contradiction.

Compléments

• Un raisonnement par contraposée démontre non Q implique non P pour établir l’implication P implique Q.

💡 Astuce mémo

Hypothèse, contre-exemple, contraposée, cas par cas, absurde, récurrence

📖 5. Notions fondamentales sur les ensembles

🔑 Notions clés & Définitions

• Ensemble : Collection d’objets bien déterminés appelés éléments, que l’on peut décrire par une liste ou par une propriété caractéristique.
• Cardinal : Nombre de ses éléments, noté card(E) ou |E|.
• Ensemble des parties : L’ensemble des parties de E, noté P(E), est l’ensemble de tous les sous-ensembles de E et possède 2^{card(E)} éléments lorsque E est fini.
• Produit cartésien : Le produit cartésien de E et F est l’ensemble des couples (x,y) tels que x appartient à E et y appartient à F.

📖 6. Opérations et structures ensemblistes

🔑 Notions clés & Définitions

• Intersection : Ensemble des éléments appartenant simultanément à A et à B.
• Réunion : Ensemble des éléments appartenant à A, à B, ou aux deux.
• Partition : Une partition d’un ensemble non vide est une famille de parties non vides, deux à deux disjointes, dont la réunion est l’ensemble tout entier.
• Différence symétrique : La différence symétrique de A et B contient les éléments appartenant à A ou à B mais pas aux deux.

💡 Astuce mémo

Des ensembles comme des régions qui se croisent, s’unissent ou se complètent

📖 7. Relations entre éléments

🔑 Notions clés & Définitions

• Relation d’équivalence : Relation binaire réflexive, symétrique et transitive.
• Classe d’équivalence : La classe d’équivalence d’un élément x est l’ensemble des éléments qui sont en relation d’équivalence avec x.
• Relation d’ordre : Relation binaire réflexive, antisymétrique et transitive.

📝 Points essentiels

📌 Un ordre total permet de comparer tous les couples d’éléments, tandis qu’un ordre partiel ne permet pas nécessairement de comparer chaque paire.

💡 Astuce mémo

Équivalence regroupe ; ordre compare

📖 8. Fonctions et applications

🔑 Notions clés & Définitions

• Fonction : Relation qui associe à chaque élément de E au plus un élément de F.
• Domaine de définition : Le domaine de définition d’une fonction est l’ensemble des éléments de départ auxquels la fonction associe effectivement une image.
• Application : Fonction qui associe à chaque élément de E exactement un élément de F.

📝 Points essentiels

📌 Pour une application f, l’image directe de A est l’ensemble f(A)={f(x) : x∈A}, tandis que l’image réciproque de B est f^{-1}(B)={x : f(x)∈B}.

💡 Astuce mémo

Une fonction associe au plus une image ; une application associe exactement une image

📖 9. Propriétés des applications

🔑 Notions clés & Définitions

• Injectivité : Une application est injective si deux éléments ayant la même image sont nécessairement égaux, c’est-à-dire si f(x)=f(y) implique x=y.
• Surjectivité : Une application est surjective si tout élément de l’ensemble d’arrivée possède au moins un antécédent.
• Bijection : Une application est bijective si elle est à la fois injective et surjective, donc si chaque élément de l’ensemble d’arrivée possède exactement un antécédent.

📝 Points essentiels

📌 Une application bijective admet une application inverse qui permet de revenir de l’ensemble d’arrivée vers l’ensemble de départ.

💡 Astuce mémo

Injective : au plus un antécédent ; surjective : au moins un ; bijective : exactement un

📖 10. Composition et application inverse

🔑 Notions clés & Définitions

• Composition : La composée de f:E→F et g:F→G est l’application g∘f:E→G définie par (g∘f)(x)=g(f(x)).
• Application inverse : Si f est une application bijective, son application inverse f^{-1} vérifie f^{-1}∘f=id_E et f∘f^{-1}=id_F.

📝 Points essentiels

📌 La composition de deux applications injectives est injective, et la composition de deux applications surjectives est surjective.

💡 Astuce mémo

Composer puis inverser : l’inverse n’existe que pour une bijection

📊 Tableaux de synthèse

Types de relations