Ryan K

EXERCICE 1.On se propose de montrer que la hauteur de toute formule propositionnelle est strictement inféreieure à sa longueur. Considérons χ une propriété sur l’ensemble F des formules propositionnelles definie par χ(F) : ht[F] < lg[F]. Nous voulons montrer que cette propriété est vraie pour tout formule F. 1.1 Montrer que χ(F) est satisfait pour tout F ∈ V ar. 1.2 Soit F ∈ F tel que χ(F). Montrer que χ(∼ F). 1.3 Soient F, G ∈ F telles que χ(F) et χ(G). Montrer que ht[(F △ G)] < Sup(lg[F], lg[G]) + 1 < lg[F] + lg[G] + 3 = lg[(F △ G)]. 1.4 En déduire que la propriété χ est satisfaite pour toute formule propositionnelle. Et conclure.