Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Mathématiques pour l’informatique. L1 Informatique I23. TD 1. Raisonnement, log

Mathématiques pour l’informatique. L1 Informatique I23. TD 1. Raisonnement, logique propositionnelle 1 EXERCICE 1. Un mathématicien discute avec un ami logicien dont la femme vient d’accoucher. Il lui demande “Avez-vous eu un garçon ou une ﬁlle ?” et le logicien lui répond “Oui”. Expliquez la réponse du logicien. Solution. Le connecteur logique ou est inclusif en logique mathématique alors qu’il est principalement utilisé de manière exclusive dans la langue naturelle, comme c’est le cas ici pour la question du mathématicien. Si on formalise ce problème en logique propositionnelle, on déﬁnit la variable propositionnelle G dont la valeur de vérité est vrai si l’enfant est une ﬁlle et faux si c’est un garçon. Le mathématicien veut donc savoir si G_␣G est vrai, ce qui est une tautologie appelée tiers exclus. EXERCICE 2. Trouvez des propositions en langue naturelle dans les- quelles le connecteur logique ou est inclusif. Solution. En voici quelques unes : paq “J’aime me promener en forêt ou à la montagne.” pbq “Le néon ou le radon sont des gaz.” pcq “12 est un multiple de 3 ou 4.” pdq “On peut trouver cet article en grande surface ou sur le net.” peq “Demain il y aura du vent ou du soleil.” EXERCICE 3. Chacun des énoncés suivant contient une erreur, indiquez s’il s’agit d’une erreur lexicale, syntaxique ou sémantique ? paq “La saucisse a mangé le chien.” pbq “Je n’ai rien compris à cet algorythme.” pcq “Moi Tarzan, toi bonjour ?” pdq “La leçon que j’ai appris.” peq “La nuit il fait plus froid que dehors.” Solution. Les phrases paq et peq ne contiennent ni erreur lexicale ni syn- taxique, elles respectent l’orthographe et la grammaire, mais contiennent une erreur sémantique, elles n’ont pas de sens. 1. Version du 29 avril 2022, 14 : 35 La phrase pbq contient uniquement une erreur lexicale, le mot algorithme étant mal orthographié. La phrase pcq contient une erreur syntaxique puisque la grammaire n’est pas respectée et une erreur sémantique. La phrase pdq contient une erreur syntaxique, la grammaire française n’est pas respectée. EXERCICE 4. Soit P, Q et R des variables propositionnelles. Dessinez un arbre de dérivation possible pour chacune des formules ci-dessous en rajoutant les parenthèses omises si nécessaire : paq pP _ Qq ñ ␣pP ^ ␣Rq pbq P _ Q _ ␣R. pcq ␣pP ^ Qq _ ␣R pdq pP ñ ␣Rq ô p␣P ô Qq. Solution. Les solutions sont représentées dans la ﬁgure 1. ñ _ ␣ P Q ␣ ^ P R paq _ _ ␣ P Q R pbq _ ^ ␣ ␣ P Q R pcq ô ô ñ ␣ ␣ P R P Q pdq Figure 1. Arbres de dérivation des formules paq à pdq. Il faut remarquer qu’en toute rigueur l’expression pbq n’est pas syntaxi- quement correcte, mais le connecteur _ étant associatif, on a pP _ Qq _ ␣R ” P _ pQ _ ␣Rq mais il faut néanmoins faire un choix et c’est la première expression qui est choisie conventionnellement. 1 L1 Informatique — Mathématiques pour l’informatique (I23) - TD. Raisonnement, Logique propositionnelle 2 EXERCICE 5. Soit P et Q deux propositions. On considère la formule P ñ Q. Que pouvez-vous déduire sur la valeur de vérité de Q si la formule est vraie ? Que pouvez déduire sur la valeur de vérité de P (resp. Q) si la formule et Q (resp. P) sont vraies ? Solution. Comme on peut le constater dans la table 1, la formule P ñ Q est vraie pour trois interprétations et Q peut être vraie ou fausse, on ne peut donc rien déduire sur Q. Si la formule P ñ Q et Q sont vraies, on ne peut rien déduire sur P qui peut là aussi être vraie ou fausse. En revanche si P ñ Q et P sont vraies alors Q est nécessairement vraie. P Q P ñ Q F F V F V V V F F V V V P Q P ñ Q F F V F V V V F F V V V P Q P ñ Q F F V F V V V F F V V V Table 1. Table de vérité du connecteur d’implication. Ce dernier résultat est appelé modus ponens. Si l’on dispose d’une pro- position P vraie et que l’on est en mesure de démontrer que P ñ Q alors on a prouvé que Q est vrai également. C’est l’un des piliers de la déduction logique. EXERCICE 6. On qualiﬁe de jumeau/jumelle toute personne qui a un ou plusieurs frères ou sœurs du même accouchement. Pourquoi la phrase “Donald et Vladimir sont des jumeaux” ne peut pas être considérée comme une proposition mathématique alors même que l’on peut lui at- tribuer une valeur de vérité ? Solution. Il y a une ambiguité sur l’interprétation du mot jumeaux dans l’énoncé. Ils le sont chacun de leur côté dans leurs propres fratries ou ils sont de la même fratrie. EXERCICE 7. Rappelez les deux lois de De Morgan et démontrez les. Solution. Si P et Q sont deux propositions, alors on a : ␣pP _ Qq ” p␣P ^ ␣Qq ␣pP ^ Qq ” p␣P _ ␣Qq et il suﬃt de comparer les tables de vérité pour conclure. P Q P _Q P ^Q ␣pP _Qq ␣P ^␣Q ␣pP ^Qq ␣P _␣Q F F F F V V V V F V V F F F V V V F V F F F V V V V V V F F F F Table 2. Tables de vérité des lois de De Morgan. EXERCICE 8. Soit P, Q et R des variables propositionnelles. Démontrez que le connecteur logique d’implication est transitif (cf. formule (F)) en construisant des tables de vérité. ppP ñ Qq ^ pQ ñ Rq ˘ ñ pP ñ Rq (F) Solution. On note A ” P ñ Q, B ” Q ñ R et C ” P ñ R. P Q R P ñ Q Q ñ R P ñ R A ^ B pA ^ Bq ñ C F F F V V V V V F F V V V V V V F V F V F V F V F V V V V V V V V F F F V F V V V F V F V V V V V V F V F F F V V V V V V V V V Table 3. Table de vérité de la formule F. Comme on peut le constater, toutes les interprétations sont vraies, la valeur de vérité de la formule F est indépendante des variables propo- sitionnelles qu’elle contient, c’est une tautologie. L1 Informatique — Mathématiques pour l’informatique (I23) - TD. Raisonnement, Logique propositionnelle 3 EXERCICE 9. : Soit P, Q et R des variables propositionnelles. Construi- sez la table de vérité du connecteur logique ternaire ⇛(“si/alors/sinon”) et démontrez que ⇛pP, Q, Rq ” pP ^ Qq _ p␣P ^ Rq. Solution. Le connecteur ternaire logique ⇛pP, Q, Rq a la valeur logique de la proposition Q si P est vrai et la valeur logique de la proposition R si P est faux. Il suﬃt alors de comparer les tables de vérité : P Q R ⇛ P ^ Q ␣P ^ R pP ^ Qq _ p␣P ^ Rq F F F F F F F F F V V F V V F V F F F F F F V V V F V V V F F F F F F V F V F F F F V V F V V F V V V V V V F V Table 4. Tables de vérité de ⇛et pP ^ Qq _ p␣P ^ Rq. EXERCICE 10. Démontrez que le connecteur ‘ est commutatif. Parmi les autres connecteurs binaires, lesquels sont commutatifs ? Solution. Pour montrer qu’un opérateur binaire ˛ est commutatif, c’est- à-dire que pour toutes propositions P et Q, on a P ˛ Q ” Q ˛ P, on peut se contenter de vériﬁer que quand on intervertit la valeur de vérité des deux variables propositionnelles P et Q, la valeur de vérité de P ˛ Q ne change pas (elle ne change évidemment pas quand les deux variables ont la même valeur de vérité !). C’est le cas également des connecteurs _, ^, ô, Ò et Ó (voir les tables de vérité dans le cours). C’est donc essentiellement le connecteur d’im- plication ñ qui n’est pas commutatif. P Q P ‘ Q F F F F V V V F V V V F Table 5. Table de vérité du connecteur ‘. EXERCICE 11. Soit P et Q deux propositions. Démontrez que pP ‘ Qq ” pP _ Qq ^ ␣pP ^ Qq Solution. Encore une fois, la table de vérité fournit le résultat : P Q P ‘ Q P _ Q ␣pP ^ Qq pP _ Qq ^ ␣pP ^ Qq F F F F V F F V V uploads/Philosophie/ correction-logique.pdf