Previous Up Next
Eléments de logique pour l’informatique 2019–20                  http://www.lri.fr/~paulin/Logique


Introduction

Motivations

La logique, chemin vers la vérité

Logique vient du grec logos (raison, langage, raisonnement). Le raisonnement est un cheminement (une déduction) qui permet à partir d’hypothèses, de construire de nouvelles propriétés. On est convaincu que si les hypothèses sont vraies alors les propriétés que l’on a déduites sont aussi vraies.

Exemple

Tous les hommes sont mortels
or Socrate est un homme
donc Socrate est mortel.

La logique énonce des règles qui permettent de se convaincre de la vérité d’une argumentation ou au contraire de la réfuter:

Exemple

Tous les hommes sont mortels
or l’âne Francis n’est pas un homme
donc l’âne Francis est immortel.

La logique étudie des règles du jeu qui permettent de construire des raisonnements logiques. On se pose des questions comme:

Chaos de la logique

L’extrait suivant est extrait du livre Rhinoceros, d’Eugène Ionesco. C’est un dialogue entre un Logicien et un Vieux Monsieur, qui sous couvert de raisonnement logique énonce, des absurdités.

Une approche fondatrice pour les mathématiques

Le questionnement sur les fondements des mathématiques date du début du 20ème siècle avec la théorie des ensembles, Hilbert, Gödel …  et quelques surprises comme le paradoxe de Russell et le théorème d’incomplétude de Gödel.

Meta-mathématique

En logique mathématique, le raisonnement est l’objet de l’étude comme les nombres en algèbre, les fonctions en analyse, les espaces vectoriels …

Les objets de base sont les énoncés mathématiques, les raisonnements …
On raisonne sur ces objets, on établit des théorèmes : il y a deux niveaux différents qu’il ne faut pas confondre. Mais c’est aussi le cas en informatique où on écrit parfois des programmes qui manipulent d’autres programmes (les compilateurs).

Logique et informatique

Il existe des liens très étroits entre logique et informatique dont voici quelques illustrations :

Programme

Objectifs

L’objectif du cours est de se familiariser avec un formalisme logique, la notion de terme, de formule, de démonstration, de validité, le lien entre syntaxe et sémantique. Ce cours met en pratique un minimum d’objets mathématiques utilisés en informatique tels que la récurrence structurelle et les définitions par système d’inférence.

Plan

  1. Introduction au langage logique
  2. Calcul propositionnel
  3. Calcul des prédicats

Previous Up Next