IMG_3112.jpeg

# Chapitre 1 Logique et raisonnement ## 1.1 Logique ### Définition 1.1. Une **déclaration** est une phrase déclarative qui est soit vraie, soit fausse, mais pas les deux à la fois. ### Exemple 1.1. Les énoncés suivants sont des déclarations : * Toronto est la capitale du Canada. * $1 + 1 = 3$...

# Chapitre 1 Logique et raisonnement ## 1.1 Logique ### Définition 1.1. Une **déclaration** est une phrase déclarative qui est soit vraie, soit fausse, mais pas les deux à la fois. ### Exemple 1.1. Les énoncés suivants sont des déclarations : * Toronto est la capitale du Canada. * $1 + 1 = 3$. Les énoncés suivants ne sont pas des déclarations : * Ouvrez la porte. * Quelle heure est-il ? * $x + 1 = 2$. ### Définition 1.2. Une **variable propositionnelle** est une variable qui représente une déclaration. Les variables propositionnelles sont généralement désignées par les lettres $p, q, r, s, \dots$. ### Définition 1.3. Un **opérateur logique** (ou **connecteur logique**) est un symbole ou un mot utilisé pour connecter deux ou plusieurs déclarations en une nouvelle. ### Définition 1.4. Une **table de vérité** est un tableau qui montre la valeur de vérité d'une déclaration composée pour toutes les valeurs de vérité possibles de ses déclarations composantes. ### Négation La négation d'une déclaration $p$ est la déclaration "non $p$", notée $\neg p$. La table de vérité de la négation est la suivante : | $p$ | $\neg p$ | | --- | --- | | V | F | | F | V | ### Conjonction La conjonction de deux déclarations $p$ et $q$ est la déclaration "$p$ et $q$", notée $p \land q$. La conjonction $p \land q$ est vraie si et seulement si $p$ et $q$ sont toutes les deux vraies. La table de vérité de la conjonction est la suivante : | $p$ | $q$ | $p \land q$ | | --- | --- | --- | | V | V | V | | V | F | F | | F | V | F | | F | F | F | ### Disjonction La disjonction de deux déclarations $p$ et $q$ est la déclaration "$p$ ou $q$", notée $p \lor q$. La disjonction $p \lor q$ est fausse si et seulement si $p$ et $q$ sont toutes les deux fausses. La table de vérité de la disjonction est la suivante : | $p$ | $q$ | $p \lor q$ | | --- | --- | --- | | V | V | V | | V | F | V | | F | V | V | | F | F | F | ### Disjonction Exclusif La disjonction exclusive de deux déclarations $p$ et $q$ est la déclaration "$p$ ou $q$, mais pas les deux", notée $p \oplus q$. La disjonction exclusive $p \oplus q$ est vraie si et seulement si exactement une de $p$ et $q$ est vraie. La table de vérité de la disjonction exclusive est la suivante : | $p$ | $q$ | $p \oplus q$ | | --- | --- | --- | | V | V | F | | V | F | V | | F | V | V | | F | F | F | ### Définition 1.5. Une **tautologie** est une déclaration qui est toujours vraie. Une **contradiction** est une déclaration qui est toujours fausse. Une **contingence** est une déclaration qui n'est ni une tautologie ni une contradiction. ### Implication L'implication de deux déclarations $p$ et $q$ est la déclaration "si $p$, alors $q$", notée $p \rightarrow q$. L'implication $p \rightarrow q$ est fausse si et seulement si $p$ est vraie et $q$ est fausse. Dans l'implication $p \rightarrow q$, $p$ est appelée l'*hypothèse* (ou l'*antécédent*) et $q$ est appelée la *conclusion* (ou le *conséquent*). La table de vérité de l'implication est la suivante : | $p$ | $q$ | $p \rightarrow q$ | | --- | --- | --- | | V | V | V | | V | F | F | | F | V | V | | F | F | V | ### Définition 1.6. Les implication suivantes sont reliées à l'implication $p \rightarrow q$: * La **réciproque** de $p \rightarrow q$ est $q \rightarrow p$. * L'**inverse** de $p \rightarrow q$ est $\neg p \rightarrow \neg q$. * La **contraposée** de $p \rightarrow q$ est $\neg q \rightarrow \neg p$. ### Exemple 1.2. Considérons l'implication "Si il pleut, alors le sol est mouillé". * La réciproque est "Si le sol est mouillé, alors il pleut." * L'inverse est "Si il ne pleut pas, alors le sol n'est pas mouillé." * La contraposée est "Si le sol n'est pas mouillé, alors il ne pleut pas." ### Théorème 1.1. L'implication $p \rightarrow q$ et sa contraposée $\neg q \rightarrow \neg p$ ont les mêmes valeurs de vérité. ### Biconditionnelle La biconditionnelle de deux déclarations $p$ et $q$ est la déclaration "$p$ si et seulement si $q$", notée $p \leftrightarrow q$. La biconditionnelle $p \leftrightarrow q$ est vraie si et seulement si $p$ et $q$ ont les mêmes valeurs de vérité. La table de vérité de la biconditionnelle est la suivante : | $p$ | $q$ | $p \leftrightarrow q$ | | --- | --- | --- | | V | V | V | | V | F | F | | F | V | F | | F | F | V | ### Définition 1.7. Deux déclarations $p$ et $q$ sont **logiquement équivalentes** si $p \leftrightarrow q$ est une tautologie. En d'autres termes, $p$ et $q$ ont les mêmes valeurs de vérité dans toutes les circonstances possibles. L'équivalence logique de $p$ et $q$ est notée $p \equiv q$. ### Exemple 1.3. Montrer que $p \rightarrow q$ et $\neg p \lor q$ sont logiquement équivalentes. *Solution.* Construisons la table de vérité des deux déclarations : | $p$ | $q$ | $p \rightarrow q$ | $\neg p$ | $\neg p \lor q$ | | --- | --- | --- | --- | --- | | V | V | V | F | V | | V | F | F | F | F | | F | V | V | V | V | | F | F | V | V | V | Puisque les colonnes de $p \rightarrow q$ et $\neg p \lor q$ sont identiques, alors $p \rightarrow q \equiv \neg p \lor q$. ### Les lois de De Morgan Les lois de De Morgan sont deux règles de la logique qui relient la négation de conjonctions et de disjonctions à la disjonction et à la conjonction de négations. Elles sont les suivantes : * $\neg (p \land q) \equiv \neg p \lor \neg q$ * $\neg (p \lor q) \equiv \neg p \land \neg q$