notions de logique

Cours de bases de données,http://sql.bdpedia.frQuelques notions de logique1Philippe RigauxNotions élémentaires de logique formelleCette session présente les notions essentielles de logique formelle à connaître :Le calcul propositionnel : valeurs de vérité et formulesLes prédicatsCollections et quantificateursImportance pour les bases de données et SQLCes diapositives correspondent au support en ligne disponiblesur le sitehttp://sql.bdpedia.fr/2Calcul propositionnelProposition: énoncé auquel on p eutaffecter deux valeurs de vérité, V raiou F aux.Formule: exp ressionbasée sur des p ropositionset leur combinaison pa rdes connecteurs logiques.la conjonction, notée^la disjonction, notée_la négation, notée:Exemple :(p^q)_r3Valeur de vérité d"une formuleInduite à partir de valeurs de vérité des propositions, et des règles suivantes :pqp^qp_q:pVraiVraiVraiVraiFauxVraiFauxFauxVraiFauxFauxVraiFauxVraiVraiFauxFauxFauxFauxVraiExemple :(p^q)_rest Vrai pour les valeurs V, V, F dep;q;r4EquivalencesUn informaticien averti sait manier avec agilité les équivalences.

Quelques exemples.: (:F)est équivalente àFF_(F1^F2)est équivalente à(F_F1)^(F_F2)(distribution)F^(F1_F2)est équivalente à(F^F1)_(F^F2)(distribution): (F1^F2)est équivalente à(:F1)_(:F2)(loi DeMorgan): (F1_F2)est équivalente à(:F1)^(:F2)(loi DeMorgan)Doncp_ :(p^ :q)est unetautologie .

5) PrédicatsExtension puissante des propositions :construire des énoncés sur des "objets" .Le prédicatCompose(X;Y)permet de construire des énoncés de la forme :Compose("Mozart";"Don Giovanni")Compose("Debussy";"La mer")Etc.Ce sont des nuplets (ou des atômes, ou des faits).Il en existe une infinitéUncontexte (ou "interp rétation")définit ceux qui sont vrais / faux.

Remarque: Base de données?C"est un contexte donnant un ensemble fini de faits vrais.Tous les autres sont considérés comme faux.

6) Nuplets ouverts et fermésUn nuplet énoncé avec des constantes est un nupletfermé .Compose("Mozart";"Don Giovanni")Un nuplet énoncé avec au moins une variable est un nupletouvert .Compose(X;"Don Giovanni")Un nuplet ouvert désigne une infinité de faits possibles.Remarque: Interêt?En général on s"intéresse aux valeurs deXpour lesquelles lesfaits sont vrais.On a effectué une requête .

7) Collections et quantificateursLes nuplets libres expriment des contraintes sur un fait.On peut exprimer des contraintes sur des collections de faits avec les quantificateurs.9 xP(x)est vraie s"il existeau moins une affectation de xpour laquelleP(x)estvraie.8 xP(x)est vraie siP(x)est vraie pourtoutes les valeurs de x.Variables libres et liées: un va riablequantifiée est li bre;sinon elle est liée.

8) SQL = formules logiqueRequête SQL= une fo rmuleavec des va riableslib res.Résultat d"une requête= les valeurs des va riableslib resqui satisfont la fo rmule.La formuleCompose(X;"Don Giovanni")s"écrit en SQLselectcomposite urfromCompose whereoeuvre= "Don Giovanni"SQL c"est une syntaxe pour écrire des formules.Remarque: DéclarativitéOn ne dit pas comment on calcule!9ExemplesDeux relations/prédicats :Expert (id_expert, nom)Manuscrit (id_manuscrit, auteur, titre, id_expert, commentaire)Manuscrit(_;"Proust";t;x;_)^Expert(x;n)selecttitre, nom from Expert, Manuscrit whereExpert.id_ex pert= Manuscrit.id_expert andauteur = "Proust" Expert(x;n)^ 9Manuscrit(_;"Proust";_;x;_)selectnom fro mExpert as e whereexists ( select* from Manuscri tas m wheree.id_exper t= m.id_expert andauteur = "Proust" )10À retenirSQL est un langagedécla ratifqui exp rimepa rune fo rmulelogique les p ropriétésdu résultat à construire.Avantages prouvés et éprouvés depuis les années 1970.signification précise, non ambiguealgorithmes efficaceslangage robuste, universellement connu et adopté,no rmalisédéclarativité: SQL ne donne aucune indication sur la manière dont le système doit trouver le résultat.11