Logique et Ensembles Discrets

Bénéficiez d'un survol complet des Mathématiques Discrètes axé sur l'essentiel pour une maîtrise rapide et efficace.

Algèbre Booléenne : Fondations de la Logique

• Proposition : Une affirmation qui est soit **Vraie (V)**, soit **Fausse (F)**.

  Ex: "La carotte est un légume" (Vraie), "La carotte est un moyen de locomotion" (Fausse).

• Table de Vérité : Annonce toutes les valeurs de vérité possibles d'une proposition.

• Tautologie : Proposition toujours vraie.

• Antilogie (Contradiction) : Proposition toujours fausse.

• Opérateurs LogiquesClés :

  • Négation () : "non ". Inverse la valeur de vérité. Ex: "Il pleut" devient "Il ne pleut pas".

  • Conjonction () : " et ". Vrai si ET sont Vrais.

  • Disjonction () : " ou " (inclusif). Vrai si OU (ou les deux) sontVrais.

  • Disjonction Exclusive ( ou ) : "soit , soit ". Vrai si EXACTEMENT un de ou est Vrai.

  • Équivalence () : " si et seulement si ". Vrai si et ont la même valeur de vérité.

  • Implication () : "si , alors ". FauxUNIQUEMENT si est Vrai ET est Faux.

    • Ne pas confondre avec le "si... alors..." du français. En math, si la prémisse est fausse, l'implication est toujours vraie.

    • Contraposée : . Équivalente à l'implication originale.

    • Réciproque : . Non équivalente à l'implication originale.

• Priorités des Opérateurs : (plus forte) > > , (même priorité) > > (plus faible). Toujours utiliser des parenthèses pour éviter les ambiguïtés.

• Lois de De Morgan :

  • Utiles pour nier des conjonctions et disjonctions.

• Négation d'une Implication : .

• Formes Normales : Conventions d'écriture pour faciliter la lecture des propositions (utilisé en informatique/électronique).

  • Disjonctive (FND) : Disjonction de termes séparés par des conjonctions. Ex: .

  • Conjonctive (FNC) : Conjonction de termes séparés par des disjonctions. Ex: .

Théorie des Ensembles : Collections Fondamentales

