En informatique, les logiques formelles ont une place centrale dans la représentation et le traitement des connaissances. Elles sont utilisées pour la modélisation et la vérification de systèmes informatiques et de leurs propriétés ainsi que pour la formalisation de différents types de raisonnement. Dans ce contexte il existe un large spectre de logiques non-classiques parmi lesquelles les logiques modales jouent un rôle important. Alors que les logiques modales classiques ont été largement étudiées, nous nous focalisons dans cette thèse sur les logiques modales intuitionnistes et aussi hybrides floues en abordant un certain nombre de questions principalement du point de vue de la théorie de la démonstration. Nous proposons pour ces logiques de nouveaux systèmes de preuve, notamment suivant les formalismes de déduction naturelle et de calcul des séquents, qui sont fondés sur de nouvelles structures multi-contextuelles généralisant la structure standard de séquent / In computer science, formal logics are central for studying the representation and the treatment of knowledge. Indeed, they are widely used for modeling and verifying computer systems and their properties and also for formalizing different kinds of reasoning. In this context there exist many non-classical logics and among them modal logics play a key role. As classical modal logics have been deeply studied, we focus in this thesis on the intuitionistic modal logics and also on fuzzy hybrid logics by studying some important questions mainly from the viewpoint of proof theory . We define for these logics new proof systems, following natural deduction and sequent calculus formalisms, that are based on new multi-contextual structures generalizing the standard sequent structure

Les logiques modales sont des logiques permettant la représentation et l'inférence de connaissances. La logique hybride est une extension de la logique modale de base contenant des nominaux, permettant de faire référence à un unique individu ou monde du modèle. Dans cette thèse nous présentons plusieurs algorithmes de tableaux pour logiques hybrides expressives. Nous présentons aussi une implémentation de ces calculs, et nous décrivons les tests de correction et de performance que nous avons effectués, ainsi que les outils les permettant. De plus, nous étudions en détail une famille particulière de logiques liée aux logiques hybrides : les logiques avec opérateurs de comptage. Nous étudions la complexité et la décidabilité de certains de ces langages / Modal logics are logics enabling representing and inferring knowledge. Hybrid logic is an extension of the basic modal logic that contains nominals which enable to refer to a single individual or world of the model. In this thesis, we present several tableaux-based algorithms for expressive hybrid logics. We also present an implementation of these calculi and we describe correctness and performance tests we carried out, and the tools that enable these. Moreover, we study a particular family of logics related to hybrid logics: logics with counting operators.We investigate previous results, and study the complexity and decidability of certain of these languages

Cette thèse propose et étudie de nouveaux systèmes déductifs mêlant calculs et déductions. La déduction modulo est un premier formalisme qui traduit un pouvoir calculatoire grâce à un système de réécriture. Nous présentons un paradigme dual appelé superdéduction qui traduit un pouvoir déductif par de nouvelles inférences. Ces pouvoirs calculatoires et déductifs modifient la représentation des preuves et leur interaction par les processus d'élimination des coupures. La normalisation forte ou l'admissibilité des coupures ne sont plus garanties et apparaissent alors comme des propriétés intrinsèques des théories représentées sous forme de systèmes de réécriture. Nous démontrons que certains critères permettent d'assurer ces propriétés, notamment en définissant un langage de termes de preuve pour la superdéduction et en étudiant la permutabilité des inférences en calcul des séquents classique. Notre attention est focalisée sur les calculs des séquents classiques et la représentation des preuves dans de tels systèmes. D'autres formalismes connexes sont envisagés, notamment les réseaux de preuve et le focusing. Nous comparons cette dernière approche à la superdéduction, ce qui nous amène à proposer une refonte du paradigme de superdéduction basée sur un système de multifocusing pour la logique classique. Nous en montrons les effets bénéfiques en démontrant la complétude des systèmes déductifs obtenus. / In this thesis we propose and study several deduction systems that mix deduction and computation. Deduction modulo proposes to translate a computational power through a rewriting system. We present the dual concept called superdeduction. It translates a deductive power into custom inference rules that enrich the deduction system. These computational and deductive powers modify the representation of proofs as well as their interaction through cut-elimination processes. Strong normalisation or cut-admissibility may be lost and therefore appear as intrinsic properties of theories represented as rewriting systems. We prove that certain criteria imply these properties by defining a proof-term language for superdeduction and by studying the permutability of inferences in classical sequent calculus. Our attention is focused on classical sequent calculi and on the representation of proofs in such systems. Other related paradigms are considered, namely proof-nets and focusing. We compare this latter approach with superdeduction. We consequently reforge the superdeduction paradigm on top of a multifocusing system for classical logic. We demonstrate the benefits of this approach by proving the completeness of the obtained deduction systems.

