Récurrence en logique

[alexis6]

Bonsoir,

Je reste dubitatif devant le texte suivant:

Supposons que l’on veuille vérifier une propriété P pour toute formule Q appartenant à l'ensemble des formules propositionnelles, on peut éventuellement le faire par récurrence. Le principe est le suivant : la première étape est de montrer que la propriété P est vérifiée pour toute variable propositionnelle ; l’étape d’induction consiste à prouver, d’une part, si une formule Q satisfait à la propriété P, il en est de même de ¬Q, et d’autre part, si deux formules Q et G satisfont à P, il en est de même des formules (QUG), (Q^G), (QssiG) et (QimpliqueG).

En gras ce que je ne comprends pas: comment si une formule vérifie une propriété, sa négation peut-elle également la vérifier? Et également que veut dire pour une proposition " vérifier une propriété " ?

Merci

[bolza]

Bonsoir,

Par curiosité, vois tu ceci dans le cadre scolaire ?

d'abord pour commencer, il faut s'apercevoir qu'ici on travaille un "niveau" au dessus.
c'est-à-dire que habituellement, en math vous travaillez sur des propositions qui
traitent d'objet mathématiques (nombre, fonction, etc).
Alors que là ce que vous manipulez ce sont des propositions qui traitent de ....
propositions.

dit autrement, en logique on n'étudie pas les propriétés des nombres, fonctions, ou autre,
mais on étudie les propriétés des propositions.

Pour répondre à ta question à propos de et , il ne faut pas se tromper de "niveau" :
i.e. par exemple un objet mathématiques ne peut pas vérifié à la fois la propositions et
la proposition .
Mais par contre et peuvent vérifier la même propriété.
Tu comprend la nuance ?

Par exemple si vérifie la propriété "être indécidable" alors vérifie aussi la même propriété. (En effet, si est indécidable, alors l'est aussi).
(Je m'aperçois que mon exemple n'est peut être pas parlant ^^' tu vois ce que c'est une proposition indécidable ? )

[Ben314]

Salut,
Un exemple éventuellement plus simple :
Tu veut par exemple montrer que n'importe quelle proposition, écrite à l'aide des "connecteurs" ET, OU, =>, <=>, et de la négation NON est "équivalente" à une proposition qui ne s'écrit qu'à l'aide du connecteur ET et de la négation NON.

Pour le rédiger proprement, tu va effectivement faire une récurrence sur la longueur de la proposition et faire exactement ce que tu as écrit dans ton premier post.

Et, concernant ton "étonnement", dans un cas comme celui là, tu voit bien que, si P est "équivalente" à une proposition P' ne contenant que des ET et des NON alors la négation de P est "équivalente" à celle de P' qui ne contient que des ET et des NON.

P.S. Il ne faudrait pas écrire que P est "équivalente" à P' (d'où les guillemets) pour ne pas confondre avec le symbole <=> que l'on utilise à l'intérieur même des proposition, mais un truc du style "à la même valeur de vérité que" ou autre chose.

[alexis6]

Merci, c'est déjà plus clair. Finalement c'est une propriété "formelle" à chaque fois, d'accord.

Je vais essayer de faire celle de Ben314 alors...

Montrons par récurrence que n'importe quelle proposition, écrite à l'aide des "connecteurs" ET, OU, =>, <=>, et de la négation NON est "équivalente" à une proposition qui ne s'écrit qu'à l'aide du connecteur ET et de la négation NON.

Initialisation: Soit P une variable propositionnelle. P s'écrit aussi, dans tous les cas non(non(PetP)) donc seulement avec le connecteur ET et la négation NON.

Induction: Soit F et Q des formules propositionnelles, supposons qu'elles puissent s'écrire uniquement avec le connecteur ET et la négation non. Alors:
- non(F) ne s'écrit également qu'avec la négation NON et le connecteur ET
- (F ou Q) équivaut à non(non(F) et non(Q))
- (F et Q) s'écrit également qu'avec le connecteur ET et la négation NON.
- (F --> Q) équivaut à non(non( F-->Q )) qui équivaut à non( F et non(Q))
- (F <-->* Q) équivaut à ((F et Q) ou (non(F) et non(Q)) équivaut à (non(F et Q) et non(non(F) et non(Q))

* je fais la différence entre "équivaut à" et <-->, comme précisé dans le message de Ben

Pour continuer, en fait je ne sais pas si j'ai juste ( et je demande confirmation ), mais il me semble que ce nom de récurrence provient en fait de la construction même de l'ensemble des formules propositionnelles F.

On pose F0 = P ( l'ensemble des variables propositionnelles )
et Fn+1 = Fn U { non(Q) tel que Q appartient à Fn } U { (F ou Q) , ( F et Q ), ( F --> Q ), (F<-->Q) tq F,Q appartiennent à Fn }

et F l'union pour n > 0 des Fn.

Donc effectivement avec cette définition, si la propriété est vérifiée sur F0, et que de plus, si elle est vérifiée en Fn elle est vérifiée en Fn+1, alors d'après le principe de récurrence ( le vrai ), elle est vérifiée sur F.

Sinon, je ne vois pas ça dans le cadre scolaire bien qu'étant dans le supérieur. J'ai posté dans le forum lycée pensant que ce que je demandais était un peu trivial pour le forum de sup.

[Ben314]

Perso, ça me va.

Il y a juste quelques détails :
- Au départ tu te fait c... pour rien avec tes non(non(P et P)), mais je pense que c'est lié au fait que tu n'est pas habitué aux "convention de langage" des matheux : pour moi l'expression "avec uniquement des ET et des NON", ça voulait seulement dire qu'il ne doit pas y avoir d'autres connecteurs, mais qu'il peut éventuellement ne pas y avoir de NON ni de ET donc l'amorce, il n'y a rien à faire vu qu'il n'y a aucun connecteurs au départ.
- Ensuite, dans la rédaction, on peut éventuellement distinguer les proposition "de départ" avec des connecteurs quelconques de celle "d'arrivé" qui ne contiennent plus que des ET et des NON : elle sont "équivalentes" (="même valeur de vérité"), mais on peut (éventuellement) les voir comme distinctes dans le sens que ce ne sont pas les même suites de lettres.
Dans ce cas là, il faut rédiger légèrement différemment en écrivant des trucs du style :
Si P est "équivalente" à P' (avec que des ET et des NON) et que Q est "équivalente" à Q' (idem) alors (P ou Q) est "équivalente" à NON(NON(P') ET NON(Q')) qui ne contient que des ET et des NON.

Ca donne l'impression d'être un peu plus "carré carré" comme preuve, et surtout, ça ressemble un peu plus à l'idée qu'on se fait d'une récurrence où on réutilise bien les hypothèses de départ.
Mais, bon, ça change pas vraiment "l'essence" de la preuve...

[alexis6]

Encore merci ( et oui je l'écris dans tous mes messages ) pour ces précisions et l'implication ( sans jeu de mot bien sûr ) que vous avez pour m'aider à comprendre.