Problème d'induction structurelle

[CotteB]

Bonjour,

Etant en licence 1 de physique, j'ai décidé de prendre des cours de maths en suppléments (notre licence flexible nous le permets) et je suis donc dans un cours nommé "Ensemble 1" ou on travaille sur la théorie des ensemble.
Si j'arrive à comprendre une bonne partie du cours et faire les exercices seuls, sur certains sujets je ne comprend même pas la correction.

notamment sur l'induction structurelle:

J'ai donc besoin de votre aide pour un exercice non corrigé, dont voici l'intitulé:
"Soit ϕ ∈ F formé avec ∧ ∨ ¬. Il existe une fonction équivalent Ψ formé de ¬ ∨ uniquement tel que |Ψ| ⩽ 2|ϕ|".

Je connais ma définition du calcul propositionnel (je pourrais vous montrer celle de mon cours si jamais) et je sais que p∧q <=> ¬(¬p∨¬q)

Que faire maintenant ? Je suis complètement perdu, je n'arrive pas à utiliser cette définition.

Merci pour votre aide,

Cordialement,
-----

[Resartus]

Bonjour,
Pouvez-vous préciser ce que votre cours (ou votre TD) définit comme |f| ?
Sans doute est-ce lié au nombre de connecteurs de la formule mais comment?

[CotteB]

Désolé, je me rend compte que je ne répond pas à votre question (désolé pour le double post, mais je ne peux pas supprimer mon message est-ce qu'un admin peut le faire ?).

Concernant la notation |f|, je n'ai trouvé nulle part dans mon cours ou dans les exemple, cette notation. Mais je suppose effectivement qu'il s'agit du nombre de connecteurs, car cela rendrais l'énoncé plus logique.
Cependant je reste perplexe, car si 2|ϕ| = 2 |p∧q| = 2, on a |Ψ| = |¬(¬p∨¬q)| = 6 > 2|ϕ|

Merci,

[Médiat]

Essayez avec |f| = nombre de symboles (variables incluses)

[A voir en vidéo sur Futura]

[CotteB]

Cela marche si on ne compte pas les parenthèses.
J'ai des partiels demain mais j'essaierai d'écrire une réponse et de la poster dans la semaine.

Merci pour vos contributions.

[CotteB]

Pour les intéressé si jamais, voici une solution:

Avant tout pour simplifié la réponse, on changera le nom des variables de l'énoncé:

"Soit ϕ ∈ F formé avec ∧ ∨ ¬. Il existe une fonction équivalent ϕ' formé de ¬ ∨ uniquement tel que |ϕ'| ⩽ 2|ϕ|".
On démontre par induction structurelle :

Début:
Soit ϕ = p une formule atomique, alors on pose ϕ'= p = ϕ donc ϕ' = ϕ et |ϕ| = |ϕ'| <= 2|ϕ|.

Hérédité I:
Soit ϕ = ¬Ψ, par hérédité, il existe une formule Ψ' = Ψ avec |Ψ'| <= 2|Ψ|.
On pose ϕ' = ¬Ψ'∈ F' et |ϕ'| = 1 + |Ψ'| <= 1+ 2|Ψ| <= 2(1+|Ψ|) = 2|ϕ|.

Hérédité II
Soit ϕ = (Ψ∨X), par hérédité, il existe Ψ' = Ψ et X'=X et |Ψ'| <= 2|Ψ| et |X'| <= 2|X|, on pose (Ψ'∨X') ∈ F'
alors |ϕ'| = 3 + |Ψ'| + |X'| <= 3 + 2(|Ψ| + |X|) = 3 + 2(|Ψ| + |X| + 3) - 6 = -3 + 2(|Ψ| + |X| + 3) <= 2|ϕ|

Hérédité III
Soit ϕ = (Ψ∧X), par hérédité, il existe Ψ' = Ψ et X'=X, Ψ' ∈ F' et X' ∈ F'.
on pose ϕ' = ¬(¬Ψ'∨¬X') alors |ϕ'| = 6 + |Ψ'| + |X'| <= 6+ 2(|Ψ| + |X|) = 2(|Ψ| + |X| + 3) = 2|ϕ|.

C'est un peu lourd à lire mais normalement, c'est une démonstration correcte.

[Resartus]

Bonjour,
Euh non, votre première intuition était la bonne : il ne faut pas compter les parenthèses, parce qu'elles ne sont pas forcément nécessaires dans Ψ∨X, dont la taille serait seulement de |Ψ| + |X|+1, et votre calcul dans heredité iii devient faux

Si on exclut les parenthèses, cela marchera, mais il faut être un peu plus "pingre" sur les majorations et montrer que |¬Ψ'|<=1+|Ψ'| *, puis |Ψ'∨X'|<=1+|Ψ'| + |X'| *
puis conclure sur |¬(¬Ψ∨¬X)| par rapport à |Ψ∨X|


*il n'y a pas forcément égalité, parce qu'il se peut qu'une simplification soit possible

[CotteB]

Justement, si on ne compte pas les parenthèse, l'inégalité devient fausse.
Après retour de mon professeur, il faut effectivement compte les parenthèse et considérer ϕ = (Ψ∨X).

[Resartus]

Bonjour,
Je sais bien qu'il faut appliquer les articles 1 (le prof a raison) et 2 (le prof a toujours raison), mais que penser alors
de l'expression parfaitement valide p∧q de taille 3 seulement (parenthèses non nécessaires)
qu'on ne peut exprimer que comme ¬(¬p∨¬q) (parenthèses là obligatoires) dont la taille est 8 (ce qui la dernière fois que j'ai vérifié était plus grand que 6)

Ou alors il faut admettre une règle additionnelle qui rend obligatoires certaines parenthèses et pas d'autres...

[CotteB]

Bonsoir,

Je suis bien d'accord avec vous, l'inégalité n'est pas valide pour une formule (valide) sans parenthèse.

Cependant, c'est une question posée par mon professeur en fin de cours en supplément des td pour nous entrainer. Il n'existe pas de corrigé pour cette question et je pense qu'il a lui même fait une erreur dans son énoncé. D'où le "non, il faut compter les parenthèses" pour que cela marche.

Je pense qu'un énoncé plus correct serait :
"Soit ϕ ∈ F formé avec ∧ ∨ ¬. Il existe une fonction équivalent ϕ' formé de ¬ ∨ uniquement tel que |ϕ'| ⩽ 3|ϕ|".

Ca si il existe une règle qui nous oblige à rajouter des parenthèses ça ne fait que complexifier le problème puisqu'il nous faudra ensuite rajouter des parenthèses pour ϕ'.