L’approche probabiliste du raisonnement émet l’hypothèse que la plupart des raisonnements, aussi bien dans la vie quotidienne qu’en science, se réalisent dans des contextes d’incertitude. Les concepts déductifs centraux de la logique classique, consistance et validité, peuvent être généralisés afin d’englober des degrés de croyance incertains. La consistance binaire peut être généralisée à travers la dénomination de cohérence, lorsque les jugements de probabilité à deux affirmations sont cohérents seulement s’ils respectent les axiomes de la théorie de la probabilité. La validité binaire peut se généraliser comme validité probabiliste (validité-p), lorsqu’une interférence est valide-p seulement si l’incertitude de sa conclusion ne peut être de façon cohérente plus grande que la somme des incertitudes de ses prémisses. Cependant le fait que cette généralisation soit possible dans une logique formelle n’implique pas le fait que les gens utilisent la déduction de manière probabiliste. Le rôle de la déduction dans le raisonnement à partir de prémisses incertaines a été étudié à travers dix expériences et 23 inférences de complexités différentes. Les résultats mettent en évidence le fait que la cohérence et la validité-p ne sont pas juste des formalismes abstraits, mais que les gens vont suivre les contraintes normatives établies par eux dans leur raisonnement. Que les prémisses soient certaines ou incertaines n’a pas créé de différence qualitative, mais la certitude pourrait être interprétée comme l’aboutissement d’une échelle commune de degrés de croyance. Les observations sont la preuve de la pertinence descriptive de la cohérence et de la validité-p comme principes de niveau de calcul pour le raisonnement. Ils ont des implications pour l’interprétation d’observations antérieures sur les rôles de la déduction et des degrés de croyance. Enfin, ils offrent une perspective pour générer de nouvelles hypothèses de recherche quant à l’interface entre raisonnement déductif et inductif. / The probabilistic approach to reasoning hypothesizes that most reasoning, both in everyday life and in science, takes place in contexts of uncertainty. The central deductive concepts of classical logic, consistency and validity, can be generalised to cover uncertain degrees of belief. Binary consistency can be generalised to coherence, where the probability judgments for two statements are coherent if and only if they respect the axioms of probability theory. Binary validity can be generalised to probabilistic validity (p-validity), where an inference is p-valid if and only if the uncertainty of its conclusion cannot be coherently greater than the sum of the uncertainties of its premises. But the fact that this generalisation is possible in formal logic does not imply that people will use deduction in a probabilistic way. The role of deduction in reasoning from uncertain premises was investigated across ten experiments and 23 inferences of differing complexity. The results provide evidence that coherence and p-validity are not just abstract formalisms, but that people follow the normative constraints set by them in their reasoning. It made no qualitative difference whether the premises were certain or uncertain, but certainty could be interpreted as the endpoint of a common scale for degrees of belief. The findings are evidence for the descriptive adequacy of coherence and p-validity as computational level principles for reasoning. They have implications for the interpretation of past findings on the roles of deduction and degrees of belief. And they offer a perspective for generating new research hypotheses in the interface between deductive and inductive reasoning.

Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux. / In this thesis, we consider problems at the intersection of two areas: databases and knowledge bases. We focus on two equivalent problems on conjunctive queries with negation : query containment and query answering with boolean queries while making the open-world assumption. We reformulate these problems as a problem of deduction in a first order logic fragment. Then we refine existing algorithm schemes and propose new algorithms. To study and compare them experimentally, we propose a random generator and we analyze the influence of parameters on problem instances difficulty. Finally, we analyse the contributions of the different refinements and we compare experimentally the algorithms.

