probleme SAT et calcul des prédicats et calcul des propositions
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

probleme SAT et calcul des prédicats et calcul des propositions



  1. #1
    youhouhou

    probleme SAT et calcul des prédicats et calcul des propositions


    ------

    bonjour,

    je ne comprends pas très bien comment on peut exprimer simplement un problème SAT et sa solution en calcul des prédicats ou en calcul des propositions.

    en calcul des prédicats : un problème SAT c'est donc une écriture très concise du théorème mais pour la preuve normalement on ne devrait faire que des déductions et on ne peut pas écrire simplement qu'on a trouvé une solution :

    et en calcul des propositions on peut très bien écrire la solution mais pour exprimer le problème on devra écrire pour chaque valeurs possibles pour les

    ce n'est pas étrange comment façon de présenter la logique ?

    -----

  2. #2
    Médiat

    Re : probleme SAT et calcul des prédicats et calcul des propositions

    Bonjour,

    Je ne suis pas sûr de comprendre, votre problème :
    1. Le problème SAT, à ma connaissance est un problème qui dépend de la valeur de vérité de variables booléennes, donc la valeur 11 ici n'a pas de sens (faute de frappe ?).
    2. Bien sûr que pour prouver une formule existentielle, un exemple suffit, où est le problème (si vous trouvez une autre méthode convaincante, personne ne vous le reprochera (comme l'algorithme de Tarjan pour le cas n = 2)) ?
    Dernière modification par Médiat ; 23/06/2015 à 18h40.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    youhouhou

    Re : probleme SAT et calcul des prédicats et calcul des propositions

    vraiment désolé, je pensais ne pas ouvrir le post finalement mais le message s'est envoyé tout seul !

    SAT est juste un exemple, mais qui est intéressant.

    - en calcul des propositions exprimer un problème SAT demande d'écrire clauses (*), par contre écrire la solution si en a trouvée une est direct : (vrai,vrai,faux,vrai,faux,faux ....)


    - alors qu'en calcul des prédicat on pourra écrire directement pour exprimer un problème SAT, mais pour la preuve, on pourra faire des déductions formelles à partir de fonctions plus simples, d'accord, mais comment exprime-t-on qu'on a juste trouvé une solution x1=vrai, x2=faux, etc. ??


    et donc en gros la question c'est comment fait-on du calcul des prédicats typé (où on précise les ensembles auxquelles appartiennent les variables quantifiées) ?

    (*) normalement pour exprimer un problème SAT en calcul des propositions il faudrait écrire (après avoir défini la fonction f bien sûr) :
    (faux,faux,faux,....) ou (vrai,faux,faux,....) ou (faux,vrai,faux,....) ou [...]
    Dernière modification par youhouhou ; 23/06/2015 à 22h45.

Discussions similaires

  1. Réponses: 2
    Dernier message: 03/01/2015, 14h40
  2. le théorème de calcul des prédicats
    Par nagato dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 08/04/2012, 17h30
  3. Aide pour calcul svp (calcul de progression ? comment on doit-dire ?)
    Par Myr dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 07/03/2012, 20h53
  4. Calcul predicats .
    Par invite6ad6c917 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 18/01/2009, 17h41
  5. Calcul 3, intégrale triples pour le calcul du volume.
    Par invitebfdf3e04 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 06/12/2008, 08h19