Dans cet article, nous proposons de calculer un ensemble de formulesbooléennes partiellement définies qui correspond à la recherche de caractérisations de groupes de vecteurs booléens selon un ensemble de caractères (variables). Ce problème peut être utile pour de nombreuses applications pratiques où les données sont des résultats expérimentaux de tests de présence/absence. Ce problème a été largement étudié, mais généralement dans un cas plus limité, car ici nous avons à calculer simultanément un ensemble complet de formules de caractérisation minimale. Nous proposons donc deux approches différentes qui nous permettent d’étudier la satisfiabilité et la complexité sous-jacente de ce problème. Afin de mettre en évidence l’applicabilité de notre travail, nous fournissons aussi des résultats expérimentaux que nous avons obtenus à partir de données biologiques.