Le premier objectif de cette thèse consistait à tester l’existence de stratégies de raisonnements dans l’estimation de la probabilité diagnostique : P(cause|effet). A travers quatre expériences, nous montrons que l’estimation de cette probabilitépeut se réaliser selon deux voies formellement distinctes. La première consiste à évaluer P(cause|effet) à travers une forme de déduction affaiblie fondée sur un Modus Ponens rétractable (EFFET ; si EFFET alors il est probable que CAUSE ) il est probable que CAUSE). La seconde stratégie consiste à estimer la probabilité diagnostique à travers un raisonnement abductif qui correspond au schéma d’Affirmation du Conséquent probabilisé (EFFET ; si CAUSE alors il est probable que EFFET ) il est probable que CAUSE). Nous montrons que le choix de la stratégie est dépendant de la probabilité prédictive P(effet|cause) empirique présente dans les données. Quand cette probabilité est faible, les participants marquent une préférence pour la stratégie de type déduction rétractable, en revanche cette stratégie est fortement concurrencée par la stratégie abductive quand P(effet|cause) est haute. Le second objectif de cette recherche consistait à vérifier si les estimations des individus sous stratégie abductive d’une part, et sous stratégie d’estimation par Modus Ponens rétractable d’autre part, reflétaient fidèlement la probabilité diagnostique empirique. Les résultats d’une cinquième expérience infirment cette hypothèse. Quelle que soit la stratégie suivie, la probabilité diagnostique est systématiquement sous-estimée par les individus. Nos résultats indiquent toutefois que la stratégie par déduction rétractable permet d’aboutir à des estimations plus proches de la probabilité empirique. / The first goal of this thesis was to test the existence of reasoning strategies in the diagnostic probability estimate : P(cause|effect). Using four experiments, we show that the estimation of this probability can be achieved according to two formally distinct ways. The first consists in assessing P(cause|effect) through a weakened form of deduction based on a retractable Modus Ponens (EFFECT; if EFFECT then it is likely that CAUSE ) it is likely that CAUSE). The second strategy consists in estimating the diagnostic probability through abductive reasoning corresponding to the Affirmation of the Consequent probability scheme (EFFECT ; if CAUSE then it is likely that EFFECT ) it is likely that CAUSE). We show that the choice of strategy is dependent on the empirical predictive probability P(effect|cause) in the data. When this probability is low,participants show a preference for the retractable deduction strategy; On the other hand this strategy is strongly challenged by the abductive strategy when P(effect|cause) is high. The second objective of this research was to verify whether the estimates of people under abductive strategy on the one hand, and under defeasible Modus Ponens strategy on the other hand, accurately reflected the empirical diagnostic probability. The results of a fifth experiment invalidate this hypothesis. Regardless of the strategy followed, the diagnostic probability is systematically underestimated by people. Our results indicate, however, that the retractable deduction strategy provides estimates which come closer to the empirical probability

Si l'éthique n'est pas illusoire, comment comprendre son efficience ? La question nécessite d'identifier des complexes objectifs de sens et d'action. Il s'agit en effet de se placer du côté du corps pour ne plus verser dans l'éternel débat idéologique qui, précisément, élude la question. Un travail empirique s'impose, que nous engageons dans un championnat départemental de tennis de table. Nous ne pouvons au demeurant mettre en relation sens et actions sans penser le plan sur lequel les apposer. La comparaison naïve conduit en effet à rabattre inconsciemment les éléments actionnels sur l'unique plan de la représentation. D'où la nécessaire induction d'un plan d'apposition à partir de la fréquentation méthodique du terrain. Cette construction ne peut se faire aux dépends des acteurs, sources du sens éthique et des actions effectives, mais doit être conforme à une épistémologie de la complexité et de l'immanence. Au terme d'une démarche graduelle qui vise la connexion de la posture et du terrain, nous déterminons ainsi le « jeu » comme plan d'apposition. « Jouer le jeu », c'est réaliser un bien dans et par des actions sportives. En en identifiant les déclinaisons, nous élaborons des complexes de sens et d'action. Ceux-ci sont déduits selon un principe généalogique à partir des données déjà collectées. Après leur analyse méthodique, nous sommes en mesure de faire une description détaillée du processus d'efficience qui a cours dans un échange type. Nous défendons par là l'idée que l'éthique adjoint au déséquilibre, coeur inconscient du mouvement et dimension physiologique de la motivation, une nuance qui lui assure perduration dans un monde de l'équilibre institué.

