Remerciez-le!

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

© J.Y. Antoine Logique pour l’informatique Jean-Yves Antoine http://www.info.un

© J.Y. Antoine Logique pour l’informatique Jean-Yves Antoine http://www.info.univ-tours.fr/~antoine UFR Sciences et Techniques Licence S&T 2°année © J.Y. Antoine MATHEMATIQUES ET INFORMATIQUE Machine de Türing (1930) : théorie logique des calculateurs Machine de Von Neumann (1946) : architecture ordinateurs Travaux pionniers … toujours d’actualité Mathématiques et informatique Conception systèmes informatiques logique booléenne Compilation : th. des langages et automates logique formelle Programmation - récursion/induction algèbre - combinatoire analyse (séries) - structures de données (arbres, graphes) maths. discrètes - programmation logique logique Bases de données algèbre relationnelle © J.Y. Antoine EVALUATION Contrôle continu intégral • Deux ou trois courts interrogations … annoncées ou non • Éventuellement un TP corrigé Note finale F • F = CC Seconde session (si échec) • Examen papier CT2 • F = CT2 (note de contrôle continu CC ne compte plus) © J.Y. Antoine BIBLIOGRAPHIE Logique S. Cerrito «Logique pour l’informatique : introduction à la déduction automatique», Vuibert. A. Aho et J. Ullman, « Concepts fondamentaux de l'informatique », Dunod (chap. 12-14) G. Chazal, « Elements de logique formelle » T. Lucas, I. Berlanger, I. De Greef, « Initiation à la logique formelle », De Boeck R. Cori et D. Lascar, "Logique mathématique", Masson (vol. 1) P. Gochet, P. Gribomont, "Logique (méthodes pour l'informatique fondamentale)" (vol. 1) D. Hofstadter, “ Gödel Escher Bach les brins d’une guirlande éternelle ”, Dunod C. Jacquemin, "Logique et mathématiques pour l'informatique et l'IA", Masson Approches logiques de la programmation D. Gries, "The science of programming", Springer Verlag L. Sterling & E. Shapiro, "L'art de Prolog", Masson © J.Y. Antoine Logique pour l’informatique Chapitre I — Introduction UFR Sciences et Techniques Licence S&T 2°année © J.Y. Antoine INTRODUCTION - Objectifs 1.1. Notions 1.2. Pratiques 1.1.1. Vérité et validité 1.1.2. Approches formelles et sémantiques : quelles relations (consistance, complétude) 1.1.3. Approche formelle : axiome, théorème 1.1.4. Approche sémantique : interprétation, modèle, tautologie, équivalence 1.1.5. Déduction : conséquence logique et validité d’un raisonnement 1.1.6. Consistance et complétude © J.Y. Antoine VERITE ET VALIDITE • Raisonnement 1 Tous les chevaux ont une crinière Les poneys sont des chevaux Donc les poneys ont une crinière • Raisonnement 2 Tous les oiseaux volent L ’autruche est un oiseau Donc l ’autruche vole • Raisonnement 3 Tout nombre pair est divisible par 2 Tout nombre divisible par 2 est pair valide valide valide valide in invalide valide • Validité ≠ ≠ ≠ ≠Vérité • CN validité : propagation de la vérité (fausseté) © J.Y. Antoine LOGIQUE Approche syntaxique (formelle) Étude du point de vue de la forme des énoncés logiques systèmes formels Approche sémantique Étude du point de vue de la propagation de la vérité entre prémisses et conclusions Deux approches ... … une même réalité © J.Y. Antoine LOGIQUE : APPROCHE FORMELLE • Axiome Proposition primitive considérée comme non démontrable et admise a priori Exemple : axiomes de la géométrie euclidienne • Théorème Proposition pouvant être démontrée à partir d’axiomes ou d’autres théorèmes à l’aide de raisonnement formels valides. Les axiomes sont considérés comme des théorèmes particuliers. Notation ⊥ ⊥ ⊥ ⊥ T • Règle d’inférence Schéma minimal de raisonnement valide qui permet de produire de nouvelles propositions à partir de prémisses qui sont soient des théorèmes, soit des hypothèses. Exemple : modus ponens (P1) Si A alors B (P2) A (T) Donc B Notation ⊥ ⊥ ⊥ ⊥ P1, P2 T © J.Y. Antoine LOGIQUE : APPROCHE SEMANTIQUE • Interprétation Toute application I attribuant une valeur de vérité aux propositions P d’un système logique : I(P) ∈{ ℘,ℑ} • Modèle Une interprétation I est un modèle d’une proposition logique P ssi I(P)=V. On dit que P est satisfaisable. Notation ⊥ ⊥ ⊥ ⊥ T • Tautologie Une proposition logique est dite contradictoire, ou insatisfaisable, si elle n’admet aucun modèle. Une proposition logique P est dite tautologique ssi elle est vraie pour toute interprétation I. • Contradiction • Equivalence Deux propositions logiques A et B sont équivalentes logiquement ssi elles ont la même valeur de vérité pour toute interprétation Notation A ≡ ≡ ≡ ≡B • Sens Sens d’un énoncé logique = valeur de vérité { ℘,ℑ} © J.Y. Antoine LOGIQUE : APPROCHE SEMANTIQUE (2) • Conséquence logique Une proposition logique B est la conséquence logique d’une proposition logique A ssi tout modèle de A est un modèle de B Notation ⊥ ⊥ ⊥ ⊥ A B • Raisonnement valide Un raisonnement est dit valide ssi sa conclusion est la conséquence logique de ses prémisses. Notation ⊥ ⊥ ⊥ ⊥ P1, …, Pn B © J.Y. Antoine EQUIVALENCE ENTRE APPROCHES • Consistance Un système logique est sain (ou consistant) si tout théorème obtenu par démonstration formelle est une conséquence logique des axiomes • Complétude Un système logique est dit complet si, pour tout ensemble de formules du système logique, les conséquences logiques de ces formules peuvent être démontrées comme des théorèmes de ces dernières (i.e. en sont des conséquences formelles). • Système sain et complet Dans un système logique sain et complet, tout théorème est une tautologie et réciproquement Exemple LP et LP1 Contre-exemple théorème d’incomplétude de Gödel © J.Y. Antoine Logique pour l’informatique Chapitre IIa — Logique des Propositions (LP) : modélisation et calcul booléen UFR Sciences et Techniques Licence S&T 2°année © J.Y. Antoine LOGIQUE DES PROPOSITONS - Objectifs 2.1. Notions 2.2. Pratiques 2.1.1. Logique des propositions : que peut-on modéliser avec ? 2.1.2. Syntaxe et formule bien formée (fbf) 2.1.3. Connecteur logique et système complet de connecteurs 2.1.4. Table de vérité 2.1.5. Forme normale (conjonctive, disjonctive) 2.1.6. Fonction booléenne : tableau de Karnaugh 2.2.1. Représenter un énoncé ou un problème en logique des propositions et savoir quand cette logique est insuffisante 2.2.2. Calculer les interprétations d’une fbf de LP à l’aide d’une table de vérité. S’en servir pour montrer des propriétés de tautologie, contradiction, équivalence 2.2.3. Trouver le modèle d’une fbf par intuition ou calcul de ses interprétations 2.2.4. Construire le tableau de Karnaugh associé à une fbf 2.2.5. Mettre une formule sous sa forme normale minimale par des méthodes différentes (formules d’équivalence ou tableau de Karnaugh) 2.2.6 Trouver la formule logique qui réalise une fonction booléenne donnée (Karnaugh) 2.3. Approfondissement 2.3.1. Montrer qu’un système de connecteurs est complet © J.Y. Antoine LP : INTRODUCTION Si le drapeau est vert et si je suis raisonnable alors je ne me baigne pas Je peux me noyer ssi je ne suis pas raisonnable ou je ne sais pas nager Le drapeau est rouge et je me baigne Je risque la noyade • Exemple • Connecteurs logiques Négation Conjonction Disjonction Implication Équivalence     ∧ ∧ ∧ ∧ ∨ ∨ ∨ ∨ ⇒ ⇒ ⇒ ⇒ ⇔ ⇔ ⇔ ⇔ Ne … pas Et Ou Alors Ssi • Atome Jugement de base irréductible : drapeau_vert © J.Y. Antoine LP : SYNTAXE • Vocabulaire • Règles de construction des formules bien formées (fbf) Symboles représentant les atomes : chaînes de caractères Symboles des connecteurs logique : { ∧, ∨, ⇔, ⇒, , ..} Symboles de parenthésage : { ( , ) } • Tout atome P est une fbf de la LP • Si F est une fbf, alors ( F ) est une fbf • Si F est une fbf alors F est une fbf • Si A et B sont deux fbd, alors les formules suivantes sont des fbf : A ∧B, A ∨B, A ⇔B, A ⇒B • Priorités d’application des connecteurs logiques prioritaire sur { ∧, ∨} prioritaire sur { ⇔, ⇒} © J.Y. Antoine CP : CALCUL DES PROPOSITIONS • Compositionnalité de la LP La valeur de vérité d’une fbf de la LP dépend uniquement : - de l’interprétation des atomes qui la composent - de l’emploi des connecteurs logiques entre ces atomes • Tables de vérité V F V V F F F V P Q P ∧ ∧ ∧ ∧Q P ∨ ∨ ∨ ∨Q P ⇔ ⇔ ⇔ ⇔Q P ⇒ ⇒ ⇒ ⇒Q F V F F V V F V F V V F F V V V P    P V F F V • Autres connecteurs : ⊕: Ou exclusif, ↑: Non-Et, ↓: Non-Ou, ... © J.Y. Antoine FORMULES D’EQUIVALENCE DE LA LP Équiv. connecteurs P ⇒Q ≡P ∨Q P ⇔Q ≡(P ⇒Q)∧(Q ⇒P) ≡(P ∧Q)∨(P ∧Q) Double négation P ≡P Lois de Morgan (P ∧Q) ≡P ∨Q (P ∨Q) ≡P ∧Q Idempotence P ∨P ≡P ∧P ≡P Commutativité P ∧Q ≡Q ∧P P ∨Q ≡Q ∨P Associativité (P ∧Q) ∧R ≡P ∧( Q ∧R) ≡P ∧Q ∧R (P ∨Q) ∨R ≡P ∨( Q ∨R) ≡P ∨Q ∨R Contradiction P ∧P ≡Faux Tiers-exclus P ∨P ≡Vrai Distributivité P ∨(Q ∧R) ≡(P ∨Q) ∧(P ∨R) P ∧(Q ∨R) ≡(P ∧Q) ∨(P ∧R) Absorption P ∨(P ∧Q) ≡P P ∧(P ∨Q) ≡P © J.Y. Antoine FORMES NORMALES Système complet de connecteur { , uploads/Philosophie/ logique-pour-l-x27-informatique.pdf