• Ensemble : Collection d'objets distincts (éléments).

  • Notation: ( appartient à ), ( n'appartient pas à ).

• Cardinal ( ou ) : Nombre d'éléments dans un ensemble. Décrit la "taille" de l'ensemble.

<li>
    <b>Ensemble Vide ($\varnothing$ ou $\{\}$) :</b> L'unique ensemble qui ne contient aucun élément. Cardinal nul.
    <ul>
        <li>Toujours inclus dans tout ensemble : $\varnothing \subseteq S$.</li>
    </ul>
</li>
<li>
    <b>Égalité d'ensembles ($S_1 = S_2$) :</b> Si $S_1$ et $S_2$ contiennent exactement les mêmes éléments.
    <ul>
        <li><mark>L'ordre et la façonde les lister n'importent pas.</mark></li>
    </ul>
</li>
<li>
    <b>Sous-ensemble ($S_1 \subseteq S_2$) :</b> Si tous les éléments de $S_1$ appartiennent à $S_2$.
    <ul>
        <li><b>Inclusion Stricte ($S_1 \subset S_2$) :</b> Si $S_1 \subseteq S_2$ et $S_1 \neq S_2$.</li>
        <li><mark>Propriété clé pour prouver l'égalité : $S_1 = S_2 \Leftrightarrow (S_1 \subseteq S_2 \text{ et } S_2 \subseteq S_1)$.</mark></li>
    </ul>
</li>
<li>
    <b>Définition d'Ensembles :</b>
    <ul>
        <li><b>En extension :</b> Lister tous les éléments (entreaccolades). Ex: $\{1, 2, 3\}$.</li>
        <li><b>En compréhension :</b> Fournir une propriété qui caractérise les éléments. Ex: \{x \in \mathbb{N} \mid x &lt; 4\}.</li>
        <li><mark>La définition en compréhension est essentielle pour les ensembles degrande taille ou infinis.</mark></li>
    </ul>
</li>
<li>
    <b>Opérations Ensemblistes (définies via opérateurs logiques) :</b>
    <ul>
        <li><b>Parties d'un ensemble ($\mathscr{P}(S)$) :</b> L'ensemble de *tous* les sous-ensembles de $S$.
            <ul>
                <li>Si $|S|=n$, alors $|\mathscr{P}(S)|=2^n$.</li>
            </ul>
        </li>
        <li><b>Complémentaire ($\mathcal{C}_A(S)$ ou $\bar{S}$):</b> Éléments de l'ensemble universel $A$ qui ne sont pas dans $S$. ($x \in A \wedge x \notin S$). <mark>Nécessite un ensemble de référence $A$.</mark></li>
        <li><b>Union ($S_1 \cup S_2$) :</b> Éléments qui sont dans $S_1$ OU dans $S_2$ (ou les deux). ($x \in S_1 \vee x \in S_2$).</li>
        <li><b>Intersection ($S_1 \cap S_2$) :</b> Éléments qui sontdans $S_1$ ET dans $S_2$. ($x \in S_1 \wedge x \in S_2$).</li>
        <li><b>Différence ($S_1 \setminus S_2$) :</b> Éléments qui sont dans $S_1$ MAIS PAS dans $S_2$.($x \in S_1 \wedge x \notin S_2$).</li>
        <li><b>Différence Symétrique ($S_1 \triangle S_2$) :</b> Éléments qui sont dans $S_1$ OU $S_2$, mais PAS dans l'intersection. ($ (S_1 \cupS_2) \setminus (S_1 \cap S_2) ).&lt;/li&gt;
    &lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt;
    &lt;b&gt;Produit Cartésien (S_1 \times S_2$) :</b> Ensemble de *tous* les couples ordonnés $(x, y)$ où $x \in S_1$ et $y \in S_2$.
    <ul>
        <li>Un <b>couple</b> $(a, b)$ est une séquence ordonnée. $(a,b) \ne (b,a)$ en général.</li>
        <li>Une <b>paire</b> $\{a, b\}$est un ensemble non ordonné. $\{a,b\} = \{b,a\}$.</li>
        <li>Peut être généralisé à $n$-uples pour $n$ ensembles ($S_1 \times \cdots \times S_n$).</li>
        <li><mark>Le produit cartésien n'estpas commutatif : $S_1 \times S_2 \neq S_2 \times S_1$ si $S_1 \neq S_2$.</mark></li>
    </ul>
</li>

Théorie des Graphes : Relations et Connexité

• Graphe non Orienté () :

  • : Ensemble fini, non vide de sommets.

  • : Ensemble fini de paires de sommets (arêtes). (Sans boucles, simples).

  • Ordre : (nombre de sommets).

  • Taille : (nombre d'arêtes).

• Adjacence :

  • Deux sommets sont adjacents si .

  • Une arête est incidente à et .

  • Voisinage () : Ensemble des sommets adjacents à .

  • Degré () : , nombre d'arêtes incidentes à .

  • Somme des degrés :.

• Matrice d'Adjacence : Matrice où si , $0$ sinon. (Symétrique pour graphes non orientés).

• Variantes de Graphes :

  • Multigraphe : Peut avoir des boucles et plusieurs arêtes entre deux mêmes sommets (arêtes parallèles).

  • GrapheDirigé : Arcs (flèches) au lieu d'arêtes, modélisant des relations non symétriques. Matrice d'adjacence non symétrique. (Couples ordonnés).

  • Graphe Étiqueté (Pondéré/Valué) : Chaquearête/arc a une étiquette (nombre), souvent un poids/coût.

• Chemins et Connexité :

  • Chemin : Séquence de sommets où chaque .

    • Longueur : Nombre d'arêtes.

    • Élémentaire : Tous les sommets du chemin sont distincts.

  • Graphe Connexe : Pour toute paire de sommets, il existe un chemin les reliant.

  • Cycle : Chemin qui se termine au sommet où il a commencé ().

  • Acyclique : Ungraphe sans cycle élémentaire.

  • Arbre : Graphe connexe ET acyclique. (Plusieurs définitions équivalentes, ex: connexe et arêtes).

• Cheminset Cycles Spéciaux :

  • Eulérien : Passe une unique fois par chaque arête.

    • Existence : Graphe connexe et tous les sommets de degré pair (pour cycle) ou deux sommets de degré impair (pour chemin).

  • Hamiltonien : Passe une unique fois par chaque sommet (élémentaire).

    • Problème difficile (NP-complet), pas de critère simple d'existence.

• Distances dans un Graphe :

  • Distance () : Longueur du plus court chemin entre et . (Uniquement pour graphes connexes).

  • Matrice des Distances : Tableau récapitulant toutes les distances entre paires de sommets.

  • Diamètre () : Plus longue distance entre deux sommets dans le graphe.

• Coloration de Graphes :

  • Coloration : Assignation de couleurs aux sommets telle que deux sommets adjacents n'aient pas la même couleur.

  • Nombre Chromatique () : Nombre minimum decouleurs nécessaires pour colorier un graphe.

    • Problème difficile (NP-complet).

  • Théorème des 4 couleurs : Si un graphe est planaire (dessinable sans que les arêtes ne se croisent), alors .

Dénombrement : L'Art de Compter

• Importance : Essentiel en informatique (complexité algorithmique, structuresde données), biologie (ADN), etc.

• Modélisation : Étape cruciale pour savoir quoi compter.

  • Diagrammes en arbre : Visualiser les choix successifs.

  • Encodage : Représenter lessolutions (ex: un code de vélo comme un n-uple).

• Questions Fondamentales pour le Choix de la Méthode :

  1. L'ordre des composantes a-t-il de l'importance ?

  2. Les répétitions des composantes sont-elles autorisées ?

• Outils de Base du Dénombrement :

  • Règle du Produit : Si une tâche est une séquence de sous-tâches, avec façons pour chaque sous-tâche, le total est .

  • Principe d'Inclusion-Exclusion : Pour deux ensembles : .

    • Permet d'éviter le surcomptage.

  • Règle de la Division : Si une tâche peut être faite de façons, et que de ces façons sont équivalentes, le nombre de façons distinctes est .

  • Principe des Tiroirs (Pigeonhole Principle) : Si objets sont placés dans boîtes avec , alors au moins une boîte contient au moins deux objets.

    • Application aux bijections : Une fonction d'un ensemble detaille vers un ensemble de taille ne peut pas être bijective.

• Arrangements et Permutations (L'ordre importe) :

  • Arrangement sans répétitions () : Séquence ordonnée de éléments distincts parmi .

    • Formule : .

  • Permutation () : Cas particulier où . Séquence ordonnée de éléments distincts.

    • Formule : .

  • Arrangement avec répétitions () :Séquence ordonnée de éléments parmi , où les répétitions sont permises.

    • Formule : .

• Combinaisons (L'ordre n'importe pas) :

  • Combinaison sans répétition ( ou ) : Séquence non ordonnée de éléments distincts parmi .

    • Formule : .

    • Propriété de symétrie : .

  • Binôme de Newton: . Les sont les coefficients binomiaux.

  • Triangle de Pascal : Représentation récursive des coefficients binomiaux.

Principe de Récurrence : Définitions et Preuves

• Récurrence : Définir un objet ou prouver une propriété en se basant sur des cas "plus petits".

• Définitions Récursives : Définir un objet ou une fonction en fonction d'elle-même.

  • Étape de base : Spécifier la valeur pour le cas le plus simple (ex: ).

  • Étape d'induction (récurrence) : Donner une règle pour calculer la valeur à partir des valeurs précédentes (ex: à partir de ).

  • Essentiel que la définition soit bien fondée et sans récursion infinie.

  • Ex: Fonction factorielle :

• Preuves par Récurrence : Prouver qu'une propriété est vraiepour tout .

  • Étape de base : Vérifier que est vraie (ou la plus petite valeur du domaine).

  • Étape d'induction : Montrer que si est vraie pour un certain (hypothèse d'induction), alors est également vraie.

    • Ne suppose pas que est toujours vrai, juste que si elle l'est, la suivante l'est aussi.

  • Très utilisé pour prouver égalités, inégalités, divisibilité, propriétés de graphes, etc.

  • Ex: Prouver que .