Fiche de révision : Logique et raisonnement mathématique

📋 Plan du Cours

1. Propositions et connecteurs logiques
2. Implication et équivalence logique
3. Prédicats et quantificateurs
4. Méthodes de démonstration
5. Raisonnement par récurrence
6. Ensembles et inclusion
7. Opérations ensemblistes
8. Tables d’appartenance

📖 1. Propositions et connecteurs logiques

🔑 Notions clés & Définitions

• Proposition : Affirmation qui est soit vraie, soit fausse, mais jamais les deux à la fois, conformément au principe du tiers exclu.
• Valeur de vérité : Nombre qui vaut 0 lorsque la proposition P est fausse et 1 lorsqu’elle est vraie.
• Négation : La négation ¬P est vraie si et seulement si P est fausse.
• Conjonction : Proposition « P et Q » vraie si et seulement si P et Q sont toutes deux vraies.
• Disjonction : Proposition « P ou Q » vraie si et seulement si au moins une des propositions P ou Q est vraie.

📝 Points essentiels

📌 Une expression contenant une variable non fixée, comme « 6x = 42 », n’est pas une proposition car sa valeur de vérité dépend de la valeur attribuée à la variable.

📌 Une tautologie est vraie pour toutes les valeurs de ses atomes, tandis qu’une contradiction est fausse pour toutes ces valeurs.

💡 Astuce mémo

Proposition vraie ou fausse, mais jamais les deux ; une expression à variable libre n’est pas une proposition.

📖 2. Implication et équivalence logique

🔑 Notions clés & Définitions

• Implication : Proposition fausse uniquement lorsque P est vraie et Q est fausse.
• Équivalence : Proposition vraie lorsque P et Q ont simultanément la même valeur de vérité.

★ À maîtriser

📌 Dans P → Q, P est une condition suffisante pour Q et Q est une condition nécessaire pour P.

📌 La contraposée de P → Q est ¬Q → ¬P, tandis que la réciproque est Q → P.

📐 Formule — La contraposée est équivalente à l’implication initiale : $(P \to Q) \equiv (\neg Q \to \neg P).$

Compléments

📐 Formule — Une implication peut s’écrire avec la disjonction : $(P \to Q) \equiv (\neg P \lor Q).$

💡 Astuce mémo

Dans P → Q, P suffit et Q est nécessaire ; dans P ↔ Q, chacune est nécessaire et suffisante.

📖 3. Prédicats et quantificateurs

🔑 Notions clés & Définitions

• Prédicat : Expression contenant des variables de E qui devient une proposition lorsqu’on remplace ces variables par des éléments de E.
• Quantificateur universel : Le quantificateur universel ∀ signifie « pour tout » ou « quel que soit » et affirme qu’un prédicat est vrai pour chaque élément du domaine.
• Quantificateur existentiel : Le quantificateur existentiel ∃ signifie « il existe au moins un » et affirme qu’un prédicat est vrai pour au moins un élément du domaine.
• Ensemble de vérité : Ensemble des éléments a de E pour lesquels P(a) est une proposition vraie.

📝 Points essentiels

• Une variable libre peut modifier la valeur de vérité d’une expression, tandis qu’une variable liée est contrôlée par un quantificateur ou un autre opérateur.

• La négation de ∀x P(x) est équivalente à ∃x ¬P(x), et la négation de ∃x P(x) est équivalente à ∀x ¬P(x).

• Les quantificateurs de même nature peuvent être permutés sans changer la proposition, tandis que permuter ∃ et ∀ ne donne en général qu’une implication.

💡 Astuce mémo

Une variable libre dépend d’une valeur ; un quantificateur la rend liée et permet d’obtenir une proposition.

📖 4. Méthodes de démonstration

★ À maîtriser

• 🔄 Une démonstration correcte suit plusieurs étapes:
  1. Identifier les hypothèses
  2. Formuler la conclusion
  3. Choisir un schéma de démonstration
  4. Justifier chaque étape

📌 Si P et P → Q sont vraies, alors Q est vraie.

• Pour démontrer P → Q, on peut démontrer sa contraposée ¬Q → ¬P, qui lui est tautologiquement équivalente.

• Pour démontrer une proposition, on peut supposer qu’elle est fausse et en déduire une proposition connue comme fausse.

• Pour démontrer ∀n ∈ N P(n), il faut prouver P(0) puis démontrer que, pour tout n ∈ N, P(n) implique P(n+1).

Compléments

📌 L’initialisation établit la propriété au premier rang, tandis que l’hérédité montre que sa validité à un rang entraîne sa validité au rang suivant.

💡 Astuce mémo

Détachement, contraposition, absurde, récurrence : appliquer une implication, la retourner, produire une contradiction, puis avancer de n à n+1.

📖 5. Raisonnement par récurrence

★ À maîtriser

