Dm

[moule]

bonjour , jai un devoir à rendre , pourriez vous m'aider pour l'exercice ci-dessous ? merci d'avance :
Soit sigma un ensemble de formules :
1- Supposons que sigma soit satisfaisable. Montrer que pour toute formule A,sigmaU{A} ou sigmaU{non A} est satisfaisable .
2- Soit v une distribution de vérité et sigma l'ensemble des formules telles que v*(A)=1. Montrer quesigma est un ensemble satisfaisable maximal (au sens de l'inclusion ).
3- Tout ensemble satisfaisable peut il s'obtenir ainsi ?
Merci encore pour votre aide :)

[moule]

Bonjour , désolée d'insister mais quelqu'un aurait une réponse svp ? c'est vraiment urgent merci davance !

[Ben314]

Le problème, c'est que, sans les définitions de "satisfaisable", de "distribution de vérité", de "sigmaU", etc...
c'est pas évident...

(et j'ai lourdement la flemme de chercher à quoi ça peut correspondre...)

[moule]

tout d'abord, merci d'avoir répondu et je comprends que tu aies la flemme de chercher . - définition de satisfaisable : " soit F une formule propositionnelle et soir lambda une valuation . On dit que F est satisfaisable s'il existe une valuation lambda telle que lambda=1".
"sigmaU " c'est sigma union ( je ne sais pas comment faire sigma sur le clavier :p)
pour la " distribution de vérité " je ne sais pas si c'est pareil que les tables de vérité .
Merci de ton aide

[wserdx]

J'imagine que les formules sont des expressions booléennes à base de variables et qu'une distribution de vérité donne à chaque variable la valeur vrai ou faux.
Un ensemble de formule est satisfaisable (?) si il existe une distribution de vérité qui donne à chaque formule la valeur vrai. C'est cela?

[moule]

oui voila :)

[Ben314]

En résumé, je trouve que... c'est un sacré charabia pour parler de truc "concon" (l'archétype de ce que j'aime pas quoi...)

1) Si ton ensemble de formule (met toi au MimeTeX...) est "satisfaisable", sauf erreur, ça veut dire qu'il existe des valeurs sur les variables "libres" (i.e. sans quantificateurs) de tes formules telles que toutes les formules prises en ces valeurs là soient vérifiées.
Sauf que, pour ces valeurs là, la proposition A est soit vraie, soit fausse.
Si elle est vrai, quand on la rajoute à , le tout reste "satisfaisable" avec les même valeurs sur les variables libres.
Si elle est fausse, on rajoute la négation de A et c'est pareil...

(c'est curieux cette impression de... parler pour ne rien dire... que j'ai après des raisonnement pareil...)

Pour le 2), ça me semble tout aussi "tarte" : Si je comprend bien, on se donne des valeurs pour les variables libres et on considère toutes les formules qui sont vraies lorsqu'on les prend en ces valeurs là.
Cet ensemble est-il "satisfaisable" : ben oui vu... qu'il est "satisfait" par les condition qu'on s'est donné au départ...
Est il maximal ? Ben évidement oui, vu qu'il n'est satisfait QUE par les condition données au départ (vu que dans la liste des formules "satisfaite", il y en a une qui dit précisément que toutes les variables libres doivent être égales au conditions données) et que, par définition, les formules pas dans c'est celle qui ne sont pas vérifiées avec les conditions de départ.

3) Tu prend un ensemble satisfaisable, des valeurs qui satifaont l'ensemble et tu complète avec toutes les autres formules qui sont vrai en ces valeurs là et ça te montre que l'ensemble de départ est contenu dans un ensemble du type du 2).
Si tu suppose en plus que ton ensemble est maximal, y'a plus le choix, y'a égalité.
Donc tout ensemble satisfaisable MAXIMAL est de cette forme.

[moule]

merci pour tes réponses (et tes petits commentaires entre parentheses:p) .. pouurait tu plus expliquer la question deux stp?

[Ben314]

merci pour tes réponses (et tes petits commentaires entre parentheses:p) .. pouurait tu plus expliquer la question deux stp?

Pour "expliquer plus", il faudrait que je sache quel formalisme utiliser.
LA seule "astuce" de la question 2, c'est de voir que, si tu prend l'ensemble des propositions vrai pour des valeurs fixées d'avance des paramètres, alors il n'y a QUE avec ces paramètres là que toute les propositions seront vraies et ça découle du fait que les "briques élémentaires" avec lesquelles tu fabrique les formules doivent contenir des truc du style "tel paramètre doit être égal à ça".

[moule]

merci pour toutes ces explications, je vais tacher de me débrouiller avec ca :)

[Ben314]

Après, mes remarques ironiques, elles sont là pour bien te faire comprendre que, pour le moment, ça consiste à "remuer du vent" ce genre de truc.

