Calcul propositionnel !

[vienin]

bonjour a tous,

Voila je suis en License 3 Info et j'ai un prof qui a pour abitude de nous laisser finir les exos chez nous, soit, mais il yen a un que je n'arive pas a finir et le controle est Jeudi, soit dans 1 jour et demi. Si vous pouviez m'aider sa serait cool.

enoncé :

On dit qu'un ensemble Q de formule est independant ssi pour toute formule F aparateant a Q, F n'est pas consequence semantique de Q-{F}.

a) l'ensemble suivant {A,B,(A->C),(C->B)} est t'il independant ?

Ici on demontre que non car {A,B,(A->C)} est consequence semantique de (C->B) acr pour A=1, B=1, (A->C)=1 on a forcement (C->B)=1.


Mais je bloque sur ces deux question qui m'ont l'air plus theorique :

b) l'ensemble vide est-il independant ? Donner une condition suffisante et necessaire pour qu'un ensemble contenant uen unique formule soit independant.

c) montrer que tout ensemble fini admet au moins un sous ensemble indépendant équivalent.


Merci de votre aide !

[vienin]

Personne n'a le moindre idee ?!

[Anonyme]

Personne n'a le moindre idee ?!

Je n'ai pas fait de sémantique, mais j'ai mon petit background en maths...

Alors il me semble que :
- pour l'ensemble vide, la réponse
est qu'il est indépendant car toute formule de l'ensemble vide vérifie
n'importe quelle propriété, en particulier celle de ne pas être conséquence
sémantique de Q-{F}.

- pour qu'un ensemble contenant une unique formule
soit indépendant, il faut et il suffit que cette formule ne soit pas une
tautologie

- dans un ensemble fini de formule, on prend "une partie génératrice
minimale" autrement dit un sous-ensemble minimal (en terme de cardinalité)
Q' tel que toute formule de Q-Q' soit conséquence de Q'. Alors
il est facile de vérifier que Q' est lui-même indépendant
et qu'il est équivalent à Q.

J'espère ne pas être à côté de la plaque.

dSP