• Pour démontrer $\forall n \in \mathbb{N},\ P(n)$ par récurrence, il faut établir l’initialisation $P(0)$ puis l’hérédité $\forall n \in \mathbb{N},\ P(n) \Rightarrow P(n+1)$.

• Pour démontrer que $2^{2n}+2$ est divisible par 3 pour tout naturel n, l’initialisation donne $2^0+2=3$, puis l’hérédité utilise $2^{2(n+1)}+2=(2^{2n}+2)+3\cdot2^{2n}$.

Compléments

• La récurrence forte consiste à prouver $P(0)$ puis $\forall n \in \mathbb{N},\ (P(0) \land P(1) \land \cdots \land P(n)) \Rightarrow P(n+1)$.

• Le principe de récurrence repose sur le fait que chaque nombre naturel est atteint en partant de 0 et en répétant le passage au successeur $n \mapsto n+1$.

• Pour une propriété sur les entiers positifs, on peut initialiser en 1 et démontrer $P(n) \Rightarrow P(n+1)$; pour une propriété sur les entiers positifs impairs, on initialise en 1 et démontre $P(n) \Rightarrow P(n+2)$.

• Pour démontrer une propriété $P(z)$ sur tous les entiers relatifs, on initialise en 0 puis on démontre simultanément $P(z) \Rightarrow P(z+1)$ et $P(z) \Rightarrow P(z-1)$.

💡 Astuce mémo

Une rangée de dominos : la base fait tomber le premier, puis l’hérédité entraîne le suivant.

📖 6. Ensembles et inclusion

🔑 Notions clés & Définitions

• Ensemble : G. Cantor — Une collection d’objets déterminée par les éléments qu’elle contient; dans une approche axiomatique, il est défini par des propriétés appelées axiomes.
• Égalité de deux ensembles : Deux ensembles E et F sont égaux si et seulement si $\forall x,\ x \in E \Leftrightarrow x \in F$.
• Inclusion : Un ensemble E est inclus dans un ensemble F, noté $E \subseteq F$, si tout élément de E appartient à F, c’est-à-dire $\forall x,\ x \in E \Rightarrow x \in F$.
• Ensemble des parties : Contient exactement tous les sous-ensembles de E, selon $\forall A,\ A\in\mathcal{P}(E)\Leftrightarrow A\subseteq E$.

★ À maîtriser

📌 Un ensemble peut être défini en extension par la liste complète de ses éléments ou en compréhension par la propriété caractéristique vérifiée par ses éléments.

📌 L’égalité de deux ensembles peut être démontrée par double inclusion : $E=F$ si et seulement si $E\subseteq F$ et $F\subseteq E$.

Compléments

• L’ensemble vide, noté $\varnothing$, est l’unique ensemble qui ne contient aucun élément.

💡 Astuce mémo

x ∈ E signifie élément, tandis que A ⊆ E signifie partie de E.

📖 7. Opérations ensemblistes

🔑 Notions clés & Définitions

• Complémentaire : Pour une partie A d’un ensemble E, le complémentaire de A est $A^c=\{x\in E\mid x\notin A\}$.
• Intersection : L’intersection de A et B est $A\cap B=\{x\mid x\in A\text{ et }x\in B\}$.
• Réunion : La réunion de A et B est $A\cup B=\{x\mid x\in A\text{ ou }x\in B\}$.
• Ensembles disjoints : Deux ensembles A et B sont disjoints si et seulement si $A\cap B=\varnothing$.
• Différence symétrique : La différence symétrique de A et B est $A\triangle B=(A\setminus B)\cup(B\setminus A)$.

📝 Points essentiels

📌 Les lois de De Morgan sont $(A\cap B)^c=A^c\cup B^c$ et $(A\cup B)^c=A^c\cap B^c$.

💡 Astuce mémo

Complémenter transforme une intersection en réunion, et une réunion en intersection.

📖 8. Tables d’appartenance

🔑 Notions clés & Définitions

• Table d’appartenance : Une table d’appartenance indique par 1 ou 0 si un élément appartient ou n’appartient pas aux ensembles étudiés et permet de comparer les expressions ensemblistes.

★ À maîtriser

📌 Deux expressions ensemblistes sont égales lorsque leurs colonnes d’appartenance sont identiques pour toutes les possibilités d’appartenance.

📌 Une condition nécessaire à une égalité X=Y est une conséquence de cette égalité, tandis qu’une condition suffisante implique cette égalité.

Compléments

• Pour démontrer la loi $(A\cup B)^c=A^c\cap B^c$ par table d’appartenance, on vérifie que les colonnes correspondant aux deux expressions sont identiques dans les quatre cas d’appartenance de x à A et B.

📌 Pour les expressions $X=A\triangle(B^c\cap C)$ et $Y=(A\triangle B^c)\cap C$, l’inclusion $Y\subseteq X$ est toujours vraie et l’égalité $X=Y$ est équivalente à $A\subseteq C$.

📊 Tableaux de synthèse

Principaux connecteurs logiques

Notions d’appartenance et d’inclusion