Je pense (j'espère...) qu'en avançant dans le cours ça va devenir plus "consistant"...

[moule]

Bonsoir , j'aurai egalement un autre exo .. si tu peux m'aider et que tu trouves ca plus " consistant" :)
L'énoncé est le suivant:
Soient les deux langages suivants sur l'alphabet sigma ={a,b}( jai pas réussi à faire le signe ) :
L={a^rb^r ;r,s>0}et L'{a^nb^n ;n>0}
C'est-à-dire deux langages qui sont formés de mots commençant par a et se terminant par b, avec une contrainte supplémentaire dans L': le nombre de a est égal au nombre de b .
a) Trouver une grammaire G réguliere qui engendre L.
b) Trouver une grammaire hors-contexte qui engendre L' .
c) Trouver, lorsque c'est possible un automate fini qui engendre le langage considéré (LouL')
Merci de ton aide .

[Ben314]

Bon, c'est encore bourré de vocabulaire "technique" ton truc...
Je regarde si je trouve ce que ça veut dire traduit "en clair" (pour moi... :marteau:)

Remarque : ton L, il est pas clair du tout : je suppose que c'est a^rb^s vu la remarque bien utile en dessous.

Si j'ai bien compris le truc que j'ai lu, on te demande comment générer les mots de L et de L' à l'aide de "formules récursives".

Dans le cas de L, je pense que ce qu'il faut dire, c'est que le "truc de base", c'est ab (vu qu'on impose r et s strictement positifs) puis que les "règles", c'est X->aX et X->Xb (on peut ajouter des a à gauche et ajouter des b à droite)

Pour L', on pert aussi comme "base" de ab (car n doit être strictement positif) et la seule rêgle, c'est X->aXb (ajout d'un a à gauche ET d'un b à droite)

[moule]

je ne sais pas ce qui est pas clair.. apres le vocabulaire je n' ai pas de signification exacte , c'est pour cela que je n'arrive pas à le faire je pense

[Ben314]

Raté (le post au dessus) : c'est pas comme ça que ça marche le chmilblick entre les "variables" et les "lettres terminales"...

Donc pour L, une seule variable X (qui est donc l'axiome), et 3 règles X->aX ; X->Xb et X->ab

Pour L', une seule variable X, et 2 règles X->aXb et X->ab

SAUF QUE (je viens de chercher quoi ça voulait dire "régulière"... :hein:) la grammaire çi dessus pour L, elle est pas régulière...

Donc pour L : deux variable X(=axiome) et Y ; 4 règles X->aX ; X->aY ; Y->bY ; Y->b

[moule]

merci , mais tu pourrais plus détailler chaque question stp, si cela ne te dérange pas ? merci d'avance

[Ben314]

Je viens de regarder ces deux trucs et... tout ce que je sais est dedans...
http://fr.wikipedia.org/wiki/Grammaire_non_contextuelle
http://fr.wikipedia.org/wiki/Grammaire_r%C3%A9guli%C3%A8re

Le principe, par exemple pour L avec :
2 variables X(=axiome), Y et 4 règles X->aX ; X->aY ; Y->bY ; Y->b

Tu part de l'axiome donc de X içi puis tu as le droit "d'enquiller" autant de fois les règles tant qu'il reste au moins une variable dans l'expression considérée et c'est fini lorsqu'il n'y a plus de variables mais que des "symboles terminaux" (i.e. des 'a' et des 'b' ici, mais plus de 'X' ou de 'Y'.

Donc là, tu part de X tu va "appliquer" un certain nombre de fois la première règle (éventuellement zéro fois) et ça va te donner du a^kX avec k>=0 (tu peut pas appliquer une des deux dernière vu que tu as pas de Y dans ton expression).
A un moment donné, tu applique la règle 2 et tu te retrouve avec du a^kY ou k>=1 (vu que la règle 2 ajoute encore un a)
La tu applique un certain nombre de fois (éventuellement nul) la troisième règle et ça te fait du a^kb^jY où j>=0
Et tu termine en appliquant la 4em règle qui te donne du a^kb^j avec j>=1 (vu que la règle ajoute un 'b')
C'est fini : tu as plus de variables et tu pouvait rien faire d'autre que cette suite "d'opérations" donc tu as "produit" tout les a^kb^j avec k et j >=1 et tu n'a "produit" rien d'autre.

Enfin, le truc en question est bien une grammaire "régulière" du fait qu'on a toujours ajouté des truc du même coté de la variable (et il semble assez clair qu'il n'y a pas de grammaire "régulière" pour engendrer L')

[Jtaicapte]

bonjour , jai un devoir à rendre , pourriez vous m'aider pour l'exercice ci-dessous ? merci d'avance :
Soit sigma un ensemble de formules :
1- Supposons que sigma soit satisfaisable. Montrer que pour toute formule A,sigmaU{A} ou sigmaU{non A} est satisfaisable .
2- Soit v une distribution de vérité et sigma l'ensemble des formules telles que v*(A)=1. Montrer quesigma est un ensemble satisfaisable maximal (au sens de l'inclusion ).
3- Tout ensemble satisfaisable peut il s'obtenir ainsi ?
Merci encore pour votre aide

Dis moi, Moule, tu serais pas en L2 MASS par hasard ? J'ai le même DM a faire . . .