Groupe d’études et de recherche en analyse des décisions

G-93-24

Le problème de la satisfaisabilité probabiliste et ses extensions

, , et

Le problème de la satisfaisabilité probabiliste (PSAT) consiste à déterminer, étant donné les probabilités de m événements (ou propositions logiques) définis à partir de n variables logiques, des bornes les meilleures possibles sur la probabilité d'un m + 1ième événement défini à partir des mêmes variables. Dans cet article de synthèse, on présente les principaux résultats obtenus en ce qui concerne: (i) la résolution analytique de PSAT; (ii) la résolution numérique de PSAT; (iii) la complexité de PSAT; (iv) un modèle dérivé de PSAT conduisant à des inégalités probabilistes généralisant les formules de Bonferroni; (v) le problème IPSAT, extension de PSAT, dans lequel on considère des intervalles de probabilité pour des événements plutôt que des valeurs ponctuelles; (vi) le problème CONDSAT dans lequel certaines probabilités sont conditionnelles; (vii) les problèmes RSAT et MAXPSAT qui consistent à déterminer les modifications minimales (extension d'intervalles de probabilités, suppression de propositions) à apporter à un problème PSAT non satisfaisable pour le rendre satisfaisable; (viii) la logique bayesienne, synthèse des réseaux bayesiens classiques et de la logique probabiliste; (ix) l'application de PSAT en intelligence artificielle et en fiabilité.

, 32 pages

Ce cahier a été révisé en août 1994