Fiche de révision : Logique et raisonnements discrets

📋 Plan du Cours

1. Propositions et prédicats
2. Connecteurs logiques fondamentaux
3. Implication et équivalence
4. Équivalences et simplifications
5. Quantificateurs et négation
6. Méthodes de démonstration
7. Logique dans les programmes
8. Applications et exercices types

📖 1. Propositions et prédicats

🔑 Notions clés & Définitions

• Proposition logique : phrase à laquelle on peut attribuer une valeur de vérité, vraie ou fausse
• Prédicat : expression dépendant d’une variable qui devient une proposition lorsque cette variable est fixée

★ À maîtriser

📌 La négation de x > 3 est x ≤ 3, et non x < 3.

Compléments

• Pour le prédicat P(x) : x + 1 > 3, P(5) est vraie tandis que P(1) est fausse.

💡 Astuce mémo

Proposition fixée = vrai ou faux ; prédicat variable = vérité dépendante de x

📖 2. Connecteurs logiques fondamentaux

🔑 Notions clés & Définitions

• Conjonction : vraie lorsque P et Q sont toutes les deux vraies
• Disjonction : vraie si au moins une des deux propositions est vraie, y compris lorsque les deux le sont
• Ou exclusif : vrai lorsque exactement une des deux propositions est vraie

📝 Points essentiels

📐 Formule — Le OU exclusif vérifie $P \oplus Q \equiv (P \lor Q) \land \neg(P \land Q)$.

📖 3. Implication et équivalence

🔑 Notions clés & Définitions

• Implication : fausse uniquement lorsque P est vraie et Q est fausse

📝 Points essentiels

📌 Dans P ⇒ Q, P est une condition suffisante pour Q, tandis que Q est une condition nécessaire pour P.

📌 Les formulations se traduisent ainsi : P si Q signifie Q ⇒ P, P seulement si Q signifie P ⇒ Q, et P si et seulement si Q signifie P ⇔ Q.

📐 Formule — Une équivalence vérifie $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$.

💡 Astuce mémo

P⇒Q n’est pas Q⇒P ; l’équivalence exige les deux implications

📖 4. Équivalences et simplifications

★ À maîtriser

📐 Formule — Les équivalences fondamentales sont $\neg(\neg P) \equiv P$ et $P \Rightarrow Q \equiv \neg P \lor Q$.

📐 Formule — Les lois de De Morgan sont $\neg(P \land Q) \equiv \neg P \lor \neg Q$ et $\neg(P \lor Q) \equiv \neg P \land \neg Q$.

Compléments

📐 Formule — Les simplifications utiles comprennent $P \land P \equiv P$, $P \lor P \equiv P$, $P \lor(P \land Q) \equiv P$ et $P \land(P \lor Q) \equiv P$.

📌 Une tautologie est une formule toujours vraie, comme P ∨ ¬P, tandis qu’une contradiction est toujours fausse, comme P ∧ ¬P.

💡 Astuce mémo

Nier une conjonction transforme ET en OU, et nier une disjonction transforme OU en ET

📖 5. Quantificateurs et négation

🔑 Notions clés & Définitions

• Quantificateur universel : signifie que P(x) est vraie pour tout x appartenant à E
• Quantificateur existentiel : signifie qu’au moins un élément de E vérifie P(x)
• Existence et unicité : signifie qu’il existe un unique élément de E vérifiant P(x)

📝 Points essentiels

📌 Pour nier un quantificateur, on échange ∀ et ∃ puis on nie la propriété : ¬(∀x ∈ E, P(x)) ≡ ∃x ∈ E, ¬P(x), et ¬(∃x ∈ E, P(x)) ≡ ∀x ∈ E, ¬P(x).

📌 L’ordre des quantificateurs change le sens : ∀x ∈ R, ∃y ∈ R, x + y = 0 est vraie, tandis que ∃y ∈ R, ∀x ∈ R, x + y = 0 est fausse.

💡 Astuce mémo

Pour nier : inverser ∀ et ∃, puis nier la propriété finale

📖 6. Méthodes de démonstration

★ À maîtriser

• Pour une démonstration directe de P ⇒ Q, on suppose P vraie puis on démontre Q.

📌 Pour démontrer P ⇒ Q par contraposée, il suffit de démontrer ¬Q ⇒ ¬P, car P ⇒ Q ≡ ¬Q ⇒ ¬P.

• Pour démontrer P par l’absurde, on suppose ¬P et on cherche une contradiction.

📌 Pour réfuter une proposition universelle, un seul contre-exemple suffit.

Compléments

• Une démonstration par récurrence comporte une initialisation vérifiant P(n0), puis une hérédité montrant que P(n) entraîne P(n + 1).

💡 Astuce mémo

Directe, contraposée, absurde, cas, contre-exemple, récurrence

📖 7. Logique dans les programmes

★ À maîtriser

• La règle d’accès « administrateur ou connecté et propriétaire » se formalise par A ∨ (C ∧ P).

📌 Une valeur est valide exactement lorsque 0 ≤ x ≤ 100, et la condition d’erreur est x < 0 ∨ x > 100.

Compléments

• Une requête sélectionnant les étudiants de BUT1 informatique non absents utilise la condition logique I(x) ∧ ¬A(x).

💡 Astuce mémo

Condition logique formalisée → test informatique exécutable

📖 8. Applications et exercices types

📝 Points essentiels

• Pour tout réel x, il existe un réel y tel que y > x ; on peut choisir y = x + 1.

• Si n est divisible par 6, alors n est divisible par 3, car n = 6k = 3(2k).

📐 Formule — Si x ≥ y, alors $\min(x,y)=\frac{x+y-|x-y|}{2}$, car |x − y| = x − y.

📊 Tableaux de synthèse

Traductions logiques françaises