Cette thèse se divise en trois parties. Dans l'introduction, nous rappelons d'abord les problèmes et les motivations philosophiques a l'origine de l'étude des logiques polyvalentes. Nous élaborons une methode qui permet d'obtenir mécaniquement a partir de la définition matricielle d'une logique, des règles d'inférence pour les connecteurs propositionnels d'un calcul des tableaux. Un traitement similaire est fait pour les règles d'inférence pour les quantificateurs. Le raffinement étudie alors est une skolemisation paresseuse. Elle permet l'utilisation de l'unification pour calculer les instances utiles a la construction d'un tableau ferme. Une implémentation dans atinf les concrétise. Nous proposons les logiques polyvalentes avec égalité graduelle, un calcul par resolution-paramodulation ordonnées. La première partie finit par une extension qui consiste a munir les valeurs de vérité de structures de treillis ou de treillis bi-dimensionnels. Au traitement systématique des logiques finies suit une étude de deux cas typiques de logiques polyvalentes infinies du premier ordre une étude systématique étant théoriquement impossible : les logiques de post et de Ukasiewicz. Le lien entre les logiques de Horn et les logiques de post est utilise, pour proposer une automatisation des logiques de post basée sur une sémantique des mondes possibles. A partir de cette sémantique nous définissons un calcul des tableaux préfixes. Afin d'augmenter l'efficacité, des contraintes, résolues en temps polynomial sur les préfixes sont introduites. Chaque développement inclut une étude bibliographique très documentée du domaine de la logique mathématique, de l'intelligence artificielle et de la déduction automatique

Le calcul de réécriture est un lambda-calcul avec filtrage. Cette thèse est consacrée à l'étude de systèmes de types pour ce calcul et à son utilisation dans le domaine de la déduction.<br /><br />Nous étudions deux paradigmes de typage. Le premier est inspiré du lambda-calcul simplement typé, mais un terme peut y être typé sans être terminant. Nous l'utilisons donc pour représenter des programmes et des systèmes de réécriture. La seconde famille de systèmes de types que nous étudions est adaptée des Pure Type Systems. Nous en démontrons la normalisation forte grâce à une traduction vers le lambda-calcul typé.<br /><br />Enfin nous proposons deux approches pour l'utilisation du calcul de réécriture en logique. La première consiste à définir des termes de preuve pour la déduction modulo à l'aide des systèmes fortement normalisants. Dans la seconde, nous définissons une généralisation de la déduction naturelle et nous montrons que le filtrage est utile pour représenter les règles de ce système de déduction.

Cette thèse propose et étudie de nouveaux systèmes déductifs mêlant calculs et déductions. La déduction modulo est un premier formalisme qui traduit un pouvoir calculatoire grâce à un système de réécriture. Nous présentons un paradigme dual appelé superdéduction qui traduit un pouvoir déductif par de nouvelles inférences. Ces pouvoirs calculatoires et déductifs modifient la représentation des preuves et leur interaction par les processus d'élimination des coupures. La normalisation forte ou l'admissibilité des coupures ne sont plus garanties et apparaissent alors comme des propriétés intrinsèques des théories représentées sous forme de systèmes de réécriture. Nous démontrons que certains critères permeent d'assurer ces propriétés, notamment en définissant un langage de termes de preuve pour la superdéduction et en étudiant la permutabilité des inférences en calcul des séquents classique. Notre attention est focalisée sur les calculs des séquents classiques et la représentation des preuves dans de tels systèmes. D'autres formalismes connexes sont envisagés, notamment les réseaux de preuve et le focusing. Nous comparons cette dernière approe à la superdéduction, ce qui nous amène à proposer une refonte du paradigme de superdéduction basée sur un système de multifocusing pour la logique classique. Nous en montrons les effets bénéfiques en démontrant la complétude des systèmes déductifs obtenus.